Handbook of Algorithms for Physical Design Automation part 25 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. | 222 Handbook of Algorithms for Physical Design Automation overlapped with the rectangle defined by the two closest corners of bi and bj and finally to bj bi for which it is considered as bi bj bj bi . Given a placement T_ can be extracted as follows. We first extract the module on the bottom-left corner. At each iteration we extract the left-most unvisited module b with all the modules below b having been extracted. The process repeats until no module is left. Figure through f illustrate the procedure to extract a T_ from the placement of Figure . We first extract the module ba on the bottom-left corner Figure and then bb because it is the left-module with all the modules below bb having been extract Figure . This process continues until no module is left resulting in r_ abcdegf . After extracting r_ we can construct Ch and Cv based on T_. For each module bi in T_ we introduce a node n with the weight being bi s width height in Ch Cv . Also for each module bi before bj in T_ we introduce an edge nh nj in Ch Cv if bi F bj bi bj . As shown in Figure andg for the first two modules ba bb in T_ we introduce the nodes na and nb in Ch Cv and assign the a b c d e f r_ a b c d e g f g FIGURE a-f Process to extract a r_ from the placement and g resulting TCG-S. From Lin . and Chang . IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 23 968 2004. With permission. Packing Floorplan Representations 223 weights as their widths heights . Also we construct a directed edge na nb in Cv because module ba is before bb and ba bb. The process repeats for all modules in r_ resulting in the TCG-S shown in Figure . Each TCG has seven nodes and 21 edges in total eleven in Ch and ten in Cv . Note that there exists a unique TCG-S corresponding to a placement. From TCG-S to a Placement Lin and Chang propose an O m lg m -time packing scheme for TCG-S based on T_ as well as a horizontal and a vertical contours Rh and Rv where m is
