Abstract
This paper describes a circuit transformation calledretiming in which registers are added at some points in a circuit and removed from others in such a way that the functional behavior of the circuit as a whole is preserved. We show that retiming can be used to transform a given synchronous circuit into a more efficient circuit under a variety of different cost criteria. We model a circuit as a graph in which the vertex setV is a collection of combinational logic elements and the edge setE is the set of interconnections, each of which may pass through zero or more registers. We give anO(¦V∥E¦lg¦V¦) algorithm for determining an equivalent retimed circuit with the smallest possible clock period. We show that the problem of determining an equivalent retimed circuit with minimum state (total number of registers) is polynomial-time solvable. This result yields a polynomial-time optimal solution to the problem of pipelining combinational circuitry with minimum register cost. We also give a chacterization of optimal retiming based on an efficiently solvable mixed-integer linear-programming problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems,Journal of the Association for Computing Machinery, Vol. 19, No. 2, 1972, pp. 248–264.
M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms,Proceedings of the 25th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, October 1984, pp. 338–346.
Z. Galil and É. Tardos, AnO(n 2(m +n logn) logn) min-cost flow algorithm,Proceedings of the 27th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, October 1986, pp. 1–9.
M. R. Garey and D. S. Johnson,Computers and Intractability, Freeman, San Francisco, 1979.
A. V. Goldberg, Efficient Parallel Algorithms for Sequential and Parallel Computers, Ph.D. dissertion, Department of Electrical Engineering and Computer Science, MIT, February 1987.
A. V. Goldberg and R. E. Tarjan, Finding Minimum-Cost Circulations by Successive Approximation, Technical Memorandum MIT/LCS/TM-33, MIT Laboratory for Computer Science, July 1987.
D. B. Johnson, Efficient algorithms for shortest paths in sparse networks,Journal of the Association for Computing Machinery, Vol. 24, No. 1, January 1977, pp. 1–13.
H. T. Kung, Let's design algorithms for VLSI systems,Proceedings of the Caltech Conference on Very Large Scale Integration, C. L. Seitz, ed., Pasadena, California, January 1979, pp. 55–90.
H. T. Kung and C. E. Leiserson, Systolic arrays (for VLSI),Sparse Matrix Proceedings 1978, I. S. Duff and G. W. Stewart, ed., Society for Industrial and Applied Mathematics, 1979, pp. 256–282. (An earlier version appears in Chapter 8 of [16] under the title, “Algorithms for VLSI processor arrays.”)
E. L. Lawler,Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.
C. E. Leiserson, Area-Efficient VLSI Computation, Ph.D. dissertation, Department of Computer Science, Carnegie-Mellon University, October 1981. Published in book form by the MIT Press, Cambridge, Massachcusetts, 1983.
C. E. Leiserson, Systolic and semisystolic design,Proceedings of the IEEE International Conference on Computer Design/VLSI in Computers (ICCD '83), Rye, New York, October 1983, pp. 627–632.
C. E. Leiserson, Flavio M. Rose, and James B. Saxe, Optimizing synchronous circuitry by retiming,”Proceedings of the 3rd Caltech Conference on Very Large Scale Integration, Randal Bryant, ed., California Institute of Technology, 1983, pp. 87–116. Computer Science Press, Rockville, Maryland.
C. E. Leiserson and J. B. Saxe, Optimizing synchronous systems,Journal of VLSI and Computer Systems, Vol. 1, No. 1, Spring 1983, pp. 41–67.
C. E. Leiserson and James B. Saxe, A mixed-integer programming problem which is efficiently solvable,Journal of Algorithms, Vol. 9, 1988, pp. 114–128. (An earlier version appears inProceedings of the 21st Annual Allerton Conference on Communication, Control, and Computing, October 1983, pp. 204–213).
C. A. Mead and L. A. Conway,Introduction to VLSI Systems, Addison-Wesley, Reading, Massachusetts, 1980.
P. Ng, W. Glauert, and R. Kirk, A timing verification system based on extracted MOS/VLSI circuit parameters,18th Design Automation Conference Proceedings, IEEE, 1981, pp. 288–292.
J. B. Orlin, A faster strongly polynomial minimum cost flow algorithm,Proceedings of the 20th Annual ACM Symposium on Theory of Computing, ACM, May 1988, pp. 377–387.
F. M. Rose, Models for VLSI Circuits, Masters thesis, Department of Electrical Engineering and Computer Science, MIT, March 1982. Also available as MIT VLSI Memo No. 82–114.
J. B. Saxe, Decomposable Searching Problems and Circuit Optimization by Retiming: Two Studies in General Transformations of Computational Structures, Ph.D. dissertation, Department of Computer Science, Carnegie-Mellon University, August 1985.
Texas Instruments Incorporated,The TTL Data Book for Design Engineers, Dallas, Texas, 1976.
Author information
Authors and Affiliations
Additional information
Communicated by F. Thomson Leighton.
This research was supported in part by the Defense Advanced Research Projects Agency under Contract N00014-80-C-0622 and by the Office of Naval Research under Contract N00014-76-C-0370. Charles Leiserson was supported in part by an NSF Presidential Young Investigator Award with matching funds provided by AT&T Corporation, IBM Corporation, and Xerox Corporation. Most of the results reported here were obtained while James Saxe was in the Computer Science Department at Carnegie-Mellon University. During part of that period, he was supported by an IBM graduate fellowship.
Rights and permissions
About this article
Cite this article
Leiserson, C.E., Saxe, J.B. Retiming synchronous circuitry. Algorithmica 6, 5–35 (1991). https://doi.org/10.1007/BF01759032
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01759032