Optimal Parallel Algorithms for Two Processor Scheduling with Tree
Precedence Constraints
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
n² 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.
