Quine-McCluskey algorithm on GPGPU
Matej Bel University, Tajovskeho 40, Banska Bystrica 974 01, Slovak Republic
AWERProcedia Information Technology and Computer Science, Vol 4 (2013): 3rd World Conference on Innovation and Computer Science (INSODE-2013), 2013
@article{siladi2013quine,
title={Quine-McCluskey algorithm on GPGPU},
author={Sil{‘a}di, Vladim{‘i}r and Filo, Tom{‘a}{v{s}}},
journal={AWERProcedia Information Technology and Computer Science},
volume={4},
number={2},
year={2013}
}
This paper deals with parallelization of the Quine-McCluskey algorithm. This boolean function minimization algorithm has a limitation when dealing with more than four variables. The problem computed by this algorithm is NP-hard and runtime of the algorithm grows exponentially with the number of variables. The goal is to show that parallel implementation of the Quine-McCluskey algorithm on graphics processing units (GPUs) brings significant acceleration of computing process. Parallelization of the algorithm is implemented through Compute Unified Device Architecture (CUDA), which is a parallel computing platform and programming model created by NVIDIA and implemented by graphics processing units (GPUs).
September 15, 2013 by hgpu
