satisfy_parfor


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:

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 MIT license

Languages:

satisfy_parfor is available in a MATLAB version.

Related Data and Programs:

satisfy_parfor_test

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.

Reference:

  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:


Last revised on 14 December 2023.