When considering general matrix multiply (GEMM) algorithms for distributed-memory systems, the dominant paradigm is to minimize communication volume. However, to minimize time, one must consider how communication volume interacts with the system characteristics --- namely, communication bandwidth, memory capacity, and the co-scheduling of computation and communication. In this work, we demonstrate that the family of 3D GEMM algorithms --- although reducing overall communication by leveraging extra memory --- fundamentally concentrates communication to the phase of memory filling. This upfront cost hinders the ability to overlap communication with computation, and, consequently, calls for a revised view of the GEMM optimality regions. Our main contribution is derivation of optimality conditions for parallel matrix multiplication that jointly accounts for communication volume and overlap effects, pushing the 3D GEMM optimality region to start with the systems more than 11× larger than previously believed.

This paper presents a parameterized analytical performance model of transformer-based Large Language Models (LLMs) for guiding high-level algorithm-architecture codesign studies. This model derives from an extensive survey of performance optimizations that have been proposed for the training and inference of LLMs; the model's parameters capture application characteristics, the hardware system, and the space of implementation strategies. With such a model, we can systematically explore a joint space of hardware and software configurations to identify optimal system designs under given constraints, like the total amount of system memory. We implemented this model and methodology in a Python-based open-source tool called Calculon. Using it, we identified novel system designs that look significantly different from current inference and training systems, showing quantitatively the estimated potential to achieve higher efficiency, lower cost, and better scalability.

ParaGraph is an open-source toolkit for use in co-designing hardware and software for supercomputer-scale systems. It bridges an infrastructure gap between an application target and existing high-fidelity computer-network simulators. The first component of ParaGraph is a high-level graph representation of a parallel program, which a) faithfully represents parallelism and communication, b) can be extracted automatically from a compiler, and c) is “tuned” for use with network simulators. The second is a runtime that can emulate the representation’s dynamic execution for a simulator. User-extensible mechanisms are available for modeling on-node performance and transforming high-level communication into operations that backend simulators understand. Case studies include deep learning workloads that are extracted automatically from programs written in JAX and TensorFlow and interfaced with several event-driven network simulators. These studies show how system designers can use ParaGraph to build flexible end-to-end software-hardware co-design workflows to tweak communication libraries, find future hardware bottlenecks, and validate simulations with traces.

Kim and Vu made the following conjecture (Advances in Mathematics, 2004): if d ≫ log n, then the random d-regular graph (n, d) can asymptotically almost surely be “sandwiched” between (n, p1) and (n, p2) where p1 and p2 are both (1 + o(1))d/n. They proved this conjecture for log n ≪ d ≪ n1/3−o(1), with a defect in the sandwiching: (n, d) contains (n, p1) perfectly, but is not completely contained in (n, p2). Recently, the embedding (n, p1) ⊆ (n, d) was improved by Dudek, Frieze, Ruciński and Šileikis to d = o(n). In this paper, we prove Kim–Vu's sandwich conjecture, with perfect containment on both sides, for all . For , we prove a weaker version of the sandwich conjecture with p2 approximately equal to (d/n) log n, without any defect. In addition to sandwiching regular graphs, our results cover graphs whose degrees are asymptotically equal. The proofs rely on estimates for the probability that a random factor of a pseudorandom graph contains a given edge, which is of independent interest. As applications, we obtain new results on the properties of random graphs with given near-regular degree sequences, including Hamiltonicity and universality in subgraph containment. We also determine several graph parameters in these random graphs, such as the chromatic number, small subgraph counts, the diameter, and the independence number. We are also able to characterise many phase transitions in edge percolation on these random graphs, such as the threshold for the appearance of a giant component.

In efforts to increase performance and reduce cost, modern low-diameter networks are designed for average case traffic and rely on non-minimal adaptive routing for network load-balancing when adversarial traffic patterns are encountered. Source adaptive routing is the predominant method for adaptive routing even though it presents many deficiencies related to making global decisions based solely on local information. In contrast, incremental adaptive routing, which performs an adaptive decision at every hop, is able to increase throughput and reduce latency by overcoming the deficiencies of source adaptive routing. We present two incremental adaptive routing algorithms for HyperX which are the first to be fully implementable in modern high-radix router architectures and interconnection network protocols. Using cycle accurate simulations of a 4,096 node network, our evaluation shows these algorithms are able to exceed the performance of prior work by as much as 4x with synthetic traffic and 25% with 27-point stencil traffic.

The interconnection networks of modern largescale computing systems are quickly increasing in size and complexity to keep up with the demand for computing capability. These systems rely heavily on complex router microarchitectures and intelligent adaptive routing algorithms structured for cost-optimized low-diameter networks. These technologies need to be properly modeled and evaluated during design space exploration and for performance characterization of the system. We present SuperSim, an open-source flit-level interconnection network simulator that enables focused evaluation of issues related to designing and deploying large-scale highperformance networks. SuperSim is a programmer-centric simulation framework explicitly designed to be flexibly extended and is supported by a number of tools making it easy to use and allowing users to model systems quickly. In this work we show the results for simulation case studies demonstrating the power of SuperSim to uncover otherwise overlooked details in large-scale interconnection networks.