This paper considers two-dimensional (2-D) retiming, which is the problem of retiming circuits that operate on 2-D signals. We begin by discussing two types of parallelism available in 2-D data processing, which we call inter-iteration parallelism and inter-operation parallelism. We then present two novel techniques for 2-D retiming that can be used to extract inter-operation parallelism. These two techniques are designed to minimize the amount of memory required to implement a 2-D data-flow graph while maintaining a desired clock rate for the circuit. The first technique is based on an integer linear programming (ILP) formulation of the problem, and is called ILP 2-D retiming. This technique considers the entire 2-D retiming problem as a whole, but long central processing unit times are required if the circuit is large. The second technique, called orthogonal 2-D retiming, is a linear programming formulation which is derived by partitioning ILP 2-D retiming into two parts called s- and a-retiming. This technique finds a solution in polynomial time and is much faster than the ILP 2-D retiming technique, but the two sub-problems (s- and a-retiming) can give results which are not compatible with one another. To solve this incompatibility problem, a variation of orthogonal 2-D retiming called integer orthogonal 2-D retiming is developed. This technique runs in polynomial time and the s-retiming and a-retiming steps are guaranteed to give compatible results. We show that the techniques presented in this paper can result in memory hardware savings of 50% compared to previously published 2-D retiming techniques.
|Number of pages
|IEEE Transactions on Very Large Scale Integration (VLSI) Systems
|Published - 1999
Bibliographical noteFunding Information:
Manuscript received July 16, 1996; revised August 14, 1998. This work was supported by the Advanced Research Projects Agency and by the Solid State Electronics Directorate, Wright–Patterson Air Force Base under Contract AF/F33615-93-C-1309. T. C. Denk is with Broadcom Corporation, Irvine, CA 92618 USA. K. K. Parhi is with the Department of Electrical Engineering, University of Minnesota, Minneapolis, MN 55455 USA. Publisher Item Identifier S 1063-8210(99)03340-5.