Optimizing two-phase, level-clocked circuitry

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimizing two-phase, level-clocked circuitry

Full text

Pdf (912 KB)

Source

Journal of the ACM (JACM) archive
Volume 44 , Issue 1 (January 1997) table of contents

Pages: 148 - 199

Year of Publication: 1997

ISSN:0004-5411

Authors

Alexander T. Ishii	MIT Laboratory for Computer Science, Cambridge, Massachusetts
Charles E. Leiserson	MIT Laboratory for Computer Science, Cambridge, Massachusetts
Marios C. Papaefthymiou	MIT Laboratory for Computer Science, Cambridge, Massachusetts

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 32, Citation Count: 13

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/256292.256301 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	2	Michael R. Dagenais , Nicholas C. Rumin, Automatic determination of optimal clocking parameters in synchronous MOS VLSI circuits, Proceedings of the fifth MIT conference on Advanced research in VLSI, p.19-33, January 1988, Cambridge, Massachusetts, United States
	3	DANTZIG, G. B., BLATTNER, W., AND RAO, M.R. 1967. Finding a cycle in a graph with minimum cost to times ratio with application to a ship routing problem. In Theory of Graphs, P. Rosenstiehl, ed., Dunod, Paris, France, and Gordon and Breach, New York, pp. 77-84.
	4	John P. Fishburn, Clock Skew Optimization, IEEE Transactions on Computers, v.39 n.7, p.945-951, July 1990 [doi>10.1109/12.55696]
	5	GAREY, M. R., AND JOHNSON, D.S. 1979. Computers and Intractability. W. H. Freeman and Co., San Francisco, Calif.
	6	Lance A. Glasser , Daniel W. Dobberpuhl, The design and analysis of VLSI circuits, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
	7	HARTMANN, M., AND ORLIN, J. 1991. Finding minimum cost to time ratio cycles with small integral transit times. Tech. Rep. UNC/OR/TR/91-19. Univ. North Carolina, Chapel Hill, N.C., Oct.
	8	Alexander Toichi Ishii, Timing in level-clocked circuits, Massachusetts Institute of Technology, Cambridge, MA, 1992
	9	Alexander T. Ishii , Charles E. Leiserson, A timing analysis of level-clocked circuitry, Proceedings of the sixth MIT conference on Advanced research in VLSI, p.113-130, March 1990, Boston, Massachusetts, United States
	10	ISHII, A. f., LEISERSON, C. E., AND PAPAEFTHYMIOU, M. C. 1992a. Optimizing two-phase, levelclocked circuitry. In Advanced Research in VLSI and Parallel Systems: Proceedings of the 1992 Brown/MIT Conference, (Mar.). MIT Press, Cambridge, Mass., pp. 245-264.
	11	ISHII, A. f., LEISERSON, C. E., AND PAPAEFTHYMIOU, M.C. 1992b. Polynomial-time algorithms for optimizing two-phase, level-clocked circuitry. Unpublished manuscript, MIT, Cambridge, Mass.
	12	LEISERSON, C. E., ROSE, F. M., AND SAXE, J. B. 1983. Optimizing synchronous circuitry by retiming. In Proceedings of the 3rd Caltech Conference on VLSI, R. Bryant, ed. Caltech, pp. 87-116.
	13	LEISERSON, C. E., AND SAXE, J.B. 1983. Optimizing synchronous systems. J. VLSI Comput. Syst. 1, (1), 41-67.
	14	Charles E. Leiserson , James B. Saxe, A mixed-integer linear programming problem which is efficiently solvable, Journal of Algorithms, v.9 n.1, p.114-128, March 1988 [doi>10.1016/0196-6774(88)90008-9]
	15	LEISERSON, C. E., AND SAXE, J.g. 1991. Retiming synchronous circuitry. Algorithmica 6, (1). (Also available as MIT/LCS/TM-372.)
	16	LOCKYEAR, B., AND EBELING, C. 1992. Optimal retiming of multi-phase level-clocked circuits. In Advanced Research in VLSI and Parallel Systems: Proceedings of the 1992 Brown/MIT Conference (Mar.). MIT Press, Cambridge, Mass., pp. 265-280.
	17	MALIK, S., SENTOVICH, E., BRAYTON, R. K., AND SANGIOVANNI-VINCENTELLI, A. 1990. Retiming and resynthesis: Optimizing sequential networks with combinational techniques. In Proceedings of the Hawaii International Conference on System Sciences.
	18	Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
	19	Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
	20	MEGIDDO, N. 1985. Partitioning with two lines in the plane. J. Algorithms 6, 430-433.
	21	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	22	M. C. Papaefthymiou, ON RETIMING SYNCHRONOUS CIRCUITRY AND MIXED-INTEGER OPTIMIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1990
	23	Marios Christos C. Papaefthymiou, A timing analysis and optimization system for level-clocked circuitry, Massachusetts Institute of Technology, Cambridge, MA, 1993
	24	Marios C. Papaefthymiou, Understanding retiming through maximum average-delay cycles, Mathematical Systems Theory, v.27 n.1, p.65-84, Jan./Feb. 1994
	25	PAPAEFTHYMIOU, M. C., LEISERSON, C. E., AND ISHII, A. T. 1991. Optimizing two-phase, levelclocked circuitry. In Proceedings of the 1991 MIT Student Workshop on VLSI and Parallel Systems (July). Massachusetts Institute of Technology, Cambridge, Mass.
	26	Marios C. Papaefthymiou , Keith H. Randall, Edge-triggering vs. two-phase level-clocking, Proceeding of the 1993 symposium on Research on integrated systems, p.201-218, February 1993, Seattle, Washington, United States
	27	Marios C. Papaefthymiou , Keith H. Randall, TIM: a timing package for two-phase, level-clocked circuitry, Proceedings of the 30th international conference on Design automation, p.497-502, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164998]
	28	Nohbyung Park , Alice C. Parker, Theory of Clocking for Maximum Execution Overlap of High-Speed Digital Systems, IEEE Transactions on Computers, v.37 n.6, p.678-690, June 1988 [doi>10.1109/12.2206]
	29	SAKALLAH, K. A., MUDGE, T. N., AND OLUKOTUN, 0. A. 1990. Optimal clocking of synchronous digital circuits. In Technical Digest of the 1990 IEEE International Conference on CAD (Nov.). IEEE Computer Society Press, Los Alamitos, Calif., pp. 552-555.
	30	Narendra V. Shenoy , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Retiming of Circuits with Single Phase Transparent Latches, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.86-89, October 14-16, 1991
	31	Thomas G. Szymanski , Narendra Shenoy, Verifying clock schedules, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.124-131, November 1992, Santa Clara, California, United States
	32	S H Unger , Chung-Jen Tan, Clocking schemes for high-speed digital systems, IEEE Transactions on Computers, v.35 n.10, p.880-895, Oct. 1986 [doi>10.1109/TC.1986.1676679]
	33	Stephen A. Ward , Robert H. Halstead, Jr., Computation structures, MIT Press, Cambridge, MA, 1990

CITED BY 13

	Noureddine Chabini , Yvon Savaria, Methods for optimizing register placement in synchronous circuits derived using software pipelining techniques, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada
	Xun Liu , Marios C. Papaefthymiou , Eby G. Friedman, Maximizing performance by retiming and clock skew scheduling, Proceedings of the 36th ACM/IEEE conference on Design automation, p.231-236, June 21-25, 1999, New Orleans, Louisiana, United States
	François R. Boyer , El Mostapha Aboulhamid , Yvon Savaria , Michel Boyer, Optimal design of synchronous circuits using software pipelining techniques, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.4, p.516-532, October 2001
	Marios C. Papaefthymiou, Asymptotically efficient retiming under setup and hold constraints, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.396-401, November 08-12, 1998, San Jose, California, United States
	Ko Yoshikawa , Yasuhiko Hagihara , Keisuke Kanamaru , Yuichi Nakamura , Shigeto Inui , Takeshi Yoshimura, Timing optimization by replacing flip-flops to latches, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.186-191, January 27-30, 2004, Yokohama, Japan
	Noureddine Chabini , El Mostapha Aboulhamid , Ismaïl Chabini , Yvon Savaria, Scheduling and optimal register placement for synchronous circuits derived using software pipelining techniques, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.2, p.187-204, April 2005
	Man Chung Hon, Spec-based flip-flop and latch repeater planning, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Hai Zhou, Deriving a new efficient algorithm for min-period retiming, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Chuan Lin , Hai Zhou, An efficient retiming algorithm under setup and hold constraints, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	Chuan Lin , Hai Zhou, Optimal wire retiming without binary search, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.452-458, November 07-11, 2004
	Chuan Lin , Hai Zhou, Trade-off between latch and flop for min-period sequential circuit designs with crosstalk, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.329-334, November 06-10, 2005, San Jose, CA
	Xun Liu , Marios C. Papaefthymiou , Eby G. Friedman, Minimizing sensitivity to delay variations in high-performance synchronous circuits, Proceedings of the conference on Design, automation and test in Europe, p.126-es, January 1999, Munich, Germany
	Hai Zhou, A new efficient retiming algorithm derived by formal manipulation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.13 n.1, p.1-19, January 2008

INDEX TERMS

Primary Classification:
B. Hardware
B.6 LOGIC DESIGN
B.6.3 Design Aids
Subjects: Optimization

General Terms:
Algorithms, Design

Keywords:
VLSI, clock tuning, level-clocked circuitry, multiphase clocking, retiming, timing analysis and optimization

REVIEW

"Thomas B. Hilburn : Reviewer"

VLSI design that is related to the implementation of clocked storage elements often concerns choices between level-clocked and edge-triggered latches. The authors investigate two strategies for reducing the clock period of a two-phase, level-c more...

Collaborative Colleagues:

Alexander T. Ishii: colleagues

Charles E. Leiserson: colleagues

Marios C. Papaefthymiou: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player