Optimal Parallel Algorithms for Two Processor Scheduling with Tree
Precedence Constraints
Ernst W. Mayr and Hans Stadtherr
Technical Report TUM-I9531
Institut für Informatik
Technische Universität München
November 1995
Abstract.
Consider the problem of finding a minimum length schedule for n 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 n2 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.
Hans Stadtherr, 1997/09/16