Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Handbook of Algorithms for Physical Design Automation part 20 provides a detailed overview of VLSI physical design automation, emphasizing state-of-the-art techniques, trends and improvements that have emerged during the previous decade. After a brief introduction to the modern physical design problem, basic algorithmic techniques, and partitioning, the book discusses significant advances in floorplanning representations and describes recent formulations of the floorplanning problem. The text also addresses issues of placement, net layout and optimization, routing multiple signal nets, manufacturability, physical synthesis, special nets, and designing for specialized technologies. It includes a personal perspective from Ralph Otten as he looks back on. | 172 Handbook of Algorithms for Physical Design Automation M1 M3 M2 FIGURE 9.6 Illustration of three types of moves. in the rest of this chapter. It employs the technique of simulated annealing 17 and uses the set of normalized Polish expressions as the solution space to avoid an unnecessarily large number of states and thus enables the speedup of the search procedure significantly. The following three types of moves M1 M2 and M3 are used to modify a normalized Polish expression to get a neighboring one. M1 Swap two adjacent modules. Two modules are adjacent iff there is no other module between them in the expression. M2 Complement a chain of cuts. A chain of cuts is a sequence of consecutive elements in the expression such that each element is a cut i.e. V or H . V and H are complements of each other. M3 Swap adjacent module and cut. A module and a cut are adjacent iff they are consecutive elements in the expression. It is clear that Ml and M2 each always produce a normalized Polish expression. M3 however might not produce a normalized Polish expression. To generate an M3 move a pair of adjacent module and cut is repeatedly chosen until swapping them will lead to a normalized Polish expression. It is claimed that the three types of moves are sufficient to ensure that any normalized Polish expression can be reached from any other via a finite number of moves. Figure 9.6 gives a demonstration of the three types of moves. Each normalized Polish expression generated in the annealing process will be evaluated as follows. Let Tf denote the corresponding slicing structure for a normalized Polish expression f. The area A and the total wirelength W off are defined to be the area and the total wirelength of a minimumarea floorplan of Tf. The cost function for measuring the quality of a normalized Polish expression is A XW where X is a user-specified constant to control the relative importance of A and W. The minimum-area floorplan can be computed efficiently by the slicing .
