Kavita Sharma12:47 AMClock Tree Synthesis,2 Comments
Clock Tree RoutingAlgorithms
The main idea behind using these algorithms to minimize the skew. So how weminimize the skew by using these algorithms. Distribute the clock signal insuch a way that the interconnections (routing wires) carrying the clock signalto the other sub-blocks that are equal in length.
Severalalgorithms exist that are trying to achieve this goal (to minimize theskew).
- H-Tree
- X-Tree
- Methodof Mean and Median
- GeometricMatching Algorithms
- Zeroskew clock routing
Thefirst to four algorithm techniques are trying to make minimize the length andthe last one is to use the actual interconnect delay in making the skew is zero.
H-Tree
Inthis algorithm Clock routing takes place like the English letter H.
Itis an easy approach that is based on the equalization of wire length.
InH tree-based approach the distance from the clock source points to each of theclock sink points are always the same.
InH tree approached the tool trying to minimize skew by making interconnection tosubunits equal in length.
Thistype of algorithm used for the scenario where all the clock terminal points arearranged in a symmetrical manner like as in gate array are arranged in FPGAs.
Infig (a) all the terminal points are exactly 7 units from the reference point P0and hence skew is zero if we are not considering interconnect delays.
Itcan be generalized to 4i. When we are going to up terminals are increased like4, 16, and 64…and so on and regularly placed across the chip in H structure.
 |
| fig: H tree with 16 sink points |
Inthis routing algorithm all the wires connected on the same metal layers, wedon’t need to move horizontal to vertical or vertical to horizontal on twolayers.
Htree do not produce corner sharper than 900 and no clock terminals in the Htree approach in close proximity like X tree.
Advantages:
Exactzero skew in terms of distance (here we are ignoring parasitic delay) due tothe symmetry of the H tree.
Typicallyused for very special structures like top-level clock level distribution notfor the entire clock then distributed to the different clock sinks.
Disadvantages:
Blockagescan spoil the symmetry of the H tree because sometimes blockages are present onthe metal layers.
Non-uniformsink location and varying sink capacitance also complicate the design of the Htree.
X-tree
Ifrouting is not restricted to being rectilinear there is an alternative treestructure with a smaller delay we can use. The X tree also ensures to skew shouldbe zero.
X-tree routing algorithm is similar to H-treebut the only difference is the connections are not rectilinear in the Xtree-based approach.
Althoughit is better than the H tree but this may cause crosstalk due to closeproximity of wires.
LikeH tree this is also applicable for top-level tree and then feeding to the nextlevel tree.
Disadvantages:
CrossTalk due to adjacent wires
ClockRouting is not rectilinear
Bothof the H Tree and X tree approach basically designed for a four array treestructure. Each of the 4 nodes connected to the other 4 nodes in the nextstages so the number of terminal points or sink will grow as the power of 4like 4,16 and 64 and so on.
Thesetwo methods basically did not consider the exact location of the clockterminals it independently create the clock tree and produce a regular array ofsink locations across the surface of the chip.
Butin other approaches, we did not ignore the exact location of the actual clockterminal points so now the question is how we what these approaches will do forexact location.
Theylook at where we required the clocks to be sent w.r.t location and try to buildthe tree systematically and that tree does not look like the H tree and X tree.
Method ofmean & median (MMM) algorithm:
Method of mean and medianfollows the strategy similar to the H-tree algorithm, but it can handle sinklocation anywhere we want.
Step 1: It continuouslypartitions the set of terminals into two subsets of equal parts (median) (AsFig.)
Step2: connects the centerof mass of the whole set (module) to the center of masses of the twopartitioned subset (mean).
How the partitioningis done?
Let Lx denoted the list of clockpoints sorted accordingly to their x-coordinates
Let Px be the median in Lx
-assign points in the list to the left of Pxand Lx
-assign the remaining points to Pr.
Next, we go for a horizontalpartition where we partition a set of points into two sets Pb &Pt
This process is repeated iteratively.
 |
| fig: MMM algorithm |
This algorithm ignores theblockages and produces a non-rectilinear (not regularly spaces) tree. Here somewire may also interact with each other.
It is a top-down approach aswe are partitioning till each partition consist of a single point.
Recursive geometric MatchingAlgorithm (RGM)
This is another binary tree-based routingalgorithm in which clock routing is achieved by constructing a binary treeusing exclusive geometry matching.
Unlike the Method of mean & median (MMM)algorithm which is top-down and this is bottom-up fashion. Here we used theconcept of recursive matching.
To construct a clock tree by using recursivematching determines a minimum cost geometric matching of n sink nodes.
The Center of each segment is called tapping pointand the clock signal is provided at this point then the signal will arrive atthe two endpoints of the segment with zero skew.
Find a set of n/2 line segments that match nendpoints and minimum total length. After each matching step a balance ortapping point is found on each matching segment to maintain zero skew to therelated sinks. These set of n/2 tapping point then forms the input to the nextmatching step.
 |
| Fig:- RGM algorithm |
This bottom-up approach gives a better result thana top-down approach.
Reference:
Algorithms for VLSI PhysicalDesign Automation for clock routing algorithms.
NPTEL video lecture Physical design clocktree synthesis 3 rd and 4th.
