An improved algorithm for minimum-area retiming

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An improved algorithm for minimum-area retiming

Full text

Pdf (131 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 34th annual Design Automation Conference table of contents

Anaheim, California, United States

Pages: 2 - 7

Year of Publication: 1997

ISBN:0-89791-920-3

Authors

Naresh Maheshwari	Department of Electrical & Computer Engineering, Iowa State University, Ames, IA
Sachin S. Sapatnekar	Department of Electrical & Computer Engineering, Iowa State University, Ames, IA

Sponsors

EDAC : Electronic Design Automation Consortium
IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 11, Citation Count: 15

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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/266021.266025 What is a DOI?

ABSTRACT

The concept of improving the timing behavior of a circuit by relocatingflip-flops is called retiming and was first presented by Leisersonand Saxe. The ASTRA algorithm proposed an alternativeview of retiming using the equivalence between retiming and clockskew optimization. This work defines the relationship betweenthe Leiserson-Saxe and the ASTRA approaches and utilizes it tosolve the problem of retiming for minimum area. The new algorithm,Minaret, uses the linear programming formulation of theLeiserson-Saxe approach. The underlying philosophy of the ASTRAapproach is incorporated to reduce the number of variablesand constraints in the linear program. This reduction in the sizeof the linear program makes Minaret space and time efficient, enablingminimum area retiming of circuits with over 56,000 gates inunder 15 minutes.

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	C. Leiserson, F. Rose, and J. B. Saxe, "Optimizing synchronous circuitry by retiming," in Proceedings of the 3rd Caltech Conference on VLSI, pp. 87-116, 1983.
	2	C. E. Leiserson and J. B. Saxe, "Retiming synchronous circuitry," Algorithmica, vol. 6, pp. 5-35, 1991.
	3	A. Ishii, C. E. Leiserson, and M. C. Papaefthymiou, "Optimizing two-phase, level-clocked circuitry," in Advanced Research in VLSI and Parallel Systems: Proceedings of the 1992 Brown/MIT Conference, pp. 246-264, 1992.
	4	B. Lockyear and C. Ebeling, "Optimal retiming of levelclocked circuits using symmetric clock schedules," IEEE Transactions on Computer-Aided Design, vol. 13, pp. 1097- 1109, Sept. 1994.
	5	Kumar N. Lalgudi , Marios C. Papaefthymiou, DELAY: an efficient tool for retiming with realistic delay modeling, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.304-309, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217546]
	6	G. Even, I. Y. Spillinger, and L. Stok, "Retiming revisited and reversed," IEEE Transactions on Computer-Aided Design, vol. 15, pp. 348-357, Mar. 1996.
	7	José Monteiro , Srinivas Devadas , Abhijit Ghosh, Retiming sequential circuits for low power, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.398-402, November 07-11, 1993, Santa Clara, California, United States
	8	Narendra Shenoy , Richard Rudell, Efficient implementation of retiming, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.226-233, November 06-10, 1994, San Jose, California, United States
	9	Rahul B. Deokar , Sachin S. Sapatnekar, A fresh look at retiming via clock skew optimization, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.310-315, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217547]
	10	S. S. Sapatnekar and R. B. Deokar, "Utilizing the retiming skew equivalence in a practical algorithm for retiming large circuits," IEEE Transactions on Computer-Aided Design, vol. 15, pp. 1237-1248, Oct. 1996.
	11	Naresh Maheshwari , Sachin S. Sapatnekar, A Practical Algorithm for Retiming Level-Clocked Circuits, Proceedings of the 1996 International Conference on Computer Design, VLSI in Computers and Processors, p.440, October 07-09, 1996
	12	John P. Fishburn, Clock Skew Optimization, IEEE Transactions on Computers, v.39 n.7, p.945-951, July 1990 [doi>10.1109/12.55696]
	13	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	14	Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
	15	Mokhtar S. Bazaraa , John J. Jarvis , Hanif D. Sherali, Linear programming and network flows (2nd ed.), John Wiley & Sons, Inc., New York, NY, 1990

CITED BY 15

	Chao-Yang Yeh , Malgorzata Marek-Sadowska, Minimum-Area Sequential Budgeting for FPGA, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.813, November 09-13, 2003
	A. Ranjan , A. Srivastava , V. Karnam , M. Sarrafzadeh, Layout aware retiming, Proceedings of the 11th Great Lakes symposium on VLSI, p.25-30, March 2001, West Lafayette, Indiana, United States
	Abdallah Tabbara , Robert K. Brayton , A. Richard Newton, Retiming for DSM with area-delay trade-offs and delay constraints, Proceedings of the 36th ACM/IEEE conference on Design automation, p.725-730, June 21-25, 1999, New Orleans, Louisiana, United States
	Vijay Sundararajan , Sachin S. Sapatnekar , Keshab K. Parhi, Marsh: min-area retiming with setup and hold constraints, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.2-6, November 07-11, 1999, San Jose, California, United States
	Naresh Maheshwari , Sachin S. Sapatnekar, Minimum area retiming with equivalent initial states, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.216-219, November 09-13, 1997, San Jose, California, United States
	N. Maheshwari , S. S. Sapatnekar, Efficient minarea retiming of large level-clocked circuits, Proceedings of the conference on Design, automation and test in Europe, p.840-847, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Ruibing Lu , Cheng-Kok Koh, Interconnect Planning with Local Area Constrained Retiming, Proceedings of the conference on Design, Automation and Test in Europe, p.10442, March 03-07, 2003
	G. Hasteer , A. Mathur , P. Bannerjee, Efficient equivalence checking of multi-phase designs using phase abstraction and retiming, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.4, p.600-625, Oct. 1998
	Klaus Eckl , Jean Christophe Madre , Peter Zepter , Christian Legl, A practical approach to multiple-class retiming, Proceedings of the 36th ACM/IEEE conference on Design automation, p.237-242, June 21-25, 1999, New Orleans, Louisiana, United States
	Klaus Eckl , Christian Legl, Retiming sequential circuits with multiple register classes, Proceedings of the conference on Design, automation and test in Europe, p.127-es, January 1999, Munich, Germany
	Rajeev K. Ranjan , Vigyan Singhal , Fabio Somenzi , Robert K. Brayton, Using combinational verification for sequential circuits, Proceedings of the conference on Design, automation and test in Europe, p.32-es, January 1999, Munich, Germany
	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
	Chris Chu , Evangeline F. Y. Young , Dennis K. Y. Tong , Sampath Dechu, Retiming with Interconnect and Gate Delay, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.221, November 09-13, 2003
	Karam S. Chatha , Ranga Vemuri, Hardware-Software partitioning and pipelined scheduling of transformative applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.10 n.3, p.193-208, June 2002
	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