CLOCK TREE ROUTING ALGORITHMS

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.