% \chapter{Ambientes de Programação}
% 
% \section{Web Services}

\chapter{Ferramentas de Programação Paralela}
\label{programacaoparalela}

\section{Troca de Mensagens (\textit{Message Passing})}
\label{trocademensagens}

O paradigma de troca de mensagens tem sido tradicionalmente empregado em sistemas fracamente acoplados, representados pelas arquiteturas baseadas em memória distribuída (clusters), em que cada processador tem acesso somente à sua memória local e, por conseguinte, a comunicação, necessariamente, dá-se por meio de uma rede de interconexão.


Conceitualmente, a idéia de troca de mensagens é totalmente independente de \textit{hardware}, sistema operacional, linguagens de programação e bibliotecas. Quando no desenvolvimento de um programa paralelo por troca de mensagens, o programador deve distribuir os dados explicitamente entre os processadores. Visto que os espaços de endereçamento dos processos que compõem o programa paralelo são distintos, concebeu-se a abstração de mensagem, que pode ser enviada de um processo a outro por um canal de comunicação. Tal conceito é denotado no programa através de primitivas do tipo \textit{send} e \textit{receive}, as quais supõem um processo que pretende enviar (\textit{send}) uma mensagem a outro, que espera recebê-la (\textit{receive}). Entre os processos comunicantes diz-se que existe um canal de comunicação.


Na prática, os programadores dispõem de bibliotecas de comunicação com primitivas à semelhança de \textit{send} e \textit{receive}. As bibliotecas de comunicação que obtiveram maior aceitação foram: MPI (Clarke \cite{CLARKE94}) e PVM (Geist \cite{GEIST94}), ambas com suporte às linguagens de programação C e Fortran.




\subsection{PVM}

O PVM\cite{PVM} é um pacote de \textit{software} que permite o funcionamento de um conjunto de máquinas mono/multi-processadas e/ou paralelas, como um único recurso computacional paralelo. Com a utilização do PVM consegue-se uma forma eficiente e transparente de distribuir tarefas entre máquinas ligadas em rede, conseguindo um bom desempenho na gerencia dos recursos computacionais, através da configuração de uma máquina paralela virtual.

\subsubsection{Características}

O PVM habilita uma coleção de computadores heterogêneos a se comportar como um único recurso computacional expansível e concorrente, o que contribuiu para torná-lo um padrão de fato. É um mecanismo de distribuição livre que oferece bastante recursos para computação paralela com uma utilização simples e de fácil compreensão.

Algumas características do PVM são:
\begin{itemize}
\item possibilita a atribuição das subtarefas de uma aplicação, de forma otimizada, aos nós que compõem o ambiente paralelo;
\item apresenta uma interface de programação intuitiva e consistente;
\item oferece suporte para tolerância à falhas, monitoração e \textit{profiling} e
\item é altamente ``portável".
\end{itemize}


Com isso, através da agregação e compartilhamento de processadores e memórias de computadores heterogêneos, problemas que exigem grande poder computacional podem ser resolvidos sem a necessidade de comprar um supercomputador. Assim, utilizar o PVM é uma forma de aumentar o desempenho, com um custo efetivo menor.

\paragraph{Funcionamento Básico}.\\


O PVM é composto de duas partes. A primeira parte é um \textit{daemon}, chamado pvmd3, que é executado em todos os computadores que vão formar a máquina virtual paralela (MORETTI\cite{MORETTI97}). Esse programa roda em \textit{background} em cada um dos nós formando a maquina virtual, sendo responsável pela troca de mensagens entre eles além da coordenação das tarefas em execução.

A segunda parte é uma biblioteca de rotinas de interface, na qual se encontra um conjunto completo de primitivas, necessárias para a interação entre as tarefas de uma aplicação. As rotinas responsáveis pela comunicação entre os computadores interligados, gerência de processos, coordenação das tarefas, além da verificação e manutenção de estado da máquina virtual, estão contidas nessa biblioteca.



Os programas paralelos que utilizam o PVM fazem uso das rotinas disponibilizadas na biblioteca de interface do PVM. Para programação, essas bibliotecas são distribuídas em linguagens como Java, Python, Perl, além das linguagens tradicionais como C, C++ e Fortran.


Ao utilizar uma aplicação PVM, o usuário executa o pvmd3 em um dos computadores do cluster, normalmente o nó mestre, que chama os demais processos pvmd3 escravos em cada computador que vai compor a máquina virtual, através de \textit{remote shell} - rsh, coordenando assim as comunicações entre os processadores e o sistema. Logo, em cada nó, é necessário ter o pvmd3 instalado, sendo que existem versões disponíveis para vários sistemas operacionais. No caso de transmissão entre arquiteturas diferentes, automaticamente é feita uma conversão dos dados pelo formato XDR (\textit{External Data Representation}), conforme RFC 1832.



\subsection{\textit{Message Passing Interface} (MPI)}


% IGNACIO em seu artigo \cite{IGNACIO02} nos dá uma explicação inicial sobre a MPI, do qual podemos citar.

Segundo Gropp et al. \cite{GROPP94}, Foster \cite{FOSTER95} e Pacheco \cite{MPIuserguide}, o MPI é um padrão de interface para a troca de mensagens em máquinas paralelas com memória distribuída e não se devendo confundi-lo com um compilador ou um produto específico.

\paragraph{Histórico do MPI}.\\

O MPI é o resultado do esforço de aproximadamente 60 pessoas, pertencentes a 40 instituições, principalmente dos Estados Unidos e Europa. A maioria dos fabricantes de computadores paralelos participou, de alguma forma, da elaboração do MPI, juntamente com pesquisadores de universidades, laboratórios e autoridades governamentais. O início do processo de padronização aconteceu no seminário sobre Padronização para Troca de Mensagens em ambiente de memória distribuída, realizado pelo Center for Research on Parallel Computing, em abril de 1992. Nesse seminário, as ferramentas básicas para uma padronização de troca de mensagens foram discutidas e foi estabelecido um grupo de trabalho para dar continuidade à padronização. O desenho preliminar, foi realizado por Dongarra, Hempel, Hey e Walker, em novembro 1992, sendo a versão revisada finalizada em fevereiro de 1993 (pode ser obtido em \www{ftp://netlib2.cs.utk.edu/mpi/mpi1.ps}).

Em novembro de 1992 foi decidido colocar o processo de padronização numa base mais formal, adotando-se o procedimento e a organização do HPF (the \textit{High Performance Fortran Forum}). O projeto do MPI padrão foi apresentado na conferência Supercomputing 93, realizada em novembro de 1993, do qual se originou a versão oficial do MPI (5 de maio de 1994).% Essa  versão em postscript pode ser obtida na Netlib, enviando um e-mail a netlib@ornl.gov com a mensagem ?send mpi-report.ps from mpi? (também pode ser obtida em ftp://netlib2.cs.utk.edu/mpi/mpi-report.ps).

Ao final do encontro do MPI-1 (1994) foi decidido que se deveria esperar mais experiências práticas com o MPI. A sessão do Fórum-MPIF de Supercomputing 94 possibilitou a criação do MPI-2, que teve inicio em abril de 1995. No SuperComputing'96 foi apresentada a versão preliminar do MPI-2. Em abril de 1997 o documento MPI-2 foi unanimamente votado e aceito. Este documento está disponível via HTML em \www{http://www.mpi-forum.org/docs/mpi-20-html/mpi2-report.html}% ou  em postscript em http://www.mpi-forum.org/docs/mpi-20.ps.

\paragraph{O Padrão MPI}.\\


No padrão MPI, uma aplicação é constituída por um ou mais processos 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 (\textit{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 (\textit{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 (\textit{communicator}) que permitem ao usuário MPI definir módulos que encapsulem estruturas de comunicação interna.

Os algoritmos que criam um processo para cada processador podem ser implementados, diretamente, utilizando-se comunicação ponto a ponto ou coletivas. Os algoritmos que implementam a criação de tarefas dinâmicas ou que garantem a execução concorrente de muitas tarefas, num único processador, precisam de um refinamento nas implementações com o MPI.
