Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


ucin1000734538.pdf (246.76 KB)

ETD Abstract Container

Abstract Header

EFFICIENT TASK SCHEDULING ALGORITHM FOR NETWORK OF HETEROGENEOUS WORKSTATIONS

BAJAJ, RASHMI
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1000734538

Abstract Details

2001, MS, University of Cincinnati, Engineering : Computer Engineering.
Optimal scheduling of parallel tasks with some precedence relationship, onto a distributed-memory machine is known to be a strong NP-hard problem. The complexity of the problem increases when task scheduling is to be done on a network of heterogeneous workstations (NoWs), where workstations may not be identical and may take different amount of time to execute the same task. This dissertation presents a Task duplication based scheduling Algorithm for Network of Heterogeneous workstations (TANH), with complexity O(V 2 ), which provides optimal results for applications represented by Directed Acyclic Graphs (DAGs), provided some simple conditions on task computation and network communication time could be satisfied. The performance of the algorithm is illustrated by comparing the scheduling time with an existing scheme BIL, for heterogeneous systems. We also observe that TANH provides speed-ups of 6 to 40 for some practical DAGs with upto 3000 nodes and the number of edges varying from 4000 to as high as 25000 edges, if adequate duplication is allowed. The flexibility of scaling to higher or lower number of workstations, as per their availability is also discussed. Some problems for future work are also briefly outlined.
Dr. Dharma P. Agrawal (Advisor)
72 p.
distributed computing; task duplicaiton algorithm; optimal algorithm; network of workstations

Recommended Citations

Citations

  • BAJAJ, R. (2001). EFFICIENT TASK SCHEDULING ALGORITHM FOR NETWORK OF HETEROGENEOUS WORKSTATIONS [Master's thesis, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1000734538

    APA Style (7th edition)

  • BAJAJ, RASHMI. EFFICIENT TASK SCHEDULING ALGORITHM FOR NETWORK OF HETEROGENEOUS WORKSTATIONS. 2001. University of Cincinnati, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1000734538.

    MLA Style (8th edition)

  • BAJAJ, RASHMI. "EFFICIENT TASK SCHEDULING ALGORITHM FOR NETWORK OF HETEROGENEOUS WORKSTATIONS." Master's thesis, University of Cincinnati, 2001. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1000734538

    Chicago Manual of Style (17th edition)

ucin1000734538
888
© 2001, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.