Optimal on-line load balancing
Gregory E. Shannon · 1989
We present a general technique for simulating a broad class of T(n)-time and P(n)-processor algorithms on P(n)/T(n) processors using only O(T(n)) time for problems of size n.Surprisingly, this technique is not work conserving; many processors might be idle for long periods of time during the simulation.This generafizes and extends recent work on designing algorithms with optimal processor-time products for the parallel RAM model.These techniques enable us to design optimal processor-time product PRAM algorithms for the problems on planar graphs of maximal independent set, 5-coloring, 7-coloring,connected components, and maximal matching.These algorithms use linear space and from O(log n) to O(log n log* n) time, depending on the model (CRCW or EREW) and the problem.These algorithms are currently the fastest, most processor efficient, and most space efficient for these problems on the PRAM models.