Two-dimensional retiming

作     者：Denk, TC Parhi, KK 

作者机构：Broadcom Corp Irvine CA 92618 USA Univ Minnesota Dept Elect Engn Minneapolis MN 55455 USA 

出 版 物：《IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS》 (IEEE Trans Very Large Scale Integr VLSI Syst)

年 卷 期：1999年第7卷第2期

页      面：198-211页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Patterson Air Force Base, (AF/F33615-93-C-1309) Solid State Electronics Directorate Advanced Research Projects Agency, ARPA 

主　　题：data flow graphs multidimensional signal processing parallel architectures retiming very large scale integration 

摘      要：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.