Bilkent University
Department of Computer Engineering
MS THESIS PRESENTATION
Send Volume Balancing in Reduce Operations
Muhammed Çavuşoğlu
MS Student
(Supervisor: Prof. Dr. Cevdet Aykanat)
Computer Engineering Department
Bilkent University
We investigate balancing send volume in applications that involve reduce operations. In such applications, a given computational-task-to-processor mapping produces partial results generated by processors to be reduced possibly by other processors, thus incurring inter-processor communication. We define the reduce communication task assignment problem as assigning the reduce communication tasks to processors in a way that minimizes the send volume load of the maximally loaded processor. We propose one novel independent-task-assignment-based algorithm and four novel bin-packing-based algorithms to solve the reduce communication task assignment problem. We validate our proposed algorithms on two kernel operations: sparse matrix-sparse matrix multiplication (SpGEMM) and sparse matrix-matrix multiplication (SpMM). Experimental results show improvements of up to 23% on average for the maximum communication volume cost metric in SpGEMM and up to 12% improvement on average in SpMM.
DATE: 20 July 2020, Monday @ 11:00