Development of LSI clock routing method Fig.1　Clock Routing Problem Fig.2　Clock Routing for Fig. 1 Fig.3　Nearest Neighbor Graph for Fig. 1 Fig.4　Result by Existing Algorithm（Wire Length=1582） Fig.5　Result by Our Method（Wire Length=1253）
In recent LSI, tens of millions of elements are synchronized with a clock signal. Along with minitualization of semiconductors, signal delay on routing dominates total delay, and therefore, it is highly important to achieve synchronization in LSI by optimizing routings of the clock signal. In this research, we have invented an efficient clock routing method with graph algorithms, circuit theory, and combinatorial optimization techniques.

When there is skew (difference of arrival time of clock signals) at synchronous elements, clock period needs to be extended to guarantee correct operations on logic circuits, which causes performance degradation. Moreover, since long signal delay results in rounding of clock signals and it also causes incorrect operations on logic circuits, the signal delay should be minimized. Therefore, it is crucial for LSI design to generate clock routing where clock signal delay and its variability are minimized with optimal wire length and width which signal delay depends on.

In this research, first, we formulate clock routing as a graph structure whose nodes are synchronous elements. On this graph structure, we analyze a problem to minimize variability of routing lengths strongly correlated with signal delay, and we have proven that this minimization problem is able to be solved by a polynomial time algorithm. On the other hand, the optimization problem of wire length and width is NP-hard, so that
the optimum solution cannot be obtained in practice. For this problem, we have invented a heuristic algorithm that efficiently generates a clock routing with minimal signal delay. In this algorithm, we generate a clock routing with optimal wire length, and then optimize wire width.

In our algorithm, clock routings are generated by iterative clustering on nearest neighbor graphs. In order to obtain optimal wire length in polynomial time, we have proposed a method to limit the number of clusters. Also, with a bucketing technique, our algorithm has linear time complexity to the number of elements for clock routing on actual LSI. Our algorithm achieves 20% reduction of wire length compared with existing algorithms.

The wire width optimization for clock routings generated by our algorithm is accomplished by solving a circuit differential equation for the clock routings. As results with simulation, our method is more effective for larger synchronized elements, and at most 80% reduction of signal delay is achieved in our experiments. As long as we know, these results are the best results so far.

Our clock routing algorithm is highly effective for future LSI design because it takes only a few second to generate a clock routing with current high-end computer. Our algorithm is applied to current actual LSI design, and contributes to the evolution of semiconductor business. In addition, our algorithm is referred by recent LSI design
such as PowerPC of IBM and Motorola.

Publications

 M. Edahiro, "Delay Minimization for Zero-Skew Routing," Proc. IEEE Int'l Conf. on Computer-Aided Design, 1993, pp. 563-566.
 M. Edahiro: “Equi-Spreading Tree in Manhattan Distance,” Algorithmica, 16 (1996), pp.316-338.
 M. Edahiro, "A Clustering-Based Optimization Algorithm in Zero-Skew Routing," Proc. ACM/IEEE Design Automation Conf., 1993, pp. 612-616.
 M. Edahiro, "An Efficient Zero-Skew Routing Algorithm," Proc. ACM/IEEE Design Automation Conf., 1994, pp. 375-380.

Category

Communication
(Electronics)
Electronics & Devices
(Fundamental Technology)

no data.