
\section{Relações Entre o \textit{Hardware} e o \textit{Software} para Exploração do Paralelismo}
\label{RHSEP}
\cutname{relacaoentrehardwareesoftwareparaexploracaodoparalelismo.html}

Esta sessão tem por objetivos caracterizar os pontos de interdependência entre o \textit{software} e o \textit{hardware} para paralelismo, e analisar as características de um modelo ideal de programação, buscando delimitar as condições necessárias para que se potencialize o desenvolvimento de programas destinados às arquiteturas paralelas.


\subsection{Relação entre Algoritmos e Arquiteturas Paralelas}
\label{RAAP}
O foco central desta seção é discutir a relação entre as características de um algoritmo paralelo e aquelas da arquitetura sobre a qual este irá ser processado. Uma clareza deste inter-relacionamento é fundamental para a qualidade, tanto do projeto do \textit{hardware} paralelo, como dos respectivos \textit{softwares} a nível de sistema e aplicativo. Este tema vem despertando o interesse dos teóricos já há algum tempo. Um primeiro estudo publicado foi o de UNG \cite{KUN80}. A relação dos critérios para inter-relacionamento que será utilizada foi extraída de MOLDOVAN \cite{MOL93}. O tema tratado nesta seção é amplo e factível de uma abordagem teórico-formal. Foi escolhido um tratamento de modo resumido, procurando mostrar da maneira mais genérica possível a relação entre o \textit{hardware} e o \textit{software} paralelo (vide tabela \ref{tab:algoparaleloversusarquitetura}). Para potencializar esta escolha, foram extraídos dos textos CULLER \cite{CUL99}, HWANG \cite{HWA93} e MORSE \cite{MOR94} exemplos para quantificar a natureza das relações.


\subsubsection{Critérios para Caracterização de Algoritmos}

O critérios que serão utilizados para caracterizar o perfil do algoritmo paralelo são: granulosidade do módulo, controle da concorrência, mecanismo de dados, geometria das comunicações e tamanho do algoritmo.

\textbf{Granulosidade}\textbf{ do módulo:} os módulos podem ser programas, processos, rotinas ou instruções, dependendo do nível no qual o paralelismo está sendo explorado. A granulosidade do módulo indica o volume de computação que o mesmo contém. É relativamente usual existir abundância de paralelismo com baixa granulosidade, o qual, via de regra, não pode ser explorado com eficiência. Isto porque o trabalho com baixa granulosidade aumenta o volume de comunicação de dados entre os módulos. O desempenho da arquitetura paralela é obtido através de um equilíbrio entre granulosidade e comunicação. As comunicações, além do custo de tempo que lhes é inerente (o qual é dependente da rede de interconexão dos processadores), normalmente estabelecem sincronizações entre processos.


\textbf{Controle da concorrência}: diz respeito à estratégia de selecionar módulos para execução. A estratégia de controle deve considerar as dependências de dados e controle para que a execução do algoritmo seja correta. Algumas estratégias de controle são executadas com base na disponibilidade dos dados (\textit{dataflow}), controle centralizado (\textit{synchronized}), ou sob demanda (\textit{d}e\textit{mand}\textit{-}\textit{driven}). Algoritmos com um alto grau de regularidade, por exemplo, multiplicação de matrizes, são indicados para um controle centralizado e são otimamente mapeados em processadores sistólicos ou outros processadores matriciais (SIMD). Por sua vez, algoritmos que incorporam transferências condicionais ou outras irregularidades no fluxo de execução, são melhor indicados para arquiteturas assíncronas tais como os multiprocessadores.

\textbf{Mecanismo de dados}: refere-se à maneira como os operandos das instruções são manipulados. Os dados gerados por uma instrução podem tanto ser utilizados como ``dados puros", padrão do modelo de controle por disponibilidade de dados (\textit{dataflow}), ou podem ser colocados em um lugar de armazenamento, e então referenciados pelo seu endereço, como no modelo de Von Neumann e suas extensões.

\textbf{Geometria das comunicações}: trata do padrão como ocorrem as interconexões entre os módulos em execução. A geometria das comunicações de um algoritmo é dita regular quando o padrão das interconexões repete ao longo dos ciclos da computação, e irregular quando as interconexões são aleatórias. É comum geometrias regulares assumirem formas semelhantes a árvores, malhas e cubos.

\textbf{Tamanho do algoritmo}: indica o número total de computações que o algoritmo deve executar. Por exemplo, a manipulação de matrizes 1000 x 1000 é considerado um problema grande. O tamanho do algoritmo diz respeito ao número de processadores e à disponibilidade de memória da arquitetura paralela.


\begin{flushleft}

\begin{table}
\centering
\begin{tabular}{m{160.15pt}|m{163.75pt}}
\hline
	\multicolumn{1}{m{160.15pt}|}{
	\begin{minipage}{160.15pt}
		\textbf{Algoritmo Paralelo}
	\end{minipage}
	}
	&
	\multicolumn{1}{m{163.75pt}}{
	\begin{minipage}{163.75pt}
			\textbf{Arquitetura Paralela}
	\end{minipage}
	}
\\\hline
	\multicolumn{1}{m{160.15pt}|}{
	\begin{minipage}{160.15pt}
		Granulosidade do módulo
	\end{minipage}
	}
	&
	\multicolumn{1}{m{163.75pt}}{
	\begin{minipage}{163.75pt}
		Complexidade do processador
	\end{minipage}
	}
\\\hline
	\multicolumn{1}{m{160.15pt}|}{
	\begin{minipage}{160.15pt}
	Controle da concorrência
	\end{minipage}
	}
	&
	\multicolumn{1}{m{163.75pt}}{
	\begin{minipage}{163.75pt}
	Modo de operação
	\end{minipage}
	}
\\\hline
	\multicolumn{1}{m{160.15pt}|}{
	\begin{minipage}{160.15pt}
	Mecanismo de dados
	\end{minipage}
	}
	&
	\multicolumn{1}{m{163.75pt}}{
	\begin{minipage}{163.75pt}
	Estrutura da memória
	\end{minipage}
	}
\\\hline
	\multicolumn{1}{m{160.15pt}|}{
	\begin{minipage}{160.15pt}
	Geometria das comunicações
	\end{minipage}
	}
	&
	\multicolumn{1}{m{163.75pt}}{
	\begin{minipage}{163.75pt}
	Rede de interconexão
	\end{minipage}
	}
\\\hline
	\multicolumn{1}{m{160.15pt}|}{
	\begin{minipage}{160.15pt}
	Tamanho do algoritmo
	\end{minipage}
	}
	&
	\multicolumn{1}{m{163.75pt}}{
	\begin{minipage}{163.75pt}
	\begin{flushleft}
	Número de processadores e tamanho da memória
	\end{flushleft}
	\end{minipage}
	}
\\\hline
\end{tabular}

\caption{Relação entre as características do \textit{hardware} e do \textit{software} paralelo}
\label{tab:algoparaleloversusarquitetura}
\end{table} 

\end{flushleft}



\subsubsection{Critérios para Caracterização das Arquiteturas Paralelas}
\label{CCAP}

Segundo a proposta de MOLDOVAN \cite{MOL93}, as arquiteturas dos computadores paralelos podem ser caracterizadas pelos seguintes critérios: complexidade do processador, modo de operação, estrutura da memória, rede de interconexão e número de processadores/tamanho da memória.

\textbf{Complexidade do processador}: trata do poder computacional e da estrutura interna de cada elemento de processamento. Sistemas cujos processadores tem capacidade idêntica são ditos homogêneos. Aqueles sistemas cujos processadores são diferentes, ou são direcionados para realizar funções específicas, são ditos heterogêneos. A complexidade do processador varia bastante de uma classe de arquitetura para outra. Em processadores sistólicos, por exemplo, as células de processamento são simples, e os dados são apenas processados, nunca armazenados. Em processadores matriciais (SIMD), alguma memória precisa estar associada ao elemento de processamento.

Em multiprocessadores, por sua vez, cada nodo de processamento pode incorporar memória local, memória cache, e gerenciamento de memória. A complexidade do processador está associada à granulosidade do algoritmo. Arquiteturas de grão-elevado tem poucos processadores bastante poderosos; um exemplo típico é a conhecida arquitetura do Cray X-MP, a qual atinge no máximo quatro processadores, porém extremamente poderosos. Um exemplo de arquitetura de grão-médio é o multiprocessador Cedar que emprega oito \textit{clusters} do Alliant FX-8, cada \textit{cluster} com oito processadores. Uma arquitetura de grão-fino utiliza um grande número de processadores pequenos. Uma representante típica desta arquitetura é a \textit{Conection}\textit{ }\textit{Machine} que atinge 64.536 pequenos processadores.


\textbf{Modo de operação:} refere-se tanto ao controle de instruções como à manipulação dos dados. O modo tradicional de operação é comando-por-fluxo (\textit{command}\textit{-}\textit{flow}), assim chamado porque a seqüência de eventos é controlada por comandos derivados do fluxo de instruções. Outro método é disparar as operações à medida que os seus operandos tornam-se disponíveis, de acordo com o modelo comando-por-dados (\textit{dataflow}); neste caso, o controle é determinado pela disponibilidade dos dados. Outra alternativa de controle ainda, é o comando-por-demanda (\textit{demand}\textit{-}\textit{flow}), no qual as computações ocorrem somente se seus resultados são solicitados por outras. É possível a combinação destes modos de controle. O modo de operação da arquitetura é relacionado com o modo de controle da concorrência do algoritmo.

\textbf{Estrutura da memória}: refere-se ao modo de operação e à organização da memória do \textit{hardware} paralelo. A memória pode ser acessada utilizando tanto endereços como conteúdo de dados (como nas memórias associativas). Em arquiteturas não convencionais, como as orientadas a conexão (\textit{Connection}\textit{ }\textit{Machine}) ou redes neurais, a memória consiste de interconexões ponderadas, cujo peso relativo indica a alternativa a ser utilizada. Nas arquiteturas convencionais, a organização e o tamanho da memória estão fortemente associadas ao mecanismo de dados utilizado pelo algoritmo.


\textbf{Rede de interconexão:} diz respeito às conexões de \textit{hardware} entre processadores,  bem como destes com os bancos de memória. Considerando o desempenho, a rede de interconexão deve ser o mais semelhante possível à geometria das comunicações do algoritmo paralelo. Computadores paralelos com redes de interconexão simples e/ou fixas conseguem ser eficientes para um determinado conjunto de tipos de algoritmos. Redes de interconexão complexas, ao contrário, podem ser configuradas para atender um ampla faixa de aplicações; naturalmente isto torna o \textit{hardware} mais caro, e também possivelmente irá crescer o custo (\textit{overhead}) decorrente de um número maior de comutações no caso de uma rede reconfigurável dinamicamente.


\textbf{Número de processadores e tamanho da memória}: indica quantos processadores o sistema paralelo contém, e o tamanho da memória disponível. Para a tecnologia atual, e considerando apenas o número de processadores e não o seu poder computacional, sistemas com 1 a 100 processadores são considerados pequenos, sistemas com 100 a 1000 processadores são considerados médios, e sistemas com mais de 1000 processadores são considerados grandes ou muito grandes. Como regra geral, um número maior de processadores confere à arquitetura um maior poder computacional, o que faculta ao sistema paralelo trabalhar com problemas mais complexos.

Quando o tamanho do algoritmo é maior que o tamanho do sistema, se faz necessário particionar o mesmo durante a execução; isto implica que à medida que os módulos de processamento (vide granulosidade do módulo) são atribuídos aos processadores e às memórias, os resultados intermediários precisam ser armazenados. O particionamento de algoritmos pode introduzir efeitos colaterais (\textit{side}\textit{-}\textit{effects}) indesejáveis. Do ponto de vista ideal, o número de processadores deve ser compatível com o tamanho do algoritmo.

A abordagem desta seção enfatizou que o processamento com desempenho otimizado em arquiteturas paralelas, exige uma sintonia entre as características do \textit{hardware} e do \textit{software}. A próxima seção deste capítulo, objetiva apresentar as propriedades necessárias em um modelo de programação paralela, para que o esforço do programador para obter esta sintonia seja minimizado.

\subsection{Propriedades de um Modelo de Programação para o Processamento Paralelo}
\label{PMPPP}

Uma alternativa para a situação de falta de portabilidade e curto tempo de vida útil do \textit{software} paralelo é o desenvolvimento de um modelo que seja abstrato o suficiente para ocultar os aspectos da arquitetura à medida que eles se alteram, ao mesmo tempo que mantém o desempenho da aplicação paralela desenvolvida. Em essência, um modelo deste tipo contempla uma máquina abstrata, para a qual o \textit{software} seria desenvolvido, e que seria eficientemente emulada nas diferentes arquiteturas paralelas. Assim, este modelo atuaria como uma fronteira entre as arquiteturas paralelas sempre em evolução, e o desenvolvimento de \textit{software} com sua exigência de vida longa, desassociando os aspectos do projeto do \textit{software}, daqueles de sua implementação. A figura \ref{fig:modelocomputparalela} resume esta proposta.

Nesta seção serão discutidos os aspectos de um modelo ideal para o desenvolvimento de \textit{software} paralelo. A organização adotada foi proposta em SKILLICORN \cite{SKI98}. Os  recursos mínimos que este modelo deve oferecer são os seguintes:

\begin{figure}
	\centering
	\insimg{1}{imagens/modelo-para-computacao-paralela.jpg}

	\caption{Modelo Para Computação Paralela}
	\label{fig:modelocomputparalela}
\end{figure}



\subsubsection{Facilidade para o Desenvolvimento do \textit{Software}}
\label{FDS}

Os aspectos pertinentes ao controle da execução paralela são bastante complexos. Na medida do possível, o modelo deve retirar do programador a responsabilidade sobre os mesmos. Para tanto, deve ficar ao encargo do compilador e do ambiente de execução, a inserção e a gerência dos mecanismos necessários. Assim, o modelo deve prover:

	
\begin{itemize}
\item decomposição do programa em tarefas paralelizáveis. Para sua execução paralela, o programa deve ser dividido em partes passíveis de serem executadas concorrentemente pelos diversos processadores da arquitetura. Isto implica em fracionar o código e a estrutura de dados em partes, cujo número e tamanho são função das características da arquitetura;

\item mapeamento das tarefas paralelas aos processadores. Uma vez que o programa tenha sido dividido, se faz necessária a decisão de em qual processador será alocada cada tarefa. Um dos principais critérios para decisão é o volume de comunicações, de tal forma que tarefas com volume de comunicações elevado entre si tenham posições o mais próximo possível na rede de interconexões. No caso de arquiteturas heterogêneas (vide item \ref{CCAP}), pode ser muito significativo para o desempenho levar em conta as características do processador no momento da alocação de uma determinada tarefa;

\item comunicação entre as tarefas paralelas. Sempre que uma tarefa necessita de um dado não disponível localmente, algum mecanismo de comunicação deve ser ativado para obtê-lo. A forma específica de atuação do mecanismo é dependente da arquitetura, porém é indispensável que as tarefas paralelas que trocam dados tenham suporte para tal, evitando atrasos no processamento em função de dados que custam a vir, ou que eventualmente nem mesmo virão;

\item sincronização entre as tarefas paralelas. É relativamente usual no processamento paralelo, duas ou mais tarefas precisarem confirmar se todo o grupo já atingiu determinado ponto comum da computação. Neste caso, também a especificidade do mecanismo que será utilizado é fortemente dependente da arquitetura. O tema sincronização é bastante amplo e complexo. Existe na relação entre comunicação e sincronização um grande potencial para inconsistências no estado de execução (\textit{deadlocks}).
\end{itemize}

\subsubsection{Uma Metodologia para o Desenvolvimento de Software}
O recurso previsto no item anterior (\ref{FDS}), deixa clara a distância semântica entre a informação a ser disponibilizada pelo programador e a necessária para execução do programa em paralelo. Para superar isto, se faz necessária uma sólida fundamentação semântica, sobre a qual as técnicas de transformação de código possam ser aplicadas.

A usual metodologia de testes e depuração utilizada na programação seqüencial, se mostra inviável para o desenvolvimento de \textit{software} paralelo, sobretudo pelos seguintes motivos:
	
\begin{itemize}
	\item o particionamento e o mapeamento das tarefas, os quais podem em alguns casos depender dos dados, ampliam a um ponto tal a complexidade da análise dos possíveis estados da computação paralela que seu uso efetivo é praticamente inviável;
	
	\item a equipe de desenvolvimento teria acesso apenas a algumas das arquiteturas paralelas nas quais o \textit{software} poderia vir a ser executado. Este aspecto fica reforçado pela heterogeneidade que as arquiteturas paralelas podem assumir, bem como pelo constante surgimento de arquiteturas com novas tecnologias no mercado.

	\item a existência, nas arquiteturas paralelas, de componentes que dificultam a reprodução exata de execuções, como por exemplo o não determinismo inerente à maioria das redes de interconexão.
\end{itemize}

Como a comprovação do comportamento dos possíveis estados do \textit{software} paralelo após seu desenvolvimento, se mostra complexo demais para uso prático, somente um processo, que leve na direção de um \textit{software} correto por metodologia de construção, colocará o desenvolvimento de \textit{software} em um patamar de segurança e conforto razoáveis (vide item \ref{DSA}).


\subsubsection{Independência de Arquitetura}
\label{IArq}
O modelo deve ser independente de arquitetura, de tal forma que os programas possam migrar entre as arquiteturas paralelas, sem exigir alterações no código ou outras modificações não triviais. Por outro lado, as arquiteturas paralelas, como aglutinam diversas tecnologias, todas em constante evolução, tem sua vida útil efetiva de poucos anos. Isto torna pouco razoável considerar a rescrita do \textit{software} a cada necessidade de trocar o \textit{hardware}.

Atender este aspecto de independência de arquitetura de forma individual é uma tarefa factível. Existem diversos modelos cujo nível de abstração satisfazem este aspecto (vide item \ref{MPEFTI}).

O complexo é atender este requisito em conjunto com os outros, que um bom modelo para o desenvolvimento de aplicações paralelas deve suprir.


\subsubsection{Facilidade para Ser Entendido}

Um modelo, para que se dissemine largamente, deve ser fácil de ser entendido. Se o processamento paralelo pretende ampliar sua fatia de mercado, o modelo para sua programação deve poder ser assimilado com facilidade pelos desenvolvedores, oferecendo para isto uma interface que oculte ao máximo a complexidade inerente ao paralelismo e seja de uso simples.


\subsubsection{Garantia de Desempenho}

Um modelo deve garantir o desempenho dos programas para ele desenvolvidos, nos diversos tipos de arquiteturas disponíveis. Segundo SKILLICORN \cite{SKI98}, somente um modelo com otimização nas comunicações pode ter previsibilidade no desempenho. Por sua vez, considerando a diversidade dos problemas reais, heurísticas complexas para otimizar o mapeamento das tarefas paralelas, considerando o custo das comunicações, podem introduzir custo computacional elevado. Assim, somente modelos que limitem a freqüência das comunicações, podem esperar ter uma garantia mínima de desempenho em diferentes \textit{hardwares} paralelos.


\subsubsection{Medidas de Custo}

O desenvolvimento de \textit{software} para arquiteturas paralelas tem sempre presente a premissa de buscar o maior desempenho possível, o que tem reflexos diretos no tempo que o programa exige do \textit{hardware} para completar sua execução.

Além do desempenho global, a taxa de utilização individual dos processadores, e o custo de desenvolvimento, são importantes indicadores para análise do custo total decorrente das etapas de projeto, programação e execução do \textit{software} paralelo.

A proporcionalidade de desempenho entre as plataformas seqüenciais, faculta que uma análise da complexidade dos algoritmos empregados no programa traga uma expectativa de desempenho, independentemente do \textit{hardware} específico que será utilizado. Na programação paralela tal situação não ocorre; pequenas modificações no programa ou a troca do \textit{hardware} paralelo podem mudar completamente o comportamento do programa (vide item \ref{RAAP} ).

Segundo SKILLICORN \cite{SKI98} um modelo oferece medidas de custo se for possível determinar o custo de um programa, em particular a partir de:

\begin{itemize}
	\item código fonte do programa;
	\item propriedades mínimas da arquitetura paralela destino (por exemplo, o número de processadores);
	\item informações a respeito do tamanho dos dados de entrada (não os seus valores);
\end{itemize}


No texto SKILLICORN \cite{SKI98}, também é caracterizada a importância de considerar os aspectos de modularidade. É relativamente usual que o \textit{software} de grande porte seja desenvolvido por módulos, e possivelmente cada módulo por equipes diferentes. Isto implica que a medida de custo precisa ter um comportamento composicional, isto é, o custo total possa ser inferido a partir do custo das partes.

Considerando as outras características indispensáveis para um modelo de programação paralela, por exemplo, a necessidade de abstração tratada no item \ref{IArq} a medida de custo se torna uma característica difícil de ser atingida.
