Loop Transformations for NUMA Machines

this paper, we describe a framework for loop transformations and code generation for NUMA (non-uniform memory access) machines. Most scalable parallel machines can be classified as NUMA machines because a processor can access data in its local memory ten to a thousand times faster than it can access non-local data. In addition, when a processor must make a number of accesses to data residing at a remote processor, it is usually more efficient to use block transfers of data rather than to use many small messages. Furthermore, each processor usually has a data cache. A system for programming these machines must tackle the following challenges: (1) expose and exploit parallelism in programs, (2) manage data to avoid making non-local accesses, (3) use block transfers to amortize the cost of non-local accesses, and (4) exploit data reuse. Program transformations, such as loop restructuring, are critical to achieving these goals. We have developed a framework based on non-singular matrices for the systematic development of loop transformations [9]. The main benefit of this framework is that it provides an approach to tackling the so-called `phase-ordering problem' --- for many problems where there is no obvious order in which the transformations should be performed, it is often possible to generate a non-singular matrix from which the desired order of loop transformations can be determined easily. This framework can be used in parallelizing compilers for MIMD machines as well as in compilers for fine-grain parallel architectures such as VLIW and superscalar machines. We have implemented a loop restructuring tool-kit called Lambda based on this framework, which will be made publicly available. We are using this loop transformation framework in Pnuma which is a parallelizing co..