A UNIFIED PARTITIONING AND SCHEDULING SCHEME FOR MAPPING MULTISTAGE REGULAR ITERATIVE ALGORITHMS ONTO PROCESSOR ARRAYS

This paper addresses the partitioning and scheduling problems in mappi ng multi-stage regular iterative algorithms onto fixed size distribute d memory processor arrays. We first propose a versatile partitioning m odel which provides a unified framework to integrate various partition ing schemes such as ''locally sequential globally parallel'', ''locall y parallel globally sequential'' and ''multi-projection''. To alleviat e the run time data migration overhead-a crucial problem to the mappin g of multi-stage algorithms, we further relax the widely adopted atomi c partitioning constraint in our model such that a more flexible parti tioning scheme can be achieved. Based on this unified partitioning mod el, a novel hierarchical scheduling scheme which applies separate sche dules at different processor hierarchies is then developed. The schedu ling problem is then formulated into a set of ILP problem and solved b y the existing software package for optimal solutions. Examples indica te that our partitioning model is a superset of the existing schemes a nd the proposed hierarchical scheduling scheme can outperform the conv entional one-level linear schedule.