International Journal of Recent Technology and Engineering (IJRTE)

ISSN: 2277-3878, Volume-7 Issue-4, November 2018

On Timing Closure: Hold-Violation Removal

using Insertion of Buffers, Inverters and Delay
Cells
S. Aruna Mastani, Patra Suresh Reddy

 violations are the delay insertion technique used in clock

Abstract: Timing closure plays a major role in the Physical period minimization [2,3,5,7] which specifies the insertion
design synthesis. In the process of timing optimization, buffers, delay as unit delay elements [3], fixing hold violations for
inverters, delay cells are used as delay elements inorder to speedup ultra-low voltage designs [8],and recently, fixing hold
the circuit. Given with the violated path proper selection of
combination of delay elements is to be made to meet the hold violations by reducing the number of buffer insertions [1].
requirement of the path. Here, in this work a standard industrial However, in modern industrial designs, other than unit delay
design is taken having 5241 violated paths. For these paths, hold elements discrete type of buffers or inverters are considered in
time is computed as per the linear programming optimization. delay insertion.
Timing closure is done by various combinations of buffers, In industrial designs, cell libraries are different for setup
inverters and delay cells. Discrete buffers, Complex timing
constraints and accurate timing models/analysis make time
and hold time constraints, means delay of the delay elements
consuming and problem difficult to solve. The linear (buffers, inverters, delay cells)caused by setup time
programming-based methodology is presented to model the setup constraints is different from hold time constraints. So, hold
and hold-time constraints. Then based on the solution to the optimization need to consider these challenges.
linear programming optimization, buffers, inverters and delay In this paper, an optimization flow is presented to fix hold
cells are inserted as delay elements to solve hold violations. The
violations by placing buffers, inverters and delay cells as
implemented approach where delay cells, buffers, inverters are
used as delay elements for optimization and using only buffers as delay elements. The optimization flow includes first linear
delay elements in optimization process are tested on industrial programming based optimization that specifies different
design together with the industrial hold optimization flow, and delays which are occurred between setup time and hold time
better results achieved in terms of minimum hold slack, hold constraints. Second, bottom up delay insertion algorithm
violations and utilization are reported.¬¬ Compared to the delay which is a reliable solution to the linear programming
insertion using buffers only, the implemented approach can
obtain 31% worst hold slack reductions and better utilization for
optimization by inserting delay elements. In the experimental
the industrial circuit level design. Analysis of timing paths and results, comparison of delay insertion using only buffers with
removal of hold violation problem in physical design flow is buffers, inverters and delay cells as delay elements on modern
implemented using TCL and PERL scripts in cadence encounter industrial design that runs together with a Industrial hold
tool. optimization flow, results shows that the implemented
Index Terms: Delay Insertion, Hold Violation, Physical algorithm achieves better results in terms of minimum hold
Design, Utilization. slack, hold violations and utilization.

I. INTRODUCTION II. PRELIMINARIES

Timing closure plays a major role in physical design Let D be the given design that consists of combinational
synthesis. Timing constraints are mainly classified into setup circuits set as C, combinational circuits pins as P, and nets N
and hold-time constraints. Signal transitions need to arrive too which defines the pins connectivity. Let PI be the primary
early for setup constraints leads to long path while for hold inputs and the sequential cells outputs (for example, latches
time constraints signal transitions need to arrive too late leas and flip-flops), and PO be the primary outputs and the
to short path. Techniques that are available for timing sequential cells inputs. Furthermore, B is the set of buffers,
optimization are buffer insertion, cell sizing and logical inverters and delay cells that are defined in the standard cell
restructuring. Buffers, Inverters or delay cells are used as library, which have different technology and area parameters
delay elements in-order to speed up the circuit. In this paper, for each delay element.
Timing closure is done by various combinations of buffers, Furthermore, the setup constraints from the standard cell
inverters and delay cells. library are different to the hold time constraints. Thus, the
Generally, hold violations are considered after performing delay information is considered individually for the setup and
setup optimization. Hold violations are solved by inserting hold-time constraints.
delay elements. Existing approaches for removing hold For the setup constraints, the setup slack with respect to the
setup constraints at pin p is given by
Revised Version Manuscript Received on 30 November, 2018. Setup_slack = setup_required time – setup_actual arrival
Dr. S.Aruna Mastani, Assistant Professor, Department of ECE, JNTUA time
College Of Engineering, Ananthapuramu (A.P), India.
Patra Suresh Reddy, Student, M.tech in Digital Electronics and
Communication Engineering, JNTUA College of Engineering,
Ananthapuramu (A.P), India.

Published By:
Blue Eyes Intelligence Engineering
195 & Sciences Publication
 On Timing Closure: Hold-Violation Removal using Insertion of Buffers, Inverters and Delay Cells

Similarly, for the hold time constraints, The hold slack with represents hold violated paths are to be considered and also
respect to the hold-time constraints at pin p is given by the total negative setup slack has to be maintained, it is natural
Hold_slack = hold_actual arrival time – hold_required time that insertion of delay is allowed to the pins that are having
Timer engine gives the required time and arrival setup slack greater than zero. Therefore, the extraction of the
time.Negative values of setup slacks means setup violations pins with hold slacks less than zero and setup slacks greater
and negative values of hold slacks means hold violations. For than zero is required to get C∗ from a combinational circuit.
on-timing closure, the design must require no timing The time taken by the flop to stable while taking data at
violations. For all the pins in PO, Let TNS be the total active edge can be said as setup time. setup analysis done
negative setup slack and THS be the total negative hold slack. based on time period with which they are operating,
Hold violations are fixed after optimization of setup combinational delay between them, transition time of launch
violations. While optimizing the hold violations total negative flop, launch and capture time,when to flops are
setup slack need to be taken care. While buffers, inverters, communicating each other. This can be well explained using
delay cells are inserted as delay elements for fixing hold mathematical equation shown below.
violations, the inserted delay elements can increase the power Tcq + T comb + T launch ≤ Tclockperiod + T setup + T capture + 2T∆j
consumption and area of the design. Therefore, the delay Skew = T capture – T launch
insertion problem for removal of hold violation is given by: Where, 2T∆j is jitter, T comb is the combinational delay and T
Given a circuit level design and a standard cell library, finding cq is the delay of the flop from clock pin to output pin.
a delay solution such that total negative hold slack and the The right side of the equation is called as required time
cost of insertion of delay elements which means area and which is the time taken by the clock pathand left side is the
power consumption both are reduced. Furthermore, total arrival time that is taken by the data to travel through data
negative setup slack is to be taken care. path.
Here in this paper, the implementing approach uses buffers, The difference between the required arrival time and the
inverters and delay cells as delay elements. Over buffering actual arrival time of the data called as setup slack. This
results increase in power consumption and area, so better to should be maintained positive as a indication that the data can
avoid over-buffering. Some other different techniques for travel without any loss. Skew is nothing but the difference
fixing hold violations are cell sizing and logical restructuring. between capture and launch path.
The implementing approach shows better results using The time taken to hold the input data should not change
buffers, inverters and delay cells as delay elements by running at active edge can be hold time. For this analysis is made
together with industrial hold optimization technique. according the timing path and data path present between the
An industrial timing engine is required for providing flops. Except the time period remaining all parameters are
timing related information such as delay of the cells, the considered for hold analysis.
required arrival times, and the actual arrival times of the pins Tcq + Tcomb + Tlaunch≥ Thold+ Tcapture+ 2T∆j
with respect to the corresponding constraints (i.e.,setup The difference between arrival time and required time is
constraints for the setup slack and the hold time constraints called as hold slack. The hold slack should maintain positive
for the hold slack). The cell delay model being used is taken
from the lookup table in which two inputs are given by slew
and load capacitance, respectively, whereas the slew is also
taken from the slew lookup table.

III. LINEAR PROGRAMMING OPTIMIZATION Figure 1: Delay insertion: a) place delay cell at the cell X
output, b) place delay cell at one of the cell Z inputs.
Given with the violated path proper selection of
combination of delay elements is to be made to meet the hold Let di,b be the delay of the delay element b when inserted
requirement of the path. Here, in this work a standard circuit delay element is either buffer, inverter or delay cell b across
level design is taken as the reference. For these paths, hold pin i. For any source/sink cell C of pin i, dbC be the change
time is computed as per the linear programming optimization. in the delays of the cell C before and after inserting delay
Timing closure is done by various combinations of buffers, element b at pin i. Figure 1a) shows that the delay cell b is
inverters and delay cells. Discrete buffers, Complex timing placed at the cell X output pin i. Therefore, delays introduced
constraints and accurate timing models/analysis make time by placing this delay element is di,b + dbX + dbY + dbZ . In
consuming and problem difficult to solve. The linear Figure 1b), a delay cell b is placed at the cell Z inputs i, so the
programming-based methodology is presented to model the overall delay that is specified by this delay element is di,b + dbX
setup and hold-time constraints. Then based on the solution to + dbZ. Here, the overall delay calculation has to be computed
the linear programming optimization, buffers, inverters and for hold time constraints and setup constraints, respectively.
delay cells are inserted as delay elements to solve hold Thus, for the hold time constraints hd is used and for setup
violations. constraints sd is used in the following equation. HIDi,b
The input to the linear programming model is a represents the overall hold delay of placing delay cell b across
combinational circuit C∗ such that for any pin p of C∗ , hold pin i, and it is given by:
slack is less than zero and setup slack should be greater than
zero. Generally, for fixing the hold violation removal
problem, the pins that are having negative hold slacks which

Published By:
Blue Eyes Intelligence Engineering
196 & Sciences Publication
 International Journal of Recent Technology and Engineering (IJRTE)
ISSN: 2277-3878, Volume-7 Issue-4, November 2018

HIDi.b = hdi,b + hdbdriver_cell(i) + b

c increase in delay elements leads to increase in area and power
consumption of the design which effects the utilization of the
Similarly for setup, design. Over buffering should be avoided. So, if d h` > DH +
margin (20 ps), then C` is removed. Next, C` is dominated by
SIDi.b = sdi,b + sdbdriver_cell(i) + b
c
any another existing candidate C* (L*, dh*, ds*, A*), if dh` < dh*
and A` > A* , then the candidate C` is removed. Decreasing dh
Here the delay is computed from the lookup table and the is not allowed. In this experiment, the process stops quickly.
output slew is computed from the slew table accordingly. The delay solution for the selected candidate has to be the
largest ratio of dh/A.
IV. BOTTOM-UP DELAY INSERTION At last a bottom up delay methodology is implemented to
realize all the pins which specifies the chosen delay elements
Here, in this paper after computing the hold delay that is are placed in a bottom up topological order (i.e., from sink to
required for removing the hold violations is based on the source).
linear programming optimization. The amount of delay that is The linear optimization flow for an industrial level
obtained from the linear programming optimization is equal design is as shown in Figure 2. Flow starts from launch timer
to the delays introduced by the delay insertion of combination which is launched by the timer engine, next the pins are
of buffers, inverters and delay cells. In bottom up delay processed for getting a combinational circuit which contains
insertion, first, a dynamic programming algorithm is the hold violated paths and setup met paths. Then, the hold
implemented in order to insert combination of delay elements violated paths are processed through a linear programming
such as buffers, inverters and delay cells to satisfy the based optimization to fix the delays that are to be inserted for
required hold delay that is calculated from the linear removing the hold violation problem. Here, the inserted delay
programming optimization. Second, a bottom up delay makes hold slack value positive by taking care of setup slack
methodology is implemented to realize all the pins in a circuit value.
level design.
For a given pin p, let DH be the hold delay and DS be the
setup delay. Finding a delay solution from a standard cell
library B is as follows: The hold delays that are obtained from
the linear programming optimization have to be considered
here
The hold delays that are introduced by the selective delay
elements should be close to the pin p hold delay DH as
possible.
The setup delays that are introduced by the selective delay
elements should not be more than the setup delay DS.
Area of the selected delay elements is to be minimum.
To realize the above problem, an algorithm is implemented
which is said to be a dynamic programming (DP) based
algorithm. In this algorithm, delay candidates C (L, dh, ds, A)
that are taken from the standard cell library. Where the list of
the selective delay elements is given by L, the hold delay that
is produced by placing L is given by dh, the setup delay that is
produced by placing L is given by ds, and the area is given by Figure 2: Implemented optimization flow
A. Here comparison of two candidates is done for better The bottom-up delay (buffers, inverters or delay cells)
realization of hold delay, for each delay element that is taken insertion is then applied to solve the hold violation problem.
from the standard cell library B, another existing delay Here, the chosen delay element is placed in between sink and
candidate is replaced to find out the new setup and hold source of a violated hold path. The flow stops after computing
delays that are introduced by the new candidate. Let the new the possible hold violated paths which results in reducing the
candidate be C′ (L′, d′h, d′s, A′), now the realization of a delay minimum worst hold slack value.
solution is done by comparing those two candidates C and C`.
First, if the setup delay of the new candidate is greater V. EXPERIMENTAL RESULTS
than the setup delay DS of pin p, then the new candidate C` is
The physical design flow is implemented using cadence
removed immediately, next, if the hold delay dh` of the new
encounter tool. Analysis of timing paths and removal of hold
candidate C` is less than are equal to the hold delay d h of the
violation problem in physical design flow is implemented
original selected candidate C, then also C` is removed. The
using TCL and PERL scripts. The results are compared based
reason for removing the candidate is that the buffers, inverters
on utilization, violated paths; hold slack values i.e., WHS
and delay cells are considered as delay elements. While
(Worst Hold Slack) and THS (Total Hold Slack). Utilization:
placing delay elements from sink to source the main criteria is
to maximize the hold delay. It is better to increase the hold
delay by placing more number of delay elements between sink
and source; however, one must be keep in a mind that the

Published By:
Blue Eyes Intelligence Engineering
197 & Sciences Publication
 On Timing Closure: Hold-Violation Removal using Insertion of Buffers, Inverters and Delay Cells

sudden jump of standard cell utilization is bad (i.e., from Results of the industrial hold optimization using buffers is
one stage to another stage increment in utilization is to be less shown in table3 and the design is having utilization of
as ~5%) and utilization should be less than 60% after route 70.057%. Table 3 shows register to register path is having
stage for addition of circuitry in future use. Slack: WHS worst hold slack value of 130ps and also 31 reg2reg paths and
should be minimum for the violating paths in-order to meet default paths 14 are violated which results in a total hold slack
the timing closure at ECO (Engineering Change Order) stage. value of 6.24 ns.
Our main aim is to achieve minimum utilization with Table 4: Results of the implemented approach after CTS
minimum hold slack value. stage
Table 1: Design specifications: Utilization of the design is 39.623%
Design type Block (tile) Hold mode All Reg2reg Reg2cgate Default
Rectangular in shape WHS (ns) -0.13 -0.13 0.25 0.03
Tile dimensions Width = 297.92 µm, Height THS (ns) -11.84 -11.84 0 0
= 1948.52µm Violating
Standard cells count 14541 136 136 0 0
paths
Total standard cell area 124789.52 µm2 All paths 12763 7680 200 8143
Number of nets 15879
Results of the implemented approach after Clock Tree
Number of pins 59043
Synthesis (CTS) stage using buffers, inverters and delay cells
Number of primary input 798 together with industrial hold optimization flow are shown in
ports table4 and the design is having utilization of 39.623%.
Number of primary 682 Results of the implemented approach after Routing stage
output ports
using buffers, inverters and delay cells together with
Clock period 4 ns
industrial hold optimization flow are shown in table5 and the
Initial utilization 21.496 % design is having utilization 39.685%.
The experiment is done on industrial design having design Table 5: Results of the implemented approach after
specifications as shown in table1. Optimization techniques routing stage
are used in each step to meet the desired timing constraints in Utilization of the design is 39.685%
the design flow. Hold
Table 2: Timing summary and initial statistics of the industrial All Reg2reg Reg2cgate Default
mode
design WHS (ns) -0.09 -0.09 0.18 0.29
Hold All Reg2reg Reg2cgate Default THS (ns) -0.15 -0.15 0 0
mode Violating
2 2 0 0
WHS -0.25 -0.14 -0.05 -0.25 paths
(ns) All paths 12763 7680 200 8143
THS (ns) -374.33 -369.04 -1.69 -3.61
Violating 5241 5155 70 16 Compared to table3 in which buffers are used together with
paths industrial hold optimization, slack has been improved about
All paths 12763 7680 200 8143 31% as shown in table5 where buffers, inverters and delay
cells are used as delay elements (i., e.130 ps to 90 ps).
Timing summary and initial timing statistics of the design is Violating paths in table3 are 45 whereas in the implemented
shown in table2. Initial standard cell utilization is approach only 2 paths are violated having a total hold slack
21.496%.Our main focus is done on reg2reg paths which value of 150 ps. Furthermore utilization of the design in the
represents register to register path. Reg2cgate path specifies implemented approach is 39.685% which represents better
the path from clock pin to the register in which additional utilization and also additional logic circuitry can be added for
logic circuitry is added to decrease the power consumption of future purpose.
the design.
Table 3: Results of the industrial hold optimization using VI. CONCLUDING REMARKS
buffers In this paper, a standard industrial circuit level design is
Utilization of the design is 70.057% taken to compare two methodologies. One method uses only
Hold buffers for optimization and another method uses
All Reg2reg Reg2cgate Default combination of delay elements such as buffers, inverters and
mode
WHS delay cells. The implemented method uses insertion of delay
-0.41 -0.13 0.26 -0.41 elements for timing closure. At first, a linear programming
(ns)
THS (ns) -6.24 -3.13 0 -3.11 optimization is used to compute the amount of hold delay that
Violating is required to overcome
45 31 0 14
paths
All paths 12763 7680 200 8143

Published By:
Blue Eyes Intelligence Engineering
198 & Sciences Publication
 International Journal of Recent Technology and Engineering (IJRTE)
ISSN: 2277-3878, Volume-7 Issue-4, November 2018

the violated hold path slack. Then the delay that is

obtained is realized as a combination of delay elements with
the help of a dynamic process based algorithm in bottom up
delay insertion. The optimization flow for a circuit level
design is also presented. The implemented approach where
combination of delay elements are used for optimization and
using buffers only for optimization are tested on industrial
design together with the state of the art industrial hold
optimization flow, better results are achieved in terms of
minimal hold slack, hold violations and utilization are
reported.

REFERENCES
1. Pei-Ci Wu ; Martin D. F. Wong ; Ivailo Nedelchev ; Sarvesh Bhardwaj
; Vidyamani Parkhe on timing closure: buffer insertion for hold
violation removal 51st ACM/EDAC/IEEE Design Automation
Conference (DAC) Pages:1 – 6,2014
2. S.-H. Huang, C.-H. Cheng, C.-M. Chang, and Y.-T. Nieh. Clock
period minimization with minimum delay insertion. InDesign
Automation Conference, 2007. DAC’07. 44th ACM/IEEE, pages
970–975. IEEE, 2007.
3. S.-H. Huang, G.-Y. Jhuo, and W.-L. Huang. Minimum buffer
insertions for clock period minimization. In Computer Communication
Control and Automation (3CA), 2010 International Symposium on,
volume 1, pages 426–429.IEEE, 2010.
4. A.B. Kahng, J. Lienig, I. L. Markov, and J. Hu. VLSI Physical Design:
From Graph Partitioning to Timing Closure. 2011..
5. B. Lin and H. Zhou. Clock skew scheduling with delay padding for
prescribed skew domains. In Design AutomationConference, 2007.
ASP-DAC’07. Asia and South Pacific,pages 541–546. IEEE, 2007
6. M. M. Ozdal, S. Burns, and J. Hu. Gate sizing and device technology
selection algorithms for high-performance industrial designs. In
Proceedings of the InternationalConference on Computer-Aided
Design, pages 724–731.IEEE Press, 2010.
7. N. V. Shenoy, R. K. Brayton, and A. L. Sangiovanni-Vincentelli.
Minimum padding to satisfy short path constraints. In
Computer-Aided Design, 1993.ICCAD-93. Digest of Technical
Papers., 1993 IEEE/ACM International Conference on, pages
156–161. IEEE, 1993.
8. W.-P. Tu, C.-H. Chou, S.-H. Huang, S.-C. Chang, Y.-T. Nieh, and
C.-Y. Chou. Low-power timing closure methodology for ultra-low
voltage designs. In Proc. Int.Conf. on Computer-Aided Design, pages
697–704, 2013.

Published By:
Blue Eyes Intelligence Engineering
199 & Sciences Publication