Write a Blog >>
PPoPP 2021
Sat 27 February - Wed 3 March 2021
Mon 1 Mar 2021 11:10 - 11:25 - Session 2. Compilers, Analysis, Synthesis Chair(s): Milind Chabbi

Collective communication algorithms are an important component of distributed computation. Indeed, in the case of deep-learning, collective communication is the Amdahl’s bottleneck of data-parallel training.

This paper introduces SCCL (for Synthesized Collective Communication Library), a systematic approach to synthesizing collective communication algorithms that are explicitly tailored to a particular hardware topology. SCCL synthesizes algorithms along the Pareto-frontier spanning from latency-optimal to bandwidth-optimal implementations of a collective. The paper demonstrates how to encode the synthesis problem as a quantifier-free SMT formula which can be discharged to a theorem prover. We show how our carefully built encoding enables SCCL to scale.

We synthesize novel latency and bandwidth optimal algorithms not seen in the literature on two popular hardware topologies. We also show how SCCL efficiently lowers algorithms to implementations on two hardware architectures (NVIDIA and AMD) and demonstrate competitive performance with hand optimized collective communication libraries.

Conference Day
Mon 1 Mar

Displayed time zone: Eastern Time (US & Canada) change

11:10 - 12:10
Session 2. Compilers, Analysis, SynthesisMain Conference
Chair(s): Milind ChabbiUber Technologies
11:10
15m
Talk
Synthesizing Optimal Collective Algorithms
Main Conference
Zixian CaiAustralian National University, Zhengyang LiuUniversity of Utah, Saeed MalekiMicrosoft Research, Madan MusuvathiMicrosoft Research, Todd MytkowiczMicrosoft Research, Jacob NelsonMicrosoft Research, Olli SaarikiviMicrosoft Research, Redmond
Link to publication
11:25
15m
Talk
Parallel Binary Code Analysis
Main Conference
Xiaozhu MengRice University, Jonathon AndersonRice University, John Mellor-CrummeyRice University, Mark W. KrentelRice University, Barton P. MillerUniversity of Wisconsin - Madison, Srđan MilakovićRice University
Link to publication
11:40
15m
Talk
Compiler Support for Near Data Computing
Main Conference
Mahmut Taylan KandemirPenn State University, USA, Jihyun RyooPenn State University, USA, Xulong TangUniversity of Pittsburgh, USA, Mustafa KarakoyTUBITAK-BILGEM, Turkey
Link to publication
11:55
15m
Talk
Scaling Implicit Parallelism via Dynamic Control Replication
Main Conference
Michael BauerNVIDIA, Wonchan LeeNVIDIA, Elliott SlaughterSLAC National Accelerator Laboratory, Zhihao JiaCarnegie Mellon University, Mario Di RenzoSapienza University of Rome, Manolis PapadakisNVIDIA, Galen ShipmanLos Alamos National Laboratory, Patrick McCormickLos Alamos National Laboratory, Michael GarlandNVIDIA, Alex AikenStanford Univeristy
Link to publication