Fast Clock Tree Generation Using Exact Zero Skew Clock Routing Algorithm

INTRODUCTION

At a deep submicron (DSM) silicon technology levels, it is now feasible to integrate all major function of an end product in a single system-on-a-chip (SOC) silicon die (Rashinkar et al., 2001). However, almost all of these chips are still designed based on synchronous clock design. Physically, the clock signal is distributed from an external pad to all similarly clocked synchronizing elements through a distribution network that includes clock distribution logic and interconnects. It serves to unify the design by determining the precise instance in time that the synchronizing elements change state. In order to improve chip performance i.e., to make the chip operates at faster clock speed; the chip designer must ensure that the clock signal is distributed to all the synchronizing elements in the design at the same time. Non-optimal clock behavior is typically caused by either one of these two phenomena: the unbalanced routing to the chip’s synchronizing elements, or the non-symmetric behavior of the clock distribution logic (Jackson et al., 1990). The problem is further complicated by the massive size of modern chip design and the fact that the design usually utilizes more than one clock signal to sync up its function. Each of these clocks may operate at different frequencies (Chi and Huang, 2000). Therefore, the common challenge faced by all chip designers is how can they create a perfect clock distribution scheme that could guarantee all the timing elements scattered all over the chip are activated by the same edge of the clock signal simultaneously. The maximum difference between the arrival times from the clock source to the elements is defined as the clock skew (Chao et al., 1992; Chen and Wong, 1996; Wei et al., 2006). The ideal case is to have all the elements sync up at the same time, which would mean no skew.

The benefits of a zero skew clock distribution are well known and have been proven to affect the performance of a chip significantly. Many researches have pointed out that minimizing clock skew is the most important task when designing a clock network. Jackson et al. (1990), Kahng et al. (1991) and Tsay (1991) have led to many other studies and researches on how to balance a clock network and achieve the zero clock skew targets. More recent studies, such as Pullela et al. (1995), Chen et al. (1999) and Chakraborty et al. (2006) also reveal that reducing clock skew can help to minimize power consumption of large chips, which is very important for chips that are designed for low power application (longer battery life) such as mobile computers and cell phones.

As the chip size grows (in term of increasing number of functional elements), the clock nets get bigger as well. Clock nets have bigger fan-out and have to be distributed over larger areas. It has been observed that existing Clock Tree Generation (CTG) tool performance has deteriorated as the clock net fan out size grow bigger and bigger. The tool execution time is getting slower and slower and it is taking more iteration before the user can get a result that matches the desired outcome. It is suspected that the tool may have hit the limit of its computation capability and is not able to handle nets with large fan-out. Although the CTG tool has been used extensively and successfully before, this capability limitation is slowing the design process.

Since, the problem is the CTG tool capacity, the logical solution is to break the clock nets into smaller parts. This can be accomplished by partitioning the chip into several pseudo-partitions at the layout level, based on the cells placement, as opposed to partitioning at the RTL level, which will be a real design partitioning effort. Partitioning at RTL level will involve some changes to the chip architecture and would increase the complexity of this solution.

The pseudo-partitioning task will be executed after the completion of cells placement stage. The design engineer can output the placement information of the chip and analyze and decide the best way to partition each clock net. The engineer must also make sure that the size of each pseudo-partition should be well below the upper limit of what the CTG tool is capable of handling.

For each of the pseudo-partition, a new buffer will be inserted to act as a new clock source point for each pseudo-partition. Each pseudo-partition will have its own clock source point and that clock point will drive a smaller number of fan-out. The location of the clock source point will be greatly influenced by the floor plan of the chip and the placement location of the fan-out cells as well. Since, the clock net is smaller, the CTG tool should perform well within expectation.

There are many clock routing algorithms that have been proposed throughout the years. The aim of all of these algorithms is to deliver a zero or minimal skew clock routing and distribution.

One of the earliest clock routing algorithms is the H-tree clock routing algorithm. While the H-Tree clock routing algorithm is widely used in the IC industry and their application is not suitable for IC design because cells placement in IC design is not symmetrical (Bakoglu et al., 1986). This fact is also supported by the power PC microprocessor design team. The team has conducted experiment on their chip and concluded that clock tree generation methodology with balance router ensure quick turnaround and produce more than 40% improvement over H-Trees (Carrig et al., 1997; Metra et al., 2003).

The Method of Means and Median (MMM) algorithm by Jackson et al. (1990) has been proposed to overcome the H-Tree algorithm shortcoming but it also has its weaknesses. The difference in wire length from the clock source to each leaf cell can be as large as half the diameter of the chip. The algorithm effectiveness depends heavily on how the cut direction is decided, thus adding lethargy to the algorithm implementation.

The Recursive Geometric Matching (RGM) algorithm was proposed in 1991 by Kahng et al. (1991). It has been proposed to fix the unbalanced wire length problem seen in the MMM algorithm. This algorithm always yields clock tree with perfectly balance path length for trees of two, three, or four terminals, but does not necessarily minimize the skew as it did not consider the cell loading. Like the MMM algorithm, the algorithm cannot guarantee a balanced wire length on certain cases and requires work around that reduces its effectiveness.

The Exact Zero Skew (EZS) algorithm was first proposed by Tsay (1991), from IBM’s (International Business Machine) T.J. Watson Research Center. It considers delay balance instead of the wire length balance has been proposed to deliver better skew performance. The EZS algorithm adopts a bottom up process similar to that of the RGM algorithm. This algorithm achieves delay balance by elongating wires that have smaller delays, therefore, does not require any look ahead techniques that can slow down the execution.

In order to have a fair comparison, simulation exercise to test out the three different algorithms, namely, the MMM, the RGM and the EZS algorithm, to route a clock net with 8 leaf cells has been performed. The wire used for routing was 1 micron wide and the wire resistance per unit length was 1 mΩ and wire capacitance per unit length was 0.075 fF. Each unit length was equivalent to 1 μm. The die area was 8000 by 8000 μ. The overall comparison is shown in the Table 1.

The simulation results clearly show that the EZS algorithm gives the smallest skew (0.004233 psec) and its amount is negligible. However, in this test case, the maximum path delay and the amount of wire length used to route the nets using EZS algorithm are only slightly lower compared to the other algorithm (3.7% difference in maximum path delay difference and 0.4% in wire length). This is consistent with what is reported by Tsay (1991).

Table 1:	Summary of the comparison

Based on all these considerations, the EZS algorithm is recommended and proposed to be deployed in the implementation of the zero skew clock net routing tools.