Old Dominion University
Two Approaches to Critical Path Scheduling for a Heterogeneous Environment
Abstract
dc:description.abstractAdvances 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.
Degree
thesis:*- Name thesis:degree_name
- Master of Science (MS)
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Computer Science
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Liu, Guangxia
- Contributors dc:contributor
-
- Mohammad Zubair
- Piyush Mehrotra
- Kurt Maly
- David Keyes
Subjects
dc:subject × 6Rights
dc:rights- Statement dc:rights
-
- <p>In Copyright. URI: <a href="http://rightsstatements.org/vocab/InC/1.0/">http://rightsstatements.org/vocab/InC/1.0/</a> This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).</p>
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.odu.edu/computerscience_etds/156