Partitioning and mapping nested loops on multiprocessor systems

Citations Over TimeTop 10% of 1991 papers

Abstract

A method for executing nested loops with constant loop-carried dependencies in parallel on message-passing multiprocessor systems to reduce communication overhead is presented. In the partitioning phase, the nested loop is divided into blocks that reduce the interblock communication, without regard to the machine topology. The execution ordering of the iterations is defined by a given time function based on L. Lamport's (1974) hyperplane method. The iterations are then partitioned into blocks so that the execution ordering is not disturbed, and the amount of interblock communication is minimized. In the mapping phase, the partitioned blocks are mapped onto a fixed-size multiprocessor system in such a manner that the blocks that have to exchange data frequently are allocated to the same processor or neighboring processors. A heuristic mapping algorithm for hypercube machines is proposed.>

Related Papers

• → Reliability measure of multiprocessor system based on enhanced hypercubes(2020)26 cited
• → Volume of Hypercubes Clipped by Hyperplanes and Combinatorial Identities(2020)7 cited
• → Hybrid Fault diagnosis capability analysis of Hypercubes under the PMC model and MM* model(2017)2 cited
• → I/O issues for hypercubes(1989)1 cited
• → Volume of Hypercubes Clipped by Hyperplanes and Combinatorial Identities(2015)