Evaluating the SAT problem on P systems for different high-performance architectures
| Autor: | José M. García, Manuel Ujaldón, Ginés D. Guerrero, José M. Cecilia |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Computer science
Locality Graphics processing unit Memory bandwidth Parallel computing Supercomputer Execution time Theoretical Computer Science Hardware and Architecture Distributed memory Boolean satisfiability problem Membrane computing Massively parallel Time complexity Software Information Systems |
| Zdroj: | The Journal of Supercomputing. 69:248-272 |
| ISSN: | 1573-0484 0920-8542 |
| DOI: | 10.1007/s11227-014-1150-9 |
| Popis: | Membrane computing is an emergent research area studying the behavior of living cells to define bio-inspired computing devices, also called P systems. Such devices provide polynomial time solutions to NP-complete problems by trading time for space. The efficient simulation of P systems poses three major challenging issues: an intrinsic massive parallelism of P systems, an exponential computational workspace, and a non-intensive floating point nature. This paper analyzes the simulation of a family of recognizer P systems with active membranes that solves the satisfiability problem in linear time on three different architectures: a shared memory multiprocessor, a distributed memory system, and a manycore graphics processing unit (GPU). For an efficient handling of the exponential workspace created by the P systems computation, we enable different data policies on those architectures to increase memory bandwidth and exploit data locality through tiling. Parallelism inherent to the target P system is also managed on each architecture to demonstrate that GPUs offer a valid alternative for high-performance computing at a considerably lower cost. Our results lead to execution time improvements exceeding 310 $$\times $$ × and 78 $$\times $$ × , respectively, for a much cheaper high-performance alternative. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|