Kernighan lin

Breif description of Kernighan-Lin graph partitioning method, applications,pros and cons of the method

1. Kernighan-Lin Method

2. What is it? Kernighan-Lin is a method of partitioning a graph containing nodes and vertices into separate subsets that are connected together in an optimal manner. Since a graph can be used to represent an electrical network containing blocks, the Kernighan-Lin algorithm can be extended to partitioning circuits into sub-circuits.

3. Application Important application to VLSI circuits. Used to find minimal numbers of connections between partitions to improve speed or decrease power consumption.

4. Kernighan-Lin is an iterative algorithm. This means that the graph/circuit may already be partitioned, but application of Kernighan-Lin will try to improve or optimize the partition. Kernighan-Lin is iterative as opposed to constructive . Kernighan-Lin is a greedy algorithm. This means the algorithm will make changes if there is a benefit right away without consideration to other possible ways of obtaining an optimal solution.

5. Kernighan-Lin is a deterministic algorithm because the same result will be achieved every time the algorithm is applied. The same result will be the same number of nets crossing the bisection, but not necessarily the same nets . One bisection or cut is made to the partition only, so partitioning using Kernighan-Lin will result in only two partitions . Partitions must be equal size.

6. Steps… Draw a line separating your graph into two halves (partitions) with an equal number of vertices (blocks or cells) in each partition. Count the number of edges that cross the line. This number is called your net cut and the goal is to decrease this number. In terms of VLSI circuits, you will be decreasing the number of connections between blocks, which could increase the speed of the circuit, decrease power consumption, and depict other desirable results .

7. Find the edge cost of all vertices in the graph. Finding edge cost is done by finding the number of connections each vertex has within its own partition and subtracting that from the number of connections each vertex has with vertices in the other partition . Determine the maximum gain by swapping any two nodes. The gain equation is given below:   G = D 1 + D 2 – 2C 12  

8. Swap the two nodes with the maximum gain. Note that if all node pairing gains have been calculated and the maximum gain is zero or negative, the nodes with the highest gain should still be swapped. Subtract the gain from the original net cut to get the new net cut . Fix the nodes that were just swapped in place Repeat steps until the maximum gain is zero or negative

9. Advantage Algorithm is Robust .

10. Disadvantages Results are random because the algorithm starts with a random partition Computationally intensive which makes the algorithm slow Only two partitions are created Partitions have to be equal in size so the algorithm does not attempt to find optimal partition sizes when they may (and probably do) exist Does not allow cells to remain fixed in place when they may need to be for timing or other reasons

11. Does not solve problems with weighted edges very well Solution largely dependant on the first swap

12. Solved Example

13. After initial partitioning

14. Step 1: Initial Partition A={ 2, 3, 4 } B={ 1, 5, 6 } Step 2: Compute D Partition A Ea Ia Compute D Partition B E b I b Compute D2 2 1 2 -1 1 1 1 3 1 -1 5 1 1 4 2 1 1 6 1 1

15. Step 3: Computing Gain Possible Pairs C( a,b ) Gain G 21 1 -2 G 25 -1 G 26 -1 G 31 G 35 -1 G 36 -1 G 41 2 G 45 1 -1 G 46 1 -1 Largest G value G41 = +2 A' = A' - { 4 } = { 2, 3 } B' = B' = { 1 } = { 5, 6 }

16. Iteration 2: D values connected to ( 4, 1) are 2 in A' 5, 6 in B' Step 1: Computing new D A' B' CA'4 CA'1 CB'4 CB'1 2 5 1 1 1 3 6 1 D'2 -1 D'5 -2 D'6 -2

17. Computing Gain Step 2: Possible Pairs C(a,b) Gain G 25 -4 G 26 -2 G 35 -3 G 36 -3 Since all Gain values are equal, we arbitrarily choose any one, A' = A' - { 3 } = { 2 } B' = B' - { 6 } = { 5 } we choose G36

18. Iteration 3: ( 3 , 6 ) connected to 2 in A' and 5 in B' Step 1: Computing new D A' B' CA'3 CA'6 CB'3 CB'6 2 5 1 1 D''2 D''5 Therefore last pair (2,5) and gain is 1

19. Determining K Step 5: G1 = +2 G2 = -3 i.e G1 + G2 = -1 G3 = 1 G1 + G2 + G3 = 0

20. References: COMPARATIVE STUDY OF CIRCUIT PARTITIONING ALGORITHMS Zoltan Baruch 1 , Octavian Cre ţ 2 , Kalman Pusztai 3 . Network decomposition using Kernighan Lin strategy aided harmony search algorithm G.A. Ezhilarasi,K.S.Swarup .

21. Thank You 