Cyclotron compiles streaming algorithms into efficient distributed processor programs
Cyclotron: A Recurrence Language for Expressing Interprocessor Communication
Distributed, Parallel, and Cluster Computing
Summary
Many programs need to split work across multiple computers or processors, making sure the parts talk to each other efficiently. The authors created Cyclotron, a tool that lets programmers describe complex data sharing in these programs using simple equations. Cyclotron then turns these equations into instructions for each processor to send and receive data correctly. This approach means programmers can change how computations are split across processors without rewriting everything. Tests showed Cyclotron matches or beats popular existing software on large matrix calculations.
What this means in practice
- •For high performance computing teams: Generate tailored programs for efficient communication patterns in distributed numerical algorithms on clusters and GPUs.
- •For software engineers in scientific computing: Simplify coding and adapting complex distributed linear algebra methods without rewriting code for different processors arrangements.
Authors
Shiv Sundram, Akhilesh Balasingam, Nathan Zhang, Kunle Olukotun, Fredrik Kjolstad
Abstract
We present Cyclotron, a compiler that expresses streaming dataflow algorithms using recurrence equations, which are then compiled to distributed topologies of interlinked processors. Our compiler lowers a language of recurrences over logical iteration spaces into per-processor programs of sends, receives, and computations. In these recurrences, data accesses are not limited to external accesses to memory; data can live separately on the iteration space itself, allowing internal points to communicate values directly with other points. Users specify this communication directly in the recurrence language, which allows them to express various communication patterns such as a nearest-neighbor systolic exchange, a one-to-all broadcast, a bidirectional split ring, or an asymmetric and piecewise broadcast pattern, which are often not supported by standard distributed linear algebra libraries. These recurrences describe the algorithm and communication independently of how they map onto the hardware. A programmer then chooses which dimensions execute across processors and which execute over time, without rewriting the entire program. Users only specify data dependencies across the iteration space, and the compiler safely generates a program, per process, with correct placement of both communication and computational operators according to the chosen space--time mapping. We evaluate distributed matrix multiplication, TRSM, Cholesky, and fused Cholesky--TRSM on up to 16 CPU nodes and 16 GPUs, comparing against ScaLAPACK, SLATE, and cuSolverMp. Cyclotron is competitive with and often outperforms these hand-optimized libraries; for Cholesky, the best communication strategy changes with problem size and architecture.