Timing convergence is paramount for the feasibility of VLSI circuit design, which is highly dependent on timing optimization during VLSI placement. Timing-driven placement usually achieves timing optimization by optimizing the locations of timing-violating cells. These cells are often characterized by timing criticality in global and detailed placement. However, we find that this metric cannot accurately capture the cells whose movement will affect the overall timing results. To bridge this gap, this article proposes a timing sensitivity analysis framework to precisely quantify the impact of physical objects (pins, combinational cells, FFs, and nets) on overall timing. Within this framework, we derive the TNS and WNS sensitivities of pins, combinational cells, FFs, and nets. Moreover, we introduce a total timing sensitivity metric to estimate how much physical objects affect the total timing. To validate its effectiveness, the timing sensitivity analysis framework is utilized to refine the combinational cell movement techniques in Rsyn [ 6 , 7 ]. Moreover, we develop an FF classification and moving scheme based on the timing sensitivity analysis framework, to further enhance timing optimization. Experimental results show that our approach achieves remarkable average improvements in TNS and WNS without compromising total wirelength and routability, compared to the state-of-the-art timing-driven detailed placer.

Routability-driven global placement is a major challenge in modern VLSI physical design, for which mitigating routing congestion is a critical approach. Cell inflation can effectively address local routing congestion and is widely adopted, but with the issue of over-inflating or moving cells back into congested areas. Minimizing the congestion within a net bounding box is effective for alleviating global routing congestion, but the bounding box may be too large and contain congestion not contributed by the net. To address the first issue, we propose a momentum-based cell inflation technique that considers historical inflation ratios for mitigating local routing congestion. Then, we construct a differentiable global congestion function, developed from Poisson’s equation, and introduce virtual standard cells onto two-pin nets to accurately guide net movements for mitigating global routing congestion. Furthermore, to improve pin accessibility, we adjust placement density around power and ground rails according to the routing congestion in global placement. The proposed techniques are integrated into an electrostatic-based global placement framework. Experiments on the ISPD 2015 contest benchmarks show that our framework achieves better routability results, with an average of 40% DRVs reduction and comparable wirelength and via count, compared to the leading routability-driven placer.

Floorplanning is a critical phase in VLSI physical design, focusing on determining block positions while optimizing wirelength under specified area constraints. However, classical analytical-based floorplanners are highly sensitive to the quality of initial solutions and existing learningbased methods often suffer from high computational inefficiency and complexity. In this paper, we propose a customized diffusion model to directly generate high-quality initial floorplans. By leveraging a classical analytical-based floorplanner on top of this initial floorplan, the final floorplanning results are significantly improved. To enhance feature extraction, a heterogeneous graph neural network (HGNN) is developed to explicitly incorporate block-to-block and pin-to-block relationships from the netlist during the diffusion process. Additionally, a novel guidance sampling function is introduced to optimize both wirelength and overlap, effectively reducing the required sampling steps while maintaining competitive initial solutions. Experimental results demonstrate that integrating our proposed diffusion model with an advanced analytical-based floorplanner achieves at least 4.8% reduction in runtime and 3.0% reduction in HPWL compared to the original floorplanner and other diffusion-based methods.

Thermal issues are becoming increasingly critical due to rising power densities in high-performance chip design. The need for fast and precise full-chip thermal analysis is evident. Although machine learning (ML)-based methods have been widely used in thermal simulation, their training time remains a challenge. In this article, we proposed a novel physics-informed separation of variables solver (PISOV) to significantly reduce training time for fast full-chip thermal analysis. Inspired by the recently proposed ThermPINN, we employ a least-square regression method to calculate the unknown coefficients of the cosine series. The proposed PISOV method combines physics-informed neural network (PINN) and separation of variables (SOVs) methods. Due to the matrix-solving method of PISOV, its speed is much faster than that of ThermPINN. On top of PISOV, we parameterize effective convection coefficients and power values for surrogate model-based uncertainty quantification (UQ) analysis by using neural networks, a task that cannot be accomplished by the SOV method. In the parameterized PISOV, we only need to calculate once to obtain all parameterized results of the hyperdimensional partial differential equations. Additionally, we study the impact of sampling methods (such as grid, uniform, Sobol, Latin hypercube sampling (LHS), Halton, and Hammersly) and hybrid sampling methods on the accuracy of PISOV and parameterized PISOV. Numerical results show that PISOV can achieve a speedup of$245\times $, and$10^{4}\times $over ThermPINN, and PINN, respectively. Among different sampling methods, the Hammersley sampling method yields the best accuracy.

The advancement of modern clock tree synthesis (CTS) encounters a bottleneck, primarily due to the difficulty in achieving multiobjective co-optimization among complex design processes. To concurrently optimize skew, latency, and load capacitance, we propose an iterative and hierarchical CTS framework, which is composed of clustering, topology generation and routing, buffering, and optimization. First, we introduce a capacitance-based metric to achieve adaptive balanced clustering and optimize the cluster results through simulated annealing. Second, to construct a clock tree with lower latency, load capacitance, and skew, we introduce the skew-latency-load tree (SLLT), which combines the advantages of bound skew tree and Steiner shallow-light tree, and we propose an effective SLLT construction algorithm. Third, to further optimize CTS result by buffering, we introduce the critical wirelength evaluation (CWE) to evaluate the capability of each buffer, and propose the insertion delay estimation (IDE) to reduce the evaluation bias during buffering, then design the iterative skew convergence algorithm (ISCA) to achieve complete convergence of skew. We validate our solution using 28 nm process technology. Compared to our method, the commercial tool increases skew, latency, and clock capacitance by 39.5%, 13.0%, and 18.5%, respectively, while the OpenROAD by 101.6%, 50.7%, and 25.5%, respectively.

Timing-driven routing is crucial in complex circuit design. Existing shallow-light Steiner tree construction methods balance between wire length (WL) and source-sink path length (PL) but lack in delay. Conversely, previous delay-driven methods prioritize delay but result in longer WL and PL, making them suboptimal. In this article, we show that simultaneously reducing the WL and PL can effectively reduce the delay. Furthermore, we investigate how delay changes during the reduction of PL. Guided by the theoretical findings, we develop a rectilinear shallow-light Steiner tree construction algorithm designed to reduce delay meanwhile maintaining a bounded WL. Furthermore, a delay-driven edge shifting algorithm is proposed to fine tune the tree’s topology, further reducing delay. We show that our proposed edge shifting algorithm can return a local Pareto optimal solution when repeatedly applied. Experimental results show that our algorithm achieves the lowest total delay compared to previous methods while maintaining competitive WL. Moreover, for nets with pins that have timing information, our algorithm can generate the most suitable Steiner Tree based on the timing information. In addition, extended experiments highlight the positive impact of constructing rectilinear Steiner trees with minimized total delay. Our codes will be available athttps://github.com/Whx97/Delay-driven-Steiner-Tree.

Taking advantage of the natural grouping structure inside data, group sparse optimization can effectively improve the efficiency and stability of high-dimensional data analysis, and it has wide applications in a variety of fields such as machine learning, signal processing, and bioinformatics. Although there has been a lot of progress, it is still a challenge to construct a group sparse-inducing function with good properties and to identify significant groups. This article aims to address the group-sparsity-constrained minimization problem. We convert the problem to an equivalent weighted $\ell _{p,q}$ -norm ( $p\gt 0$ , $0\lt q\leq 1$ ) constrained optimization model, instead of its relaxation or approximation problem. Then, by applying the proximal gradient method, a solution method with theoretical convergence analysis is developed. Moreover, based on the properties proved in the Lagrangian dual framework, the homotopy technique is employed to cope with the parameter tuning task and to ensure that the output of the proposed homotopy algorithm is an L-stationary point of the original problem. The proposed weighted framework, with the central idea of identifying important groups, is compatible with a wide range of support set identification strategies, which can better meet the needs of different applications and improve the robustness of the model in practice. Both simulated and real data experiments demonstrate the superiority of the proposed method in terms of group feature selection accuracy and computational efficiency. Extensive experimental results in application areas such as compressed sensing, image recognition, and classifier design show that our method has great potential in a wide range of applications. Our codes will be available at https://github.com/jianglanfan/ HIWT-GSC.

This article proposes a novel analytical steady-state thermal simulation framework considering anisotropic thermal conductivity for 3-D integrated circuits (3D-ICs) that combine an adaptive rectangular discretization algorithm with a conformal meshing strategy to achieve enhanced computational efficiency and accuracy. To address the challenges of arbitrary power density distributions in modern 3D-ICs, we develop an adaptive rectangle approximation method that dynamically adjusts rectangular partition sizes based on local gradient analysis and error-controlled discretization criteria. The derived rectangular thermal sources are subsequently processed through a conformal meshing technique that preserves geometric fidelity while minimizing mesh complexity. For analytical solution derivation, we employ the domain decomposition method effectively to divide the multilayer 3-D structure into several individual layers with customized general solutions. Interlayer thermal coupling is resolved through interfacial boundary condition enforcement. Numerical simulations demonstrate that the proposed analytical thermal method achieves significant performance improvements, exhibiting$60\times $acceleration over conventional finite element method (FEM) implementations while maintaining a maximum absolute error (MAX) below 0.5 K across multiple benchmark cases with 3D-ICs.

By leveraging the power of open-source software, the EDA tool offers a cost-effective and flexible solution for designers, researchers, and hobbyists alike. Open-source EDA promotes collaboration, innovation, and knowledge sharing within the EDA community. It emphasizes the role of the toolchain in accelerating the development of electronic systems, reducing design costs, and improving design quality. This paper presents an open-source EDA project, iEDA, aiming to build a basic infrastructure for EDA technology evolution and closing the industrial-academic gap in the EDA area. As the foundation for developing EDA tools and researching EDA algorithms and technologies, iEDA is mainly composed of file system, database, manager, operator and interface. To demonstrate the effectiveness of iEDA, we implement and tape out four chips of different scales (from 700k to 500M gates) on different process nodes (110nm and 28nm) with iEDA. iEDA is publicly available on the project home page https://github.com/OSCC-Project/iEDA.

In VLSI, a large number of vias may reduce manufacturability, degrade circuit performance, and increase layout area required for interconnection. In this paper, we propose a 3D global router V-GR, which considers minimizing the number of vias. V-GR uses a modified via-aware routing cost that considers the impact of wire density on the via. This cost function is more sensitive to the number of vias. Meanwhile, a novel multi-strategy rip-up & rerouting framework is developed for V-GR to solve the overflowed net, effectively optimizing wire length, overflow, and minimizing the number of vias. The proposed framework first leverages two proprietary routing techniques, namely the 3D monotonic routing and 3D 3-via-stack routing, to control the number of vias and reduce overflow. Additionally, the framework incorporates an RSMT-aware expanded source 3D maze routing algorithm to build routing paths with shorter wire length. Experimental results on the ICCAD’19 contest benchmarks show that, V-GR achieves high-quality results, reducing vias by 8% and overflow by 7.5% in the global routing phase. Moreover, to achieve a fair comparison, TritonRoute is used to conduct detailed routing, and Innovus is used to evaluate the final solution. Comparison shows that V-GR achieves 4.7% reduction in vias and 8.7% reduction in DRV, while maintaining almost the same wire length.

Clock tree synthesis (CTS) constructs an efficient clock tree, meeting design constraints and minimizing resource usage. It serves as a bridge between placement and routing, facilitating concurrent optimization of multiple design objectives. To construct a clock tree with lower latency and load capacitance while maintaining a specified skew constraint, we introduce skew-latency-load tree (SLLT) which combines the merits of bound skew tree and Steiner shallow-light tree, along with an analysis and demonstration of the boundaries of these two tree types. We propose a method for constructing SLLT, which significantly reduces both the maximum latency and load capacitance compared to previous methods while ensuring skew control. Combining this routing topology generation method, we introduce a hierarchical CTS framework, and it is constructed by integrating partition schemes and buffering optimization techniques. We validate our solution at 28nm process technology, demonstrating superior performance compared to the solutions of OpenROAD and advanced commercial tool. Our approach outperforms in all metrics (max latency, skew, buffer number, clock capacitance), achieving a significant reduction in latency of 29.45% compared to OpenROAD and 6.75% compared to the commercial tool.

With the advancement of semiconductor technologies, the acceleration of advanced EDA algorithms is receiving much attention. However, developing a faster mixed-size placer without hardware acceleration and loss of solution quality is of great challenge. In this article, we propose a novel definition of potential energy for each block for global placement based on an analytical solution of Poisson’s equation. A fast approximate computation scheme for partial derivatives of the potential energy is given with considerably less computational loads than existing electrostatics-based placers. Moreover, we propose an effective and efficient occupy-aware macro legalization algorithm. Then, a mixed-size placer named Pplace-MS is developed. Compared to the existing leading mixed-size placer, Pplace-MS on average achieves$2.054\times $speedup in single-threaded mode on the same machine and 2.3% reduction of scaled half-perimeter wirelength on the modern mixed-size placement benchmarks. The proposed approach can also be considered accelerated on GPU, as previous works.

Global routing is a critical step in VLSI physical design. This paper proposes a novel pathfinding model based on integer linear programming for VLSI global routing. The Lagrangian relaxation method combined with a direction-aware weighted A*-algorithm is developed to quickly solve the model to obtain a better initial routing solution, which is further optimized by a designed multi-stage rip-up & rerouting algorithm. In each stage of rip-up & rerouting, different routing algorithms and cost functions are used to optimize the overflow and wire length. SPRoute and CUGR are two state-of-the-art global routers. Our proposed global routing algorithm outperforms SPRoute 1.0 & 2.0 in both the wire length and the number of vias on the ISPD08 benchmarks. On the ISPD18 benchmarks, compared to CUGR, our algorithm has about 5.1% reduction in the number of vias, and the average runtime is 4.89× speedup; compared to SPRoute 2.0, our algorithm has about 1.7% reduction on the average wire length, and the number of vias is comparable.

In this paper, we present an improved electrostatics-based analytical method for fixed-outline floorplanning, which incorporates module rotation and sizing driven by wirelength. To accurately compute the density function after module rotation, we propose a novel density calculation algorithm based on line drawing and polygon clipping algorithms commonly used in computer graphics. By using this algorithm, we are able to accurately compute the density function after module rotation without adding any complexity. Moreover, we propose a module legalization algorithm by adding module sizing and module rotation after the existing constraint graph adjustment step. Furthermore, we adopt a linear programming to minimize wirelength to improve the quality of the results. Experimental results demonstrate that our floorplanning algorithm achieves at least 5.9% and 11% reduction in half-perimeter wirelength on the HB+ and ami49_x benchmarks, respectively, compared to state-of-the-art floorplanners.

The paper proposes SMuLe, a secure mutual learning protocol for two-party deep model training, to support low demand for interaction complexity and communication overhead. The strategy is that two parties exchange their blind predictions securely on each other's dataset and the underlying models can thereby benefit from not only the true label of the data but the prediction of the other party, as being different from federated learning and prior art that counts on secure multi-party computation. After this protocol, each participant occupies a well trained plaintext model privately. The contributions include the following: (i) the communication cost of SMuLe is lower than state-of-the-art two-party training protocols; (ii) our solution is flexible with different secure inference schemes; (iii) SMuLe can resist malicious attacks through poisoning samples. The experiments show that on CifarlO, SMuLe can obtain desirable accuracy even in a small convnet and the communication cost in each epoch is less than 75 MB as expected.

Floorplanning is the first stage of VLSI physical design. An effective floorplanning engine definitely has a positive impact on chip design speed, quality, and performance. In this article, we present a novel mathematical model to characterize nonoverlapping of modules, and propose a flat fixed-outline floorplanning algorithm based on the VLSI global placement approach using Poisson’s equation. The algorithm consists of global floorplanning and legalization phases. In global floorplanning, we redefine the potential energy of each module based on the novel mathematical model for characterizing nonoverlapping of modules and an analytical solution of Poisson’s equation. In this scheme, the widths of soft modules appear as variables in the energy function and can be optimized. Moreover, we design a fast approximate computation scheme for partial derivatives of the potential energy. In legalization, based on the defined horizontal and vertical constraint graphs, we eliminate overlaps between modules remained after global floorplanning, by modifying relative positions of modules. Experiments on the MCNC, GSRC, HB+, and ami49_x benchmarks show that, our algorithm improves the average wirelength by at least 2% and 5% on small and large-scale benchmarks with certain whitespace, respectively, compared to state-of-the-art floorplanners.

As design complexity keeps increasing, the 2.5D field-programmable gate array (FPGA) with large logic capacity has become popular in modern circuit applications. A 2.5D FPGA consists of multiple dies connected through super long lines (SLLs) on an interposer. Each die contains heterogeneous logic blocks and ASIC-like clocking architectures to achieve better skew and timing. Existing works consider these problems separately and thus may lead to serious timing issues or routing failure. This article presents an analytical placement algorithm for the 2.5D FPGA to simultaneously minimize the number of inter-die SLL signals and intra-die clocking violations. Using a lifting dimension technique, we first formulate the 2.5D global placement problem as a three-dimensional continuous and differential minimization problem, where the SLL-aware block distribution is modeled by 3D Poisson’s equation and directly solved to obtain an analytical solution. Then, we further reformulate the minimization problem as a separable optimization problem with linear constraints. Based on the proximal alternating direction method of multipliers optimization method, we efficiently optimize the separable subproblems one by one in an alternating fashion. Finally, clock-aware legalization and detailed placement are applied to legalize and improve our placement results. Compared with the state-of-the-art works, experimental results show that our algorithm can resolve all clocking constraints and reduce the number of SLL crossing signals by 36.9% with similar wirelength in a comparable running time.

Metal fill insertion has become an essential step in reducing dielectric thickness variation and improving pattern uniformity, which is important in mitigating process variations, thereby achieving better manufacturing yield. However, metal fills could induce coupling capacitance, which is not often considered in existing works that typically focus more on pattern density uniformity, incurring significant problems in timing closure. However, it is a great challenge to consider three types of capacitances (i.e., area, fringe, and lateral capacitances) with design rules and density constraints at the fill insertion stage simultaneously. This article presents an efficient timing-aware fill insertion algorithm for minimizing the total capacitance and fill amount, considering the density constraints. First, we present an initial metal fill insertion and design-rule-aware legalization to obtain an initial fill insertion solution quickly. Second, from critical conductors to powers/grounds in a circuit, we divide conductors into different equivalent paths and then construct a capacitance graph to reduce the capacitance of each equivalent path globally. Third, we propose a density-aware coupling capacitance optimization method and a fast Monte Carlo-based fill selection to further reduce the coupling capacitance between any pair of conductors. Finally, we present a density-aware fill deletion method to reduce the fill amount. We evaluate the performance of our algorithm on the benchmarks of the 2018 CAD Contest at ICCAD and its official contest evaluator. Compared with the first-place team of the contest and the state-of-the-artwork, experimental results show that our algorithm achieves the lowest total capacitance and the least fill amount in a comparable runtime.

Fogging and proximity effects (FPEs) are two major factors that cause inaccurate exposure and layout pattern distortions in e-beam lithography. In this article, we propose an analytical placement algorithm that considers both FPEs. We formulate the global placement problem as a separable minimization problem with linear constraints, where different objectives can be tackled one by one in an alternating fashion. Then, we propose a novel proximal group alternating direction method of multipliers (ADMM) to solve the separable minimization problem with two subproblems, where the first subproblem (associated with wirelength and density) is solved by the steepest descent method without line search, and the second one (associated with the FPEs) is handled by an analytical scheme. We prove the property of global convergence of the proximal group ADMM method. Finally, the FPEs-aware legalization and detailed placement are employed to legalize and improve the placement result. The experimental results show that our algorithm is effective and efficient for the addressed problem. Our algorithm achieved 5.7% smaller fogging variation, 6.8% lower proximity variation, and 5.4% lower runtime with a minor wirelength overhead compared with the state-of-the-art work.

Mixed-cell-height standard cells are prevailingly used in advanced technologies to achieve better design tradeoffs among timing, power, and routability. As feature size decreases, the placement of cells with multiple threshold voltages may violate the complex minimum-implant-area (MIA) layer rule arising from the limitations of patterning technologies. Existing works consider the mixed-cell-height placement problem only during legalization or handle the MIA constraints during detailed placement. In this article, we address the mixed-cell-height placement problem with MIA constraints in two major stages: 1) post-global placement (Post-GP) and 2) MIA-aware legalization. In the Post-GP stage, we first present a continuous and differentiable cost function to address the Vdd/Vss alignment constraints and add weighted pseudonets to MIA-violation cells dynamically. Then, we propose a proximal optimization method based on the given global placement result to simultaneously consider Vdd/Vss alignment constraints, MIA constraints, cell distribution, cell displacement, and total wirelength. In the MIA-aware legalization stage, we develop a graph-based method to cluster cells of specific threshold voltages and apply a strip-packing-based binary linear programming to reshape cells. Then, we propose a matching-based technique to resolve intrarow MIA violations and reduce filler insertion. Furthermore, we formulate inter-row MIA-aware legalization as a quadratic programming problem, which is efficiently solved by a modulus-based matrix splitting iteration method. Finally, MIA-aware cell allocation and refinement are performed to further improve the result. Experimental results show that without any extra area overhead, our algorithm still can achieve 5.4% shorter final total wirelength than the state-of-the-art work.

The data imbalance problem often occurs in nanometer VLSI applications, where normal cases far outnumber error ones. Many imbalanced data handling methods have been proposed, such as oversampling minority class samples and downsampling majority class samples. However, existing methods focus on improving the quality of minority classes while causing quality deterioration of majority ones. In this paper, we propose a two-stage classifier to handle the data imbalance problem. We first develop an iterative neural network framework to reduce false alarms. Then the oversampling method on a final classification network is applied to predict the two classes better. As a result, the data imbalance problem is well handled, and the quality deterioration of majority classes is also reduced. Since the iterative stage does not change any existing network structure, any convolutional neural network can be used in the framework. Compared with the state-of-the-art imbalanced data handling methods, experimental results on the hotspot detection problem show that our two-stage classification method achieves the best prediction accuracy and reduces false alarms significantly.

This article proposes a novel iterative weighted group thresholding method for group sparse recovery of signals from underdetermined linear systems. Based on an equivalent weighted group minimization problem with ℓpp-norm (0 <; p ≤ 1), we derive closed-form solutions for a subproblem with respect to some specific values of p when using the proximal gradient method. Then, we design the corresponding algorithmic framework, including stopping criterion and the method of nonmonotone line search, and prove that the solution sequence generated by the proposed algorithm converges under some mild conditions. Moreover, based on the proposed algorithm, we develop a homotopy algorithm with an adaptively updated group threshold. Extensive computational experiments on the simulated and real data show that our approach is competitive with state-of-the-art methods in terms of exact group selection, estimation accuracy, and computation time.

Modern circuits often contain standard cells of different row heights to meet various design requirements. Taller cells give larger drive strengths and higher speed at the cost of larger areas and power. Multi-row height standard cells incur challenging issues for layout designs, especially the mixed-cell-height legalization problem with heterogeneous cell structures. Honoring the good cell positions from global placement, we present in this article a robust modulus-based matrix splitting iteration method (RMMSIM) to solve the mixed-cell-height legalization problem. Fixing the cell ordering from global placement and relaxing the right-boundary constraints, our proposed method first converts the problem into an equivalent linear complementarity problem (LCP), and then properly splits the matrices in the LCP so that the RMMSIM can solve the LCP optimally. The RMMSIM effectively explores the sparse characteristic of a circuit, and takes only linear time per iteration; as a result, it can solve the QP very efficiently. Finally, an allocation scheme for illegal cells is used to align such cells to placement sites on rows and fix the placement of out-of-right-boundary cells, if any. Experimental results show the effectiveness and efficiency of our proposed algorithm. In addition, the RMMSIM convergence and optimality are theoretically proved and empirically validated. In particular, this article provides a new RMMSIM formulation for various optimization problems that require solving large-scale convex quadratic programming problems efficiently.

With the increasing design requirements of modern circuits, a standard-cell library often contains cells of different row heights to address various trade-offs among performance, power, and area. However, maintaining all standard cells with integer multiples of a single-row height could cause some area overheads and increase power consumption. In this paper, we present an analytical placer to directly consider a circuit design with non-integer multiple-height standard cells and additional layout constraints. The region of different cell heights is adaptively generated by the global placement result. In particular, an exact penalty iterative shrinkage and thresholding (EPIST) algorithm is employed to efficiently optimize the global placement problem. The convergence of the algorithm is proved, and the acceleration strategy is proposed to improve the performance of our algorithm. Compared with the state-of-the-art works, experimental results based on the 2017 CAD Contest at ICCAD benchmarks show that our algorithm achieves the best wirelength and area for every benchmark. In particular, our proposed EPIST algorithm provides a new direction for effectively solving large-scale nonlinear optimization problems with non-smooth terms, which are often seen in real-world applications.

In modern circuit designs, standard cells are designed with different heights based on the power, area, and other characteristics to address various design requirements. For those cells with different heights, in particular, there are inter-cell diffusion steps if the diffusion heights of neighboring cells are different, called the neighbor diffusion effect (NDE) which has become critical in advanced technology nodes. In this paper, we present a Hamiltonian-path-based mixed-cell-height legalization algorithm for NDE mitigation. We first present a row assignment method considering both cell displacements and diffusion steps to assign cells to their desired rows that meet the power-rail alignment constraints. Then, we propose a Hamiltonian-path-based diffusion-step reduction method to effectively reduce the NDE violations while preserving the global placement solution. Particularly, we develop a 2-approximation algorithm to find a minimum weight Hamiltonian path connecting two vertices, and a 1.5-approximation algorithm to find a minimum weight Hamiltonian path with a specified end vertex. Finally, we present an NDE-aware legalization method with design compaction to resolve overlaps and NDE violations. Experimental results show that our algorithm can resolve all NDE violations without any area overhead in reasonable runtime.

We are indebted to Spink and Tiba Spink and Tiba [3] for pointing out that the key technical lemma (Lemma 4) is incorrect in our paper [2]. We tried to make a revision for fixing the gap. However, with the help of mathematical software Lingo, we found that our lemma has counterexamples and its conclusion is incorrect. The Bollobás--Scott conjecture Spink and Tiba [3], “Every $r$-uniform hypergraph with $m$ edges has a vertex partition into $k$ sets with at most $m/k^r+o(m)$ edges in each set,” remains open for $r\ge4$ and seems difficult. The following result shows that Lemma 4 in [2] is wrong even in the case $k=2$.

The sparse representation-based classifier (SRC) has been developed and verified as having great potential for real-world face recognition. In this paper, we propose a discriminative projection and representation-based classification (DPRC) method to enhance the discriminant ability of the SRC. The proposed method first obtains a discriminative projection matrix not only maximizing the ratio of the distance within interclass over the distance within intraclass, but also minimizing the linear approximation error within intraclass. Then it maps the original data onto the discriminative space, and adopts an SRC method to obtain the final solution. An inexact augmented Lagrangian method of multiplier is proposed for finding the optimal representation vector in our framework, and a proximal alternating minimization method is adopted to the iteration subproblems of the proposed method. The proposed method is proven to have the subsequence convergence property. Experimental results on Yale, ORL, and AR face image databases demonstrate that, compared with some existing feature extraction methods based on the SRC, the proposed DPRC method is more efficient.

Mixed-cell-height circuits have become popular in advanced technologies for better power, area, routability, and performance tradeoffs. With technology and region constraints imposed by modern circuit designs, the mixed-cell-height legalization problem has become even more challenging. Additionally, an ideal legalization method should minimize both the average and maximum cell movements to preserve the quality of a given placement as much as possible. In this article, we present an effective and efficient mixed-cell-height legalization algorithm to consider technology and region constraints while minimizing the average and maximum cell movements. We first present a fence region handling technique to unify the fence regions and the default region. To obtain a desired cell assignment, we then propose a movement-aware cell reassignment method by iteratively reassigning cells in locally dense areas to their desired rows. After cell reassignment, a technology-aware legalization is presented to remove cell overlaps while satisfying the technology constraints. Finally, we propose a technology-aware refinement to further reduce the average and maximum cell movements without increasing the technology constraints violations. Compared with the champion of the 2017 CAD Contest at ICCAD and the state-of-the-art work, experimental results based on the 2017 CAD Contest at ICCAD benchmarks show that our algorithm achieves the best average and maximum cell movements and significantly fewer technology constraint violations, in a comparable runtime. The experimental results based on the modified 2015 ISPD Contest benchmarks also demonstrate the effectiveness of our algorithm in minimizing the average and maximum cell movements, compared with state-of-the-art mixed-cell-height legalizers.

As an emerging manufacture technology, block copolymer directed self-assembly (DSA) is promising for via layer fabrication. Meanwhile, redundant via insertion is considered as an essential step for yield improvement. For better reliability and manufacturability, in this paper, we concurrently consider DSA guiding template assignment with redundant via and dummy via insertion at post-routing stage. Firstly, by analyzing the structure property of guiding templates, we propose a building-block based solution expression to discard redundant solutions. Then, honoring the compact solution expression, we construct a conflict graph with dummy via insertion, and then formulate the problem to an integer linear programming (ILP). To make a good trade-off between solution quality and runtime, we relax the ILP to an unconstrained nonlinear programming (UNP). Finally, a line search optimization algorithm is proposed to solve the UNP. Experimental results verify the effectiveness of our new solution expression and the efficiency of our proposed algorithm.

As the design complexity keep increasing, the 2.5D FPGA with large logic capacity has become popular in modern circuit applications. A 2.5D FPGA consists of multiple dies connected through super long lines (SLLs) on an interposer, where each die contains heterogeneous logic blocks and ASIC-like clocking architectures to achieve better skew and timing. To address the crucial SLL issue and the special clocking architecture, this paper presents the first analytical placement algorithm for the 2.5D FPGA with the objective of minimizing the numbers of inter-die SLL signals and intra-die clocking violations simultaneously. Using a lifting dimension technique, we first formulate the 2.5D global placement problem as a three-dimensional continuous and differential minimization problem, where the SLL-aware block distribution is modeled by 3D Poisson's equation and directly solved to obtain an analytical solution. Then, we further reformulate the minimization problem as a separable optimization problem with linear constraints. Based on the proximal alternating direction method of multipliers (ADMM) optimization method, we efficiently optimize the separable subproblems one by one in an alternating fashion. Finally, clock-aware legalization and detailed placement are applied to legalize and further improve our placement results. Compared with the state-of-the-art work, experimental results show that our algorithm can resolve all clocking constraints and reduce the number of SLL crossing signals by 36.9% with similar wirelength in comparable running time.

Metal fill insertion has become an essential step to reduce dielectric thickness variation and improve pattern uniformity, which is important in mitigating process variations, thereby achieving better manufacturing yield. However, metal fills could induce coupling capacitance, which is not often considered in existing works that typically focus more on pattern density uniformity, incurring significant problems in timing closure. In this paper, we address the timing-aware fill insertion problem that considers the total capacitance and density constraints simultaneously. First, initial metal fill insertion and design-rule-aware legalization are used to quickly obtain an initial fill insertion solution. Second, from critical conductors to powers/grounds in a circuit, we divide conductors into different equivalent paths and then construct a capacitance graph to globally reduce the capacitance of each equivalent path. Third, we present a density-aware coupling capacitance optimization method and a fast Monte Carlo based fill selection to further reduce the coupling capacitance between any pair of conductors. Finally, we present a density-aware fill deletion method to reduce the fill amounts. We evaluate the performance of our algorithm based on the benchmarks of the 2018 CAD Contest at ICCAD and its official contest evaluator. Compared with the first place team of the contest and the state-of-the-art work, experimental results show that our algorithm achieves the lowest total capacitance and the least fill amount for each benchmark.

Modern circuit designs often contain standard cells of different row heights to meet various design requirements. Due to the higher interference among heterogeneous cell structures, the legalization problem for mixed-cell-height standard cells becomes more challenging. In this paper, we present an analytical legalization algorithm for mixed-cell-height standard cells to simultaneously minimize the average and the maximum cell movements. We formulate it as a mixed integer quadratic programming problem (MIQP), which allows cell spreading concurrently in both the horizontal and vertical directions. By relaxing its discrete constraints to linear ones, we convert the MIQP into a quadratic programming problem (QP). To solve the QP efficiently, we further reformulate it as a linear complementarity problem (LCP), and solve the LCP by a modulus-based matrix splitting iteration method (MMSIM). To guarantee the convergence of the MMSIM and the equivalence between the QP and the LCP, we use a series of operations to ensure that its induced objective matrix is symmetric positive definite and its constraint matrix is of full row rank. Experimental results demonstrate the effectiveness of our algorithm in reducing both the average and the maximum cell movements for mixed-cell-height legalization.

Global placement dominates the circuit placement process in its solution quality and efficiency. With increasing design complexity and various design constraints, it is desirable to develop an efficient, high-quality global placement algorithm for modern large-scale circuit designs. In this paper, we first analyze the properties of four nonlinear optimization methods (the quadratic penalty method, the Lagrange multiplier method, and two augmented Lagrangian methods) for global placement, and then develop a generalized augmented Lagrangian method to solve this problem. Our proposed method preserves the advantages of the quadratic penalty method and the augmented Lagrangian method, and provides a smooth progress from the quadratic penalty method to the augmented Lagrangian method. We prove that the proposed generalized augmented Lagrangian method is globally convergent for the original global placement problem, even with different constraints. Compared with the other four popular optimization methods, experimental results show that our method achieves the best quality and is robust for handling different objectives. In particular, our generalized augmented Lagrangian formulation is theoretically sound and can solve generic large-scale constrained nonlinear optimization problems, which are widely used in many fields.

Fogging and proximity effects are two major factors that cause inaccurate exposure and thus layout pattern distortions in e-beam lithography. In this paper, we propose the first analytical placement algorithm to consider both the fogging and proximity effects. We first formulate the global placement problem as a separable minimization problem with linear constraints, where different objectives can be tackled one by one in an alternating fashion. Then, we propose a novel proximal group alternating direction method of multipliers (ADMM) to solve the separable minimization problem with two subproblems, where the first subproblem (mainly associated with wirelength and density) is solved by a steepest descent method without line-search, and the second one (mainly associated with the fogging and proximity effects) is handled by an analytical scheme. We prove the property of global convergence of the proximal group ADMM method. Finally, legalization and detailed placement are used to legal and further improve the placement result. Experimental results show that our algorithm is effective and efficient for the addressed problem. Compared with the state-of-the-art work, our algorithm not only can achieve 13.4% smaller fogging variation and 21.4% lower proximity variation, but also has a 1.65× speedup.

Mixed-cell-height standard cells are prevailingly used in advanced technologies to achieve better design trade-offs among timing, power, and routability. As feature size decreases, placement of cells with multiple threshold voltages may violate the complex minimum-implant-area (MIA) layer rule arising from the limitations of patterning technologies. Existing works consider the mixed-cell-height placement problem only during legalization, or handle the MIA constraints during detailed placement. In this paper, we address the mixed-cell-height placement problem with MIA constraints into two major stages: post global placement and MIA-aware legalization. In the post global placement stage, we first present a continuous and differentiable cost function to address the Vdd/Vss alignment constraints, and add weighted pseudo nets to MIA violation cells dynamically. Then, we propose a proximal optimization method based on the given global placement result to simultaneously consider Vdd/Vss alignment constraints, MIA constraints, cell distribution, cell displacement, and total wirelength. In the MIA-aware legalization stage, we develop a graph-based method to cluster cells of specific threshold voltages, and apply a strip-packing-based binary linear programming to reshape cells. Then, we propose a matching-based technique to resolve intra-row MIA violations and reduce filler insertion. Furthermore, we formulate inter-row MIA-aware legalization as a quadratic programming problem, which is efficiently solved by a modulus-based matrix splitting iteration method. Finally, MIA-aware cell allocation and refinement are performed to further improve the result. Experimental results show that, without any extra area overhead, our algorithm still can achieve 8.5% shorter final total wirelength than the state-of-the-art work.

Poisson's equation has been used in VLSI global placement for describing the potential field induced by a given charge density distribution. Unlike previous global placement methods that solve Poisson's equation numerically, in this paper, we provide an analytical solution of the equation to calculate the potential energy of an electrostatic system. The analytical solution is derived based on the separation of variables method and an exact density function to model the block distribution in a placement region, which is an infinite series and converges absolutely. Using the analytical solution, we give a fast computation scheme of Poisson's equation and develop an effective and efficient global placement algorithm called Pplace. Experimental results show that our Pplace achieves smaller placement wirelength than ePlace and NTUplace3, two leading wirelength-driven placers. With the pervasive applications of Poisson's equation in scientific fields, in particular, our effective, efficient, and robust computation scheme for its analytical solution can provide substantial impacts to these fields.

Mixed-cell-height circuits have become popular in advanced technologies for better power, area, routability, and performance tradeoffs. With the technology and region constraints imposed by modern circuit designs, the mixed-cell-height legalization problem has become more challenging. In this paper, we present an effective and efficient legalization algorithm for mixed-cell-height circuit designs with technology and region constraints. We first present a fence region handling technique to unify the fence regions and the default ones. To obtain a desired cell assignment, we then propose a movement-aware cell reassignment method by iteratively reassigning cells in locally dense areas to their desired rows. After cell reassignment, a technology-aware legalization is presented to remove cell overlaps while satisfying the technology constraints. Finally, we propose a technology-aware refinement to further reduce the average and maximum cell movements without increasing the technology constraints violations. Compared with the champion of the 2017 ICCAD CAD Contest and the state-of-the-art work, experimental results show that our algorithm achieves the best average and maximum cell movements and significantly fewer technology constraint violations, in a comparable runtime.

Let $r\ge 3$ and $k\ge 2$ be fixed integers. Bollobás and Scott conjectured that every $r$-uniform hypergraph with $m$ edges has a vertex partition into $k$ sets with at most $m/k^r+o(m)$ edges in each set, and proved the conjecture in the case $r=3$. In this paper, we confirm this conjecture in the case $r=4$ by showing that every 4-uniform hypergraph with $m$ edges has a vertex partition into $k$ sets with at most $m/k^4+O(m^{8/9})$ edges in each set.

This paper proposes two homotopy methods for solving the compressed sensing (CS) problem, which combine the homotopy technique with the iterative hard thresholding (IHT) method. The homotopy methods overcome the difficulty of the IHT method on the choice of the regularization parameter value, by tracing solutions of the regularized problem along a homotopy path. We prove that any accumulation point of the sequences generated by the proposed homotopy methods is a feasible solution of the problem. We also show an upper bound on the sparsity level for each solution of the proposed methods. Moreover, to improve the solution quality, we modify the two methods into the corresponding heuristic algorithms. Computational experiments demonstrate effectiveness of the two heuristic algorithms, in accurately and efficiently generating sparse solutions of the CS problem, whether the observation is noisy or not.

For circuit designs in advanced technologies, standard-cell libraries consist of cells with different heights; for example, the number of fins determines the height of cells in the FinFET technology. Cells of larger heights give higher drive strengths, but consume larger areas and power. Such mixed cell heights incur new, complicated challenges for layout designs, due mainly to the heterogeneity in cell dimensions and thus their larger solution spaces. There is not much published work on layout designs with mixed-height standard cells. This paper addresses the legalization problem of mixed-height standard cells, which intends to place cells without any overlap and with minimized displacement. We first study the properties of Abacus, generally considered the best legalization method for traditional single-row-height standard cells but criticized not suitable for handling the new challenge, analyze the capability and insufficiencies of Abacus for tackling the new problem, and remedy Abacuss insufficiencies and extend its advantages to develop an effective and efficient algorithm for the addressed problem. For example, dead spaces become a critical issue in mixed-cell-height legalization, which cannot be handled well with an Abacus variant alone. We thus derive a dead-space-aware objective function and an optimization scheme to handle this issue. Experimental results show that our algorithm can achieve the best wirelength among all published methods in reasonable running time, e.g., about 50% smaller wirelength increase than a state-of-the-art work.

Modern circuits often contain standard cells of different row heights to meet various design requirements. Higher cells give larger drive strengths at the costs of larger areas and power. Multi-row-height standard cells incur challenging issues to layout designs, especially the mixed-cell-height legalization problem due to the heterogeneous cell structures. Honoring the good cell positions from global placement, we present in this paper a fast and near-optimal algorithm to solve the legalization problem. Fixing the cell ordering from global placement and relaxing the right boundary constraints, we first convert the problem into a linear complementarity problem (LCP). With the converted LCP, we split its matrices to meet the convergence requirement of a modulus-based matrix splitting iteration method (MMSIM), and then apply the MMSIM to solve the LCP. This MMSIM method guarantees the optimality if no cells are placed beyond the right boundary of a chip. Finally, a Tetris-like allocation approach is used to align cells to placement sites on rows and fix the placement of out-of-right-boundary cells, if any. Experimental results show that our proposed algorithm can achieve the best cell displacement and wirelength among all published methods in reasonable runtimes. The MMSIM optimality is theoretically proven and empirically validated. In particular, our formulation provides new generic solutions and research directions for various optimization problems that require solving large-scale quadratic programs efficiently.

In this paper, we consider the triple patterning lithography layout decomposition problem. To address the problem, a discrete relaxation theory is built. For designing a discrete relaxation based decomposition framework, we propose a surface projection method for identifying native conflicts in a layout, and then constructing the conflict graph. Guided by the theory, the conflict graph is reduced to small size subgraphs by vertex removals, which is a discrete relaxation. Furthermore, by ignoring stitch insertions and assigning weights to features, the layout decomposition problem on the small subgraphs is further relaxed to a 0-1 program, which is solved by the Branch-and-Bound method. To obtain a feasible solution of the original problem, legalization methods are introduced to legalize a relaxation solution. At the legalization stage, we prior utilize one-stitch insertion to eliminate conflicts, and use a backtrack coloring algorithm to obtain a better solution. We test our decomposition approach on the ISCAS-85 & 89 benchmarks. Comparisons of experimental results show that our approach finds solutions of some benchmarks better than those by the state-of-the-art decomposers. Especially, according to our discrete relaxation theory, some optimal decompositions are obtained.

In a mobile network, wireless data broadcast over$m$channels (frequencies) is a powerful means for distributed dissemination of data to clients who access the channels through multi-antennae equipped on their mobile devices. The$\delta$-antennae largest weight data retrieval ($\delta$ALWDR) problem is to compute a schedule for downloading a subset of data items that has a maximum total weight using$\delta$antennae in a given time interval. In this paper, we first give a linear programming (LP) relaxation for$\delta$ALWDR and show that it is polynomial-time solvable when every data item appears at most once. We also show that when there exist data items with multiple occurrences, the integrality gap of this LP formula is 2. We then present an approximation algorithm of ratio$1-\frac{1}{e}$for the$\delta$-antennae$\gamma$-separated largest weight data retrieval ($\delta$A$\gamma$LWDR) problem, a weaker version of$\delta$ALWDR where each block of up to$\gamma$data (time) slots is separated by a vacant slot on all channels, applying the techniques called collectively randomized LP rounding and layered DAG construction. We show that$\delta$A$\gamma$LWDR is${\mathcal NP}-$complete even for the simple case of$\gamma =2$,$m=3$, and equal-weight data items each appearing up to 3 times. Our algorithm runs in time$O(2^{\gamma}m^{7}T^{3.5}L)$, where$T$is the number of time slots, and$L$is the maximum length of the input. Then, from the simple observation that a ratio$\alpha$approximation solution to$\delta$A$\gamma$LWDR implies a ratio$\alpha -\epsilon$approximation solution to$\delta$ALWDR for any fixed$\epsilon >0$, we immediately have an approximation algorithm of ratio$1-\frac{1}{e}-\epsilon$for$\delta$ALWDR. Our algorithm has the same approximation ratio as the known result in[15]which holds only for$\delta =1$, with a significantly lower time complexity of$O(2^{\frac{1}{\epsilon}}\frac{1}{\epsilon}m^{7}T^{3.5}L)$(improved from$O(\epsilon ^{3.5}m^{\frac{3.5}{\epsilon}}T^{3.5}L)$of[15]). As a by-product, we also give a fixed-parameter tractable (fpt-)algorithm of time complexity$O(2^{B}m^{7}T^{3.5}L)$for$\delta$ALWDR, where$B$is the number of time slots that contain data items with multiple occurrences.

Hybrid e-beam lithography (EBL) and triple patterning lithography (TPL) are advanced technologies for the manufacture of integrated circuits. We propose a technology that combines the advantages of EBL and TPL, which is more promising for the pattern product industry. Layout decomposition is a crucial step in this technology. In this article, we propose a two-stage decomposition flow for the hybrid e-beam and triple patterning lithography of the general layout decomposition (HETLD) problem. At the first stage, we formulate two optimization problems: the e-beam and stitch-aware TPL mask assignment (ESTMA) problem and the extended minimum weight dominating set for R 4 mask assignment (MDS R 4 MA) problem. Binary linear program formulations of the two problems are solved by the cutting plane approach. At the second stage, solutions of the first stage problems are legalized to feasible solutions of the HETLD problem by stitch insertion and e-beam shot. To speed up decomposition, we reduce the problem size by removing some vertices and some minor conflict edges before decomposition. Experimental results show the effectiveness of our decomposition methods based on ESTMA and MDS R 4 MA.

The minimum weight-dominating set (MWDS) problem is NP-hard and has a lot of applications in the real world. Several metaheuristic methods have been developed for solving the problem effectively, but suffering from high CPU time on large-scale instances. In this paper, we design an effective hybrid memetic algorithm (HMA) for the MWDS problem. First, the MWDS problem is formulated as a constrained 0-1 programming problem and is converted to an equivalent unconstrained 0-1 problem using an adaptive penalty function. Then, we develop a memetic algorithm for the resulting problem, which contains a greedy randomized adaptive construction procedure, a tabu local search procedure, a crossover operator, a population-updating method, and a path-relinking procedure. These strategies make a good tradeoff between intensification and diversification. A number of experiments were carried out on three types of instances from the literature. Compared with existing algorithms, HMA is able to find high-quality solutions in much less CPU time. Specifically, HMA is at least six times faster than existing algorithms on the tested instances. With increasing instance size, the CPU time required by HMA increases much more slowly than required by existing algorithms.

The common objective of very large-scale integration (VLSI) placement problem is to minimize the total wirelength, which is calculated by the total half-perimeter wirelength (HPWL). Since the HPWL is not differentiable, various differentiable wirelength approximation functions have been proposed in analytical placement methods. In this paper, we reformulate the HPWL as an l1-norm model of the wirelength function, which is exact but nonsmooth. Based on the l1-norm wirelength model and exact calculation of overlapping areas between cells and bins, a nonsmooth optimization model is proposed for the VLSI global placement problem, and a subgradient method is proposed for solving the nonsmooth optimization problem. Moreover, local convergence of the subgradient method is proved under some suitable conditions. In addition, two enhanced techniques, i.e., an adaptive parameter to control the step size and a cautious strategy for increasing the penalty parameter, are also used in the nonsmooth optimization method. In order to make the placement method scalable, a multilevel framework is adopted. In the clustering stage, the best choice clustering algorithm is modified according to the l1-norm wirelength model to cluster the cells, and the nonsmooth optimization method is recursively used in the declustering stage. Comparisons of experimental results on the International Symposium on Physical Design (ISPD) 2005 and 2006 benchmarks show that the global placement method is promising.

The max-bisection problem consists in partitioning the vertices of a weighted undirected graph into two equally sized subsets so as to maximize the sum of the weights of crossing edges. It is an NP-hard combinatorial optimization problem that arises in many applications. In this paper, we present a memetic algorithm for the max-bisection problem, which integrates a new fast local search procedure, a crossover operator, and a pool updating strategy. These strategies achieve a balance between intensification and diversification. Extensive experiments were performed on a number of benchmark instances with 800 to 10,000 vertices from the literature. The proposed memetic algorithm improved the best known solutions for all benchmark instances tested in this paper. The improvement in terms of cut value over the CirCut by Burer et al.ranging from 0.02 to 4.15 percent, and the average time of our proposed memetic algorithm is much lower than that of CirCut. It shows that the proposed memetic algorithm can find high quality solutions in an acceptable running time.

In this paper, we propose a “multistart-type” algorithm for solving the max-k-cut problem. Central to our algorithm is an auxiliary function we propose. We formulate the max-k-cut problem as an explicit mathematical form, which allows us to use an easy implementable local search. The construction of the auxiliary function requires a local maximizer of the max-k-cut problem. If the best local maximizer obtained is used in the construction of the auxiliary function, then the local maximization of the auxiliary function leads to a better maximizer of the max-k-cut problem. This proves to be a good strategy to escape from the current local optima and to search a broader solution space. Indeed, we have shown, both numerically and theoretically, that the maximization of the auxiliary function by the local search method can escape successfully from previously converged discrete local maximizers by taking increasing values of a parameter. Computational results on many test instances with different sizes and densities show that the proposed algorithm is efficient and stable to find approximate global solutions for the max-k-cut problems. Although we have presented results for k ≥ 2, the robustness of our algorithm is shown for k = 2 by comparisons with a number of recent methods. A number of theoretical results are also presented, which justify the design of our algorithm.

Ignoring some cell overlaps, global placement computes the best position for each cell to minimize some cost metric (e.g., total wire length, density overflow). It is a crucial step in very large scale integration (VLSI) physical design, because it affects rout ability, performance, and power consumption of a circuit. In this paper, we propose an Augmented Lagrangian method to solve the VLSI global placement. In this method, a cautious dynamic density weight increasing strategy is used to balance the wire length and density constraint. We incorporated our method into NTUplace3's global placement framework, and tested it on the IBM mixed-size benchmark circuits. Experimental results show that it obtains high-quality results in a reasonable running time.

Placement is the process of determining the exact locations of circuit elements within a chip. It is a crucial step in very large scale integration (VLSI) physical design, because it affects routability, performance, and power consumption of a design. In this paper, we develop a new analytical placer to solve the VLSI standard cell placement problem. The placer consists of two phases, multilevel global placement (GP) and detailed cell placement (DP). In the stage of GP, during the clustering stage, we use a nonlinear programming technique and a best-choice clustering algorithm to take a global view of the whole netlist and placement information, and then use an iterative local refinement technique during the declustering stage to further distribute the cells and reduce the wirelength. In the stage of DP, we develop a fast legalization algorithm to make the solution by global placement legal and use a cell order polishing to improve the legal solution. The proposed algorithm is tested on the IBM standard cell benchmark circuits and Peko suites. Experimental results show that our placer obtains high-quality results in a reasonable running time.

Floorplanning in very large scale integrated-circuit (VLSI) design is the first phase in the process of designing the physical layout of a chip. This makes the floorplanning problem of paramount importance, since it determines the performance, size, yield, and reliability of VLSI chips . From the computational point of view, the VLSI floorplanning is an NP-hard problem. In this paper, we present a hybrid simulated annealing algorithm (HSA) for nonslicing VLSI floorplanning. The HSA uses a new greedy method to construct an initial B*-tree, a new operation on the B*-tree to explore the search space, and a novel bias search strategy to balance global exploration and local exploitation. Experimental results on Microelectronic Center of North Carolina (MCNC) benchmarks show that the HSA can quickly produce optimal or nearly optimal solutions for all the tested problems.

The partner selection problem with a due date constraint in virtual enterprises is proved to be NPcompleteness problem. So it cannot have any polynomial time solution algorithm at present. Nonlinear integer programming model for the problem is established. The objective function and constraint function of the model have monotonicity properties. Based on the above observations, a Branch-and-Bound algorithm is constructed to solve the problem. Numerical experiments show that the algorithm is effective.