Optimal Parallel Algorithms for Two Processor Scheduling with Tree Precedence Constraints

Dokumenttyp:: Technical Report
Autor(en):: Ernst W. Mayr; Hans Stadtherr
Titel:: Optimal Parallel Algorithms for Two Processor Scheduling with Tree Precedence Constraints
Abstract:: Consider the problem of finding a minimum length schedule for an unit execution time tasks on m processors with tree-like precedence constraints. A sequential algorithm can solve this problem in linear time. The fastest known parallel algorithm needs O(log n) time using n^2 processors. For the case m=2 we present two work optimal parallel algorithms that produce greedy optimal schedules for intrees and outtrees. Both run in O(log n) time using n/(log n) processors of an EREW PRAM.
Stichworte:: parallel algorithms; scheduling; tree precedence constraints; optimal work
Jahr:: 1995
Jahr / Monat:: 1995-11-08 00:00:00
Seiten/Umfang:: 26
BibTeX

Vorkommen: