Optimizing Synchronous Systems for Multi-Dimensional Applications

Time-critical sections of multi-dimensional problems, such as image processing applications, are in general iterative or recursive. In this paper these sections are modeled as cyclic multi-dimensional data flow graphs (MDFGs), which are also used to represent the digital circuit designed to compute such problems. Each node in the MDFG is associated with a set of functional elements in the circuit. Memory elements and circuit paths are associated with graph edges representing data dependencies. This new optimization technique consists of a multi-dimensional retiming being applied to the MDFG to reduce its cycle time while considering memory requirements. This technique guarantees that all functional elements of a circuitry, designed to be applied to problems involving more than one dimension, can be executed simultaneously. The algorithm runs in O(jEjjV j) time, where V is the set of nodes and E is the set of edges of the MDFG representing the circuit