Abstract
dc:description.abstractImproving the performance of collective communication---algorithms for coordinated data movement in distributed computing---becomes increasingly important as the use of large-scale machine learning clusters continues to grow. In this work, we introduce techniques for synthesizing optimal algorithms for collective communication for any given host and network topology. We provide a novel multicommodity flow-based approach that allows us to find provably optimal algorithms in terms of both latency and bandwidth utilization. Critical to our techniques are two important innovations: a conversion method from fluid solutions to discrete step-based solutions, and Mirrored Dantzig-Wolfe, which exploits the high degree of symmetry often present in communication networks. We complement our theoretical contributions with experimental results, demonstrating the practical efficacy of the constructed algorithms.
Degree
thesis:*- Name thesis:degree_name
- Ph. D., Operations Research and Information Engineering
- Level thesis:degree_level
- Doctor of Philosophy
- Discipline thesis:degree_discipline
- Operations Research and Information Engineering
- Grantor
- Cornell University
- Year dc:date.issued
- 2025
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Shapley, Richard
- Chair dc:contributor.chair
-
- Shmoys, David
- Committee members dc:contributor.committeemember
-
- Banerjee, Siddhartha
- Williamson, David
Subjects
dc:subject × 4Rights
dc:rights- Statement dc:rights
-
- Attribution 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Dc Identifier Bibid
- 17422614
- Dc Identifier Other
-
ProQuest Submission ID: 15258
ProQuest Publication ID: 32171531