Nested Loop Tiling for Distributed Memory Machines
Jagannathan Ramanujam, Ponnuswamy Sadayappan · 2005
This paper addresses the problem of compiling nested loops for distributed memory machines. The relatively high communication start-up costs in these machines renders frequent communication very expensive. Motivated by this, we present a method for aggregating a number of loop iterations into tiles where the tiles execute atomically - a processor executing the iteration belonging to a tile receives all the data it needs before executing any one of the iterations in the tile, executes all the iterations in the tile and then sends the data needed by other processors. Since synchronizations are not allowed during the execution of a tile, partitioning the iterations into tiles must not lead to deadlock. Given a perfectly nested loop to be executed on a multicomputer with given execution and communication costs, the tile shape and size have to be chosen to optimize the performance; in addition, the tiles must be assigned to processors to minimize communication costs and reduce processor idle times. We present an approach to determine the shape, size, allocation and scheduling of tiles for 2-level nested loops on distributed memory machines.