This work presents a method for global routing (GR) to minimize interconnect power. We consider design with multi-supply voltage, where level converters are added to nets that connect driver cells to sink cells of higher supply voltage. The level converters are modeled as additional terminals during GR. Given an initial GR solution obtained with the objective of minimizing wirelength, we propose a GR method to detour nets to further save the interconnect power. When detouring routes via this procedure, overflow is not increased, and the increase in wirelength is bounded. The power saving opportunities include: 1) reducing the area capacitance of the routes by detouring from the higher metal layers to the lower ones, 2) reducing the coupling capacitance between adjacent routes by distributing the congestion, and 3) considering different power-weights for each segment of a routed net with level converters (to capture its corresponding supply voltage and activity factor). We present a mathematical formulation to capture these power saving opportunities and solve it using integer programming techniques. In our simulations, we show considerable saving in an interconnect power metric for GR, without any wirelength degradation.

This paper introduces GRIP, a global routing technique via integer programming. GRIP optimizes wirelength and via cost directly without going through a traditional layer assignment phase. Candidate routes spanning all the metal layers are generated using a linear programming pricing phase that formally accounts for the impact of existing candidate routes when generating new ones. To make an integer-programming-based approach applicable for today's large-scale global routing instances, the original problem is decomposed into smaller subproblems corresponding to rectangular subregions on the chip together with their net assignments. Route fragments of nets that fall in adjacent subproblems are connected in a flexible manner. In case of overflow, GRIP applies a second-phase optimization that explicitly minimizes overflow. By using integer programming in an effective manner, GRIP obtains high-quality solutions. Specifically, for the ISPD 2007 and 2008 benchmarks, GRIP obtains an average improvement in wirelength and via cost of 9.23% and 5.24%, respectively, when compared to the best result in the open literature.

We propose a parallel global routing algorithm that concurrently processes routing subproblems corresponding to rectangular subregions covering the chip area. The algorithm uses at it core an existing integer programming (IP) formulation---both for routing each subproblem and for connecting them. Concurrent processing of the routing subproblems is desirable for effective parallelization. However, achieving no (or low) overflow global routing solutions without strong, coordinated algorithmic control is difficult. Our algorithm addresses this challenge via a patching phase that uses IP to connect partial routing solutions. Patching provides feedback to each routing subproblem in order to avoid overflow, later when attempting to connect them. The end result is a flexible and highly scalable distributed algorithm for global routing. The method is able to accept as input target runtimes for its various phases and produce high-quality solution within these limits. Computational results show that for a target runtime of 75 minutes, running on a computational grid of few hundred CPUs with 2GB memory, the algorithm generates higher quality solutions than competing methods in the open literature.

This paper proposes a framework for (signal) interconnect power optimization at the global routing stage. In a typical design flow, the primary objective of global routing is minimization of wirelength and via consumption. Our framework takes a global routing solution that is optimized for this objective, and quickly generates a new solution that is optimized for signal power, with only a small, controlled degradation in wirelength. Our model of signal power includes layer-dependent fringe and area capacitances of the routes, and their spacing. Our framework is fast compared to the existing global routing procedures, thereby not causing much overhead and fitting well in the design flow to optimize signal power after wirelength minimization. The framework is based on Pareto-algebraic operations and generates multiple global routing solutions to provide a tradeoff between power and wirelength, thereby allowing the user to optimize power with a controlled degradation in wirelength. The generated solution remains free of overflow in routing resource usage. We experiment with large benchmarks from the ISPD 2008 suite and a 45nm technology model. We show on average 19.9% dynamic power saving with at most 3% wirelength degradation using the existing wirelength optimized solutions from the open literature.

We propose GRIP, a scalable global routing technique via Integer Programming (IP). GRIP optimizes wirelength and via cost without going through a layer assignment phase. GRIP selects the route for each net from a set of candidate routes that are generated based on an estimate of congestion generated by a linear programming pricing phase. To achieve scalability, the original IP is decomposed into smaller ones corresponding to balanced rectangular subregions on the chip. We introduce the concept of a floating terminal for a net, which allows flexibility to route long nets going through multiple subregions. We also use the IP to plan the routing of long nets, detouring them from congested subregions. For ISPD 2007 benchmarks, we obtain 3.9% and 11.3% average improvement in wirelength and via cost for the 2D and 3D versions respectively, compared to the best results reported in the open literature.

We propose Parallel and Randomized cell Sizing (PaRS), a parallel and randomized algorithm and tool to solve the discrete gate sizing (cell sizing) problem on a grid. PaRS is formulated based on an optimization framework known as nested partitions which we adopt for the first time in the computer-aided design area. PaRS uses parallelism from a novel perspective to better identify the optimization direction. It achieves near-optimal solutions (under 1%) for minimizing the total power subject to meeting a delay constraint. The embarrassingly parallel nature of PaRS makes it highly scalable. We show small algorithm runtimes, in at most minutes for large benchmarks featuring over 47 000 cells. We make comparison with the optimal solution which we are able to generate using customized and parallel branch-and-bound implementation on a grid. Consequently, we are able to generate the optimal solution within hours. While the optimal algorithm uses up to 200 central processing units (CPUs) on our grid, PaRS achieves significant speedups and near-optimal solutions using only 20 CPUs. We also study the impact of varying number of CPUs in PaRS. Finally, we discuss a grid-based implementation using the ldquomaster-workerrdquo framework.

This paper presents an adjustment-based modeling framework for timing analysis under variability. Instead of building a complex model (such as polynomial one) directly between the circuit timing and parameter variability, we propose to build a model that adjusts an approximate variation-aware timing into an accurate one. The idea is that it is easier to build a model that adjusts an approximate estimate into an accurate one. In addition, it is more efficient to obtain an approximate circuit timing model. The combination of these two observations makes the use of an adjustment-based model a better choice for statistical static timing analysis with high dimension of parameter variability (e.g., at sign-off stage). It can also be used at the postsilicon stage to predict the circuit timing from a smaller subcircuit. To build the adjustment model, we use a simulation-driven approach based on Gaussian Process. Combined with the intelligent sampling, we show that an adjustment-based model can more effectively capture the nonlinearity of the circuit timing with respect to parameter variability compared to polynomial models. Simulation results show that with 42 independent device and interconnect parameter variations, our proposed adjustment-based model obtained using 200 circuit timing samples can achieve much higher accuracy than quadratic model obtained using 2000 samples.

We propose PaRS, a parallel and randomized tool which solves the discrete gate sizing (cell sizing) problem on a grid. PaRS is formulated based on an optimization framework known as Nested Partitions which uses parallelism and randomization from a novel perspective to better identify the optimization direction. It achieves near-optimal solutions for minimizing total power and area subject to meeting a delay constraint. The embarrassingly-parallel nature of PaRS makes it highly efficient. We show small algorithm run-times, in at most minutes for circuits with over 47,000 cells. We make comparison with the optimal solution generated by a custom and parallel branch-and-bound algorithm. Consequently, we are able to generate the optimal solution within hours. While the optimal algorithm uses up to 200 nodes in our grid, PaRS achieves its speedups and near-optimal solutions using only 20 nodes.

This paper presents an adjustment-based modeling framework for statistical static timing analysis (SSTA) when the dimension of parameter variability is high. Instead of building a complex model between the circuit timing and parameter variability, we build a model which adjusts an approximate variation-aware timing into an accurate one. The intuition is that it is simpler to build a model which adjusts an approximate estimate into an accurate one. It is also more efficient to obtain an approximate circuit timing model. The combination of these two observations makes the use of an adjustment-based model a good choice for SSTA with high dimension of parameter variability. To build the adjustment model, we use a simulation-based approach, which is based on Gaussian Process. Combined with intelligent sampling, we show that an adjustment-based model can more effectively capture the nonlinearity of the circuit timing with respect to parameter variability compared to polynomial modeling. We also show that with only 200 samples of the circuit timing and 42 independent parameter variations, adjustment-based modeling obtains higher accuracy than direct SSTA using quadratic modeling.

We present SynECO, a framework to achieve predictable timing improvement via incremental resynthesis and replacement. We target timing-critical paths postplacement and resynthesize and replace promising gates. We show since the wire delays are the non-negligible contributors to a critical-path delay, it is crucial to accurately estimate them to make a predictable synthesis modification. For this purpose, we incorporate an accurate timing analysis tool which uses fast detail routing for wire delay estimation. This allows generating timing estimates that correlate much better with post-routing values compared to Steiner-tree-based estimate of wiring tree and using D2M delay model. Detail routing information allows incorporation of factors such as crosstalk, metal layer assignment and via delays which are crucial for accurate analysis. For fast synthesis, we constrain our logical modifications to be from the physical neighborhood of target gates on the critical paths. Our synthesis framework is completely integrated with the Cadence Encounter tools for physical design.

We propose a parallel and randomized algorithm to solve the problem of discrete dual-Vt assignment combined with continuous gate sizing which is an important low power design technique in high performance domains. This combinatorial optimization problem is particularly difficult to solve on large-sized circuits. We first introduce a hybrid algorithm which combines the existing heuristics and convex formulations for this problem to achieve a better tradeoff between the runtime of the algorithm and the quality of generated solution. We then extend our algorithm to include parallelism and randomization. We introduce a unique utilization of parallelism to better identify the optimization direction. Consequently, we can reduce both the number of iterations in optimization as well as improve the quality of solution. We further use random sampling to avoid being trapped in local minima and to focus the optimization effort on the more "promising" regions of the solution space. Our algorithm improves the average power by 37% compared to an approach which is based on solving a continuous convex program and applying discretization. Power improvement is over 50% for larger benchmarks for an implementation on a grid of 9 computers.