tailieunhanh - Handbook of algorithms for physical design automation part 102

Handbook of Algorithms for Physical Design Automation part 102 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. | 992 Handbook of Algorithms for Physical Design Automation a mincost maxflow problem which has the form of a transportation problem. The flow graph is constructed as follows Source node of the flow graph is connected through directed edges to a set of nodes vi representing candidate thermal vias the edges have capacity 1 and cost 0. Directed edges connect a second set of nodes Tj from each tile to the sink node with capacity equaling the number of vias that the tile can contain and cost zero. The capacity is computed using a heuristic approach that takes into account the temperature difference between the tile and the one directly in the tier below it under the assumption that heat flows downward toward the sink the thermal analysis is based on a commercial FEA solver. Source and sink both have cost m which equals the number of intertier vias in the entire region. Finally a node vt is connected to a tile Tj through an arc with infinite capacity and cost equaling the estimated wirelength of assigning an intertier via vi to tile Tj . Another approach to 3D routing presented in Ref. 17 combines the problem of 3D routing with heat removal by inserting thermal vias in the z direction and introduces the concept of thermal wires. Like a thermal via a thermal wire is a dummy object it has no electrical function but is used to spread heat in the lateral direction. Each tier is tiled into a set of regions as shown in Figure . The global routing scheme goes through two phases. In phase I an initial routing solution is constructed. A 3D MST is built for each multipin net and based on the corresponding two-pin decomposition the routing congestion is statistically estimated over each lateral routing edge using the method in Ref. 18 . This congestion model is extended to 3D by assuming that a two-pin net with pins on different tiers has an equal probability of utilizing any intertier via position within the bounding box defined by the pins. A recursive bipartitioning scheme is