Efficient communication algorithms for parallel computing platforms
Viktor K. Prasanna, Jinwoo Suh · 1999
High Performance Computing (HPC) platforms are used for various applications. In these platforms, processor speed has increased rapidly. However, data communication speed among processor, memory, and disk has not kept pace. Thus, efficient communication algorithms are critical for effective utilization of HPC platforms. Our work focuses on the design of efficient communication algorithms on HPC platforms. To design efficient communication algorithms, we first design a simple and accurate model of HPC platforms. We identify three main costs on HPC platforms: processor-processor, memory-disk, and processor-memory communication costs. Among these, we investigate the first two. We design communication algorithms using the above model. First, we develop a set of communication algorithms for the software task pipeline which consists of several stages of processors. The general communication for the software task pipeline is M-to-N K-block-cyclic communication, where M is the number of source processors, N is the number of destination processors, and K is the number of consecutive blocks that need to be sent to the same processor. Our algorithm for the communication reduces the number of communication steps to as small as lg(N/M + 1) whereas a previous serial communication takes MN communication steps. Our experimental results show that the number of processors required to process Synthetic Aperture Radar (SAR) data is reduced by as much as 50%. The second class of algorithms is memory-disk communication algorithms. In this research, several algorithms for memory-disk communications are designed: all-to-all broadcast communication and matrix transpose. The results show that the execution time of a matrix transpose on IBM SP2 is reduced by as much as 31.2% when the data size is 64 MBytes and the number of processors is one. The execution time of the all-to-all broadcast communication is reduced by as much as 86% on SGI/Cray T3E when the number of processors is 64 and the data size is 256 KBytes per processor. Finally, several benchmarks that measure HPC performance are implemented. We choose a recently proposed benchmark to measure the real-time performance. We implement it using our communication algorithms and the previous serial algorithm. Also, we implement our low-level benchmark on HPC platforms.