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 us 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 re-timing being applied to the MDFG to reduce its cycle time while considering memory requirements. This technique guarantees that all functional elements of a circuit, designed to be applied to problems involving more than one dimension, can be executed simultaneously. The algorithm runs in O(|E||V|) time, where V is the set of nodes and E is the set of edges of the MDFG representing the circuit