Macro placement is a critical step in 3D integrated circuit (IC) designs due to the challenges posed by the large size of macros and the presence of obstacles in certain areas. Previous research in 3D placement often simplifies macro validation based on prototyping outcomes. However, this approach may result in macros being placed far from their intended locations, leading to longer wire lengths and increased Through-Silicon Vias (TSVs). To tackle these challenges, this paper introduces a novel approach called K-tier Partially Occupied Corner Stitching (K-POCS). This method aims to determine optimal and permissible 2D positions for movable macros on a projection plane early in the design phase, which are then fixed permanently in place. Building on this concept, we propose two distinct design flows for managing 3D macro placement: the Partitioning Last Macro Flow (PL-MF) and the Partitioning First Tier Reassignment (PF-TR). In our experiments, we compare the effectiveness of different macro placement flows. The results consistently demonstrate that the PF-TR approach achieves superior outcomes. This success is attributed to its effective utilization of various placement strategies.

Macro placement plays a critical role in modern designs. Some researchers have applied reinforcement learning (RL) techniques to handle this problem. This paper proposes an effective placer based on the Monte Carlo Tree Search (MCTS) algorithm, guided by a pretrained RL agent. To reduce the complexities of RL and MCTS, we transform the macro placement problem into a macro group allocation problem. Additionally, we propose a new reward function to facilitate training convergence in RL. Moreover, to reduce runtime without affecting placement quality, we use the pretraining result to directly evaluate the placement quality in MCTS. Experiments show that our MCTS-based placer can achieve high-quality results even in the early stages of RL training. Moreover, our method outperforms state-of-the-art placers.

This paper proposes a Hybrid-Region-Aware Multi-Electrostatic System to address various types of region constraints in the placement problem, which is crucial for meeting the demands of modern chip designs with multiple power domains and providing designers with the flexibility needed to achieve performance goals. Previous methods have attempted to build multiple electrostatic systems for different fence region types to manage this issue. However, these approaches fail to handle situations where instances from different fence region types are allowed to be placed within the same region for a specific type of fence region constraint. To overcome these limitations, we propose generating General electrostatic system that eliminates overlaps between instances across isolated electrostatic systems while minimizing disruptions to the placement result. Additionally, instances assigned to a fence region may initially be displaced from their designated placeable regions due to wirelength forces, requiring extra time and effort to reposition them. To address this issue, we develop a resistive force formulation based on a non-Newtonian fluid model and integrate it into the analytical framework to enhance both convergence stability and efficiency. Experimental results demonstrate the efficiency and effectiveness of our approach, achieving an 11-14% reduction in iteration count compared to MORPH and DREAMPlace 3.0 on academic benchmarks, and a 7.8x reduction in runtime compared to Innovus on industrial benchmarks.

Fence region constraints are essential in cell placement, as they can enhance design convergence speed and improve placement quality. This paper introduces a multilevel framework approach to tackle this challenge while maintaining placement quality and reducing complexity. First, the coarsening stage utilizes a fence region aware clustering to avoid inappropriate groupings. Next, recursive quadratic programming is employed to achieve a better initial cell distribution. Previous methods may result in longer wire-length because they typically assign fence objects to their placement regions before distributing cells over a placement region. To mitigate wirelength increases caused by overly restrictive constraints, our refinement stage uses a three-phase approach to gradually adjust the placement regions of fence objects. Additionally, cells are distributed across desired regions using an analytical placement formulation that includes a fence region aware penalty term. Experimental results demonstrate that our methodology achieves improved wirelength and routability while effectively managing fence region constraints.

Since the multilevel framework with the analytical approach has been proven as a promising method to handle the very-large-scale integration (VLSI) placement problem, this paper presents two techniques including a pin-connectivity-aware cluster score function and identification of expected object distribution ranges to further improve the coarsening and refinement stages of this framework. Moreover, we extend the proposed analytical placement method to consider timing in order to speed up design convergence. To optimize timing without increasing wirelength, our approach only increases the weights of timing-critical nets, where the weight of a net is estimated according to the associated timing slack and degree. Besides, we propose a new equation to update net weights based on their historical values to maintain the stability of the net-based timing-driven placement approach. Experimental results demonstrate that the proposed analytical placement approach with new techniques can actually improve wirelength of the classic approach. Moreover, our TDP can get much better WNS and TNS than the previous timing-driven placers such as DREAMPlace4.0 and Differentiable TDP.

This paper proposes a hybrid 3D placement approach which can reduce the number of TSVs while getting short wirelength. Although existing 3D analytical placement approaches can get short wirelength, they usually use a large number of TSVs. Moreover, because cells may be allocated to two tiers by their analytical placement formulations, placement utilization cannot be calculated precisely which may increase the difficulty in cell legalization. To get a less number of TSVs, our approach first allocates cells to tiers by a partitioning algorithm and maintains the result in the following stages. More importantly, we propose a novel 2D-2-3D analytical placement approach according to the space transformation technique. This approach can spread cells over 3D space while optimizing 3D wirelength by a 2D analytical placement formulation. Moreover, placement utilization can be calculated accurately in this approach since cells and TSVs are spread over a 2D plane instead of a 3D space. Experimental results show that our approach can obtain short wirelength and significantly fewer TSVs than previous works.

As the challenge of advanced process in ICs increases, system in package (SiP for short) has played a more important role in the semiconductor industry. SiP has several advantages such as heterogeneous integration, lower manufacturing and development cost, and better reliability of preventing mechanical stress. In order to obtain high quality SiP, component placement is the most important stage in an SiP design, and its result not only determines wirelength but also has a great impact on routability. Hence, this paper proposes the first placement algorithm to consider routabiltiy by the analytical formulation for SiP. Furthermore, to obtain the accurate orientations of components, we propose two models by the softmax function to estimate wirelength and density precisely. However, in order to consider the 135 degree routing nets, we also propose a new model to estimate routing overflow to reduce routing congestion by our analytical placement. Experimental results show that our SiP placement algorithm with the proposed models can obtain better results than other works.

As the complexity increases, power delivery network (PDN) optimization becomes a more important step in a modern design. In order to construct a robust PDN, most classic PDN optimization methods focus on adjusting the dimensions of power stripes. However, this approach becomes infeasible when voltage violation regions also have severe routing congestion. Hence, this paper proposes a delicate procedure to insert additional power stripes to reduce voltage violation while maintaining routability. In the beginning, IR-drop high related regions are identified to reveal those locations which are thirsty for more currents. Then, we solve a minimum-cost flow problem to find the topologies of power delivery paths (PDPs) from power sources to these regions and determine the widths of edges in each PDP so that enough currents can be provided to these regions. Moreover, vertical power stripes (VPSs for short) are inserted to the locations which have less routing congestion and severe voltage violations by the dynamic programming to reduce a probability to deteriorate routability. Finally, more wires will be inserted to IR-drop high related regions if there still exist voltage violations. Experimental results show that our method can use much less routing resource and induce less routing congestion to meet IR-drop constraint in industry designs.

Due to better performance and lower manufacturing cost, system in package (SiP) has attracted more attention in recent years. Fixed-outline component placement and ball assignment are the most important stages for an SiP design; however, they are still manually performed by experienced engineers nowadays. To speed up runtime and get better quality, this article proposes an efficient and effective two-stage approach to handle them. Our multilevel placement algorithm explores possible distributions of components over a placement region by the branch-and-bound (B&B) partitioning algorithm before they are legalized by the simulated annealing (SA) algorithm. Unlike previous methods which can only handle a limited number of components, our approach can easily get a feasible solution in a fixed-outline for several hundred components. In addition, we propose an iterative approach to assign external nets to solder balls by the graph-based algorithm. To further reduce wirelength and net crossing, a pair-exchange procedure is used to swap used balls with unused balls. The experimental results show that our placement algorithm can get shorter wirelength than IMF and other SA-based algorithm. Moreover, a net crossing number can be greatly reduced by our graph-based ball assignment algorithm than the integer linear programming approach with a little more wirelength.

Quality of a true 3D placement approach greatly relies on the correctness of the models used in its formulation. However, the models used by previous approaches are not precise enough. Moreover, they do not actually place TSVs which makes their approach unable to get accurate wirelength and construct a correct congestion map. Besides, they rarely discuss routability which is the most important issue considered in 2D placement. To resolve this insufficiency, this paper proposes more accurate models to estimate placement utilization and TSV number by the softmax function which can align cells to exact tiers. Moreover, we propose a fast parallel algorithm to update the locations of TSVs when cells are moved during optimization. Finally, we present a novel penalty model to estimate routing overflow of regions covered by cells and inflate cells in congested regions according to this model. Experimental results show that our methodology can obtain better results than previous works.

Although the 3D integrated circuit (IC) placement problem has been studied for many years, few publications devoted to the macro legalization. Due to large sizes of macros, the macro placement problem is harder than cell placement, especially when preplaced macros exist in a multi-tier structure. In order to have a more global view, this paper proposes the partitioning-last macro-first flow to handle 3D placement for mixed-size designs, which performs tier partitioning after placement prototyping and then legalizes macros before cell placement. A novel two-step approach is proposed to handle 3D macro placement. The first step determines locations of macros in a projection plane based on a new representation, named K-tier Partially Occupied Corner Stitching. It not only can keep the prototyping result but also guarantees a legal placement after tier assignment of macros. Next, macros are assigned to respective tiers by Integer Linear Programming (ILP) algorithm. Experimental results show that our design flow can obtain better solutions than other flows especially in the cases with more preplaced macros.

Even though routability is of great concern to a recent global placement algorithm, there still exists a large room to improve it. To make legalization more easier and get a better placement, this article proposes an iterative approach to refine cell locations after global placement, where wirelength and routability are separately optimized in each iteration. It first moves cells to better locations to reduce wirelength. Unlike previous approaches, our approach guarantees that no wirelength will be increased so that the previous optimization result can be better maintained. Moreover, we propose a delicate procedure to move cells according to their gain values to reduce the largest wirelength. Next, the whitespace re-allocation approach is applied to redistribute whitespace over a chip to improve routability without changing relative locations of cells. To ensure that enough space will be allocated to the most routing congestion regions, we propose a sigmoid function to increase routing demands of regions according to their routing overflows and number of pins. The experimental results show that our methodology can obtain shorter wirelength and better routability in industrial designs when compared to other approach.

This article presents an analytical-based placement algorithm to handle dataflow constraint for mixed-size circuits. To quickly obtain a better placement at an early stage, engineers often reference dataflow of a design to determine the relative locations of cells and macros. To achieve this target, this paper presents two methods to make a placement follow this constraint. First, we give larger weights to those nets which connect to datapath-oriented objects in the beginning, and then gradually shrink the values by the modified Gompertz curve according to the status of placement utilization in order to shorten their distances without interfering with object distribution. Second, we define desirable placement regions for each datapath-oriented object and propose a novel sigmoid function to give additional penalties to these objects in the analytical placement formulation if they are not in the regions. The experiment demonstrates that our methodology can obtain better results than the other approach which does not consider dataflow constraint. Not only wirelength but also routability will be improved in the resulting placement. Furthermore, our placer outperforms the RTL-aware dataflow-driven macro placer.

Cell placement remains a big challenge in the modern VLSI design especially in routability. Routing overflow may come from global and local routing congestion in a placement. To target on resolving these problems, this paper proposes two techniques in a global placement algorithm based on an analytical placement formulation and the multilevel framework. To remove global routing congestion, we consider each net as a movable soft module and propose a novel congestion-aware net penalty model so that a net will receive a larger penalty if it covers more routing congested regions. Therefore, our placement formulation can be more easier to move nets away from routing congested regions than other approaches and has less impact on wirelength. In addition, to relieve local congestion, we propose an inflation technique to expand the area of a cluster according to its internal connectivity intensity and routing congestion occupied by the cluster. The experimental results demonstrate that our approaches can get better routability and wirelength compared to other approaches such as NTUplace4h, NTUplace4dr, and RePlAce.

As the power consumption of an electronic equipment varies more severely, the device voltages in a modern design may fluctuate violently as well. Consideration of dynamic IR-drop becomes indispensable to current power network design. Since solving voltage violations according to all power consumption files in all time slots is impractical in reality, this paper applies a clustering based approach to find representative power consumption files and shows that most IR-drop violations can be repaired if we repair the power network according to these files. In order to further reduce runtime, we also propose an efficient and effective power network optimization approach. Compared to the intuitive approach which repairs a power network file by file, our approach alternates between different power consumption files and always repairs the file which has the worst IR-drop violation region that involves more power consumption files in each iteration. Since many violations can be resolved at the same time, this method is much faster than the iterative approach. The experimental results show that the proposed algorithm can not only eliminate voltage violations efficiently but also construct a power network with less routing resource.

High temperature or temperature nonuniformity has become a serious threat to performance and reliability of high-performance integrated circuits (ICs), which makes the thermal effect turn into a nonignorable issue in the circuit design or the physical design. In order to estimate temperature accurately, the locations of modules have to be determined in advance, which makes an efficient and effective thermal-aware floorplanning play a more important role. Hence, this article proposes a differentiable nonlinear placement model that can optimize temperature and minimize wirelength at the same time without needing to construct a congestion map. In addition, to avoid inducing longer wirelength while optimizing temperature, we propose some techniques, such as thermal-aware clustering, shrink of hot modules, or thermal-force modulation in the multilevel framework. The experimental results demonstrate that temperature and wirelength are greatly improved by our method compared to Corblivar. More importantly, our runtime is quite fast and the fixed-outline constraint can also be satisfied.

High temperature or temperature nonuniformity has become a serious threat to performance and reliability of high-performance integrated circuits (ICs). Since the temperature in a 3-D IC is mainly determined by a power distribution across tiers, this article proposes a novel method to allocate modules to tiers while exploring a better power distribution according to the hyperparameter optimization technique. In addition, we integrate the sub-3-D thermal mask into the analytical formulation to interleave high power consumption modules in contiguous tiers during distributing modules over placement regions so that it is possible to insert through-silicon vias (TSVs) around high power modules to further reduce the temperature at a later stage. Since the temperature in a tier will be changed every time the locations of TSVs in its lower tier are moved, we also propose a procedure to update the temperature map before refining locations of TSVs. Experimental results have demonstrated that the proposed methodology can effectively reduce the temperature of a 3-D IC with a slight increase in the wirelength. Moreover, its runtime is quite fast.

This article proposes a novel approach to handle macro placement. Previous works usually apply the simulated annealing (SA) algorithm to handle this problem. However, the SA-based approaches usually have difficulty in handling preplaced macros and require longer runtime. To resolve these problems, we propose a macro placement procedure based on the corner stitching data structure and then apply an efficient and effective simulated evolution algorithm to further refine placement results. In order to relieve local routing congestion, we propose to expand areas of movable macros according to the design hierarchy before applying the macro placement algorithm. Finally, we extend our macro placement methodology to consider dataflow constraint so that dataflow-related macros can be placed at close locations. The experimental results show that our approach obtains a better solution than a previous macro placement algorithm and a tool. Besides, placement quality can be further improved when the dataflow constraint is considered.

The mixed-size placement becomes a great challenge in the modern VLSI design. To handle this problem, the three-stage mixed-size placement methodology is considered as the most suitable approach for a commercial design flow, where the placement prototyping is the most important stage. Since standard cells and macros have to be considered simultaneously in this stage, it is more complicated than the other two stages. To reduce complexity and improve design quality, this paper applies the multilevel framework with a design hierarchy-guided clustering scheme for getting a better coarsening result in order to improve outcome in the following stages. We propose an efficient and effective clustering scheme to group standard cells and macros based on the tree built from their design hierarchies. More importantly, our clustering algorithm considers indirect connectivity between macros which is ignored by previous works. Moreover, we propose a new overlapping bounding box constraint to avoid clustering improper macros which have connections to fixed pins. The experimental results show that wirelength and routability are improved by our methodology.

This paper proposes a novel approach to handle the macro placement problem, which integrates the simulated evolution algorithm and corner stitching data structure. Unlike the simulated annealing based algorithm which has to pack each macro to a contour in its representation, a macro can be placed at any empty region according to the corner stitching. Hence, even when a chip contains several preplaced macros which do not abut to boundaries, it can be easily handled by our approach. Moreover, we further apply an efficient and effective simulated evolution algorithm to refine a placement. To avoid standard cells being placed at a small region or being pushed away from related macros in the cell placement stage, our macro placement method also preserves placement areas for standard cells by expanding macros according to the design hierarchy. The experimental results show that our approach obtains better results than CP-tree and a commercial tool in term of wirelength and routability. More importantly, our methodology can complete a large test case in 6 minutes that CP-tree fails to get a result in one day, and their runtime is 659 times longer than ours even when large test cases are ignored.

This paper introduces a routability-driven macro placement algorithm for mixed-size circuits and pays special attention to the effect of regular placement of macros. Once macros are placed with regularity, powerplanning will become easier and better routability can be obtained. Our methodology consists of two stages. First, placement prototyping stage distributes cells and macros over a placement region while keeping those macros and cells with a strong connection and in similar hierarchies tied together. This is facilitated by clustering macros and cells properly in advance. In the second stage, a deterministic macro legalization algorithm is proposed to arrange macros without deteriorating the result obtained in the previous stage. Although several macro legalization algorithms have been proposed in recent years, most of these works adopt the simulated annealing algorithm which usually takes longer runtime. Moreover, they either cannot handle preplaced macros or require preplaced macros to be abutted to chip boundaries. Unlike these approaches, our method iteratively places a macro by extracting available space for it. Experimental results demonstrate the efficiency and effectiveness of our method according to real industry circuits.

This paper proposes a general floorplanning methodology which can be applied to 3D ICs with an arbitrary bonding style. Some researches have shown that a 3D IC with the hybrid bonding style, which includes face-to-back and face-to-face, may obtain better results than that simply using the face-to-back bonding style. We respectively present an approach to assign modules to tiers for each kind of bonding style. Further, a new utilization function, called cosine-shaped function, is proposed to estimate utilizations of bins required by the analytical-based approach. Our experimental results show the cosine-shaped function can obtain a little better result than the bell-shaped function on IBM benchmarks for 2D floorplanning. We also show that the proposed 3D floorplanning methodology consumes less TSVs and induces shorter wirelength compared to previous work in the hybrid bonding style.

This paper addresses a 3D floorplanning methodology, which considers floorplanning and powerplanning at the same time for Multiple Supply Voltage (MSV) circuits. Physical design becomes more complex for MSV designs since modules with the same power domain have to be placed at close locations in 3D space to facilitate powerplanning and reduce IR-drop, which would deteriorate wirelength. By properly partitioning modules of the same power domain into several voltage islands and increasing overlap area of the voltage islands in contiguous dies, we can reduce routing resource usage without increasing wirelength significantly. Further, unlike previous works, our approach not only can handle a netlist with soft modules and hard modules but also can meet the fixed-outline constraint. The experimental results show that our methodology gets better results than other approach in designs with single voltage domain and is also promising for MSV designs.

Today, secure systems are built by identifying potential vulnerabilities and then adding protections to thwart the associated attacks. Unfortunately, the complexity of today's systems makes it impossible to prove that all attacks are stopped, so clever attackers find a way around even the most carefully designed protections. In this article, we take a sobering look at the state of secure system design, and ask ourselves why the “security arms race” never ends? The answer lies in our inability to develop adequate security verification technologies. We then examine an advanced defensive system in nature – the human immune system – and we discover that it does not remove vulnerabilities, rather it adds offensive measures to protect the body when its vulnerabilities are penetrated We close the article with brief speculation on how the human immune system could inspire more capable secure system designs.

Reliability of a P/G network is one of the most important concerns in a chip design, which makes powerplanning the most critical step in the physical design. Traditional P/G network design mainly focuses on reducing usage of routing resource to satisfy voltage drop and electromigration constraints according to a regular mesh. As the number of macros in a modern design increases, this style may waste more routing resource and make routing congestion more severe in local regions. In order to save routing resource and increase routability, this paper proposes a delicate powerplanning method. First, we propose a row-style power mesh to facilitate connection of pre-placed macros and increase routability of signal nets in the later stage. Besides, an effective power stripe width which can reduce wastage of routing resource and provide stronger supply voltage is found. Moreover, we propose the first work to use the linear programming algorithm to minimize P/G routing area and consider routability at the same time. The experimental results show that routability of a design with many macros can be significantly improved by our row-style power networks.

The paper introduces a routability-driven placement prototyping algorithm for hierarchical mixed-size circuits and pays special attention to regular placement of macros. The three-stage algorithm has become the most popular placement approach for commercial design flows, where placement prototyping plays a critical role in the algorithm because distribution of cells and macros is mainly determined by it. SOC circuits usually contain sets of macros which have identical shapes and are in similar hierarchies. If these macros can be placed regularity, powerplanning will become easier and better routability may be obtained. To consider placement regularity, the paper proposes a physical aware clustering algorithm which is possible to cluster two objects with large area. Experimental results have demonstrated effectiveness of our methodology according to industrial benchmarks tested by a real design low.

Although 3-D floorplanning has been studied widely, routability which is a very important issue in modern integrated circuit (IC) designs is rarely discussed. Floorplanning in 3-D ICs is much difficult than that in 2-D ICs because of large difference in sizes between modules and through silicon vias (TSVs), which are key components in 3-D ICs. And the locations of TSVs have great impact on wirelength and routability in resulting floorplans. Hence, this paper proposes a TSV-aware 3-D floorplanning methodology which can consider wirelength and routability at the same time under the fixed-outline constraint. Unlike most of previous works which completely apply the simulated annealing algorithm, our methodology mainly apply deterministic algorithms to resolve the problem. Thus, our approach is more efficient and flexible than previous works. Experimental results have demonstrated that the proposed methodology can significantly reduce routing congestion in 3-D ICs with a slight increase in wirelength.

A sophisticated SoC chip that incorporates many design modules including 2 ARM-like CPUs, a dynamic voltage and frequency scaling (DVFS) design, a master/slave temperature sensing system, and an on-chip test/debug platform is developed and implemented with TSMC 90 nm technology. Measurement results validate the functions and efficiencies of the whole chip.

Three-dimensional integrated circuits (3D ICs) offer significant improvements over two-dimensional circuits in several aspects. Classic 3D floorplanning algorithm places each module at one single die. However, power consumption and wirelength of a 3D IC may be further reduced if it contains folding modules or stack modules such as stack memory. Hence, this paper proposes a fixed-outline 3D floorplanning algorithm which can simultaneously handle different kinds of modules such as soft modules, hard modules, folding modules, and stack modules. In order to maintain the shape of a 3D module, our algorithm aligns the sub-modules of a folding (or stack) module such that they have identical coordinates in respective dies. Experimental results have demonstrated efficiency and effectiveness of our approach even in large benchmarks such as IBM circuits.

As technology advances, power consumption becomes a big challenge in modern very large-scale integration designs. To resolve this problem, power-gated technology has been widely adopted in circuit designs. Since the turn-on sequence of power switches has a great impact on the rush current, wake-up, and sequence times of a power gating design, this paper proposes a methodology to construct a hybrid routing structure to connect power switches. Our hybrid routing structure can induce less rush current and satisfy timing constraints because a better daisy chain is constructed. To find members of the daisy chain, an integer linear programming algorithm is used to pick up suitable power switches. To determine suitable depth of a daisy chain, we propose a model for a power gating design and induct precise equations to estimate voltage and rush current equations according to the model. All of our experiments are based on industrial designs and measured by vendor tools. The experimental results demonstrate the efficiency and effectiveness of our design methodology.

Successive approximation register (SAR) analog-to-digital converters (ADCs) are widely used in biomedical and portable/wearable electronic systems due to their excellent power efficiency. However, both the design and the optimization of high-performance SAR ADCs are time consuming, even for well-experienced circuit designers. For system designers, it is also hard to quickly evaluate the feasibility of a given specification in a process node. This paper presents a systematic sizing procedure for asynchronous SAR ADCs based on design considerations. A sizing tool based on the proposed design procedure is also implemented, the sizing results of which are highly competitive in comparison with other state-of-the-art manual works. Moreover, the sizing time is relatively short due to the efficient and effective search algorithms employed. In addition to the simulation results, two silicon proofs with different specifications and process nodes are provided to demonstrate the feasibility of this design methodology.

As advances in manufacture technology, leakage current increases dramatically in modern ICs. By turning off supply voltage in a low-power domain with power switches, power gating becomes a useful technique in resolving this problem. Since number and locations of power switches have great impact on chip area and IR-drop, an efficient and effective approach to insert power switches is required for the power gating designs. Unlike previous works using the greedy algorithm to handle this problem, this paper uses a simplified model to approximate required equivalent resistance of power switches in a low-power domain, and then determines number and types of power switches based on the value. In order to reduce impact on preplaced standard cells, we also propose a mathematical approach to find locations with less placement density to place power switches. The proposed methodology was integrated into a real-design flow. Experimental results demonstrate that our approach can insert less number of power switches and still satisfy the IR-drop constraint than other approaches.

Due to advances in manufacture technology, leakage current increases dramatically in modern ICs. Power gating technique is an efficient and effective method to resolve this problem. In order to turn off supply voltage in a low-power domain, it has to insert power switches into designs. However, chip area and IR-drop of circuits are impacted by the number and locations of inserted power switches. Unlike previous works using greedy algorithm to handle this problem, this paper proposes a simple model to approximate the equivalent resistance of power switches in a low-power domain, and uses the binary search method to get the precise value. Based on this value, power switches are allocated by a partition-based approach. Experimental results demonstrate that our approach can insert less number of power switches and still satisfy the IR-drop constraint than other approaches. Moreover, this method is very efficient.

This paper presents a two-stage approach to handle fixed-outline floorplanning for mixed size modules, named F-FM. F-FM combines the advantages of the analytical approach and the slicing tree representation. Thus, it is not only suitable for handling fixed-outline floorplanning but also can be extended to handle other important issues in floorplanning such as routability or thermal effect in addition to wirelength. Recently, low power has become big challenges in very large-scale integration designs, which makes voltage-island driven floorplanning more important than ever. Although the problem has been discussed by previous works, no paper considers signal wirelength, powerplanning, and voltage drop at the same time under the fixed-outline constraint. Thus, this paper extends F-FM to handle this problem and consider these issues by properly dividing modules in a voltage domain into several islands. The experimental results show our approach obtains the best results in these problems.

Power has become a burning issue in modern VLSI design. In modern integrated circuits, the power consumed by clocking gradually takes a dominant part. Given a design, we can reduce its power consumption by replacing some flip-flops with fewer multi-bit flip-flops. However, this procedure may affect the performance of the original circuit. Hence, the flip-flop replacement without timing and placement capacity constraints violation becomes a quite complex problem. To deal with the difficulty efficiently, we have proposed several techniques. First, we perform a co-ordinate transformation to identify those flip-flops that can be merged and their legal regions. Besides, we show how to build a combination table to enumerate possible combinations of flip-flops provided by a library. Finally, we use a hierarchical way to merge flip-flops. Besides power reduction, the objective of minimizing the total wirelength is also considered. The time complexity of our algorithm is Θ(n1.12) less than the empirical complexity of Θ(n2). According to the experimental results, our algorithm significantly reduces clock power by 20-30% and the running time is very short. In the largest test case, which contains 1 700 000 flip-flops, our algorithm only takes about 5 min to replace flip-flops and the power reduction can achieve 21%.

Low power has become a burning issue in modern VLSI design. To deal with this problem, the multiple-supply voltage (MSV) is a technique widely applied to a design to reduce its power consumption. However, there exist several challenges in implementing Multi-Voltage designs, which includes floorplanning, level-shifter placement, and power planning [5]. Among these challenges, placement of level shifters has direct impacts on the chip area, total wirelength, and power planning. Although several works considering MSV driven floorplanning have been proposed, they do not actually place level shifters in their flows, which makes their results unrealistic. Yu et al. [19] first proposed a methodology to place level shifters during floorplanning. But, level shifters are inserted in the whitespace of a chip, which would increase wirelength of long wires and make power planning more difficult. Thus, in this paper, we first propose two ways to allocate regions for level shifters during floorplanning, and then give a two-stage approach to place these level shifters at proper locations. The experimental results reveal that the wirelength is underestimated if we do place level shifters and it can obtain smaller wirelength if we can consider level shifters during floorplanning.

Switched capacitors are commonly used in analog design. The circuit performance based on this technique relies on the accuracy of capacitance ratios, which are affected by random and systematic mismatches. To meet the accuracy requirement, designers can increase the layout area of unit capacitors to reduce random mismatch. Since increasing layout area enlarges the distance between unit capacitors, it induces more gradient errors, which results in larger systematic mismatch. Therefore, the better way for reducing the gradient errors is to carefully determine the locations of unit capacitors in a capacitor array. Moreover, the resulting placement must have high capacitance correlation in order to enhance yield. In this paper, we first explore the attributes of a good capacitor placement, which can reduce gradient errors and increase capacitance correlation. Then, an analytical-based approach is proposed to complete capacitor placement considering these issues. Finally, the results are optimized by arbitrarily swapping two unit capacitors. Compared with the simulated annealing based approach, the proposed method not only achieves better placement results but also gets 34x faster for the largest benchmark capacitor array.

To obtain good layout quality and reliability, placement is a very important stage during the physical design of analog circuits. Many works have been proposed to consider topological constraints for analog placement, and they devote to generate compact placements to minimize area and wirelength. However, a compact placement may induce unwanted routing issues. In order to reduce parasitics and cross-talk effects during the routing phase, wires are preferred not to pass above the active area of analog devices. Therefore, it is required to preserve enough routing spaces between devices for successful routing. Currently, there exists limited works studying routability for analog placement, but none of these works consider that symmetry property must be maintained during placement expansion. In this paper, we present a two-stage routability-driven analog placer based on ASF-B*-tree and HB*-tree representations. To reduce running time, our placement algorithm first generates a compact placement to minimize wirelength and area without considering congestion problem. Then, routing congestion regions are expanded locally to resolve the routability problem. Most importantly, the symmetry property of analog placement is always satisfied during the expansion process. Experimental results show that our analog placer can effectively minimize routing congestion without violating the symmetry property after placement expansion.

Switched capacitors are commonly used in analog circuits to increase the accuracy of analog signal processing and lower power consumption. To take full advantage of switched capacitors, it is very important to achieve accurate capacitance ratios in the layout of the capacitor arrays, which are affected by systematic and random mismatches. A good capacitor placement should have a common-centroid structure with the highest possible degree of dispersion to mitigate mismatches. Several dummy units should be inserted to make the placement shape more square and compact. This paper proposes a simulated-annealing-based approach for mismatch-aware common-centroid placement under the above constraints. A pair-sequence representation is used to record a placement, and a couple of associated operations are developed to find better solutions. The experimental results show that the proposed placements achieve smaller oxide-gradient-induced mismatch and larger overall correlation coefficients (i.e., higher degree of dispersion) than those of previous works.

In this paper, we propose an SKB-tree representation for two modern floorplaning problems: fixed-outline and voltage-island driven floorplanning. Since SKB-tree can dynamically allocate regions for blocks so that all blocks can be placed into a specific outline for each solution, it is a suitable representation for dealing with the fixed-outline constraint. Due to this good property, we also use it to deal with the voltage-island driven floorplanning. Different from previous works, we constrain blocks of the same voltage to be placed into one region to save power routing resource, simplify power planning, and reduce IR Drop. Experimental results show the feasibility of SKB-tree. For the fixed-outline constraint with zero deadspace, SKB-tree achieved significantly better wirelength than A-FP, Parquet 4.0, ZDS, and SAFFOA. SKB-tree can get better results than other fixed-outline driven floorplanners because it only needs to focus on wirelength optimization during simulated annealing. Besides, for voltage island driven floorplanning, SKB-tree also consumes less power and wirelength.

Constructing rectilinear Steiner trees for signal nets is a very important procedure for placement and routing because we can use it to find topologies of nets and measure the design quality. However, in modern VLSI designs, pins are located in multiple routing layers, each routing layer has its own preferred direction, and there exist numerous routing obstacles incurred from IP blocks, power networks, pre-routed nets, etc, which make us need to consider multilayer obstacle-avoiding preferred direction rectilinear Steiner minimal tree (ML-OAPDRSMT) problem. This significantly increases the complexity of the problem, and an efficient and effective algorithm to deal with the problem is desired. In this paper, we propose a very simple and effective approach to deal with ML-OAPDRSMT problem. Unlike previous works usually build a spanning graph and find a spanning tree to deal with this problem, which takes a lot of time, we first determine a connection ordering for all pins, and then iteratively connect every two neighboring pins by a greedy heuristic algorithm. The experimental results show that our method has average 5.78% improvement over and at least five times speed up comparing with their approach.

One of the most important issues during the analog layout phase is to achieve accurate capacitance ratios. However, systematic and random mismatches will affect the accuracy of the capacitance ratios. A common-centroid placement is helpful to reduce the systematic mismatch, but it still needs the property of high dispersion to reduce the random mismatch [10]. To deal with this problem, we propose a simulated annealing [15] based approach to construct a common-centroid placement which exhibits the highest possible degree of dispersion. To facilitate this framework, we first propose the pair-sequence representation to represent a common-centroid placement. Then, we present three operations to perturb the representation, which can increase the degree of dispersion without breaking the common-centroid constraint in the resulting placement. Finally, to enhance the efficiency of our simulated annealing based approach, we propose three techniques to speed up our program. The experimental results show that our placements can simultaneously achieve smaller oxide-gradient-induced mismatch and larger overall correlation coefficients (i.e., higher degree of dispersion) than [10] in all test cases. Besides, our program can run much faster than [10] in larger benchmarks.

Fixed outline floorplanning has recently attracted more attention due to its usefulness in solving real problems in industry. This paper applies two convex optimization methods, named UFO, to solve this problem, which consists of a global distribution stage followed by a local legalization phase. In the first stage, modules are transformed into circles, and a push-pull (PP) model is proposed to uniformly distribute modules over the fixed outline with consideration of their wirelength. Due to the quality of the PP model, we obtain good results after the first stage. Therefore, it is not necessary to consider wirelength in the legalization phase. In order to maintain good results of the first stage, we propose a procedure to extract the geometric relations of the modules from the results of the first stage and store it in constraint graphs. Then, the locations and shapes of the modules are determined by second-order cone programming, which penalizes overlap and obeys the boundary constraints. Finally, we extend the UFO methodology to consider pre-placed modules in a fixed outline. We have implemented two convex functions on MATLAB, and experimental results have demonstrated that UFO clearly outperforms the results reported in the literature on the GSRC and MCNC benchmarks.

In this paper, we apply two convex optimization methods, named UFO, for fixed-outline floorplanning. Our approach consists of two stages which are a global distribution stage and a local legalization stage. In the first stage, we first transform modules into circles and use a pull-push model to distribute modules among a fixed outline under the wirelength consideration. Because good results can be obtained after the first stage, we do not need to consider wirelegnth in the second stage; thus, we can devote to legalize modules. To keep the good results of the first stage, we propose a procedure to extract the geometric relations of modules from a layout and record them by constraint graphs. Then, a quadratic function as well as non-overlap and boundary constraints are formulated to determine the locations and shapes of modules. We have implemented the two convex functions on Matlab, and experimental results have demonstrated that UFO clearly outperforms the results reported in the literature on the GSRC benchmark.

To reduce parasitic mismatches in analog design, we usually care about the property of symmetric placement for symmetry groups, which would form several symmetry islands in a chip. However, routing is greatly affected by placement results. If modules with input or output ports are placed arbitrarily in a symmetry island, the routing wires, which connect these modules with other modules outside the island, may induce unwanted parasitics coupling to signals, and thus circuit performance is deteriorated. This phenomenon can not be identified by a cost function, which only considers placement area and total wire length. Therefore, we would like to introduce the necessity of considering boundary constraint for the modules with input or output ports in symmetry islands. Based on ASF-B* tree [3], we explore the feasible conditions for 1D and 2D symmetry islands to meet this constraint. Further, a procedure is presented to maintain the feasibility for each ASF-B* tree after perturbation. Experimental results show that our approach guarantees the boundary property for the modules with input or output ports in symmetry islands.

In order to handle device matching for analog circuits, some pairs of modules need to be placed symmetrically with respect to a common axis. In this paper, we deal with the module placement with symmetry constraints for analog design using the Transitive Closure Graph-Sequence (TCG-S) representation. Since the geometric relationships of modules are transparent to TCG-S and its induced operations, TCG-S has better flexibility than previous works in dealing with symmetry constraints. We first propose the necessary and sufficient conditions of TCG-S for symmetry modules. Then, we propose a polynomial-time packing algorithm for a TCG-S with symmetry constraints. Experimental results show that the TCG-S based algorithm results in the best area utilization.

In this brief, we introduce the concept of the P*-admissible representation and propose a P*-admissible, transitive closure graph-based representation for general floorplans, called transitive closure graph (TCG), and show its superior properties. TCG combines the advantages of popular representations such as sequence pair, BSG, and B*-tree. Like sequence pair and BSG, but unlike O-tree, B*-tree, and CBL, TCG is P*-admissible. Like B*-tree, but unlike sequence pair, BSG, O-tree, and CBL, TCG does not need to construct additional constraint graphs for the cost evaluation during packing, implying a faster runtime. Further, TCG supports incremental update during operations and keeps the information of boundary modules as well as the shapes and the relative positions of modules in the representation. More importantly, the geometric relation among modules is transparent not only to the TCG representation but also to its operation, facilitating the convergence to a desired solution. All of these properties make TCG an effective and flexible representation for handling the general floorplan/placement design problems with various constraints. Experimental results show the promise of TCG.

In this paper, we extend the concept of the P-admissible floorplan representation to that of the P/sup */-admissible one. A P/sup */-admissible representation can model the most general floorplans. Each of the currently existing P/sup */-admissible representations, sequence pair (SP), bounded-slicing grid, and transitive closure graph (TCG), has its strengths as well as weaknesses. We show the equivalence of the two most promising P/sup */-admissible representations, TCG and SP, and integrate TCG with a packing sequence (part of SP) into a representation, called TCG-S. TCG-S combines the advantages of SP and TCG and at the same time eliminates their disadvantages. With the property of SP, a fast packing scheme is possible. Inherited nice properties from TCG, the geometric relations among modules are transparent to TCG-S (implying faster convergence to a desired solution), placement with position constraints becomes much easier, and incremental update for cost evaluation can be realized. These nice properties make TCG-S a superior representation which exhibits an elegant solution structure to facilitate the search for a desired floorplan/placement. Extensive experiments show that TCG-S results in the best area utilization, wirelength optimization, convergence speed, and stability among existing works and is very flexible in handling placement with special constraints.

Architecture and CAD are closely related issues in FPGA design. Routing architecture design shall optimize routability and facilitate router development; on the other hand, router design shall consider the specific properties of routing architectures to optimize the performance of the router. In this paper, we propose effective and efficient unified matching-based algorithms for array-based FPGA routing and segmentation design. For the segmentation design, we consider the similarity of input routing instances and formulate a net-matching problem to construct the optimal segmentation architecture. For the router design, we present a matching-based timing-driven routing algorithm which can consider a versatile set of routing segments. Experimental results show that our designed segmentations significantly outperform those used in commercially available FPGAs. For example, our designed segmentations achieve, on average, 14.6% and 19.7% improvements in routability, compared with those used in the Lucent Technologies ORCA 2C-series and the Xilinx XC4000E-series FPGAs, respectively.

Floorplanning/placement allocates a set of modules into a chip so that no two modules overlap and some specified objective is optimized. To facilitate floorplanning/placement, we need to develop an efficient and effective representation to model the geometric relationship among modules. In this paper, we present a P-admissible representation, called corner sequence (CS), for nonslicing floorplans. CS consists of two tuples that denote the packing sequence of modules and the corners to which the modules are placed. CS is very effective and simple for implementation. Also, it supports incremental update during packing. In particular, it induces a generic worst case linear-time packing scheme that can also be applied to other representations. Experimental results show that CS achieves very promising results for a set of commonly used MCNC benchmark circuits.

We extend in this paper the concept of the P-admissible floorplan representation to that of the P*-admissible one. A P*-admissible representation can model the most general floorplans. Each of the currently existing P*-admissible representations, SP, BSG, and TCG, has its strengths as well as weaknesses. We show the equivalence of the two most promising P*-admissible representations, TCG and SP, and integrate TCG with a packing sequence (part of SP) into a new representation, called TCG-S. TCG-S combines the advantages of SP and TCG and at the same time eliminates their disadvantages. With the property of SP, faster packing and perturbation schemes are possible. Inherited nice properties from TCG, the geometric relations among modules are transparent to TCG-S (implying faster convergence to a desired solution), placement with position constraints becomes much easier, and incremental update for cost evaluation can be realized. These nice properties make TCG-S a superior representation which exhibits an elegant solution structure to facilitate the search for a desired floorplan/placement. Extensive experiments show that TCG-S results in the best area utilization, wirelength optimization, convergence speed, and stability among existing works and is very flexible in handling placement with special constraints.

Deals with arbitrary convex and concave rectilinear module packing using the transitive closure graph (TCG) representation. The geometric meanings of modules are transparent to TCG and its induced operations, which makes TCG an ideal representation for floor-planning/placement with arbitrary rectilinear modules. We first partition a rectilinear module into a set of submodules and then derive necessary and sufficient conditions of feasible TCG for the submodules. Unlike most previous works that process each submodule individually and thus need post processing to fix deformed rectilinear modules, our algorithm treats a set of submodules as a whole and thus not only can guarantee the feasibility of each perturbed solution but also can eliminate the need of the post processing on deformed modules, implying better solution quality and running time. Experimental results show that our TCG-based algorithm is capable of handling very complex instances; further, it is very efficient and results in better area utilization than previous work.

In this article, we introduce a new placement problem motivated by the Dynamically Reconfigurable FPGA (DRFPGA) architectures. Unlike traditional placement, the problem for DRFPGAs must consider the precedence constraints among logic components. For the placement, we develop an effective metric that can consider wirelength, register requirement, and power consumption simultaneously. With the considerations of the new metric and the precedence constraints, we then present a three-stage scheme of partitioning, initial placement generation, and placement refinement to solve the new placement problem. Experimental results show that our placement scheme with the new metric achieves respective improvements of 17.2, 27.0, and 35.9% in wirelength, the number of registers, and power consumption requirements, compared with the list scheduling method.

In this paper, we deal with arbitrarily shaped rectilinear module placement using the transitive closure graph (TCG) representation. The geometric meanings of modules are transparent to TCG as well as its induced operations, which makes TCG an ideal representation for floorplanning/placement with arbitrary rectilinear modules. We first partition a rectilinear module into a set of submodules and then derive necessary and sufficient conditions of feasible TCG for the submodules. Unlike most previous works that process each submodule individually and thus need to perform post processing to fix deformed rectilinear modules, our algorithm treats a set of submodules as a whole and thus not only can guarantee the feasibility of each perturbed solution but also can eliminate the need for the postprocessing on deformed modules, implying better solution quality and running time. Experimental results show that our TCG-based algorithm is capable of handling very complex instances; further, it is very efficient and results in better area utilization than previous work.

In this paper, we propose a transitive closure graph-based representation for general floorplans, called TCG, and show its superior properties. TCG combines the advantages of popular representations such as sequence pair, BSG, and B*-tree. Like sequence pair and BSG, but unlike O-tree, B*-tree, and CBL, TCG is P-admissible. Like B*-tree, but unlike sequence pair, BSG, O-tree, and CBL, TCG does not need to construct additional constraint graphs for the cost evaluation during packing, implying faster runtime. Further, TCG supports incremental update during operations and keeps the information of boundary modules as well as the shapes and the relative positions of modules in the representation. More importantly, the geometric relation among modules is transparent not only to the TCG representation but also to its operations, facilitating the convergence to a desired solution. All these properties make TCG an effective and flexible representation for handling the general floorplan/placement design problems with various constraints. Experimental results show the promise of TCG.

In this paper, we introduce a new placement problem motivated by the Dynamically Reconfigurable FPGA (DRFPGA) architectures. Unlike traditional placement, the problem for DRFPGAs must consider the precedence constraints among logic components. For the placement, we develop an effective metric that can consider wirelength, register requirement, and power consumption simultaneously. With the considerations of the new metric and the precedence constraints, we then present a three-stage scheme of partitioning, initial placement generation, and placement refinement to solve the new placement problem. Experimental results show that our placement scheme with the new metric achieves respective improvements of 17.2%, 27.0%, and 35.9% in wirelength, the number of registers, and power consumption requirements, compared with the list scheduling method.

Due to the precedence constraints among vertices, the partitioning problem for dynamically reconfigurable FPGAs (DRFPGAs) is different from the traditional one. In this paper, we first derive logic formulations for the precedence constrained partitioning problems, and then transform the formulations into integer linear programs (ILPs). The ILPs can handle the precedence constraints and minimize cut sizes simultaneously. To enhance performance, we also propose a clustering method to reduce the problem size. Experimental results based on the Xilinx DRFPGA architecture show that our approach outperforms the list scheduling, the network flow based, and the probability based methods by respective average improvements of 46.6%, 32.3%, and 21.5% in cut sizes. Our approach is practical and scales well to larger problems; the empirical runtime grows close to linearly in the circuit size. More importantly, our approach is very flexible and can readily extend to the partitioning problems with various objectives and constraints, which makes the ILP formulations superior alternatives to the DRFPGA partitioning problems.

Process technology advances have made multimillion gate field programmable gate arrays (FPGAs) a reality. A key issue that needs to be solved in order for the large-scale FPGAs to realize their full potential lies in the design of their segmentation architectures. Channel segmentation designs have been studied to some degree in much of the literature; the previous methods are based on experimental studies, stochastic models, or analytical analysis. In this paper, we address a new direction for studying segmentation architectures. Our method is based on graph-theoretic formulation. We first formulate a problem of finding the optimal segmentation architecture for two input routing instances and present a polynomial-time optimal algorithm to solve the problem. Based on the solution to the problem, we develop an effective and efficient multi-level matching-based algorithm for general channel segmentation designs. Experimental results show that our method significantly outperforms the previous work. For example, our method achieves average improvements of 18.2% and 8.9% in routability in comparison with other work.

Due to the precedence constraints among vertices, the partitioning problem for time-multiplexed field-programmable gate arrays (TMFPGAs) is different from the traditional one. In this paper, we first derive logic formulations for the precedence-constrained partitioning problems and then transform the formulations into integer linear programs (ILPs). The ILPs can handle the precedence constraints and minimize cut sizes simultaneously. To enhance performance, we also propose a clustering method to reduce the problem size. Experimental results based on the Xilinx TMFPGA architecture show that our approach outperforms the list-scheduling (List), the network-flow-based (FBB-m) (Liu and Wong, 1998), and the probability-based (PAT) (Chao, 1999) methods by respective average improvements of 46.6%, 32.3% and 21.5% in cut sizes. Our approach is practical and scales well to larger problems; the empirical runtime grows close to linearly in the circuit size. More importantly, our approach is very flexible and can readily extend to the partitioning problems with various objectives and constraints, which makes the ILP formulations superior alternatives to the TMFPGA partitioning problems.

Process technology advances will soon make the one-miilion gate FPGA a reality.A key issue that needs to be solved for the large-scale FPGAs to realize their full potential lies in the design of their segmentation architectures [10].Onedimensional segmentation designs have been studied to some degree in much of the literature; most of the previously proposed methods are based on stochastic or analytical analysis.In this paper, we address a new direction for studying segmentation architwtures.Our method is based on graph-theoretic formulation.tire first formulate a net matching problem and present a polynomial-time optimal algorithm to solve the problem.Based on the solution to the problem, we develop an effective and eficient matching-based a!gonthm for FPGA segmentation designs.Eqem.mental results show that our method significantly outperforms previous work. For uample,our method achieves averagw of 18.2% and 8.9% improvements m routability, compared with the work in [lJ] and the most recent work in [7], respectively.More importantly, our approaches are vey flm.ble and can Teadi[y utend to higherorder segmentation designs (e.g., two-or three-dimensional segmentation design, etc), which aTe crucial to the design of large-scale FPGAs.