We describe a placement-level decoupling capacitance (decap) insertion technique whose objective is to reduce power noise, taking into account circuit timing. Our approach consists of prediction and correction steps. Before placement, we estimate the power noise of each cell considering switching frequency of cells that, after placement, will most likely be in the neighborhood. If a frequently switching cell has neighbors that switch infrequently, it is unlikely that this cell will suffer from a power-noise problem. Based on the cell power-noise estimation, we add decap padding to each cell. Then, we invoke a standard cell placement tool and perform power grid analysis. We eliminate the power grid noise by gate sizing. Our technique can allocate decaps to improve power noise, power consumption, and timing. We propose two gate-sizing algorithms. The first one uses a sequence of linear programs (SLP) formulation, and the second one uses a budgeting-based heuristic algorithm. The SLP algorithm can produce better power-noise results than the heuristic, at the expense of runtime. Experimental results show that our techniques can effectively reduce power noise and still meet timing constraints

In this paper, we propose a skew-programmable clock-routing architecture. The skews can be adjusted using programmable delay elements (PDEs) which we insert into the clock trees. We develop efficient, shortest-path-based algorithms for programming PDEs to optimize timing. Unlike previous methods for FPGA skew optimization which require large power and routing penalty, our method can achieve large timing improvement with small overhead. Typically, if timing requirements are tight, placers make efforts to satisfy them, often at a cost of compromising routability, total wire length, and power. In this work, we propose novel clock-skew-aware placement algorithms which allow us to relax the timing constraints during placement. Timing can be later optimized as a post process. Even though we demonstrate the efficiency of our approach using FPGAs, the new skew optimization method and the new placement algorithm are quite general and can be applied to any general, topology-constrained skew optimization problem. Experimental results indicate that using the new clock-architecture we can obtain a 22% timing improvement for post-layout skew optimization and an additional 21% improvement from our skew-aware placement algorithm. In one fabric, the cost of added logic is 2.19% as measured by dynamic power dissipation, and 0.85% in terms of area overhead.

Mesh architectures are used for distributing critical global signals on a chip such as clock and power/ground. The inherent redundancy created by loops present in the mesh smooths out undesirable variations between signal nodes spatially distributed over the chip. However, one outstanding problem with mesh architectures is the difficulty in analyzing them with sufficient accuracy. In this paper, we present a new sliding window-based scheme to analyze the latency in clock meshes. We show that for small meshes, our scheme comes within 1% of the SPICE simulation of the complete mesh with respect to clock latency. Our scheme is ideally suited for distributed- or grid-computing. We show large design instances where SPICE could not finish, whereas our scheme could complete the analysis in less than 2 hours.

In this paper, we propose a timing-aware power-noise reduction technique. Our approach consists of prediction and correction steps. Before placement, we estimate the power noise of each cell considering switching frequency of cells which, after placement, will most likely be in the neighborhood. If a frequently switching cell has neighbors which switch infrequently, it is unlikely that this cell will suffer from a power noise problem. Based on the cell power noise estimation, we add decap padding to each cell. Then we invoke a standard cell placement tool and perform power grid analysis. We eliminate the power grid noise by gate sizing. Our technique can reallocate decaps to improve power noise, power consumption, and timing. The gate sizing is based on the sequence of linear programs (SLP) formulation, and it can be solved efficiently. Experimental results show that our techniques can effectively reduce power noise and meet timing constraints.

Delay budgeting is a process of determining upper bounds for net delays to guide timing-driven placement. The existing approaches deal de facto only with combinational circuits. However, incorporating retiming into delay budgeting introduces more freedom to optimize sequential circuits. In this paper, we propose an approach for budgeting sequential circuits. We propose a new linear programming formulation for timing-aware sequential budgeting, which guarantees that the clock period constraints are met. We demonstrate the usefulness of our approach in the context of field-programmable gate arrays placement flow. We have performed two experiments. The first experiment compares sequential budgeting with traditional budgeting and retiming. The results show that the new placement flow reduces budget violations by 16% and improves timing by 9%. In the second experiment, we demonstrate methods of interconnect length prediction that are useful to estimate delay and to decide net weighting in sequential budgeting. We compare net delay predictions using traditional delay budgeting, the Donath's method, and mutual contraction. The results from this experiment show that sequential budgeting, using the new net weighting and predicted delays, can improve circuit speeds on average by 12.29%, compared to traditional timing-driven placement. The new net weighting method also performs better than a uniform weighting method.

Delay budgeting is a process of determining upper bounds for net delays to guide timing-driven placement. The existing approaches deal de facto only with combinational circuits. However, incorporating retiming into delay budgeting introduces more freedom to optimize sequential circuits. In this paper, we propose an approach for budgeting sequential circuits. We propose a new algorithm, T-SBGT, which uses an LP formulation to solve the budgeting problem in sequential circuits and guarantees that the clock period constraints are met. We then utilize the skew-retiming equivalence relation [9] and retime the circuit. We demonstrate usefulness of our approach in the context of FPGA placement flow. An effective algorithm to minimize Flip-Flops (FFs) number after placement using the net slack is also proposed. The results show the placement flow improves timing by 9%, and reduces budget violations by 16% compared to the traditional flow. The post-placement FF reduction algorithm decreases the FF count by 19% on average.