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
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;
Conference_Titel :
High Performance Computing on the Information Superhighway, 1997. HPC Asia '97
Print_ISBN :
0-8186-7901-8
DOI :
10.1109/HPC.1997.592150
