Two-dimensional retiming with low memory requirements

This paper considers throughput and memory requirements in architectures which operate on two-dimensional (2D) digital signals. We present a novel technique for retiming a 2D data-flow graph to meet a given throughput constraint while keeping the memory required by the architecture low. This technique, which we call orthogonal two-dimensional retiming, is posed as two linear programming problems which can be solved in polynomial time. Our results show that, for a given throughput constraint, the orthogonal two-dimensional retiming formulation leads to architectures which require less memory than architectures designed using previously known techniques.