tailieunhanh - Handbook of algorithms for physical design automation part 60

Handbook of Algorithms for Physical Design Automation part 60 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. | 572 Handbook of Algorithms for Physical Design Automation Algorithm Buffered_Path G B s t Input Routing graphG V E Buffer libraryB Source node se V and sink node t e V Output Buffered path labelingm 1. Q C 0 0 t 2. while Q 0 do 3. c d m u extract_min Q 4. if c 0 return m 5. if u s push 0 d Rd c m s into Qand prune continue 6. for each u v e E do d d R u v c C u v 2 push c C u v d m v into Q and prune 7. if p u 1 and m u 0 8. for each b e B do d d R b c K b m u b push C b d m u into Q and prune FIGURE Pseudocode of the dynamic programming-based buffered path algorithm. with m v b. If a solution reaches the source node as c d m s the driver is added by updating the solution as 0 d Rd c m s . When a solution with the driver is at the top of the Q it is the minimum delay solution. The pseudocode of this algorithm is given in Figure . Please note that pruning is performed in many steps to remove inferior solutions so that the runtime can be improved. The complexity of this algorithm is O n V E B V log B V 1 . Graph-Based Approach The graph-based approaches 3 4 first transform the routing graph G V E into a buffer graph GB VB Eb and then obtain the minimum delay buffered path by the Dijkstra s shortest path algorithm. The node set VB of the buffer graph is composed of the source node sink nodes and a set of buffer nodes. A buffer node always has a buffer inserted and therefore it has to be out of any buffer blockage. An edge e e EB is usually directed from the source or a buffer node to a buffer node or the sink node Figure . There is a delay associated with each edge. If the Elmore delay model is employed thedelayd u v foredge u v isequaltoR u C u v C v R u v C u v 2 C v where Source Buffer Buffer Buffer Buffer a Sink c FIGURE Buffer graph. Buffering in the Layout Environment 573 R u is the driving resistance at u R u v is the edge resistance C u v is the edge capacitance and C v is the input capacitance at v. Unlike the routing graph .