Scheduling tasks with communication delays on a two-levels virtual distributed system

Author

Colin, Jean-yves ; Nakechbandi, Mustafa

Author_Institution

Lab. d´´Inf., Le Havre Univ., France

fYear

1999

fDate

3-5 Feb 1999

Firstpage

344

Lastpage

348

Abstract

A set of tasks has to be scheduled on the parallel identical processors of the clusters of a two-levels distributed memory multiprocessor, subject to precedence constraints and small intra-cluster communication delays. The architecture model includes network of shared memory multiprocessors. In this paper, we present a new critical-path like algorithm that finds an optimal solution to this new problem in polynomial time, if task duplication is allowed and the number of available processors is not limited. The solution found is an earliest schedule that spreads the tasks between the clusters and the processors

Keywords

distributed shared memory systems; processor scheduling; distributed memory multiprocessor; intra-cluster communication delays; parallel identical processors; precedence constraints; scheduling tasks; task duplication; Clustering algorithms; Communication networks; Delay; Global communication; Joining processes; Memory architecture; Polynomials; Processor scheduling; Scheduling algorithm;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing, 1999. PDP '99. Proceedings of the Seventh Euromicro Workshop on

Conference_Location

Funchal

Print_ISBN

0-7695-0059-5

Type

conf

DOI

10.1109/EMPDP.1999.746698

Filename

746698