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
Abstract:
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).