Vector Execution of Flow Graphs
H. Raymond Strong · Journal of the ACM · 1983
Cons~deraUon ~s given to the optunal scheduling of an SIMD (Single Instrucuon Multiple Data) machine that ~s a set of processors synchronized at the instruction level so that only one mstrucuon may be executed at a time, but that instrucuon may be executed by all or any subset of the set of processors Each processor is assumed to be executing the same program; however, since each Is operatmg on different data, each may take a different path through that program.A scheduler decides at each point m tune wluch instruction to execute next without knowledge of the future paths through the program that each processor wall take An optunal scheduler would schedule these execuuons to minimize the total execution tune (number of instructions executed).Programs for which such an opttmal scheduler exists are characterized by graph-theoreuc properties of the corresponding flow graph: They are exactly the reducible flow graphs w~th only disJoint cycles.Scheduling methods based on pnoray ordering and node listing are compared as to worst-case behavior on programs for which no optunal scheduler exists Categories and Subject Descriptors: C.1.