**Clock Tree Routing Algorithms**

The main idea behind using these algorithms to minimize the skew. So how we
minimize the skew by using these algorithms. Distribute the clock signal in
such a way that the interconnections (routing wires) carrying the clock signal
to the other sub-blocks that are equal in length.

Several
algorithms exist that are trying to achieve this goal (to minimize the
skew).

- H-Tree
- X-Tree
- Method of Mean and Median
- Geometric Matching Algorithms
- Zero skew clock routing

The
first to four algorithm techniques are trying to make minimize the length and
the last one is to use the actual interconnect delay in making the skew is zero.

**H-Tree**

In
this algorithm Clock routing takes place like the English letter H.

It
is an easy approach that is based on the equalization of wire length.

In
H tree-based approach the distance from the clock source points to each of the
clock sink points are always the same.

In
H tree approached the tool trying to minimize skew by making interconnection to
subunits equal in length.

This
type of algorithm used for the scenario where all the clock terminal points are
arranged in a symmetrical manner like as in gate array are arranged in FPGAs.

In
fig (a) all the terminal points are exactly 7 units from the reference point P0
and hence skew is zero if we are not considering interconnect delays.

It
can be generalized to 4i. When we are going to up terminals are increased like
4, 16, and 64…and so on and regularly placed across the chip in H structure.

fig: H tree with 16 sink points |

In
this routing algorithm all the wires connected on the same metal layers, we
don’t need to move horizontal to vertical or vertical to horizontal on two
layers.

H
tree do not produce corner sharper than 900 and no clock terminals in the H
tree approach in close proximity like X tree.

**Advantages:**

Exact
zero skew in terms of distance (here we are ignoring parasitic delay) due to
the symmetry of the H tree.

Typically
used for very special structures like top-level clock level distribution not
for the entire clock then distributed to the different clock sinks.

**Disadvantages:**

Blockages
can spoil the symmetry of the H tree because sometimes blockages are present on
the metal layers.

Non-uniform
sink location and varying sink capacitance also complicate the design of the H
tree.

**X-tree**

If
routing is not restricted to being rectilinear there is an alternative tree
structure with a smaller delay we can use. The X tree also ensures to skew should
be zero.

X-tree routing algorithm is similar to H-tree
but the only difference is the connections are not rectilinear in the X
tree-based approach.

Although
it is better than the H tree but this may cause crosstalk due to close
proximity of wires.

Like
H tree this is also applicable for top-level tree and then feeding to the next
level tree.

**Disadvantages:**

Cross
Talk due to adjacent wires

Clock
Routing is not rectilinear

Both
of the H Tree and X tree approach basically designed for a four array tree
structure. Each of the 4 nodes connected to the other 4 nodes in the next
stages so the number of terminal points or sink will grow as the power of 4
like 4,16 and 64 and so on.

These
two methods basically did not consider the exact location of the clock
terminals it independently create the clock tree and produce a regular array of
sink locations across the surface of the chip.

But
in other approaches, we did not ignore the exact location of the actual clock
terminal points so now the question is how we what these approaches will do for
exact location.

They
look at where we required the clocks to be sent w.r.t location and try to build
the tree systematically and that tree does not look like the H tree and X tree.

**Method of mean & median (MMM) algorithm:**

Method of mean and median
follows the strategy similar to the H-tree algorithm, but it can handle sink
location anywhere we want.

Step 1: It continuously
partitions the set of terminals into two subsets of equal parts (median) (As
Fig.)

Step2: connects the center
of mass of the whole set (module) to the center of masses of the two
partitioned subset (mean).

**How the partitioning is done?**

Let Lx denoted the list of clock
points sorted accordingly to their x-coordinates

Let Px be the median in Lx

-assign points in the list to the left of Px
and Lx

-assign the remaining points to Pr.

Next, we go for a horizontal
partition where we partition a set of points into two sets Pb &Pt

This process is repeated iteratively.

fig: MMM algorithm |

This algorithm ignores the
blockages and produces a non-rectilinear (not regularly spaces) tree. Here some
wire may also interact with each other.

It is a top-down approach as
we are partitioning till each partition consist of a single point.

**Recursive geometric Matching Algorithm (RGM)**

This is another binary tree-based routing
algorithm in which clock routing is achieved by constructing a binary tree
using exclusive geometry matching.

Unlike the Method of mean & median (MMM)
algorithm which is top-down and this is bottom-up fashion. Here we used the
concept of recursive matching.

To construct a clock tree by using recursive
matching determines a minimum cost geometric matching of n sink nodes.

The Center of each segment is called tapping point
and the clock signal is provided at this point then the signal will arrive at
the two endpoints of the segment with zero skew.

Find a set of n/2 line segments that match n
endpoints and minimum total length. After each matching step a balance or
tapping point is found on each matching segment to maintain zero skew to the
related sinks. These set of n/2 tapping point then forms the input to the next
matching step.

Fig:- RGM algorithm |

This bottom-up approach gives a better result than
a top-down approach.

Reference:

Algorithms for VLSI Physical
Design Automation for clock routing algorithms.

NPTEL video lecture Physical design clock
tree synthesis 3 rd and 4th.

Very well explained. Thank you so much miss you always give useful content

ReplyDelete