LOOP COALESCING AND SCHEDULING FOR BARRIER MIMD ARCHITECTURES

作     者：OKEEFE, MT DIETZ, HG 

作者机构：PURDUE UNIVSCH ELECT ENGNW LAFAYETTEIN 47907 

出 版 物：《IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS》 (IEEE Trans Parallel Distrib Syst)

年 卷 期：1993年第4卷第9期

页      面：1060-1064页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation, NSF, (8624385-CDR) National Science Foundation, NSF 

主　　题：BARRIER SYNCHRONIZATION COMPILER OPTIMIZATION COMPILER PARALLELIZATION LOOP COALESCING LOOP TRANSFORMATION STATIC BARRIER MIMD 

摘      要：Barrier MIMD s are asynchronous multiple instruction stream, multiple data stream architectures capable of parallel execution of variable execution time instructions and arbitrary control flow (e.g., while loops and calls);however, they differ from conventional MIMD s in that the need for run-time synchronization is significantly reduced. This work considers the problem of scheduling nested loop structures on a barrier MIMD. The basic approach employs loop coalescing, a technique for transforming a multiply-nested loop into a single loop. Loop coalescing is extended to nested triangular loops, in which inner loop bounds are functions or outer loop indices. In addition, a more efficient scheme to generate the original loop indices from the coalesced index is proposed for the case of constant loop bounds. These results are general, and can be applied to extend previous work using loop coalescing techniques. We concentrate on using loop coalescing for scheduling barrier MIMDs, and show how previous work in loop transformations and linear scheduling theory can be applied to this problem.