Scheduling variable-width parallelism on workstation clusters

A network of workstations, or workstation cluster, consists of a group of possibly heterogeneous machines each of which supports timesharing and may integrate multiple processors sharing a common memory. Compiler techniques developed for such a system, in conjunction with static load balancing across the cluster, can improve the overall cluster throughput. In addition, a dynamic task scheduler which allocates processors to jobs in proportion to their individual parallelism width can reduce job turnaround times on each individual machine. This thesis shows that a combination of compiler technology, hardware information, and dynamic task scheduling within each workstation can yield good cluster performance when loads are statically balanced across the cluster. It proposes a new dynamic task scheduling algorithm called PASS, and compares its performance with some other scheduling schemes within a single shared-memory workstation. It also evaluates the merits of task migration across machines as a way to enhance processor allocation of individual jobs. This thesis shows that migration at the task level is not profitable when loads across the cluster are statically balanced. It concludes that for migration to be beneficial, entire jobs (not tasks of a job) should be migrated to remote machines, and even this should not be done unless there is a load imbalance within the cluster