Nl. Passos et al., MULTIDIMENSIONAL INTERLEAVING FOR SYNCHRONOUS CIRCUIT-DESIGN OPTIMIZATION, IEEE transactions on computer-aided design of integrated circuits and systems, 16(2), 1997, pp. 146-159
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.