tailieunhanh - Handbook of algorithms for physical design automation part 65

Handbook of Algorithms for Physical Design Automation part 65 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. | 622 Handbook of Algorithms for Physical Design Automation overall solution. This schema represents an iterative optimization technique . a pivot is made by tightening some violated constraint and then solving the resulting problem. 1. Route nets 2. Identify areas where the design constraints are violated 3. Identify nets connectionsrto a. Remove r b. Reroute r This schema was proposed in the earliest papers on rip-up and reroute. An early sophisticated discussion is in Ting and Tien 1983 . They define a loop as a closed nonintersecting sequence of boundaries in the grid graph. The loop constraint states that the number of times that connections cross a loop must be no greater than the maximum number of crossings allowed on the loop. For each connection define its crossing count to be the number of times the connection intersects the loop. The crossing count of a net is the sum of the crossing counts of its connections. A net is said to violate the loop constraint if there exists a Steiner tree that can decrease the crossing count. As a specific example suppose a net contains two pins that are outside the loop but the routed connection for these two pins crosses the loop Figure . This connection violates the loop constraint because there must be a Steiner tree that lies entirely outside the loop. Ting and Tien consider several loops simultaneously. Given a set of loops and a set of violating nets they form a bipartite graph. One set of vertices are the violating nets the other set are the loops and there is an edge between a net and a loop if the net violates the corresponding loop constraint. Using this bipartite graph Ting and Tien attempt to find an intelligent subset of nets to rip-up and reroute. They select a minimal set of nets such that if removed no loop constraint will be violated. By minimal this means that if any net was removed from the set some loop constraint would be violated. The smallest such set is called a set cover which is also an .