MULTIDIMENSIONAL INTERLEAVING FOR SYNCHRONOUS CIRCUIT-DESIGN OPTIMIZATION

This paper presents a novel optimization technique for the design of a pplication specific integrated circuits dedicated to perform iterative or recursive time-critical sections of multidimensional problems, suc h as image processing applications. These sections are modeled as cycl ic multidimensional data dow graphs (MDFG's). This new optimization te chnique, called multidimensional interleaving, consists of a multidime nsional 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 s imultaneously, and no additional memory queues proportional to the pro blem size are required. The algorithm runs optimally in O(\E\) time, w here E is the set of edges of the MDFG representing the circuit. Our e xperiments allow that the additional memory requirement is significant ly less than the results obtained in other methods.