Abstract
Consideration is given to the optunal scheduling of an SIMD (Single Instrucuon Multiple Data) machine that is 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 with 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. © 1983, ACM. All rights reserved.