Dynamic Scheduling and Allocation in Two-Dimensional Mesh-Connected Multicomputers for Real-Time Tasks

Seong-Moo YOO  Hee Yong YOUN  Hyunseung CHOO  

IEICE TRANSACTIONS on Information and Systems   Vol.E84-D   No.5   pp.613-622
Publication Date: 2001/05/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Systems
2D meshes,  earliest available time,  free/reserved submeshes,  on-line scheduling and allocation,  

Full Text: PDF(603.1KB)>>
Buy this Article

Among several multiprocessor topologies, two-dimensional (2D) mesh topology has become popular due to its simplicity and efficiency. Even though a number of scheduling and processor allocation schemes for 2D meshes have been proposed in the literature, little study has been done aimed for real-time environment. In this paper, we propose an on-line scheduling and allocation scheme for real-time tasks that require the exclusive use of submeshes in 2D mesh system. 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. We employ a limited preemption approach to reduce the complexity of the search for a feasible schedule. Computer simulation reveals that the proposed scheme allows high throughput by decreasing the number of tasks rejected.