Optimizing synchronous systems for multi-dimensional applications
Nelson Luiz Passos, Edwin H.‐M. Sha, Liang-Fang Chao · 1995
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 ow graphs (MDFGs), which are also used torepresent 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 toreduce its cycle time while considering memory requirements. This technique guarantees that all functional elements of a circuitry, designed tobeapplied toproblems 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. 1