Recently, the topic of how to utilize prior knowledge obtained by machine-learning (ML) techniques during the EDA flow has been widely studied. In this article, we study this topic and propose a practical plug-in named PROS for both routability optimization and routed wirelength estimation which can be applied in the state-of-the-art commercial EDA tool or an academic EDA flow with negligible runtime overhead. PROS consists of three parts: 1) an effective fully convolutional network (FCN)-based predictor that only utilizes the data from placement result to forecast global routing (GR) congestion; 2) a parameter optimizer that can reasonably adjust GR cost parameters based on the prediction result to generate a better GR solution for detailed routing (DR); and 3) a convolutional neural network (CNN)-based wirelength estimator which can report accurate routed wirelength at the placement stage by using the predicted GR congestion. Experiments show that on the industrial benchmark suite in the advanced technology node, PROS can achieve high accuracy of GR congestion prediction and significantly reduce design rule checking (DRC) violations by 11.65% on average, and on the DAC-2012 benchmark suite, PROS can achieve a very low error rate (1.82%) for wirelength estimation which greatly outperforms that of FLUTE (21.52%) by 19.70%.

Recently the topic of routability optimization with prior knowledge obtained by machine learning techniques has been widely studied. However, limited by the prediction accuracy, the predictors of the existing related works can hardly be applied in a real-world EDA tool without extra runtime overhead for feature preparation. In this paper, we revisit this topic and propose a practical plug-in for routability optimization named PROS which can be applied in the state-of-the-art commercial EDA tool with negligible runtime overhead. PROS consists of an effective fully convolutional network (FCN) based predictor that only utilizes the data from placement result to forecast global routing (GR) congestion and a parameter optimizer that can reasonably adjust GR cost parameters based on prediction result to generate a better GR solution for detailed routing. Experiments on 19 industrial designs in advanced technology node show that PROS can achieve high accuracy of GR congestion prediction and significantly reduce design rule checking (DRC) violations by 11.65% on average.

We propose an electrostatics-based placement algorithm for large-scale mixed-size circuits (ePlace-MS). ePlace-MS is generalized, flat, analytic and nonlinear. The density modeling method eDensity is extended to handle the mixed-size placement. We conduct detailed analysis on the correctness of the gradient formulation and the numerical solution, as well as the rationale of dc removal and the advantages over prior density functions. Nesterov's method is used as the nonlinear solver, which shows high yet stable performance over mixed-size circuits. The steplength is set as the inverse of Lipschitz constant of the gradient function, while we develop a backtracking method to prevent overestimation. An approximated nonlinear preconditioner is developed to minimize the topological and physical differences between large macros and standard cells. Besides, we devise a simulated annealer to legalize the layout of macros and use a second-phase global placement to reoptimize the standard cell layout. All the above innovations are integrated into our mixed-size placement prototype ePlace-MS, which outperforms all the related works in literature with better quality and efficiency. Compared to the leading-edge mixed-size placer NTUplace3, ePlace-MS produces up to 22.98% and on average 8.22% shorter wirelength over all the 16 modern mixed-size benchmark circuits with the same runtime.

ePlace is a generalized analytic algorithm to handle large-scale standard-cell and mixed-size placement. We use a novel density function based on electrostatics to remove overlap and Nesterov's method to minimize the nonlinear cost. Steplength is estimated as the inverse of Lipschitz constant, which is determined by our dynamic prediction and backtracking method. An approximated preconditioner is proposed to resolve the difference between large macros and standard cells, while an annealing engine is devised to handle macro legalization followed by placement of standard cells. The above innovations are integrated into our placement prototype ePlace, which outperforms the leading-edge placers on respective standard-cell and mixed-size benchmark suites. Specifically, ePlace produces 2.83%, 4.59% and 7.13% shorter wirelength while runs 3.05×, 2.84× and 1.05× faster than BonnPlace, MAPLE and NTUplace3-unified in average of ISPD 2005, ISPD 2006 and MMS circuits, respectively.

Many previous works in partitioning have used some underlying clustering algorithm to improve performance. As problem sizes reach new levels of complexity, a single application of a clustering algorithm is insufficient to produce excellent solutions. Recent work has illustrated the promise of multilevel approaches. A multilevel partitioning algorithm recursively clusters the instance until its size is smaller than a given threshold, then unclusters the instance, while applying a partitioning refinement algorithm. In this paper, we propose a new multilevel partitioning algorithm that exploits some of the latest innovations of classical iterative partitioning approaches. Our method also uses a new technique to control the number of levels in our matching-based clustering algorithm. Experimental results show that our heuristic outperforms numerous existing bipartitioning heuristics with improvements ranging from 6.9 to 27.9% for 100 runs and 3.0 to 20.6% for just ten runs (while also using less CPU time). Further, our algorithm generates solutions better than the best known mincut bipartitionings for seven of the ACM/SIGDA benchmark circuits, including golem3 (which has over 100000 cells). We also present quadrisection results which compare favorably to the partitionings obtained by the GORDIAN cell placement tool. Our work in multilevel quadrisection has been used as the basis for an effective cell placement package.

The "quadratic placement" methodology is rooted in [Module Placement Based on Resistive Network Optimization, Proud: A Sea-Of-Gate Placement Algorithm, A Combined Force and Cut Algorithm for Hierarchical VLSI Layout]and is reputedly used in many commercial and in-house tools forplacement of standard-cell and gate-array designs. The methodologyiterates between two basic steps: solving sparse systems oflinear equations, and repartitioning. This work dissects the implementationand motivations for quadratic placement. We firstshow that (i) Krylov subspace engines for solving sparse systemsof linear equations are more effective than the traditional successiveover-relaxation (SOR) engine [A Unified Approach to Partitioning and Placement] and (ii) order convergence criteriacan maintain solution quality while using substantially fewersolver iterations. We then discuss the motivations and relevanceof the quadratic placement approach, in the context of past and futurealgorithmic technology, performance requirements, and designmethodology. We provide evidence that the use of numerical linearsystems solvers with quadratic wirelength objective may be due tothe pre-1990's weakness of min-cut partitioners, i.e., numerical engineswere needed to provide helpful hints to min-cut partitioners.Finally, we note emerging methodology drivers in deep-submicrondesign that may require new placement approaches to the placement problem.

Recent work has illustrated the promise ofmultilevel approaches for partitioning large circuits. Multilevel partitioningrecursively clusters the instance until its size is smallerthan a given threshold, then unclusters the instance while applyinga partitioning refinement algorithm. Our multilevel partitioner usesa new technique to control the number of levels in the matching-basedclustering phase and also exploits recent innovations in classiciterative partitioning. Our heuristic outperforms numerousexisting bipartitioning heuristics, with improvements rangingfrom 6.9 to 27.9% for 100 runs and 3.0 to 20.6% for just 10 runs(while also using less CPU time).

Article Faster minimization of linear wirelength for global placement Share on Authors: Charles J. Alpert IBM Austin Research Laboratory, Austin, TX IBM Austin Research Laboratory, Austin, TXView Profile , Tony F. Chan UCLA Mathematics Department, Los Angeles, CA UCLA Mathematics Department, Los Angeles, CAView Profile , Dennis J.-H. Huang UCLA Computer Science Department, Los Angeles, CA UCLA Computer Science Department, Los Angeles, CAView Profile , Andrew B. Kahng UCLA Computer Science Department, Los Angeles, CA and Cadence Design Systems, Inc., San Jose, CA UCLA Computer Science Department, Los Angeles, CA and Cadence Design Systems, Inc., San Jose, CAView Profile , Igor L. Markov UCLA Mathematics Department, Los Angeles, CA UCLA Mathematics Department, Los Angeles, CAView Profile , Pep Mulet UCLA Mathematics Department, Los Angeles, CA UCLA Mathematics Department, Los Angeles, CAView Profile , Kenneth Yan UCLA Computer Science Department, Los Angeles, CA UCLA Computer Science Department, Los Angeles, CAView Profile Authors Info & Claims ISPD '97: Proceedings of the 1997 international symposium on Physical designApril 1997 Pages 4–11https://doi.org/10.1145/267665.267670Online:01 April 1997Publication History 17citation150DownloadsMetricsTotal Citations17Total Downloads150Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We present a nexv top-down quadrisection-based global placer for standard-cell layout.The key contribution is a new general gain update scheme for partitioning that can exactly capture detailed placement objectives on a per-net basis.We use this gain update scheme, along with an efficient multilevel partitioner, as the basis for a new quadrisection-based placer called QUAD.Even though QUAD is a global placer, it can achieve significant improve ments in wirelength and congestion distribution over GOR-DIAN-L/DOMINO[SDJSI] [DJS94] (a leading quadratic placer with linear wirelength objective and detailed placement improvement).QUAD can be easily extended to capture various practical considerations; our timing-driven placement can obtain wirelength savings (as well as small cycle time improvements) versus the SPEED [RE95].1.

Iterative improvement partitioning algorithms such as the FM algorithm of Fiduccia and Mattheyses (1982), the algorithm of Krishnamurthy (1984), and Sanchis's extensions of these algorithms to multiway partitioning (1989) all rely on efficient data structures to select the modules to be moved from one partition to the other. The implementation choices for one of these data structures, the gain bucket, is investigated. Surprisingly, selection from gain buckets maintained as last-in-first-out (LIFO) stacks leads to significantly better results than gain buckets maintained randomly (as in previous studies of the FM algorithm or as first-in-first-out (FIFO) queues. In particular, LIFO buckets result in a 36% improvement over random buckets and a 43% improvement over FIFO buckets for minimum-cut bisection. Eliminating randomization from the bucket selection not only improves the solution quality, but has a greater impact on FM performance than adding the Krishnamurthy gain vector. The LIFO selection scheme also results in improvement over random schemes for multiway partitioning and for more sophisticated partitioning strategies such as the two-phase FM methodology. Finally, by combining insights from the LIFO gain buckets with the Krishnamurthy higher-level gain formulation, a new higher-level gain formulation is proposed. This alternative formulation results in a further 22% reduction in the average cut cost when compared directly to the Krishnamurthy formulation for higher-level gains, assuming LIFO organization for the gain buckets.

We show h o w t o quantify the suboptimality o f heuristic algorithms for NP-hard problems arising in VLSI layout.Our approach is based on the notion of constructing new scaled instances from an initial problem instance.From the given problem instance, we essentially construct doubled, tripled, etc. instances which h a v e optimum solution costs at most twice, three times, etc. that of the original instance.By executing the heuristic on these scaled instances, and then comparing the growth of solution cost with the growth of instance size, we can measure the scaling suboptimality of the heuristic.We give experimentally determined scaling behavior of several placement and partitioning heuristics; these results suggest that sigini cant improvement remains possible over current state-of-the-art methods.

We study the minimum-cost bounded-skewrouting tree (BST) problem under the linear delay model.This problem captures several engineering tradeoffs in the design of routing topologies with controlled skew.We propose three tradeoff heuristics.(1) For a fixed topology Extended-DME (Ex-DME) extends the DME algorithm for exact zero-skew trees via the concept of a merging region.(2) For arbitrary topology and arbitrary embedding, Extended Greedy-DME (ExG-DME) very closely matches the best known heuristics for the zero-skew case,and for the infinite-skew case (i.e., the Steiner minimal tree problem).(3) For arbitrary topology and single-layer (planar) embedding, the Extended Planar-DME (ExP-DME) algorithm exactly matches the best known heuristic for zero-skew planar routing, and closely approaches the best known performance for the infinite-skew case.Our work provides unifications of the clock routing and Steiner tree heuristic literatures and gives smooth cost-skew tradeoff that enable good engineering solutions.

This paper considers the problem of partitioning a circuit into a collection of subcircuits, such that each subcircuit is feasible for some device from an FPGA library, and the total cost of devices is minimized. We propose a three-phase heuristic that uses ordering, clustering, and dynamic programming to achieve good solutions. Experimental comparisons are made with the previous methods of [4][9].

Analysis of Elmore delay in distributed RC tree structures shows the influence of both tree cost and tree radius on signal delay in VLSI interconnects. We give new and efficient interconnection tree constructions that smoothly combine the minimum cost and the minimum radius objectives, by combining respectively optimal algorithms due to Prim (1957) and Dijkstra (1959). Previous "shallow-light" techniques are both less direct and less effective: in practice, our methods achieve uniformly superior cost-radius tradeoffs. Timing simulations for a range of IC and MCM interconnect technologies show that our wirelength savings yield reduced signal delays when compared to shallow-light or standard minimum spanning tree and Steiner tree routing.>