tailieunhanh - Handbook of algorithms for physical design automation part 4

Handbook of Algorithms for Physical Design Automation part 4 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. | 12 Handbook of Algorithms for Physical Design Automation discussed in Chapter 24 . Routing in many wiring layers can also straightforwardly be incorporated by adopting a three-dimensional grid. Even bipartiteness is preserved but looses its significance because of preferences in layers and usually built-in resistance against creating vias. The latter and some other desirable features can be taken care of by using other cost functions than just distance and tuning these costs for satisfactory results. Also a net ordering strategy has to be determined mostly to achieve close to full wire list completion. And taking into account sufficient effects of modern technology . cross talk antenna phenomena metal fill lithography demands makes router design a formidable task today even more than in the past. This will be the subject of Chapters 34 through 36 and 38. Assignment and Placement Placement is initially seen as an assignment problem where n modules have to be assigned to at least n slots. The easiest formulation associated a cost with every module assignment to each slot independent of other assignments. The Hungarian method also known as Munkres algorithm 11 was already known and solved the problem in polynomial time. This was however an unsatisfactory problem formulation and the cost function was soon replaced by ai p i cijdp i p j where dP t p j is the distance between the slots assigned to modules i and j aip f is a cost associated with assigning module i to slot p i cij is a weight factor . the number of wires between module i and j penalizing the distance between the modules i and j With all ctj equal to zero it reduces to the assignment problem above and with all a equal to zero it is called the quadratic assignment problem that is now known to be NP hard the traveling salesperson problem is but a special case . Paul C. Gilmore 12 soon provided in 1962 a branch-and-bound solution to the quadratic assignment problem even before that approach had got