An Efficient Task Scheduling Scheme for Mesh Multicomputers

Oh Han KANG  

IEICE TRANSACTIONS on Information and Systems   Vol.E80-D   No.6   pp.646-652
Publication Date: 1997/06/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Systems
task scheduling,  multiprocessor,  fragmentation,  mesh multicomputers,  submesh allocation,  

Full Text: PDF>>
Buy this Article

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.