Effective dynamic scheduling and memory management on parallel processing systems

An effective dynamic processor self-scheduling scheme is presented for general parallel program constructs in a restructuring compiler. In the program constructs, parallel loops, serial loops, if-then-else constructs and a generalization of fork-joins can be nested in an arbitrary order, and procedure calls can be involved in any level of the nested constructs. In parallel programs, a piece of the program code, such as loop iterations, is called a chore, which is considered to be a work unit in the program. In this scheme, processors schedule themselves to the chores dynamically at execution time without involving the operating system. Memory management is another issue addressed. Efficiency concerns dictate treating chore locality differently from procedure locality. As a corollary, the number of call frames required at any one time for a nonrecursive procedure is bounded by the number of processors