Mapping of uniform dependence algorithm onto fixed size processor arrays
Z. Chen, Wentong Shang · 2002
The paper addresses the problem of mapping uniform dependence algorithms onto fixed size processor arrays. The optimal computation time of executing uniform dependence algorithm on a fixed size processor array is first discussed. A mapping and partitioning method for 2-dimensional algorithms (algorithms with doubly nested loops) which can achieve near optimal computation time is proposed. Necessary and sufficient conditions are presented for a given pair of schedule and partition to be time optimal. The inefficient utilization of processors is caused by the boundary time steps. For a given pair of schedule and partition vectors, the number of boundary time steps is identified. Also, the amount of external communication, which is the communication between blocks of a partition, by a given pair of schedule and partition vectors is studied. Issues concerning minimizing boundary time steps and external communication are discussed.>