Efficient task scheduling and allocation for two-dimensional mesh-connected parallel systems.

摘要

Recently task scheduling and allocation in two-dimensional (2D) mesh-connected parallel computers have drawn a lot of attention in the research community. This is because the 2D mesh topology has become popular among various interconnection topologies developed for parallel and distributed computing, and task scheduling and allocation are critical processes to the performance of parallel computers. In this dissertation, new approaches for task scheduling and allocation in 2D meshes which allow high performance at low overhead are presented.; First, an efficient task allocation scheme is presented. By employing a new approach for searching the array, the proposed scheme can find the available submesh without the scanning of the entire 2D array unlike earlier designs. As a result, the proposed scheme can significantly reduce the task allocation time. Comprehensive computer simulation reveals that the average allocation time and waiting delay are much smaller than earlier schemes irrespective of the size and distribution of requested meshes. The scheme is also shown to be easily applied to tori architecture.; Next, two relocation schemes--full relocation and partial relocation scheme--are presented to alleviate external fragmentation. The former is desirable when the system is highly fragmented, while the latter is for minimizing the number of relocated tasks. For the relocation process, two basic submesh movement operations--shifting and rotating--are formally defined and used. The proposed schemes turn out to be beneficial when the relocation overhead is not high, which is machine dependent.; An efficient scheduling scheme is then proposed. By employing the largest job first and scan-all policy along with the waiting time limit, the proposed scheme can also alleviate the external fragmentation problem. Contrary to the previous largest-job-first only scheduling schemes, larger jobs do not block smaller jobs in our scheme. As a result, the mean response time is significantly reduced as identified by computer simulation. In addition to this, an on-line scheduling and allocation scheme is proposed for real-time sporadic tasks. By effectively manipulating the information on allocated or reserved submeshes, the proposed scheme can quickly identify the earliest available time of a free submesh for a newly-arrived task. A preemption approach is employed to reduce the complexity of the search for a feasible schedule. Computer simulation reveals that the proposed scheme significantly improves the system performance by decreasing the number of tasks rejected.