Tiling of Iteration Spaces for Multicomputers.
Jagannathan Ramanujam, Ponnuswamy Sadayappan · 1990
We deal with compiler support for parallelizing perfectly nested loops for coarse-grain distributed memory machines. The relatively high communication start-up costs in these machines renders frequent communication very expensive. We study the effect of clustering communication and the ensuing loss of parallelism on performance and propose a method for aggregating a number of loop iterations into "tiles" where the tiles execute atomically where there are no synchronizations to be performed during the execution of a tile. As a result, it is important that dividing the loops into tiles does not lead to deadlock. Based on conditions for deadlock-free tiles, we present a method for deriving legal tiles for nested loops. We then develop an approach to optimize the shape and size of tiles along with the assignment of tiles to processors for load-balanced execution with reduced communication costs on distributed memory machines given communication setup and transfer rates and instruction exec...