DocumentCode
3570462
Title
An optimal parallel algorithm for two-processor scheduling
Author
Albacea, Eliezer A.
Author_Institution
Inst. of Comput. Sci., Philippines Los Barios Univ., Laguna, Philippines
fYear
1997
Firstpage
220
Lastpage
223
Abstract
The author presents a parallel algorithm for two-processor scheduling of tasks with treelike precedence constraints (outforests and inforests). The algorithm runs in O(log n) time using n/log n processors on the EREW PRAM. The algorithm is optimal and has a better time-processor product compared to the existing two-processor scheduling algorithms for outforests and inforests
Keywords
computational complexity; parallel algorithms; processor scheduling; trees (mathematics); EREW PRAM; computation time; inforests; optimal parallel algorithm; outforests; processors; task scheduling; time-processor product; treelike precedence constraints; two-processor scheduling; Algorithm design and analysis; Computer science; Constraint theory; Educational institutions; Joining processes; Optimal scheduling; Parallel algorithms; Phase change random access memory; Processor scheduling; Scheduling algorithm;
fLanguage
English
Publisher
ieee
Conference_Titel
High Performance Computing on the Information Superhighway, 1997. HPC Asia '97
Print_ISBN
0-8186-7901-8
Type
conf
DOI
10.1109/HPC.1997.592150
Filename
592150
Link To Document