Access based data decomposition fam distributed memory machines
Jagannathan Ramanujam, Ponnuswamy Sadayappan · 2005
This paper addresses the problem of partitioning data for distributed memory machines or multicomputer. 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.