Compiling for NUMA Parallel Machines

Wei Li

Department of Computer Science University of Rochester

Abstract

A common feature of many scalable parallel machines is non-uniform memory access (NUMA). A parallelizing compiler for NUMA parallel machines must exploit both parallelism and data locality.

In this talk, we present Pnuma, a parallelizing compiler for sharedmemory parallel machines like the KSR1 and the BBN Butterfly. The input to this system is a sequential program with user-specified data distributions. We propose a systematic loop transformation method called access normalization that improves data locality, and reduces communication overhead by exploiting block transfers.

To facilitate the systematic development of program transformations, we have developed a framework based on matrix algebra and integer lattice theory. This framework solves the so-called ‘phase-ordering problem’ for an important set of loop transformations, and it can be used in parallelizing compilers for both coarse-grain and fine-grain parallel architectures. We discuss both the framework and its implementation – the Lambda loop-restructuring toolkit.

System evaluations have been conducted on a multiprocessor machine without cache (BBN GP1000), a uniprocessor workstation with cache (HP 9000/720) and a multiprocessor machine with caches (KSR1).