Affine scheduling on bounded convex polyhedric domains is asymptotically optimal

AbstractWe address the scheduling problem for algorithms which can be described by a system of uniform recurrence equations, when the computation domain is a bounded convex polyhedron. We study an affine schedule, first introduced by Darte and Robert, and we show that it is asymptotically time-optimal. Moreover we study the difference between its makespan and the optimal one, and we show that, in a special case, it is bounded by a logarithmic function of thedomain size