Bilkent University
Department of Computer Engineering

---

CS 590/690 SEMINAR

 

Iterative Improvement Heuristics for Reducing Communication Volume Overhead of STFW Scheme

 

Salih Deniz Uzel
Master Student
(Supervisor: Prof.Dr.Cevdet Aykanat)
Computer Engineering Department
Bilkent University

Abstract: Sparse matrix operations such as SpMV are latency bound applications where number of messages sent by processors dominate the overall communication overhead. Recently, Store and Forward (STFW) schemes are proposed to scale such fine-grain operations as SpMV. STFW schemes work on Virtual Process Topologies (VPTs). However, the STFW schemes incur an increase in the communication volume due to the STFW overhead. This increase in communication volume disturbs the scalability of the STFW scheme, especially in SpMM kernels where a sparse matrix is post-multiplied by a tall-and-skinny dense matrix. In this work, we propose a KL-based heuristic to improve the one-to-one mapping produced by the initial task partition. The objective of this heuristic is to reduce the increase in the communication volume to be incurred by the STFW scheme in SpMM type of kernels. We will discuss the KL algorithms proposed and implemented for improving STFW scheme on 1D, 2D, 3D and lg(K) dimensional VPTs and provide experimental performance comparison

 

DATE: March 11, Monday @ 14:10 Place: EA 502