• Linux, Open MPI Entwicklerpakete installieren (Ubuntu: openmpi-bin openmpi-doc libopenmpi-dev)
• passwortloser SSH-Zugriff auf beteiligte Maschinen

Das OpenMP-Programm wurde für MPI nach einem Client/Server-Ansatz umgeschrieben. Vom Master-Prozess werden einzelne Zeilen(nummern) an Slave-Prozesse übergeben, die berechnete Zeilen als Felder zurückliefern.

//: mpi_mandelbrot.cpp : Demo Open MP / Open MPI - R.Richter 2011-01-20
///////////////////////////////////////////////////////////////////////
// g++ -fopenmp ... für Open MP
// mpic++ ...       für Open MPI
 
#define USE_MPI
 
#include <iostream>
#include <complex>
#include "image.h"
 
#ifdef USE_MPI
  #include <mpi.h>
  char processorName[MPI_MAX_PROCESSOR_NAME] = "myHostName";
#endif
 
#define MASTER   0
#define GOTOWORK 1
#define GOTODIE  2
 
typedef std::complex<double> complex;
 
int compute(complex c, int maxIterations)
{
  int count = 0;
  complex z; 
 
  while (abs(z) <= 2.0 && count < maxIterations) 
  {
    z = z * z + c;
    ++ count;
  }
  return count;
}
 
inline 
Color color(int height, int max)
{
  // color scheme from: 
  // http://shreyassiravara.wordpress.com/2010/08/14/the-mandelbrot-set/
  if (height >= max) return Color::BLACK;
  double h = 255 * log(double(height)) / log(double(max)); 
  return Color(0.9 * h, 0.8 * h, 0.6 * h);
}
 
inline
double scale(int pos, int length, double low, double high)
{
  return low + pos * (high-low) / (length-1);
}
 
#ifdef USE_MPI
 
void send(int line, int size, int task, int tag)
{
  MPI_Send(&line, size, MPI_INT, task, tag, MPI_COMM_WORLD);
  if (tag == GOTOWORK) 
  {
    std::cout << "Line " << line 
              << " sent to process " << task << std::endl;
  }
}
 
int incoming(std::vector<int>& results)
{
  MPI_Status status;
  MPI_Recv(&results[0], results.size(), MPI_INT, 
           MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
 
  int task = status.MPI_SOURCE;
  std::cout << "Line " << results[results.size() - 1] 
            << " received from process " << task 
            << " (" << processorName << ")" << std::endl;
  return task;  
}
 
void process(Image& image, std::vector<int> const& iterations, int max)
{
  int const width = iterations.size() - 1;
  int const y = iterations[width];
  for (int x = 0; x < width; ++x)
  {
    image.pixel(x, y) = color(iterations[x], max);   
  }
}
 
#endif // USE_MPI
 
void master(int nProcesses)
{
  std::cout << "starting master of " << nProcesses << " tasks" << std::endl;
 
  int width  = 500;
  int height = 500;
  Image image(width, height);
  int maxIterations = 10000;
  complex left_bottom(-2.0, -2.0);
  complex right_top  ( 2.0,  2.0);
 
#ifndef USE_MPI
 
  // serial program or shared-memory parallelism with Open MP:
  #pragma omp parallel for
  for (int y = 0; y < height; ++y)
  {
    for (int x = 0; x < width; ++x)
    {
      complex c(scale(x, width,  real(left_bottom), real(right_top)),
                scale(y, height, imag(left_bottom), imag(right_top)));
 
      int iterations = compute(c, maxIterations);
      image.pixel(x, y) = color(iterations, maxIterations);   
    }
  }
 
#else // USE_MPI
 
  // broadcast global data to all other processes
  int    buffer1[3] = { width, height, maxIterations };
  double buffer2[4] = { real(left_bottom), imag(left_bottom),
                        real(right_top), imag(right_top) };
 
  MPI_Bcast(buffer1, 3, MPI_INT,    MASTER, MPI_COMM_WORLD);
  MPI_Bcast(buffer2, 4, MPI_DOUBLE, MASTER, MPI_COMM_WORLD);
 
  // distribute first lines to all other processes
  int line = 0;
  for (int task = 1; task < nProcesses; ++task, ++line)
  {
    send(line, 1, task, GOTOWORK);
  }
 
  std::vector<int> results(width + 1); // iterations + lineNr
 
  for ( ; line < height; ++line)  // until all lines processed 
  {
    int task = incoming(results);
    send(line, 1, task, GOTOWORK);
    process(image, results, maxIterations);
  }
 
  for (int task = 1; task < nProcesses; ++task)  // all outstanding tasks
  {
    incoming(results);
    send(0, 0, task, GOTODIE);
    process(image, results, maxIterations);
  }
 
#endif // USE_MPI
 
  saveBMP("mandel.bmp", image);
}
 
void slave(int myId)
{
  std::cout << "starting slave " << myId << std::endl;
#ifdef USE_MPI
 
  // get global data broadcasted from master
  int    buffer1[3];
  double buffer2[4];
 
  MPI_Bcast(buffer1, 3, MPI_INT,    MASTER, MPI_COMM_WORLD);
  MPI_Bcast(buffer2, 4, MPI_DOUBLE, MASTER, MPI_COMM_WORLD);
 
  int width           = buffer1[0];
  int height          = buffer1[1];
  int maxIterations   = buffer1[2];
  complex left_bottom ( buffer2[0], buffer2[1]);
  complex right_top   ( buffer2[2], buffer2[3]);
 
  while (true)
  {
    // get work : line number
    MPI_Status status;
    int y;
    MPI_Recv(&y, 1, MPI_INT, 
             MASTER, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
 
    if (status.MPI_TAG == GOTODIE) break;   
 
    // do work : compute a vector of data
    std::vector<int> iterations(width + 1);
    iterations[width] = y; // store line number for return here  
 
    for (int x = 0; x < width; ++x)
    {
      complex c(scale(x, width,  real(left_bottom), real(right_top)),
                scale(y, height, imag(left_bottom), imag(right_top)));
 
      iterations[x] = compute(c, maxIterations);
    }
    // send results
    MPI_Send(&iterations[0], width+1, MPI_INT, MASTER, 0, MPI_COMM_WORLD);
  }
 
#endif // USE_MPI
}
 
int main(int argc, char* argv[])
{
  int nProcesses = 1;
  int myId = MASTER;
 
#ifdef USE_MPI  
  MPI_Init(&argc, &argv);
  MPI_Comm_size(MPI_COMM_WORLD, &nProcesses);
  MPI_Comm_rank(MPI_COMM_WORLD, &myId);  
  int nameLength = MPI_MAX_PROCESSOR_NAME;
  MPI_Get_processor_name(processorName, &nameLength);
#endif
 
  std::cout << "Hello from process " << myId 
            << " of " << nProcesses << std::endl;
 
  if (myId == MASTER) master(nProcesses);
  else                slave(myId);
 
#ifdef USE_MPI
  MPI_Finalize();
#endif
  return 0;
}

mpic++ hello.cpp -o hello

Das Programm kann lokal unter Angabe der gewünschten Prozessanzahl (beim Master/slave-Ansatz mindestens 2) gestartet werden.

mpirun -np 8 mpi_mandelbrot 

Zum verteilten Ausführen muss das Programm auf allen beteiligten Maschinen vorhanden sein und passwortloser SSH-Zugang (siehe unten) auf die Maschinen möglich sein. Das Machinefile listet die beteiligten Maschinen mit Hostname oder IP-Addresse auf:

# my_hostfile 
192.168.0.205
192.168.0.208 slots=4 max_slots=8

Die Angabe der (maximal) zu startenden Prozesse ist optional. Der Programmstart erfolgt mit

mpirun --hostfile my_hostfile mpi_mandelbrot

oder

mpirun --machinefile my_hostfile mpi_mandelbrot

Die Ausgaben aller Programme erscheinen auf der Konsole des MPI-Hauptprozesses.

1. auf dem Master-System ein SSH-Schlüsselpaar erzeugen (ablegen unter ~/.ssh)

ssh-keygen -t rsa

2. mit Editor Inhalt von ~/.ssh/rsa.pub auf Zielsystem in ~/.ssh/authorized_keys2 einfügen

Die Ausführung erfolgte in Ubuntu innerhalb eines VirtualBox-Systems.

Die MPI-Version benötigte auf der Einzelmaschine mit 8 Prozessen 100 Sekunden. Zum Vergleich dazu die OpenMP-Version 88 Sekunden. Da VirtualBox nur einen CPU-Kern des Hostsystems (AMD Turion 64, 2.1 GHz unter Windows 7 64bit) auslastet, ist dieser Zeitbedarf mit einem Einzelprozess auf dem Hostsystem vergleichbar.

Auf mehrere Maschinen (virtuelle und native Linux-Systeme) verteilt, verkürzt sich die Gesamtrechenzeit. Vor der ersten Rückmeldung der Client-Prozesse vergehen allerdings einige Sekunden für den Aufbau der SSH-Verbindung.

• http://www.open-mpi.org/
• http://bisseling.de/georg/mpitutorial/tutorial.pdf
• http://www.cs.ucsb.edu/~hnielsen/cs140/openmpi-install.html
• http://www.lam-mpi.org/tutorials/one-step/ezstart.php
• http://pl.postech.ac.kr/~gla/cs700-07f/resources.html
• http://www-uxsup.csx.cam.ac.uk/courses/MPI/Programs/mandelbrot.cpp
• http://stackoverflow.com/questions/4568645/printing-1-to-1000-without-loop-or-conditionals/4580366#4580366