tailieunhanh - Handbook of algorithms for physical design automation part 17

Handbook of Algorithms for Physical Design Automation part 17 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. | 142 Handbook of Algorithms for Physical Design Automation a FIGURE a Rectangular graph N b its geometric dual without the vertex for the exterior face c its inner dual and d its rectangular dual. Figure a b and c from Sur-Kolay S. and Bhattacharya . Lecture Notes in Computer Science 338 88 1988. 12 a 9 5 h 1 e 6 2 d i b 4 3 f 8 11 g 7 10 c d duals for a given R the strength of the dualization method lies in the fact that a solution if one exists can nevertheless be found in linear time 14 . A graph embedding is a particular drawing of a graph on a surface which may often be a twodimensional plane such that its edges may intersect only at their endpoints. A graph is planar if there exists an embedding of it on a plane whereas a plane graph is an embedding of a planar graph on a plane 5 . By definition a rectangular floorplan is embedded on a plane which therefore implies that its rectangular graph is a plane graph. As all intersections of cuts of F form T-junctions all the internal faces of R the rectangular graph of F are triangles bounded by three edges. Hence a rectangular graph is a plane triangulated graph 12 13 . Given an n-vertex plane triangulated graph G its rectangular dual Rd 12 13 consists of n nonoverlapping rectangles where a rectangle in Rd corresponds to a distinct vertex i e G and rectangles i and j in Rd share at least a portion of a side if and only if there is an edge i j in G. The rectangular dual of G if it exists corresponds to a valid rectangular floorplan where the rectangles represent the modules of the floorplan. Because all faces of G are triangles no more than three rectangular faces in the rectangular dual of G meet at a vertex and thus the floorplan has only T-junctions and no cross junctions. A rectilinear embedding of a plane graph is an embedding in which all the edges of the graph are either horizontal or vertical. Thus a cycle in the plane graph is embedded as a rectilinear polygon. Next let G be a given plane triangulated