VLSI CAD Software Bookshelf: Bounded-Skew Clock Tree Routing -- Version 1.0: May 2000
Andrew B. Kahng and Chung-Wen (Albert) Tsao 

Contents

I.  Introduction
II.  Data Formats and Usage
III. Benchmarks and reference performance results
IV.  Executables and source codes

I. Introduction

In layout synthesis of high-performance systems, one of the most essential problem is the clock skew minimization. At the same time, a routing solution should have low wiring area to reduce the die size and the capacitive effect on both performance and power dissipation. There had been rapid growth on the ``zero-skew'' clock tree literatures. One of best-known paradigm for zero-skew clock tree routing is the Deferred-Merge Embedding (DME) algorithm. In practice, circuits still operate correctly within some non-zero skew bound, and so the actual design requirement is for a bounded-skew routing tree (BST). Our BST-DME algorithm is an extension of the DME algorithm such that the clock tree wirelength can be further reduced under this more general skew constraint. The problem we address is formulated as follows: Given a set of clock sinks S in the Manhattan plane and a skew bound B, construct a tree over S such that the total wirelength is minimized and the maximum delay difference (skew) from the tree root to each sink in S is at most B. Our algorithm provides unifications of the clock routing and Steiner tree heuristic literatures and give smooth cost-skew tradeoff that enable good engineering solutions between zero-skew and infinity-skew bound. For more detailed, please see the following references:

  • D. J.-H. Huang, A. B. Kahng, and C.-W. A. Tsao, "On the Bounded-Skew Clock and Steiner Routing Problems", Proc. 32nd ACM/IEEE Design Automation Conf., San Francisco, June 1995, pp. 508-513.

  • J. Cong, A. B. Kahng, C.-K. Koh, and C.-W. A. Tsao, "Bounded-Skew Clock and Steiner Routing Under Elmore Delay", Proc. IEEE Intl. Conf. on Computer Aided Design, San Clara, November 5-9, 1995, pp. 66-71.

  • J. Cong, A. B. Kahng, C.-K. Koh and C.-W. A. Tsao, ``Bounded-Skew Clock and Steiner Routing'', ACM Trans. on Design Automation of Electronic Systems, Vol. 4, No. 1, January, 1999.

    II. Sample Data Formats

    The data format for BST-DME is shown as follows: 

       # UCLA MCNC clock benchmark 1.0                       
   # Created       : Wed May 17 10:47:57 PDT 2000  
   # User          : tsao@cs.ucla.edu         
   # PlatForm      : SunOS 5.7 sparc SUNW,Ultra-1
   # Source        : DAC90 paper by Jackson et al. 
   # Note          : Coordinate unit can be micro-meter or anything 
   NumPins : 269 
   PerUnitResistance : 0.016600   Ohm
   PerUnitCapacitance  : 2.7000e-17 Farad 
   Sink  : 0                                  
     Coordinate : 3380 270                    
     Capacitive Load : 5.0e-13  Farad         
   Sink  : 1                                  
     Coordinate : 3020 270                    
     Capacitive Load : 5.0e-13  Farad         
   Sink  : 2                                  
     Coordinate : 1660 500                    
     Capacitive Load : 5.0e-13  Farad         
   ...                  
   ...                  
   ...                  
   Sink  : 268                                  
     Coordinate : 1420 960                    
     Capacitive Load : 5.0e-13  Farad

    III. Benchmarks and reference performance results

    Three set of benchmarks were tested: 

      - IBM benchmarks from R.S. Tsay 
  r1 
  r2  
  r3  
  r4  
  r5 
  - MCNC benchmarks (from DAC90 paper by Jackson et al.) 
  Prim1
  Prim2
  - ISCAS89 benchmarks (from DAC96 paper by J.G. Xi et al.) 
  s1423
  s5378
  s15850
    The results of current version are shown in the following, which may be slightly different from the ones published in the literature due to implementation and the platform (we use SUN Workstation,UltraSPARC-II 400 MHz).

    IBM Benchmark Results
    Skew Bound (pico-second)
    0 1 10 50 100 1000 10000
    Benchmarks Wire-length (units)
    CPU time (min:sec)
    r1
    1,320,665
    1,230,884
    1,070,421
    969551
    930,020
    795,350
    775,922
    00:02
    00:14
    00:25
    00:33
    00:37
    00:42
    00:45
    r2
    2,602,907
    2,421,655
    2,169,791
    1,918,561
    1,888,915
    1,673,720
    1,578,753
    00:05
    00:40
    01:14
    01:42
    01:46
    02:05
    02:13
    r3
    3,388,951
    3,120,071
    2,734,959
    2,405,663
    2,319,911
    2,113,674
    2,035,825
    00:07
    00:49
    01:34
    01:59
    02:15
    02:30
    02:47
    r4
    6828510
    6229330
    5442046
    4935105
    4758984
    5056449
    4443549
    00:19
    02:22
    04:23
    05:18
    05:41
    06:46
    07:10
    r5
    10242660
    9301658
    8033650
    7291868
    6894846
    6321356
    5989367
    00:29
    03:52
    06:47
    08:35
    08:58
    10:22
    11:33
    Prim1
    132120
    131463
    115500
    103496
    97346
    82572
    78900
    00:01
    00:07
    00:12
    00:19
    00:21
    00:25
    00:28
    Prim2
    313613
    301610
    268681
    246976
    231073
    195373
    178080
    00:03
    00:10
    00:20
    00:36
    00:40
    00:53
    01:02
    s1423
    107277
    91605
    75990
    70721
    70523
    65207
    65207
    00:01
    00:03
    00:06
    00:06
    00:07
    00:07
    00:07
    s5378
    176517
    146874
    128184
    115047
    109843
    104098
    104098
    00:01
    00:12
    00:17
    00:21
    00:22
    00:23
    00:23
    s15850
    445659
    359990
    315474
    280302
    282128
    256550
    253206
    00:04
    00:55
    01:19
    01:26
    01:32
    01:42
    01:47

    IV. Executables and source codes
     
    README

    Executables (Sun Solaris/Sparc) (Linux)

    Source codes

    For any compilation or run-time bugs, please report to C.-W. (Albert) Tsao at tsao@cs.ucla.edu

    Maintained by tsao@cs.ucla.edu
    Last updated Sun May 5 2000