Vector execution of flow graphs (extended abstract)

Abstract

Given a vector of tasks intended to execute the same program simultaneously on a machine which can execute only one instruction at a time, but can execute that instruction for any specified subset of the vector, the object is to schedule the execution to take maximal advantage of parallelism. Such a scheduling is called a vector execution scheme. A class of "perfect" programs is characterized for which such scheduling is easy and on which many vector execution schemes are optimal. This characterization shows that scheduling difficulties arise from unrestricted use of gotos producing irreducible programs, from branches in loops, and from nested loops. Once the path through the program is known for each task, it is a finite problem to find an optimal schedule; so there is an optimal vector execution scheme, even over imperfect programs. However, there is no implementable vector execution scheme which does not make use of knowledge of the future and which is optimal with respect to length of execution sequences. Some implementable vector execution schemes based on priority ordering and node sequence approaches are studied and compared as to worst case behavior on imperfect programs.