Multi-Dimensional Interleaving for Synchronous Circuit Design Optimization

This paper presents a novel optimization technique for the design of application specific integrated circuits dedicated to perform iterative or recursive time-critical sections of multidimensional problems, such as image processing applications. These sections are modeled as cyclic multi-dimensional data flow graphs (MDFGs). This new optimization technique, called multi-dimensional interleaving consists of a multi-dimensional expansion and compression of the iteration space, followed by a multi-dimensional retiming, while considering memory requirements. It guarantees that all functional elements of a circuit can be executed simultaneously, and no additional memory queues proportional to the problem size are required. The algorithm runs optimally in O(|E|) time, where E is the set of edges of the MDFG representing the circuit. Our experiments show that the additional memory requirement is significantly less than the results obtained in other methods