Handbook of Algorithms for Physical Design Automation part 54 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. | 512 Handbook of Algorithms for Physical Design Automation BRBC algorithm Input Graph G V E with radius R source s0 e V e 0 Output Spanning tree TBEBC with r TBEBC 1 e R and cost TBEBc 1 cost T Q tm L depth-first tour of TM Sum 0 For i 1 to L -1 Sum Sum dist LirLi 1 If Sum e distG s0 Li 1 Then Q QU edges in minpathG s0 Li 1 Sum 0 Output TBEBC shortest paths tree of Q FIGURE BRBC spanning tree algorithm produces a tree TBRBC with radius at most 1 e R and cost at most 1 2 cost TM . From Cong J. Kahng A. B. Robins G. Sarrafzadeh M. and Wong C. K. IEEE Trans. Comput. Aided Des. 11 739 1992 Kahng A. B. and Robins G. On Optimal Interconnections for VLSI Kluwer Academic Publishers Boston MA 1995. and 2 1 1 times optimal respectively. For X-geometries which allow wiring angles of y 54 a cost bound of cos n 1 times optimal can be shown for BRBC 16 . Experimental benchmarks indicate that both the BPRIM and BRBC algorithms run quickly and indeed yield a smooth trade-off between tree cost and tree radius 16 43 . In fact on typical nets the cost-radius trade-off is on average significantly more favorable than suggested by the theoretical bounds. For example for ten pins and e 1 BRBC offers an average of 21 percent savings in tree radius over optimal at the expense of only 13 percent average rise in tree cost over optimal. Moreover the interconnects produced by BPRIM and BRBC have significantly better delay characteristics than classical Steiner trees as verified by accurate timing simulators . SPICE 16 43 . An alternative approach to the wirelength-radius trade-offs is the AHHK algorithm 40 which integrates Prim s minimum spanning tree algorithm 58 and Dijkstra s shortest path tree algorithm 57 . Prim s algorithm minimizes the total wirelength while Dijkstra s algorithm minimizes the tree radius . the source-to-sink pathlengths . Thus these two classic algorithms address albeit separately two major concerns in performance-driven interconnect synthesis. On the other .
