Clock Routing Algorithms

CTS (Clock Tree Synthesis) process is carried out after placement of macros and standard cells, because only after placement of cells the exact physical location of cells can be identified which is needed to establish the tree structure in the design. CTS process is carried out before routing, because clock’s routes are to be given more priority when compared to other logical routing.

Even though modern ICs have many I/O ports, only one or two pins are dedicated for clock signal’s entry. So delivering the clock signal to all sequential elements within an IC at zero skew or minimum skew is really a challenging task. To make ease the difficult process of delivering clock signals, a tree like structure is designed and ASIC physical design tools uses these algorithms to maintain the minimum or zero skew. Algorithms used by EDA (Electronic Device Automation) tools are

1)      H tree

2)      X tree

3)      Method of Mean and Median (MMM)

4)      Geometric Matching Algorithm (GMA)

5)      Π (Pi) configuration

H Tree Algorithm

A perfect synchronization between the clock signals is achieved by ‘H’ like model before the arrival of clock to the sub-blocks or synchronous elements. With the help of H-tree zero skew can be easily achieved. The pictorial representation of H-tree is given below in figure-1 with an example.

fig-1: H-tree for 16 point structure

                Consider ‘a’ to ‘p’ as clock pin of sequential elements and the four modules (boxed) are nothing but sub-modules within the top module. All those sequential elements need to get the clock at same time. To achieve this H-tree is built within the top module and the sub module as shown above.

                From figure-1, it is clear that all the clock pins are exactly 9 units from the clock definition point. The points marked are called as tap points and when the signal reaches these tap points, they split into two different directions as shown in figure-1. This is how the clock consumes exactly 9 time units to reach all the sequential elements with zero skew.

X Tree Algorithm

                X tree is similar to H-tree but only difference is the connections are not rectilinear. The module design used for H-tree (fig-1) is taken and X-tree is implemented and the difficulties are shown below.

fig-2: X tree for 16 point structure

• Cross talk
• Routing is not rectilinear

Method of Mean and Median (MMM)

                Method of mean and median follows the strategy similar to H-tree algorithm, provided the H-tree shape is achieved by proper partitioning of the module. It continuously partitions the system into two equal parts (fig-3) and connects the center of the whole circuit (module) to center of the two sub-circuits (sub-module) and thus produces a non-linear tree. Here intersection of wires may be possible. Figure-3 shows the exact flow of MMM and the process of partitioning. Partition keeps on continues until each division contains only one sub-module.

fig-3: MMM (Method of Mean and Median) for 16 point structure

Geometric Matching Algorithm (GMA)

                For explaining H, X and MMM algorithms 16 point structures were taken, and let us consider an 8 point structure for explaining the Geometric Matching Algorithm.

fig-4: GMA (Geometrical Matching Algorithm) for 8 point structure

                In figure-4(A), the physical locations of sub-modules are not symmetric. Developing H-tree among these sub-modules is practically not possible. At first two sub-modules are grouped together and those trees are named as X-1, X-2, X-3 and X-4 (fig-4(B)). The optimal entry point may not be equidistant from the entry point of X-1 and X-2; buffer insertion can balance the delay because of un-equal net length. Then two two-point trees are joined together to form a H like structure. The resultant H-trees are named as X-12 and X-34 (fig-4(C)).

                As shown in fig-4(D), the tap points of both the H structure cannot be connected by using rectilinear nets. In order to connect the two trees the geometrical position of one H-tree is changed compatible to the other tree’s tap point and the resultant will be as shown in fig-4(E).

Pi (π) Configuration

                In pi configuration, the total number of buffers inserted along the clock path is multiple of previous level. This type of structure uses the same number of buffers and geometrical wires and relies on matching the delay components at each level of the clock. The pi structure is clock tree is considered to be balanced. The representation of pi tree is shown in figure-5.

fig-5: Pi (π) Configuration

Π and H-tree are the most efficient clk routing algorithms because of no cross talk and it consumes minimum skew.