NDLI: Minimum padding to satisfy short path constraints

Content Provider	IEEE Xplore Digital Library
Author	Shenoy, N.V. Brayton, R.K. Sangiovanni-Vincentelli, A.L.
Copyright Year	1993
Description	Author affiliation: California Univ., Berkeley, CA, USA (Shenoy, N.V.)
Abstract	Combinational circuits are often embedded in synchronous designs with memory elements at the input and output ports. A performance metric for a circuit is the cycle time of the clock signal. Correct circuit operation requires that all paths have a delay that lies between an upper bound and a lower bound. Traditional approaches in delay optimization for combinational circuits have dealt with methods to decrease the delay of the longest path. We address the issue of satisfying the lower bound constraints. Such a problem also arises in wave pipelining of circuits. We propose to handle short path constraints as a post processing step after traditional delay optimization techniques. There are two issues presented in this paper. We first discuss necessary and sufficient conditions for successful delay insertion without increasing delays of any long paths. In the second part, we present a naive approach to padding delays (greedy heuristic) and an algorithm based on linear programming. We describe an application of the theory to wave pipelining of circuits. Results are presented on a set of benchmark circuits, using two delay models.
Starting Page	156
Ending Page	161
File Size	566851
Page Count	6
File Format	PDF
ISBN	0818644907
DOI	10.1109/ICCAD.1993.580048
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1993-11-07
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Delay Combinational circuits Pipeline processing Measurement Clocks Upper bound Optimization methods Constraint optimization Sufficient conditions Heuristic algorithms
Content Type	Text
Resource Type	Article

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