Thursday, January 21, 2010

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 Review: Combinatorial Algorithms for Fast Mesh Optimization

Abstract
We present a fast and efficient combinatorial algorithm to simul- taneously identify the candidate locations as well as the sizes of the buffers driving a clock mesh. Due to the high redundancy, a mesh architecture offers high tolerance towards variation in the clock skew. However, such a redundancy comes at the expense of mesh wire length and power dissipation. Based on survivable net- work theory, we formulate the problem to reduce the clock mesh by retaining only those edges that are critical to maintain redun- dancy. Such a formulation offers designer the option to trade-off between power and tolerance to process variations. Experimental results indicate that our techniques can result in power savings up to 28% with less than 4% delay penalty.

Paper Review: Activity-Driven Clock Design

Abstract
In this paper, we investigate reducing the power consumption of a synchronous digital system by minimizing the total power consumed by the clock signals. We construct activity-driven clock trees wherein sections of the clock tree are turned off by gating the clock signals. Since gating the clock signal implies that additional control signals and gates are needed, there exists a tradeoff between the amount of clock tree gating and the total power consumption of the clock tree.We exploit similarities in the switching activity of the clocked modules to reduce the number of clock gates. Assuming a given switching activity of the modules, we propose three novel activity-driven problems: a clock tree construction problem, a clock gate insertion problem, and a zero-skew clock gate insertion problem. The objective of these problems is to minimize system’s power consumption by constructing an activity-driven clock tree.We propose an approx- imation algorithm based on recursive matching to solve the clock tree construction problem. We also propose an exact algorithm employing the dynamic programming paradigm to solve the gate insertion problems. Finally, we present experimental results that verify the effectiveness of our approach. This paper is a step in understanding how high-level decisions (e.g., behavioral design) can affect a low-level design (e.g., clock design).

Paper Review: Clock Skew Optimization

Abstract

This paper investigates the problem of improving the per- formance of a synchronous digital system by adjusting the path delays of the clock signal from the central clock source to individual flip-flops. Through the use of a model to detect clocking hazards, two linear pro- grams are investigated: 1) Minimize the clock period, while avoiding clock hazards. 2) For a given period, maximize the minimum safety margin against clock hazard. These programs are solved for a simple example, and circuit simulation is used to contrast the operation of a resulting circuit with the conventionally clocked version. The method is extended to account for clock skew caused by relative variations in the drive capabilities of N-channel versus P-channel transistors in CMOS.

Paper Review: Minimum-Cost Bounded-Skew Clock Routing

Abstract

In this paper, we present a new clock routing algorithm which minimizes total wirelength under any given path-length skew bound. The algorithm constructs a bounded-skew tree (BST) intwosteps: (i) a bottom-upphase to construct a binarytree of shortest-distance feasible regions which represent the loci of possible placements of clock entry points, and (ii) a top-down phase to determine the exact locations of clock entry points.Experimental results show that our clock routing algorithm, named BST/DME, can produce a set of routing solutionswith skew and wirelength trade-off.

Monday, January 18, 2010

Updates for 01/18/10

Main Goal:
Build on clock router to add in effects of stub-tuning, rounded
corners and made purely planar

Accomplished:
  • Understand that single-ended lines do not have a simple impedance, ground return always plays a key role.
  • Read through and found the knee frequency of a 10ps rise time.
  • Found the geometry of corners with OPC off may be relatively close to the desired corners for large power transfer. Also discovered that on the large metal wires, the feature size is large enough that OPC may not need to be done in the first place.
  • Wrote a 1-page summary for Matt to edit for SRC
  • Toyed around with Spice and Matlab picking up certain bits of the command line ngspice
  • Spent a ridiculous amount of time trying to reproduce the first graph in RLC interconnect, and failing. Off by several orders of magnitude.

Goals:
  • Modify clock code to use a planar DME algorithm
  • Modify clock code to consider rounded corners
  • Figure out why the graph is wrong
  • Add in third harmonic from model in RLC Interconnect to have accuracy above 9GHz (Need the graph to get a good estimate of frequency accuracy limit)

Read:
223:
[1] G. Venkataraman, Z. Feng, J. Hu, and P. Li, "Combinatorial
algorithms for fast clock mesh optimization," Proceedings of the 2006
IEEE/ACM international conference on Computer-aided design, ACM, 2006,
p. 567.

280G:
[1] Z. Feng, Y. Hu, L. He, and R. Majumdar, "IPR: In-Place
Reconfiguration for FPGA Fault Tolerance," ICCAD, ICCAD, 2009, pp.
1-4.

EE270:
[1] D. Panescu, "Emerging technologies. Implantable neurostimulation
devices.," IEEE engineering in medicine and biology magazine: the
quarterly magazine of the Engineering in Medicine \& Biology Society,
vol. 27, 2009, p. 100.
[2] B.S. Wilson and M.F. Dorman, "The surprising performance of
present-day cochlear implants.," IEEE transactions on bio-medical
engineering, vol. 54, 2007, pp. 969-72.

Monday, January 11, 2010

Updates for 01/11/10

Main Goal:
Build on clock router to add in effects of stub-tuning, rounded
corners and made purely planar

Accomplished:
  •  Seg faulted current VLSIDA clock router under Ubuntu. (After many build issues)
  • Read deeply on current clock routing techniques
  • Stumbled upon the 280G paper I would like to review
  • Got clock routing code running on Quiche

Goals:
  • Understand characteristic impedance of single-ended lines better
  • Understand stub tuning of single-ended lines better
  • Simulate the spectral components of a 10ps rise time
  • Simulate loss due to 90 degree corners
  • Modify clock code to use impedance instead of purely RC components
  • Modify clock code to consider rounded corners by way of no OPC
  • Look into geometry of corners when OPC is turned off.


Read:
[1] E. Friedman, "An RLC interconnect model based on fourier
analysis," IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems, vol. 24, 2005, pp. 170-183.
[2] Z. Jiang, S. Hu, J. Hu, Z. Li, and W. Shi, "A new RLC buffer
insertion algorithm," Proceedings of the 2006 IEEE/ACM international
conference on Computer-aided design, ACM, 2006, p. 557.
[3] B. Taskin, J. Demaio, O. Farell, M. Hazeltine, and R. Ketner,
"Custom topology rotary clock router with tree subnetworks," ACM
Transactions on Design Automation of Electronic Systems, vol. 14,
2009, pp. 1-14.
[4] F. O'Mahony, C.P. Yue, M.a. Horowitz, and S.S. Wong, "Design of a
10GHz clock distribution network using coupled standing-wave
oscillators," Proceedings of the 40th conference on Design automation
- DAC '03, 2003, p. 682.
[5] M. El-Moursy and E. Friedman, "Exponentially tapered H-tree clock
distribution networks," IEEE Transactions on Very Large Scale
Integration(VLSI) Systems, vol. 13, 2005, p. 971–975.
[6] J. Wood, T. Edwards, and S. Lipa, "Rotary traveling-wave
oscillator arrays: a new clock technology," IEEE Journal of
Solid-State Circuits, vol. 36, 2001, pp. 1654-1665.

223:
[1] J. Cong, "Minimum-cost bounded-skew clock routing," Proceedings of
ISCAS'95 - International Symposium on Circuits and Systems, vol. 2775,
pp. 215-218.
[2] J.P. Fishburn, "Clock Skew Optimization," Theory and Practice,
vol. 39, 1990, pp. 945-951.
[3] a. Farrahi, a. Srivastava, G. Tellez, and M. Sarrafzadeh,
"Activity-driven clock design," IEEE Transactions on Computer-Aided
Design of Integrated Circuits and Systems, vol. 20, 2001, pp. 705-714.