# Message Passing Interface

MPI (Message-Passing Interface, interfície de pas de missatges) és una especificació d'interfície de biblioteca en el que totes les operacions són expressades com a funcions, subrutines o mètodes enllaçats normalment als llenguatges C i Fortran. Cal destacar que aquesta especificació és la més utilitzada actualment per a la programació concurrent en entorns en la que la comunicació es fa a través de missatges i se la considera l'estàndard de referència.
L'objectiu principal de l'MPI és formar un estàndard que sigui àmpliament utilitzat en programes que requereixin utilitzar missatges per comunicar-se, per això, la interfície intenta ser pràctica, portable, eficient i flexible per tal d'incrementar la productivitat a l'hora de fer aquest tipus d'algoritmes.
Els altres objectius de l'MPI es poden trobar en la següent llista:
* Dissenyar una interfície de programació d'aplicacions
* Permetre una comunicació eficient: això s'assoleix evitant les còpies de memòria a memòria, permetent solapar la comunicació amb la computació i afegir sobrecarrega per permetre la comunicació dels co-processadors quan sigui possible
* Permetre que les implementacions es puguin utilitzar en entorns heterogenis
* Permetre dotar als llenguatges C i Fortran de directives convenients
* Assolir una interfície de comunicació fiable: l'usuari no necessita bregar amb els errors de les comunicacions, ja que aquestes comunicacions es fan en un subsistema de comunicació intern
* Definir una interfície que pugui ser implementada en qualsevol plataforma dels venedors sense haver de modificar les comunicacions internes i el software del sistema
* La semàntica de la interfície hauria de ser independent del llenguatge
* La interfície hauria de ser dissenyada per assegurar la seguretat dels threads

## Història

La estandardització de la interfície de pas missatges va començar-se a desenvolupar gràcies al patrocini del Centre d'Investigació en Computació Paral·lela de Williamsburg, Virgínia, Estats Units (Abril 29-30 de 1992). Va sorgir la primera versió preliminar, anomenada MPI1, que estava principalment enfocada a les comunicacions Punt-A-Punt, sense incloure rutines de comunicació col·lectiva. L'estàndard final va ser presentat a la conferencia de Supercomputació al 1993.
A causa de la utilitat i potencial d'aquest projecte, es va continuar actualitzant aquest estàndard de comunicació. D'aquesta manera, al 1994 es va publicar el MPI-1 i, al 1997, el MPI-2, (entre aquestes dues versions només va haver-hi correccions i aclariments). La versió MPI-2 va comportar noves funcionalitats referents a la creació i manteniment dels processos, un nou tipus de comunicació (comunicació a una banda, també denominada RMA de l'anglés Remote Memory Access), comunicacions col·lectives ampliades, interfícies externes i entrada/sortida paral·lels (I/O). Las posteriors versions d'MPI, que van ser la 2.1 i la 2.2, només van comportar canvis menors i petites correccions.
A l'any 2012 sorgí la versio MPI-3, que va comportar canvis significatius a l'estàndard d'MPI, com per exemple la comunicació col·lectiva no bloquejant, noves operacions de comunicació a una banda, nous vincles amb el llenguatje Fortran 2008, entre d'altres. La versió MPI-3.1 va introduir també operacions d'entrada-sortida col·lectives no bloquejants.
Actualment s'està desenvolupant la versió MPI-4.0, on s'està treballant en aspectes com noves extensions per un millor suport a models de programació híbrida, suport per la tolerància a fallades en aplicacions MPI, funcions col·lectives persistents i comunicació a una banda.

## Conceptes

MPI ofereix una extensa gamma d'habilitats. Els següents conceptes ajuden a la comprensió i proporcionen un context per a totes aquestes habilitats, ajudant al programador per decidir quina funcionalitat utilitzar en els seus programes.

### Funcions bàsiques

| Funció | Definició |
| int MPI_Init(int *argc, char **argv) | Inicialitza MPI |
| int MPI_Finalize | Finalitza MPi, i ha de ser cridada per tots els procesos que formen part del programa MPI. |

### Missatges

Els missatges en MPI consten de dues parts diferenciades:
* La capçalera: està dividida en quatre camps, on cadascun dels quals conté les dades que indiquen el procés que envia les dades del missatge, el procés que les ha de rebre, el comunicador pel qual s'envien aquestes dades i l'etiqueta (tag en anglès, que permet distinguir entre diferents tipus de missatge), respectivament.
* Cos: aquest conté tres parts que són el buffer, que conté les dades a enviar, el datatype (el tipus de dada que hi ha al buffer) i count, que indica el nombre d'elements d'aquest tipus que hi ha al buffer.

### Tipus de comunicació

A MPI, podem dividir les comunicacions per dos característiques en concret:
* Nombre de processos implicats: exsisteixen les comunicacions punt-a-punt, en el que un procés envia un missatge a un altre procés, i aquell el rep, i la comunicació col·lectiva, on s'involucren un grup de processos per repartir-se feina, distribuir conjunts de dades, retrasmetre dades d'un procés a la resta, etc.
* Bloquejant i no bloquejant: les funcions que impliquen comunicació bloquejant (send, per exemple), no retornaràn fins que la comunicació s'hagi completat (bloquejant el procés fins al final de la comunicació, i confirmant l'èxit o fallada de la comunicació), mentre que les no-bloquejants inicien la comunicació i retornen immediatament, però no es pot saber si la comunicació s'ha completat amb èxit, i s'ha de comprovar d'altres maneres (amb funcions com MPI_Wait, que esperar a la finalització d'una petició de dades i MPI-Test, que serveix per compovar la finalització de la petició). La comunicació no bloquejant permet als processos continuar fent còmput i esperar a la finalització d'aquesta, permetent solapar còmput amb comunicació.

### Grups

Els grups són els conjunts de processos que formen part dels programes MPI i estan inclosos als comunicadors. Els grups no es poden crear de zero, i s'han de fer a partir de subgrups d'un ja exsistent, per exemple, el grup de processos que inicialment estiguin presents al programa MPI. Alguns exemples de funcions associades als grups són:
| Funció | Definició |
| int MPI_Comm_group(MPI_Comm comm, MPI_Group *group) | Retorna el a group el grup de processos associat al comunicador comm. |
| int MPI_Group_union(MPI_Group group1, MPI_Group group2, MPI_Group *newgroup) | Crea un grup de processos nou a partir dels processos presents a group1 o a group2, i els col·loca a newgroup. |
| int MPI_Group_intersection(MPI_Group group1, MPI_Group group2,MPI_Group *newgroup) | Crea un nou grup de processos newgroup a partir dels processos que pertanyin a group1 que també estiguin a group2, i els col·loca al newgroup. |
| int MPIAPI MPI_Group_difference(MPI_Group group1,MPI_Group group2, MPI_Group *newgroup) | Crea un nou grup de processos newgroup a partir dels processos presents a group1 que no estiguin a group2 i els col·loca al newgroup. |

### Comunicador

El comunicador es un objecte (MPI_Comm en C) que descriu una estructura de comunicació per a un grup de processos. Aquests processos dins del comunicador son capaços d'enviar-se i rebre missatges, essent una estructura básica en MPI. Els comunicadors formen part dels handlers (que són els apuntadors a les estructures de dades que MPI crea i manté per establir la comunicació entre els diferents processos del programa), i estan composts per un group (els procesos que participen en aquell comunicador en concret), y el seu context (comunicació punt-a-punt o col·lectiva). El comunicador predefinit a MPI es MPI_COMM_WORLD, que engloba tots els processos que inicialment formen part d'un programa MPI.
El comunicador dona a cadascun dels seus processos un identificador i els ordena formant una topologia. A més, MPI també té grups explícits, però s'utilitzen principalment per organitzar grups de processos abans que un altre comunicador els adopti. MPI comprèn les operacions de comunicació dins del comunicador, així com les comunicacions bilaterals entre comunicadors. Al MPI-1, són més utilitzades les comunicacions internes, mentre que al MPI-2 són més comuns les comunicacions bilaterals, ja que inclou mètodes de gestió de comunicacions col·lectives. A partir de l'MPI-3, també s'inclouen les comunicacións col·lectives no bloquejants.
Algunes de les funcions per crear o gestionar els comunicadors i els processos corresponents són:
| Funció | Definició |
| int MPI_Comm_size(MPI_Comm comm, int *size) | Retorna a size la mida (el nombre de processos) que té el comunicador a qui es fa referència al paràmetre comm. |
| int MPI_Comm_rank(MPI_Comm comm, int *rank) | Retorna el valor del rang que té el procés que fa la crida a la funció al comunicador indicat per comm. |
| int MPI_Comm_create(MPI_Comm comm, MPI_Group group, MPI_Comm *newcomm) | Crea un nou comunicador a partir del grup de procesos indicat per group, i retorna el handle corresponent a aquest comunicador al paràmetre newcomm. |
| int MPI_Comm_split(MPI_Comm comm, int color, int key, MPI_Comm *newcomm) | Divideix els processos que pertanyen al comunicador apuntat per comm en diferents subgrups (indicat pel paràmetre color), ordenats en cada subgrup pel valor que tingui el paràmetre key (el nou rank dins d'aquest subgrup). Per a cada subgrup es crea un nou comunicador newcomm (amb el seu corresponent handle). |
| int MPI_Comm_dup(MPI_Comm comm,MPI_Comm *newcomm) | Crea un nou comunicador newcomm a partir de comm, amb el mateix grup de processos i la mateixa informació que tingui emmagatzemada, però amb un context diferent. |

### Bàsiques Punt-a-Punt

Un gran nombre de funcions MPI involucren la comunicació entre dos processos. Un exemple popular és MPI_Send, que permet que un procés enviï un missatge a un altre procés, iMPI_Recv, que permet rebre aquests missatges. Les operacions Punt-a-Punt, que així és com s'anomenen, són particularment útils en comunicacions regulars com, per exemple, una arquitectura amb dades en paral·lel en la qual cada processador intercanvia rutinàriament regions de dades amb altres processadors després de realitzar certs càlculs, o una arquitectura Mestre/Esclau, on el mestre envia dades d'una tasca a un esclau cada cop que aquest acaba amb la tasca a la qual està treballant.
MPI-1 té especificats mecanismes tant per sistemes de comunicacions Punt-a-Punt bloquejats i no, com el mecanisme denominat "Llest-Enviat", on una sol·licitud d'enviament només pot fer-se quan una resposta de recepció d'aquella mateixa transmesa ha sigut rebuda.
No només hi ha un tipus de send. A més del send tradicional, es troben:
* MPI_Bsend(Buffered send): aquest tipus de funció send es completa quan es copia el missatge al buffer, pero s'han de prendre altres tipus de mesures, com assegurar-se de que existeix un buffer adequat i controlar la mida d'aquest buffer.
* MPI_SSend(Synchronous send): el Synchronous send es completarà quan s'hagi rebut el missatge per part del receptor, i es una bona opció si es vol assegurar que els missatges arriben correctament.
* MPI_RSend(Ready Send): aquest tipus de send només s'iniciarà amb èxit si ja hi ha prèviament una proposta de recepció (recv) que li correspongui. Aquest tipus de send comporta que el programador hagi de sincronitzar els processos perque el receptor faci la petició (recv) abans que s'iniciï el send.
Aquests tipus de send son bloquejants (no permeten que el programa continui fins que finalitzin), però tenen la seva versió no bloquejant corresponent (MPI_Ibsend, MPI_Issend, MPI_Irsend).
| Funció | Definició |
| int MPI_Send (void *buf,int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm) | Envia, mitjançant un missatge MPI, les dades apuntades per buf, on count representa el nombre d'elements a enviar, datatype el tipus de dades que s'envien, dest el rang del procés que l'ha de rebre, tag el tipus de missatge, i comm el comunicador per on s'enviaran les dades. |
| int MPI_Recv (void *buf,int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status) | Rep un missatge MPI, guardant-lo a buf, on els parámetres representen el mateix que a la funció send (al parámetre tag es pot col·locar MPI_ANY_TAG si es vol rebre missatges amb qualsevol tag), i source representa el rang del procés de que s'han de rebre les dades (es pot posar MPI_ANY_SOURCE si es vol rebre de qualsevol procés), mentre que status és un objecte que conté dades com la font, el tag i el count corresponent al missatge. |

### Bàsiques de comunicació col·lectiva

Les funcions col·lectives involucren comunicacions entre tots els processos d'un grup de procés. Una funció típica és l'anomenada MPI_Bcast (abreviatura de l'angles "Broadcast"). Aquesta funció pren les dades d'un node i les envia a tots els processos d'un grup de procés. Una operació inversa és MPI_Reduce, que pren les dades de tots els processos d'un grup, realitza una operació amb ells i emmagatzema els resultats en un únic node. MPI_Reduce sovint és útil a l'inici o al final d'un gran càlcul distribuït, on cada processador treballa amb una porció de les dades i, a continuació, és combinen tots els resultats. Les funcions de comunicació col·lectiva han de ser cridades per tots els processos presents al comunicador.
Hi ha operacions més sofisticades, com MPI_Alltoall, que reorganitza n elements de dades tals que el node n-èsim obté l'element n-èsim de les dades. Algunes de les funcions de comunicació col·lectiva que hi ha són:
| Funció | Definició |
| int MPI_Bcast (void *buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm) | Aquesta funció fa que el procés identificat amb el rang root enviï a la tots els procesos les dades a les que l'apuntador buffer fa referència, on s'envien count elements del tipus determinat pel paràmetre datatype, a través del comunicador comm. |
| int MPI_Scatter(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm) | Aquesta funció fa que el procés de rang root enviiï a cada procés del comunicador comm una quantitat d'elements igual al paràmetre sendcount, del tipus especificat a sendtype, que formen part de les dades que hi ha apuntades pel buffer sendbuf. És a dir, el procés root enviarà una fracció de les dades originals a cada procés. Les dades rebudes mitjançant la crida a aquesta funció es col·locaran al buffer recvbuf de cada procés. |
| int MPI_Gather (void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm) | La funció gather fa que el procés de rang root reculli de cada procés present al comunicador comm una quantitat de dades representades al parámetre sendcount (cada procés envia les dades a les que apunta el seu buffer sendbuf)', de tipus datatype. Els paràmetres recvbuf i recvcount indiquen el buffer on es guardaran totes les dades i el nombre d'elements a rebre per procés, respectivament. |
| int MPI_Allgather(void*sendbuf,int sendcount, MPI_Datatype sendtype) | Aquesta variant de la funció gather fa que tots els procesos rebin les mateixes dades que rebia només un procés a la funció gather. |

### Tipus de dades derivades

Moltes funcions MPI requereixen que s'especifiqui el tipus de dades que s'enviaran entre processos. El motiu d'això és que MPI té com a objectiu el suport a entorns heterogenis on les dades poden ser representades de maneres diferents a cada node (per exemple, poden tenir diferents arquitectures de CPU amb ordres de bytes diferents). Per això, MPI permet crear dades personalitzades anomenades derived datatypes (tipus de dades derivades), que permeten definir-li a MPI nous tipus de dades que tenim als nostres programes que MPI no reconeix inicialment. Els mètodes per crear nous tipus de dades són els següents:
| Funció | Definició |
| int MPI_Type_contiguous(int count, MPI_Datatype old_type,MPI_Datatype *new_type_p) | Crea un nou tipus de dades en new_type_p que representa count vegades el tipus de dades representat a old_type, és a dir, count elements consecutius en memòria. |
| int MPI_Type_vector(int count,int blocklength, int stride, MPI_Datatype oldtype, MPI_Datatype * newtype) | Crea un tipus de dades que representa count elements que són d'una mida blocklength. Cadascun d'aquest elements es troba separat per una distància representada pel paràmetre stride del següent, permetent fer salts regulars i enllaçant elements distants en memòria. |
| int MPI_Type_indexed(int count, int blocklengths,int offset,MPI_Datatype old_type, MPI_Datatype *newtype)= | Crea un datatype de count blocs d'elements, que poden ser de diferent mida segons el que indiqui la posició respectiva de blocklengths (per exemple, el valor de blocklens[0] representa la mida de l'element 0). Cadascun d'aquests blocs esta a una distància de la posició de memòria inicial del datatype representada en offset (de la mateixa manera que la mida en blocklengths), essent del tipus indicat a old_type. |
| int MPI_Type_create_struct(int count, int blocklengths, MPI_int offsets,MPI_Datatype datatypes,MPI_Datatype *newtype) | Crea un datatype que representa una estructura de dades de count elements, amb els seus respectius blocklenghts respresentats a l'array blocklengths (blocklengths[0] = mida de l'element 0), amb diferents offsets (posició de memòria on comencen respecte la posició inicial del datatype). A diferencia de indexed, aquest datatype pot contenir més d'un tipus de dada diferent (datatypes[0] = tipus de dada de l'element 0). |
Els passos que se segueixen per crear, utilitzar y alliberar un datatype són els següents:
* Primer l'hem declarar el nou datatype (MPI_Datatype nomdataype).
* Després hem de decidir de quin tipus de datatype utilitzarem i activar-lo amb la funció MPI_Commit(MPI_datatype *datatype).
* Fem ús en les diverses funcions del nostre programa.
* Quan ja no fem servir més aquest tipus de dada, alliberem el datatype mitjançant la funció MPI_Type_free (MPI_datatype *datatype).

## Informació Bàsica per la implementació
### Tipus de dades bàsics

| Dada MPI | Correspondència de tipus de dada en C |
| MPI_CHAR | Char amb signe |
| MPI_SHORT | Enter short amb signe |
| MPI_INT | Enter amb signe. |
| MPI_LONG | Long amb signe |
| MPI_UNSIGNED_CHAR | Char sense signe |
| MPI_UNSIGNED_SHORT | Enter short sense signe |
| MPI_UNSIGNED_INT | Enter sense signe |
| MPI_UNSIGNED_LONG | Long sense signe |
| MPI_FLOAT | Float |
| MPI_DOUBLE | Double |
| MPI_LONG_DOUBLE | Long double |

## Referències

* ↑ «MPI Forum» (en anglès). [Consulta: 14 juliol 2017].
* ↑ «MPI Documents» (en anglès). [Consulta: 18 maig 2017].
* ↑ «MPI 4.0» (en anglès). [Consulta: 17 maig 2019].
* ↑ «Basic MPI».