Chain grouping: A method for partitioning loops onto mesh-connected processor arrays

This paper presents Chain Grouping, a new low complexity method for the pro blem of partitioning the loop iteration space into groups with little inter communication requirements, for mapping onto mesh-connected architectures. First, the iterations are scheduled in time, according to the hyperplane me thod, taking into consideration the minimum time displacement. Then, the it eration space is divided into discrete groups of related iterations, which are assigned to different processors, while preserving the optimal completi on time. Chain Grouping is based on clustering together neighboring uniform chains of iterations, formed by a particular dependence vector. This vecto r will be proven as the best among all to reduce the total communication re quirements. Inside every group, the optimal hyperplane scheduling is preser ved and references to intragroup iterations are considerably increased. The partitioned groups are afterward assigned to meshes of processors. The res ulting space mapping maximizes processor utilization and cuts down overall communication delays while preserving the optimal hyperplane time schedule.