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 computer code and data files described and made available on this web page are 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 program which seeks the maximum Collatz sequence between 1 and N, running in parallel using MATLAB's parfor() feature.
HEATED_PLATE_PARFOR, a MATLAB program which solves the steady (time independent) heat equation in a 2D rectangular region, using MATLAB's parfor() facility to run in parallel.
HELLO_PARFOR, a MATLAB program which prints out "Hello, world!" multiple times, using MATLAB's parfor() command for parallel execution.
HIGH_CARD_PARFOR, a MATLAB program 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.
MATLAB_PARALLEL, MATLAB program which illustrate "local" parallel programming on a single computer with MATLAB's Parallel Computing Toolbox.
MATLAB_RANDOM_PARALLEL, MATLAB programs which illustrate the use of Matlab's random number generator (RNG) functions when using parallel features such as parfor() or spmd.
MATRIX_ASSEMBLE_PARFOR, a MATLAB program which demonstrates the parfor() parallel programming feature by assembling the Hilbert matrix in a parallel loop.
MD_PARFOR, a MATLAB program which carries out a molecular dynamics simulation, running in parallel using MATLAB's parfor() feature.
ODE_SWEEP_PARFOR, a MATLAB program which demonstrates how the PARFOR command can be used to parallelize the computation of a grid of solutions to a parameterized system of ODE's.
PRIME_PARFOR, a MATLAB program which counts the number of primes between 1 and N; running in parallel using MATLAB's "PARFOR" feature.
QUAD_PARFOR, a MATLAB program which estimates an integral using quadrature; running in parallel using MATLAB's "PARFOR" feature.
SATISFY, a MATLAB program which demonstrates, for a particular circuit, an exhaustive search for solutions of the circuit satisfy problem.
SATISFY_MPI, a Fortran90 program which demonstrates, for a particular circuit, an exhaustive search for solutions of the circuit satisfy problem, using MPI to carry out the calculation in parallel.
SATISFY_OPENMP, a C++ program which demonstrates, for a particular circuit, an exhaustive search for solutions of the circuit satisfy problem, using OpenMP for parallel execution.
SPARSE_PARFOR, a MATLAB library 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.
TRAPZ_PARFOR, a MATLAB library which shows how a parfor loop can be used to call the trapz() function, to compute several integral approximations in parallel.