# 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

* 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
### Diferenciando Tarefas através de Rank

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.
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_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_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_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_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_Initialized: Usado para saber se MPI_Init já foi chamado, retornando true (1) se já foi ou false (0) caso contrário.
* MPI_Wtime: Retorna o tempo decorrido em segundos (precisão dupla) no processador requisitante.
* 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.

### Agrupando tarefas por comunicadores

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.
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

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

* 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

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.

### Rotinas de comunicação ponto a ponto

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_Recv: Recebe uma mensagem e bloqueia até que o dado que está sendo recebido esteja disponível no buffer da aplicação.
* MPI_Ssend: Bloqueia até que o destino tenha recebido a mensagem.
* 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_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_Rsend: Dispensa o handshake, é mais eficiente, porém só pode ser usado se o receptor estiver em receive.
* 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_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_Probe: Executa um teste de bloqueio para uma mensagem.
O código em C abaixo mostra um exemplo da utilização dessas rotinas.
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_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_Issend
Indica quando o processo destino recebeu a mensagem.
* MPI_Ibsend
Indica quando o processo destino recebeu a mensagem. Deve ser usado com a rotina
* 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_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_Iprobe
Executa um teste não bloqueante para uma mensagem.
Segue abaixo um exemplo em C de uso dessas retinas não bloqueantes.

### Topologias Virtuais
#### O que são?

* 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?

* 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.

## Implementações de MPI

* Open MPI
* LAM/MPI Congelada. Desenvolvimento direcionado para a Open MPI.
* Los Alamos MPI (LA-MPI) Congelada. Desenvolvimento direcionado para a Open MPI.
* FT-MPI Também vai ser parte da Open MPI.
* PACX-MPI Também vai ser parte da Open MPI.
* MPICH
* MPICH2
* MVAPICH MPI sobre InfiniBand.

### Comerciais

* Scali MPI Connect
* WMPI II
* SGI Message Passing Toolkit
* Intel MPI
* Sun MPI
* HP-MPI
* MPI/Pro