tailieunhanh - Handbook of algorithms for physical design automation part 18

Handbook of Algorithms for Physical Design Automation part 18 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. | 152 Handbook of Algorithms for Physical Design Automation or four modules rectangles at any level with their given connectivity and size specifications takes constant time. Another strong motivation for employing a hierarchical approach is that because floorplanning decisions affect the subsequent phases of placement or global routing it is desirable to integrate these phases as much as possible. A hierarchical method makes this computationally feasible as designed and implemented by Dai et al. 16 39 and Lengauer et al. 40 . As part of the macrocell based layout system called BEAR the hierarchical floorplanner by Dai et al. consists of three steps Step 1 Bottom-up clustering A hierarchical tree is constructed in a bottom-up fashion by clustering strongly connected modules greedily. Each cluster has a limited number of modules typically upto four. For each cluster the shapes of the blocks are also considered so that there is no mismatch within the cluster. Issues with size incompatibility at higher levels between two neighboring clusters with fewer connections may arise but these can be resolved by limiting the sizes of the clusters at the higher levels so that the smaller sized clusters are dealt with earlier thereby reducing the percentage of wasted area. Step 2 Top-down placement The cluster tree is traversed from the root which has its desired shape and terminals specified. These requirements are propagated to the children clusters and their respective shape and terminals are determined. The small number of possible floorplan templates Figure are enumerated and clusters are assigned to rectangles or rooms in a template to obtain a floorplan topology. In most cases the winning topology is determined by computing the estimated routing space for each of the possible topologies. This is continued till the orientations of the leaf modules are decided. It may be pointed out that this method works well when the leaf level modules can be of flexible shape. A .