Message Passing Interface

Z Multimediaexpo.cz

Message Passing Interface (dále jen MPI) je knihovna implementující stejnojmennou specifikaci (protokol) pro podporu paralelního řešení výpočetních problémů v počítačových clusterech. Konkrétně se jedná o rozhraní pro vývoj aplikací (API) založené na zasílání zpráv mezi jednotlivými uzly. Jedná se jak o zprávy typu point-to-point, tak o globální operace. Knihovna podporuje jak architektury se sdílenou pamětí, tak s pamětí distribuovanou (dnes častější). Z pohledu referenčního modelu ISO/OSI je protokol posazen do páté, tedy relační vrstvy, přičemž většina implementací používá jako transportní protokol TCP.

Toto API je nezávislé na programovacím jazyce, neboť se jedná především o síťový protokol. Nejčastěji se však setkáme s implementací v C, C++, Javě, Pythonu, Fortranu a výjimkou není ani podpora přímo na úrovni hardwaru. Při návrhu celého rozhraní i při jeho implementaci byl vždy kladen důraz především na výkon, škálovatelnost a přenositelnost. K nevýhodám, ale zároveň také výhodám této knihovny patří její nízkoúrovňový přístup. Nehodí se tedy pro rychlý vývoj aplikací (RAD), ale spíše pro aplikace, kde je rozhodující rychlost běhu aplikace, což je ale pro paralelní systémy typické. To je i možná důvodem, proč se stala v této oblasti de-facto standardem. Ke standardizačnímu řízení u některé ze známých organizací zabývajících se standardy, jako např. ISO, IEEE apod., však zatím nedošlo.

Historie

První návrh standardu MPI byl uveřejněn v časopise Supercomputing v roce 1994. V současné době existují dvě hojně používané verze: Starší verze 1.2 (často označovaná pouze jako MPI-1), která klade důraz na posílání zpráv, a verze 2.1 (často označovaná pouze jako MPI-2), která přináší navíc (mimo jiné) paralelní vstupně výstupní operace, dynamickou správu procesů a vzdálené operace s pamětí. Verze 1.2 obsahovala okolo 128 funkcí, zatímco verze 2.1 čítá více než 500 funkcí. Přičemž verze 2.1 zpětně kompatibilní s 1.2, čili programy napsané pro verzi 1.2 by měly s verzí 2.1 bez problému fungovat. Pouze budete u některých funkcí upozorněni, že jsou již zastaralé. Vzhledem ke stále velkému počtu aplikací psaných pro verzi 1.2 byla zpětná kompatibilita nutností.

Funkce a důležité rysy

Účelem rozhraní knihovny MPI je poskytnout nezbytnou virtuální topologii a funkce pro synchronizaci a komunikaci mezi množinou procesů (namapovaných na množinu počítačů) nezávisle na programovacím jazyce, avšak zároveň se přizpůsobit možnostem daných programovacích jazyků. MPI programy pracují vždy s procesy, ačkoli se často hovoří o procesorech. Pro dosažení nejlepšího výkonu je zapotřebí přidělit každému procesu jeden procesor, odpadá tím tak zpoždění způsobené přepínáním kontextu. K tomuto mapování však nedochází v době překladu aplikace ale v době běhu aplikace, a to prostřednictvím agenta, který MPI program spustil. Většinou se tento agent jmenuje mpirun nebo mpiexec.

Mezi funkce knihovny MPI patří:

• operace odeslání / přijetí point-to-point zprávy
• výběr mezi kartézskou a grafovou topologií procesů
• výměna dat mezi dvojicemi procesorů
• kombinování mezivýsledků výpočtů
• synchronizace uzlů
• získávání informací týkajících se sítě, jako např. počet procesů, identita procesoru, na kterém běží daný proces, seznam sousedních procesů, apod.

Operace point-to-point mohou být:

• blokující
• neblokující

Komunikátor (communicator)

Jednou z nejdůležitějších věcí pro pochopení knihovny MPI jsou komunikátory. Komunikátory jsou skupiny procesů při běhu MPI aplikace. Komunikátory se dají dynamicky vytvářet. Skupina MPI_COMM_WORLD existuje vždy a obsahuje všechny procesy dané aplikace. Proces je identifikován podle ranku, což je jeho pořadové číslo od nuly uvnitř skupiny. Pro komunikaci jsou pak k dispozici dva mechanismy: message passing a remote memory access. [6]

Point-to-point komunikace

Velká část funkcí v MPI je určena pro realizaci komunikace mezi dvěma procesy. Klasickým příkladem je funkce MPI_Send, která pošle zprávu od jednoho procesu jinému procesu. Často jsou tyto funkce používány programových architekturách typu master-slave, kde je řídící uzel zodpovědný za činnost svých „sluhů“. Typicky master pošle dávky instrukcí nebo dat každému podřízenému, počká až přijdou všechny odpovědi a pak je poskládá do jednoho celku.

Blokující funkce:

int MPI_Recv(void* buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status)
int MPI_Send(void* buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm)

Parametr buf je ukazatel na data která chceme odeslat, respektive na místo v paměti, kam chceme uložit přijatou zprávu. count udává počet přijatých hodnot, datatype jejich datový typ (pomocí vynásobení velikosti datového typu a počtu hodnot pak funkce zjistí kolik bajtů přečíst), source identifikuje proces, od kterého chceme číst (pomocí ranku – pořadového čísla), tag identifikuje zprávu a slouží spíše pro vizualizaci nebo ladění, comm je handle komunikátoru a konečně status obsahuje informaci o stavu operace.

Neblokující funkce:

int MPI_Irecv(void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Request *request)
int MPI_Isend(void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request *request)

Tyto funkce fungují stejně jako jejich blokující protějšky, pouze s tím rozdílem, že program nečeká na jejich dokončení.

Kolektivní komunikace

Mezi funkce pro hromadnou komunikaci patří například:

int MPI_Bcast(void* buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm);
int MPI_Scatter(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvcount, int root, MPI_Comm comm);
int MPI_Gather(void* sendbuf, int sendcount, MPI_Datatype sendype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm);
int MPI_Reduce(void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm)

• MPI_Bcast – Pošle zprávu od procesu s rankem 0 všem ostatním procesům ve skupině
• MPI_Scatter – Pošle data od jedné úlohy všem ostatním ve skupině
• MPI_Gather – Shromáždí hodnoty ze skupiny procesů
• MPI_Reduce – Zredukuje data všech procesů na jednu hodnotu. Operaci redukce si lze vybrat v parametru op

Datové typy

Implementace, aneb která je ta pravá?

Implementací MPI existuje celá řada, a proto zde zmíníme jen ty nejdůležitější: MPICH, LAM/MPI a OpenMPI.

MPICH

Je původní implementací standardu MPI 1.x. Správná výslovnost této zkratky má být „em pí aj sí ejč“, nikoli jako „m-pitch“. Tato implementace vznikla v Argonne National Laboratory a na vývoji se také podílela Mississippi State University. První ze zmíněných pak pokračovala ve vývoji celé následující desetiletí a nyní nabízí MPICH 2, jež implementuje standard MPI 2.1. Tato knihovna je například součástí distribuce Debian.

LAM/MPI

LAM/MPI je zkratka z Local Area Multicomputer / Message Passing Interface. Tato implementace vznikla v Ohio Supercomputing Center. Dále se na jejím vývoji podílely týmy z Ohio State University, University of Notre Dame a Indiana University Ti nyní také udržují webové stránky knihovny. Více o autorech lze najít v [1]. Podle informací dostupných na oficiálních webových stránkách projektu [2] však byl vývoj LAM/MPI zastaven (přijímají již pouze bezpečnostní záplaty) a snaha jeho vývojářů LAM/MPI se přesunula k projektu Open MPI (viz dále). Uživatelé LAM/MPI jsou zároveň vyzýváni k přechodu na Open MPI.

Pro komunikaci mezi výpočetními uzly LAM/MPI podporuje TCP/IP, sdílenou paměť, Myrinet (GM) a Infiniband (mVAPI). LAM/MPI implementuje kompletně MPI-1 a z velké části také MPI-2. Aplikace psané pro LAM/MPI jsou plně kompatibilní a snadno portovatelné na jiné implementace standardu MPI. Navíc však LAM/MPI přidává kvalitní podporu ladění. Monitorování probíhá na dvou úrovních: Jednak knihovna dokáže kdykoli pozastavit proces a vytvořit jeho snímek (angl. snapshot) a odeslat informace o jeho stavu. Takovýto snapshot pak obsahuje veškeré aspekty synchronizace, členství ve skupinách komunikátorů a také obsah zpráv. A za druhé, knihovna MPI je navržena tak, aby mohla poskytnout globální záznam veškeré komunikace, a to jak za běhu, tak po jeho skončení. Tento záznam může být dokonce vizualizován.

Open MPI

Open MPI je poměrně nový, avšak slibný projekt, který se pokouší o spojení několika ostatních implementací MPI (FT-MPI, LA-MPI, LAM/MPI a PACX-MPI) s tím, že z každé implementace si vezme to, v čem je nejlepší. Vznikla tak kompletně nová implementace MPI-2. Za jejím vývojem stojí celé konsorcium firem a univerzit, mezi něž patří i např. University Of British Columbia, Cisco, IBM nebo Sun Microsystems. Kompletní seznam organizací podílejících se na vývoji lze najít v [3].

Její vývoj začal v říjnu roku 2005 [4]. V březnu roku 2006 spatřilo světlo světa verze 1.0. Vývoj pak pokračoval plynule dále. Sedmého dubna 2008 pak vyšla momentálně (v době psaní tohoto textu) aktuální stabilní verze 1.2.6. Kromě toho je také možné si stáhnout nestabilní snapshot vývojové verze, který vychází každý den, nebo rovnou získat aktuální obsah vývojového repozitáře pomocí SVN. Tato knihovna je také součástí mnoha populárních distribucí Linuxu (Fedora, Ubuntu, openSUSE...).

Příklady

Poznámka: následující příklady byly testovány pouze na Open MPI, a proto nemusejí fungovat správně s jinými implementacemi.

Hello World

Kostra aplikace

Prvním krokem úspěšného vytvoření MPI aplikace je instalace potřebných knihoven. Instalace z vaší distribuce bude pravděpodobně nejrychlejší, kdežto instalace kompilací zdrojových kódů stažených přímo z oficiálních stránek vám přinese nejčerstvější verzi. Dále je potřeba vytvořit soubor obsahující zdrojový text, např. main.c, do kterého napíšeme standardní kostru programu v jazyce C a navíc přidáme tyto tři řádky:

• na začátek souboru: #include <mpi.h> // dovoz rozhraní MPI
• na začátek funkce main: MPI_Init(&argc, &argv); // inicializace knihovny
• na konec funkce main: MPI_Finalize(); // ukončení práce s MPI

Tím jsme získali minimální kostru MPI aplikace.

Kompilace a spuštění

K běhu takovéto aplikace nám bude stačit jeden počítač. Kompilace se provede příkazem: $ mpicc main.c Spuštění pak jako obvykle: $ ./a.out

V případě, že budeme chtít v programu používat více procesů a tedy i počítačů (kvůli tomu jsme přeci MPI instalovali…), musíme nejprve vytvořit soubor openmpi_hosts, do kterého dáme jména těchto počítačů a kolik slotů mají používat. Jestliže potřebujeme používat více strojů, ale máme jen jeden, můžeme využít možnost takzvaných slotů: jednoduše napíšeme, kolik procesů může běžet na kterém stroji. Takže jestliže potřebujeme deset procesů a všechny na našem počítači, napíšeme do openmpi_hosts pouze toto:

localhost slots=10

Takto můžeme pro každý počítač specifikovat počet procesů na něm běžících. Takže takový soubor pak může vypadat například takto:

# Sample hostfile for OpenMPI
localhost slots=1
merlin    slots=2
eva       slots=2
adela     slots=2

V tomto případě však již nemůžeme aplikaci spouštět jako předtím, ale musíme k tomu použít již výše zmíněný démon mpiexec:

mpiexec --hostfile openmpi_hosts -np 10 ./a.out

Parametr -np pak udává, kolik kopií programu se má spustit a parametr - -hostfile udává cestu k souboru mapujícímu procesy na hosty.

 HelloWorld

Nyní již známe některé základní funkce knihovny MPI a také jak aplikaci zkompilovat a spustit, a proto si již můžeme vytvořit legendární Hello World (dle anglické wikipedie):

/*
  "Hello World" s využitím MPI
 */
 #include <mpi.h>
 #include <stdio.h>
 #include <string.h>
 
 #define BUFSIZE 128
 #define TAG 0
 
 int main(int argc, char *argv[])
 {
   char idstr[32];
   char buff[BUFSIZE];
   int numprocs;
   int myid;
   int i;
   MPI_Status stat; 
 
   MPI_Init(&argc,&argv); /* inicializace MPI */
   MPI_Comm_size(MPI_COMM_WORLD,&numprocs); /* zjistíme, kolik procesů běží */
   MPI_Comm_rank(MPI_COMM_WORLD,&myid); /* zjistíme id svého procesu */
 
   /* Protože všechny programy mají stejný kód (Same Program, Multiple Data – SPMD) rozdělíme činnost
      programů podle jejich ranku. Program s rankem 0 rozešle postupně všem zprávu a přijme od všech
       odpověď 
   */
   if(myid == 0)
   {
     printf("%d: We have %d processors\n", myid, numprocs);
     for(i=1;i<numprocs;i++)
     {
       sprintf(buff, "Hello %d! ", i);
       MPI_Send(buff, BUFSIZE, MPI_CHAR, i, TAG, MPI_COMM_WORLD);
     }
     for(i=1;i<numprocs;i++)
     {
       MPI_Recv(buff, BUFSIZE, MPI_CHAR, i, TAG, MPI_COMM_WORLD, &stat);
       printf("%d: %s\n", myid, buff);
     }
   }
   else
   {
     /* obdržíme zprávu od procesu s rankem 0: */
     MPI_Recv(buff, BUFSIZE, MPI_CHAR, 0, TAG, MPI_COMM_WORLD, &stat);
     sprintf(idstr, "Processor %d ", myid);
     strcat(buff, idstr);
     strcat(buff, "OK\n");
     /* Odpovíme na zprávu: */
     MPI_Send(buff, BUFSIZE, MPI_CHAR, 0, TAG, MPI_COMM_WORLD);
   }
 
   MPI_Finalize(); 
   return 0;
 }

Program zkompilujeme a spustíme:

[michel@localhost pokusy]$ mpicc HelloWorld.c && mpiexec --hostfile openmpi_hosts -np 4 ./a.out
0: We have 4 processors
0: Hello 1! Processor 1 OK
 
0: Hello 2! Processor 2 OK
 
0: Hello 3! Processor 3 OK
 
[michel@localhost pokusy]$

Suma řady čísel

#include <stdio.h>
#include <mpi.h>
 
#define N 100000
#define MSG_DATA 100
#define MSG_RESULT 101
 
void master (void);
void slave (void);
 
int main(int argc, char *argv[]){
  int myrank;
  // initializace
  MPI_Init (&argc, &argv);
  // pořadí tohoto procesu
  MPI_Comm_rank (MPI_COMM_WORLD, &myrank);
 
  if (myrank == 0)
    master ();
  else
    slave ();
  MPI_Finalize ();
  exit (1);
}
 
/* rozdeluje praci sluhum */
void master (void) {
  float array[N];
  double mysum = 0, tmpsum;
  unsigned long long i;
  MPI_Status status;
  // Naplneni pole
  for (i = 0; i < N; i++)
    array[i] = i + 1;
  // Pole rozdelime na dve poloviny a kazdou posleme jednomu sluhovi
  MPI_Send (array, N / 2, MPI_FLOAT, 1, MSG_DATA, MPI_COMM_WORLD);
  MPI_Send (array + N / 2, N / 2, MPI_FLOAT, 2, MSG_DATA, MPI_COMM_WORLD);
  // Vyzvedneme si vysledky od sluhu
  MPI_Recv (&tmpsum, 1, MPI_DOUBLE, 1, MSG_RESULT, MPI_COMM_WORLD, &status);
  mysum += tmpsum;
  MPI_Recv (&tmpsum, 1, MPI_DOUBLE, 2, MSG_RESULT, MPI_COMM_WORLD, &status);
  mysum += tmpsum;
  printf ("%lf\n", mysum);
}
 
/* kod sluhu – sectou cast pole kterou obdrzeli a vrati panovi */
void slave (void) {
  float array[N];
  double sum;
  unsigned long long i;
  MPI_Status status;
  // prijmeme polovicku pole
  MPI_Recv (array, N / 2, MPI_FLOAT, 0, MSG_DATA, MPI_COMM_WORLD, &status);
  for (i = 0, sum = 0; i < N / 2; i++)
    sum += array[i];
  // vratime vysledek panovi
  MPI_Send (&sum, 1, MPI_DOUBLE, 0, MSG_RESULT, MPI_COMM_WORLD);
}

Alternativy

Ačkoli je standard MPI v oblasti paralelního počítání velmi rozšířený, není jediným. Jeho hlavním „konkurentem“ je systém PVM.

Literatura

1. Seznam autorů LAM/MPI. Dokument dostupný na URL http://www.lam-mpi.org/about/devel/ (duben 2008)
2. Oficiální stránky projektu LAM/MPI. Dokument dostupný na URL http://www.lam-mpi.org/ (duben 2008)
3. Seznam organizací podílejících se na vývoji Open MPI. Dokument dostupný na URL http://www.open-mpi.org/about/members/ (duben 2008)
4. Open MPI: Version Timeline. Dokument dostupný na URL http://www.open-mpi.org/software/ompi/versions/timeline.php (duben 2008)
5. MPI: A Message Passing Interface Standard. Dokument dostupný na URL http://www.mpi-forum.org/docs/mpi-10.ps (duben 2008)
6. Skripta předmětu Middleware z MFF UK. Dokument dostupný na URL http://dsrg.mff.cuni.cz/~ceres/sch/mwy/text/ch06s07.php (duben 2008)