Due to the increased power density and lower thermal conductivity, 3D is faced with heat dissipation and temperature problem seriously. Previous researches show that leakage power and delay are both relevant to temperature. The timing-power-temperature dependence will potentially negate the performance improvement of 3D designs. TSV (Through-Silicon-Vias) has been shown as an effective way to help heat removal, but they create routing congestions. Therefore, how to reach the trade-off between temperature, via number and delay is required to be solved. Different from previous works on TSV planning which ignored the effects of leakage power, in this paper, we integrate temperature-leakage-timing dependence into thermal via planning of 3D ICs. A weighted via insertion approach, considering both performance and heat dissipation with resource constraint, is proposed to achieve the best balance among delay, via number and temperature. Experiment results show that, with leakage power and resource constraint considered the temperature and via number required can be quite different, and weighted TSV insertion approach can improve thermal via number, by about 5.6%.

As technology advances, the voltage (IR) drop in the Power/Ground (P/G) network becomes a serious problem in modern IC design. The P/G network co-design with floorplan can improve the power design quality. Different with traditional approaches which analyze P/G network during the floorplanning iterations, in this paper, an efficient pattern selection method is used to provide gradient information for fast signal-integrity estimation. We also propose a novel P/G aware incremental algorithm which can intelligently fix the violations during the floorplanning process. The P/G pin assignment and wire sizing method are adopted during the floorplanning process so that the power routing resource can be minimized with the constraints of IR drop and electron migration (EM) considered. Experimental results based on the MCNC benchmarks show that our design not only significantly speeds up the optimization process, but also optimizes the power routing resource while the quality of the floorplanning is maintained.

With the challenges of growing functionality and scaling chip size, the possible performance improvements should be considered in the earlier IC design stages, which gives more freedom to the later optimization. Potential slack as an effective metric of possible performance improvements is considered in this work which, as far as we known, is the first work that maximizes the potential slack by retiming for synchronous sequential circuit. A simultaneous slack budgeting and incremental retiming algorithm is proposed for maximizing potential slack. The overall slack budget is optimized by relocating the FFs iteratively with the MIS-based slack estimation. Compared with the potential slack of a well-known min-period retiming, our algorithm improves potential slack averagely 19.6% without degrading the circuit performance in reasonable runtime. Furthermore, at the expense of a small amount of timing performance, 0.52% and 2.08%, the potential slack is increased averagely by 19.89% and 28.16% separately, which give a hint of the tradeoff between the timing performance and the slack budget.

Off-chip substrate routing for high-density packages is challenging due to requirements such as high density, lack of vertical detour, non-Manhattan routing, and primarily planar routing. The existing substrate routing algorithms often result in a large number of unrouted nets that have to be routed manually. This article develops an effective yet efficient diffusion-driven method D-Router to reduce congestion. Starting with an initial routing, we develop an effective diffusion-based congestion reduction. We iteratively find a congested window and spread out connections to reduce congestion inside the window by a simulated diffusion process based on the duality between congestion and concentration. The window is released after the congestion is eliminated. Compared with the state-of-the-art substrate routing method that leads to 480 nets unrouted for ten industrial designs with a total of 6415 nets, the D-Router reduces the amount of unrouted nets to 104, a reduction to the 4.6 multiple. In addition, the D-Router obtains a similar reduction on unrouted nets but runs up to 94 times faster when compared with a negotiation-based substrate routing.

Clock gating is one of the most effective techniques to reduce clock tree power. Although it has already been studied considerably, most of the previous works are restricted to either register transfer level (RTL) or clock tree synthesis stage. Clock gating design at RTL is coarse and it pays no attention to the physical information, therefore, it often results in large wirelength overhead. While if clock gating is considered only at clock tree synthesis, the optimization space is largely limited due to the fixing of registers. To fully use the logical and physical information between registers, we propose a new flow for low-power gated clock tree design in this work. It mainly includes three parts: gated clock tree aware register placement, gated clock tree construction, and incremental placement. Compared with the previous works on clock gating, our algorithm reduces the clock tree power with much fewer gating logics, therefore, the overhead to the placement is also reduced.

In this paper, a novel design-for-manufacture-aware detailed routing algorithm that seeks to minimize the thickness range of the chip surface after copper damascene process is proposed. The paper is based on an electroplating (ECP) and chemical mechanical polishing (CMP) model and predictors for final thickness range are abstracted. The proposed detailed routing is implemented in a W-shape multilevel full-chip routing framework using depth first search and branch-and-bound techniques in maze backtracking. Experimental results show that compared to maze routing (MR) (that does not consider CMP), the improvements in the average metal density standard and the average amount of dummy fill are 12.0% and 6.99% respectively. Compared to density-driven maze routing (DMR) that considers only CMP but does not consider ECP, the improvements in the average metal density standard and the average amount of dummy fill are 0.53% and 0.72%, respectively. So, the proposed algorithm can obtain improvement in optimizing CMP while the wire length and vias are not increased clearly and the completion rate is guaranteed. Therefore, the yield of chips is improved.

Thermal issue is a critical challenge in 3D IC design. To eliminate hotspots, physical layouts are always adjusted by shifting or duplicating hot blocks. However, these modifications may degrade the packing area as well as interconnect distribution greatly. In this paper, we propose some novel thermal-aware incremental changes to optimize these multiple objectives including thermal issue in 3D ICs. Furthermore, to avoid random incremental modification, which may be inefficient and need long runtime to converge, here potential gain is modeled for each candidate incremental change. Based on the potential gain, a novel thermal optimization flow to intelligently choose the best incremental operation is presented. We distinguish the thermal-aware incremental changes in three different categories: migrating computation, growing unit and moving hotspot. Mixed integer linear programming (MILP) models are devised according to these different incremental changes. Experimental results show that migrating computation, growing unit and moving hotspot can reduce max on-chip temperature by 7%, 13% and 15% respectively on MCNC/GSRC benchmarks. Still, experimental results also show that the thermal optimization flow can reduce max on-chip temperature by 14% compared to an existing 3D floorplan tool CBA, and achieve better area and total wirelength improvement than individual operations do.

In this paper, we present a novel statistical full-chip leakage power analysis method. The new method can provide a general framework to derive the full-chip leakage current or power in a closed form in terms of the variational parameters, such as the channel length, the gate oxide thickness, etc. It can accommodate various spatial correlations. The new method employs the orthogonal polynomials to represent the variational gate leakages in a closed form first, which is generated by a fast multi-dimensional Gaussian quadrature method. The total leakage currents then are computed by simply summing up the resulting orthogonal polynomials (their coefficients). Unlike many existing approaches, no grid-based partitioning and approximation are required. Instead, the spatial correlations are naturally handled by orthogonal decompositions. The proposed method is very efficient and it becomes linear in the presence of strong spatial correlations. Experimental results show that the proposed method is about 10× faster than the recently proposed method [4] with constant better accuracy.

In this paper, we propose a fast placer for FPGA placement on a new commercial hierarchical FPGA device. The novelty of this research lies in the application of a multilevel V-shape optimization flow including an architecture related cluster process and a constructive placement. The new placer can handle large-scale FPGA placement problem quickly. Experimental results show that the proposed placer can further reduced the wirelength average 28.3% compared with simulated annealing based tool while achieving near 5X speedup in runtime for the five largest MCNC benchmarks.

This paper proposes an efficient decoupling (decaps) capacitance optimization algorithm to reduce the voltage noise of on-chip power grid networks. The new method is based on the efficient charge formulation of the decap allocation problem. But different from the existing work [12], the new method applies the more accurate piecewise polynomial micromodels to estimate the voltage noises during the linear programming process. The resulting method overcomes the over-estimation problem, which plagues the existing method. The proposed method has the best of two worlds: it has the efficiency of the charge-based methods and the accuracy of the sensitivity-based methods. Experimental results demonstrate that the proposed method leads to the decap values similar to that of the sensitivity-based methods, which give the best reported results and are much better than the existing charge-based method, and at the same time, it enjoys the similar efficiency of the charge-based method.

With recent advance of VLSI design, interconnect delay plays dominant role in the chip performance. 3D integration, which stacks multiple device layers, greatly reduces interconnect delay. Buffer insertion, as another approach to reduce wire delay, is still necessary to further optimize interconnects. In this paper, a buffer planning algorithm at floorplanning stage for 3D ICs is proposed. Firstly, we reduce buffer insertion to a dynamic programming path problem. Then we show its potential to handle the 3D buffer insertion problem. At the same time, vertical interlayer vias are also planned. At last, buffer planning is integrated with floorplanning to optimize the packing so that not only area and wire length reach a satisfying value, timing performance is also optimized.

O-chip substrate routing for high density packages is chal-lenging, and the existing substrate routing algorithms often result in a large number of unrouted nets that have to be routed manually. This paper develops an eective yet e-cient diusion-driven method D-Router to improve routabil-ity by a simulated diusion process based on the duality between congestion and concentration. Compared with a recently published A*-based algorithm used in a state of the art commercial tool and with similar routability and run-time as the negotiation based routing, D-Router reduces the number of unrouted nets by 4.6x with up to 94x runtime reduction.

Off-chip substrate routing for high-density packages is on the critical path for time to market. Compared with on-chip routers, existing commercial tools for off-chip routing have lower routability and often result in a large number of unrouted nets for manual routing. In this paper, we explain why planar routing is still required with multiple routing layers for substrate routing and then propose a flexible via-staggering technique to improve routability. In addition, we develop an efficient yet effective substrate routing algorithm, applying dynamic pushing to tackle the net ordering problem and reordering and rerouting to further reduce wire length and congestion. Compared with an industrial design tool that leaves 936 nets unrouted for nine industrial designs with a total of 6100 nets, our algorithm reduces the unrouted nets to 212, a 4.5-times net number reduction, which translates to design time reduction.

Thermal issue is a critical challenge in 3D IC circuit design. Incorporating thermal vias into 3D IC is a promising way to mitigate thermal issues by lowering down the thermal resistances between device layers. However, it is usually difficult to get enough space at target regions to insert thermal vias. In this paper, we propose a novel analytical algorithm to re-allocate white space for 3D ICs to facilitate via insertion. Experimental results show that after reallocating whitespaces, thermal vias and total wirelength could be reduced by 14% and by 2%, respectively. It also shows that whitespace distribution with via planning alone will degrade performance by 9% while performance-aware via planning method can reduce thermal via number by 60% and the performance is kept nearly unchanged.

In multi-layered power/ground (P/G) networks, to connect the whole network together, vertical vias are usually placed at intersections between metal wires of adjoining layers. In this paper, a deep study about the design of vertical vias is presented. First we present an efficient heuristic algorithm based on sensitivity analysis to optimize via allocation in early design stage. Compared with even allocation, averagely our algorithm is capable of reducing worst voltage drop by 8.43% while using the same or even less number of vias. Also, adjoint network method is utilized and significantly improves the efficiency of our algorithm. Next, we demonstrate that by linking metal wires of nonadjacent layers, cross-layer vias are powerful in eliminating "hot" areas which suffer from large voltage drop on bottom layer. A similar heuristic algorithm is also developed for the addition of cross-layer vias.

The conventional tools for mismatch elimination such as geometric symmetry and common centroid technology can only eliminate systematic mismatch, but can do little to reduce random mismatch and thermal-induced mismatch. As the development of VLSI technology, the random mismatch is becoming more and more serious. And in the context of Silicon on Insulator (SOI), the self-heating effect leads to unbearable thermal-induced mismatch. Therefore, in this paper, we first propose a new model which can estimate the combination effect of both random mismatch and thermal-induced mismatch by mismatch analysis and SPICE simulation. And in order to meet the different sensitivities of different symmetry pairs, an automatic classification tool and a configurable optimization process are also introduced. All of these are embedded in the floorplanning process. The final experimental results prove the effectiveness of our method.

It's a trend to consider power supply integrity at early stage to improve the design quality. In this paper, we propose a novel algorithm to optimize floorplan together with P/G network. Compared with previous methods, our algorithm can search the floorplan space more efficiently and therefore lead to better results. Further, we also propose a smart heuristic method to build P/G mesh grid with optimized topology. Experimental results show our method can speedup the floorplanning process by about 10 times and reduce the routing area of P/G network while maintaining the floorplan quality and P/G integrity.

Traditionally, clock network layout is performed after cell placement. Such methodology is facing a serious problem in nanometer IC designs where people tend to use huge clock buffers for robustness against variations. That is, clock buffers are often placed far from ideal locations to avoid overlap with logic cells. As a result, both power dissipation and timing are degraded. In order to solve this problem, we propose a low power clock buffer planning methodology which is integrated with cell placement. A Bin- Divided Grouping algorithm is developed to construct virtual buffer tree, which can explicitly model the clock buffers in placement. The virtual buffer tree is dynamically updated during the placement to reflect the changes of latch locations. To reduce power dissipation, latch clumping is incorporated with the clock buffer planning. The experimental results show that our method can reduce clock power significantly by 21% on average.

Compared with on-chip routers, the existing commercial tools for off-chip routing have a much lower routability and often result in a large number of unrouted nets for manual routing. In this paper, we develop an effective, yet efficient, substrate routing algorithm, applying dynamic pushing to alleviate the net ordering problem and reordering and rerouting for further wire length and congestion reduction. Compared with an industrial design tool that leaves 936 nets unrouted for nine industrial designs with a total of 6100 nets, our algorithm reduces the unrouted nets to 212, a 4.5-times net number reduction and practically more design time reduction.

Recent generation of FPGA devices takes advantage of speed and density benefits resulted from heterogeneous FPGA architecture, in which several basic LUTs can be combined to form one larger size LUT called Macro. Large Macros not only decrease network depth efficiently but also reduce area. In this paper, a new technology mapping algorithm, named MacroMap is proposed for the heterogeneous FPGAs with effective area estimation to overcome the main disadvantage that traditional technology mapping algorithms only generate one kind of typical K-LUT and cannot make full use of LUTs with different sizes (basic LUTs and Macros). Experimental results show that MacroMap can obtain 19% gain on area while keeping the network depth optimal compared with the existing heterogeneous FPGA mapping algorithm heteromap[8].

Power Gating is an effective method to reduce leakage power. One of the most important issues in power gating design is the decision on the size of sleep transistor, which is mostly determined by the maximum instantaneous current (MIC) and the maximum tolerable voltage drop. In order to reduce the sleep transistor area, the distributed sleep transistor network (DSTN) was proposed to reduce MIC by connecting all the virtual ground nets together. Most of the following works focused on estimating the MICs through sleep transistors accurately. But the previous works use a pre-defined global voltage drop constraint on circuit, which leads to a uniform gate slowdown. In this paper, we propose a performance driven methodology for DSTN design, which exploits the maximum tolerable voltage drops of gates, particularly the non-critical ones, to reduce the total sleep transistor area without additional performance loss. Moreover, a clustering strategy in placement is proposed to help further reduce the total sleep transistor area. Experimental results show that the proposed approach can reduce the total sleep transistor area by about 36% on average.

Clock gating is a popular technique for reducing power dissipation in clock network. Although there have been numerous research efforts on clock gating, the previous approaches still have a significant weakness. That is, they usually construct a gated clock tree after cell placement, i.e., cell placement is performed without considering clock gating and may generate a solution unfriendly to subsequent gated clock tree construction. As a result, the control gates inserted in the tree construction is very likely to cause cell overlap. Even though the overlap can be eventually removed in placement legalization, remarkable wirelength/power overhead is incurred. In this paper, we propose a gate planning technique which is integrated with a partition-based cell placer. During cell placement, the planning judiciously inserts clock gates based on power estimation. In addition, pseudo edges are inserted between clock gates and registers in order to reduce clock wirelength and enable long shut-off periods. At the end, when a relatively detailed placement is obtained, a post-processing is performed to degrade the inefficient clock gates to clock buffers. We compared our approach with recent previous works on ISCAS89 benchmark circuits. Our method reduces the clock tree wirelength and power by 22.06% and 40.80%, respectively, with a very limited increase on signal nets wirelength and power compared with the conventional (register-oblivious) placement. The results also indicate that our algorithm outperforms the clock-gating-oblivious placement [9] on power reduction and performance improvement.

Leakage power soars quickly as VLSI technology advance and supply voltage scaling, in the near future, it will exceed the dynamic power to become the main contributor of power dissipation. Previous methods on leakage power minimization always notice the negative effect of increasing the gate’s threshold voltage Vth, and the power reduction is obtained based on power and speed (or performance) tradeoff. However, increasing the gate’s Vth could be used to adjust the subtrees’ imbalance for a clock tree. In this paper, for a gated clock tree, we analyze the bottom up merging segment generation process and conclude the conditions for increasing the gate’s Vth. Our idea is trying to assign high Vthto the gates without total wirelength and performance overheads, and in some cases, it could even be used to get more balanced subtrees. Experimental results on a set of ISCAS89 benchmark circuits demonstrate that our algorithm could assign more than half of the gates with high Vth, the resultant leakage power reduction is more than 43% without any total wirelength and delay penalties.

Clock gating is one of the most effective techniques to reduce clock network power dissipation. Although it has already been studied considerably, most of the previous works are restricted to either logic level or clock routing stage. Due to the restriction, clock gating often meets the trouble of wirelength overhead and frequent control signal switching, both of which degrade its effectiveness. Furthermore, previous design flows which insert gate logics after placement introduce a lot of overlaps, especially when there are lots of gate logics inserted. In this work, we propose a new design flow for low power gated clock network construction, in order to minimize the clock wirelength and the activity of control signals, and to eliminate the overlaps incurred by the gate logics. Our method begins with a coarse placement followed by soft register clustering. Then, we perform clock tree topology construction and zero skew clock routing to further reduce the power and the clock skew. Last, the gated clock network is fed back to the placer for incremental placement. Experimental results on ISCAS89 benchmarks demonstrate that our method outperforms previous algorithm of activity aware register placement in clock wirelength and clock power reduction with signal nets wirelength and signal nets power increase within 5% and 3%, respectively

This paper presents a fast and accurate solution, namely Fashion, to routability-driven global routing problem. Fashion is based on two efficient yet effective techniques: 1) dynamic pattern routing (DPR) and 2) movable-segment-driven DPR. These two techniques enable Fashion to explore large solution space to achieve high routability with low time complexity. Compared with BoxRouter, Fashion has a shorter wire length and reduces overflow and runtime by 5 and 15 times, respectively. Compared with FastRoute, Fashion has similar runtime but 90% smaller overflow and 1.9% shorter wire length. Fashion is significantly better than Labyrinth and Fengshui in terms of overflow, wire length, and runtime.

This paper proposes a novel stochastic method for analyzing the voltage drop variations of on-chip power grid networks, considering lognormal leakage current variations. The new method, calledStoEKS, applies Hermite polynomial chaos to represent the random variables in both power grid networks and input leakage currents. However, different from the existing orthogonal polynomial-based stochastic simulation method, extended Krylov subspace (EKS) method is employed to compute variational responses from the augmented matrices consisting of the coefficients of Hermite polynomials. Our contribution lies in the acceleration of the spectral stochastic method using the EKS method to fast solve the variational circuit equations for the first time. By using the reduction technique, the new method partially mitigates increased circuit-size problem associated with the augmented matrices from the Galerkin-based spectral stochastic method. Experimental results show that the proposed method is about two-order magnitude faster than the existing Hermite PC-based simulation method and many order of magnitudes faster than Monte Carlo methods with marginal errors. StoEKS is scalable for analyzing much larger circuits than the existing Hermit PC-based methods.

This paper presents a fast and accurate global routing algorithm, DpRouter, based on two efficient techniques: (1) dynamic pattern routing (Dpr), and (2) segment movement. These two techniques enable DpRouter to explore large solution space to achieve better routability with low time complexity. Compared with the state-of-the-arts, experimental results show that we consistently obtain better routing quality in terms of both congestion and wire length, while simultaneously achieving a more than 30x runtime speedup. We envision that this algorithm can be further leveraged in other routing applications, such as FPGA routing.

Multiple supply voltage (MSV) is one of the most effective schemes to achieve low power, but most works are based on logic level. A few recent works are based on physical level but all of them do not consider level converters which have an important effect in dual-vdd design. In this work we propose a logic and layout aware approach for voltage assignment and voltage island generation in placement process to minimize the number of level converters and to implement voltage islands with minimal overheads. Experimental results show that our approach uses much less level converters than the approach in (Bin Liu, 2006) (reduced by 59.50% on average) when achieving the same power savings. The approach is able to produce feasible placement with a small impact to traditional placement goals.

This paper proposes a fast and practical decoupling capacitor (decap) budgeting algorithm to optimize the power ground (P/G) network design. The new method adopts a modified random walk process to partition the circuit. Then, by utilizing the isolation property of decaps, this new method avoids solving the large nonlinear programming problem in traditional decap optimization process. Also, this method integrates leakage currents optimization algorithm using a refined leakage model. Experimental results demonstrate that our proposed method achieves approximate a 10times speed up over the heuristic method based on sensitivity and only about 6% decap area deviation from the optimal budget using the programming method.

In the context of SOI, thermal constraint is more serious for analog devices. Besides the hot-spot effect, the temperature gradient on symmetrical devices may cause errors and even failures in the function. In order to handle these problems, this paper introduces an accurate thermal model into the placement process. Based on the geometric symmetry which is achieved with corner block list (CBL) for the first time, the thermal model helps to find the thermal-optimal placement. And the experimental results show this method is promising.

For modern processor designs in nanometer technologies, both block and interconnect pipelining are needed to achieve multi-gigahertz clock frequency, but previous approaches consider block pipelining and interconnect pipelining separately. For example, all recent works on wire pipelining assume pre-pipelined components and consider only inserting pipeline stages on point-to-point wire or bus connections. To the best of our knowledge, this paper is the first that considers block pipelining and interconnect pipelining simultaneously. We optimize multiple critical paths or loops in the micro-architecture and insert the pipelines stages optimally in the blocks and wires of these loops to meet the clock frequency requirement. We propose two approaches to this problem. The first approach is based on mixed integer linear programming (MILP) which is theoretically guaranteed to produce the optimal solution, and the second one is an efficient graph-based algorithm that produces near-optimal solutions. Experimental results show that simultaneous block and interconnect pipelining leads to more than 20% improvement over wire-pipelining alone on the overall processor performance. Moreover, the graph-based approach gives solutions very close to the MILP results ( 2% more than MILP results on average) but in a much shorter runtime.

This paper describes the stochastic model order reduction algorithm via stochastic Hermite polynomials from the practical implementation perspective. Comparing with existing work on stochastic interconnect analysis and parameterized model order reduction, we generalized the input variation representation using polynomial chaos (PC) to allow for accurate modeling of non-Gaussian input variations. We also explore the implicit system representation using sub-matrices and improved the efficiency for solving the linear equations utilizing block matrix structure of the augmented system. Experiments show that our algorithm matches with Monte Carlo methods very well while keeping the algorithm effective. And the PC representation of non-Gaussian variables gains more accuracy than Taylor representation used in previous work (Wang et al., 2004).

With the rapid development of semiconductor technology, the working frequency of chips increases dramatically. Thus simultaneous switching noise (SSN) must be considered for robust power/ground (P/G) network design. In this paper, we mainly focus on the SSN effects for P/G network optimization. We first point out the drawbacks of the P/G optimization process without considering the SSN, by analyzing the optimized P/G grids. Then we propose a random walk based technique to consider SSN by adding decoupling capacitor (decap) prior to the nonlinear optimization process. This additional decap allocation phase constructs good current return path for the switching current caused by clock buffers and then reduces the dynamic voltage drop. Experiment results show that the proposed method achieves 2X speed up over the original approach without adding decaps in advance while the decap budget overhead is acceptable.

Leakage power is becoming a key design challenge in current and future CMOS designs. Due to technology scaling, the leakage power is rising so quickly that it largely elevates the die temperature. In this paper, we deeply investigate the impact of leakage power on thermal profile in 2D and 3D floorplanning. Our results show that chip temperature can increase by about 11 V in 2D design and 68 V for 3D case with leakage power considered. Then we propose a thermal-driven floorplanning flow integrated with an iterative leakage-aware thermal analysis process to optimize chip temperature and save leakage power consumption. Experimental results show that for 2D design, the max chip temperature can be reduced by about 8 "C and the proportion of leakage power to total power can be reduced from 19.17% to 11.12%. The corresponding results for 3D are 60 degC temperature reduction and 16.3% less leakage power proportion.

More and more IP cores are used in modern SOC designing. In order to place IP cores effectively, hierarchical design has been introduced and better supported by fixed-outline floorplanning than outline-free [1]. In this paper, we also consider buffer insertion issue in fixed-outline floorplanning with the help of the Less Flexibility First (LFF) algorithm, which runs in a fixed-outline area and places IP cores as hard modules one after another with no backtracks. Unlike Simulated Annealing (SA), LFF is a deterministic packing algorithm and runs without topological representations. Therefore, it is able to tell the difference among geometric floorplans with the same topological structure, which is helpful to get a better result for buffer planning since buffer insertions are quite sensitive to a geometric change. Moreover, a 2-staged packing and a post greedy method after packing are also introduced based on a net-classing strategy and finally help to achieve great success rate improvement of buffer insertion (about +40.7% in 0.18um and +37.1% in 0.07μm). Meanwhile, our buffer planning method runs much faster than SA, since it is deterministic and has no backtracks. Besides, it is also useful to provide an initial solution for SA for further optimization.

This paper studies the impacts of dummy fill for chemical mechanical polishing (CMP)-induced capacitance variation on buffer insertion during routing. Compared with existing methods, our algorithm is more feasible by performing buffer insertion not in post-process but during routing. Our contributions are threefold. First, we introduce a fast dummy fill estimation algorithm based on [4], which is better than traditional linear programming (LP) algorithm and suitable for early estimation. Second, based on some reasonable assumptions, we present an optimum virtual dummy fill method to estimate dummy position and the effects on the interconnect capacitance. Third, further analysis shows that the influences on the intermediate layer are more than that on the global layer, and as the required metal layer density increases the influences become more serious. Experiments gave the similar results and verified the necessity of early dummy fill estimation. Our dummy fill aware buffer insertion during early routing is promising and necessary.

Yield driven skew scheduling method leads to a clock tree with much greater wire length and buffer number that is not acceptable by designer. Geometry based register position relationships are converted to skew constraints and are combined with timing constraints harmoniously. With the two kinds of skew constraints together, our algorithm solves the skew scheduling problem for both restrictions and gives safety margins for not only timing variations but clocktree wire variations. It makes the yield driven clock network realizable inpractical design. Experimental results show that our algorithm has 72.7% yield improvement then normal scheduling. In addition, the clock tree wire length and buffer number are reduced by 52.2% and 40.4% compared with previous yielddriven skew scheduling method.

We present new timing and congestion driven FPGA placement algorithms with minimal runtime overhead. By predicting the post-routing critical edges and estimating congestion accurately, our algorithms simultaneously reduce the critical path delay and the minimum number of routing tracks. The core of our algorithm consists of a criticality history record of connection edges and a congestion map. This approach is applied to the 20 largest MCNC benchmark circuits. Experimental results show that compared with VPR [1], our algorithms yield an average of 8.1% reduction (maximum 30.5%) in the critical path delay and 5% reduction in channel width. Meanwhile, the average runtime of our algorithms is only 2.3X as of VPR's.

In this paper, we propose a novel stochastic method for analyzing the voltage drop variations of on-chip power grid networks with log-normal leakage current variations. The new-method, called StoEKS, applies Hermite polynomial chaos (PC) to represent the random variables in both power grid networks and input leakage currents. But different from the existing Hermit PC based stochastic simulation method, extended Krylov subspace method (EKS) is employed to compute variational responses using the augmented matrices consisting of the coefficients of Hermite polynomials. Our contribution lies in the combination of the statistical spectrum method with the extended Krylov subspace method to fast solve the variational circuit equations for the first time. Experimental results show that the proposed method is about two-order magnitude faster than the existing Hermite PC based simulation method and more order of magnitudes faster than Monte Carlo methods with marginal errors. StoEKS also can analyze much larger circuits than the exiting Hermit PC based methods.

Thermal issues are a primary concern in the threedimensional (3D) integrated circuit (IC) design. Temperature, area, and wire length must be simultaneously optimized during 3D floorplanning, significantly increasing optimization complexity. Most existing floorplanners use combinatorial stochastic optimization techniques, hampering performance and scalability when used for 3D floorplanning. In this work, we propose and evaluate a scalable, temperature-aware, force-directed floorplanner called 3D-STAF. Force-directed techniques, although efficient at reacting to physical information such as temperature gradients, must eventually eliminate overlap. This can cause significant displacement when used for heterogeneous blocks. To smooth the transition from an unconstrained 3D placement to a legalized, layer-assigned floorplan, we propose a three-stage force-directed optimization flow combined with new legalization techniques that eliminate white spaces and block overlapping during multi-layer floorplanning. A temperature-dependent leakage model is used within 3D-STAF to permit optimization based on the feedback loop connecting thermal profile and leakage power consumption. 3D-STAF has good performance that scales well for large problem instances. Compared to recently published 3D floorplanning work, 3D-STAF improves the area by 6%, wire length by 16%, via count by 22%, peak temperature by 6% while running nearly 4× faster on average.

Minimization of clock network is traditionally achieved by clock routing, which may be helpless for a poor placement result. In this paper, a novel Dynamic Clock-Tree Building technique integrated into placement for zero-skew design is proposed. This method combines a pre-designed clock-tree with the Force-Directed Placement procedure to navigate the register placement for minimizing the clock network. Meanwhile, a new model of Multi-Level Bounding Box and technique of Multi-Level Attractive Force are proposed to give a better local distribution of registers. Experiments on several standard-cell benchmarks indicate an average 26.1% clock network reduction with the logic cell placement preserved well.

Iterative slack distribution is a prevalent method in timing analysis and clock scheduling. Finding minimum mean cycle is the most time consuming step in the each iterative process. We present a practical strategy that can speed up the loop. A fast negative cycle detection method is used for examining whether the cycle of length two is really the minimum mean cycle. Traditional complicated minimum mean cycle algorithm can be skipped during the iterative slack distribution process. Experimental results show that our method can reduce running time of the iterative slack distribution process. The percentages are from 47% to 90% for different benchmark circuits.

An efficient analytical 3D placement algorithm for mixed-mode placement is presented, which consists of 3D global placement and detailed placement. In global placement, wire length and cell division are unified into a quadratic objective function. It takes advantage of quadratic programming to optimize the unified objective efficiently. 3D discrete cosine transformation (DCT) is introduced to help divide cells into different layers. The number of vertical vias gets better controlled during global placement and a new method to optimize cell division after global placement is presented. For detailed placement, we traverse 3D to 2D by net decomposition and finish detailed placement by network flow algorithm. Experimental results show that the 3D placement algorithm is very promising.

3D packing is a fundamental problem for VLSI design. It arises from 3D-ICs floorplan design and task schedule in reconfigurable FPGA design. In this paper, we present a novel 3D floorplan representation by improving the 3D bounded slice-surface grid (3D-BSG) structure in two aspects: (1) optimize the evaluation time complexity from O(n3) to O(n2) by using three block relation graphs; (2) handle the infeasible assignment problem of 3D-BSG in linear time by giving the rule of null relation rooms. The effectiveness and efficiency of the fast 3D-BSG are shown by both theoretical analysis and experimental results. The average speedup compared to the original 3D-BSG is 44times high.

Obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction is an essential part of routing. Recently, IC routing and related researches have been extended from Manhattan architecture (lambda2-geometry) to Y-/X-architecture (lambda3-lambda4-geometry) to improve the chip performance. This paper presents an O(n log n) heuristic, lambda-OAT, for obstacle-avoiding Steiner minimal tree construction in the lambda-geometry plane (lambda-OASMT). In this paper, based on obstacle-avoiding constrained Delaunay triangulation, a full connected tree is constructed and then embedded into lambda-OASMT by zonal combination. To the best of our knowledge, this is the first work addressing the lambda-OASMT problem. Compared with most recent works on OARSMT problem, lambda-OAT obtains up to 30-Kx speedup with quality solution. We have tested randomly generated cases with up to 10 K terminals and 10-K rectilinear obstacles within 4 seconds on a Sun V880 workstation (755-MHz CPU and 4-GB memory). The high efficiency and accuracy of lambda-OAT make it extremely practical and useful in the routing phase.

In this paper, we investigate thermal via (T-via) planning during three-dimensional (3-D) floorplanning. First, we consider the temperature constrained T-via planning (TVP) problem on a given 3-D floorplan. Second, we integrate dynamic TVP into 3-D floorplanning process. Our main contribution and results can be summarized as follows. We solve the temperature constrained TVP problem by solving a sequence of simplified interlayer and intralayer TVP subproblems. Each subproblem is formulated as convex programming problem and we derive nearly optimal solution for detailed T-via distribution. Based on the TVP solution, we implement the integrated TVP and 3-D floorplanning algorithm in a two-stage approach. Before floorplanning, blocks are assigned into different layers by solving a sequence of knapsack problems. During floorplanning, T-vias are allocated with white space redistribution to optimize T-via insertion. Experimental results show that our TVP approach can reduce T-vias by 12% compared with a recent published work (J. Cong and Y. Zhang, "Thermal via planning for 3-D ICs," in Proc. Int. Conf. Comput.-Aided Des., Nov. 2005, pp.745-752). Compared with the postfloorplanning optimization approach, integrating TVP into floorplanning process can reduce T-vias by 16% with 21% runtime overhead

In this paper, we present a novel pattern-based method to simulate large-scaled power/ground (P/G) grids. This method takes advantage of both traditional direct simulation methods and iterative simulation methods. The new method explores the geometry characteristics of regular P/G grids and translates topology similarity to submatrix regularity, which is called “pattern” in this paper. Such pattern structures can reduce the memory usage dramatically. Further, a new type of preconditioner is constructed to optimize the simulation process. Experimental results show that the proposed approach is about 5$\times$faster than the previous iterative methods with much lower memory, and is superior to the macro model-based hierarchical method on the tested large cases with pattern structures.

In recent years, the X-architecture is introduced to obtain better performance for integrated circuit physical design. This paper reformulates the global routing problem in X-architecture under the liquid routing model. Then, a dynamic resource assignment (Dra) method is presented to reduce potential vias. At last, a global router called DraXRouter, is designed, in which we adopt a dynamic-tabulist-based tree construction algorithm and a stochastic optimization strategy to gain high quality routing solution. Tested on ISPD'98 benchmarks, DraXRouter achieves better routing performance compared with two recent global routers.

In this paper we propose a method for standard cell placement with support for dual supply voltages, aiming to reduce total power under timing constraints and to implement voltage islands with minimal overheads. The method begins with timing and power driven coarse placement, followed by a few iterations between voltage assignment and placement refinement to generate voltage islands. Several techniques, including timing and power driven net weighting, seed growth based voltage assignment, and soft clustering strategy for placement refinements are employed in our implementation. Experimental results on a set of MCNC benchmarks show that our approach is able to produce feasible placement for dual-Vdd designs and significantly reduce total power with a wirelength increase within 14% compared to a power and timing driven placer without voltage islands.

This paper advances a new methodology based on signal-path information to resolve the problem of device-level placement for analog layout.This methodology is mainly based on three observations: thinking of hierarchical design for analog, structural feature of circuit based on signal-path, requirements of matching/symmetry constraint and the reduction of parasitics.The thinking of hierarchical design makes the whole analog circuit divided into core-circuit and bias-circuit.So, the algorithm is designed as two independent steps: core-circuit is placed firstly, and then bias-circuit.The structural feature of circuit based on signal-path and the requirement of matching/symmetry constraint decide the placement pattern of core-circuit.The reduction of parasitics requires the algorithm to select the optimal variants to realize the placement.Experimental results demonstrate that this algorithm can generate the compact layout with high performance and it is universal and effective.

In this paper, we study the relationship between C4 package resonance effects and logical switching timing correlations, which has not been thoroughly investigated in the past. We show that improper logic designs with some special timing correlations can lead to adverse large voltage drops, which are due to resonance effects in the widely used C4 package. We first present the numerical analysis results on industry C4 package circuits to demonstrate resonance phenomenon. Then we propose a simple algorithm to compute the worst-case logical timing correlations among cells leading to resonance. Finally, we develop an efficient technique in early logic design stage to estimate the resonance risk. Experiment results demonstrate the effectiveness of the proposed method for the accurate prediction of the resonance effect in C4 package.

Routing tree construction is a fundamental problem in modern VLSI design. In this paper we propose CDCTree, an Obstacle-Avoiding Rectilinear Steiner Minimum Tree (OARSMT) heuristic algorithm to construct an OARSMT. CDCTree is based on the current driven circuit (CDC) model mapped from an escape graph. The circuit structure comes from the topology of the escape graph, with each edge replaced by a resistor indicating the wirelength of that edge. By performing DC analysis on the circuit and selecting the edges according to the current distribution to construct an OARSMT, the wirelength of the resulting tree is short. The algorithm has been implemented and tested on cases of different scales and with different shapes of obstacles. Experiments show that CDCTree can achieve shorter wirelength than the existing best algorithm, An-OARSMan, when the terminal number of a net is less than 50.

In current manufacturing processes, certain layout configurations are likely to have reduced yield and/or reliability due to increased susceptibility to stress effects or poor tolerance to certain processes like lithography. These problematic layout configurations need to be efficiently detected and eliminated from a design layout to enable better yield. In this paper, such layout configurations are called processhotspots and an efficient and scalable algorithm is proposed to detect such process-hotspots in a given layout.

This paper studies the buffer planning problem for interconnect-driven floorplanning. With development of deep submicron technology, interconnect plays dominant role and buffer-insertion is a most flexible and efficient way to resolve this problem. However, buffer-planning on a fixed topology which only optimizes area or total wire-length is not reasonable and at the same time, trying to generate a topology which optimizes timing is much too time-consuming. We develop an algorithm which exchanges blocks of similar size to optimize timing constraint. With this algorithm applied, based on a topology which has already optimized area, we generate a packing that doesn't increase total area but exchanges block's position so that interconnect performance could be optimized in reasonable time.

2.5-D integration is a promising technique to significantly reduce the interconnection delay and thus bring advancement to VLSI technology. New CAD tools and approaches are desired by 2.5-D IC circuit design. This paper designed a novel representation multi-layer-BSG and proposed an effective algorithm based on this structure. Quick strategy for solution evaluation and phrase-based strategy for simulated annealing engine are used to reduce the runtime complexity and to improve the performance. Compared with other representations, our algorithm are experimentally proved to be a better choice for 2.5-D floorplanning problem.

Increasing buffer number for future technology makes traditional one-pass-flow (timing driven placement is followed by buffer insertion and legalization) failed, since accommodation for buffers significantly disturbs original design. This paper exploits the delicate relationship between buffer insertion and timing driven placement, and proposes a novel method to incorporate buffer insertion during timing driven placement. Experimental results show that this incorporation not only ensures design convergence, but also benefits timing behavior and alleviates buffer explosion

As a promising approach to mitigate the challenge of interconnect limit, X-architecture allows routings along diagonal directions in addition to rectilinear directions. It can reduce routing wire length and vias number compared with conventional Manhattan routing. Although Steiner minimum tree and signal routing algorithms have been developed for X-architecture, clock routing has not been addressed to the best of our knowledge. However, wire length reduction is even more compelling for clock net, as wire is a major power consumer and power supply noise generator. In addition, X-architecture is very effective for interconnect delay and clock skew optimization. In this paper, we investigate the layout embedding technique for clock routing in X-architecture and integrate it with the deferred-merge embedding (DME) algorithm. To alleviate the inaccuracy of the Elmore delay (ED) model, a more accurate fitted Elmore delay (FED) model is employed. Experimental results on benchmarks exhibit encouraging results.

Power dissipation problem becomes a dominant factor in the state-of-the-art IC design. Not only transistor but also interconnect should be taken into consideration in power calculation. In this paper, we use accurate delay and power models to construct buffered routing trees with considerations of delay and power optimization. Experimental results show our method can save much of buffer and power dissipation with better solutions

In this paper, we propose an efficient approach on handling the fixed-outline constraints with the objectives of both improving the success rate and minimizing the wire length. Our approach uses the less flexibility first principles (Sheqin Dong, 2001) which are derived from human's experience in solving rectangle packing problem in the daily life. In this construction based approach, success rate is guaranteed by using effective heuristics to guide the placement process. For the wire length objective, we use a wire length minimized solution gained by circuit partitioning and multilevel simulated annealing as a reference, where the topological relations derived from it are tried to be kept. We also apply a local grouping strategy and the minimal local wire length objective as supplements of wire length optimization. Experiment results show that our approach can achieve high success rates under tight outlines and comparable wire length with various aspect ratios

This paper presents a novel W-shape multilevel full-chip routing framework. The framework features the W-shape optimization flow. The first V-shape flow aims to optimize the global routing solution. And the second V-shape flow intends to improve the quality of the detailed routing result. The framework is tested on a set of commonly used benchmark circuits and compared with the previous multilevel routing systems. The experimental results are promising.

The optimization of virtual supply network plays an important role in MTCMOS low power design. Existing low power works are mainly on gate-level without any optimization on physical design level, which can lead to large amount of virtual supply networks. This paper presents (1) a low power driven physical design flow; (2) a novel low power placement to simultaneously place standard cells and sleep transistors and (3) sleep transistor relocation technique to further reduce the virtual supply networks. Experiment results are promising for both achieving up to 28.15% savings for virtual supply networks and well controlling the increase of signal nets

Routing is one of the important phases in VLSI/ULSI physical design. The obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction is an essential part of routing since macro cells, IP blocks, and pre-routed nets are often regarded as obstacles in the routing phase. Efficient OARSMT algorithms can be employed in practical routers iteratively. Recently, IC routing and related researches have been extended from Manhattan architecture (λ2-geometry) to Y- / X-architecture (λ3- / λ4-geometry) to improve the chip performance. This paper presents an O(nlogn) heuristic, λ-OASMT, for obstacle-avoiding Steiner minimal tree construction in the λ-geometry plane. Based on obstacle-avoiding constrained Delaunay triangulation, a full connected tree is constructed and then embedded into λ-OASMT by a novel method called zonal combination. To the best of our knowledge, this is the first work addressing the λ-OASMT problem. Compared with two most recent works on OARSMT problem, λ-OASMT obtains up to 30Kx speedup with an even better quality solution. We have tested randomly generated cases with up to 1K terminals and 10K rectilinear obstacles within 3 seconds on a Sun V880 workstation (755MHz CPU and 4GB memory). The high efficiency and accuracy of λ-OASMT make it extremely practical and useful in the routing phase, as well as interconnect estimation in the process of floorplanning and placement.

Incorporating thermal vias into 3D ICs is a promising way to reduce circuit temperature by lowering down the thermal resistances between device layers. In this paper, we integrate dynamic thermal via planning into 3D floorplanning process. Our 3D floorplanning and thermal via planning approaches are implemented in a two-stage approach. Before floorplanning, the temperature-constrained vertical thermal via planning is formulated as a convex programming problem. Based on the analytical solution, blocks are assigned into different layers by solving a sequence of knapsack problems. Then a SA engine is used to generate floorplans of all these layers simultaneously. During floorplanning, thermal vias are distributed horizontally in each layer with white space redistribution to optimize thermal via insertion. Experimental results show that compared to a recent published result from [14], our method can reduce thermal vias by 15% with 38% runtime overhead.

In this paper, we propose more accurate power/ground network circuit model, which consider both via and ground bounce effects to improve the performance estimation accuracy of on-chip power distribution networks. On top of this, a new precondition iterative method, which exploits geometry characters of power/ground networks, is developed to reduce memory usage and speed up the simulation. Experimental results show that the proposed method is about 5X faster than the incomplete LU decomposition (ILU) based preconditioned conjugate gradient iterative method and about half memory usage for simulating multi-layers large scale power/ground networks.

This paper proposes a fast decoupling capacitance (decap) allocation and budgeting algorithm for both early stage decap estimation and later stage decap minimization in today's very large scale integration physical design. The new method is based on a sensitivity-based conjugate gradient (CG) approach. But several new techniques that significantly improve the efficiency of the optimization process were adopted. First, an efficient search step scheme to replace the time-consuming line search phase in the conventional CG method for decap budget optimization was proposed. Second, instead of optimizing an entire large circuit, the circuit is partitioned into a number of smaller subcircuits and optimized separately by exploiting the locality of adding decaps. Third, the time-domain merged adjoint method was applied to compute the sensitivity information and show that the partitioning-based merged adjoint method leads to better results than the flat merged adjoint method with the improved search scheme. Experimental results show that the proposed algorithm achieves at least ten times speed-up over similar decap allocation methods reported so far with similar budget quality, and a power grid circuit with about one million nodes can be optimized using the new method in half an hour on the latest Linux workstations

New three-dimensional (3D) floorplanning and thermal via planning algorithms are proposed for thermal optimization in two-stacked die integration. Our contributions include (1) a two-stage design flow for 3D floorplanning, which scales down the enlarged solution space due to multidevice layer structure; (2) an efficient thermal-driven 3D floorplanning algorithm with power distribution constraints; (3) a thermal via planning algorithm considering congestion minimization. Experiments results show that our approach is nine times faster with better solution quality compared to a recent published result. In addition, the thermal via planning approach is proven to be very efficient to eliminate localized hot spots directly.

CAD tools have become more and more important for integrated circuit (IC) design since a complicated system can be designed into a single chip, called system-on-a-chip (SOC), in which physical design tool is an essential and critical part. We try to consider the via minimization problem as early as possible in physical design. We propose a routing method focusing on minimizing vias while considering mutability and wire-length constraint. That is, in the global routing phase, we minimize the number of bends, which is closely related to the number of vias. Previous work only dealt with very small nets, but our algorithm is general for the nets with any size. Experimental results show that our algorithm can greatly reduce the count of bends for various sizes of nets while meeting the constraints of congestion and wire-length.

This paper proposes a novel hierarchical approach to the efficient analysis of large VLSI power/ground grids. Different from the existing hierarchical approach where sub-circuit equivalent models are sparsified with computation-intensive integer programming and the resulting modeling may lead to larger errors if the top circuit matrix has large condition number, the new approach employs an iterative (relaxation) procedure to explicitly compensate the errors and avoid introducing dense matrix caused by the circuit reduction. We also propose an efficient scheme for partitioning high performance center-bumped P/G grids. Experimental results demonstrate that the new algorithm is more accurate than the existing hierarchical method while delivering more speedup over the flat simulators.

In today's power/ground(P/G) network design, on-chip decoupling capacitors(decaps) are usually made of MOS transistors with source and drain connected together. The gate leakage current becomes worse as the gate oxide layer thickness continues to shrink below 20Å. As a result, decaps will become leaky due to the gate leakage from CMOS devices. In this paper, we take a first look at the leaky decaps in P/G network optimization. We propose a leakage current model for practical decaps and also present a new two-stage leakage-current-aware approach to efficiently optimize P/G networks in a more area efficient way.

Routing is one of the important steps in VLSI/ULSI physical design. The rectilinear Steiner minimum tree (RSMT) construction is an essential part of routing. Since macro cells, IP blocks, and pre-routed nets are often regarded as obstacles in the routing phase, obstacle-avoiding RSMT (OARSMT) algorithms are useful for practical routing applications. This paper focuses on the OARSMT problem and presents an algorithm, named An-OARSMan, based on ant colony optimization. A greedy obstacle penalty distance (OP-distance) local heuristic is used in the algorithm and performed on the track graph. The algorithm has been implemented and tested on different kinds of obstacles. Experimental results show that An-OARSMan can handle complex obstacle cases including both convex and concave polygon obstacles with good length performance. It can always achieve the optimal solution in the cases with no more than 7 terminals.

In ultra-deep submicron VLSI circuits, clock network is a major source of power consumption and power supply noise. Therefore, it is very important to minimize clock network size. Traditional design methodologies usually let the clock router to undertake the task of clock network minimization independently. Since a clock routing is carried out based on register locations, register placement actually has fundamental influence to a clock network size. In this paper, we propose a new clock network design methodology that Incorporates register placement optimization. Given a cell placement result, incremental modifications are performed according to clock skew specifications. The incremental placement change moves registers toward preferred locations that may enable a small clock network size. At the same time, the side-effect to logic cell placement and wire connections is controlled. Experimental results on benchmark circuits show that the proposed methodology can reduce clock network size considerably with limited impact on signal net wirelength and critical path delay.

This paper presents a novel global routing algorithm, AT-PO-GR, to minimize the routing area under both congestion, timing, and RLC crosstalk constraints. The proposed algorithm is consisted of three key parts: (1) timing and congestion optimization; (2) crosstalk budgeting and estimation; and (3) crosstalk elimination and local refinement. Compared with the recent work introduced in [9] and [10], the proposed algorithm can achieve smaller routing area and fewer shields under the same design constraints, yet use less running time.

In modern VLSI designs, the increasingly severe power problem requests to minimize clock routing wirelength so that both power consumption and power supply noise can be alleviated. In contrast to most of traditional works that handle this problem only in clock routing, we propose to navigate standard cell register placement to locations that enable further less clock routing wirelength and power. To minimize adverse impacts to conventional cell placement goals such as signal net wirelength and critical path delay, the register placement is carried out in the context of a quadratic placement. The proposed technique is particularly effective for the recently popular prescribed skew clock routing. Experiments on benchmark circuits show encouraging results.

The Corner Block List representation (CBL) introduced in 2000 is an efficient and effective model for floorplanning and placement while still having some limitations such as redundancy and incompleteness. In this paper, we present an auxiliary 3-Route Model to eliminate the redundancy and insert empty rooms to resolve the incompleteness. Finally we attain a P-admissible representation ECBL(2) which has higher performances than the original CBL and the count of its solution space is O((2n)!26n/n!n4).

Motivated by VLSI/ULSI routing applications, we present a heuristic for rectilinear Steiner minimal tree (RSMT) construction. We transform a rectilinear minimum spanning tree (RMST) into an RSMT by a novel method called polygonal contraction. Experimental results show that the heuristic matches or exceeds the solution quality of previously best known algorithms and runs much faster.

With increasing of FPGA densities and greater demand for performance, a hierarchical approach is often used in FPGA design. Floorplanning is a key ingredient of the hierarchical approaches. However, heterogeneous resources across FPGA fabric have made FPGA floorplanning quite different from traditional floorplanning for ASICs. Enlightened by human's accumulated experience in "packing" problem, we propose a "less flexibility first" (LFF) algorithm. Experiment results based on Xilinx's XC3S5000 show that our algorithm can work better for heterogeneous FPGA floorplanning problem.

This paper presents a novel approach for fast transient analysis of buffered hybrid structured clock networks. The new method applies structure reduction and relaxed hierarchical analysis methods to reduce the circuit complexity and speedup the simulation. A simple controlled sources model is used for modeling clock buffers to deal with nonlinearity in the buffered clock trees. Our experiment results show that the proposed algorithm is about two orders of magnitude faster than HSPICE without loss on accuracy and stability. The relatively errors on delay times are within a few percent of the exact ones.

In this paper, we present an efficient and effective algorithm addressed to fixed-outline floorplanning. Unlike simulated annealing based algorithms, the proposed algorithm starts with sub-instances of the given instance. When feasible solution of a sub-instance is found, it augments this instance and tries to find a feasible solution of the augmented instance. This process continues until feasible solution of the given instance is found, or some stopping criteria met. Local search without hill-climbing is adopted to search for feasible solution of each instance. To optimize wirelength, once feasible solution of current instance is found, instead of augments it immediately, the proposed algorithm performs another local search for this instance. Experiments on MCNC and GSRC benchmarks show that in most cases the proposed algorithm can obtain feasible floorplans in quite short time, even with tight outlines or outlines with large aspect ratios imposed, and the results of wirelength optimization are also quite promising.

This paper proposes a fast decoupling capacitance (decap) allocation and budgeting algorithm for both early stage decap estimation and later stage decap minimization in today's VLSI physical design. The new method is based on a sensitivity-based conjugate gradient (CG) approach. But it adopts several new techniques, which significantly improve the efficiency of the optimization process. First, the new approach applies the time-domain merged adjoint network method for fast sensitivity calculation. Second, an efficient search step scheme is proposed to replace the timeconsuming line search phase in conventional conjugate gradient method for decap budget optimization. Third, instead of optimizing an entire large circuit, we partition the circuit into a number of smaller sub-circuits and optimize them separately by exploiting the locality of adding decaps. Experimental results show that the proposed algorithm achieves at least 10X speed-up over the fastest decap allocation method reported so far with similar or even better budget quality and a power grid circuit with about one million nodes can be optimized using the new method in half an hour on the latest Linux workstations.

The progress of VLSI technology is facing two limiting factors: power and variation. Minimizing clock network size can lead to reduced power consumption, less power supply noise, less number of clock buffers and therefore less vulnerability to variations. Previous works on clock network minimization are mostly focused on clock routing and the improvements are often limited by the input register placement. In this work, we propose to navigate registers in cell placement for further clock network size reduction. To solve the conflict between clock network minimization and traditional placement goals, we suggest the following techniques in a quadratic placement framework: (1) Manhattan ring based register guidance; (2) center of gravity constraints for registers; (3) pseudo pin and net; (4) register cluster contraction. These techniques work for both zero skew and prescribed skew designs in both wirelength driven and timing driven placement. Experimental results show that our method can reduce clock net wirelength by 16%~33% with no more than 0.5% increase on signal net wirelength compared with conventional approaches.

In this paper, an efficient algorithm addressed to fixed-outline floorplanning is presented. The proposed algorithm takes sequence pair as representation and has following main features: (1) it uses common subsequence and penalty function to bound the variations of the widths of the floorplans to a quite small range; (2) a simple cost function which has no items about the heights of the floorplans is presented; (3) two-stage simulated annealing is adopted to minimize the wirelength. Experimental results show that the proposed algorithm is superior to other state-of-the-art fixed-outline floorplanning approaches in the following aspects: (1) it can achieve high successful probabilities, even with tight outlines and large aspect ratios given; (2) the feasibility of the given outline will be evaluated at the beginning of the floorplanning, which can save much time when infeasible outline is given. Besides, the experimental results on wirelength optimization are also promising.

A new methodology is proposed to accelerate AltPSM design flow for dark field AltPSM for large-scale layouts. When scaling to large-scale layouts, designing AltPSM may be much time consuming. Our new algorithm solves this problem by splitting a layout into smaller, easier-to-solve parts, solving the sub-layouts independently and simultaneously, and then recombining the sub-layouts. The experimental results on industry layouts indicate that parallel algorithm has potential to provide more significant improvement in speed and achieve a better quality of solutions.

It is important to model the substrate coupling for mixed-signal circuit designs today. This paper presents an improved direct boundary element method (DBEM) for substrate resistance calculation, where only the boundary of substrate volumes is discretized and only the free-space Green function is used. At first, we discard some inessential unknowns to compress the linear system without accuracy loss. Then we make the coefficient matrix sparser. In this way, solving the linear system is greatly accelerated. Experiments on various substrates validate that DBEM is several to tens of times faster than DCT-accelerated Green's function methods and the eigendecomposition method, while preserving high accuracy. Besides, another experiment shows that this method is versatile for irregular substrates.

This paper presents an improved multilevel Full-chip routing system which integrates global routing and detailed routing algorithms to achieve great enhancement in yield and reliability considering the redundant via placement. The system features a pre-coarsening stage which is equipped with a fast congestion-driven L-pattern global routing followed by the rvia-driven detailed routing. The L-pattern global routing benefits a lot to the reduction of vias and thus relieves the burden of redundant via addition. Then the rvia-driven maze routing algorithm considers the addition of redundant vias during routing. Finally the redundant via placement heuristic also contributes to improve the completion rate. We have tested the system on a set of commonly used benchmark circuits and compared the results with a previous multilevel routing framework. The experimental results are promising.

The dominating contribution of interconnect to system performance has made it critical to plan the resources of the buffers and routes in the early stage of the layout. In this paper, we integrate floorplanning with buffer insertion for performance-driven design processes. We devise a two-step method to evaluate the feasible buffer insertion sites, which can improve the efficiency of the buffer-planning algorithm. By partitioning all empty spaces into blocks in the packing process, the buffer allocation is handled as an integral part of the floorplanning. Our buffer-planning algorithm maps the buffers into tiles with consideration of routing congestion. In this approach, we construct a distribution graph to model the possible routes. The buffer allocation method is performed on the updated distribution graph to find the buffer locations with their respective congestion costs. The method is based on a simulated annealing approach, which is composed of multiple phases to speed up the optimization. Since there is more freedom with floorplan optimization, the empirical results demonstrate better performance.

With advances in fabrication technology of very/ultra large scale integrated circuit (VLSI/ULSI), we must face many new challenges. One of them is the interconnect effects, which may cause longer delay and heavier crosstalk. To solve this problem, many interconnect performance optimization algorithms have been proposed. However, when these algorithms are designed based on rectilinear interconnect architecture, the optimization capability is limited. Therefore, nonrectilinear interconnect architectures become a field of active research in which the octilinear interconnect architecture is the most promising one since it extends from the rectilinear case and greatly shortens the wire length. Meanwhile, an interconnect with less length is helpful to reduce wire capacitance, congestion, and routing area. In an interconnect architecture, the Steiner minimal tree (SMT) construction is one of the key problems. In this paper, we give two practical octilinear Steiner minimal tree (OSMT) construction algorithms based on octilinear spanning graphs (OSGs). The one with edge substitution (OST-E) has a worst-case running time of O(nlogn) and a similar performance as the recent work using batched greedy. The other one with triangle contraction (OST-T) has a small increase in the constant factor of running time and a better performance. These two are the fastest algorithms for octilinear Steiner tree construction so far. Experiments on both industrial and random test cases are conducted to compare with other programs. We also proposed the extension of our algorithms to any /spl lambda/ geometry.

This paper presents a novel approach to reducing the complexity of the transient linear circuit analysis for a hybrid structured clock network. Topology reduction is first used to reduce the complexity of the circuits and a preconditioned Krylov-subspace iterative method is then used to perform the nodal analysis on the reduced circuits. By proper choice of the simulation time step based on Elmore delay model, the delay of the clock signal between the clock source and the sink node and the skews between the sink nodes can be obtained efficiently and accurately. Our experimental results show that the proposed algorithm is two orders of magnitude faster than HSPICE without loss of accuracy and stability and the maximum error is within 0.4% of the exact delay time.

Timing performance and routability are two main goals of global routing. These two targets are mutually conflicting if we view and handle their effects independently. In this paper, we adopt a shadow price mechanism to incorporate the two issues into one unified objective function. We formulate global routing as a multicommodity flow problem. The objective function is the slack of congestion with the clock period as the delay limit from registers and inputs to registers and outputs. The multicommodity flow is expressed by a linear-programming formulation as a primal problem. We then convert the primal problem into a dual formulation using the shadow price as the variables. The shadow price of a net is the sum of its congestion price and timing price. The primal and dual formulation offers theoretical upper and lower bounds of the routing solution. Throughout the optimization process, the difference of the two bounds reduces, which provides the user's insight into the quality of the solutions. Based on the new formulation, this paper presents the UTACO algorithm for standard cell global routing.

This paper deals with area minimization of power network for very large-scale integration designs. A new algorithm based on efficient nonlinear programming techniques is presented to solve this problem. During the optimization, a penalty method, conjugate gradient method, circuit sensitivity analysis, and merging adjoint networks are applied, which enables the algorithm to optimize large circuits. The experiment results prove that this algorithm is robust and can achieve the objective of minimizing the area of power network in a short runtime.

Corner Block List (CBL) was recently proposed as an efficient representation for MOSAIC packing of rectangles. Although the original method is really innovative, there still remains room for improvement for our purpose. This article proposes a compact algorithm for placement based on corner block list. By introducing the dummy blocks in CBL, our algorithm can intellectively employ dummy blocks in the packing to represent the placement including empty rooms, which corner block list cannot represent. Our algorithm can obtain the fast convergence to an optimal solution. Based on the compact approach, we propose a new way to handle arbitrary shaped rectilinear modules. The experimental results are demonstrated by some benchmark data and the performance shows effectiveness of the proposed method.

This paper studies the buffer planning problem for interconnect-centric floorplanning for nanometer technologies. The dead-spaces are the spaces within a placement that are not held by any circuit block. In this paper, we proposed a buffer planning algorithm based on dead space redistribution to make good use of dead-spaces for buffer insertion. Associated with circuit blocks under topological representations, the dead space can be redistributed by freely moving some circuit blocks within their rooms in the placement. The total area and the topology of the placement keep unchanged while doing the dead space redistribution. The number of nets satisfying the delay constraint can be increased by redistributing the dead space all over the placement, which has been demonstrated by the experimental results. The increment of the number of nets that satisfy delay constraints is 9% on an average.

Solution space smoothing allows a local search heuristic to escape from a poor, local minimum. In this paper, we propose a technique that can smooth the rugged terrain surface of the solution space of a placement problem. We design the solution space smoothing algorithms for VLSI placement with pre-placed modules and placement with consideration of congestion. Experiment results demonstrated that solution space smoothing is very efficient for VLSI module placement, and it can be applied to all floorplanning representations proposed so far.

This paper presents a path-based timing-driven quadratic placement algorithm. The delay of the path acts as the timing constraints. In the global optimization step, it tries to satisfy the timing constraints. In the partition step, it tries to decrease the cut number of critical paths. It has some special skills, such as decrease the delay on the longest path, pad assign, to decrease the delay further. Results show this algorithm can make the timing behavior improve more than 20%.

Timing performance and routability are two main issues of global routing. In this paper, we adopt a shadow price mechanism to incorporate the two issues into one unified objective function. The shadow price of a net is the sum of its congestion price and timing price. Based on the new formulation, this paper presents the UTACO algorithm for standard cell (SC) global routing. The experimental results show that UTACO is efficient for both timing and congestion optimization.

Abstract Congestion minimization is the least understood in placement objectives, however, it models routability most accurately. In this paper, a new incremental placement algorithm C-ECOP for standard cell layout is presented to reduce routing congestion. Congestion estimation is based on a new routing model and a more accurate cost function. An integer linear programming (ILP) problem is formulated to determine cell flow direction and avoid the conflictions between adjacent congestion areas. Experimental results show that the algorithm can considerably reduce routing congestion and preserve the performance of the initial placement with high speed. Key words: congestion, standard cell, incremental placement 1.

Fast and accurate interconnect parasitic parameter extraction has become increasingly critical for verification and analysis in VLSI today. In this paper, a fast hierarchical extraction approach based on Boundary Element Method (BEM) is presented for 3-D parasitic capacitance computation. Hierarchical partition of the 3-D field creates many parts which are called 3-D BEM blocks. After combining all the 3-D BEM blocks, the capacitance matrix for a given set of nets can be computed by applying the boundary conditions. Numerical results shows that this method performs many times faster than the 3-D field solver, with equal accuracy.

As the CMOS technology enters the very deep submicron era, inter-wire coupling capacitance becomes the dominant part of load capacitance. The coupling effects have brought new challenges to routing algorithms on both delay estimation and optimization. In this paper, we propose a timing-driven global routing algorithm with consideration of coupling effects. The two-phase algorithm based on a timing-relax method includes a heuristic Steiner tree algorithm and an optimization algorithm. Experimental results are given to demonstrate the efficiency and accuracy of the algorithm.

By dividing the packing area into routing tiles, we can give the budget of the buffer insertion. And the detail locating of the blocks in their rooms can be implemented for each iterations during the annealing process to favor the later buffer planning. The buffer insertion will affect the possible routes as well the congestion of the packing. The congestion estimation in this paper takes the buffer insertion into account. So we devise a buffer planning algorithm to allocate the buffer into tiles with congestion information considered. The buffer allocation problem is formulated into a net flow problem and the buffer allocation can be handled as an integral part in the floorplanning process. Since there is more freedom for floorplan optimization, the floorplanning algorithm integrated with buffer planning can result in better performance and chip area.

The computational time and memory of three-dimensional (3-D) capacitance extraction have been greatly reduced by using a quasimultiple medium (QMM) technology, because it enlarges the matrix sparsity produced by the direct boundary element method (BEM). An approach to automatically determining the QMM cutting pair number and a preconditioning technique are proposed to enhance the QMM-based capacitance extraction. With these two enhancements, the capacitance extraction can achieve much higher speed and adaptability. Experimental results show over 10X speed-up and memory saving over the multipole approach with comparable accuracy.

Previous works on buffer planning are mainly based on fixed die placement. It is necessary to reduce the complexity of computing the feasible buffer insertion sites to integrate the buffer planning with the floorplanning process. In this paper, we give an efficient buffer planning algorithm with linear complexity by computing all the feasible buffer insertion sites in a 2-step method. By partitioning all the dead spaces into blocks while doing the packing, the buffer allocation can be handled as an integral part in the floorplanning process. Our method is based on a simulated annealing approach which is divided into two phases: timing optimization phase and buffer insertion phase. Since there is more freedom for floorplan optimization, the floorplanning algorithm integrated with buffer planning can result in better time performance and chip area.

The timing behavior and congestion behavior are two important goals in the performance-driven standard-cell placement. In this paper, we analyze the relationship between the timing and congestion behavior. We bring up a multi-step placement algorithm to reach the two goals. First, the timing-driven placement algorithm is used to find the global optimal solution. In the second step, the algorithm tries to decrease the maximum congestion while not deteriorating the timing behavior. We have implemented our algorithm and tested it with real circuits. The results show that the maximum delay can decrease by 30% in our timing-driven placement and in the second step the maximum congestion will decrease by 10% while the timing behavior is unchanged.

A deterministic algorithm for VLSI block placement was developed in this paper through human's accumulated experience in solving "packing" problem. Rectangle packing problem is just a simplified case of the polygon-shape stone plate packing problem that the ancient masons needed to face. Several "packing" principles derived from the so-called "less flexibility first" experience of the masons. A k-d tree data structure is used for manipulating the packed rectangles under the derived packing principles. Experiment results demonstrate that the algorithm is effective and promising in building block layout application.

In this paper, we describe a new congestion-driven placement based on cell inflation. In our approach, we have used the method of probability- estimation to evaluate the routing of nets. We also take use of the strategy of cell inflation to eliminate the routing congestion. Further reduction in congestion is obtained by the scheme of cell moving. We have tested our algorithm on a set of sample circuits from American industry and the results obtained have shown great improvement of routability.

In floorplanning of typical VLSI design, some modules are required to satisfy some placement constraints in the final packing. Boudary Constraint is one kind of those placement constraints to pack some modules along one of the four sides: on the left, on the right, at the bottom or at the top of the final floorplan. We implement the boundary constraint algorithm for general floorplan by extending the Corner Block List (CBL) - a new efficient topology representation for non-slicing floorplan. Our contribution is to find the necessary and sufficient characterization of the modules along the boundary represented by Corner Block List. So that we can check the boundary constraints by scanning the intermediate solutions in the linear time during the simulated annealing process and fix the corner block list in case the constraints are violated. The experiment results are demonstrated by several examples of MCNC benchmarks and the performance is remarkable.

The abutment constraint problem is one of the common constraints in practice to favor the transmission of data between blocks. Based on Corner Block List(CBL), a new algorithm to deal with abutment constraints is developed in this paper. We can obtain the abutment information by scanning the intermediate solutions represented by CBL in linear time during the simulated annealing process and fix the CBL in case the constraints are violated. Based on this algorithm, a new method to deal with L-shaped/T-shaped blocks is proposed. The shape flexibility of the soft blocks and the rotation and reflection of L-shaped/T-shaped blocks are exploited to obtain a tight packing. The experiment results are demonstrated by some benchmark data and the performance shows effectiveness of the proposed method.

This paper deals with area minimization of power distribution networks for VLSIs. A new algorithm based on efficient nonlinear programming techniques is presented to solve this problem. Experimental results prove that this algorithm has achieved the objectives of minimizing the area of power/ground networks with higher speeds.

Abstract This paper describes a simplified hybrid method to calculate the frequency-dependent inductances of transmission lines, which combines cross-section coupled circuit method with boundary element method (BEM) just solving Laplace’s equation. The coupled circuit method is used to calculate inductance in low frequency range; The BEM builds the capacitance matrix, then we invert this matrix (omit the row and column relate to ground plane), we can obtain inductance relating to the high frequency at which the current only distributes on surfaces of conductor. A cubic spline interpolation between inductance at low and very high frequency gives a good result over entire frequency range. Comparing this method with previous hybrid method [3], it avoids solving Helmholtz’s equation and obtains the capacitance matrix at the same time, greatly reducing the total burden of calculation. Numerical tests show it is applicable and efficient. I.

%&''&()**& +,$ %&''&() -'$ ., /012"" " "

Article Free Access Share on Area routing oriented hierarchical corner stitching with partial bin Authors: Zhang Yan Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. China Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. ChinaView Profile , Wang Baohua Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. China Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. ChinaView Profile , Cai Yici Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. China Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. ChinaView Profile , Hong Xianlong Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. China Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. ChinaView Profile Authors Info & Claims ASP-DAC '00: Proceedings of the 2000 Asia and South Pacific Design Automation ConferenceJanuary 2000Pages 105–110https://doi.org/10.1145/368434.368587Published:28 January 2000Publication History 0citation220DownloadsMetricsTotal Citations0Total Downloads220Last 12 Months45Last 6 weeks9 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on MMP: a novel placement algorithm for combined macro block and standard cell layout design Authors: Hong Yu Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. China Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. ChinaView Profile , Xianlong Hong Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. China Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. ChinaView Profile , Yici Cai Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. China Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. ChinaView Profile Authors Info & Claims ASP-DAC '00: Proceedings of the 2000 Asia and South Pacific Design Automation ConferenceJanuary 2000 Pages 271–276https://doi.org/10.1145/368434.368632Online:28 January 2000Publication History 16citation61DownloadsMetricsTotal Citations16Total Downloads61Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this paper, a corner block list-a new efficient topological representation for non-slicing floorplan is proposed with applications to VLSI floorplan and building block placement. Given a corner block list, it takes only linear time to construct the floorplan. Unlike the O-tree structure, which determines the exact floorplan based on given block sizes, corner block list defines the floorplan independent of the block sizes. Thus, the structure is better suited for floorplan optimization with various size configurations of each block. Based on this new structure and the simulated annealing technique, an efficient floorplan algorithm is given. Soft blocks and the aspect ratio of the chip are taken into account in the simulated annealing process. The experimental results demonstrate the algorithm is quite promising.

We proposed a new global routing algorithm solving the net ordering problem. The algorithm uses random optimization methods to keep the equality of earlier routed nets and later routed nets in passing congested areas. It can find a solution independent of net ordering in short time. A global router is implemented in this method. Experiments show that the router performs much faster than Matula router while obtaining solutions with approximate quality.

In this paper, we defined a new FSM model based on the synchronous behavior and symbolic representation technique. The algorithm to elaborate the model from the VHDL description of synchronous circuits is presented. By eliminating the unnecessary transition function, our model has much less states than Deharbe's mixed model. The experimental results demonstrate the model and modeling method can make symbolic model checking more practical.

In deep submicron VLSI circuits, the interconnect parasitic capacitance is a very important factor determining circuit performances such as power and time-delay. The Boundary Element Method (BEM) is an effective tool for solving Laplacian's equation applied in the parasitic capacitance extraction. In this paper, a hierarchical h-adaptive BEM is presented. It constructs a 3-D linear hierarchical shape function based on a constant boundary element and uses previous computations and solutions. Hence, it reduces computation significantly in the adaptive procedure. Besides, a combination of a residual-type estimator and reduced Z-Z error estimator for more reliable and efficient estimation of error is presented. Some numerical results show that this method is effective.

In this paper, an effective timing-driven building block placer is proposed. Interconnection delay is modeled and included during the placing process in order to minimize the area and wirelength, as well as to satisfy the timing constraints in the algorithm. The simulated annealing technique for constrained optimization problem and the sequence pair model proposed by H. Murata et al. (1996) are applied. Not only the timing constraint but also the aspect ratio is taken into account in the search process. The experimental results demonstrate the algorithm can improve the timing delay and obtain good placement.

This paper deals with the design and optimization of mesh-based power/ground network for cell-based VLSIs with macro cells. These macro cells absorb a lot of current, furthermore, the current that each pin of the macro cell absorbs is not known, which introduces a new problem to the design of power routing. This problem has not been discussed so far. In this paper, a new algorithm is presented to solve this problem. The algorithm includes 3 sub-algorithms: searching feasible solution, cutting branches and minimizing strap width. The algorithm has achieved the object of minimizing the area of power straps with high running speed.

In this paper we present a very simple, efficient while effective placement algorithm for Row-based VLSIs. This algorithm is based on strict mathematical analysis, and provably can find the global optima. From our experiments, this algorithm is one of the fastest algorithms, especially for very large scale circuits. Another point desired to point out is that our algorithm can be run in both wirelength and timing-driven modes.

In this paper, we propose an efficient timing-driven global router, TIGER, for gate array and standard cell layout design. Unlike other conventional global routing techniques, interconnection delays are modeled and included during the routing and rerouting process in order to minimize the maximum channel density for gate arrays or the total track number for standard cells, as well as to satisfy the timing constraints in TIGER. The timing-driven global routing problem is formulated as a multiterminal, multicommodity network flow problem with integer flows under additional timing constraints. Two novel performance-driven Steiner tree algorithms are proposed to generate the initial global routing trees. A critical-path-based timing analysis method is used to guarantee the satisfaction of timing constraints. Experimental results based on MCNC (ISCAS) benchmarks show that TIGER can obtain better results than or comparable results with TimberWolf 5.6.

This paper presents two performance-driven Steiner tree algorithms or global routing which consider the

In this paper, we propose an eflicient timing-driven global routing algorithm.Unlike other conventional global routing techniques, interconnection delays