A Load Balanced Scheduler for PVM Jobs

José Nagib Cotrim Árabe (1)
Virgilio Augusto Fernades Almeida (2)

Departamento de Ciência da Computação
Universidade Federal de Minas Gerais
30161-970 Belo Horizonte, Brazil


We present the design and implementation of a distributed dynamic scheduler for PVM jobs on a network of workstations. The scheduler has the objectives of maintaining a balanced system-wide workload and reducing the average execution time for the jobs. It uses sender-initiated algorithms to perform global assignment of tasks to the nodes of the system. Each node runs an identical copy of the scheduling function, without a master node. The system was implemented through two daemons that run at each workstation. One function of the scheduler is to collect load information at each node and periodically exchange this information with the other nodes. The other function uses this global information to decide on which node to assign a new task, giving priority to less-loaded nodes. The load status is represented by a load index, which is a function of the number of processes in the ready queue, the fraction of idle time, and the processor speed. Four different scheduling policies were investigated. The first, implemented for comparison purposes, allocates the next processor of a circular list; it is the policy used by PVM. The second policy allocates the node with minimum load index. The third policy is a modification of the second to avoid overloading a processor in the case of fast arrival of tasks between load information exchanges. Finally, the last policy allows the user to specify priority for some tasks; these tasks are serviced first. Several experiments were carried out, with lightly and heavily-loaded nodes, to evaluate the scheduler on a heterogeneous network. A set of parallel applications - Harmonics summation, Bessel's equation and Matrix Multiplication - was developed to compose the workload. Results showing a significant reduction (from 20% to 60%) on the average execution time of the applications will be presented.

1. Partially supported by CNPq, Brazil. Currently, he is a Visiting Scholar at the School of Computer Science of Carnegie Mellon University (arabe@cs.cmu.edu).

2. Partially supported by CNPq, Brazil (virgilio@dcc.ufmg.br).