Czasopismo | PRZEGLĄD ELEKTROTECHNICZNY | Rocznik 2015 - zeszyt 11

A parallel pipelined naive method for testing satisfiability

10.15199/48.2015.11.38

nr katalogowy: 94738
10.15199/48.2015.11.38

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. Streszczenie. Układy FPGA ze wzgle˛du na swoja˛ architekture˛ bardzo dobrze pasuja˛ do rozwia˛zywania zagadnien´ z zakresu rozwia˛zywania problemów spełnialnos´ci SAT. W artykule przedstawiono współbierzne rozwia˛zanie problemu spełnialnos´ci z zastosowaniem programowalnych układów FPGA. Dla potrzeb realizacji zadania opracowno dedykowana˛ architekture˛, oparta˛ o układ FPGA (Xilinx Spartan-3AN) kominukuja˛cie˛ sie˛ za pomoca˛ protokołu UART. (Równoległa realizacja naiwnej potokowej metody testowania spełnialno´ sci) Keywords: satisfiability, parallel programming, FPGA Słowa kluczowe: spełnialno´s´c, programowanie równoległe, FPGA The problem of satisfiability testing (SAT) has been used in various types of applications related to the study of algorithms correctness including cryptography, automatic generation of test patterns and the test of logical formulas. There are solutions to these problems of software, hardware or software-hardware. Currently, the most commonly used for this purpose is SAT-solver, which uses recording a logical formula as a logical formula in conjunctive normal form (CNF) [1]. These SAT-solvers test if for a logical formula transformed to (k-SAT), recorded in CNF there exists such a valuation, for which the formula is true. The basic algorithm for SAT-solver is an DPLL algorithm that uses ’Basic Backtrack Algorithm’ and other heuristic. However, [...]

Jeśli masz wykupiony/przyznany dostęp - zaloguj się. Skorzystaj z naszych propozycji zakupu!

Publikacja


e-Publikacja (format pdf) - nr 94738 "A parallel pipelined naiv..." licencja: Osobista Produkt cyfrowy	10.00 zł

Zeszyt


PRZEGLĄD ELEKTROTECHNICZNY - e-zeszyt (pdf) 2015-11 licencja: Osobista Produkt cyfrowy	55.00 zł

Prenumerata

PRZEGLĄD ELEKTROTECHNICZNY - prenumerata cyfrowa
licencja: Osobista

Produkt cyfrowy
Nowość

762.00 zł

PRZEGLĄD ELEKTROTECHNICZNY - PAKIET prenumerata PLUS
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEGLĄD ELEKTROTECHNICZNY - PAKIET prenumerata PLUS (Prenumerata papierowa + dostęp do portalu sigma-not.pl + e-prenumerata)	1002.00 zł brutto 927.78 zł netto 74.22 zł VAT (stawka VAT 8%)

1002.00 zł

PRZEGLĄD ELEKTROTECHNICZNY - papierowa prenumerata roczna + wysyłka
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEGLĄD ELEKTROTECHNICZNY - papierowa prenumerata roczna	960.00 zł brutto 888.89 zł netto 71.11 zł VAT (stawka VAT 8%)
PRZEGLĄD ELEKTROTECHNICZNY - pakowanie i wysyłka	42.00 zł brutto 34.15 zł netto 7.85 zł VAT (stawka VAT 23%)

1002.00 zł

Zeszyt

2015-11

Twój Koszyk

Publikacja

Zeszyt

Prenumerata

Zeszyt

Czasopisma