# Partitioning Tool – KL Algorithm

VLSI Design Automation – Dr. Ranga Vemuri

This is a VLSI partitioning tool using the KL algorithm to solve the bipartitioning problem. It takes a netlist as input, attempts to partition it into 2 sets with a minimum cutset. The minimization is of the number of connections between the resulting netlists. The algorithm implemented is the Kernighanâ€“Lin (KL) algorithm.

I won’t try to do better than the Wikipedia article, but here is a basic description of the algorithm and its application to this problem:

The KL algorithm works by first dividing the graph into two sets with an equal number of vertices (presumably randomly, unless there is some prior knowledge). A cost is then calculated for each vertex. The cost is the weighted external connections (an edge connecting a vertex to the other set) minus the number of weighted internal connections (an edge connecting to a vertex in the same set). This difference is called the D value. The greater the D value, the greater the benefit of switching the vertex to the other set.

The KL algorithm simply proceeds by sorting the vertices in each set by D value, and then swapping them two at a time (one from each set). After each swap, the two that just participated in the swap are marked as no longer eligible for more swaps this pass. The D values are recalculated for all eligible vertices, and the process begins again. They are sorted, and the highest beneficial swap from each set is chosen. This continues until there are no more beneficial swaps. Then all nodes are marked eligible again, and another pass is attempted. This continues until more passes cannot improve the cost of the cut. This is the basic thinking behind the algorithm, it will actually proceed as follows:

- Step 1: G(V,E) is graph of V vertices and E edges.

(A,B) is initial partition of V, such that A and B are equal sized subsets with no overlap and their union covering all of V. - Step 2: Compute Dv = Ev – Iv for all v in V.
- Step 3: Choose ai from A and bi from B that maximizes gi = Dai + Bai + 2caibi. The final term is the connection between the two, if it exists. Add pair (ai, bi) to queue. Remove ai and bi from allowable swaps.
- Step 4: If there are no more eligible nodes for swap, goto Step 5.

Else, recalculate D values for remaining eligible nodes, goto Step 3. - Step 5: find k to maximize the partial sum of gi from i to k in the queue. If total sum G is greater than 0, perform all swaps (a1, …, ak with b1, …, bk), and goto Step 2. Else, end.

This is a deterministic heuristic.

This was one of my first projects writing software from scratch, and it can definitely be seen from my design. I was pretty new as far as my C++ skill, so there is a lot of room for improvement in the design (as far as object orientation). However, it does perform correctly. I learned a lot from this project, and I think improvement can be seen from this project to the next I did, the Placement/Routing tool.

Print article | This entry was posted by Derek on August 12, 2010 at 9:34 pm, and is filed under Projects, VLSI Projects. Follow any responses to this post through RSS 2.0. You can leave a response or trackback from your own site. |