Application of CUDA in the Boolean Domain for the Unate Covering Problem

Authors

Eric Paul, Portland State University
Bernd Steinbach, Freiberg University of Mining and Technology
Marek Perkowski, Portland State UniversityFollow

Document Type

Pre-Print

Publication Date

9-2010

Subjects

Computer algorithms, Graphics processing units, Boolean algebra

Abstract

NVIDIA’s Compute Unified Device Architecture (CUDA) is a relatively-recent development that allows to realize very fast algorithms for several Constraint Satisfaction and Computer Aided Design tasks. In this paper we present an approach to use Graphics Processing Units (GPU) and CUDA for solving Unate Covering Problem, a practical problem related to SAT. In particular we present a CUDA-enabled Petrick Function Minimizer. We compare the performance of a pipeline-processor (CPU) and a parallel processor (GPU) implementation of the matrix-multiplication method for solving unate covering problems.

Description

Originally presented at the 9th International Workshop on Boolean Problems, September 16-17, 2010, and included in volume 16 of its proceedings.

Persistent Identifier

http://archives.pdx.edu/ds/psu/12768

Citation Details

Paul, Eric, Bernd Steinbach, and Marek Perkowski. "Application of CUDA in the Boolean Domain for the Unate Covering Problem." Boolean Problems, Proceedings of the 9th International Workshops on Boolean Problems. 2010.