Fast Processor Allocation And Dynamic Scheduling For Mesh Multiprocessors

Processor allocation and task scheduling are two important aspects of partitionable multiprocessor systems. In earlier work, we studied the first-fit and the best-fit processor allocation strategies for mesh-connected systems and pointed out that the First-Come-First-Serve (FCFS) scheduling discipline is inefficient. In this study, we first develop a new first-fit allocation strategy, called the Area Tree (AT) strategy. It is implemented through a. hierarchical data structure used in image processing. Compared with the earlier strategies, the AT strategy runs faster while maintaining performance. Then we investigate the issue of dynamic task scheduling: for mesh systems and present scheduling disciplines for reducing the system response time and increasing the system utilization. Extensive simulation runs have been conducted to compare the performance of the different allocation strategies and various scheduling disciplines