Unformatted text preview:

Prof. A. Richard NewtonUniversity of California at BerkeleyPage 1Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.1EE244: Design Technology for Integrated Circuits and SystemsOutlineLecture 2.2◆Overall Physical Design Flow◆Introduction to Partitioning▲Kernighan-Lin▲Fiduccia & MattheysesEE244 Fall 97 1.2.2Abstracting LayoutsVDDGNDD E QD E QTerminal FramePinPort DProf. A. Richard NewtonUniversity of California at BerkeleyPage 2Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.3Standard Cell LayoutEE244 Fall 97 1.2.4Goals of Placement(a) Two tracks required andall connections routed.(b) Shorter wire length butthree tracks required.Prof. A. Richard NewtonUniversity of California at BerkeleyPage 3Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.5Physical Design: Overall FlowRead NetlistInitial PlacementPlacementImprovementCost EstimationRouting RegionDefinitionGlobal RoutingInputPlacementRoutingOutputCleanupRouting RegionOrderingDetailed RoutingCost EstimationRoutingImprovementWrite Layout DatabaseFloorplanningFloorplanningEE244 Fall 97 1.2.6Physical Design: Overall FlowInitial PlacementPlacementImprovementCost EstimationRouting RegionDefinitionGlobal RoutingPlacementProf. A. Richard NewtonUniversity of California at BerkeleyPage 4Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.7Netlist PartitioningAFEDCBGAFEDCBGEE244 Fall 97 1.2.8Partitioning for Minimum Cut-Set(a) Original Partition (Random) (b) Improved PartitionProf. A. Richard NewtonUniversity of California at BerkeleyPage 5Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.9Partitioning◆Given a graph, G, with n nodes with sizes (weights) w:with costs on its edges, partition the nodes of G into k, subsets,k >0, no larger than a given maximim size, p, so as to minimizethe total cost of the edges cut.◆Define :as a weighted connectivity matrix describing the edges of G.◆A k-way partition of G is a set of non-empty, pairwise-disjointsubsets of G, v1,…,vk, such that◆A partition is said to be admissible if◆Problem: Find a minimal-cost permissible partition of G01<≤ =wpi ni,,,LCcij nij==(),, ,,1LvGiik==1U|| , , ,vpi ki≤=1LEE244 Fall 97 1.2.10Exact Solutions◆n nodes, k subsets of size p: kp=n◆ ways to choose the first subset◆ ways to choose the second, etc.◆ ways total◆n=40, p=10◆In general, problems whereare impractical for real circuits (>1,000,000 gates)()npnp−12knpnp p p!−L20Tββ2Prof. A. Richard NewtonUniversity of California at BerkeleyPage 6Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.11n-Way Partitioning◆Hard problem and no really good heuristics for n>2▲ Direct Methods: Start with seed node for each partitionand assign nodes to each partition using some criterion(e.g. sum of weighted connections into partition)▲ Group Migration Methods: Start with (random) initialpartition and migrate nodes among partitions via someheuristic▲ Metric Allocation Methods: uses metrics other thanconnection graph and clusters nodes based on metric.▲ Stochastic Optimization Approaches: Use a general-purpose stochastic approach like simulated annealing orgenetic algorithms◆Usually apply two-way partitioning (Kernighan-Lin orFiduccia-Matheyses) recursively, or simulated annealingEE244 Fall 97 1.2.12Two-Way Partitioning(Kernighan & Lin)◆Consider the set S of 2n vertices, all of equal size for now,with an associated cost matrix◆Assume C is symmetric and◆We want to partition S into two subsets A and B, each with npoints, such that the external costis minimized◆Start with any arbitrary partition [A,B] of S and try todecrease the initial cost T by a series of interchanges ofsubsets of A and B◆When no further improvement is possible, the resultingpartition [A’,B’] is a local minimum and has a fairly highprobability of being a global minimum with this schemeCijij()12ci=∀0TC∑Prof. A. Richard NewtonUniversity of California at BerkeleyPage 7Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.13Two-Way Partitioning(Kernighan & Lin)◆For each :▲external cost (same for Eb)▲internal cost (same for Ib)◆If a ∈Α Α and b ∈Β Β are interchanged, then the gain:◆Proof: If Z is the total cost of connections between A and B,excluding a and b, then:aA∈EcaayyB=∑∈IcaaxxA=∑∈DEIzSzzz=−∀∈gD D cab ab=+−2TZEEcTZIIcgain T T D D cab a b abba a b abab ba a b ab,,,,=+ + −=+ + +=−=+−2EE244 Fall 97 1.2.14Two-Way Partitioning(Kernighan & Lin)(1) Compute all D values in S(2) Choose ai, bi such thatis maximized(3) Set ai and bi asside and call them ai’ and bi’(4) Recalculate the D values for all the elements ofABa bgDDciababijij=2AaBbij{}{}DD c cxAaDDccyBbx x xa xb iyyybyajijji'',{}{}=+ − ∈−=+ ∈2222Prof. A. Richard NewtonUniversity of California at BerkeleyPage 8Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.15Two-Way Partitioning(Kernighan & Lin)◆Repeat (2)-(4) on a new pair until all nodes exhausted◆If sum to m > 0, some gain, so repeat until sum to m=0◆What is the time and memory complexity of this algorithm?( , ), ( , ), , ( , )'' ' ' ' 'ab ab a bnn11 2 2Lgkki=∑1i123mnEE244 Fall 97 1.2.16Two-Way Partitioning(Fiduccia & Mattheyses)◆Move one cell at a time from one side of thepartition to the other in an attempt to minimize thecutset of the final partition▲ base cell -- cell to be moved▲ gain g(i) -- no. of nets by which the cutset woulddecrease if cell i were moved from partition A to partitionB (may be negative)◆To prevent thrashing, once a cell is moved it islocked for an entire pass◆Claim is O(n) timeProf. A. Richard NewtonUniversity of California at BerkeleyPage 9Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.17Two-Way Partitioning(Fiduccia & Mattheyses)◆Steps:(1) Choose a cell(2) Move it(3) Update the g(i)’s of the neighbors◆O(n) neighbors, each cell recomputed each timeneighbor moved, and must recompute for each pin(assume #pins=K.n, Amdahl 470 K~2.7)n n n O pins passii i22 2 2++ =L(# ) / !EE244 Fall 97 1.2.18Two-Way Partitioning(Fiduccia & Mattheyses)◆If p(i) = no. of pins on cell i:◆Bin-sort cells on gi◆Time required to maintain each bucket array O(P)/pass−<<pi g pii() ()-pmaxpmaxMAX_GAINLOCKED_CELLS......CELL1 2 3CProf. A. Richard NewtonUniversity of California at BerkeleyPage 10Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.19Two-Way Partitioning(Fiduccia &


View Full Document
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?