A parallel pipelined naive method for testing satisfiability

• Autorzy: Sadowski A. , Jakubski A. , Michalski G.

Warianty tytułu

PL

Równoległa realizacja naiwnej potokowej metody testowania spełnialności

• Języki publikacji: EN

Abstrakty

EN

Field Programmable Gate Array (FPGA) systems are highly suitable for solving satisfiability problems SAT. The paper will present the possibilities in programmable FPGA chips to test satisfiability by use of parallelism and pipelining. There will be presented various options to approach this problem by use of VHDL language. For this purpose, authors created a dedicated architecture, combined with a PC, by use of the UART protocol. To build the architecture authors used a Xilinx Spartan-3AN plate, the synthesis was performed in the ISE 11.3. Xilinx software.

PL

Układy FPGA ze względu na swoją architekturę bardzo dobrze pasują do rozwiązywania zagadnień z zakresu rozwiązywania problemów spełnialności SAT. W artykule przedstawiono współbierzne rozwiązanie problemu spełnialności z zastosowaniem programowalnych układów FPGA. Dla potrzeb realizacji zadania opracowno dedykowaną architekturę, opartą o układ FPGA (Xilinx Spartan-3AN) komunikującą się za pomocą protokołu UART.

Słowa kluczowe

EN

satisfiability; parallel programming; FPGA

PL

spełnialność; programowanie równoległe; FPGA

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2015
• Tom: R. 91, nr 11
• Strony: 154--157
• Opis fizyczny: Bibliogr. 10 poz., rys., tab.

Twórcy

autor

Sadowski A.

• Institute of Computer and Information Sciences, The Faculty of Mechanical Engineering and Computer Science, Czestochowa University of Technology, ul. Dabrowskiego 69, 42-201 Czestochowa, Poland

autor

Jakubski A.

• Institute of Computer and Information Sciences, The Faculty of Mechanical Engineering and Computer Science, Czestochowa University of Technology, ul. Dabrowskiego 69, 42-201 Czestochowa, Poland

autor

Michalski G.

• Institute of Computer and Information Sciences, The Faculty of Mechanical Engineering and Computer Science, Czestochowa University of Technology, ul. Dabrowskiego 69, 42-201 Czestochowa, Poland

Bibliografia

• [1] Hauck S., DeHon A. Reconfigurable Computing The Theory and Practice of FPGA-Based Computation. Morgan Kaufmann/ Elsevier, 2008.
• [2] Zhang L., Malik S. The Quest for Efficient Boolean Satisfiability Solvers. Proceeding CAV ’02 Proceedings of the 14th International Conference on Computer Aided Verification, Springer- Verlag London, 2002.
• [3] Cichoń J., Gogolewski M., Kutyłowski M. Logika dla informatyków. Wydawnictwo Wyższej Szkoły Komunikacji i Zarządzania w Poznaniu, 2006.
• [4] Sadowski A., Jakubski A. Dedykowana architektura stworzona na FPGA do badania logicznych formuł. Zeszyty Naukowe Wydziału Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej, 2011.
• [5] Dlugosch P., Brown D., Glendenning P., Leventhal M., Noyes H. An Efficient and Scalable Semiconductor Architecture for Parallel Automata Processing IEEE Transactions on Parallel & Distributed Systems , no. 1, pp. 1, PrePrints PrePrints, doi:10.1109/TPDS.2014.8
• [6] Hu, Y. Exploring Formal Verification Methodology for FPGABased Digital Systems. Technical Report SAND2012-7926, Sandia National Laboratories, 2012
• [7] Łuba T., Rawski M., Tomaszewicz P., Zbierzchowski B. Synteza układów cyfrowych. Praca zbiorowa. Wydawnictwa Komunikacji i Łącznosci, Warszawa, 2011.
• [8] Wiatr K. Dedicated Pipelined Architecture of Specialized Processors for Real-Time Image Pre-Processing. Proc. of the International Symposium on Robotics and Automation, Monterrey 2000, pp. 301-306
• [9] Redekopp M., Dandalis A. A Parallel Pipelined SAT Solver for FPGA. Lecture Notes in Computer Science, Volume 1896/2000, pp. 462-468, Springer-Verlag, 2000
• [10] Pagarani T., Kocan F., Saab D.G., Abraham J.A. Parallel and scalable architecture for solving SATisfiability on reconfigurable FPGA. Proceedings of the IEEE Custom Integrated Circuits Conference, CICC 2000, pp. 147-150.