Đang chuẩn bị liên kết để tải về tài liệu:
Handbook of algorithms for physical design automation part 34

Không đóng trình duyệt đến khi xuất hiện nút TẢI XUỐNG Tải xuống

Handbook of Algorithms for Physical Design Automation part 34 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. | 312 Handbook of Algorithms for Physical Design Automation Algorithm simulated_annealing void 1 T To Initial Temperature 2 do 3 do 4 j generate i Move Strategies 5 if accept hC T then Metropolis function 6 i j 7 until cost is in equilibrium Temperature equilibrium 8 update T Temperature decrement 9 until cost cannot be reduced any further Stopping criteria FIGURE 16.1 Basic simulated annealing algorithm. Unfortunately the placement problem described here does not exhibit optimal substructure. If we apply the greedy algorithm search strategy we will usually get stuck in a local minimum. This means that c i c jj Vj e S jmn 16.1 where jmn is the local minimum state and S jmn is the set of states reachable from the state jmin. In many cases there is a large disparity between the local minimum and the global minimum cost. We need a search strategy that avoids local minima and finds the global minimum. Simulated annealing is such a search strategy. At the heart of the simulated annealing algorithm is the Metropolis Monte Carlo procedure that was introduced to provide an efficient simulation of a collection of atoms in equilibrium at a given temperature 2 . The Metropolis procedure is the inner loop of the simulated annealing algorithm as shown in Figure 16.1. Although the greedy algorithm forbids changes of state that increase the cost function the Metropolis procedure allows moves to states that increase the cost function. Kirkpatrick et al. suggested that the Metropolis Monte Carlo method can be used to simulate the physical annealing process and to solve combinatorial optimization problems 1 . They suggested adding an outer loop that lowers the temperature from a high melting temperature in slow stages until the system freezes and no further changes occur. At each temperature the simulation must proceed long enough for the system to reach a steady state. The sequence of temperatures and the method to reach equilibrium at each temperature is known as annealing schedule.