Message Passing Interface

Message Passing Interface (MPI) é um padrão para comunicação de dados em computação paralela. Existem várias modalidades de computação paralela, e dependendo do problema que se está tentando resolver, pode ser necessário passar informações entre os vários processadores ou nodos de um cluster, e o MPI oferece uma infraestrutura para essa tarefa.

No padrão MPI, uma aplicação é constituída por uma ou mais tarefas (as quais podem ser processos, ou threads, dependendo da implementação) que se comunicam, acionando-se funções para o envio e recebimento de mensagens entre os processos. Inicialmente, na maioria das implementações, um conjunto fixo de processos é criado. Porém, esses processos podem executar diferentes programas. Por isso, o padrão MPI é algumas vezes referido como MPMD (multiple program multiple data). Elementos importantes em implementações paralelas são a comunicação de dados entre processos paralelos e o balanceamento da carga. Dado o fato do número de processos no MPI ser normalmente fixo, neste texto é enfocado o mecanismo usado para comunicação de dados entre processos. Os processos podem usar mecanismos de comunicação ponto a ponto (operações para enviar mensagens de um determinado processo a outro). Um grupo de processos pode invocar operações coletivas (collective) de comunicação para executar operações globais. O MPI é capaz de suportar comunicação assíncrona e programação modular, através de mecanismos de comunicadores (communicator) que permitem ao usuário MPI definir módulos que encapsulem estruturas de comunicação interna.

O objetivo de MPI é prover um amplo padrão para escrever programas com passagem de mensagens de forma prática, portátil, eficiente e flexível. MPI não é um IEEE ou um padrão ISO, mas chega a ser um padrão industrial para o desenvolvimento de programas com troca de mensagens.

Motivação

editar
  • Portabilidade: MPI permite que você coloque sua aplicação em uma plataforma diferente, mas que suporte o padrão MPI sem necessitar alterar o código de forma que processos em diferentes linguagens podem rodar em plataformas diferentes.
  • Funcionalidade: Mais de 300 rotinas são definidas em MPI.
  • Disponibilidade: Há uma enorme variedade de implementações disponíveis.

Utilizando MPI

editar

Diferenciando Tarefas através de Rank

editar

Cada tarefa MPI deve ser identificada por um id, essa identificação deve ser feita no momento que um processo envolvendo aplicação MPI está sendo iniciada. O ambiente MPI atribui a cada processo um rank (guardado como um int) e um grupo de comunicação. O rank é um tipo de identificador de processo para cada tarefa MPI. É contíguo e começa por zero. Usado pelo programador para especificar a origem e o destino de mensagens:mensagem e frequentemente usado em condições para controle de execução (if rank == 0 faça isso / if rank == 1 faça aquilo). O grupo de comunicação define quais processos podem chamar comunicações ponto a ponto. Inicialmente, todos os processos MPI são associados a um grupo de comunicação default. Os membros de um grupo de comunicação podem mudar depois da aplicação ter iniciado. A atribuição do rank deve ser feita pela rotina MPI_Comm_rank() assim que a aplicação MPI está sendo iniciada. O primeiro argumento dessa rotina especifica qual comunicador será associado e o rank é retornado pelo segundo argumento. O exemplo abaixo mostra como a rotina MPI_Comm_rank() é usada.[1]

//…
int Tag = 33;
int WorldSize;
int TaskRank;
MPI_Status Status;
MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD,&TaskRank);
MPI_Comm_size(MPI_COMM_WORLD,&WorldSize);
//…

O comunicador MPI_COMM_WORLD é o comunicador default que todas as tarefas MPI são associadas quando iniciadas. Tarefas MPI são agrupadas por comunicadores. Um comunicador é o que identifica um grupo de comunicação.

Segue abaixo algumas rotinas usadas em MPI:

  • MPI_INIT: Inicializa o ambiente de execução de MPI. Deve ser chamada apenas uma vez em todos os programas de MPI e antes de qualquer outra função. Um exemplo em C seria:
MPI_Init (&argc,&argv)
  • MPI_Comm_size: Determina o número de processos em um grupo associado a um comunicador. Geralmente usado com o comunicador MPI_COMM_WORLD para determinar o número de processes que estão sendo usados por uma aplicação.
MPI_Comm_size (comm,&size)
  • MPI_Comm_rank: Utilizado para associar um rank do processo requisitante ao comunicador. Inicialmente, cada processo será associado a um único rank inteiro entre 0 e o número de processos -1 com o comunicador MPI_COMM_WORLD. Se um processo se tornar associado a outros comunicadores, ele terá um único rank com cada um desses comunicadores.
MPI_Comm_rank (comm,&rank)
  • MPI_Abort: Termina todos os processos MPI associados com o comunicador. Em várias implementações de MPI, essa rotina termina todos os processos independentemente do comunicador especificar.
MPI_Abort (comm,errorcode)
  • MPI_Get_processor_name: Retorna o nome do processador. Também retorna o tamanho do nome. O buffer do “nome” deve ser pelo menos MPI_MAX_PROCESSOR_NAME caracteres em tamanho.
MPI_Get_processor_name (&name,&resultlength)
  • MPI_Initialized: Usado para saber se MPI_Init já foi chamado, retornando true (1) se já foi ou false (0) caso contrário.
MPI_Initialized (&flag)
  • MPI_Wtime: Retorna o tempo decorrido em segundos (precisão dupla) no processador requisitante.
MPI_Wtime ()
  • MPI_Finalize: Termina a execução do ambiente MPI. Esta função deve ser a última rotina MPI chamada em todo programa MPI, nenhuma outra rotina MPI deve ser chamada após ela.
MPI_Finalize ()

Agrupando tarefas por comunicadores

editar

Além de ranks, processos também são associados com comunicadores. Os comunicadores especificam o domínio de comunicação de um conjunto de processos. Processos com os mesmos comunicadores estão no mesmo grupo de comunicação. Uma tarefa que um programa MPI faz pode ser dividida em grupos de comunicadores. MPI_Comm_create() pode ser usado para criar um novo comunicador. MPI provê mais de 40 rotinas relacionadas com grupos, comunicadores e topologias virtuais, a tabela abaixo mostra uma lista e uma pequena descrição das rotinas usadas por comunicadores.[1]

Tabela 1 - Rotinas usadas por comunicadores.
Rotina Descrição
1 #include "mpi.h"
2
int MPI_Intercomm_create
(MPI_Comm LocalComm,
int LocalLeader,
MPI_Comm PeerComm,
int remote_leader,
int MessageTag,
MPI_Comm *CommOut);
Cria um intercomunicador de dois

intracomunicadores.

3
int MPI_Intercomm_merge
(MPI_Comm Comm,int High,
MPI_Comm *CommOut);
Cria um intracomunicador de um

intercomunicador.

4
int MPI_Cartdim_get
(MPI_Comm Comm,int *NDims);
Retorna a informação da topologia

cartesiana associada ao comunicador.

5
int MPI_Cart_create
(MPI_Comm CommOld,int NDims,
int *Dims,int *Periods,
int Reorder,
MPI_Comm *CommCart);
Cria um novo comunicador cuja

informação de topologia tem sido anexada ao comunicador.

6
int MPI_Cart_map
(MPI_Comm CommOld,
int NDims,int *Dims,
int *Periods,int *Newrank);
Mapeia processo para informação

topológica cartesiana.

7
int MPI_Cart_get
(MPI_Comm Comm,int MaxDims,
int *Dims,int *Periods,
int *Coords);
Retorna a informação topológica

cartesiana associada a um comunicador.

8
int MPI_Comm_create
(MPI_Comm Comm,
MPI_Group Group,
MPI_Comm *CommOut);
Cria um novo comunicador.
9
int MPI_Comm_rank
(MPI_Comm Comm,int *Rank);
Calcula e retorna o resultado do

rank do processo requisitante.

10
int MPI_Comm_compare
(MPI_Comm Comm1,
MPI_Comm Comm2,
int *Result);
Compara dois comunicadores

Comm1 e Comm2.

11
int MPI_Comm_dup
(MPI_Comm CommIn,
MPI_Comm *CommOut);
Duplica um comunicador existente

junto com todas as informações em cache.

12
int MPI_Comm_group
(MPI_Comm Comm,
MPI_Group *Group);
Acessa o grupo associado com um

dado comunicador.

13
int MPI_Comm_size
(MPI_Comm Comm,int *Size);
Calcula e retorna o tamanho de um

grupo associado com um comunicador.

14
int MPI_Comm_split
(MPI_Comm Comm,int Color,
int Key,MPI_Comm *CommOut);
Cria um novo comunicador baseado

nas cores e chaves.

15
int MPI_Comm_test_inter
(MPI_Comm Comm,int *Flag);
Determina se um comunicador é um

intercomunicador.

16
int MPI_Comm_remote_group
(MPI_Comm Comm,
MPI_Group *Group);
Acessa o grupo remote associado

com um dado intercomunicador.

17
int MPI_Comm_remote_size
(MPI_Comm Comm,int *Size);
Calcula e retorna o tamanho de um

grupo remote associado com um intercomunicador.

Os principais propósitos de um grupo e objetos comunicadores

editar

1. Permitir organizar tarefas em grupos de tarefas;

2. Permitir operações de comunicação coletiva através de subconjuntos de tarefas relacionadas;

3. Prover comunicação segura.

Importante

editar
  • Grupos/comunicadores são dinâmicos, eles podem ser criados e destruídos durante a execução do programa;
  • Processos podem estar em mais de um grupo ou comunicador, no entanto eles terão um único rank para cada grupo/comunicador;
  • MPI provê mais de 40 rotinas relacionadas a grupos, comunicadores e topologias virtuais.

É comum que

editar

1. Um processo se agrupe ao grupo MPI_COMM_WORLD usando a rotina MPI_Comm_group;

2. Forme novos grupos como um subconjunto do grupo global utilizando MPI_Comm_incl;

3. Crie novo comunicador para o novo grupo utilizando MPI_Comm_create;

4. Determine um novo rank no novo comunicador utilizando MPI_Comm_rank;

5. Conduza comunicações usando qualquer rotina de troca de mensagem MPI;

6. Quando acabado, libere o novo comunicador e grupo (opcional) usando MPI_Comm_free e MPI_Group_free.

O exemplo abaixo mostra um exemplo de um programa em C que faz a criação de dois grupos de processos diferentes que requer a criação de novos comunicadores também.[2]

#include "mpi.h"
#include <stdio.h>
#define NPROCS 8

int main(argc, argv)
	int argc;char *argv[]; {
	int rank,new_rank,sendbuf,recvbuf,numtasks,ranks1[4] = {0,1,2,3},
			ranks2[4] = {4,5,6,7};
	MPI_Group orig_group, new_group;
	MPI_Comm new_comm;

	MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &numtasks);

	if (numtasks != NPROCS) {
		printf("Deve especificar MP_PROCS= %d. Terminando.\n", NPROCS);
		MPI_Finalize();
		exit(0);
	}

	sendbuf = rank;

	/* Extrai o grupo original */
	MPI_Comm_group(MPI_COMM_WORLD, &orig_group);

	/* Divide tarefas em dois grupos distintos baseados no ''rank'' */
	if (rank < NPROCS / 2) {
		MPI_Group_incl(orig_group, NPROCS/2, ranks1, &new_group);
	} else {
		MPI_Group_incl(orig_group, NPROCS/2, ranks2, &new_group);
	}

/* Cria novos comunicadores e então realiza comunicação coletiva. */
	MPI_Comm_create(MPI_COMM_WORLD, new_group, &new_comm);
	MPI_Allreduce(&sendbuf, &recvbuf, 1, MPI_INT, MPI_SUM, new_comm);

	MPI_Group_rank(new_group, &new_rank);
	printf("rank= %d newrank= %d recvbuf= %d\n", rank, new_rank, recvbuf);

	MPI_Finalize();
}

Rotinas de comunicação ponto a ponto

editar

Operações MPI ponto a ponto envolvem troca de mensagem entre APENAS duas tarefas distintas. Uma tarefa executa a operação de envio enquanto outra executa a operação de recebimento que casa com a de envio.

Há diferentes tipos de rotinas de envio e recebimento, tais como:

  • Envio síncrono;
  • Envio bloquente/recebimento bloqueante;
  • Envio não bloqueante /recebimento não bloqueante;
  • Envio buferizado;
  • Envio e recebimento combinado;

Todos esses tipos de envio e recebimento de mensagens podem ser usados para diferentes propósitos e qualquer tipo de rotina de envio pode ser usado com qualquer tipo de rotina de recebimento.

Envio bloqueante de mensagens só irá retornar da rotina quando a mensagem estiver no buffer da fonte ou no buffer do destino. Vai depender da rotina que foi invocada. Analogamente podemos dizer o mesmo das rotinas de recebimento bloqueante. São rotinas que só retornam quando o seu buffer tiver recebido a mensagem ou quando tiver lido a mensagem. Abaixo segue as rotinas de envio bloqueantes mais usadas:

  • MPI_Send: Operação básica de bloqueio de envio. A rotina retorna apenas depois da aplicação buferizar na tarefa de envio.
MPI_Send (&buf,count,datatype,dest,tag,comm)
  • MPI_Recv: Recebe uma mensagem e bloqueia até que o dado que está sendo recebido esteja disponível no buffer da aplicação.
MPI_Recv (&buf,count,datatype,source,tag,comm,&status) 
  • MPI_Ssend: Bloqueia até que o destino tenha recebido a mensagem.
MPI_Ssend (&buf,count,datatype,dest,tag,comm) 
  • MPI_Bsend: Permite ao programador escolher um certo valor de buffer que torna a chamada da rotina bloqueada até que esse valor de buffer tenha sido atingido.
MPI_Bsend (&buf,count,datatype,dest,tag,comm) 
  • MPI_Buffer_attach
  • MPI_Buffer_detach: Usado para alocar e desalocar o espaço de buffer de mensagem que será usado pela rotina MPI_Bsend.
MPI_Buffer_attach (&buffer,size) 
     MPI_Buffer_detach (&buffer,size) 
  • MPI_Rsend: Dispensa o handshake, é mais eficiente, porém só pode ser usado se o receptor estiver em receive().
MPI_Rsend (&buf,count,datatype,dest,tag,comm) 
  • MPI_Sendrecv: Envia uma mensagem e coloca um receive antes de bloquear. Essa rotina bloqueia até que o buffer da aplicação fonte esteja livre para reuso e até o buffer da aplicação destino contenha a mensagem recebida.
MPI_Sendrecv (&sendbuf,sendcount,sendtype,dest,sendtag, 
                   &recvbuf,recvcount,recvtype,source,recvtag, 
                   comm,&status) 
  • MPI_Wait
  • MPI_Waitany
  • MPI_Waitall
  • MPI_Waitsome: MPI_Wait boqueia até que um específico envio não bloquente ou operação de recebimento tenha completado. Para múltiplas operações não bloqueantes, o programador pode especificar qualquer, todas ou algumas conclusões.
MPI_Wait (&request,&status) 
     MPI_Waitany (count,&array_of_requests,&index,&status) 
     MPI_Waitall (count,&array_of_requests,&array_of_statuses) 
     MPI_Waitsome (incount,&array_of_requests,&outcount, 
                   &array_of_offsets, &array_of_statuses)
  • MPI_Probe: Executa um teste de bloqueio para uma mensagem.
MPI_Probe (source,tag,comm,&status) 

O código em C abaixo mostra um exemplo da utilização dessas rotinas.[2]

#include "mpi.h"
#include <stdio.h>

int main(argc, argv)
	int argc;char *argv[]; {
	int numtasks, rank, dest, source, rc, count, tag = 1;
	char inmsg, outmsg = 'x';
	MPI_Status Stat;

	MPI_Init(&argc, &argv);
	MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);

	if (rank == 0) {
		dest = 1;
		source = 1;
              rc = MPI_Send(&outmsg, 1, MPI_CHAR, dest, tag, MPI_COMM_WORLD);
              rc = MPI_Recv(&inmsg, 1, MPI_CHAR, source, tag, MPI_COMM_WORLD, &Stat);
	}

	else if (rank == 1) {
		dest = 0;
		source = 0;
              rc = MPI_Recv(&inmsg, 1, MPI_CHAR, source, tag, MPI_COMM_WORLD, &Stat);
              rc = MPI_Send(&outmsg, 1, MPI_CHAR, dest, tag, MPI_COMM_WORLD);
	}

      rc = MPI_Get_count(&Stat, MPI_CHAR, &count);
      printf("Tarefa %d: Recebida %d char(s) da tarefa %d com tag %d \n", rank,count,  
      Stat.MPI_SOURCE, Stat.MPI_TAG);

	MPI_Finalize();
}

Envio não bloqueante de mensagens implica que o fluxo de execução continua após ter chamado a rotina de envio, sem se importar se a mensagem chegou ao buffer da fonte ou do destino. Analogamente podemos dizer o mesmo das rotinas de recebimento não bloqueante.

Abaixo segue as rotinas de envio não bloqueantes mais usadas:

  • MPI_Isend

Identifica uma área na memória que sirva como buffer de envio. O processamento continua sem que a aplicação espere por uma confirmação de que a mensagem foi copiada com sucesso.

MPI_Isend (&buf,count,datatype,dest,tag,comm,&request) 
  • MPI_Irecv

Identifica uma area na memória que sirva como buffer de recebimento. O processamento continua sem que a aplicação espere por uma confirmação de que a mensagem foi recebida e copiada para o buffer com sucesso.

MPI_Irecv (&buf,count,datatype,source,tag,comm,&request) 
  • MPI_Issend

Indica quando o processo destino recebeu a mensagem.

MPI_Issend (&buf,count,datatype,dest,tag,comm,&request) 
  • MPI_Ibsend

Indica quando o processo destino recebeu a mensagem. Deve ser usado com a rotina

MPI_Buffer_attach.
MPI_Ibsend (&buf,count,datatype,dest,tag,comm,&request) 
  • MPI_Irsend

Indica quando o processo destino recebeu a mensagem. Deve ser usado apenas se o programador tem certeza que o receive que casa está pronto.

MPI_Irsend (&buf,count,datatype,dest,tag,comm,&request) 
  • MPI_Test
  • MPI_Testany
  • MPI_Testall
  • MPI_Testsome

MPI_Test verifica o status de um envoi não bloqueante específico ou operação de recebimento. Retorna (1) caso a operação está concluída ou (0) caso contrário. Para múltiplas operações não bloqueantes o programador pode especificar qualquer, todos ou algumas conclusões.

MPI_Test (&request,&flag,&status) 
MPI_Testany (count,&array_of_requests,&index,&flag,&status)
MPI_Testall (count,&array_of_requests,&flag,&array_of_statuses)
MPI_Testsome (incount,&array_of_requests,&outcount,
               &array_of_offsets, &array_of_statuses)
  • MPI_Iprobe

Executa um teste não bloqueante para uma mensagem.

MPI_Iprobe (source,tag,comm,&flag,&status)

Segue abaixo um exemplo em C de uso dessas retinas não bloqueantes.[2]

#include "mpi.h"
#include <stdio.h>

int main(argc,argv)
	int argc;
	char *argv[];  {
	int numtasks, rank, next, prev, buf[2], tag1=1, tag2=2;
	MPI_Request reqs[4];
	MPI_Status stats[4];

	MPI_Init(&argc,&argv);
	MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);

	prev = rank-1;
	next = rank+1;
	if (rank == 0)  prev = numtasks - 1;
	if (rank == (numtasks - 1))  next = 0;

	MPI_Irecv(&buf[0], 1, MPI_INT, prev, tag1, MPI_COMM_WORLD, &reqs[0]);
	MPI_Irecv(&buf[1], 1, MPI_INT, next, tag2, MPI_COMM_WORLD, &reqs[1]);

	MPI_Isend(&rank, 1, MPI_INT, prev, tag2, MPI_COMM_WORLD, &reqs[2]);
	MPI_Isend(&rank, 1, MPI_INT, next, tag1, MPI_COMM_WORLD, &reqs[3]);
  
      {  do some work  }

	MPI_Waitall(4, reqs, stats);

	MPI_Finalize();
}

Topologias Virtuais

editar

O que são?

editar
  • Uma topologia virtual descreve um mapeamento de processos MPI em um “forma” geométrica;
  • Os dois principais tipos de topologias virtuais são Cartesiano e gráfico;
  • A topologia MPI é virtual, ou seja, não tem relação alguma com a topologia física que se encontra do conjunto de máquinas ou da organização dos processos paralelos;
  • A topologia virtual é construída pelos grupos e comunicadores MPI;
  • Deve ser implementado pelo desenvolvedor da aplicação.

Para que utilizar Topologias Virtuais?

editar
  • Pode ser usada para aplicações com padrões específicos de comunicação, padrões que casem com uma estrutura topológica MPI;
  • Por exemplo, uma topologia cartesiana é conveniente para uma aplicação que necessite dos comunicadores vizinhos mais próximos;
  • Algumas arquiteturas de hardware têm o desempenho prejudicado por conta da comunicação entre comunicadores distantes;
  • Uma implementação particular pode ser otimizada se for feito um mapeamento baseado nas características físicas de uma dada máquina paralela;
  • O mapeamento de processos em uma topologia virtual é dependente da implementação MPI, e pode ser totalmente ignorada.

O Exemplo 4 mostra um exemplo da criação de uma topologia cartesiana 4 x 4 de 16 processos e cada processo troca seu rank com 4 vizinhos.

#include "mpi.h"
#include <stdio.h>
#define SIZE 16
#define UP    0
#define DOWN  1
#define LEFT  2
#define RIGHT 3

int main(int argc, char **argv)
{
    int numtasks,rank,source,dest,outbuf,i,tag = 1,inbuf[4] = {
        MPI_PROC_NULL, MPI_PROC_NULL, MPI_PROC_NULL, MPI_PROC_NULL, },
        nbrs[4], dims[2] = { 4, 4 }, periods[2] = { 0, 0 }, reorder = 0,
	coords[2];

    MPI_Request reqs[8];
    MPI_Status stats[8];
    MPI_Comm cartcomm;

    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &numtasks);

    if (numtasks == SIZE) 
    {
        MPI_Cart_create(MPI_COMM_WORLD, 2, dims, periods, reorder, &cartcomm);
	MPI_Comm_rank(cartcomm, &rank);
	MPI_Cart_coords(cartcomm, rank, 2, coords);
	MPI_Cart_shift(cartcomm, 0, 1, &nbrs[UP], &nbrs[DOWN]);
	MPI_Cart_shift(cartcomm, 1, 1, &nbrs[LEFT], &nbrs[RIGHT]);

	outbuf = rank;

	for (i = 0; i < 4; i++) 
        {
	    dest = nbrs[i];
	    source = nbrs[i];
            MPI_Isend(&outbuf, 1, MPI_INT, dest, tag, MPI_COMM_WORLD, &reqs[i]);
            MPI_Irecv(&inbuf[i], 1, MPI_INT, source, tag, MPI_COMM_WORLD,&reqs[i + 4]);
	}

	MPI_Waitall(8, reqs, stats);

        printf("rank= %d coords= %d %d  visinhos(u,d,l,r)= %d %d %d %d\n", rank, coords[0], 
            coords[1], nbrs[UP], nbrs[DOWN], nbrs[LEFT], nbrs[RIGHT]);
	printf("rank= %d  inbuf(u,d,l,r)= %d %d %d %d\n", rank, inbuf[UP], inbuf[DOWN],  
            inbuf[LEFT], inbuf[RIGHT]);
    }
    else
        printf("Deve ser especificado %d processadores. Terminando.\n", SIZE);

    MPI_Finalize();
}

Implementações de MPI

editar
Comerciais

Ver também

editar

Ligações externas

editar

Referências

  1. a b HUGHES, Cameron; HUGHES, Tracey. Parallel and Distributed Programming Using C++. Addison-Wesley, 2003.
  2. a b c https://computing.llnl.gov/tutorials/mpi/