Automatic mapping of multi-stage algorithms onto distributed memory systems
Yin‐Tsung Hwang · 1993
Algorithm mapping is a systematic method to derive implementations of computing algorithms on multiprocessor systems. In this thesis, we present a multi-stage algorithm (MSA) mapping scheme which maps algorithms containing more than one nested DO loop onto a fixed-size distributed memory system. New challenges arise from the MSA mapping problem. These include issues like interface matching, computation overlap, tiling, data migration, partitioning and scheduling problems. These issues, if not handled properly, can degrade the overall performance significantly. In this thesis, we first formulate the interface matching and computation overlap problems by establishing a set of formal conditions. We also develop procedures to derive the interface matched mappings and to calculate the maximum period for computation overlap. To reduce the inter-processor communication overhead, we then address the tiling problem. Powerful schemes to test and generate valid tilings are proposed. Discussion on the optimality of tiling is also provided. With regard to the partitioning problem, a new partitioning model is proposed to incorporate the existing partitioning schemes into a unified frame-work. A novel two-level hierarchical scheduling scheme, capable of handling non-atomic partitioning, is then developed. This scheme has been shown to outperform the existing schemes and can relieve the data migration overhead. Finally, the entire mapping problem is formulated as an optimization problem and is solved by a best-first search algorithm. By incorporating these new results, we developed an automated mapping tool, called MSSM, which demonstrates the potential use of the proposed techniques.