Back to search

Old Dominion University

Two Approaches to Critical Path Scheduling for a Heterogeneous Environment

Abstract

dc:description.abstract

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.

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 × 6

Rights

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.*

Chain of custody

source
Harvested from
Old Dominion University
Base URL
digitalcommons.odu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Liu, Guangxia. Two Approaches to Critical Path Scheduling for a Heterogeneous Environment. Thesis thesis, https://digitalcommons.odu.edu/computerscience_etds/156