Dynamic scheduling and allocation in two-dimensional mesh-connected multicomputers for real-time tasks

Among several multiprocessor topologies, two-dimensional (2D) mesh topology has become popular due to its simplicity and efficiency. Even though a num ber of scheduling and processor allocation schemes for 2D meshes have been proposed in the literature, little study has been done aimed for realtime e nvironment. In this paper, we propose an on-line scheduling and allocation scheme for real-time tasks that require the exclusive use of submeshes in 2 D mesh system. By effectively manipulating the information on allocated or reserved submeshes, the proposed scheme can quickly identify the earliest a vailable time of a free submesh for a newly arrived task. We employ a limit ed preemption approach to reduce the complexity of the search for a feasibl e schedule. Computer simulation reveals that the proposed scheme allows hig h throughput by decreasing the number of tasks rejected.