IntroductionPartitioningPartitioning - contdPartitioning - examplesK-way PartitioningConstraintsConstraints - contdCost FunctionsTwo-Way PartitioningTwo-Way Partitioning-contdTwo-Way Partitioning-contdKernighan-Lin AlgorithmK-L Algorithm - contdK-L Algorithm - contdDefinitionsDefinitionsExampleExample-contdProofProof - contdProof - contdProof - contdProof - contdProof - contdOverview of K-L Algorithm:Greedy Procedure-Identify $X$,$Y$Iterative ImprovementK-L algorithm for TWPPExampleExample - contdExample - contdExample - contdExample - contdExample - contdExample - contdTime ComplexityTime Complexity - contdTime Complexity - contdTime Complexity - contdVariations of K-L AlgorithmAnother approachAnother approach - contd$k-$way partition$k-$way partition - contdFiduccia-Mattheyses HeuristicIllustrationKL vs. FM heuristicsKL vs. FM heuristics - contdKL vs. FM heuristics - contdDefinitionsDefinitions - contdDefinitions - contdIllustration of critical netsFM Algorithm TWPPFM Algorithm TWPP - contdExampleExample - contdExample - contdExample - contdExample - contdExample - contdExample - contdExample - contdExample - contdExample - contdExample - contdExample - contdExample - contdExample - contdAnother ExampleExample - contdExample - contdExample - contdExample - contdExample - contdExample - contdExample - contdSimulated AnnealingSA - contdSA - contdSA - AlgorithmSA - AlgorithmSA - contdSA - contdSA - contdChapter 2:PartitioningSadiq M. Sait & Habib YoussefKing Fahd University of Petroleum & MineralsCollege of Computer Sciences & EngineeringDepartment of Computer EngineeringSeptember 2003Chapter 2: Partitioning – p.1Introduction•Introduction to Partitioning•Problem Definition•Cost Function and Constraints•Approaches to Partitioning1. Kernighan-Lin Heuristic2. Fiduccia-Mattheyses heuristic3. Simulated AnnealingChapter 2: Partitioning – p.2Partitioning•Partitioning is assignment of logic components tophysical packages.1. Circuit is too large to be placed on a single chip.2. I/O pin limitations.•Relationship between the number of gates and thenumber of I/O pins is estimated by Rent‘s rule,IO = tGrwhere:IO: number of I/O pins,t: number of terminals per gate,G: the number of gates in the circuit, andr is Rent’s exponent (0 < r < 1).Chapter 2: Partitioning – p.3Partitioning - contd•A large pin count increases dramatically the cost ofpackaging the circuit.•The number of I/O pins must correspond to one of thestandard packaging technologies - 12, 40, 128, 256 etc.•When it becomes necessary to split a circuit acrosspackages, care must be exercised to minimizecross-package interconnections. because off-chip wiresare undesirable.1. Electrical signals travel slower along wires external to the chip.2. Off-chip wires take up area on a PCB and reduce reliability.Printed wiring and plated-through holes are both likely sources oftrouble.3. Finally, since off-chip wires must originate and terminate into I/Opins, more off-chip wires essentially mean more I/O pins.Chapter 2: Partitioning – p.4Partitioning - examples18274653CC121234567812345678(a)(b)(c)Figure 1: A circuit to be partitionedChapter 2: Partitioning – p.5K-way PartitioningGiven:•A graph G(V, E), where each vertex v ∈ V has a sizes(v), and each edge e ∈ E has a weight w(e).Output:•A division of the set V into k subsets V1, V2, · · · , Vk, suchthat1. an objective function is optimized,2. subject to certain constraints.Chapter 2: Partitioning – p.6Constraints•The cutset of a partition is indicated by ψ and is equal tothe set of edges cut by the partition.•The size of the ithsubcircuit is given byS(Vi) =Xv∈Vis(v)where s(v) is the size of a node v (area of thecorresponding circuit element).•Let Aibe the upper bound on the size of ithsubcircuit;then,Xv∈Vis(v) ≤ AiChapter 2: Partitioning – p.7Constraints - contd•If it is desirable to divide the circuit into roughly equalsizes then,S(Vi) =Xv∈Vis(v) ≤ d1kXv∈Vs(v)e =1kS(V )•If all the circuit elements have the same size, then aboveequation reduces to:ni≤nkwhere niand n are the number of elements in Viand in Vrespectively.Chapter 2: Partitioning – p.8Cost FunctionsMinimize External Wiring.Cost =Xe∈ψw(e)where w(e) is the cost of edge/connection e.•Let the partitions be numbered 1, 2, · · · , k, and p(u) be thepartition number of nodeu.•Equivalently, one can write the function Cost as follows:Cost =X∀e=(u,v)&p(u)6=p(v)w(e)Chapter 2: Partitioning – p.9Two-Way Partitioning•Given a circuit with 2n elements, we wish to generate abalanced two-way partition of the circuit into twosubcircuits ofn elements each.•The cost function is the size of the cutset.•If we do not place the constraint that the partition bebalanced, the two-way partitioning problem (TWPP) iseasy. One simply applies the well known max-flowmincut.•However, the balance criterion is extremely important inpractice and cannot be overlooked. This constraint makesTWPP NP-Complete.Chapter 2: Partitioning – p.10Two-Way Partitioning-contd•A number of “heuristic” techniques can be used to find agood feasible solution.1. Deterministic.(a) Kernighan-Lin.(b) Fiduccia-Mattheyes.2. Non-Deterministic.(a) Simulated Annealing.(b) Genetic Algorithm.(c) Tabu Search.3. Constructive vs. Iterative.Chapter 2: Partitioning – p.11Two-Way Partitioning-contdYesNoProblem instanceConstructive heuristic Stop; Output best solution encountered so far Iterative heuristic Stopping  criteria met ? Figure 2: General structure combining constructiveand iterative heuristicsChapter 2: Partitioning – p.12Kernighan-Lin Algorithm•Most popular algorithm for the two-way partitioningproblem.•The algorithm can also be extended to solve more generalpartitioning problems.•The problem is characterized by a connectivity matrix C.Elementcijrepresents the sum of weights of the edgesconnecting elementsi and j.•In TWPP, since the edges have unit weights, cijsimplycounts the number of edges connectingi and j.•The output of the partitioning algorithm is a pair of sets Aand B such that |A| = n = |B|, and A ∩ B = ∅, and suchthat the size of the cutsetT is minimized.Chapter 2: Partitioning – p.13K-L Algorithm - contdT =Xa∈A,b∈Bcab•Kernighan-Lin heuristic is an iterative improvement algorithm. It startsfrom an initial partition (A, B) such that |A| = n = |B|, andA ∩ B = ∅.•How can a given partition be