VLSI partitioning using parallel kernighan lin algorithm

摘要

Isolating the vertices of graph into sets of definite sizes so that the number of edges crossing between sets is minimum is called graph partitioning. This NP-complete problem has important applications in computing, like dynamic load balancing, image segmentation and task scheduling. The graph partitioning algorithms are classified as local and global algorithms. We are implementing Kernighan-Lin, a local algorithm on both a CPU (using C) and a GPU (using CUDAC) system. This algorithm has important applications in VLSI partitioning. The objective of VLSI partitioning is to search for ideal arrangements of components on a board and profitable interconnection between these components to satisfy certain constraints. We need to model VLSI design as a graph and do graph partitioning to achieve this. The CPU implementation of VLSI partitioning using KL-algorithm has a complexity of O(n³). To overcome such a large complexity we are recognizing steps that can be done parallely, thereby implementing in GPU. GPU has densely parallel design containing thousands of smaller efficient cores which are designed for handling numerous tasks concurrently. Thus, implementation in GPU reduces the complexity to O(n). By implementing KL-algorithm in GPU we tend to make VLSI partitioning efficient.