Search

Combinatorial algorithms in general and graph algorithms in particular play a critical enabling role in numerous scientific applications. However, the irregular memory access nature of these algorithms makes them one of the hardest algorithmic kernels to implement on parallel systems. With tens of billions of hardware threads and deep memory hierarchies, the exascale computing systems in particular pose extreme challenges in scaling graph algorithms. The codesign center on combinatorial algorithms, ExaGraph, was established to design and develop methods and techniques for efficient implementation of key combinatorial (graph) algorithms chosen from a diverse set of exascale applications. Algebraic and combinatorial methods have a complementary role in the advancement of computational science and engineering, including playing an enabling role on each other. In this paper, we survey the algorithmic and software development activities performed under the auspices of ExaGraph from both a combinatorial and an algebraic perspective. In particular, we detail our recent efforts in porting the algorithms to manycore accelerator (GPU) architectures. We also provide a brief survey of the applications that have benefited from the scalable implementations of different combinatorial algorithms to enable scientific discovery at scale. We believe that several applications will benefit from the algorithmic and software tools developed by the ExaGraph team.

In this research, we investigated two approaches to detect job anomalies and/or contention for large scale computing efforts: 1. Preemptive job scheduling using binomial classification long short-term memory networks 2. Forecasting intra-node computing loads from the active jobs and additional job(s) For approach 1, we achieved a 14% improvement in computational resources utilization and an overall classification accuracy of 85% on real tasks executed in a High Energy Physics computing workflow. For this paper, we present the preliminary results used in second approach.

Distributed-memory graph algorithms are fundamental enablers in scientific computing and analytics workflows. A majority of graph algorithms rely on the graph neighborhood communication pattern, i.e., repeated asynchronous communication between a vertex and its neighbors in the graph. The pattern is adversarial for communication software and hardware due to high message injection rates and input-dependent, many-to-one traffic with variable destinations and volumes. We present benchmarks and performance analysis of graph neighborhood communication on modern large-scale network interconnects from four supercomputers: ALCF Theta, NERSC Cori, OLCF Summit and R-CCS Fugaku. Our benchmarks characterize communication from the perspectives of latency and throughput. Benchmark parameters make it possible to mimic the behaviors of complex applications on real world or synthetic graphs by varying work distribution, remote edges, message volume, and per-vertex work. We find that minor changes in the input graph can substantially increase latencies; and contention can develop in memory caches and network stacks before contention in the network itself. Further, latencies and contention vary significantly for different graph neighborhoods, motivating the need for exploring asynchronous algorithms in greater detail. When adding work, load imbalance on real-world graphs can be pronounced: latencies for the 99th percentile were 8–128× than the corresponding average latencies. Our results help analysts and developers understand the performance implications of this important pattern, especially for the impending exascale platforms. [ABSTRACT FROM AUTHOR]

The OpenAD/F tool allows the evaluation of derivatives of functions defined by a Fortran program. The derivative evaluation is performed by a Fortran code resulting from the analysis and transformation of the original program that defines the function of interest. OpenAD/F has been designed with a particular emphasis on modularity, flexibility, and the use of open source components. While the code transformation follows the basic principles of automatic differentiation, the tool implements new algorithmic approaches at various levels, for example, for basic block preaccumulation and call graph reversal. Unlike most other automatic differentiation tools, OpenAD/F uses components provided by the OpenAD framework, which supports a comparatively easy extension of the code transformations in a language-independent fashion. It uses code analysis results implemented in the OpenAnalysis component. The interface to the language-independent transformation engine is an XML-based format, specified through an XML schema. The implemented transformation algorithms allow efficient derivative computations using locally optimized cross-country sequences of vertex, edge, and face elimination steps. Specifically, for the generation of adjoint codes, OpenAD/F supports various code reversal schemes with hierarchical checkpointing at the subroutine level. As an example from geophysical fluid dynamics, a nonlinear time-dependent scalable, yet simple, barotropic ocean model is considered. OpenAD/F's reverse mode is applied to compute sensitivities of some of the model's transport properties with respect to gridded fields such as bottom topography as independent (control) variables. Categories and Subject Descriptors: G.1.4 [Numerical Analysis]: --Automatic differentiation; D.3.4 [Programming Languages]: --Code generation, Compilers; F.3.2 [Logics and Meanings of Program]: Semantics of Programming Languages Program analysis; G. 1.6 [Numerical Analysis]: --Gradient methods General Terms: Algorithms, Performance Additional Key Words and Phrases: Automatic differentiation, source transformation, adjoint compiler