Recently, the challenge of integrating an increasing number of transistors on a single die to adhere to Moores Law has spurred the need for innovative packaging solutions. Power/ground planes are integral to packages, and designers typically strive to maximize their size. This provides shielding and maintains constant impedance for adjacent high-speed signal wires, benefiting signal integrity. Additionally, large power/-ground planes help reduce DC IR drops, enhancing power integrity. However, the necessity for multiple power/ground nets, each requiring independent power/ground planes within a package, makes the optimal allocation of limited free space a complex task. This paper introduces a game-theoretic optimization method aimed at evenly mitigating DC IR drops across the multi-layer package power/ground planes. In the formulated game of achieving the ideal power/ground plane design, we can enhance the use of package space and realize a design with evenly distributed DC IR drops across all power/ground planes. This is accomplished by adjusting strategies and reaching a state of Nash equilibrium in the allocation of free space. Additionally, we propose a rapid multi-layer power/ground plane DC IR drop evaluation and a power/ground plane legalization method to bolster our optimization method.

Non-integer multiple cell height (NIMCH) standard-cell libraries offer promising co-optimization for power, performance and area in advanced technology nodes. However, such non-uniform design introduces new layout constraints where any sub-region can only accommodate gates of the same cell height due to manufacturability concerns. The existing physical design flow for NIMCH circuits, which handles the layout constraint by clustering and relocating gates according to their cell heights, often leads to substantial gate displacement that harms circuit performance. To alleviate the above issue, this paper proposes a row-based logic resynthesis procedure that explicitly adjusts cell heights after initial placement without changing cell positions. Experiment results demonstrate that compared with the conventional NIMCH physical design flow, our proposed approach can reduce the maximal delay by 26.1%.

A circuit design incorporating non-integer multi-height (NIMH) cells, such as a combination of 8-track and 12-track cells, offers increased flexibility in optimizing area, timing, and power simultaneously. The conventional approach for placing NIMH cells involves using commercial tools to generate an initial global placement, followed by a legalization process that divides the block area into row regions with specific heights and relocates cells to rows of matching height. However, such placement flow often causes significant disruptions in the initial placement results, resulting in inferior wirelength. To address this issue, we propose a novel multi-electrostatics-based global placement algorithm that utilizes the NIMH-aware clustering method to dynamically generate rows. This algorithm directly tackles the global placement problem with NIMH cells. Specifically, we utilize an augmented Lagrangian formulation along with a preconditioning technique to achieve high-quality solutions with fast and robust numerical convergence. Experimental results on the OpenCores benchmarks demonstrate that our algorithm achieves about 12% improvements on HPWL with 23.5X speed up on average, outperforming state-of-the-art approaches. Furthermore, our placement solutions demonstrate a substantial improvement in WNS and TNS by 22% and 49% respectively. These results affirm the efficiency and effectiveness of our proposed algorithm in solving row-based placement problems for NIMH cells.

3D heterogeneous integration enables the integration of multiple heterogeneous chiplets into the same package with the effective reduction of package size and interconnection latency. According to the market requirement, chiplets with robust re-usability and effective cost reduction can be selected from a library to form different package products for enlarging total profit. Since die-to-wafer (D2W) bonding enables the chiplets with different sizes to be bonded in a package, it is a more flexible option for 3D heterogeneous integration compared with the conventional wafer-to-wafer (W2W) bonding. However, this promising technique creates new issues, including 1) flexible chiplet bonding enabling more than one chiplet to be bonded with a base chiplet to construct multiple products and 2) degraded bonding leading to the degradation of performance. In this work, a distributed integer-linear-programming-based (ILP-based) method is proposed to efficiently maximize the profits of multiple package products considering the issues of cost-addition 3D heterogeneous integration with D2W bonding. Compared with the baseline, the distributed ILP-based method can achieve the best profits while achieving a 5.96X speedup. To the best of our knowledge, this is the first work to solve the multi-product optimization problem for 3D heterogeneous integration with D2W bonding.

Due to the cost and design complexity associated with advanced technology nodes, it is difficult for traditional monolithic System-on-Chip to follow the Moore's Law, which means the economic benefits have been weakened. Semiconductor industries are looking for advanced packages to improve the economic advantages. Since the multi-chiplet architecture supporting heterogeneous integration has the robust re-usability and effective cost reduction, chiplet integration has become the mainstream of advanced packages. Nowadays, the number of mounted chiplets in a package is continuously increasing with the requirement of high system performance. However, the large area caused by the increasing of chiplets leads to the serious reliability issues, including warpage and bump stress, which worsens the yield and cost. The multi-package architecture, which can distribute chiplets to multiple packages and use less area of each package, is a popular alternative to enhance the reliability and reduce the cost in advanced packages. However, the primary challenge of the multi-package architecture lies in the tradeoff between the inter-package costs, i.e., the interconnection among packages, and the intra-package costs, i.e., the reliability caused by warpage and bump stress. Therefore, a co-design methodology is indispensable to optimize multiple packages simultaneously to improve the quality of the whole system. To tackle this challenge, we adopt mathematical programming methods in the multi-package co-design problem regarding the nature of the synergistic optimization of multiple packages. To the best of our knowledge, this is the first work to solve the multi-package co-design problem.

Interconnect delay is a key factor that affects the chip performance in layer assignment. Particularly in the advanced process technologies of 5 nm and beyond, interconnect delay has grown significantly due to the increase of circuit scale. Moreover, coupling effect existed in wires reduces the accuracy of delay evaluation. On the other hand, the size of vias is often ignored in layer assignment, which enlarges the mismatch between global routing and detailed routing. To solve these problems, we proposeVPT, a timing-aware layer assignment algorithm considering via pillars, which includes the following five key techniques: 1) via pillar structure combined with nondefault-rule (NDR) wires is adopted to form a net delay optimization system for advanced process technologies; 2) a synthetical model that can adapt to varying types and sizes of both vias and wires is designed to evaluate overflow effectively; 3) a sorting strategy is devised to reduce uncertainty of layer assignment flow and improve stability of the proposed algorithm; 4) an awareness strategy based on multiaspect congestion assessment is designed to reduce overflow significantly; and 5) a net scalpel algorithm is devised to minimize the maximum delay of nets, so that the timing behaviors can be improved systematically. The experimental results on multiple benchmarks confirm that the proposed algorithm leads to lower delay and less overflow, while achieving the best solution quality among the existing algorithms with the shortest runtime.

This paper addresses a delay-driven layer assignment problem with consideration of via delay and coupling effect in the global routing stage. A negotiation-based framework is proposed to balance delay, congestion, and via count. Coupling capacitance is considered using a probabilistic look-up table. Finally, the proposed algorithm uses both parallel wires and wide wires to reduce wire delay. The effectiveness of our layer assignment algorithm is supported by extensive experimental results.

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

For high-performance synchronous systems, non-uniform/non-ideal supply voltages of buffers (e.g., due to IRdrop) may incur a large clock skew and thus serious performance degradation. This paper addresses this problem and presents the first symmetrical buffered clock-tree synthesis flow that considers supply voltage differences of buffers. We employ a two-phase technique of bottom-up clock sink clustering to determine the tree topology, followed by top-down buffer placement and wire routing to complete the clock tree. At each level of processing, clock skew and wirelength are minimized by the determination of buffer embedding regions and the alignment of buffer supply voltages. Experimental results show that our method can reach, on average, respective 76% and 40% clock skew reduction compared to the state-of-the-art work (1) without supply voltage consideration and (2) with an extension for supply voltages based on our top-down flow. The reduction is achieved by marginal resource and runtime overheads. Note that our method can meet the stringent skew constraint set by the 2010 ISPD contest for all cases, while other counterparts cannot. In particular, our work provides a key insight into the importance of handling practical design issues (such as IR-drop) for real-world clock-tree synthesis.

Modern global routers employ various routing methods to improve routing speed and quality. Maze routing is the most time-consuming process for existing global routing algorithms. This paper presents two bounded-length maze routing (BLMR) algorithms (optimal-BLMR and heuristic-BLMR) that perform much faster routing than traditional maze routing algorithms. In addition, a rectilinear Steiner minimum tree aware routing scheme is proposed to guide heuristic-BLMR and monotonic routing to build a routing tree with shorter wirelength. This paper also proposes a parallel multithreaded collision-aware global router based on a previous sequential global router (SGR). Unlike the partitioning-based strategy, the proposed parallel router uses a task-based concurrency strategy. Finally, a 3-D wirelength optimization technique is proposed to further refine the 3-D routing results. Experimental results reveal that the proposed SGR uses less wirelength and runs faster than most of other state-of-the-art global routers with a different set of parameters , , , . Compared to the proposed SGR, the proposed parallel router yields almost the same routing quality with average 2.71 and 3.12-fold speedup on overflow-free and hard-to-route cases, respectively, when running on a 4-core system.

Since some of major IC industry participants are moving to the highly regular 1D gridded designs to enable scaling to sub-20nm nodes, how to manufacture the randomly distributed cuts with reasonable throughput and process variation becomes a big challenge. With the help of hybrid lithography, people can apply different types of processes for one single layer manufacturing such that the advantages from different technologies can be combined together to further benefit manufacturing. In this paper, targeting cut printing difficulties and hybrid lithography with electron beam (E-Beam) and 193 nm immersion (193i) processes, we propose a novel algorithm to optimally assign cuts to 193i or E-Beam processes with proper modifications on cut distribution, in order to maximize the overall throughput. To validate our method, we construct our algorithm based on the forbidden patterns obtained from the optical simulation; then we formulate the redistribution problem into a well defined ILP problem and finally call a reliable solver to solve the whole problem. Experimental results show that the throughput is dramatically improved by the cut redistribution. Besides that, for sparser layers, the EBL process can be totaly saved, which largely reduces the fabrication cost.

DRAM has been the technology for computer main memory since Intel released the first commercial DRAM chip (i1103) in 1970. As technology scales and demand for memory performance, it seems DRAM is facing several challenges. Many other memory technologies are anticipated to replace it but none has emerged as a clear winner thus far. In this paper we post the question. Is it possible to re-examine the design of DRAM to continue its life for another decade at least?

In this paper, we formulate a problem of simultaneous redundant via insertion and line end extension for via yield optimization. Our problem is more general than previous works in the sense that more than one type of line end extension is considered and the objective function to be optimized directly accounts for via yield. We present a zero-one integer linear program based approach, that is equipped with two speedup techniques, to solve the addressed problem optimally. In addition, we describe how to modify our approach to exactly solve a previous work. Extensive experimental results are shown to demonstrate the effectiveness and efficiency of our approaches.

Double patterning lithography (DPL) is the enabling technology for printing in sub-32nm nodes. In the EDA literature, researchers have been focusing on double-exposure double-patterning (DEDP) DPL for printing arbitrary 2D features where the layout decomposition problem for double exposure is an interesting graph coloring problem. But due to overlay errors, it is very difficult for DEDP to print even 1D features. A more promising DPL technology is self-aligned double patterning (SADP) for 1D design. SADP first prints dense lines and then trims away the portions not on the design by a cut mask. The complexity of cut mask is very high, adding to the skyrocketing manufacturing cost. In this paper we present a mask cost reduction method with circuit performance consideration for SADP. This is the first paper to focus on the mask cost reduction issue for SADP from a design perspective. We simplify the polygons on the cut mask, by formulating the problem as a constrained shortest path problem. Experimental results show that with a set of layouts in 28nm technology, we can largely reduce the complexity of cut polygons, with little impact on performance.

Multiple dynamic supply voltage (MDSV) provides an effective way to reduce dynamic power and is widely used in high-end or low-power designs. The challenge of routing MDSV designs is that the net in MDSV designs needs to be planned carefully to avoid electrical problems or functional failure as a long interconnect path pass through the shutdown power domains. As the first work to address the MDSV global routing problem, power domain-aware routing (PDR) problem is defined and the point-to-point PDR algorithm is also presented herein with look-ahead path selection method and look-up table acceleration approach. For multi-pin net routings, a novel constant-time table-lookup mechanism by invoking four enhanced monotonic routings to fast compute the least-cost monotonic path from every node to the target sub-tree is presented to speed up the query about routing cost (including driven-length slack) to target during multi-source multi-target PDR. Experimental results confirm that the proposed MDSV-based global router can efficiently identify legally optimized routing results for MDSV designs, and can effectively reduce overflow, wire length, inserted level shifters and runtime.

Before VLSI design starts, it is strategically important to do product planning for targeted market segments that need specific applications, and to optimally reuse at different levels to save design and silicon costs with shorter time-to-market schedule. Conventional ASIC or SoC design floorplan usually targets for one single product; and, high efforts in re-floorplan and re-convergence for different products are still required if there is no pre-design stage multi-product planning. Therefore, the problem of designing floorplans at product or market planning stage that simultaneously optimizes multiple products, or Multi-product Floorplanning, is introduced. To the best of our knowledge, this is the first work in literature that addresses this newly emerged and financially important problem. We start with the necessary number of basic functional blocks to accommodate all the products, and pack them using a simulated annealing (SA) based floorplanner that can easily incorporate other costs (e.g., product finance weights). Given a candidate floorplan, we provide both an O(n3) exact algorithm and a O(n) greedy heuristic to identify the Minimum Feasible Region for each product, where n is the number of basic blocks in this floorplan. These identification procedures are integrated into the SA framework to generate a floorplan that favors the configurable multi-product design. The effectiveness of our approach is validated by promising results on several data sets derived from industrial test cases.

When VLSI technology scales down to sub-40nm process node, systematic variation introduced by the lithography is a persistent challenge to the manufacturability. The limitation of the resolution enhancement technologies (RETs) forces people to adopt a regular cell design methodology. In this paper, targeted on 1D cell design, we use simulation data to analyze the relationship between the line-end gap distribution and printability. Based on the gap distribution preferences, an optimal algorithm is provided to efficiently extend the line ends and insert dummies, which will significantly improve the gap distribution and help printability. Experimental results on 45nm and 32nm processes show that significant improvement can be obtained on edge placement error (EPE).

Modern global routers use various routing methods to improve routing speed and the quality. Maze routing is the most time-consuming process for existing global routing algorithms. This paper presents two bounded-length maze routing (BLMR) algorithms (optimal-BLMR and heuristic-BLMR) to perform much faster routing than traditional maze routing algorithms. The proposed sequential global router, which adopts a heuristic-BLMR, identifies less-wirelength routing results with less runtime than state-of-the-art global routers. This study also proposes a parallel multi-threaded collision-aware global router based on a previous sequential global router. Unlike the conventional partition-based concurrency strategy, the proposed algorithm uses a task-based concurrency strategy. Experimental results reveal that the proposed sequential global router uses less wirelength and runs about 1.9X to 18.67X faster than other state-of-the-art global routers. Compared to the proposed sequential global router, the proposed parallel global router yields almost the same routing quality with average 2.71 and 3.12-fold speedup on overflow-free and hard-to-route benchmarks, respectively, when running on an Intel quad-core system.

As on-track double vias take less routing resources and have better electrical characteristics, we study in this paper the problem of double via insertion with a preference for on-track double vias (DVI/ON) in a postrouting stage. The primary goal is to insert as many double vias as possible, and maximizing the number of on-track double vias is a secondary objective. We present a zero-one integer linear program-based approach to optimally solve the DVI/ON problem. Moreover, we also discuss a special case of the DVI/ON problem and present a maximum-weighted bipartite matching-based optimal approach. Experimental results indicate that our approaches outperform existing algorithms in terms of solution quality.

Post-silicon validation has recently drawn designers' attention due to its increasing impacts on the VLSI design cycle and cost. One key feature of the post-silicon validation is the use of spare cells. In the literature, most existing works focus on developing new delicate spare cell structures. On the other hand, the placement of spare cells has a crucial impact on the design cycle and cost of the post-silicon debugging; however, there exists not much work on this placement problem. In this paper, we propose the first spare-cell-aware analytical placement framework which predicts the spare cell requirement and considers spare cell insertion during global placement. We also propose a multilevel spare cell insertion technique which provides a more efficient spare cell planning and a better control of quality impact due to spare cell insertion. To guide the selection of available spare cell positions during insertion, we propose a mixed-integer-linear-programming formulation to determine the optimal spare cell positions. Experimental results show that our algorithm can averagely achieve 17--33% and 1.77--2.61X better quality of spare cell insertion than that of the existing spare cell insertion algorithms, UniSpare [10] and PostSpare [22, 26], on the tested real designs with 1--5% spare cell insertion rates.

Wire shaping for delay/power minimization has been extensively studied. Due to the perceived high design and manufacturing costs for using non-uniform wire shapes, wire shaping is generally considered to be impractical. In this paper, we present a practical wire shaping methodology. Non-uniform wire shapes are directly implemented on silicon wafer instead of in GDSII during design. We present novel enhancements to existing OPC technology to accurately print non-uniform wire shapes. Experimental results show that the post-OPC mask complexities of uniform wire and non-uniform wire are comparable. With minimal impact on the design and manufacturing flows and minimal additional design and manufacturing costs, we demonstrate that wire shaping can help to obtain substantial reduction of interconnect dynamic power without affecting timing closure. Our wire shaping methodology is an excellent example of Manufacturing for Design.

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

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

As the device shapes keep shrinking, the designs are more sensitive to manufacturing processes. In order to improve performance predictability and yield, mask-layout uniformity/evenness is highly desired, and it is usually measured by the feature densities within defined feasible ranges determined by the manufacturing-process design rules. To address the density-control problem, one fundamental problem is how to calculate density accurately and efficiently. In this paper, we propose a fast exact algorithm to identify the maximum/minimum density for a given layout. Compared with the existing exact algorithms, our algorithm reduces the running time from days/long hours to a few minutes/seconds. Moreover, it is even faster than the existing approximate algorithms in the literature.

In modern very large scale integration manufacturing processes, dummy fills are widely used to adjust local metal density in order to improve layout uniformity and yield optimization. However, the introduction of a large amount of dummy features also affects wire electrical properties. In this paper, we propose the first coupling-constrained dummy-fill analysis algorithm which identifies feasible locations for dummy fills such that the fill-induced coupling capacitance can be bounded within the given coupling threshold of each wire segment. A speedup approach is presented based on the cache concept. The algorithm also makes efforts to maximize ground dummy fills, which are more robust and predictable. The output of the algorithm can be treated as the upper bound for dummy-fill insertion, and it can be easily adopted in density models to guide dummy-fill insertion without disturbing the existing design.

As integrated circuits manufacturing technology is advancing into 65nm and 45nm nodes, extensive resolution enhancement techniques (RETs) are needed to correctly manufacture a chip design. The widely used RET called off-axis illumination (OAI) introduces forbidden pitches which lead to very complex design rules. It has been observed that imposing uniformity on layout designs can substantially improve printability under OAI. For metal layers, uniformity can be achieved simply by inserting dummy metal wire segments at all free spaces. Simulation results indeed show significant improvement in printability with such a dummy metal insertion approach. To minimize mask cost, it is advantageous to use dummy metal segments that are of the same size as regular metal wires due to their simple geometry. But these dummy wires are printable and hence increase coupling capacitances and potentially affect yield. The alternative is to use a set of parallel sub-resolution thin wires (which is not printed) to replace a printable dummy wire segment. These invisible dummy metal segments do not increase coupling capacitances but bring a higher lithography cost, which includes mask cost and RET/process expense. This paper presents a strategy for dummy metal insertion that can optimally trade off lithography cost and coupling capacitance. In particular, we present an optimal algorithm that can minimize lithography cost subject to any given coupling capacitance bound. Moreover, this dummy metal insertion achieves a highly uniform density because of the locality of coupling capacitance, which automatically ameliorates chemical mechanical polish (CMP) problem.

As the device shapes keep shrinking, the designs are more sensitive to manufacturing processes. In order to improve performance predictability and yield, mask layout uniformity/evenness is highly desired, and it is usually measured by the feature density with defined feasible range in manufacture process design rules. To address the density control problem, one fundamental problem is how to calculate density accurately and efficiently. In this paper, we propose a fast exact algorithm to identify the maximum density for a given layout. Compared with the existing exact algorithms, our algorithm reduces the running time from days/hours to a few minutes/seconds. And it is even faster than the existing approximate algorithms in literature.

In modern VLSI manufacturing processes, dummy fills are widely used to adjust local metal density in order to improve layout uniformity and yield optimization. However, the introduction of a large amount of dummy features also affects wire electrical properties. In this paper, we propose the first Coupling constrained Dummy Fill (CDF) analysis algorithm which identifies feasible locations for dummy fills such that the fill induced coupling capacitance can be bounded within the given coupling threshold of each wire segment. The algorithm also makes efforts to maximize ground dummy fills, which are more robust and predictable. The output of the algorithm can be treated as the upper bound for dummy fill insertion, and it can be easily adopted in density models to guide dummy fill insertion without disturbing the existing design.

Redundant via insertion and line end extension employed in the post-routing stage are two well known and highly recommended techniques to reduce yield loss due to via failure. However, if the amount of inserted redundant vias is not well controlled, it could violate via density rules and adversely worsen the yield and reliability of the design. In this paper, we first study the problem of redundant via insertion, and present two methods to accelerate a state-of-the-art approach (which is based on a maximum independent set (MIS) formulation) to solve it. We then consider the problem of simultaneous redundant via insertion and line end extension. We formulate the problem as a maximum weighted independent set (MWIS) problem and modify the accelerated MIS-based approach to solve it. Lastly, we investigate the problem of simultaneous redundant via insertion and line end extension subject to the maximum via density rule, and present a two-stage approach for it. In the first stage, we ignore the maximum via density rule, and enhance the MWIS-based approach to find the set of regions which violate the maximum via density rule after performing simultaneous redundant via insertion and line end extension. In the second stage, excess redundant vias are removed from those violating regions such that after the removal, the maximum via density rule is met while the total amount of redundant vias removed is minimized. This density-aware redundant via removal problem is formulated as a set of zero-one integer linear programming (0-1 ILP) problems each of which can be solved independently without sacrificing the optimality. The superiorities of our approaches are all demonstrated through promising experimental results.

Engineering change order changes are almost inevitable in the late stages of a design process. Based on an existing design, incremental change is favored since it can avoid considerable efforts of redoing the whole process and can minimize the disturbance on the existing converged design. The coupling-capacitance violation elimination (CVE) problem is addressed. Due to the changes in the multiple layer routing design, the total coupling capacitance on some signal wire segments on a layer may be larger than their allowable bounds after postlayout timing/noise analysis. The target is to find a new routing solution without coupling-capacitance violations under certain constraints, which helps to keep the new design close to the original one. This paper proposes a two-stage algorithm to solve CVE problems, and present optimization strategies to speed up the execution. Experimental results demonstrate the efficiency and effectiveness of this algorithm

ECO changes are almost inevitable in late stages of a design process. Based on an existing design, incremental change is favored since it can avoid considerable efforts of re-doing the whole process and can minimize the disturbance on the existing converged design. In this paper, we address the CVE (Crosstalk Violation Elimination) problem. Due to the changes in a multiple layer routing design, the total capacitive crosstalk on some signal wire segments on a layer may be larger than their allowable bounds after post-layout timing/noise analysis. The target is to find a new routing solution without crosstalk violations under certain constraints which help to keep the new design close to the original one. We propose a two-stage algorithm to solve CVE problems, and present optimization strategies to speed up the execution. Experimental results demonstrate the efficiency and effectiveness of our algorithm.

As technology advances and the number of interconnections among modules rapidly increases, timing closure, and design convergence are the most important concerns. Hence, it is desirable to consider interconnect optimization as early as possible. Previous work for this issue can be classified into two directions: wire planning and buffer-block planning for interconnect-driven floorplanning. Wire planning for interconnect-driven floorplanning does not consider buffer insertion, and buffer-block planning for interconnect-driven floorplanning cannot overcome the limitation of a bad initial floorplan. In this paper, we first address simultaneous floorplanning and buffer-block planning (i.e., integrating buffer-block planning into floorplanning) for interconnect optimization. We adopt simulated annealing to refine a floorplan so that buffers can be inserted more effectively. In each iteration, we construct a routing tree for each net, allocate buffers for all nets, introduce corresponding buffer blocks into the intermediate floorplan, and invoke Lagrangian relaxation to optimize area and satisfy timing requirements. Further, in order to reduce the problem size, we present supermodule partitioning which partitions modules into supermodules. Experimental results show that our method of integrating buffer-block planning into floorplanning can significantly improve the interconnect delay and reduce the number of buffers needed. Based on a set of MCNC benchmark circuits, our approach achieves an average success rate of 86.1% of nets meeting timing constraints, inserts only 272 buffers on average, and consumes an average extra area of only 0.28% over the given floorplan, compared with the average success rate of 62.6%, 1123 buffers, and extra area of 1.05% resulted from a famous recent work presented at ICCAD'99.

As technology advances and the number of interconnections among modules rapidly increases, timing closure and design convergence are the most important concerns. Hence, it is desirable to consider interconnect optimization as early as possible. In this paper, we first address simultaneous floorplanning and buffer block planning (i.e., integrating buffer block planning into floorplanning) for interconnect optimization. Experimental results show that our method can significantly improve the interconnect delay and reduce the number of buffers needed.

We present a unified framework that considers flipflop and repeater insertion and the placement of flip-flop/repeater blocks during RT or higher level design. We introduce the concept of independent feasible regions in which flip-flops and repeaters can be inserted in an interconnect to satisfy both delay and cycle time constraints. Experimental results show that, with flip-flop insertion, we greatly increase the ability of interconnects to meet timing constraints. Our results also show that it is necessary to perform interconnect optimization at early design steps as the optimization will have even greater impact on the chip layout as feature size continually scales down.

Design ECO commonly happens in industry due to constraints or target changes from manufacturing, marketing, reliability, or performance. At each step, designers usually want to modify the existing solution incrementally and keep the design as close as possible to the existing one. In this paper, we address the PSO (Power rail - Signal wire Overlap) problem which solves overlaps between power rails and signal wires due to the changes in power rail design on the top layer of a multiple layer routing region. PSO problems are frequently caused by changes from power delivery system or package design. The new routing solution satisfies the following constraints: 1) Keep the routing of power rails in the new design unchanged. 2) Only the routing of the top two layers is changed. 3) Horizontal (vertical) signal wire segments on the top layer can only move up/down (left/right). At the same time, the new routing solution keeps the routing pattern unchanged. This requires: a) If one end point of a horizontal (vertical) wire segment on the top layer is a fixed pin, this segment can not move. b) If vertical (horizontal) projections of two horizontal (vertical) signal wire segments have overlaps, then the up/down (left/right) relationship should not be changed. c) If two horizontal (vertical) segments belonging to different nets are on the same track, their left/right (up/down) relationship should not be changed as long as the two segments still exist in the new solution. 4) For each signal wire segment, the deviation (i.e., the difference between its new position and the old one) should not exceed the user-defined allowable deviation bound. Different bounds can be set on different segments. We propose two algorithms to solve the PSO problem. Both algorithms guarantee to find a feasible solution as long as one exists. One is faster, while the other makes effort to minimize the total deviation as well as the max deviation. According to time and quality requirements, users can choose an appropriate algorithm to solve the problem. For a set of industrial test circuits, we were able to remove all overlaps between power rails and signal wires with minimal wire deviation.

Pad assignment with signal integrity optimization is very important for high-speed VLSI design. In this paper, an efficient method is proposed to effectively minimize both simultaneous switching noise and crosstalk that are inevitably caused by package inductance and capacitance during the design of high-speed/high-bandwidth circuits. Due to its efficiency, our algorithm can be incorporated into existing circuit floorplanning and placement schemes for the co-design of VLSI and packaging. For a set of industrial circuits/packages tested in our experiment, on the average, our method achieves a 16.8% reduction of total electrical noise when compared with the conventional design rule of thumb popularly used by circuit designers.

A placement scheme that considers both electrical performance requirements and thermal behavior for the high-performance multichip modules is described in this paper. Practical thermal models are used for placement of high-speed chips in multichip module packages under two different cooling environments: conduction cooling and convection cooling. Placement methods are modified to optimize conventional electrical performance and chip junction temperatures.

In this paper, a floorplanner for low power designs is presented. Our objective is to optimize total power consumption and area during the selection and placement of circuit modules. Furthermore, our method considers the reduction of power line noises, thermal reliability problems, and performance requirements.

With the increasing density of VLSI circuits, the interconnection wires are getting packed even closer. This has increased the effect of interaction between these wires on circuit performance and hence, the importance of controlling crosstalk. We consider the gridded channel routing problem where, specifically, the channel has 3 routing layers in the VHV configuration. Given a horizontal track assignment for the nets, we present an optimal algorithm for minimizing the crosstalk between vertical wiring segments in the channel by finding an optimal vertical layer assignment for them. We show an algorithm that minimizes total crosstalk between between wires on the same V layer on adjacent columns of the grid in O(/spl nu/ log /spl nu/) time using O(/spl nu/) memory, where the channel has /spl nu/ columns. We then extend this algorithm to consider crosstalk between wires in non-adjacent columns and between wires on different layers.

In this paper, we present a layer assignment method for high-performance multi-chip module environments. In contrast with treating global routing and layer assignment separately, our method assigns nets to layers while considering preferable global routing topologies simultaneously. We take transmission line effects into account to avoid noise in high-speed circuit packages. The problem is formulated as a quadratic Boolean programming problem and an algorithm is presented to solve the problem after linearization. Our method is applied to a set of benchmark circuits to demonstrate the effectiveness.