Push-up scheduling: optimal polynomial-time resource constrained scheduling for multi-dimensional applications

摘要

Multi-dimensional computing applications, such as image processing and fluid dynamics, usually contain repetitive groups of operations represented by nested loops. The optimization of such loops, considering processing resource constraints, is required to improve their computational time. This study presents a new technique, called push-up scheduling, able to achieve the shortest possible schedule length in polynomial time. Such technique transforms a multi-dimensional dataflow graph representing the problem, while assigning the loop operations to a schedule table in such a way to occupy, legally, any empty spot. The algorithm runs in O(n|E|) time where n is the number of dimensions of the problem, and |E| is the number of edges in the graph.