range of computer systems, including general-purpose systems and many real-time systems in which some of the above information is not available. Our focus in this paper is on dynamic scheduling.
A dynamic scheduler for a hypercube system can be divided into two components: a job scheduler and a processor allocator. Job scheduling is concerned with choosing the next job to which processors will be allocated, while processor allocation is concerned with choosing a subcube to assign to that job. 2 An earlier study [12] compared the relative importance of these two components in achieving good performance on hypercube computers. This study showed that when the workload consists of jobs having no scheduling constraints, job scheduling is much more important than processor allocation. In particular, a new job scheduling discipline called Scan was shown to be far better able to improve performance than even an optimal processor allocation strategy, while carrying less overhead than even the simplest processor allocation strategy. In addition, the Scan discipline was shown to dramatically improve performance relative to previously studied job scheduling disciplines, such as First-Come-First-Served and Shortest-Job-First. Scan scheduling achieves this performance advantage by carefully ordering job executions in such a way that the hypercube is efficiently ''packed,'' reducing external fragmentation. Though this paper focuses on hypercube systems, Scan has been shown to have similar advantages for mesh-connected multiprocessors [1].
An important weakness in these results is that, while they are based on the assumption that jobs have no scheduling constraints, such constraints are not uncommon in practice. As a result, a job scheduler may not have complete freedom to set job execution order, so it may have limited ability to affect performance. Two important types of scheduling constraints are precedence and priority constraints. A precedence constraint disallows a job from beginning execution until the jobs on which it depends have completed. 2 We assume that the size of the subcube necessary to accommodate a given job has been determined before it is submitted to the system. Research that addresses this step includes [4,17].