Algorithm for zero-skew clock tree routing with buffer insertion

Y. P. Chen, D. F. Wong

Research output: Contribution to journalConference articlepeer-review


We study the problem of multi-stage zero skew clock tree construction for minimizing clock phase delay and wire-length. In existing approaches clock buffers are inserted only after clock tree is constructed. The novelty of this paper lies in simultaneously perform clock tree routing and buffer insertion. We propose a clustering-based algorithm which uses shortest delay as the cost function. We show that the feasible positions for clock tree nodes and buffers can be generalized from diagonal segments (merging segments) to rectangles (merging blocks). Buffers are large components and must be placed pairwise disjointly. We also show that the problem of finding legal positions for buffers such that no buffers overlap can be formulated as a shortest path problem on graphs, and can be solved by the Bellman-Ford algorithm. By making use of the special properties of the graphs, we further speedup the Bellman-Ford algorithm. The experimental results show that our algorithm greatly outperforms the approach of inserting buffers after clock routing.

Original languageEnglish (US)
Pages (from-to)230-236
Number of pages7
JournalProceedings of European Design and Test Conference
StatePublished - 1996
Externally publishedYes
EventProceedings of the 1996 European Design & Test Conference - Paris, Fr
Duration: Mar 11 1996Mar 14 1996

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering


Dive into the research topics of 'Algorithm for zero-skew clock tree routing with buffer insertion'. Together they form a unique fingerprint.

Cite this