Combinatorial algorithms for fast clock mesh optimization

Ganesh Venkataraman, Zhuo Feng, Jiang Hu, Peng Li

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

Clock mesh has been widely used to distribute the clock signal across the chip. Clock mesh is driven by a top-level tree and a set of mesh buffers. We present fast and efficient combinatorial algorithms to simultaneously identify the candidate locations as well as sizes of the buffers driving the clock mesh. We show that such a sizing offers a better solution than inserting buffers of uniform size across the mesh. Due to the high redundancy, a mesh architecture offers high tolerance toward variations in clock skew. However, such a redundancy comes at the expense of mesh wire length and power dissipation. Based on survivable network theory, we formulate the problem to reduce the clock mesh by retaining only those edges that are critical to maintain redundancy. Such a formulation offers designer the option to tradeoff between power and tolerance to process variations. We present efficient postprocessing techniques to reduce the size of the mesh buffers after mesh reduction. Experimental results indicate that our techniques can result in power savings up to 28% with less than 3.3% delay penalty. We also present driver models that can help in simulating the clock mesh. Such models achieve near-HSPICE accuracy with significant speedup in run time.

Original languageEnglish
Article number4814497
Pages (from-to)131-141
Number of pages11
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume18
Issue number1
DOIs
StatePublished - Jan 2010

Keywords

  • Circuit simulation
  • Clock distribution
  • Low power
  • Variation

Fingerprint

Dive into the research topics of 'Combinatorial algorithms for fast clock mesh optimization'. Together they form a unique fingerprint.

Cite this