Publication

Abstract : Grouping the vertex of the graph into sets of certain sizes such that minimum number of edges cross between the sets is called graph partitioning. This NP (Non-deterministic Polynomial time)-complete problem has important applications in computing, task scheduling, and parallel processing. We are implementing Kernighan-Lin, a local algorithm on both a Central Processing Unit (CPU) and a Graphics Processing Unit (GPU) system. The implementation in CPU is done in C language whereas GPU implementation is done in CUDAC. The CPU implementation of KL-algorithm has a complexity of O(n 3 ). To overcome such a large complexity we are recognizing steps that can be done in parallel, thereby implementing in GPU. GPU has a highly parallel architecture consisting of thousands of cores. These small, efficient cores are constructed in such a way that they can handle multiple task concurrently. Thus, implementation in GPU reduces the complexity to O(n).