Two Approaches to Critical Path Scheduling for a Heterogeneous Environment

Advances in computing and networking technologies are making large scale distributed heterogeneous computing a reality. Multi-Disciplinary Optimization (MDO) is a class of applications that is being addressed under this paradigm. It consists of multiple heterogeneous modules interacting with each other to solve an overall design problem. An efficient implementation of such an application requires scheduling heterogeneous modules (with different computing and disk 1/0 requirements) on a heterogeneous set of resources (with different CPU, memory, disk IO specifications). Given a set of tasks and a set of resources, an optimal schedule of the tasks on the resources is very hard to compute (NP-Complete). In this study, we focus on scheduling of coarse grained tasks on heterogeneous resources. We propose two algorithms based on the classic static Critical Path Method (CPM). CPM has been suggested for homogeneous environments. We adapt this method for a heterogeneous environment. One of the proposed algorithms, named EA-CPM, maps a highest priority ready task to a processor that ensures its earliest assignment. The other algorithm, called EF-CPM, assigns a highest priority ready task to a processor that yields the earliest finishing time. We describe a series of qualitative, systematic numerical studies for evaluating algorithms. Overall, the performance of both algorithms is very promising. In particular, EF-CPM is close to the locally optimal solution obtained by the branch exhaustive search method