SATISFY_PARFOR
A Parallel MATLAB Function Using PARFOR


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:

Usage:

The basic calculation is performed by satisfy_fun and has the form:

solutions = satisfy_fun ( )
where

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Related Data and Programs:

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.

Reference:

The User's Guide for the Parallel Computing Toolbox is available at http://www.mathworks.com/access/helpdesk/help/pdf_doc/distcomp/distcomp.pdf

  1. Gaurav Sharma, Jos Martin,
    MATLAB: A Language for Parallel Computing,
    International Journal of Parallel Programming,
    Volume 37, Number 1, pages 3-36, February 2009.
  2. Michael Quinn,
    Parallel Programming in C with MPI and OpenMP,
    McGraw-Hill, 2004,
    ISBN13: 978-0071232654,
    LC: QA76.73.C15.Q55.

Source Code:

Examples and Tests:

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.


Last revised on 23 May 2012.