Modern computer chips have on the order of millions of elements to be placed on them in order to achieve the desired functionality. The arrangement of these elements on the placement area can have a huge impact on how the chip will perform. A better placement will result in shorter wire length which amounts to less power used and faster performances. My problem concerns the optimal placement of these computer chip elements on the placement area. The problem input is a description of the placement area, a list of elements with their width and height, and a netlist describing the connections between the elements. The output to the problem is a list of x,y coordinates for each cell on the placement area such that the placement of the elements yields an optimal result measured in terms of wire length. However, to find the optimal solution to the problem is an NP complete problem, meaning it is infeasible to find the guaranteed optimal solution, therefore any method we adopt to solve the problem will be an approximation of the optimal solution.
The problem divides down into three sub-categories. The first category is known as standard cell placement which concerns the placement of elements that have different widths, but all have one standard height.
The next category is known as macro block placement which concerns the placement of elements that are all very "large" meaning that they have varying widths and heights significantly bigger than the standard height.
The third category is known as mixed block placement which, as the name implies, concerns the placement of both standard cells and macro blocks. This problem is unique because the simplistic techniques used in the standard cell placement cant handle the macro blocks because of their non-standard height and the techniques used in macro block placement can not scale to handle the large number of standard cells in the designs. It is the mixed block placement that I am addressing this summer.
A current way of addressing the problem is a technique known as recursive bisection. Previously, at each step, the method sought to divided the placement area and the netlist of cells in half. The process would repeat until there was only one cell per area, at which point the cell would be placed into that location. The netlist of cells is divided in half according to total cell area. However, this method would ignore circumstances in which the dimensions of macro blocks exceed half of the area to be split. In this case, blocks would end up being stacked upon each other because of the overlap of the macro block. Obviously, such a design is not possible and is considered illegal. To address this problem, after the recursive bisection is complete, a legalization step takes place. There are many different possible legalizers, but the functionality of a legalizer is to take a design that contains overlaps and shift the blocks in a minimal way so that the design contains no overlaps at the end of legalization. However, legalization has no knowledge of wire length, therefore the more work the legalizer has to do, the greater the wire length becomes. So it becomes necessary to have the legalizer do the minimal amount of work required, thus we need to reduce overlaps during placement.
My focus is to reduce the number of overlaps during the recursive bisection placement process.