A single layer zero skew clock routing in X architecture. (English) Zbl 1191.68132
Summary: With its advantages in wirelength reduction and routing flexibility compared with conventional Manhattan routing, X architecture has been proposed and applied to modern IC design. As a critical part in high-performance integrated circuits, clock network design meets great challenges due to feature size decrease and clock frequency increase. In order to eliminate the delay and attenuation of clock signal introduced by the vias, and to make it more tolerant to process variations, in this paper, we propose an algorithm of a single layer zero skew clock routing in X architecture (called Planar-CRX). Our Planar-CRX method integrates the extended deferred-merge embedding algorithm (DME-X, which extends the DME algorithm to X architecture) with modified Ohtsuki’s line-search algorithm to minimize the total wirelength and the bends. Compared with planar clock routing in the Manhattan plane, our method achieves a reduction of 6.81% in total wirelength on average and gets the resultant clock tree with fewer bends. Experimental results also indicate that our solution can be comparable with previous non-planar zero skew clock routing algorithm.
MSC:
| 68M99 | Computer system organization |
| 68W35 | Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C90 | Applications of graph theory |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
References:
| [1] | Ting H C, Yu C H, Jan M H, et al. Zero skew routing with minimum wirelength. IEEE Trans Circuit-II, 1992, 39(11): 799–814 · Zbl 0825.94280 · doi:10.1109/82.204128 |
| [2] | Cong J, Cheng K K. Minimum-cost bounded-skew clock routing. In: IEEE Symposium on Circuits and Systems, Seattle, WA, USA. 1995. 215–218 |
| [3] | Tsao C W A, Koh C-K. UST/DME: a clock tree routing for general skew constraints. In: IEEE/ACM International Conference on Computer-Aided Design, San Jose, California, USA. 2000. 400–405 |
| [4] | Cai Y C, Xiong Y, Hong X L, et al. Reliable clock tree routing algorithm with process variation tolerance. Sci China Ser F-Inf Sci, 2005, 48(5): 670–680 · Zbl 1161.68305 · doi:10.1360/04yf0232 |
| [5] | Zhu Q, Wayne Wei-Ming Dai. Planar clock routing for high performance chip and package co-design. IEEE Trans VLSI Syst, 1996, 4(2): 210–226 · doi:10.1109/92.502193 |
| [6] | Kahng A B, Tsao C W A. Planar-DME: a single-layer zeroskew clock tree router. IEEE Trans Comput Aided Des, 1996, 15(1): 8–19 · doi:10.1109/43.486268 |
| [7] | Kim H, Zhou D. Efficient implementation of a planar clock routing with the treatment of obstacles. IEEE Trans Comput Aided Des, 2000, 19(10): 1220–1225 · doi:10.1109/43.875342 |
| [8] | Jackson M A B, Srinivasan A, Kuh E S. Clock routing for high performance ICs. In: Proc of ACM/IEEE Design Automation Conf, Orlando, Florida, USA. 1990. 573–579 |
| [9] | Zeng X, Zhou D, Li W. Buffer insertion for clock delay and skew minimization. In: Porc of ACM/IEEE Symp on Physical Design, Monterey, California, USA. 1999. 36–41 |
| [10] | http://www.xinitiative.org |
| [11] | Hong X L, Zhu Q, Jing T, et al. Non-rectilinear on chip interconnect-an efficient routing solution with high performance (in Chinese). Chinese J Semicond, 2003, 24(3): 225–233 |
| [12] | Teig S. The X architecture: not your father’s diagnoal wiring. In: Proc of SLIP, San Diego, California, USA. 2002. 33–37 |
| [13] | Ho T H, Chang C F, Chang Y W, et al. Multilevel full-chip routing for the X-based architecture. In: Proc of ACM/IEEE Design Automation Conf, Anaheim, California, USA. 2005. 597–602 |
| [14] | Shen W X, Cai Y C, Hu J, et al. High performance clock routing in X-architecture. In: Proc of IEEE Int Symp on Circuits and Systems, Kos Island, Greece. 2006. 2081–2084 |
| [15] | Cheon Y, Ho P H, Kahng A B, et al. Power-aware placement. In: Proc of ACM/IEEE Design Automation Conf, Anaheim, California, USA. 2005. 795–800 |
| [16] | Edahiro M. A clustering-based optimization algorithm in zeroskew routings. In: Proc ACM/IEEE Design Automation Conference, Dallas, Texas, USA. 1993. 612–616. |
| [17] | Mehta A, Chen Y P, Menezes N, et al. Clustering and load balancing for buffered clock tree synthesis. In: Proc IEEE International Conference on Computer Design, Austin, Texas, USA. 1997. 217–223 |
| [18] | Shelar R S. An efficient clustering algorithm for low power clock tree synthesis. In: Porc of ACM/IEEE Symp on Physical Design, Austin, Texas, USA. 2007. 181–188 |
| [19] | Ohtsuki T. Gridless routers-new wire routing algorithms based on computational geometry. In: Proc of Int Conf Circuits System, Beijing, China. 1985. 802–809 |
| [20] | Ohtsuki T. Layout design and verification, Advances in CAD for VLSI. Amsterdam: North-Holland, 1996, Vol. 4, ch. 9 |
| [21] | Tsay R S. Exact zero skew. In: Proc IEEE Int Conf Computer Aided Design, Santa Clara, California, USA. 1991. 336–339 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
