Search

There are striking differences between constructing clock trees based on dynamic implied skew constraints and based on static arrival time constraints. Dynamic implied skew constraints allow the full timing margins to be utilized, but the constraints are required to be updated (with high time complexity). In contrast, static arrival time constraints are decoupled and are not required to be updated. Therefore, the constraints can be obtained in constant time, which facilitates the exploration of various tree topologies. On the other hand, arrival time constraints do not allow the full timing margins to be utilized. Consequently, there is a trade-off between topology exploration and timing margin utilization. In this paper, the advantages of static arrival time constraints are leveraged to construct clock trees with useful skew while exploring various tree topologies. Moreover, the constraints are specified and respecified throughout the synthesis process reduce the cost of the constructed clock trees. It is experimentally demonstrated that the proposed approach results in clock trees with 16% lower average capacitive cost compared with clock trees constructed based on dynamic implied skew constraints.

Clock trees must be constructed to function even under the influence of on-chip variations (OCV). Bounding the latency of a clock tree, i.e., the maximum delay from the tree root to any sequential element, is important because the latency correlates with the maximum magnitude of the skews caused by OCV. In this paper, a latency constraint graph (LCG) that captures the latencies of a set of subtrees and the skew constraints between the subtrees is introduced. The minimum latency of a clock tree that can be constructed from the corresponding subtrees is equal to the (negative of the) length of a shortest path in the LCG, which can be computed in $O(VE)$. Based on the LCG, we propose a framework that consists of a latency-aware clock tree synthesis (CTS) phase and a clock tree optimization (CTO) phase to construct latency-bounded clock trees. When applied to a set of synthesized circuits, the framework is capable of constructing latency-bounded clock trees that have higher yield compared to clock trees constructed in previous studies.

The clock networks of modern circuits must be able to operate in multiple corners and multiple modes (MCMM). Earlier studies on clock network synthesis for MCMM designs focus on the legalization of an initial clock network that has timing violations in different corners or modes. We propose a mode reconfigurable clock tree (MRCT) that is based on a correct-by-construction approach. An MRCT consists of multiple clock trees. Depending on the active mode, the MRCT is reconfigured such that one of the clock trees is activated to deliver the clock signal. To limit the overhead, the bottom part of the network (closer to the clock sinks) is shared among all of the clock trees, and only the top part of the network (closer to the clock source) is mode reconfigurable. The reconfiguration is realized using or-gates and a single one-input-multiple-output demultiplexer. The MRCT is constructed in a bottom-up fashion by iteratively merging subtrees to form larger subtrees. When two sub-trees cannot be merged because of mode-incompatible constraints, an or-gate is inserted to separate the incompatible modes. Corner-incompatible constraints are resolved by reducing safety margins of appropriate skew constraints. The experimental results show that for a set of synthesized MCMM circuits with 715 to 13, 216 sequential elements, the proposed approach can achieve high yield.

The construction of clock trees for modern designs is challenging because the clock trees need to be constructed with adequate safety margins such that the skew constraints are satisfied even under variations. The amount of safety margin required in a skew constraint is dependent on the distance of the corresponding sequential elements in the tree topology. In certain cases, the amount of safety margin that can be inserted may be limited. Consequently, the corresponding sequential elements should be placed close in the topology, i.e., the point of divergence to these elements is low in the clock tree, in order to reduce the influence of variations. By using safety margins and lowering the point of divergence, we present a framework for the construction of useful skew trees with large safety margins inserted in the skew constraints. The framework, called UST-LSM, first identifies tight skew constraints by the detection of negative cycles in a weighted skew constraint graph. Next, the corresponding sequential elements of these skew constraints are clustered early in tree topology. Compared to earlier studies, we can allow larger safety margins in skew constraints spanning between sequential elements within a subtree. This translates into an improvement of yield from 46.8% to 98.8% on a synthesized benchmark with 7,674 sequential elements and 63,440 skew constraints.

To obtain high yield for 3D ICs, random open defects, process variations, and thermal induced stress are key issues that must be addressed when synthesizing 3D clock networks. Current research on 3D clock synthesis often focuses on the construction and optimization of a 3D clock tree topology. Moreover, extra circuitry has been proposed to enable pre-bond testing and substitution of through silicon vias (TSVs) with random open defects. However, tree structures inherently have limited robustness to variations and may suffer failures arising from defects and/or process variations. To counter such problems, we propose to use TSVs to add redundancy in a 3D clock network. The proposed 3D network would have a complete 2D clock network on each die, facilitating pre-bond testing. Also, cross links would be inserted within each die using wires and across dies using TSVs to improve timing robustness within each die and across dies, respectively. Moreover, clock buffers are placed outside of zones that have high TSV-induced stress that could influence carrier mobility. Experimental results show that the proposed 3D clock networks have no failures due to random open defects, and on the average have 53% lower skew compared to 3D tree structures.

Wire sizing can be used to reduce the delays of critical nets. However, because of the forbidden pitch issue in sub-20nm designs, wide wires may no longer be an attractive solution because of the restrictive wire spacing requirement from advanced lithography. In this work, we investigate the suitability of the parallel wiring technique, in which multiple parallel wires are used to route the same net, as an alternative to routing a net using a single wide wire. In particular, we study the trade offs between parasitics, timing, power, and routing resources. Our study reveals that wire sizing using both parallel wires and wide wires can be advantageous. Moreover, if high layout densities are required, parallel wiring can be a viable approach in solving timing problems for sub-20nm designs.

By modifying an existing Mixed Integer Programming (MIP) model for optimizing the placement of cells in sliding windows, we develop a detailed placer for large-scale mixed-size circuits. To make it possible to optimize the placement of larger sliding windows in reasonable time, we reduce the number of integer variables in the modified MIP model such that when compared with the original complete MIP model, the solution time is shortened greatly while the solution quality does not degrade much. Experimental results on DAC12 benchmark circuits show that our detailed placer manages to further reduce half-perimeter wirelength (HPWL) of the placement results generated by many other existing detailed placement techniques. Moreover, by making use of a commercial router, we also evaluate the routability of the placement results before and after the application of our detailed placer. Both the routed wirelength and the number of vias in routing solutions are reduced, while the number of design rule violations does not change much for most circuits, implying the routablity of placement results are not perturbed.

Routability has become a critical issue in VLSI design flow. To avoid producing an unroutable design, many placers [4-7] invoke global routers to get a congestion map and then move cells to reduce congestion based on this map. However, as cells move, the accuracy of the congestion map degrades, thereby affecting the effectiveness of the placer in minimizing congestions. Moreover, most global routers [8-13] ignore local congestion. If placers are guided by these routers, it may produce hard-to-route placement solutions in terms of detailed routing. This work develops a routability optimizer, called Ropt, to reduce both global and local routing congestion levels of a given placement. Based on a local-routability-aware routing model, Ropt builds a global routing instance to obtain global and local congestion information for guiding global re-placement. In addition, this work presents a new legalization scheme to preserve the global routing instance after legalization. Finally, local detailed placement further minimizes the local congestion and wirelength. For the evaluation of Ropt, we use an academic global router and a commercial router to obtain both global and detailed routing results, respectively. Experimental results reveal that Ropt can improve the routing quality (in terms of congestion, wirelength, and violation) and routing runtime of a given placement solution.

Process and environmental variations affect the reliability of clock networks. By synthesizing non-tree structures, the robustness of clock networks can be improved at the expense of higher capacitance. A cheap way of converting a tree structure to a non-tree structure is to insert cross links. Unfortunately, the robustness seems to improve only when the links are sufficiently short. Other non-tree structures such as meshes and multilevel fusion trees improve the robustness more effectively, but with much higher cost. In this work, we develop a new non-tree topology by merging a sub-clock tree with all other sub-clock trees that contain sequential elements that require strict synchronization. Results show that when compared with the state-of-the-art solutions, clock networks constructed with the proposed structure have similar capacitance but notable improved robustness. moreover, the clock networks can satisfy tight skew constraints even when simulated under a more stringent variations model, with 22% lower capacitance when compared to solutions in earlier studies.

Routability is a critical issue in VLSI design flow. To address this issue, the routability-driven placement contests [1, 2] held at ISPD11 and DAC12 promote the development of routability-driven placers such as those in [4-6]. ISPD11 and DAC12 contests adopt metrics that are based on global routing solutions to evaluate the routability of placement solutions. However, such global-routing-based metrics typically ignore local congestion, and they cannot evaluate the actual routability effectively. In this work, we develop a translator that allows us to feed the placement solutions of mPL [3], NTUplace [4], Ripple [5], and SimPLR [6] into a commercial router for detailed routing. We then analyze the detailed routing result of each placement solution to better understand the issues that may cause routing violations. Moreover, we examine the suitability of using the ISPD11 and DAC12 metrics in predicting routability. Our findings indicated that the metrics might not reliably predict actual routability, in terms of the number of (detailed) routing violations.

Considering routability issue in the early stages of VLSI design flow can avoid generating an unroutable design. Several recent routablity-driven placers [8--11] adopt a built-in global router to estimate routing congestion. While the routability of the placement solution improves, the performance of these placers degrades. Many of these built-in global router and state-of-the-art academic global routers use maze routing to seek a detoured path. Although very effective, maze routing is relatively slower than other routing algorithms, such as pattern routing and monotonic routing algorithms. This work presents two efficient routing algorithms, called unilateral monotonic routing and hybrid unilateral monotonic routing, to replace maze routing and to realize a highly fast maze-free global router that is suited to act as a built-in routing congestion estimator for placers. Experimental results indicate that RCE achieves similar routing quality when compared with [20], as well as an over 20-fold runtime speedup in large benchmarks.

Existing detailed placement optimization methods typically involve the use of enumeration to determine the optimal location of a small number of cells. We propose two Mixed Integer Programming (MIP) models that can optimize the detailed placement of more cells efficiently. Compared with existing models, the first proposed model has fewer integer variables. The second proposed model, derived based on Dantzig-Wolfe decomposition principle, is with tighter bounds during its solution. Experimental results show that both models are capable of optimizing in reasonable time the detailed placement of much larger problem instances than existing models. Experiments on large-scale real benchmark circuits also show that detailed placer based on advanced MIP models can effectively reduce half-perimeter wirelengh (HPWL), as well as routed wirelength and vertical vias, of the original placement results generated by enumeration approach.

We propose a global placement algorithm that employs size scaling of circuit components to provide continuity during placement. In the context of mixed-size placement, size scaling is utilized to handle significant variations among the sizes of the components, thereby avoiding additional complexity that is often associated with multiple levels of smoothing. By using the optimal region approach to first determine an initial placement, the size scaling approach allows the global placement algorithm to converge to better placement solutions.

The International Symposium on Physical Design (ISPD) 2010 contest presents the challenge of synthesizing clock distribution networks that are tolerant to severe power-supply and wire-width variations. In particular, a robust clock network should satisfy the local clock skew (LCS) constraint, i.e., the clock skew between any pair of sequential elements that are closer than a user-specified distance is below a user-specified limit, even in the presence of variations. In this paper, we identify a few factors that help in tolerating these variations in clock trees. Our proposed clock tree router uses a two-stage flow to construct low-power clock trees for which the LCS constraints are met. Our clock tree router has been tested on ISPD'10 contest benchmark circuits. Extensive Monte-Carlo simulations showed that low power clock tree solutions could effectively handle variations, even when we imposed more stringent conditions in the experimental setup.

Cross links have been used to reduce skew variations in clock trees. In earlier studies cross links are inserted between the sinks of DC-connected trees. In this paper, we propose a link insertion scheme that inserts cross links between internal nodes of a clock tree. In addition to reducing the skew variability, the proposed approach also reduces the total cross link length. Our work also improves the correlation of sink delays for those sinks within a subtree that have similar path lengths to the cross link. Monte-Carlo (MC) simulations on the ISPD-2010 benchmarks showed that our work could handle variations effectively. In addition to meeting all the design constraints, the solutions produced by our approach have on the average 32% lower capacitance than the least capacitance obtained by the top three teams in the ISPD-2010 design contest [1].

This paper studies the effects of clustering as a pre-processing step and routability estimation in the placement flow. The study shows that when clustering and routability estimation are considered, the placer effectively improves the routed wirelength for the circuits of IBM-PLACE 2.0 standard-cell Benchmark Suite [1] and results in the best average routed wirelength when compared against state-of-the-art academic placers.

State-of-the-art integral-equation-based solvers rely on techniques that can perform a matrix-vector multiplication in O(N) complexity. In this work, a fast inverse of linear complexity was developed to solve a dense system of linear equations directly for the capacitance extraction of any arbitrary shaped 3D structure. The proposed direct solver has demonstrated clear advantages over state-of-the-art solvers such as FastCap and HiCap; with fast CPU time and modest memory consumption, and without sacrificing accuracy. It successfully inverts a dense matrix that involves more than one million unknowns associated with a large-scale on-chip 3D interconnect embedded in inhomogeneous materials. Moreover, we have successfully applied the proposed solver to full-wave extraction.

Redundant via insertion is highly recommended for improving chip yield and reliability. In this paper, we study the problem of double-cut via insertion (DVI) in a post-routing stage, where a single via can have at most one redundant via inserted next to it and the goal is to insert as many redundant vias as possible. The DVI problem can be naturally formulated as a zero-one integer linear program (0-1 ILP). Our main contributions are acceleration methods for reducing the problem size and the number of constraints. Moreover, we extend the 0-1 ILP formulation to handle via density constraints. Experimental results show that our 0-1 ILP is very efficient in computing optimal DVI solution, with up to 35.3 times speedup over existing heuristic algorithms

Negative bias temperature instability (NBTI) has become a dominant reliability concern for nanoscale PMOS transistors. In this paper, we propose variable-latency adder (VL-adder) technique for NBTI tolerance. By detecting the circuit failure on-the-fly, the proposed VL-adder can automatically shift data capturing clock edge to tolerate NBTI-induced delay degradation on critical timing paths. VL-adder operates with a fixed supply voltage and clock period, avoiding the high design and manufacturing costs incurred by existing NBTI-tolerant techniques. Compared to other related lower-power adder designs, VL-adder technique always provides better energy efficiency through the whole chip lifetime with very limited performance degradation (4.6% or less).

Logic duplication, a commonly used synthesis technique to remove trapped inverters in reconvergent paths of Domino circuits, incurs high area and power penalties. In this paper, we propose a synthesis scheme to reduce the duplication cost by allowing inverters in Domino logic under certain timing constraints. In order to guarantee the robustness of such Domino circuits, we perform the reduction of logic duplication at the physical level. Experimental results show significant reduction in duplication cost, which translates into significant improvements in area, power, and/or delay.

This paper presents an efficient t o-stage project-and-balance scheme for passivity-preserving model order reduction. Orthogonal dominant eigenspace projection is implemented by integrating the Smith method and Krylov subspace iteration. It is followed by stochastic balanced truncation herein a novel method, based on the complete separation of stable and unstable invariant subspaces of a Hamiltonian matrix, is used for solving two dual algebraic Riccati equations at the cost of essentially one. A fast-converging quadruple-shift bulge-chasing SR algorithm is also introduced for this purpose. Numerical examples confirm the quality of the reduced-order models over those from conventional schemes.

Many current designs contain a large number of standard cells intermixed with larger macro blocks. The range of size in these "mixed block" designs complicates the placement process considerably; traditional methods produce results that are far from satisfactory.In this paper we extend the traditional recursive bisection standard cell placement tool Feng Shui to directly consider mixed block designs. On a set of recent benchmarks, the new version obtains placements with wire lengths substantially lower than other current tools. Compared to Feng Shui 2.4, the placements of a Capo-based approach have 29% higher wire lengths, while the placements of mPG are 26% higher. Run times of our tool are also lower, and the general approach is scalable.

The determination of the set (or window) of segments that are inductively coupled to a significant degree with a given segment plays a fundamental role in window-based techniques for the extraction of the susceptance of interconnect structures. We present a measure that quantifies the degree of coupling between segments in a window, thereby paving the way for an adaptive scheme for determining the coupling window associated with each segment. This measure has the properties that: (i) it is well-correlated with the simulation error that is inherent in window-based susceptance extraction techniques, and (ii) it can be computed efficiently using incremental and computation reuse techniques.

We investigate the problem of decoupling capacitance allocation for power supply noise suppression at floorplan level. Decoupling capacitance budgets for the circuit modules are calculated based on the power supply noise estimates. A linear programming technique is used to maximize the allocation of the existing white space in the floorplan for the placement of decoupling capacitors. An incremental heuristic is proposed to insert more white space into the existing floorplan to meet the remaining demand required for decoupling capacitance fabrication. Experimental results on six MCNC benchmark circuits show that the white space allocated for decoupling capacitance is about 6%-12% of the chip area for the 0.25mm technology, and the power supply noise can be kept below 10%Vdd.

In this paper, we present a repeater block planning algorithm for interconnect-centric floorplanning. We introduce the concept of independent feasible regions for repeaters and derive an analytical formula for their computation. We develop a routability-driven repeater clustering algorithm to perform repeater block planning based on iterative deletion. The goal is to obtain a high-quality solution for the repeater block locations so that performance-driven interconnect synthesis at the routing stage can be carried out with ease while minimizing the chip area. Experimental results show that our method increases the percentage of all global nets that meet their target delays from 67.5% to 85%. Moreover, our approach minimizes the expected routing congestion, making it easier for performance-driven routers to synthesize global nets that require the insertion of repeaters to meet timing constraints.