A parallel approach to solving satisfiability problems on graphics processing units using neural networks
| dc.contributor | Graduate Program in Computer Engineering. | |
| dc.contributor.advisor | Gündem, Taflan. | |
| dc.contributor.author | Mert, Melih. | |
| dc.date.accessioned | 2023-03-16T10:02:20Z | |
| dc.date.available | 2023-03-16T10:02:20Z | |
| dc.date.issued | 2016. | |
| dc.description.abstract | Graphics Processing Units (GPUs) have become popular for parallelization of general purpose applications recently. GPUs are composed of huge number of powerful processors in a readily available package. The Satis ability Problem (SAT) is one of the earliest NP-complete problems. The solution to SAT has various application areas, including automated theorem proving, circuit design, arti cial intelligence, and software veri cation. Although many algorithms exist to experimentally solve SAT, they are not believed to be e cient on all SAT instances. In this thesis, we propose a novel GPU based parallel approach using neural networks as the algorithm selection mechanism to solve the SAT.We demonstrate speedups of up to 3 times on benchmarks by choosing the correct algorithms (solvers) to solve sub problems to reach the nal result in our system. | |
| dc.format.extent | 30 cm. | |
| dc.format.pages | xii, 49 leaves ; | |
| dc.identifier.other | CMPE 2016 M47 | |
| dc.identifier.uri | https://digitalarchive.library.bogazici.edu.tr/handle/123456789/12314 | |
| dc.publisher | Thesis (M.S.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2016. | |
| dc.subject.lcsh | Graphics processing units -- Programming. | |
| dc.title | A parallel approach to solving satisfiability problems on graphics processing units using neural networks |