min Y The complete mixed-integer LP formulation is [Sutanthavibul et al., 1991] min Y x1,Y,W1≥0 Pa Q=0 or 1 ≥￥1+H X+W≤X+W(P+Q) X+W≤X+W(1-P+Q Y+H1≤Y+H(1+PQ Y;+H When H appears in the above equations, it must be replaced (using first-order approximation techniques) by H=D,W;+ E, where D, and E, are defined below: √RA1 R, B, H R,/A1 D, =(Hmax -Hmin)/(Wmin- DW The unknown variables are X, Y, w P and Q all other variables are known the fed into an Lp solver to find a minimum cost solution for the unknowns Placement Techniques Placement is a restricted version of floorplanning where all cells have fixed dimension. The objective of a placement routine is to determine an optimal position on the chip for a set of cells in a way that the total occupied area and total estimated length of connections are minimized. Given that the main cause of delay in a chip is the length of the connections, providing shorter connections becomes an important objective in placing a set of cells. The placement should be such that no cells overlap and enough space is left to complete all the All exact methods known for determining an optimal solution require a computing effort that increases exponentially with number of cells. To overcome this problem, many heuristics have been proposed [Preas and Lorenzetti, 1988]. There are basically three strategies of heuristics for solving the placement problem, namely, constructive, partitioning, and iterative methods. Constructive methods create placement in an incremental manner where a complete placement is only available when the method terminates. They often start by placing a seed(a seed can be a single cell or a group of cells)on the chip and then continuously placing other cells based on some heuristics such as size of cells, connectivity between the cells, design condition for connection lengths, or size of chip. This process continues until all the cells are divide the cells into two or more partitions so that the number of connections that cross the partition boundaries c 2000 by CRC Press LLC
© 2000 by CRC Press LLC min Y Xi + Wi £ W Y ³ Yi + Hi The complete mixed-integer LP formulation is [Sutanthavibul et al., 1991]: min Y Xi ,Yi ,Wi ³ 0 Pij,Qij = 0 or 1 Xi + Wi £ W Y ³ Yi + Hi Xi + Wi £ Xj + W(Pij + Qij) Xj + Wj £ Xi + W(1-Pij + Qij) Yi + Hi £ Yj + H(1 + Pij-Qij) Yj + Hj £ Yi + H(2-Pij-Qij) When Hi appears in the above equations, it must be replaced (using first-order approximation techniques) by Hi = Di Wi + Ei where Di and Ei are defined below: Wmin = Wmax = Hmin = Hmax = Di = (Hmax – Hmin)/(Wmin – Wmax) Ei = Hmax – Di Wmin The unknown variables are Xi , Yi , Wi , Pij, and Qij. All other variables are known. The equations can then be fed into an LP solver to find a minimum cost solution for the unknowns. Placement Techniques Placement is a restricted version of floorplanning where all cells have fixed dimension. The objective of a placement routine is to determine an optimal position on the chip for a set of cells in a way that the total occupied area and total estimated length of connections are minimized. Given that the main cause of delay in a chip is the length of the connections, providing shorter connections becomes an important objective in placing a set of cells. The placement should be such that no cells overlap and enough space is left to complete all the connections. All exact methods known for determining an optimal solution require a computing effort that increases exponentially with number of cells. To overcome this problem, many heuristics have been proposed [Preas and Lorenzetti, 1988]. There are basically three strategies of heuristics for solving the placement problem, namely, constructive, partitioning, and iterative methods. Constructive methods create placement in an incremental manner where a complete placement is only available when the method terminates. They often start by placing a seed (a seed can be a single cell or a group of cells) on the chip and then continuously placing other cells based on some heuristics such as size of cells, connectivity between the cells, design condition for connection lengths, or size of chip. This process continues until all the cells are placed on the chip. Partitioning methods divide the cells into two or more partitions so that the number of connections that cross the partition boundaries RiAi RiBi Ri Bi § Ri Ai §
is minimized. The process of dividing is continued until the number of cells per partition becomes less than a certain small number. Iterative methods seek to improve an initial placement by repeatedly modifying it. Improvement might be made by transforming one cell to a new position or switching positions of two or more cells. After a change is made to the current placement configuration based on some cost function, a decision is made to see whether to accept the new configuration. This process continues until an optimal (in most cases a near optimal)solution is obtained. Often the constructive methods are used to create initial placement on which an iterative method subsequently improves. Constructive Method In most of the constructive methods, at each step an unplaced cell is selected and then located in the p area. There are different strategies for selecting a cell from the collection of unplaced cells [wimer and 1988]. One strategy is to select the cell that is most strongly connected to already placed cells For each unplaced cell, we find the total of its connections to all of the already placed cells. Then we select the unplaced cell that has the maximum number of connections. As an example consider the cells in Fig. 25.15. Assume that cells cr and c2 are already placed on the chip In Fig. 25. 16 we see that cell cs has been selected as the next cell to be placed. This is because cell cs has the largest number of connections(i.e, three)to cells c and c2 岛 lIs to be placed chip area )=21((s1)=2 FIGURE 25 15 Initial configuration. FIGURE 25.16 Selection based on the number of connections c 2000 by CRC Press LLC
© 2000 by CRC Press LLC is minimized. The process of dividing is continued until the number of cells per partition becomes less than a certain small number. Iterative methods seek to improve an initial placement by repeatedly modifying it. Improvement might be made by transforming one cell to a new position or switching positions of two or more cells. After a change is made to the current placement configuration based on some cost function, a decision is made to see whether to accept the new configuration. This process continues until an optimal (in most cases a near optimal) solution is obtained. Often the constructive methods are used to create initial placement on which an iterative method subsequently improves. Constructive Method In most of the constructive methods, at each step an unplaced cell is selected and then located in the proper area. There are different strategies for selecting a cell from the collection of unplaced cells [Wimer and Koren, 1988]. One strategy is to select the cell that is most strongly connected to already placed cells. For each unplaced cell, we find the total of its connections to all of the already placed cells. Then we select the unplaced cell that has the maximum number of connections. As an example consider the cells in Fig. 25.15. Assume that cells c1 and c2 are already placed on the chip. In Fig. 25.16 we see that cell c5 has been selected as the next cell to be placed. This is because cell c5 has the largest number of connections (i.e., three) to cells c1 and c2. FIGURE 25.15 Initial configuration. FIGURE 25.16 Selection based on the number of connections