satisfy_mpi/satisfy_mpi.html

<html>

  <head>
    <title>
      SATISFY_MPI - Circuit Satisfiability Using MPI
    </title>
  </head>

  <body bgcolor="#EEEEEE" link="#CC0000" alink="#FF3300" vlink="#000055">

    <h1 align = "center">
      SATISFY_MPI <br> Circuit Satisfiability Using MPI
    </h1>

    <hr>

    <p>
      <b>SATISFY_MPI</b>
      is a FORTRAN90 program which
      demonstrates, for a particular circuit, an exhaustive search
      for solutions of the circuit satisfy problem.  This version of
      the program uses MPI to carry out the solution in parallel.
    </p>

    <p>
      This problem assumes that we are given a logical circuit of AND, OR and NOT
      gates, with N binary inputs and a single output.  We are to determine all
      inputs which produce a 1 as the output.
    </p>

    <p>
      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.
    </p>

    <p>
      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!
    </p>

    <p>
      This problem was a natural candidate for parallel computation, since
      the individual evaluations of the circuit are completely independent.
    </p>

    <h3 align = "center">
      Licensing:
    </h3>

    <p>
      The computer code and data files described and made available on this web page
      are distributed under
      <a href = "../../txt/gnu_lgpl.txt">the GNU LGPL license.</a>
    </p>

    <h3 align = "center">
      Languages:
    </h3>

    <p>
      <b>SATISFY_MPI</b> is available in
      <a href = "../../c_src/satisfy_mpi/satisfy_mpi.html">a C version</a> and
      <a href = "../../cpp_src/satisfy_mpi/satisfy_mpi.html">a C++ version</a> and
      <a href = "../../f77_src/satisfy_mpi/satisfy_mpi.html">a FORTRAN77 version</a> and
      <a href = "../../f_src/satisfy_mpi/satisfy_mpi.html">a FORTRAN90 version</a>.
    </p>

    <h3 align = "center">
      Related Data and Programs:
    </h3>

    <p>
      <a href = "../../data/cnf/cnf.html">
      CNF</a>,
      a data directory which
      describes the DIMACS CNF file format for defining instances of the
      satisfy problem in for boolean formulas in conjunctive normal form.
    </p>

    <p>
      <a href = "../../f_src/communicator_mpi/communicator_mpi.html">
      COMMUNICATOR_MPI</a>,
      a FORTRAN90 program which
      creates new communicators involving a subset of initial
      set of MPI processes in the default communicator MPI_COMM_WORLD.
    </p>

    <p>
      <a href = "../../f_src/heat_mpi/heat_mpi.html">
      HEAT_MPI</a>,
      a FORTRAN90 program which
      solves the 1D Time Dependent Heat Equation using MPI.
    </p>

    <p>
      <a href = "../../f_src/hello_mpi/hello_mpi.html">
      HELLO_MPI</a>,
      a FORTRAN90 program which
      prints out "Hello, world!" using the MPI parallel programming environment.
    </p>

    <p>
      <a href = "../../examples/moab/moab.html">
      MOAB</a>,
      examples which
      illustrate the use of the MOAB job scheduler for a computer cluster.
    </p>

    <p>
      <a href = "../../f_src/mpi/mpi.html">
      MPI</a>,
      FORTRAN90 programs which
      illustrate the use of the MPI application program interface
      for carrying out parallel computatioins in a distributed memory environment.
    </p>

    <p>
      <a href = "../../f_src/mpi_stubs/mpi_stubs.html">
      MPI_STUBS</a>,
      a FORTRAN90 library which
      contains "stub" MPI routines, allowing a user to compile, load, and possibly
      run an MPI program on a serial machine.
    </p>

    <p>
      <a href = "../../f_src/multitask_mpi/multitask_mpi.html">
      MULTITASK_MPI</a>,
      a FORTRAN90 program which
      demonstrates how to "multitask", that is, to execute several unrelated
      and distinct tasks simultaneously, using MPI for parallel execution.
    </p>

    <p>
      <a href = "../../f_src/prime_mpi/prime_mpi.html">
      PRIME_MPI</a>,
      a FORTRAN90 program which
      counts the number of primes between 1 and N, using MPI for parallel execution.
    </p>

    <p>
      <a href = "../../f_src/quad_mpi/quad_mpi.html">
      QUAD_MPI</a>,
      a FORTRAN90 program which
      approximates an integral using a quadrature rule, and carries out the
      computation in parallel using MPI.
    </p>

    <p>
      <a href = "../../f_src/random_mpi/random_mpi.html">
      RANDOM_MPI</a>,
      a FORTRAN90 program which
      demonstrates one way to generate the same sequence of random numbers
      for both sequential execution and parallel execution under MPI.
    </p>

    <p>
      <a href = "../../f_src/ring_mpi/ring_mpi.html">
      RING_MPI</a>,
      a FORTRAN90 program which
      uses the MPI parallel programming environment, and measures the time
      necessary to copy a set of data around a ring of processes.
    </p>

    <p>
      <a href = "../../f_src/satisfy/satisfy.html">
      SATISFY</a>,
      a FORTRAN90 program which
      solves the circuit satisfy problem.
    </p>

    <p>
      <a href = "../../f_src/search_mpi/search_mpi.html">
      SEARCH_MPI</a>,
      a FORTRAN90 program which
      searches integers between A and B for a value J such that F(J) = C,
      using MPI for parallel execution.
    </p>

    <p>
      <a href = "../../f_src/satisfy_openmp/satisfy_openmp.html">
      SATISFY_OPENMP</a>,
      a FORTRAN90 program which
      demonstrates, for a particular circuit, an exhaustive search
      for solutions of the circuit satisfy problem,
      using OpenMP for parallel execution.
    <p>

    <h3 align = "center">
      Reference:
    </h3>

    <p>
      <ol>
        <li>
          Michael Quinn,<br>
          Parallel Programming in C with MPI and OpenMP,<br>
          McGraw-Hill, 2004,<br>
          ISBN13: 978-0071232654,<br>
          LC: QA76.73.C15.Q55.
        </li>
      </ol>
    </p>

    <h3 align = "center">
      Source Code:
    </h3>

    <p>
      <ul>
        <li>
          <a href = "satisfy_mpi.f90">satisfy_mpi.f90</a>, the source code.
        </li>
      </ul>
    </p>

    <h3 align = "center">
      Examples and Tests:
    </h3>

    <p>
      <b>SATISFY_FSU</b> compiles and runs the program on the FSU HPC cluster.
      <ul>
        <li>
          <a href = "satisfy_fsu.sh">satisfy_fsu.sh</a>,
          the MOAB script.
        </li>
        <li>
          <a href = "satisfy_fsu_output.txt">satisfy_fsu_output.txt</a>,
          the output file.
        </li>
      </ul>
    </p>

    <p>
      <b>SATISFY_SYSX</b> compiles and runs the program on Virginia Tech's System X cluster.
      <ul>
        <li>
          <a href = "satisfy_sysx.sh">satisfy_sysx.sh</a>,
          the MOAB script.
        </li>
        <li>
          <a href = "satisfy_sysx_output.txt">satisfy_sysx_output.txt</a>,
          the output file.
        </li>
      </ul>
    </p>

    <p>
      You can go up one level to <a href = "../f_src.html">
      the FORTRAN90 source codes</a>.
    </p>

    <hr>

    <i>
      Last revised on 21 October 2011.
    </i>

    <!-- John Burkardt -->

  </body>

  <!-- Initial HTML skeleton created by HTMLINDEX. -->

</html>