Low overhead parallel schedules for task graphs
Richard J Anderson, Paul W. Beame, Walter L. Ruzzo · 1990
We introduce a task scheduling model which is useful in the design and analysis of algorithms for small parallel machines.We prove that under our model, the overhead experienced in scheduling an n x n grid graph is O(loglogn) for p processors, p > 2. We also prove a matching lower bound of Q(loglog n) for p processors, p 1 2. We give an extension of the model to cover the case where the processors can have varying speed or are subject to delay.