Multidimensional 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 multidimensional data flow graphs (MDFG's). This new optimization technique, called multidimensional interleaving, consists of a multidimensional expansion and compression of the iteration space, followed by a multidimensional 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.