Clock trees, which deliver the clock signal to every clock sink in the whole system, are one of the most active components on a chip which makes them one of the most dominant sources of noise. While many clock polarity assignment (PA) techniques were proposed to mitigate the clock noise, no attention has been paid to the PA under useful skew constraints. In this work, we show that the clock PA problem under useful skew constraints is intractable and propose a comprehensive and scalable clique search based algorithm to solve the problem effectively. In addition, we demonstrate the applicability of our solution by effectively extending it for PA under delay variation environment. Through experiments with ISPD'10 benchmark circuits, it is shown that our proposed clock PA algorithm is able to reduce the peak noise by 10.9% further over that of the conventional global skew bound constrained PA.

The clock buffer polarity assignment is one of the effective design schemes to mitigate the power/ground noise caused by the clock signal propagation in high-speed digital systems. This paper overcomes a set of fundamental limitations of the conventional clock buffer polarity assignment methods, which are: 1) the unawareness of the signal delay (i.e., arrival time) differences to the leaf clock buffering elements; 2) the ignorance of the effect of the current fluctuation of nonleaf clock buffering elements on the total peak current waveform; and 3) the inability of supporting low-power digital designs with multiple (dynamically operating) power modes. Clearly, not addressing 1 and 2 in the polarity assignment may cause a severe inaccuracy on the peak current estimation, which results in unnecessarily high peak current. Moreover, without tackling 3, designs may suffer from clock skew violation in some of the power modes, affecting circuit speed or reliability. To overcome the limitations, we propose a completely new fine-grained approach to the clock buffer polarity assignment combined with buffer sizing, formulating the problem into a multiobjective shortest path problem and solving it effectively for designs with a single power mode, while exploiting the flexibility of our multiobjective shortest path formulation for designs with multiple power modes. Through experiments using benchmark circuits, it is shown that the proposed approach is able to produce designs with 17% lower peak current and 20% lower power noise on average, compared with the results produced by the best ever known method.

Meeting clock skew constraint is one of the most important tasks in the synthesis of clock trees. Moreover, the problem becomes much hard to tackle as the delay of clock signals varies dynamically during execution. Recently, it is shown that adjustable delay buffer (ADB) whose delay can be adjusted dynamically can solve the clock skew variation problem effectively. However, inserting ADBs requires non-negligible area and control overhead. Thus, all previous works have invariably aimed at minimizing the number of ADBs to be inserted, particularly under the environment of multiple power modes in which the operating voltage applied to some modules varies as the power mode changes. In this work, unlike the previous works which have solved the ADB minimization problem heuristically or locally optimally, we propose an elegant and easily adoptable solution to overcome the limitation of the previous works. Precisely, we propose an O(n log n) time (bottom-up traversal) algorithm that (1) optimally solves the problem of minimizing the number of ADBs to be inserted with continuous delay of ADBs and (2) enables solving the ADB insertion problem with discrete delay of ADBs to be greatly simple and predictable. In addition, we propose (3) a systematic solution to an important extension to the problem of buffer sizing combined with the ADB insertion to further reduce the ADBs to be used.

Satisfying a clock skew constraint is one of the most important tasks in clock tree synthesis. Moreover, the task becomes much harder to solve when the clock tree is designed in a multiple power mode environment, in which the voltage applied to some design module varies as the power mode changes. Recently, it has been shown that an adjustable delay buffer (ADB), whose delay can be tuned dynamically, can be used to solve the clock skew problem effectively under multiple power modes. However, due to the area or control overhead by ADBs, it is very important to minimize the number of ADBs to be allocated. This paper provides a complete solution to the problem of clock skew optimization using ADBs under multiple power modes. We propose a linear-time algorithm that simultaneously solves the problems of computing: 1) the minimum (optimal) number of ADBs to be used; 2) the location where each ADB is to be placed; and 3) the delay value of each ADB to be assigned to each power mode. Experimental results show that, in comparison with the previous work, which iteratively performs the ADB allocation, placement, and value assignment, our integrated algorithm produces consistently better designs for all tested benchmarks; it reduces the numbers of ADBs by 9.27% on average under the skew bound of 30-50 ps, even with shorter clock latencies compared to that of previous algorithm of ADB allocation, placement, and delay assignment. To make it practically feasible, we also propose a new ADB design technique and systematic algorithmic solutions to address the problems of discrete delay values, slew rate variation, nonzero initial ADB delay, and a possible exploration of ADB resizing.

The clock buffer polarity assignment is one of the effective design schemes to mitigate the power/ground noise caused by the clock signal propagation. This work overcomes two fundamental limitations of the conventional clock buffer polarity assignment methods, which are (1) the unawareness of the signal delay (i.e., arrival time) differences to the leaf buffering elements and (2) the ignorance of the effect of the current fluctuation of non-leaf buffering elements on the total peak current waveform. Clearly, not addressing (1) and (2) in polarity assignment may cause a severe inaccuracy on the peak current estimation, which results in unnecessarily high peak current. To overcome the limitations, we propose a completely new fine-grained approach to the clock buffer polarity assignment combined with buffer sizing, formulating the problem into a multi-objective shortest path problem and solving it effectively. The experimental results show that the proposed method is able to produce designs with 17% lower peak current and 20% lower power noise on average compared the results produced by the best ever known method.

In synchronous systems, clock tree causes high peak current at clock edges, increasing power/ground noise significantly, if the clock tree is not carefully designed. This paper addresses the problem of minimizing power/ground noise in the clock tree synthesis. Contrary to the previous approaches which only make use of assigning polarities to clock buffers to reduce power/ground noise, our approach solves a new problem of simultaneous consideration of assigning polarities to clock buffers and determining buffer sizes to fully exploit the effects of buffer sizing together with polarity assignment on the minimization of power/ground noise while satisfying the clock skew constraint. Specifically, the contributions of this paper are: 1) precisely estimating peak currents by clock buffers and reflecting them on the power/ground noise minimization; 2) proposing a pseudo-polynomial time optimal algorithm based on dynamic programming for solving the integrated problem, together with the proof of intractability of the problem; 3) devising a systematic design flow framework for reducing the power/ground noise over the entire chip; and 4) considering the effect of thermal variation on the clock skew bound and the noise minimization.