Reducing data communication overhead for DOACROSS loop nests

Abstract

If the loop iterations of a loop nest cannot be partitioned into independent sets, the data communication for data dependences are inevitable in order to execute them on parallel machines. These kind of loop nests are referred to as DOACROSS loop nests. This paper is concerned with compiler algorithms for parallelizing DOACROSS loop nests for distributed-memory multicomputers. We present a method that combines loop tiling, chain-based scheduling and indirect message passing to generate efficient message-passing parallel codes. We present our experiment results on Fujitsu AP1000 which show that low communication overhead and high speedup for DOACROSS loop nests on multicomputers can be achieved by tuning these techniques.