Synchronous circuit optimization via multidimensional retiming

Time-critical sections of multidimensional applications, such as image processing and computational fluid dynamics are in general iterative or recursive. Most of these applications require each iteration to be executed under a specific time constraint associated with the data input rate. The design of circuits dedicated to perform such repetitive tasks depend on optimization techniques to achieve the desired execution time. The retiming technique is one of these optimization tools; however the traditional retiming deals only with one dimension of the problem and has lower bound constraints in the execution time due to characteristics of the initial design. This paper presents a novel optimization technique based on the application of a multidimensional retiming. Multidimensional retiming improves the circuitry performance by inserting a fixed number of registers, which is independent of the size of the problem, into the circuit paths, and restructuring the memory elements in a legal way. This technique guarantees that all functional elements can be executed simultaneously on circuits designed to solve problems involving more than one dimension. Experiments show that the additional elements required for the performance improvement have a small impact on the circuit area.