P. Evripidou et Jl. Gaudiot, BLOCK SCHEDULING OF ITERATIVE ALGORITHMS AND GRAPH-LEVEL PRIORITY SCHEDULING IN A SIMULATED DATA-FLOW MULTIPROCESSOR, IEEE transactions on parallel and distributed systems, 4(4), 1993, pp. 398-413
Citations number
22
Categorie Soggetti
System Science","Computer Applications & Cybernetics","Engineering, Eletrical & Electronic
While data-flow principles permit the utilization of large-scale multi
processor systems with high programmability and good efficiency, they
also introduce much overhead at runtime. In this paper, we have studie
d an important class of PDE solvers, namely iterative methods for solv
ing linear systems. Although these methods are inherently highly seque
ntial, we have found that much parallelism could be exploited in a dat
a-flow system by scheduling the iterative part of the algorithms in bl
ocks and by looking ahead across several iterations. This approach is
general and will apply to other iterative and loop-based problems. It
is also demonstrated by simulation means, that relying solely on data-
driven scheduling of parallel and unrolled loops results in low resour
ce utilization and poor performance. A graph-level priority scheduling
mechanism has been developed that drastically improves resource utili
zation and yields higher performance.