Message Passing Interface - MO601
Message Passing
Interface (MPI)
Gustavo Waku
[email protected]
1
•
•
•
•
•
•
•
•
•
•
•
Introdução e breve histórico
Conceitos Básicos
Comunicação ponto a ponto
DeadLocks e Starvation
Modos de comunicação e operações não bloqueantes
Comunicação coletiva
Topologia de Processos
Entrada e Saída Paralela
Fechamento
Q&A
Referências Bibliográficas
Message Passing Interface - MO601
Agenda
2
• O que é o MPI?
• É uma especificação que define um conjunto de apis para passagem de
mensagens, estabelecendo padrões de comportamento.
• Várias implementações, comportamentos diferentes => sistemas
heterogêneos, diversos fabr, necessidade de convergência.
• Adoção em ambientes hetetorêneos (portabilidade, facilidade de
programar, grande nro de rotinas disponíveis).
• Atualmente especificado pelo MPI forum [http://mpj-express.org/]
• Utilizado em sistemas de alta performance.
Message Passing Interface - MO601
Introdução e Breve histórico
V1.0 Mai
V1.1 Jun
V1.2 Mai
V2.1 Jun
V1.2 Jul
e V2.0
V2.2 Set
V3.0 Set
1994 1995 1997
2008 2009
2012
3
• Processo (Process)
• Identificado pelo rank (similar ao pid do linux, vai de 0 a N-1).
• Grupos (Group)
• Coleção de processos
• Contexto (Context)
• Particiona o espaço, e serve para isolar.
• Communicador (Communicator)
Message Passing Interface - MO601
Conceitos Básicos
• Agrega os conceitos de Grupo + Contexto (MPI_COMM_WORLD,
MPI_COMM_SELF)
• Intra-Communicator (dentro do grupo), Inter-Communicator
(entre grupos)
4
• Formação de pacotes e matching
• Como funciona
• Par send – receive
• DEST/SOURCE+ TAG + COMM => envelope
• matching
• Variantes com MPI_ANY_SOURCE, MPI_ANY_TAG.
• Assimetria entre send / receive.
• Como identificar processos? ( comm + rank ).
Message Passing Interface - MO601
Comunicação ponto a ponto
5
Comunicação ponto a ponto
Processo 0
#include "mpi.h"
Send
int main( int argc, char *argv[])
{
char message[20];
int myrank;
MPI_Status status;
MPI_Init( &argc, &argv );
MPI_Comm_rank( MPI_COMM_WORLD, &myrank );
if (myrank == 0) /* code for process zero */
{
strcpy(message,"Hello, there");
MPI_Send(message, strlen(message)+1, MPI_CHAR, 1, 99, MPI_COMM_WORLD);
}
else if (myrank == 1) /* code for process one */
{
MPI_Recv(message, 20, MPI_CHAR, 0, 99, MPI_COMM_WORLD, &status);
printf("received :%s:\n", message);
}
MPI_Finalize();
return 0; }
Processo 1
Receive
Message Passing Interface - MO601
• Sends/Receives Bloqueantes, unidirecional
6
Comunicação ponto a ponto
• Sends/Receives Bloqueantes
public class HelloWorldMPI {
public static final int TAG = 99;
public static void main(String[] args) throws Exception {
MPI.Init(args) ;
int myrank = MPI.COMM_WORLD.Rank();
int numprocs = MPI.COMM_WORLD.Size();
System.out.println("I am process <"+myrank+"> of total <"+ numprocs +"> processes.");
char [] message1 = "Hello There, I`m process <0> speaking".toCharArray();
char [] buf1 = new char[message1.length];
char [] message2 = ("Hi, I`m process <" + myrank + "> speaking").toCharArray();
char [] buf2 = new char[message2.length];
if (myrank == 0) {
for ( int i=1; i<numprocs; i++ ) {
System.out.println(" process <0> sends message to: <" + i + ">");
MPI.COMM_WORLD.Send(message1, 0, message1.length, MPI.CHAR, i, TAG);
}
for ( int i=1; i<numprocs; i++ ) {
System.out.println(" process <0> waits to receive messages from <" + i + ">");
MPI.COMM_WORLD.Recv(buf2, 0, buf2.length, MPI.CHAR, i, TAG);
}
} else {
System.out.println(" process <"+ myrank +"> waits to receive from <0>");
MPI.COMM_WORLD.Recv(buf1, 0, buf1.length, MPI.CHAR, 0, TAG);
System.out.println("process <"+ myrank +"> received: " + new String(buf1) + "!");
System.out.println(" process <"+ myrank +"> sends message back to <0>");
MPI.COMM_WORLD.Send(message2, 0, message2.length, MPI.CHAR, 0, TAG);
}
MPI.Finalize();
}
}
P0
P1
P2
P3
…
Message Passing Interface - MO601
package p1;
import mpi.*;
PN
Múltipos Processos:
- P0 envia a mensagem
e aguarda a resposta
- Os demais recebem e
enviam
uma outra mensagem para
P0
7
Comunicação ponto a ponto
P1
(4) Inicia e aguarda P0
(8) Recebe msg de P0
(9) Envia msg para P0
P2
(3) Inicia e aguarda P0
(12) Recebe msg de P0
(13) Envia msg para P0
Message Passing Interface - MO601
MPJ Express (0.38) is started in the multicore configuration
I am process <3> of total <4> processes.
process <3> waits to receive from <0>
P0
I am process <0> of total <4> processes.
(2) Inicia e Envia msg
process <0> sends message to: <1>
para P1
I am process <2> of total <4> processes.
(5) Envia msg para P2
process <2> waits to receive from <0>
(6) Envia msg para P3
(7) Aguarda msg de P1
I am process <1> of total <4> processes.
(14) Recebe msg de P1
process <1> waits to receive from <0>
(15) Recebe msg de P2
process <0> sends message to: <2>
(16) Recebe msg de P3
process <0> sends message to: <3>
process <0> waits to receive messages from <1>
process <1> received: Hello There, I`m process <0> speaking!
process <1> sends message back to <0>
process <3> received: Hello There, I`m process <0> speaking!
process <3> sends message back to <0>
process <2> received: Hello There, I`m process <0> speaking!
process <2> sends message back to <0>
process <0> received: Hi, I`m process <1> speaking
process <0> waits to receive messages from <2>
process <0> received: Hi, I`m process <2> speaking
process <0> waits to receive messages from <3>
process <0> received: Hi, I`m process <3> speaking
P3
(1) Inicia e aguarda P0
(10) Recebe msg de P0
(11) Envia msg para P0
8
• Deadlocks
• Em uma comunicação síncrona, podem ocorrer deadlocks caso o
programa tenha sido projetado de forma equivocada. Um
exemplo é a situação em que um processo 0 envia uma
mensagem ao processo 1 e fica esperando, o processo 1 envia
para o processo 0 que também fica esperando. Uma maneira de
evitar isso é fazer com que um deles comece recebendo a
mensagem, e o outro enviando.
• Outras situações de deadlock podem ocorrer e devem ser
observadas caso a caso. O padrão não especifica formas de
identificar, apenas enumera alguns possíveis casos de deadlock.
Processo 0
Processo 1
Processo 0
Processo 1
Send
Send
Send
Receive
Receive
Receive
Receive
Send
Message Passing Interface - MO601
Deadlocks e Starvation
9
• Starvation
• O protocolo não garante justiça na comunicação. Suponha que
um processo envie uma mensagem, o processo destino pode não
receber a mensagem devido a mensagem ter sido sobreposta por
outra mensagem enviada por outro processo. De maneira
análoga, suponha vários processos receptores de mensagens
produzidas por outro processo, é possível que algum deles nunca
receba a mensagem produzida. É responsabilidade do
programador garantir que não ocorra starvation.
Processo 0
Send
Processo 1
Send
?, X
Processo 2
Processo 0
Receive
Send
Message Passing Interface - MO601
Deadlocks e Starvation
Processo 1
?, X
Receive
Processo 2
Receive
Processo 3
Receive
10
• Bloqueantes e não bloqueantes (continuam ou não a execução)
• Local ou não local (depende ou não de um comando correspondente).
• Sends Bloqueantes:
• Standard (sujeito à disponibilidade de memória do sistema se a mensagem
vai ser armazenada em buffer ou não; se ela for armazenada em buffer, o
programa pode continuar assim que a mensagem for transferida ao buffer. Se
não houver memória (ou por questões de desempenho) e a mensagem não
for armazenada em buffer, o programa não retoma sua execução até que o
comando receive correspondente seja invocado. – não local
• Buffered (copiada para um buffer temporário e não espera o comando
receive correspondente para continuar a execução) – local
• Synchronous (só termina quando o comando receive correspondente é
alcançado e a mensagem começou a ser recebida) – não local
• Ready (espera o comando receive correspondente ser alcançado para poder
iniciar, semântica igual ao send standard e send synchronous.) – não local
• Mesma idéia para Sends não bloqueantes. (mas dividida em start e
complete). send_start, send_complete, receive_start, receive_complete
• Receives não possuem tantas variantes, apenas bloq./não bloq.
Message Passing Interface - MO601
Modos de comunicação e operações
não bloqueantes
11
Message Passing Interface - MO601
Modos de comunicação e operações
não bloqueantes
• Todas as combinações de send-receives bloqueantes e não
bloqueantes são possíveis.
• Ex: send bloqueante – receive não bloqueante, etc…
12
• Objetivo: fornecer uma maneira de comunicação entre os processos
de um grupo ou entre grupos de processos. Exemplos principais são
barreiras e broadcasts. (APIS relacionadas: MPI_BARRIER,
MPI_BCAST, MPI_SCATTER, MPI_GATHER, MPI_ALLGATHER,
MPI_ALLTOALL )
• MPI-3.0 adicionou operações assíncronas: MPI_ISCATTER,
MPI_IBARRIER, etc…
Message Passing Interface - MO601
Comunicação Coletiva
13
• Exemplo de MPI_BCAST(buffer, count, datatype, root, comm)
• Broadcast de 100 inteiros do processo 0 (root) para cada
processo dentro do grupo (comm)
….
MPI_Comm comm;
int array[100];
int root=0;
...
MPI_Bcast(array, 100, MPI_INT, root, comm);
Message Passing Interface - MO601
Comunicação Coletiva
14
• Atributo extra e opcional dado ao intRA-comunicador
• Ajuda a prover um mecanismo de referência conveniente para
processos (dentro de um grupo)
• Pode ajudar no mapeamento físico de processos
• O padrão MPI não estabelece como devem ser mapeados os
processos em hardware. Cada fornecedor possui uma impl.
• Tipos suportados: Cartesiana, Grafal e Grafal Distribuída.
Message Passing Interface - MO601
Topologia (Virtual) de
Processos
15
• E/S tradicionalmente é feita de forma serial, uma possível
otimização é criar vários processos fazendo uma computação
e deixar um processo cuidando de toda a E/S.
#include "mpi.h"
#include <stdio.h>
#define BUFSIZE 100
int main(int argc, char *argv[])
{ int i, myrank, numprocs, buf[BUFSIZE];
MPI_Status status;
FILE *myfile;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
for (i=0; i<BUFSIZE; i++)
buf[i] = myrank * BUFSIZE + i;
if (myrank != 0)
MPI_Send(buf, BUFSIZE, MPI_INT, 0, 99, MPI_COMM_WORLD);
else {
myfile = fopen("testfile", "w");
fwrite(buf, sizeof(int), BUFSIZE, myfile);
for (i=1; i<numprocs; i++) {
MPI_Recv(buf, BUFSIZE, MPI_INT, i, 99, MPI_COMM_WORLD,
&status);
} fwrite(buf, sizeof(int), BUFSIZE, myfile);
} fclose(myfile);
MPI_Finalize();
return 0; }
• Vantagem:
Message Passing Interface - MO601
E/S Paralela
• Simplicidade (com a
delegação de E/S para
1 único processo).
• Desvantagem:
• Processo 0 precisa
esperar por todos,
pouca paralelização.
16
• Escrita em um único arquivo com MPI_FILE_SET_VIEW(fh,
offset, etype, filetype, datarep, info) e MPI_FILE_WRITE.
#include "mpi.h"
#include <stdio.h>
#define BUFSIZE 100
int main(int argc, char *argv[])
{ int i, myrank, buf[BUFSIZE];
MPI_File thefile;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
for (i=0; i<BUFSIZE; i++)
buf[i] = myrank * BUFSIZE + i;
MPI_File_open(MPI_COMM_WORLD, "testfile",
MPI_MODE_CREATE | MPI_MODE_WRONLY,
MPI_INFO_NULL, &thefile);
MPI_File_set_view(thefile, myrank * BUFSIZE * sizeof(int),
MPI_INT, MPI_INT, "native", MPI_INFO_NULL);
MPI_File_write(thefile, buf, BUFSIZE, MPI_INT,
MPI_STATUS_IGNORE);
MPI_File_close(&thefile);
MPI_Finalize();
return 0; }
Message Passing Interface - MO601
E/S Paralela
17
• Leitura paralela, setando o ponteiro na posição com MPI_FILE_SET_VIEW e
lendo com MPI_FILE_READ
#include "mpi.h"
#include <stdio.h>
int main(int argc, char *argv[])
{ int myrank, numprocs, bufsize, *buf, count;
MPI_File thefile;
MPI_Status status;
MPI_Offset filesize;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
MPI_File_open(MPI_COMM_WORLD, "testfile", MPI_MODE_RDONLY,
MPI_INFO_NULL, &thefile);
MPI_File_get_size(thefile, &filesize); /* in bytes */
filesize = filesize / sizeof(int); /* in number of ints */
bufsize = filesize / numprocs + 1; /* local number to read */
buf = (int *) malloc (bufsize * sizeof(int));
MPI_File_set_view(thefile, myrank * bufsize * sizeof(int),
MPI_INT, MPI_INT, "native", MPI_INFO_NULL);
MPI_File_read(thefile, buf, bufsize, MPI_INT, &status);
MPI_Get_count(&status, MPI_INT, &count);
printf("process %d read %d ints\n", myrank, count);
MPI_File_close(&thefile);
MPI_Finalize();
return 0; }
Message Passing Interface - MO601
E/S Paralela
18
• O padrão MPI define um conjunto de operações padrão +
comportamento esperado
• Portabilidade e Facilidade de Uso
• Implementações
• Fortran, C, C++, Java
• Produtos Comerciais
•
•
•
•
•
SGI Message Passing Toolkit
WMPI II
Sun MPI
Intel MPI
HP-MPI
Message Passing Interface - MO601
Fechamento
19
Message Passing Interface - MO601
Q&A ?
20
[1] MPI: A Message-Passing Interface Standard Version 3.0. Setembro 2012. Disponível em:
http://www.mpi-forum.org/docs/mpi-3.0/mpi30-report.pdf. Acessado em outubro de 2012.
[2] Message Passing Interface. Disponível em: http://en.wikipedia.org/wiki/Message_
Passing_Interface. Acessado em: outubro de 2012.
[3] MPJ Express. Disponível em: http://mpj-express.org/. Acessado em: outubro de 2012.
[4] MPJ Express: An Implementation of MPI in Java Linux/UNIX/Mac User Guide. Disponível
em: http://mpj-express.org/docs/guides/linuxguide.pdf. Acessado em: outubro de 2012.
[5] Culler D. E.; Singh J. P. Kaufmman M. Parallel Computer Architecture. Morgan Kaufmann
Publishers, 1999.
Message Passing Interface - MO601
Referências Bibliográficas
[6] Gropp W.; Lusk E.; Thakur R. Using MPI-2 Advanced Features of the Message Passing
Interface, MIT press, 1994.
[7] Open MPI. Disponível em: http://www.open-mpi.org/. Acessado em: outubro de 2012.
[8] Sun MPI 6.0 Software Programming and Reference Manual. Disponível em:
http://docs.oracle.com/cd/E19061-01/hpc.cluster5/817-0085-10/. Acessado em: outubro de
2012.
21
Message Passing Interface - MO601
BACKUP
22
• Uma forma alternativa seria escrever em múltiplos arquivos.
#include "mpi.h"
#include <stdio.h>
#define BUFSIZE 100
int main(int argc, char *argv[])
{
int i, myrank, buf[BUFSIZE];
char filename[128];
MPI_File myfile;
• Vantagem: Paralelização da escrita
e computação.
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
• Desvantagens:
for (i=0; i<BUFSIZE; i++)
• os arquivos precisam ser juntados
para utilização futura por um
buf[i] = myrank * BUFSIZE + i;
outro processo
sprintf(filename, "testfile.%d", myrank);
• se uma aplicação for escrita de
MPI_File_open(MPI_COMM_SELF, filename,
forma paralela, ela vai
MPI_MODE_WRONLY | MPI_MODE_CREATE,
necessariamente paralelizar até
MPI_INFO_NULL, &myfile);
no máximo o número de arquivos
produzidos
MPI_File_write(myfile, buf, BUFSIZE, MPI_INT,
• é difícil manusear e trafegar na
MPI_STATUS_IGNORE);
rede vários arquivos, assim como
MPI_File_close(&myfile);
manter lógica deles.
MPI_Finalize();
return 0; }
Message Passing Interface - MO601
E/S Paralela
23