The Hierarchical Memory Machine (HMM) is a theoretical parallel computing model that captures the essence of computing on CUDA-enabled GPUs. The summed area table (SAT) of a matrix is a data structure frequently used in the area of computer vision which can be obtained by computing the column-wise prefix-sums and then the rowwise prefix-sums. The […]

October 14, 2014 by hgpu

SAT solving strategies that perform backtracking or clause learning are usually difficult to implement efficiently on massively-parallel architectures because the necessary synchronization does not scale linear with the number of processors available. Strategies like Lookahead Solving and Cube and Conquer are more promising. In order to evaluate a potential GPU implementation of Cube and Conquer, […]

July 16, 2014 by hgpu

The parallel computing power offered by Graphical Processing Units (GPUs) has been recently exploited to support general purpose applications-by exploiting the availability of general API and the SIMT-style parallelism present in several classes of problems (e.g., numerical simulations, matrix manipulations) – where relatively simple computations need to be applied to all items in large sets […]

July 15, 2014 by hgpu

Since the slowdown in improvement in the frequency of processors, a new tendency has arisen to allow software to take advantage of faster hardware: parallelization. However, different from increasing the frequency of processors, using parallelization requires a different kind of programming, parallel programming, which is usually harder than common sequential programming. In this context, automatic […]

May 31, 2014 by hgpu

SAT solver is an algorithm for finding the solution of a given problem by using CNF (Conjunctive Normal Form). Recently SAT solver studies have focused on the aspect of cryptography. The purpose of this paper is to construct the framework of a parallel SAT solver that can be applied to cryptanalysis. First, we transform an […]

May 10, 2014 by hgpu

In order to provide efficient software tools to deal with large membrane systems, high-throughput simulators are required. Parallel computing platforms are good candidates, since they are capable of partially implementing the inherently parallel nature of the model. In this concern, today GPUs (Graphics Processing Unit) are considered as highly parallel processors, and they are being […]

August 5, 2013 by hgpu

The Boolean Satisfability Problem is one of the most important problems in computer science with applications spanning many areas of research. Despite this importance and the extensive study and improvements that have been made, no efficient solution to the problem has been found to the date. During the last years, nVidia introduced CUDA, a platform […]

July 15, 2013 by hgpu

In the last few decades there have been substantial improvements in approaches for solving the Boolean satisfiability problem. Many of these consisted in elaborating on existing algorithms, both on the side of complete solvers as in the area of incomplete solvers. Besides the improvements to existing solving methods, however, recent evolutions in SAT solving take […]

September 17, 2012 by hgpu

We present an investigation of the use of GPGPU techniques to parallelize the execution of a satisfiability solver, based on the traditional DPLL procedure – which, in spite of its simplicity, still represents the core of the most competitive solvers. The investigation tackles some interesting problems, including the use of a predominantly data-parallel architecture, like […]

June 14, 2012 by hgpu

In the last few decades there have been substantial improvements in approaches for solving the Boolean satisfiability problem. Many of these improvements consisted in elaborating on existing algorithms. On the side of the complete solvers this led to more efficient branching heuristics and the use of watched literals for unit propagation; incomplete solvers on the […]

October 3, 2011 by hgpu

Combinational equivalence checking (CEC) is a mainstream application in Electronic Design Automation used to determine the equivalence between two combinational netlists. Tools performing CEC are widely deployed in the design flow to determine the correctness of synthesis transformations and optimizations. One of the main limitations of these tools is their scalability, as industrial scale designs […]

July 19, 2011 by hgpu

NP Complete problems are one of the most complex problems in computer science but their vast applications in real world always pushes the scientists to explore new ways to solve them. We extended the original problem definition of Boolean Satisfiability Problem to finding all satisfiable solutions of a given problem instance and used massively parallel […]

June 14, 2011 by hgpu