A Comparison of Task Scheduling Algorithms on Multicomputers

For many years, the von Neumann bottleneck has imposed speed limits on the execution of a program. Because of their sequential nature, von Neumann computers can only execute a single instruction at a time. Instructions that are side-effect free and can be executed in parallel must wait. In an effort to overcome this bottleneck, multicomputers have been developed and implemented. These multicomputers are a new class of computers based on multiple processors. With multiple processors available, instructions can be processed in parallel. However, now interprocessor communication (IPC) delays must be taken into account. A program that is run on several processors may take longer to execute than if it were run on a single processor. The focus of the speed limits has now changed. The new focus now hinges on the efficient partitioning of a program and allocation of those partitions to processors. Several algorithms have been developed to solve the problem of partitioning and scheduling. Three algorithms were studied under uniform conditions to determine the efficiencies of each. They were Internalization, Balanced Layered Allocation Scheme (BLAS) and Dynamic Level Scheduling (DLS). Simulation studies indicate that BLAS performs the best overall. These algorithms based their communications costs on a simplified IPC cost model. A more realistic message grouping IPC model was developed to test the accuracy of the algorithms which are based on the simplified model. These simulation studies indicated that the simplified model was a fairly accurate gauge of a more realistic system