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: