Research Article Open Access

Parallel Memetic Algorithm for VLSI Circuit Partitioning Problem using Graphical Processing Units

P. Subbaraj1 and P. Sivakumar1
  • 1 ,
Journal of Computer Science
Volume 8 No. 5, 2012, 705-710

DOI: https://doi.org/10.3844/jcssp.2012.705.710

Submitted On: 1 August 2011 Published On: 27 February 2012

How to Cite: Subbaraj, P. & Sivakumar, P. (2012). Parallel Memetic Algorithm for VLSI Circuit Partitioning Problem using Graphical Processing Units. Journal of Computer Science, 8(5), 705-710. https://doi.org/10.3844/jcssp.2012.705.710

Abstract

Problem statement: Memetic Algorithm (MA) is a form of population-based hybrid Genetic Algorithm (GA) coupled with an individual learning procedure capable of performing local refinements. Here we used genetic algorithm to explore the search space and simulated annealing as a local search method to exploit the information in the search region for the optimization of VLSI netlist bi-Partitioning problem. However, they may execute for a long time, because several fitness evaluations must be performed. A promising approach to overcome this limitation is to parallelize this algorithms. General Purpose computing over Graphical Processing Units (GPGPUs) is a huge shift of paradigm in parallel computing that promises a dramatic increase in performance. Approach: In this study, we propose to implement a parallel MA using graphics cards. Graphics Processor Units (GPUs) have emerged as powerful parallel processors in recent years. Using of Graphics Processing Units (GPUs) equipped computers; it is possible to accelerate the evaluation of individuals in Genetic Programming. Program compilation, fitness case data and fitness execution are spread over the cores of GPU, allowing for the efficient processing of very large datasets. Results: We perform experiments to compare our parallel MA with a Sequential MA and demonstrate that the former is much more effective than the latter. Our results, implemented on a NVIDIA GeForce GTX 9400 GPU card. Conclusion: Its indicates that our approach is on average 5×faster when compared to a CPU based implementation. With the Tesla C1060 GPU server, our approach would be potentially 10×faster. The correctness of the GPU based MA has been verified by comparing its result with a CPU based MA.

  • 1,165 Views
  • 1,941 Downloads
  • 1 Citations

Download

Keywords

  • Genetic Algorithm (GA)
  • Graphics Processing Units (GPUs)
  • Memetic Algorithm (MA)
  • netlist partitioning
  • genetic programming
  • graphics cards
  • local search
  • physical design