NDLI: Wire Retiming Problem With Net Topology Optimization

Content Provider	IEEE Xplore Digital Library
Author	Tong, D.K.Y. Young, E.F.Y. Chu, C. Dechu, S.
Copyright Year	1982
Abstract	In this paper, we study the retiming problem of sequential circuits with net topology optimization. Both interconnect and gate delay are considered in retiming. Most previous retiming algorithms have assumed ideal conditions for the nonlogical portions of data paths, which are not sufficiently accurate to be used in high-performance circuits today. In our modeling, we assume that the delay of a wire is directly proportional to its length. This assumption is reasonable since the quadratic component of a wire delay is significantly smaller than its linear component when the more accurate Elmore delay model is used. A simple experiment was conducted to illustrate the validity of this assumption. We present two approaches to solve the retiming problem, both of which have polynomial time complexity. The first one can compute the optimal clock period, while the second one is an improvement over the first one in terms of practical applicability. The second approach gives solutions that are very close to the optimal (0.06% more than the optimal on average) but in a much shorter runtime. The optimally retimed circuit will then be realized physically by placing the registers and finding the net topologies. In contrast to many previous works [Proc. IEEE Int. Conf. Comput.-Aided Des., p. 136, 1998], [IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 22(7) Jul. 2003] that performed simple calculations to determine the register positions, our approach can preserve the optimal clock period that is obtained by the retiming step and utilize as few registers as possible. Minimization of register number saves both area and power in register and clock loading. Our topology optimization step is shown to be optimal for nets with four or fewer pins, and this type of nets constitutes over 90% of the nets in a sequential circuit on average. Using the ISCAS89 benchmark, we tested our algorithm with a 0.35-mum complementary metal-oxide-semiconductor standard cell library. Silicon Ensemble was used to layout the design with a row utilization of 50%. Experimental results showed that our algorithm could find the best sharing of registers for a net in most of the cases, i.e., using the minimum number of registers while preserving the target clock period that is obtained by the retiming step, within a minute run on an Intel Pentium IV 1.5 GHz PC with 512 MB RAM.
Sponsorship	IEEE Council on Electronic Design Automation IEEE Circuits and Systems Society
Starting Page	1648
Ending Page	1660
Page Count	13
File Size	437499
File Format	PDF
ISSN	02780070
Volume Number	26
Issue Number	9
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-09-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Wire Registers Circuit topology Delay Clocks Sequential circuits Integrated circuit interconnections Polynomials Runtime Minimization very-large-scale integration Design automation flip-flops interconnect delay placement registers retiming
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Electrical and Electronic Engineering Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Optimal wire retiming without binary search

Retiming for wire pipelining in system-on-chip

Optimal clock period clustering for sequential circuits with retiming

Optimal FPGA mapping and retiming with efficient initial state computation

Efficient retiming of large circuits

Utilizing the retiming-skew equivalence in a practical algorithm for retiming large circuits

Retiming edge-triggered circuits under general delay models

An efficient and optimal algorithm for simultaneous buffer and wire sizing

Sensitivity guided net weighting for placement-driven synthesis

Wire Retiming Problem With Net Topology Optimization

Similar Documents

Optimal wire retiming without binary search

Retiming for wire pipelining in system-on-chip

Optimal clock period clustering for sequential circuits with retiming

Optimal FPGA mapping and retiming with efficient initial state computation

Efficient retiming of large circuits

Utilizing the retiming-skew equivalence in a practical algorithm for retiming large circuits

Retiming edge-triggered circuits under general delay models

An efficient and optimal algorithm for simultaneous buffer and wire sizing

Sensitivity guided net weighting for placement-driven synthesis

Wire Retiming Problem With Net Topology Optimization