Microarchitecture support for dynamic scheduling of acyclic task graphs
Carl Beckmann, Constantine D. Polychronopoulos · ACM SIGMICRO newsletter/SIGMICRO newsletter/SIGMICRO, TCMICRO newsletter · 1992
It can be shown that any program can be broken into its loop structure, plus acyclic dependence graphs representing the body of each loop or subroutine. The parallelism inherent in these acyclic graphs augments the loop-level parallelism available in the program. This paper presents two algorithms for dynamic scheduling of such acyclic task graphs containing both data and control dependences, and describes a microarchitecture which implements these algorithms efficiently. Keywords-- Functional parallelism, fine-grain parallelism, microarchitecture, dynamic scheduling, parallelizing compiler. ############################# 1 This work was funded in part by NSF grant CCR 89-57310 PYI, DOE grant DE-FG0285ER25001, and a Shell Doctoral Fellowship (Carl Beckmann). - 2 - 1. Introduction Traditional approaches to parallel processing have focused largely on loop-level parallelism. Another source of parallelism in programs is non-loop, or functional, parallelism [Girk91]. While the amount o...