# 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:

• interactively, and locally, using the matlabpool command;
• indirectly, and locally, using the batch command;
• indirectly, and on the Virginia Tech Ithaca cluster, using the batch command;
• indirectly, and on the FSU HPC cluster, using the fsuClusterMatlab command;

### Usage:

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

solutions = satisfy_fun ( )
where
• solutions is a solution_num by n array, containing the solutions that were found. Each row is a sequence of 0's and 1's indicating an assignment of the variables that makes the formula true.

### Languages:

SATISFY_PARFOR is available in a MATLAB version.

### 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.

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.

### 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.

### 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.

• satisfy_fsu.m a script which uses the fsuClusterMatlab command to run the function indirectly on the FSU HPC cluster.

You can go up one level to the MATLAB source codes.

Last revised on 23 May 2012.