SCHEDULING METHODS FOR EFFICIENT UTILIZATION OF CLUSTER COMPUTING
ENVIRONMENTS

Reda A. Ammar

Computer Science and Engineering Department

University of Connecticut

Scheduling a large number of applications on a cluster computing
environment is a serious obstacle to achieving good performance. This
becomes more critical in real time systems. Due to the NP-completeness
of the scheduling problem, most of the related work is based on heuristic
techniques with the objective of finding high performance solutions.

A cluster scheduler without enough knowledge of the cluster and
the scheduled tasks of given applications cannot adequately manage
the cluster resources. Consequently, the cluster resources may not be
utilized effectively. Much of the current allocation and scheduling
work dealing with real-time applications has not provided mechanisms
to satisfy the application performance requirements while maximizing
processing power utilization.

In this work, we developed a set of new algorithms and heuristics to
schedule real time applications on a cluster. We assumed that each
application is represented as a task graph. The objective of these
algorithms is to satisfy the deadlines of applications' tasks, to improve
the processing power utilization, and to increase the throughput. Our
scheduling approaches utilized the available processing power on
each processor to accommodate as many different applications' tasks
as possible while satisfying the required deadline of each task. The
algorithms reduce the communication cost among tasks and the possibility
of decreasing power fragmentation.

The new scheduling algorithms were designed for different applications'
structures: the sequential structures, the fork-join structures,
conditional structures, and loop structures. We combined the four
techniques to schedule general structures. We proved that they produced
a better acceptance rate compared to treating each application as one
unit. The proposed scheduling techniques have been evaluated through
extensive simulation studies and yielded better performance.


Professor Reda A. Ammar

Reda A. Ammar is a professor and the Department Head of the computer
Science and Engineering Department, University of Connecticut. His primary
research interests are in the area of software performance engineering,
real-time systems, and distributed and parallel computing. His
publication record exceeds 170 journal and conference papers. Dr. Ammar
was the chairman of five international conferences. He also served many
conferences as an organizing officer and as a member of program technical
committees. He served the International Society of Computers and Their
Applications as the vice president, the conference coordinator and a
member of the board of directors, and served the IEEE as the chairman
of the IEEE technical committee on Simulation. He is currently the
editor-in-chief of the International Journal on Computers and Their
Applications.