SATISFY_PARFOR is a directory which illustrates how a MATLAB function using the PARFOR statement can be 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 GNU LGPL license.
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.
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.
The User's Guide for the Parallel Computing Toolbox is available at http://www.mathworks.com/access/helpdesk/help/pdf_doc/distcomp/distcomp.pdf
SATISFY_POOL executes the function locally and interactively.
SATISFY_POOL executes the function locally and interactively.
SATISFY_FSU executes the function remotely on the FSU HPC cluster.
You can go up one level to the MATLAB source codes.