A fast and scalable scheduling algorithm for distributed memory systems

Author

Darbha, Sekhar ; Agrawal, Dharma P.

Author_Institution

Dept. of Electr. & Comput. Eng., North Carolina State Univ., Raleigh, NC, USA

fYear

1995

fDate

25-28 Oct 1995

Firstpage

60

Lastpage

63

Abstract

The inter-processor communication time is a major bottleneck for distributed memory systems (DMSs) and can be reduced by having an efficient task partitioning and scheduling strategy. The paper deals with the scheduling issues and presents an algorithm to schedule tasks onto DMSs. The complexity of this algorithm is O(V²), where Vr is the number of nodes of the directed acyclic graph (DAG). This algorithm has been applied to some practical DAGs and the results obtained using this algorithm are very promising

Keywords

computational complexity; directed graphs; distributed memory systems; processor scheduling; complexity; directed acyclic graph nodes; distributed memory systems; fast scheduling algorithm; interprocessor communication time; scalable scheduling algorithm; task partitioning strategy; task scheduling strategy; Clustering algorithms; Communication networks; Cost function; Distributed computing; Optimal scheduling; Partitioning algorithms; Polynomials; Processor scheduling; Scheduling algorithm; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing, 1995. Proceedings. Seventh IEEE Symposium on

Conference_Location

San Antonio, TX

ISSN

1063-6374

Print_ISBN

0-81867195-5

Type

conf

DOI

10.1109/SPDP.1995.530665

Filename

530665