Data access optimizations for parallel computers
Ponnuswamy Sadayappan, N.S. Sundar · 1998
Parallel computers are increasingly used to deliver more computing power to demanding applications than is possible with uniprocessor systems. Another major trend affecting computer architecture is that processor speeds exceed memory speeds, with the differential increasing over time. This has led to the widespread use of cache memories to bridge the speed gap between processor and main memories. Cache-based scalable parallel computers, whether with a unified logical memory address space or a distributed address space, are characterized by a higher latency for remote data access compared to local data access. Hence it is important to minimize the number and amount of off-processor memory accesses. Methods and techniques to maximize data locality are, therefore, of great importance in parallel computing. This thesis explores issues in data locality in two different contexts. Firstly, on parallel systems with physically distributed memory, many existing applications need to perform collective communication to ensure data locality. Therefore, it is important to reduce the running time for these communication patterns. Complete exchange is an important pattern that arises in many commonly used applications. This study presents a new algorithm to perform complete exchange and shows that it can be effectively hybridized with existing algorithms to enhance performance. Secondly, automatic conversion of sequential numerical programs to a parallel form often produces programs that perform poorly due to lack of data locality. Manual conversion to a (MPI-based) message-passing model addresses performance but is tedious and error-prone. So, it is important to create a parallelizing methodology that eases manual implementation without compromising performance. This study proposes a methodology, for stencil computations that access their data with unit stride, which achieves ease of use by taking an incremental approach and by decoupling data distribution issues from communication issues. The resulting programs are demonstrated to scale well on many parallel architectures. Furthermore, on cache-based shared memory multiprocessors, the methodology enables an alternative to automatic parallelization and conversion to MPI, which can yield programs of performance comparable to MPI by exploiting data locality but takes less development effort. A performance study of the three approaches is presented to validate this conclusion.