In this paper, we develop a mixed-size placement tool, Dragon2006, to solve large scale placement problems effectively. A top-down hierarchical approach based on min-cut partitioning and simulated annealing is used to place very large SoC-style designs containing fixed blockage, movable macro blocks of various sizes and standard cells. Moreover, we have applied several techniques for wirelength optimization, congestion estimation in the presence of blockage and white space allocation for congestion removal.

We propose a new cell moving algorithm to achieve a desired cell density distribution during the detailed placement stage of a large size standard-cell placement flow. To evaluate our algorithm, we also define a distribution deviation metric on how close a placement result is to the target cell density distribution. Experiments show that our approach can generate placement results, which have a cell density distribution closer to the desired distribution with very little increase in the wirelength. We achieve a 32.3% improvement in the distribution deviation at the cost of 11.2% increase in the wirelength on average. Also, the final placement results have 5.9% shorter wirelength than those of an industrial placer, Cadence QPlace.

This paper presents a novel method to reduce routing congestion during placement stage. The proposed approach is used as a post-processing step in placement. Congestion reduction is based on local improvement on the existing layout. However, the approach has a global view of the congestion over the entire design. It uses integer linear programming (ILP) to formulate the problem of conflicts between multiple congested regions, and performs local improvement according to the solution of the ILP problem. The approximation algorithm of the formulated ILP problem is studied and good approximation bounds are given and proved. Experiments show that the proposed approach can effectively alleviate the congestion of global routing results. The low computational complexity of the proposed approach indicates its scalability on large designs.

Abstract | The multi-way partition problem is very important in various applications. In this paper, we use analytical and experimental results to study the k-way partition problem. We introduce the concept of embedding graph for the the k-way partition problem. Based on this concept, we explain di erent scenarios of using a bi-partition heuristic to solve the k-way partition problem. If C denote the optimal cut cost for the k-way partition problem and the bi-partition heuristics we use are-approzimation heuristics (dened in Section 2), we prove that the cut cost from the hierarchical approach has an approximate upper bound of C log k while the cut cost from the all-way bipartition, or at approach, has an upper bound of Ck. This is contrary to some claims made in recent literature ( and CAD tools designed based on it). Experimental results strongly support our theoretical analysis. Our results show that for large target graph, the hierarchical approach is about 77 % better than the single-pass all-way bi-partition approach. The all-way bi-partition approach will perform better in a multipass set-up. However, the hierarchical approach is still on average 7:1 % better in quality and 144 times faster than the multi-partition all-way bi-partition approach. The main conclusion of this paper is, contradicted to what has been suggested in literature, hierarchical bipartitioning is a more e ective multi-way partitioning scheme. I.

Abstract| Typical placement objectives in volv e reducing net-cut cost or minimizing wirelength.Congestion minimization is least understood, ho w ev er, it models routability most accurately.In this paper, w estudy the congestion minimization problem during placement.First we pointed out that the bounding box router used in [12] is not an accurate measurement of the congestion in the placement.We use a realistic global router to evaluate congestion in the placement stage.This ensures that the nal placement is truely congestion minimized.We also proposed tw o new post processing algorithms, the ow-based cell-centric algorithm and the net-centric algorithm.While the o w-based cell-centric algorithm can move multiple cells at the same time to minimize the congestion, it suers large consumption of memory.Experimental results show that the net-centric algorithm can eectiv ely identify the congested spots in the placement and reduce the congestion.It can produce on an average 7:7% less congestion than the method proposed in [12].Finally, w euse a nal global router to verify that the placement obtained from our algorithm has 39% less congestion than a wirelength-optimized placement obtained by TimberWolf (commercial version 1.3.1).

In this paper, we develop a new standard cell placement tool, Dragon2000, to solve large scale placement problem effectively. A top-down hierarchical approach is used in Dragon2000. State-of-the-art partitioning tools are tightly integrated with wirelength minimization techniques to achieve superior performance. We argue that net-cut minimization is a good and important shortcut to solve the large scale placement problem. Experimental results show that minimizing net-cut is more important than greedily obtain a wirelength optimal placement at intermediate hierarchical levels. We run Dragon2000 on recently released large benchmark suite ISPD98 as well as MCNC circuits. For circuits which have more than 100 k cells, comparing to iToolsl.4.0, Dragon2000 can produce slightly better placement results (1.4%) while spending much less amount of time (2/spl times/ speedup). This is also the first published placement result on the publicly available large industrial circuits.

As technology advances, more and more issues need to be considered in the placement stage, e.g., wirelength, congestion, timing, coupling. It is very hard to consider all of them together at the same time. Thus it is good if we can optimize one cost function without a ecting others. In this paper, we will study methods to optimize congestion in placement without in icting degradations/violations in other objectives or constraint. We give a mathematical equation to predict the over ow within a region using a normal distribution approximation. According to experiments, this equation does give a good estimation of over ow. We used this equation to nd the smallest regions whichhave enough routing resource to alleviate the congestion and propose the exible expansion scheme in our multi-center congestion reduction (MC 2 R) algorithm. Experimental results show that generally there is a correlation between the amount of reduction in congestion and the amount ofchange made to the placement: the more we change the placement, the more reduction in congestion we will get. However, the exible expansion scheme is very e ective in helping us reduce congestion while make only little change to the placement. Comparing to the full expansion scheme (49 % congestion reduction and 6:5 % change in placement), the exible expansion scheme together with MC 2 R algorithm can reduce congestion by almost the same amount (42%) with much less change made to the placement (1:8%). 1.

The standard cell placement problem has been extensively studied in the past twenty years. Many approaches were proposed and proven effiective in practice. However, successful placement tools need enormous time in the course of development. In this paper we propose a new snap-on placement tool, which is based on multilevel hierarchical placement method. It has great flexibility to combine existing packages and techniques in its top-down framework. In addition, it can be used to build a good placement tool in a short amount of time. Some important issues in multilevel hierarchical placement are discussed here. We investigate the behavior of net-cut and wirelength objectives in global placement problem, propose a + level clustering technique and design a new topdown placement method based on partitioning, annealing and + level technique. We alsowork on the trade-off between solution quality and running time during the hierarchical placement. Experimental results show the strength of proposed placement tool, it produces very good results on all benchmarks and the best known result on the largest MCNC benchmark (avql).

Typical placement objectives involve reducing net-cut cost or minimizing wirelength. Congestion minimization is the least understood, however, it models routability most accurately. In this paper, we study the congestion minimization problem during placement. First, we show that a global placement with minimum wirelength has minimum total congestion. We show that minimizing wirelength may (and in general, will) create locally congested regions. We test seven different congestion minimization objectives. We also propose a post processing stage to minimize congestion. Our main contribution and results can be summarized as follows. (1) Among a variety of cost functions and methods for congestion minimization (including several currently used in industry), wirelength alone followed by a post processing congestion minimization works the best and is one of the fastest. (2) Cost functions such as a hybrid length plus congestion (commonly believed to be very effective) do not always work very well. (3) Net-centric post-processing techniques are among the best congestion alleviation approaches. (4) Congestion at the global placement level, correlates well with congestion of detailed placement.

Typical placement objectives involve reducing net-cut cost or minimizing wirelength.Congestion minimization is least understood, however, it models routability accurately.In thii paper, we study the congestion minimization problem during placement.We introduce the notion of consistent routing model and promote its adoption by placement systems.First, we show that in thii model the wirelength objective is indeed a good measure of congestion by establishing that a placement with minimum wirelength has minimum total congestion.We show that miniibmg wirelength may (and in general, will) create locally congested regions.We demonstrate that most other congestion related objectives are ill behaved and they should only be used in a post processing step.We then propose several novel congestion minimization objectives.One in psrticulsr, called overflow minimization with look-ahead, performs very well and can be computed very efficiently in an incremental manner.At the end, we propose a post processing phase that further improves the congestion.By combining the overflow minimization with look-ahead and the post processing phase, we improve the congestion by more than 40% on the average.

Traditional placement problems are studied under a fully specified cell library and a complete netlist. However, in the first, e.g., 2 years of a 2-3 year microprocessor design cycle, the detailed netlist is unavailable. For area and performance estimation, layout must nevertheless be done with incomplete information. Another source of incompleteness comes from reuse of instances from earlier design generations; these instances and their parameters will change as the project evolves. The problem of placement with incomplete data (PID) can be abstracted as having to place a circuit when p/sub c/% of the cells and p/sub n/% of the nets are missing. The key challenge in PID is how to add missing cells and nets. In this paper, two patching-methods for adding missing nets and cells are proposed. The methods are called abstraction and fusion. Experimental results are very interesting and illustrative. First, they show that PID is a difficult problem and an arbitrary (and perhaps intuitively sound) method may not produce high-quality results. Experiments verify that the abstraction method is a very good predictor and that fusion is not because circuits produced by abstraction attain much of the properties of the original circuits. Summary Table 3 in Section 4 shows that when a circuit has 10% incompleteness, abstraction can predict the final total wirelength with an error of 5.8%, while fusion has a 67.8% error in predicting the wirelength in the same circuit.

We present a new approach to the placement problem. The proposed approach consists of analyzing the input circuit and deciding on a two-dimensional global grid for that particular input. After determination of the grid size, the placement is carried out in three steps: global placement, detailed placement, and final optimization. We show that the output of the global placement can also serve as a fast and accurate predictor. Current implementation is based on simulated annealing. We have put all algorithms together in a placement package called NRG (pronounced N-er-G). In addition to area minimization, NRG can perform timing-driven placement. Experimental results are strong. We improve TimberWolf's results (version 1.2) by about 5%. Our predictor can estimate the wavelength within 10-20% accuracy offering 2-20x speedup compared with the actual placement algorithm.