A Parallel Approach to Solving Satisfiability Problems on graphics processing units using neural networks

A Parallel Approach to Solving Satisfiability Problems on graphics processing units using neural networks

Advisor: 

Taflan Gündem

Assigned to: 

Melih Mert

Type: 

Year: 

2016

Status: 

Summary:

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 Satisability Problem (SAT) is one of the earliest NP-complete problems. The solution to SAT has various application areas, including automated theorem proving, circuit design, artificial intelligence, and software verification. Although many algorithms exist to experimentally solve SAT, they are not believed to be efficient 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 final result in our system.

Özet:

Grafik İşleme Üniteleri (GİÜ'ler) son zamanlarda genel amaçlı uygulamaların paralelleştirilmesi konusunda popüler olmuştur. GİÜ'ler çok sayıda güçlü işlemciden oluşup hazır paket olarak sunulmaktadır. Gerçeklenebilirlik Problemi (GP) bilinen en eski NP-karmaşıklık problemlerinden biridir. GP çözümünün otomatik teorem ispatı, devre tasarımı, yapay zeka ve yazılım doğrulama gibi çeşitli uygulama alanları vardır. GP'yi deneysel olarak çözen birçok algoritma olmasına karşın, bunların tüm GP örnekleri üzerinde etkili olduğuna inanılmamaktadır. Bu tezde, GP'yi çözmek için algoritma seçim mekanizması olarak yapay sinir ağlarını kullanan yeni bir GİÜ tabanlı paralel bir yaklaşım öneriyoruz. Bizim sistemimizde, nihai sonuca ulaşmak için yapılan deneyler üzerinde oluşturulan alt problemlerin, doğru algoritmalar (çözücüler) seçilerek çözülmesi ile 3 kata kadar hızlanmalar olduğunu gösteriyoruz.

Contact us

Department of Computer Engineering, Boğaziçi University,
34342 Bebek, Istanbul, Turkey

  • Phone: +90 212 359 45 23/24
  • Fax: +90 212 2872461
 

Connect with us

We're on Social Networks. Follow us & get in touch.