Processor Lower Bounds for Array Computations with Linear Schedules

Using a directed acyclic graph (dag) model of algorithms, this paper treats aproblem related to precedence-constrained multiprocessor schedules for arraycomputations: Given a dag and a valid linear schedule for it, compute a lowerbound on the number of processors required by the schedule. This is animportant practical problem: A good schedule uses time efficiently; a goodmapping of nodes to processors uses energy efficiently. The lower boundsobtained are good; we know of no case where they are not exactly tight.Actually, a harder problem is solved: Given a parametrized family of dags anda correspondingly parametrized valid linear schedule, symbolically generate aprocessor lower bound formula. To visualize the method for computing thisformula, the nodes, representing computational tasks, are viewed as a set oflattice points in a convex polyhedron. The number of tasks that are scheduledfor execution during any given time step of a linear schedule is the number ofnon-negative integer solutions to a set of linear Diophantine equationsparametrized by the number of nodes of the dag. An algorithm, based onconstruction of generating functions, is presented for computing thesenumbers. This is the first such algorithm to be reported. Using thisalgorithm and a symbolic algebra package, formulas for processor lower boundsare obtained automatically.The algorithm has been implemented as a Mathematica program. Example runs forMatrix-Vector Product, and Triangular Matrix Product problems are given. Whilewidely applicable and elegant, it has worst case exponential running time.This is not surprising however; the simpler computation: ``Are any processorsscheduled for a particular time step?\'\' which is equivalent to ``Is aparticular coefficient of the generating function nonzero?\" is already known tobe an NP-complete problem.