tailieunhanh - Handbook of algorithms for physical design automation part 14

Handbook of Algorithms for Physical Design Automation part 14 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. | 112 Handbook of Algorithms for Physical Design Automation For example a net consisting of four vertices is represented by an equivalent six-edge complete graph. To cut off one vertex from the rest requires cutting three edges so the weight should be 1 3 for a total edge weight of 1 . However to cut off two vertices from the rest requires cutting four edges each with weight 1 4 . Because some of the edges assigned weights of 1 3 and 1 4 may be the same this weighting scheme is inconsistent. Lengauer Len90 proves that no matter what weighting scheme is selected there will always exist an exact graph bipartition with a deviation of 2 VkT from the cost of cutting a single net. Additionally Ihler et al. IWW93 conjecture that a clique graph model is the best in terms of deviation from the true cost of cutting one net. In the generic clique model a net on e vertices induces a complete graph where each edge has weight 1 w 77-------T e - 1 This weighting scheme arises from linear placements into fixed slots separated by a unit distance. The denominator indicates the minimum total wirelength used to connect the e vertices. Vannelli and Hadley VH90 propose the following metric that guarantees the weight of edges cut under a k-way partitioning has an upper bound of 1. 1 Wi i i rm k k Huang HK97 proposes a weight of 4 Wt ------------- e e - 1 that distributes the weight of one net evenly across two edges and gives an expected cut weight of 1. The following weighting scheme distributes the edge weight evenly across e - 1 edges 2 Wt 77 e In Ref. AY95 the authors use a variant of Huang s metric Wi 4 2e - 2 e e - 1 2 e Partitioning and Clustering Metrics In this section we give some definitions relevant to hypergraph partitioning and use them to describe metrics used in hypergraph partitioning. Definition 3 Given a hypergraph G V E nets that have vertices in multiple blocks belong to the cutset Ec of the hypergraph. Given k blocks the cutset between the ith pair of blocks .