Paper Review: Improved algorithms for link-based non-tree clock networks for skew variability reduction

Abstract
In the nanometer VLSI technology, the variation effects like manufacturing variation, power supply noise, temperature etc. become very significant. As one of themost vital nets in any synchronous VLSI chip, the Clock Distribution Network (CDN) is especially sensitive to these variations. Recently proposed link-based non-tree [1] addresses this problem by constructing a non-tree that is significantly more tolerant to variations when compared to a clock tree. Although the two algorithms proposed in [1] are effective in reducing the skew variability, they have a few drawbacks including high com- plexity, lengthy links and uneven link distribution across the clock network. In this paper, we propose two new algorithms that can overcome these disadvantages. The effectiveness of the proposed algorithms has been validated using HSPICE based Monte Carlo simulations. Experimental results show that the new algorithms are able to achieve the same or better skew reduction with an average of 5% wire length increase when compared to the 15% wire length increase of the existing algorithms in [1]. Moreover, the new algorithms scale extremely well to big clock networks, i.e., the bigger the clock network, the less overall link cost (less than 2% for the biggest benchmark we have).

Paper Location
ACM Portal

Citation
[1] A. Rajaram, D. Pan, and J. Hu, "Improved algorithms for link-based non-tree clock networks for skew variability reduction," Proceedings of the 2005 international symposium on Physical design, New York, New York, USA: ACM, 2005, p. 62.
Positive

• Good review of the current, main approaches in the field.
• Fair analysis of the rule based algorithm (in the form of merits and demerits.)
• Moves to nLog(n) complexity - a massive improvement over n^3

Negative

• 
  
• Elmore delay is not a particularly accurate model for certain situations, but their algorithm is based on it.



• No algorithmic complexity for rule-delta or even pseudo-code for the rule-delta method.



• While complexity went down for practical purposes, proved to be nearly no visible (to the human time frame) difference in runtime. It's a massive speed improvement for something that didn't particularly need it right now.