Bilkent University
Department of Computer Engineering
M.S.THESIS PRESENTATION
TWO OPTIMIZATION FRAMEWORKS FOR SCALING 1D PARALLEL APPLICATIONS WITH HETEROGENEOUS MESSAGING
Serdar Özata
Master Student
(Supervisor: Prof. Dr. Cevdet Aykanat )
Computer Engineering Department
Bilkent University
Abstract: Irregularly sparse applications on distributed-memory systems often exhibit highly nonuniform communication patterns, making communication bandwidth a major scalability bottleneck. This thesis proposes two complementary post-partition communication optimizations for such applications. The first contribution is an expand-task-sharing framework that balances process communication volume by redistributing part of an input owner’s communication responsibility to recipient processes. We also incorporate task sharing into minimum-vertex-cover-based heterogeneous messaging, which reduces total volume by combining expanded inputs with intermediate input-data results. In parallel SpMM experiments, the resulting scheme reduces the maximum process volume load by 72% and parallel runtime by 41% on average relative to conventional expand communication. The second contribution is an a posteriori partition-refinement framework that directly minimizes the communication volume induced by heterogeneous messaging. An FM-like heuristic evaluates vertex moves according to their effect on minimum-vertex-cover cardinalities of inter-process dependency bipartite graphs. Dulmage–Mendelsohn decomposition enables efficient gain computation and maintenance after accepted moves, with an O(E) update cost for an affected bipartite graph G = (V, E). Across 148 symmetric sparse matrices, 2048-way refined partitions reduce total communication volume by 58.6% and 53.1% relative to 1D METIS and 1D PaToH, respectively. On the largest instances on LUMI, these reductions yield approximately 30% lower parallel SpMM runtimes. Together, the proposed methods address both total volume and bottleneck process load in bandwidth-bound irregular sparse computations.
DATE: August 25, Tuesday @ 13:00
Place: EA 516