Placement Optimization Method Of Standard Cells Within VLSI Circuits

Placement is one of the most crucial tasks in very large scale integration (VLSI) physicaldesign that has been studied for several decades. With the rapid increase in integrated circuit(IC) design complexity and the development of deep sub-micron technology, the placementproblem has given rise to many researchers’ broad attention recently. Since the placement hasbeen proven to be computationally difficult, most modern placement is done in consecutivesteps:(1) Global placement tries to spread roughly the cells on the chip as evenly as possible,resulting in few overlaps on the chip;(2) Legalization means to align the cells to the rowswithout overlaps;(3) After legalization, detailed placement further optimizes the legalplacement to improve the placement quality according to certain criteria. Typically, manycircuits consist of millions of standard cells, which all have a constant height but variablewidths (or vice-versa). These standard cells to be placed should be organized in rows and haveto be aligned to these rows in order to facilitate power supply. Meanwhile, with the increase ofthe reuse of the intellectual property (IP) modules and pre-designed macro blocks (such asanalog blocks, embedded memories, et al.), which are fixed on the chip and can’t overlap otherblocks, the placement problem becomes more and more difficult.The paper presents a routability-driven global placement method using the wire density of thenet. A highly congested region may result in routing detours around the region and a largerrouted wirelength, even degrade the performance of the router and yield an unroutable design.In order to solve the above-mentioned problem and obtain a global placement eventuallyroutable, the proposed method is analytical based the two-level framework. It applies the LSEfunction to wirelength model and Bell-shaped function to cell density, integrates the analyticalplacement and two-level framework and guides the entire global placement flow using awirelength estimation technique. First of all, it can use an efficient global placement algorithmto place the clusters on the chip area and assign the clusters to the updated positions.Meanwhile, every cell of the original netlist is located at the center of its corresponding cluster.And then, the cells will be placed on the chip to further alleviate overlap. In the wirelengthestimation technique, the wire density of a net is defined as the product between the ratio ofthe wire area over the net area of the net and a parameter, which relates with the pin positions.Moreover, the overlaps between the net and bin grid are carefully analyzed and the overlapfunction is presented and smoothed further. Empirical validation shows our approach is feasible and efficient.An efficient approach to placement legalization within standard cell circuits was alsopresented in this thesis. The residual cell overlaps in the global placement are guaranteed toprevent successful routing in very large scale integration physical design. In order to resolveaforementioned illegal placement, the proposed method is divided into two main stages:sorting the cells to be placed according to certain criteria; legalizing the cells one at a time.During legalization, a new term “collision” is introduced to resolve cell overlaps and then wedissect how this term helps to achieve a better placement. Moreover, cells are reassigned torows through a modified Dijkstra algorithm. Empirical validation shows our approach canobtain a better placement quality.