Title :
A decentralized task scheduling algorithm and its performance modeling for computer networks
Author :
Ahmad, Ishfaq ; Ghafoor, Arif ; Mehrotra, Kishan
Author_Institution :
Sch. of Comput. & Inf. Sci., Syracuse Univ., NY, USA
Abstract :
A dynamic task scheduling algorithm is presented. The algorithm is an extension of a nearest neighbor load balancing strategy with an enhanced degree of efficiency and it is intended for multicomputers connected by a store and forward communication network. The algorithm is modeled by a central server open queueing network. It is shown that the response time of a task consists of two parts. The first part comprises a task´s settling time which consists of scheduling time, communication time, and waiting time. The second part comprises waiting time in the execution queue in the execution time itself. The algorithm is comprehensively evaluated through a simulation and analytical model, and is shown to be both stable and efficient. For performance evaluation, the task transfer cost and the scheduling overhead is also taken into account. Experimental results are also obtained for another nearest neighbor scheduling scheme and compared with the algorithm
Keywords :
computer networks; distributed algorithms; parallel machines; performance evaluation; queueing theory; resource allocation; scheduling; central server open queueing network; communication network; communication time; computer networks; decentralized task scheduling algorithm; dynamic task scheduling algorithm; execution queue; multicomputers; nearest neighbor load balancing; performance evaluation; performance modeling; response time; scheduling queues; scheduling time; settling time; store and forward; task transfer cost; waiting time; Analytical models; Computer networks; Costs; Delay; Load management; Nearest neighbor searches; Network servers; Performance analysis; Queueing analysis; Scheduling algorithm;
Conference_Titel :
Parallel and Distributed Processing, 1991. Proceedings of the Third IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2310-1
DOI :
10.1109/SPDP.1991.218225