Access Based Data Decomposition for Distributed Memory Machines

This paper addresses the problem of partitioning data for distributed memory machines or multicomputers. If insufficient attention is paid to the data allocation problem, then the amount of time spent in interprocessor communication might be so high as to seriously undermine the benefits of parallelism. It is therefore worthwhile for a compiler to analyze patterns of data usage to determine allocation, in order to minimize interprocessor communication. We present a matrix notation to describe array accesses in fully parallel loops which lets us derive sufficient conditions for communication-free decomposition of arrays. 1 Introduction In distributed memory machines such as the Intel iPSC/2 and NCUBE, each process has its own address space and processes must communicate explicitly by sending and receiving messages. Communication in message passing machines could arise from the need to synchronize and from the non-locality of data. The impact of the absence of a globally shared memory ..