| Bulk Synchronous Parallel Scheduling of Uniform Dags (1996) | |||||||||||||||||
Abstract | |||||||||||||||||
| . This paper addresses the dag scheduling problem, proposing the bulk synchronous parallel (BSP) model as a framework for the derivation of general purpose parallel computer schedules of uniform dags, i.e., of dags that stand for tightly-nested loops with computable distance vectors. A general technique for the BSP scheduling of normalised uniform dags is introduced and analysed in terms of the BSP cost model, and methods for the normalisation of generic uniform dags are briefly overviewed in the paper. 1 Introduction During the last two decades a great deal of research effort has been devoted to the identification and scheduling of potential parallelism. Despite the criticism pointing out its slow pace of progress, this research has led to remarkable advances. Data dependence analysis [2], loop transformation [1, 13], potential parallelism identification [6, 13], and dag scheduling [4, 7] are but a few examples of fields whose tremendous development has provided techniques successful... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||