Scheduling directed acyclic task graphs with coarse granularity onto multiprocessors

Author

Park, Choung Shik ; Choi, Sang Bang

Author_Institution

Dept. of Electron. Eng., Inha Univ., Inchon, South Korea

fYear

1996

fDate

18-21 Nov 1996

Firstpage

464

Lastpage

467

Abstract

The multiprocessor scheduling is the problem of mapping the tasks of a directed acyclic graph (DAG) onto the processors of a multiprocessor system in a way that minimizes the completion time. Since this problem is known to be NP-complete, many heuristic scheduling algorithms are developed to achieve near optimal schedules in a reasonable amount of computation time. In this paper we present a heuristic scheduling algorithm based on linear clustering scheme and effectiveness of proposed algorithm is assured by computer simulations

Keywords

computational complexity; directed graphs; multiprocessing systems; processor scheduling; NP-complete problem; coarse granularity; completion time; computation time; directed acyclic task graphs; heuristic scheduling algorithm; linear clustering scheme; multiprocessor scheduling; Clustering algorithms; Computational efficiency; Computational modeling; Computer simulation; Multimedia systems; Multiprocessing systems; Optimal scheduling; Processor scheduling; Real time systems; Scheduling algorithm;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1996., IEEE Asia Pacific Conference on

Conference_Location

Seoul

Print_ISBN

0-7803-3702-6

Type

conf

DOI

10.1109/APCAS.1996.569314

Filename

569314