With the advancement of 3D IC technology, multilayer chip stacking enables improved performance and reduced power consumption, albeit at the cost of increased design complexity. In 3D IC designs, soft modules are also adopted to enable flexible floorplanning across multiple dies. To preserve module integrity and simplify interconnects, the standard cells and macros within the same module are typically constrained to be placed on the same layer and thus using the same technology. In addition, determining an appropriate shape and placement location for each soft module is critical for minimizing wirelength. This paper presents the first technology-aware 3D placement framework for mixed-size designs that incorporates region planning for soft modules. It combines an analytical placement engine with an integer linear programming (ILP)-based region planning strategy to handle the flexible nature of soft modules. To further enhance placement flexibility while limiting region complexity, the ILP formulation identifies an optimal L-shaped or rectangular region for each soft module. Experimental results demonstrate that, compared to a baseline approach, our flow achieves over 21% wirelength reduction, with only a 5% overhead compared to placement without the soft module constraint.

This paper presents the first warpage-aware generative learningbased floorplanning algorithm to effectively model the warpage effect and optimize the die floorplan on a fixed outlined substrate. With more heterogeneous materials and dense interconnects in advanced packaging, warpage is a main reliability concern and may degrade system performance. We present a novel transformer-based encoding scheme to learn node and edge representations, followed by parallel decoding and warpage-aware legalization to jointly minimize die displacement and warpage. Experimental results show that our algorithm improves warpage by 9.9% and wirelength by 8.3% on average, compared with the state-of-the-art work.

Modern very large-scale integration (VLSI) design requires the implementation of integrated circuits using electronic design automation (EDA) tools. Due to the complexity of EDA algorithms, the vast parameter space poses a huge challenge to chip design optimization, as the combination of even moderate numbers of parameters creates an enormous solution space to explore. Manual parameter selection remains industrial practice despite being excessively laborious and limited by expert experience. To address this issue, we present CROP, the first large language model (LLM)-powered automatic VLSI design flow tuning framework. Our approach includes: (1) a scalable methodology for transforming RTL source code into dense vector representations, (2) an embedding-based retrieval system for matching designs with semantically similar circuits, and (3) a retrieval-augmented generation (RAG)-enhanced LLM-guided parameter search system that constrains the search process with prior knowledge from similar designs. Experiment results demonstrate CROP’s ability to achieve superior quality-of-results (QoR) with fewer iterations than existing approaches on industrial designs, including a 9.9% reduction in power consumption.

To better utilize space and reduce wirelength within a fixed-outline with preplaced modules, modern floorplanning is desired to be able to handle rectilinear soft modules. Nevertheless, the induced special shape constraints have not been fully explored in the literature. In this paper, we propose a novel analytical-based approach to address the challenges of fixed-outline, preplaced modules, and rectilinear soft modules. Unlike most previous work, which abstracts modules as circles during global floorplanning, we treat modules as shape-adjustable rectangles and propose a differentiable shape mechanism to capture the impact of shaping on the floorplan quality. For legalization, we first construct an overlap graph to extract the neighborhood of overlaps, modules, and whitespaces. Then, a shortest-path based algorithm effectively migrates area from overlaps through a chain of modules to whitespaces while carefully considering the shape constraints. Finally, we iteratively expand and shrink the bounding boxes of modules to further refine the wirelength by improving area utilization. Our legalization and refinement allows rectilinear shapes to form naturally. Based on the experiments conducted on the GSRC, MCNC, and CAD contest benchmark suites, our results show that our approach achieves superior wirelength and runtime to the state-of-the-art works and the contest winning team, demonstrating its effectiveness and efficiency.

We have gathered a panel of experts who will delve into the electronic design automation (EDA) challenges at advanced technology nodes. In this rapidly evolving field, the race towards miniaturization presents new hurdles and complexities. With advanced nodes shrinking, design and technology co-optimization becomes an increasingly intricate task. Our panelists will share their unique insights on how they approach these challenges and the impact of complicated design rules on the design process. As designs grow larger and more complex, novel strategies and methodologies are necessary to address the runtime issues of EDA tools. Our discussion will explore these strategies, including promising emerging technologies such as multi-machine or GPU acceleration that show potential in mitigating runtime challenges.

Recently, successful applications of reinforcement learning to chip placement have emerged. Pretrained models are necessary to improve efficiency and effectiveness. Currently, the weights of objective metrics (e.g., wirelength, congestion, and timing) are fixed during pretraining. However, fixed-weighed models cannot generate the diversity of placements required for engineers to accommodate changing requirements as they arise. This paper proposes flexible multiple-objective reinforcement learning (MORL) to support objective functions with inference-time variable weights using just a single pretrained model. Our macro placement results show that MORL can generate the Pareto frontier of multiple objectives effectively.

AI-dedicated hardware designs are growing dramatically for various AI applications. These designs often contain highly connected circuit structures, reflecting the complicated structure in neural networks, such as convolutional layers and fully-connected layers. As a result, such dense interconnections incur severe congestion problems in physical design that cannot be solved by conventional placement methods. This paper proposes a novel placement framework for CNN accelerator units, which extracts kernels from the circuit and insert kernel-based regions to guide placement and minimize routing congestion. Experimental results show that our framework effectively reduces global routing congestion without wirelength degradation, significantly outperforming leading commercial tools.

In this paper, we present a new hybrid representation of slicing trees and multi-packing trees, called multi-domain-packing trees (MDP-trees), for macro placement to handle ultra large-scale multi-domain mixed-size designs. A multi-domain design typically consists of a set of mixed-size domains, each with hundreds/thousands of large macros and (tens of) millions of standard cells, which is often seen in modern high-end applications (e.g., 4G LTE products and upcoming 5G ones). To the best of our knowledge, there is still no published work specifically tackling the domain planning and macro placement simultaneously. Based on binary trees, the MDP-tree is very efficient and effective for handling macro placement with multiple domains. Previous works on macro placement can handle only single-domain designs, which do not consider the global interactions among domains. In contrast, our MDP-trees plan domain regions globally, and optimize the interconnections among domains and macro/cell positions simultaneously. The placement area of each domain is well reserved, and the macro displacement is minimized from initial macro positions of the design prototype. Experimental results show that our approach can significantly reduce both the average half-perimeter wirelength and the average global routing wirelength.

As design complexity rapidly grows, a modem design contains more complex constraints and has more clock domains. To these stringent timing requirements, a design is iteratively optimized. Along with intensive optimizations, fast timing analysis guiding designers to fix timing violations is desired. Thus far, previous works have focused on either timing exception handling or path search only. Different from them, in this paper, we tackle these two issues together for the urgent need in modern design. We first generalize timing exceptions to model all common timing exceptions and other path-specific timing quantities. Then, we propose a novel timing analysis flow that performs fast path search for generalized timing exception handling. Furthermore, we develop three delicate techniques to achieve fast path search, including local slack bounds, dynamic slack recovering, and slack priority queue. Experimental results show that our model is general, and our flow is promising with high efficiency and scalability.

A placer without considering modern technology and region constraints could generate solutions with irresolvable detailed-routing (DR) violations or even illegal solutions. This paper presents a high-quality placement algorithm to satisfy technology and region constraints and optimize DR routability with five major techniques: 1) a clustering algorithm followed by two-round quadratic placement to obtain an initial placement satisfying region constraints; 2) a novel density control technique to handle prefixed architectures and minimize global routing congestions; 3) an analytical placement algorithm with new wirelength and density models to consider region constraints; 4) a dynamic penalty increment strategy that reduces wirelength increments during global placement; and 5) a legalization algorithm that preserves the solution quality of global placement while satisfying technology and region constraints. Compared with the winning teams of the ISPD 2015 Blockage-Aware Detailed Routing-Driven Placement Contest and recent works, our placer achieves the best overall score and DR results.

In this paper, we present a damped-wave constructive macro placement framework which packs big macros to optimize both wirelength and routability simultaneously. Unlike traditional V-shaped and Λ-shaped multilevel frameworks which might lack respective local and global information during processing, our dampedwave framework considers both local and global information by the following two major techniques: (1) macro clustering to improve scalability, and (2) constructive macros declustering to assist a standard-cell placer to obtain better solutions. We also present a macro-grouping cost model to remedy the key drawback of ignoring the mismatches of standard-cell locations between the prototyping and the final standard-cell placement stages in existing three-stage mixed-size placers (containing prototyping, macro placement, and standard cell placement). We further propose the regularity penalty model to guide macros to form an integral, regular region during macro placement, facilitating the succeeding placement of standard cell. Compared with manual placement from industrial and a leading mixed-size placer, experimental results show that our damped-wave multilevel framework and cost models are efficient and effective in reducing half-perimeter wirelength and routed wirelength and overflows. In particular, our work provides a new research direction on effective frameworks for large-scale designs, which readily apply to many optimization problems limited with scalability.

With the increasing use of pre-designed macros in a modern chip and its induced high design complexity, macro placement has become a challenging problem in today's design houses. Most popular macro placement algorithms adopt a three-stage approach: placement prototyping, macro placement, and standard-cell placement, where cell positions after macro placement are assumed the same as those at the prototyping stage, possibly misguiding succeeding standard-cell placement. To close the gap between macro and standard-cell placement, we propose a macro-refining algorithm that adopts an integrated spreading technique considering the spreading of both macros and cells and the dynamic information of cell positions to improve macro placement. We further propose a new force-modulation technique to refine macro placement and a congestion-aware macro shifter to preserve more space for better routability. Extensive experiments based on various macro placements show that our proposed techniques are effective and our macro-refining algorithm can find significantly better placement solutions for large-scale mixed-size circuit designs.

Wirelength is the most fundamental objective in placement because it also affects various placement metrics (routability, timing, etc.). Half-perimeter wirelength (HPWL) is a pervasive metric for circuit placement. However, preplaced blocks (i.e., blockages) might misguide an HPWL-based placer to generate a placement solution that incurs significant routing detours. Consequently, it is desirable to develop an effective method to resolve the HPWL-rooted routing detour problem for placement optimization. This paper presents an efficient, generic, yet effective terminal propagation algorithm as a pre-placement process which can readily be integrated into a traditional placement flow to improve wirelength (and routability). Our algorithm identifies a region for each preplaced terminal according to its connectivity, and applies a minimum-cost maximum flow algorithm to propagate all preplaced terminals to their feasible propagation locations with the minimum total propagation length. Experimental results show that our flow with terminal propagation can reduce both global routed wirelength and routing congestion by 4% on average, compared with one without terminal propagation. In particular, our work also provides a long unnoticed insight into placement optimization with blockages, which can be addressed with an efficient, generic, yet effective scheme.

Custom layouts of digital blocks are often used in mixed-signal designs in order to meet the critical performance requirements. Unlike traditional standard-cell based digital placement, custom-cell based digital placement may need additional manual help and intervention to achieve higher performance. The need for manual intervention is primarily due to the inability of modern analytical placers in delivering satisfactory performance on placing designs without pre-placed blocks. While most design flow works in a flat or top-down fashion, custom digital design generally works in a bottom-up fashion that there is no prior knowledge on I/O pin plan since it is changeable by the owners of modules. Without any or very few fixed I/O locations, modern analytical placers tend to produce unsatisfactory results. In this work, we propose a method, mimicking the process of making beds, to guide state-of-the-art analytical placers to deliver better placement results. With the crafted pseudo anchors and nets, total HPWL on Capo10.5 [1], mPL6 [2], NTUplace3 [3] and VDAPlace [4] have improved by 2.92%, 8.69%, 25.26% and 10.72% respectively on a set of industry custom digital designs and improved by 2.19%, 4.34%, 36.09%, and 14.27% respectively on Peko-Suite1 benchmarks.

Analog layout generation in the advanced CMOS design is challenging by its increasing layout constraints and performance requirements. This situation becomes more intricate by the growing parasitic variability and manufacturing reliability. To facilitate the feasibility of template-based layout migration, this paper first introduces a layout preservation, which extracts placement and routing behaviors from an existing layout into a crossing graph via constrained Delaunay triangulation. And later this crossing graph can be migrated into multiple layouts with placement and routing reconnection. The proposed approach also provides a refinement for wire to optimize the performance metrics. This approach is applied to a variable-gain amplifier, a folded-cascode operational amplifier, and a low dropout regulator. The experimental results demonstrate more possibility on layout migration, such that averagely more than 75% routing of migrated layout is generated by our approach. Additionally, it exhibits the productivity with qualified performance on different designs.

Analog layout design has been a manual, time-consuming, and error-prone task for decades. To speed up layout design time for a new design, analog layout designers prefer referring to legacy designs and layouts rather than starting from scratch, or thoroughly applying placement and routing tools because legacy layouts contain pretty much design expertise. Motivated by such layout design process, this paper presents the first knowledge-based physical synthesis methodology to generate new layouts by integrating existent design expertise. The proposed approach can automatically analyze legacy design data including circuits, layouts, and constraints, extract matched sub-circuits between new and legacy designs, and generate multiple layouts for the new design by utilizing the quality-approved legacy layouts as much as possible. Experimental results show that the proposed methodology can achieve high layout reusage rate, and hence the designers' layout preference can be successfully reserved.

A wirelength-driven placer without considering routability could introduce irresolvable routing-congested placements. Therefore, it is desirable to develop an effective routability-driven placer for modern mixed-size designs employing hierarchical methodologies for faster turnaround time. In this paper, we propose a novel routability-driven analytical placement algorithm for hierarchical mixed-size circuit designs. This paper presents a novel design hierarchy identification technique to effectively identify design hierarchies and guide placement for better wirelength and routability. The proposed algorithm optimizes routability from four major aspects: 1) narrow channel handling; 2) pin density; 3) routing overflow optimization; and 4) net congestion optimization. Routability-driven legalization and detailed placement are also proposed to further optimize routing congestion. Compared with the participating teams for the 2012 ICCAD Design Hierarchy Aware Routability-driven Placement Contest, our placer can achieve the best quality (both the average overflow and wirelength) and the best overall score (by additionally considering running time).

Although modern analog placement algorithms aimed to minimize area and wirelength while satisfying symmetry, proximity, and other placement constraints, the generated layout does not reflect the circuit performance very well because of the routing-induced parasitics on the critical current/signal paths. To simultaneously consider symmetry, wirelength, area utilization, and current/signal paths during analog placement, this paper explores the feasibilities of symmetry islands and monotonic current paths in slicing trees for analog placement optimization. Experimental results show that the proposed formulation and algorithms can generate much more compact layouts resulting in similar or even better circuit performance compared with the previous work.

Double patterning lithography (DPL) is one of the most promising solutions for the 28nm technology node and beyond. The main idea of DPL is to decompose the layout into two sub-patterns and manufacture the layout by two masks. In addition to traditional analog design constraints, the pre-coloring constraint should also be considered, in which patterns of critical or sensitive modules have predefined masks before layout decomposition to reduce mismatches. In this paper, we present the first work that considers DPL during analog placement and simultaneously minimizes area, wirelength, and DPL conflicts. We first propose an extended conflict graph (ECG) to represent the relation between patterns of analog modules and apply an integer linear programming (ILP) formulation to determine the orientation of each module and the color of each pattern for conflict minimization. ILP reduction schemes are proposed to further reduce the runtime. Finally, we present a three-stage flow and DPL-aware perturbations to obtain desired solutions. Experimental results show that the proposed flow can effectively and efficiently reduce area, wirelength, and DPL conflicts.

A wirelength-driven placer without considering routability could introduce irresolvable routing-congested placements. Therefore, it is desirable to develop an effective routability-driven placer for modern mixed-size designs employing hierarchical methodologies for faster turnaround time. This paper presents a novel two-stage technique to effectively identify design hierarchies and guide placement for better wirelength and routability. To optimize wirelength and routability simultaneously during placement, a new analytical net-congestion-optimization technique is also proposed. Compared with the participating teams for the 2012 ICCAD Design Hierarchy Aware Routability-driven Placement Contest, our placer can achieve the best quality (both the average overflow and wire-length) and the best overall score (by additionally considering running time).

To strive for better circuit performance on analog design, layout generation heavily relies on experienced analog designers' effort. Other than general analog constraints such as symmetry and wire-matching are commonly embraced in many proposed works, analog circuit performance is also sensitive to routing behavior. This paper presents a CDT-based layout extraction to preserve routing behavior of the reference layout. Furthermore, a generalized layout prototyping methodology is proposed based on the layout extraction to achieve routing reuse. The proposed layout prototyping is applied to a variable-gain amplifier and a folded-cascode operational amplifier for both migration and prototypes generation. Experimental results show that our approach effectively reduces design cycle time and simultaneously produces reasonable performance.

As process technologies advance to the subwavelength era, the 1-D design style is regarded as one of the most effective ways to continue scaling down the minimum feature size. To improve the printability of 1-D cell design, it is essential to insert dummy patterns and optimize line-end gap distribution for each layer. This paper presents novel 1-D cell generation algorithms that simultaneously minimize 1-D cell area and enhance the printability. Experimental results show that the proposed algorithms can effectively and efficiently reduce the number of diffusion gaps, minimize used routing tracks, insert sufficient dummy patterns, and eliminate stage-like line-end gaps without power and timing overhead. Consequently, the 1-D cell area is minimized and the printability of the cell is enhanced. To the best of our knowledge, this is also the first work in the literature that considers line-end gap distribution during 1-D cell generation.

Although modern analog placement algorithms aimed to minimize area and wirelength while satisfying symmetry, proximity, and other placement constraints, the generated layout does not reflect the circuit performance very well because of the routing-induced parasitics on the critical current/signal paths. This paper introduces the current-path constraints in analog placement, demonstrates their impact on circuit performance, and derives new problem formulation and algorithms to find placement solutions with monotonic current paths. Experimental results show that the proposed formulation and algorithms can generate compact layouts resulting in the even better circuit performance after performing post-layout simulation.

This paper presents an analog layout migration methodology to quickly provide multiple layouts while keeping similar or better circuit performance. Unlike previous works that often generate a single layout that has exactly the same topology with the original layout, this new migration algorithm is able to provide results with different aspect ratios. First, various placement constraints, including topology, matching, and symmetry, are extracted from the original layout. The extracted constraints are hierarchically stored into a topology slicing tree. Placement is performed from the bottom tree nodes to the root tree node. In each tree node, multiple placements for the subtree are recorded. All possible placements under the constraints are recorded in the root node. This algorithm has been successfully applied to a variable gain amplifier and a folded cascode operational amplifier migrating from UMC 90nm to UMC 65nm. The experimental results validate that our approach can provide reasonable layouts, even a better result almost in no time.

Custom layouts of digital blocks are often used in mixed-signal designs in order to meet the critical performance requirements. Unlike traditional standard-cell based digital placement, custom-cell based digital placement may need to consider special routing patterns and pre-wires, very high design utilization, topology placement constraints, etc.

Due to skewed scaling of interconnect versus cell delay in deep submicron CMOS, modern VLSI timing closure requires extensive buffer insertion. Inserting a large number of buffers may cause not only dramatic cell migration but also routing hotspots. If buffering is not controlled well, it may fail to close a design. Placement with buffer porosity (i.e., cell density) awareness can allocate space for inserting these buffers, and buffering with congestion awareness can improve the routability. Therefore, there is essential need for a placement framework with explicit porosity and congestion control. In this paper, we propose the first integrated nonlinear placement framework with porosity and congestion aware buffer planning. We demonstrate the integration of increasingly refined cell porosity and routing congestion aware buffer planning and insertion methodology in a high quality nonlinear placer. Our experiments show the improvement of average routing overflow by 69%, average wirelength by 28% and average buffer count by 40%, compared with the traditional placement framework without buffer planning.

In this paper, we propose the first metal-density driven placement algorithm to reduce CMP variation and achieve higher routability. Based on an analytical placement framework, we use a probabilistic routing model to estimate the wire density during the placement. Then, the metal density and thickness are predicted by a predictive CMP model. The spreading forces are adjusted according to the metal density map to reduce the metal density variation. Experimental results show that our method reduces the topography variation by 12% and the number of dummy fills by 6% and achieves much better routability, compared with wirelength-driven placement

In this paper, we derive the X-half-perimeter wirelength (XHPWL) model for X-architecture placement and explore the effects of three different wire models on X-architecture placement, including the Manhattan-half-perimeter wirelength (MHPWL) model, the XHPWL model, and the X-Steiner wirelength (XStWL) model. For min-cut partitioning placement, we apply the XHPWL and XStWL models to the generalized net-weighting method that can exactly model the wirelength after partitioning by net weighting. For analytical placement, we smooth the XHPWL function using log-sum-exp functions to facilitate analytical placement. This paper shows that both the XHPWL and XStWL models can reduce the X wirelength effectively. In particular, our results reveal the effectiveness of the X architecture on wirelength reduction during placement and, thus, the importance of the study on the X-placement algorithms, which is different from the results given in the work of Ono et al. which suggests that the X-architecture placement might not improve the X-routing wirelength over the Manhattan-architecture placement.

We present in this paper a new interconnect-driven multilevel floorplanner, called interconnect-driven multilevel-floorplanning framework (IMF), to handle large-scale building-module designs. Unlike the traditional multilevel framework that adopts the ldquoLambda-shapedrdquo framework (inaccurately called the ldquoV-cyclerdquo framework in the literature): bottom-up coarsening followed by top-down uncoarsening, the IMF, in contrast, works in the ldquoV-shapedrdquo manner: top-down uncoarsening (partitioning) followed by bottom-up coarsening (merging). The top-down partitioning stage iteratively partitions the floorplan region based on min-cut bipartitioning with exact net-weight modeling to reduce the number of global interconnections and, thus, the total wirelength. Then, the bottom-up merging stage iteratively applies fixed-outline floorplanning using simulated annealing for all regions and merges two neighboring regions recursively. Experimental results show that the IMF obtains the best published fixed-outline floorplanning results with the smallest average wirelength for the Microelectronics Center of North Carolina/Gigascale Systems Research Center benchmarks. In particular, IMF scales very well as the circuit size increases. The V-shaped multilevel framework outperforms the Lambda-shaped one in the optimization of global circuit effects, such as interconnection and crosstalk optimization, since the V-shaped framework considers the global configuration first and then processes down to local ones level by level, and thus, the global effects can be handled at earlier stages. The V-shaped multilevel framework is general and, thus, can be readily applied to other problems.

In this paper, we propose the first metal-density-driven (MDD) placement algorithm to reduce chemical-mechanical planarization/polishing (CMP) variation and achieve higher routability. To efficiently estimate metal density and thickness, we first apply a probabilistic routing model and then a predictive CMP model to obtain the metal-density map. Based on the metal-density map, we use an analytical placement framework to spread blocks to reduce metal-density variation. Experimental results based on BoxRouter and NTUgr show that our method can effectively reduce the CMP variation. By using our MDD placement, for example, the topography variation can be reduced by up to 38% (23%) and the number of dummy fills can be reduced by up to 14% (8%), compared with those using wirelength-driven (cell-density-driven) placement. The results of our MDD placement can also lead to better routability.

In addition to wirelength, modern placers need to consider various constraints such as preplaced blocks and density. We propose a high-quality analytical placement algorithm considering wirelength, preplaced blocks, and density based on the log-sum-exp wirelength model proposed by Naylor and the multilevel framework. To handle preplaced blocks, we use a two-stage smoothing technique, i.e., Gaussian smoothing followed by level smoothing, to facilitate block spreading during global placement (GP). The density is controlled by white-space reallocation using partitioning and cut-line shifting during GP and cell sliding during detailed placement. We further use the conjugate gradient method with dynamic step-size control to speed up the GP and macro shifting to find better macro positions. Experimental results show that our placer obtains very high-quality results.

In this paper, we present a new multipacking-tree (MP-tree) representation for macro placements to handle modern mixed-size designs with large macros and high chip utilization rates. Based on binary trees, the MP-tree is very efficient, effective, and flexible for handling macro placements with various constraints. Given a global placement that already considers the areas and the interconnections among standard cells and macros, our MP-tree-based macro placer optimizes macro positions, minimizes the macro displacement from the initial macro positions, and maximizes the area of the chip center for standard-cell placement and routing. Experiments based on the Proceedings of the 2006 International Symposium on Physical Design placement contest benchmarks and Faraday benchmarks show that our macro placer combined with APlace 2.0, Capo 10.2, mPL6, or NTUplace3 for a standard-cell placement outperforms these state-of-the-art academic mixed-size placers alone by large margins in robustness and quality. In addition to wirelength, experiments on four real industrial designs with large macros and high utilization rates show that our method significantly reduces the average half-perimeter wirelength by 35 %, the average routed wirelength by 55 %, and the routing overflows by 13 times compared with Capo 10.2, implying that our macro placer leads to much higher routability.

In this paper, we present a new multi-packing tree (MP-tree) representation for macro placement to handle mixed-size designs. Based on binary trees, the MP-tree is very efficient, effective, and flexible for handling macro placement with various constraints. Given a global placement, our MP-tree-based macro placer optimizes macro positions, minimizes the macro displacement from the initial macro positions, and maximizes the area of the chip center for standard-cell placement and routing. Experiments based on the eight ISPD'06 placement contest benchmarks show that our macro placer combined with Capo 10.2, NTUplace3, or mPL6 for standard-cell placement outperforms these state-of-the-art academic mixed-size placers alone by large margins in both robustness and quality. In addition to wirelength, experimented on five real industrial designs show that our method significantly reduce the average HPWL by 35%, the average routed wirelength by 55%, and the routing overflows than the counterpart with Capo 10.2, implying that our macro placer leads to much higher routability.

In this paper, we derive the X-half-perimeter wirelength (XHPWL) model for X-architecture placement and explore the effects of three different wire models on X-architecture placement, including the Manhattan-half-perimeter wirelength (MHPWL) model, the XHPWL model, and the X-Steiner wirelength (XStWL) model. For min-cut partitioning placement, we propose a generalized net-weighting method that can exactly model the wirelength after partitioning by the net weight. The net-weighting method is general and can be incorporated into any wire models such as the XHPWL and XStWL models. For analytical placement, we smooth the XHPWL function using log-sum-exp functions to facilitate analytical placement. Our study shows that both the XHPWL model and the XStWL model can reduce the X wirelength. In particular, our results reveal the effectiveness of the X architecture on wirelength reduction during placement and thus the importance of the study on the Xplacement algorithms, which is different from the results given in the previous work that the X-architecture placement might not improve the X-routing wirelength over the Manhattan-architecture placement.

In addition to wirelength, modern placers need to consider various constraints such as preplaced blocks and density. We propose a high-quality analytical placement algorithm considering wirelength, preplaced blocks, and density based on the log-sum-exp wirelength model proposed by Naylor et al. [20] and the multilevel framework. To handle preplaced blocks, we use a two-stage smoothing technique, Gaussian smoothing followed by level smoothing, to facilitate block spreading during global placement. The density is controlled by white-space re-allocation using partitioning and cut-line shifting during global placement and cell sliding during detailed placement. We further use the conjugate gradient method with dynamic step-size control to speed up the global placement and macro shifting to and better macro positions. Experimental results show that our placer obtains the best published results.

In this paper, we present a hybrid placer, called NTUplace2, which integrates both the partitioning and the analytical (quadratic programming) placement techniques for large-scale mixed-size designs. Unlike most existing placers that minimize wirelength alone, we also control the cell density to optimize routability while minimizing the total wirelength. NTUplace2 consists of three major stages: multilevel global placement, legalization, and detailed placement. To handle mixed-size designs, in particular, we present a linear programming based legalization algorithm to remove overlaps between macros during global placement. Various other techniques are integrated to improve the solution quality at every stage.

Unlike classical floorplanning that usually handles only block packing to minimize silicon area, modern very large scale integration (VLSI) floorplanning typically needs to pack blocks within a fixed die (outline), and additionally considers the packing with block positions and interconnect constraints. Floorplanning with bus planning is one of the most challenging modern floorplanning problems because it needs to consider the constraints with interconnect and block positions simultaneously. In this paper, the authors study two types of modern floorplanning problems: 1) fixed-outline floorplanning and 2) bus-driven floorplanning (BDF). This floorplanner uses B/sup */-tree floorplan representation based on fast three-stage simulated annealing (SA) scheme called Fast-SA. For fixed-outline floorplanning, the authors present an adaptive Fast-SA that can dynamically change the weights in the cost function to optimize the wirelength under the outline constraint. Experimental results show that this floorplanner can achieve 100% success rates efficiently for fixed-outline floorplanning with various aspect ratios. For the BDF, the authors explore the feasibility conditions of the B/sup */-tree with the bus constraints, and develop a BDF algorithm based on the conditions and Fast-SA. Experimental results show that this floorplanner obtains much smaller dead space for the floorplanning with hard/soft macro blocks, compared with the most recent work. In particular, this floorplanner is more efficient than the previous works.

We present in this paper a new algorithm to co-optimize the problems of test scheduling and core wrapper design under power constraints for core-based SoC (System on Chip) designs. The problem of test scheduling is first transformed into a floorplanning problem with a given maximum height (test access mechanism width) constraint. Then, we apply the B*-tree based floorplanning technique to solve the SoC test scheduling problem. Experimental results based on the ITC'02 benchmarks show that our method is very effective and efficient---our method obtains the best results ever reported for SoC test scheduling with power constraint in every efficient running time. Compared with recent works, our method achieves average improvements of 4.7% to 20.1%.

We present in this paper, a new interconnect-driven multilevel floorplanning, called IMF, to handle large-scale building-module designs. Unlike the traditional multilevel framework that adopts the "V-cycle" framework: bottom-up coarsening followed by top-down uncoarsening, in contrast, IMF works in the "/spl Lambda/-cycle" manner: top-down uncoarsening (partitioning) followed by bottom-up coarsening (merging). The top-down partitioning stage iteratively partitions the floorplan region based on mm-cut bipartitioning with exact net-weight modeling to reduce the number of global interconnections and thus the total wirelength. Then, the bottom-up merging stage iteratively applies fixed-outline floorplanning using simulated annealing for all regions and merges two neighboring regions recursively. We also propose an accelerative fixed-outline floorplanning (AFF) to speed up wirelength minimization under the outline constraint. Experimental results show that IMF consistently obtains the best floorplanning results with the smallest wirelength for large-scale building-module designs, compared with all publicly available floorplanners. In particular, IMF scales very well as the circuit size increases. The /spl Lambda/-cycle multilevel framework outperforms the V-cycle one in the optimization of global circuit effects, such as interconnection and crosstalk optimization, since the /spl Lambda/-cycle framework considers the global configuration first and then processes down to local ones level by level and thus the global effects can be handled at earlier stages. The /spl Lambda/-cycle multilevel framework is general and thus can be readily applied to other problems.

Unlike classical floorplanning that usually handles only block packing to minimize silicon area, modern VLSI floorplanning typically needs to pack blocks within a fixed die (outline) and additionally considers the packing with block positions and interconnect constraints. Floorplanning with bus planning is one of the most challenging modern floorplanning problems because it needs to consider the constraints with interconnect and block positions simultaneously. We study in this paper two types of modern floorplanning problems: (1) fixed-outline floorplanning and (2) bus-driven floorplanning. Our floorplanner uses the B*-tree floorplan representation and is based on a fast three-stage simulated annealing scheme, called Fast-SA. For fixed-outline floorplanning, we present an adaptive Fast-SA that can dynamically change

In this paper, we present a hierarchical ratio partitioning based placement algorithm for large-scale mixed-size designs. The placement algorithm consists of three steps: global placement, legalization,and detailed placement; it works in a hierarchical manner and integrates net-weighting partitioning, whitespace management, look-ahead bipartitioning, and fast legalization to handle the large-scale mixed-size placement problems. Unlike the traditional partitioning-based technique that is based on balanced partitioning, we apply ratio partitioning in each level. Further, applying the look-ahead bipartitioning technique in each level, we can evaluate the feasibility of the placement for sub-partitions more accurately. Therefore, we can find better ratios for the partitions, leading to easier legalization for the global placement result and finally a better detailed placement solution. Experimental results show the efficiency and effectiveness of our algorithm.