VLSI Physical Design AutomationSystem HierarchyLevels of PartitioningPartitioning of a CircuitImportance of Circuit PartitioningSome TerminologyCircuit RepresentationCircuit Partitioning FormulationA Bi-Partitioning ExampleCircuit Partitioning Formulation (Cont’d)Partitioning AlgorithmsIterative Partitioning AlgorithmsKernighan-Lin AlgorithmRestricted Partition ProblemProblem FormulationA Trivial ApproachIdea of KL AlgorithmSlide 18Slide 19ExampleTime Complexity of KLRecap of Kernighan-Lin’s AlgorithmA Useful Survey Paper101/14/19VLSI Physical Design AutomationProf. David [email protected]: ACES 5.434Lecture 3. Circuit Partitioning201/14/19System Hierarchy301/14/19Levels of PartitioningSystem Level PartitioningBoard Level PartitioningChip Level PartitioningSystemPCBsChipsSubcircuits/ Blocks401/14/19Partitioning of a Circuit501/14/19Importance of Circuit PartitioningDivide-and-conquer methodologyThe most effective way to solve problems of high complexityE.g.: min-cut based placement, partitioning-based test generation,…System-level partitioning for multi-chip designs inter-chip interconnection delay dominates system performance.Circuit emulation/parallel simulation partition large circuit into multiple FPGAs (e.g. Quickturn), or multiple special-purpose processors (e.g. Zycad).Parallel CAD developmentTask decomposition and load balancingIn deep-submicron designs, partitioning defines local and global interconnect, and has significant impact on circuit performance…… ……601/14/19Some TerminologyPartitioning: Dividing bigger circuits into a small number of partitions (top down)Clustering: cluster small cells into bigger clusters (bottom up).Covering / Technology Mapping: Clustering such that each partitions (clusters) have some special structure (e.g., can be implemented by a cell in a cell library).k-way Partitioning: Dividing into k partitions.Bipartitioning: 2-way partitioning.Bisectioning: Bipartitioning such that the two partitions have the same size.701/14/19Circuit Representation•Netlist:–Gates: A, B, C, D–Nets: {A,B,C}, {B,D}, {C,D}•Hypergraph:–Vertices: A, B, C, D–Hyperedges: {A,B,C}, {B,D}, {C,D}–Vertex label: Gate size/area–Hyperedge label: Importance of net (weight)ABC DABCD801/14/19Circuit Partitioning FormulationBi-partitioning formulation: Minimize interconnections between partitionsMinimum cut: min c(x, x’)minimum bisection: min c(x, x’) with |x|= |x’|minimum ratio-cut: min c(x, x’) / |x||x’|X X’c(X,X’)901/14/19A Bi-Partitioning ExampleMin-cut size=13Min-Bisection size = 300Min-ratio-cut size= 19abc ed fmini-ratio-cut min-bisectionmin-cut910100100 1001001001004Ratio-cut helps to identify natural clusters1001/14/19Circuit Partitioning Formulation (Cont’d)General multi-way partitioning formulation: Partitioning a network N into N1, N2, …, Nk such thatEach partition has an area constrainteach partition has an I/O constraintMinimize the total interconnection:iNviAva )(iiiINNNc),(),(iNiNNNci1101/14/19Partitioning AlgorithmsIterative partitioning algorithmsSpectral based partitioning algorithmsNet partitioning vs. module partitioningMulti-way partitioningMulti-level partitioning Further study in partitioning techniques (timing-driven …)1201/14/19Iterative Partitioning AlgorithmsGreedy iterative improvement method[Kernighan-Lin 1970][Fiduccia-Mattheyses 1982][krishnamurthy 1984]Simulated Annealing[Kirkpartrick-Gelatt-Vecchi 1983][Greene-Supowit 1984]1301/14/19Kernighan-Lin AlgorithmKernighan-Lin AlgorithmKernighan-Lin AlgorithmKernighan-Lin Algorithm““An Efficient Heuristic Procedure for An Efficient Heuristic Procedure for Partitioning Graphs”Partitioning Graphs”The Bell System Technical JournalThe Bell System Technical Journal49(2):291-307, 197049(2):291-307, 19701401/14/19Restricted Partition Problem•Restrictions:–For Bisectioning of circuit.–Assume all gates are of the same size.–Works only for 2-terminal nets.•If all nets are 2-terminal,the Hypergraph is called a Graph.ABCDHypergraph RepresentationGraph RepresentationABCD1501/14/19Problem Formulation•Input: A graph with –Set vertices V. (|V| = 2n)–Set of edges E. (|E| = m) –Cost cAB for each edge {A, B} in E.•Output: 2 partitions X & Y such that–Total cost of edges cut is minimized.–Each partition has n vertices.•This problem is NP-Complete!!!!!1601/14/19A Trivial Approach•Try all possible bisections. Find the best one.•If there are 2n vertices, # of possibilities = (2n)! / n!2 = nO(n)•For 4 vertices (A,B,C,D), 3 possibilities.1. X={A,B} & Y={C,D}2. X={A,C} & Y={B,D}3. X={A,D} & Y={B,C}•For 100 vertices, 5x1028 possibilities.•Need 1.59x1013 years if one can try 100M possbilities per second.1701/14/19Idea of KL Algorithm•DA = Decrease in cut value if moving A–External cost (connection) EA – Internal cost IA –Moving node a from block A to block B would increase the value of the cutset by EA and decrease it by IA ABCDX YABCDX YDA = 2-1 = 1DB = 1-1 = 01801/14/19Idea of KL Algorithm•Note that we want to balance two partitions•If switch A & B, gain(A,B) = DA+DB-2cAB –cAB : edge cost for ABABCDX YABCDX Ygain(A,B) = 1+0-2 = -11901/14/19Idea of KL Algorithm•Start with any initial legal partitions X and Y.•A pass (exchanging each vertex exactly once) is described below:1. For i := 1 to n do From the unlocked (unexchanged) vertices, choose a pair (A,B) s.t. gain(A,B) is largest. Exchange A and B. Lock A and B. Let gi = gain(A,B).2. Find the k s.t. G=g1+...+gk is maximized.3. Switch the first k pairs.•Repeat the pass until there is no improvement (G=0).2001/14/19Example1X23456YOriginal Cut Value = 94X23156YOptimal Cut Value = 5A good step-by-step example in SY book2101/14/19Time Complexity of KL•For each pass,–O(n2) time to find the best pair to exchange.–n pairs exchanged.–Total time is O(n3) per pass.•Better implementation can get O(n2log n) time per pass.•Number of passes is usually small.2201/14/19Recap of Kernighan-Lin’s AlgorithmPair-wise exchange of nodes to reduce cut sizeAllow cut size to increase temporarily within a pass Compute the gain of a swapRepeatPerform a feasible swap of max gainMark swapped nodes “locked”;Update swap gains; Until no feasible swap; Find max prefix partial sum in gain sequence g1, g2, …, gm Make corresponding swaps