satisfy_parfor a MATLAB code which solves the satisfiability problem, using the parfor() statement to run in parallel.
This problem assumes that we are given a logical circuit of AND, OR and NOT gates, with N=23 binary inputs and a single output. We are to determine all inputs which produce a 1 as the output.
The general problem is NP complete, so there is no known polynomial-time algorithm to solve the general case. The natural way to search for solutions then is exhaustive search of all 2^N possible inputs.
In an interesting way, this is a very extreme and discrete version of the problem of maximizing a scalar function of multiple variables. The difference is that here we know that both the input and output only have the values 0 and 1, rather than a continuous range of real values!
This problem is a natural candidate for parallel computation, since the individual evaluations of the circuit are completely independent.
Depending on the situation, the function could be executed in parallel:
The basic calculation is performed by satisfy_fun and has the form:
solutions = satisfy_fun ( )where
The information on this web page is distributed under the MIT license.
satisfy_parfor is available in a MATLAB version.
cnf, a data directory which describes the DIMACS CNF file format for defining instances of the satisfy problem for boolean formulas in conjunctive normal form.
collatz_parfor, a MATLAB code which seeks the maximum Collatz sequence between 1 and N, running in parallel using the parfor() command.
heated_plate_parfor, a MATLAB code which solves the steady (time independent) heat equation in a 2D rectangular region, using parfor() to run in parallel.
hello_parfor, a MATLAB code which prints out "Hello, world!" multiple times, using parfor() for parallel execution.
high_card_parfor, a MATLAB code which uses the parfor() statement to compute in parallel the statistics for a card game in which you are required to guess the location of the highest card.
matrix_assemble_parfor, a MATLAB code which uses parfor() for parallel execution to assemble the Hilbert matrix in a parallel loop.
md_parfor, a MATLAB code which carries out a molecular dynamics simulation, running in parallel using the parfor() feature.
ode_sweep_parfor, a MATLAB code which uses parfor() to parallelize the computation of a grid of solutions to a parameterized system of ordinary differential equations (ODE).
prime_parfor, a MATLAB code which counts the number of primes between 1 and N; running in parallel using the parfor() feature.
quad_parfor, a MATLAB code which estimates an integral using quadrature; running in parallel using the parfor() feature.
satisfy_parfor, a MATLAB code which demonstrates, for a particular circuit, an exhaustive search for solutions of the circuit satisfiability problem, running in parallel using the parfor() feature.
sparse_parfor, a MATLAB code which demonstrates how a sparse matrix can be constructed by evaluating individual blocks in parallel with the parfor() command, and then assembled (on a single processor) using the sparse() command.