For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Efficient Task Scheduling Scheme for Mesh Multicomputers
Oh Han KANG
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1997/06/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Systems
task scheduling, multiprocessor, fragmentation, mesh multicomputers, submesh allocation,
Full Text: PDF>>
In this paper, we propose an efficient task scheduling scheme, called CTS (Class-based Task Scheduling), to obtain high performance in terms of high system utilization and low waiting times for tasks. While a better submesh allocation scheme can improve system performance, an allocation policy alone cannot improve performance significantly. This is due to the fact that the FCFS task scheduling policy leads to large external fragmentation. The CTS strategy maintains four separate queues, one for each incoming task class. This avoids the blacking property incurred in the FCFS scheduling. To reduce the external fragmentation, a job tends to wait for an occupied submesh of the same size instead of using a new submesh in the CTS strategy. Simulation results indicate that the proposed scheduling strategy improves the performance compared to the FCFS scheduling policy by reducing the average waiting delay significantly.