\subsection{A Importância da Rede de Comunicação}
Em cluster a eficiência do sistema da rede de comunicação entre os nós é de extrema importância e criticidade. Se a rede falha ou tem baixo desempenho, o cluster inteiro sentirá esse problema e, por conseqüência, o desempenho do sistema como um todo será atingido.

Assim é comum se projetar redes para cluster pensando não apenas no desempenho e latência desta, mas também na alta-disponibilidade da rede.

É importante considerar que uma rede é um elemento bastante seguro a nível físico: dificilmente uma vez instalada, a rede fisicamente irá falhar.


Outro tópico importante da rede é a sua eficiência: uma rede congestionada destrói o desempenho do cluster. Assim, dependendo do tamanho do cluster, e da quantidade de nós pertencentes a este, a rede poderá ser a culpada diretamente pela baixa eficiência computacional do cluster. É por isto que o investimento em uma rede tecnologicamente moderna é habitual nestes tipos de sistemas.

\subsection{Redes de Interconexão Utilizadas em Arquiteturas Paralelas}
\label{redesinter}

Não importando o tipo da arquitetura, todo computador paralelo necessita de uma rede de interconexão para criar canais de comunicação entre os seus diversos recursos de processamento, armazenamento e entrada/saída. Considerando a diversidade das alternativas tecnológicas, esta seção vai explorar aspectos centrais pertinentes ao tema, a partir dos quais, podem ser entendidas as várias alternativas possíveis para as redes de interconexão.


\subsubsection{Alternativas para Interligar o Processador à Rede de Interconexão}

Do ponto de vista da organização do \textit{hardware}, existem duas possibilidades para o posicionamento das chaves de interconexão (vide figura \ref{fig:altprocessador}) apresentada por MORSE (\cite{MOR94}):
\begin{itemize}
	\item \textbf{chave associada ao processador}: neste caso, na maioria das vezes a chave está localizada no mesmo circuito integrado (\textit{chip}) do processador. Nesta implementação é possível para o processador enviar e/ou receber múltiplas mensagens concorrentes, o que em determinadas situações pode ser oportuno para exploração do paralelismo. Como exemplo, temos o emprego desta tecnologia nas arquiteturas SIMD (vide item \ref{arqsincm}) CM-1, CM-2 e AMT DAP, e também nas arquiteturas MIMD (vide item \ref{arqmemodist}) nCube, Transputer, iWarp e KS-1.
	\item \textbf{chave independente do processador}: nesta implementação, o processador tem um único canal com a sua chave de interconexão. A principal vantagem deste caso é a maior flexibilidade para criação de nós heterogêneos na arquitetura. Os nós responsáveis pela entrada/saída poderiam utilizar a mesma chave de interconexão que os nós processadores. Embora não seja uma prática comum, esta segunda estratégia também faculta que possam ser trocados os processadores e mantida a rede de interconexão. As arquiteturas SIMD não utilizam esta segunda opção de chave. Alguns exemplos de arquiteturas MIMD que a empregam seriam o Intel Paragon, a CM-5 e o Cray T-3D. Uma desvantagem decorrente da dissociação entre o processador e a chave de interconexão é o prejuízo do nível de integração (mais circuitos integrados, mais conexões, etc.).
\end{itemize}



\begin{figure}[!htb]
	\centering
	\insimg{1}{imagens/alternativa-para-conectar-o-processador-a-rede-de-interconexao.jpg}

	\caption{Alternativas para conectar o processador a rede de interconexão}
	\label{fig:altprocessador}
\end{figure}



\subsubsection{Características que Definem o Desempenho de uma Rede de Interconexão}
\label{redesdesemp}

Além da topologia da rede de interconexão, as outras características que se destacam na definição do seu desempenho são:

\begin{itemize}
\item \textbf{largura de banda do canal}: número de \textit{bytes} por segundo que pode fluir entre dois nós com conexão direta. Via de regra, a largura de banda é dependente do número de pulsos por segundo da arquitetura (\textit{clock}) e do número de \textit{bits} possíveis de serem enviados por pulso.
\item \textbf{latência de comutação}: tempo inerente à operação da chave de comutação. Se dois processadores precisam trocar dados, e não existe um canal interligando os dois diretamente, as chaves de comutação intermediárias precisam propagar a mensagem através da rede de interconexão. As latências elevadas trazem prejuízo ao desempenho da arquitetura paralela, sobretudo quando a mensagem necessita passar por diversas chaves.
\item \textbf{independência de processador}: caracteriza a necessidade de o processador ser ou não interrompido, para auxiliar na atividade de comunicação. Muitas das atuais implementações de redes de interconexão permitem que o processador continue sua computação enquanto uma mensagem está sendo transmitida, recebida ou roteada. Isto minimiza o custo introduzido pela
necessidade de comunicação entre processadores.
\item \textbf{contenção}: pode ocorrer a recepção praticamente simultânea de duas mensagens por uma determinada chave, e ambas podem necessitar usar o mesmo canal de saída. Uma obrigatoriamente terá de aguardar. O atraso na computação do processador que aguarda a mensagem retida pode resultar em perda de desempenho. Uma possibilidade é o \textit{hardware} de comutação prever uma política de tempo compartilhado para as portas das chaves; isto dividiria o custo de espera entre os dois processadores destinatários, porém introduziria custos de comutação (vide latência de comutação).
\end{itemize}


\subsection{Topologias da Rede de Interconexão}

A interconexão direta de todos os processadores, entre si, não é viável quando o número dos mesmos aumenta. Como regra geral é utilizado um padrão para definir as ligações. Este padrão é denominado de topologia da rede de interconexões. Três parâmetros podem ser utilizados para caracterizar o possível desempenho de uma topologia. Os mesmos são: a largura da bisseção, o diâmetro e o grau (BAKER \cite{BAK96}).

A \textbf{largura da }\textbf{bisseção} indica quantas mensagens simultâneas podem ser trocadas entre duas metades da rede de interconexão. É um indicador da largura de banda possível para as comunicações através da rede.
O \textbf{diâmetro} indica qual o menor número de nós intermediários que precisam ser envolvidos, para que dois processadores, o mais distantes possível, se comuniquem.

O \textbf{grau} indica o número máximo de mensagens que podem ser manipuladas (enviadas ou recebidas) simultaneamente por cada um dos processadores.

\subsubsection{Topologia em Barramento}

Nesta topologia, todos os processadores estão conectados em um único barramento compartilhado. Quando um processador necessita comunicar-se com outro, ele aguarda que o barramento esteja livre e propaga no mesmo a mensagem; o destinatário, por sua vez, identifica que a mensagem é para si e a recebe (vide figura \ref{fig:topbarramento}).

No caso de duas transmissões simultâneas, o \textit{software} detector de colisões interrompe as transmissões e os processadores voltam a tentar novamente após um período de tempo determinado aleatoriamente.

Assim sendo, a sua largura da bisseção é 1. Isto significa que esta topologia não permite mais do que um par de processadores em comunicação simultaneamente.



\begin{figure}[!htb]
	\centering
	\insimg{1}{imagens/topologia-em-barramento.jpg}

	\caption{Topologia em barramento}
	\label{fig:topbarramento}
\end{figure}

Do ponto de vista do desempenho, esta topologia somente é viável para um pequeno número de processadores e/ou classes de problemas cujos algoritmos implementem pouca comunicação. Esta topologia é bastante usual em pequenos agrupamentos (\textit{clusters}) de estações de trabalho interligadas por redes locais.

\subsubsection{Topologia em Malha}
Os processadores nesta topologia tem um canal de comunicação direto com o seu vizinho (a). Uma variação que é utilizada consiste em interligar as extremidades da grade, criando uma configuração denominada malha toroidal (b), a qual reduz o diâmetro da malha por um fator de 2 (vide figura \ref{fig:topmalha}).


A largura da bisseção de uma malha é $\sqrt{N}$ onde $N$ é o número de processadores. A largura da bisseção dobra para a malha toroidal. O diâmetro da topologia em malha é $2(\sqrt{N}- 1)$, e o seu grau é fixo e de valor 4.



\begin{figure}[!htb]
	\centering
	\insimg{1}{imagens/topologia-em-malha.jpg}

	\caption{Topologia em malha}
	\label{fig:topmalha}
\end{figure}


O \textit{hardware} para este tipo de tecnologia é de simples construção e expansão. A malha se adapta bem a algoritmos utilizados em cálculos científicos,  onde se destaca a manipulação de matrizes.


Uma arquitetura que utiliza esta topologia é o Intel Paragon.


\subsubsection{Topologia em Hipercubo}
\label{hipercubo}

Toda rede de interconexão hipercúbica está alicerçada sobre uma estrutura multi-dimensional baseada em endereços binários.

Os tamanhos do hipercubo são definidos por potências de 2; N=2\textsuperscript{D} onde D é a dimensão do hipercubo e N o número de processadores.

Em função disto, todos os nós podem ser identificados por um número binário. Cada nó é conectado a todos os seus vizinhos; isto faz com que o hipercubo tenha grau variável e de valor D (vide figura \ref{fig:tophipercubo}).


\begin{figure}[!htb]
	\centering
	\insimg{1}{imagens/topologia-em-hipercubo.jpg}

	\caption{Topologia em hipercubo}
	\label{fig:tophipercubo}
\end{figure}



A topologia hipercúbica confere boas propriedades à rede de interconexão; a largura da bisseção é $N/2$, e o diâmetro é log$_{2}$ $N$. Apesar de apresentar bom desempenho para muitos padrões de comunicação, sua eficiência se mostra bastante dependente do algoritmo de roteamento a ser empregado.

Um aspecto inconveniente do hipercubo é sua escalabilidade, o número de processadores sempre cresce em potência de 2. Além disso, como o grau de cada nó é em função do tamanho do cubo, toda expansão no número de processadores implica em adicionar mais um canal de comunicação a todos os nós. Para cubos maiores, estas características podem trazer inconvenientes para a administração do custo/benefício quando da expansão da arquitetura. Um equipamento que emprega esta topologia é o Ncube 2.

\subsubsection{Topologia em Árvore}
A clássica árvore binária, com processadores nas suas folhas, tem se mostrado uma boa opção de topologia para arquiteturas paralelas. O diâmetro de uma árvore completa é 2log$_{2}$((N+1)/2), bastante similar ao do hipercubo ($N$ é o número de processadores). A largura da bisseção, por sua vez, é somente 1, o que pode introduzir um severo gargalo quando processadores de uma metade da árvore precisarem se comunicar com os da outra metade.


A solução para pequeníssima largura da bisseção da árvore é utilizar uma variante denominada árvore larga. Em uma árvore larga (vide figura \ref{fig:toparvore}), a largura dos ramos (canal) cresce a medida em que se sobe das folhas em direção à raiz.

\begin{figure}[!htb]
	\centering
	\insimg{1}{imagens/topologia-em-arvore.jpg}

	\caption{Topologia em árvore}
	\label{fig:toparvore}
\end{figure}



A largura da bisseção da árvore larga plena é N e o seu diâmetro proporcional a $2(log N)$. A arquitetura da CM-5 da \textit{Thinking} \textit{Machines} utiliza uma versão modificada da árvore larga.



\subsection {Dispositivos de interconexão}


Já estão disponíveis comercialmente dispositivos de interconexão que propiciam a criação de ambientes similares a multicomputadores ou multiprocessadores, utilizando computadores convencionais.

Existem atualmente duas grandes classes de dispositivos de interconexão para alto desempenho. Uma primeira classe é formada por dispositivos cuja solução é baseada em programação por troca de mensagens entre processadores no nível de placa de rede, esta solução permite a criação de multicomputadores. Exemplos de equipamentos desta classe são: \textit{Myrinet}, \textit{Gigabyte System Network} e \textit{Giganet}, sistemas que utilizam rede \textit{Gigabit ethernet} também são encontrados, mas com desempenho de rede mais baixo. Não se pode confundir as tecnologias \textit{Gigabit ethernet}, \textit{Gigabyte System Network} e \textit{Giganet}. A \textit{Gigabit ethernet} é a mais conhecida, utilizada e de menor custo, todavia o seu desempenho é muito menor comparado com as outras soluções.

A segunda classe é formada por interconexões e tem como peculiaridade uma solução que cria a abstração de uma memória virtual única (multiprocessador) entre todos os computadores interligados no dispositivo. Exemplo desta são o \textit{Quadrics Network} (QSNET) e \textit{Dolphin SCI}.

% \begin {itemize}
% %   \item Ethernet
% %   \item Fast Ethernet
%   \item Gigabit Ethernet - ok
%   \item Gigabyte System Network
% %   \item Giganet
%   \item myrinet - ok
%   \item quadric
%   \item SCI
% \end {itemize}

\subsubsection{\textit{Gigabit Ethernet}}

% Cereja, Sales, Silveira em seu trabalho de fim de curso \cite{PFEXCL} explicam a tecnologia, como se segue:

O padrão \textit{Gigabit Ethernet} é uma extensão dos padrões 10 Mbps \textit{Ethernet} e 100 Mbps \textit{Fast Ethernet} para interconexão em redes. Esse padrão surgiu da necessidade criada pelo aumento da largura de banda nas "pontas" das redes (ex.: servidores e estações de trabalho) e também pela redução constante dos custos entre as tecnologias compartilhadas e comutadas, juntamente com as demandas das aplicações atuais.

O padrão \textit{Gigabit Ethernet} tem como principais vantagens a popularidade da tecnologia \textit{Ethernet} e o seu baixo custo. Trata-se de uma tecnologia padrão, protegendo o investimento feito em recursos humanos e em equipamentos. Não há nenhuma nova camada de protocolo para ser estudada, conseqüentemente, há uma pequena curva de tempo de aprendizagem em relação à atualização dos profissionais. Graças às vantagens trazidas por essa tecnologia, ela tornou-se também outra possibilidade para a interconexão em clusters.

Apesar da alta velocidade, o padrão \textit{Gigabit Ethernet} não garante o fornecimento de QoS (Qualidade de Serviço), que é um dos pontos mais fortes da tecnologia ATM. Desta forma, ele não pode garantir o cumprimento das exigências de aplicações, como a videoconferência com grande número de participantes, ou mesmo uma transmissão de vídeo em tempo-real de um ponto para muitos outros.
%O fato do custo por porta da \textit{Gigabit Ethernet} ser mais alto, quando comparado com a \textit{Myrinet}, e devido ao uso de cabos de fibra-ótica. Contudo, uma queda substancial no custo da \textit{Gigabit Ethernet} agora é aparente. Os custos baixos estão impulsionando a \textit{Gigabit Ethernet} para tomar uma fatia cada vez maior de mercado, caracterizado pela competição entre diversos fabricantes e um potencial muito grande de base de instalações; eventualmente, o custo por porta da \textit{Gigabit Ethernet} se tornará comparável ao custo de um nó convencional, de forma muito parecida com o que ocorreu com  a \textit{Fast Ethernet} há alguns anos atrás. %A \textit{Myrinet} nunca terá uma difusão tão larga, o seu nicho de mercado (\textit{system area networks}) permanecerá extremamente pequeno quando comparado com LANs, e portanto, seu preço nunca terá uma queda representativa.

\subsubsection{\textit{Myrinet}}
\label{myricom}

% Cereja, Sales, Silveira em seu trabalho de fim de curso \cite{PFEXCL} explicam a tecnologia, como se segue:
	
\textit{Myrinet} é um tipo de rede baseada na tecnologia usada para comunicação e troca de pacotes entre processadores trabalhando em paralelo. \textit{Myrinet} implementa auto-inicialização, baixa latência e switches ``\textit{cut-through}". As interfaces de \textit{host} mapeiam redes, selecionam rotas, controlam o tráfico de pacotes e transformam endereços de rede em rotas. Seu \textit{software} otimizado permite que seja feita uma comunicação direta entre os processos do usuário e a rede. Uma diferença em relação às LAN's está nas altíssimas taxas de transmissão e nas baixíssimas taxas de erro, além de controle de fluxo em todos os \textit{links}.

Um \textit{link} \textit{Myrinet} é um par \textit{full-duplex} de canais \textit{Myrinet} opostos. Um canal \textit{Myrinet} é unidirecional e ele é o meio de comunicação que carrega caracteres de informações. O fluxo do remetente pode ser bloqueado, temporariamente, pelo receptor a qualquer hora, durante ou entre pacotes, usando controle de fluxo.

Num ambiente de comunicação confiável pode-se empregar roteamento ``\textit{cut-through}", no qual não existe a bufferização do pacote inteiro com checagem de erro no ``\textit{checksum}".

No roteamento ``\textit{store-and-forward}", se o canal de saída está ocupado ele fica enfileirado num circuito de roteamento ou nó, que supostamente tem memória suficiente para bufferizar o pacote. Já no roteamento ``\textit{cut-through}" os circuitos de roteamento podem bloquear com controle de fluxo se o canal de saída não estiver disponível. Desta forma o circuito de roteamento ``\textit{cut-through}" não requer bufferização, pois cada \textit{link} pode prover seu próprio controle de fluxo. Para prover o controle de fluxo, as redes MPP reconhecem cada unidade de fluxo de controle,  tipicamente um \textit{byte}.



\subsubsection{\textit{InfiniBand}}
\label{infinitband}

% Cereja, Sales, Silveira em seu trabalho de fim de curso \cite{PFEXCL} explicam a tecnologia, como se segue:

\textit{InfiniBand} é uma arquitetura que define um barramento de computador serial de alta velocidade,  projetado tanto para conexões internas quanto externas. Ele é o resultado da combinação de duas tecnologias concorrentes, Future I/O, desenvolvida pela Compaq, IBM e Hewlett-Packard com a Next Generation I/O (ngio), desenvolvido por Intel, Microsoft, Dell, Hitachi, Siemens e Sun Microsystems. Em agosto de 1999, os sete líderes da indústria, Compaq, Dell, Hewlett-Packard, IBM, Intel, Microsoft e Sun Microsystems formaram a IBTA (\textit{InfiniBand Trade Association}). A primeira especificação da arquitetura \textit{InfiniBand} foi feita em junho de 2001.

A arquitetura \textit{InfiniBand}  surgiu devido à necessidade de se melhorar o desempenho dos dispositivos de E/S e das comunicações, que surgiu juntamente com o aumento da capacidade de processamento dos processadores.

\textit{InfiniBand} é uma arquitetura ponto-a-ponto que se destina a fornecer aos centros de dados uma conectividade para entradas/saídas melhoradas e adaptadas a qualquer tipo de tráfego. Uma conexão \textit{InfiniBand} substituirá os vários cabos atuais e servirá simultaneamente para a conectividade do cluster (proprietária), da rede (em vez do \textit{Gigabit Ethernet}) e do armazenamento (em vez da atual \textit{Fibre Channel}).É uma tecnologia comutada que utiliza três tipos de dispositivos, comutadores, interfaces HCA (\textit{Host Channel Adapter}), que são os conectores usados na comunicação interprocessadores do lado dos servidores e nas interfaces TCA (\textit{Target Channel Adapter}), que são tipicamente usadas para conexão nos subsistemas de E/S.

A tecnologia \textit{InfiniBand} utiliza uma estrutura hierárquica, com comunicação do tipo ponto-a-ponto. Nessa abordagem, todo nó pode ser o iniciador de um canal para qualquer outro. Ainda é possível que vários dispositivos de E/S peçam dados simultaneamente ao processador.

As duas principais vantagens do \textit{InfiniBand} são a baixa latência e alta largura de banda. A baixa latência beneficia principalmente as aplicações sensíveis à latência, com comunicação entre processos (IPC) e sistemas gerenciadores de bancos de dados (DMBS). A alta largura de banda beneficia principalmente as aplicações que necessitam grande largura de banda, como armazenamento, web, computação de alto desempenho, e outras aplicações especializadas, como edição de vídeo. %A Figura 02 apresenta uma comparação da latência entre \textit{InfiniBand} e \textit{Gigabit Ethernet}, enquanto a Figura 5 apresenta um gráfico que compara a largura de banda disponibilizada pelas duas tecnologias.

Devido a suas características, \textit{InfiniBand} é uma tecnologia adequada para aplicações de HPC (\textit{High Performance Computing}). Enquanto \textit{InfiniBand} provê muitas características avançadas que servem para um grande leque de aplicações, contudo esta tecnologia ainda é um padrão em evolução e deve sofrer muitas melhorias. Algumas das melhorias planejadas para \textit{InfiniBand} incluem especificações de maiores taxas de sinalização, controle de congestionamento e qualidade de serviço (QoS).


\subsubsection{\textit{Gigabyte System Network}}

GSN é um padrão ANSI (\textit{American National Standards Institute}) de tecnologia de rede que foi desenvolvida para redes de alta performance enquanto mantém compatibilidade com tecnologias de rede como HIPPI, \textit{Ethernet}, e outros padrões de rede. GSN tem uma alta capacidade de banda (800MB por segundo) e baixa latência.

Características:

    \begin{itemize}
	\item Capacidade de Banda: acima de 800MB por segundo em \textit{full-duplex}. Velocidade comparável com \textit{Fibre Channel}, ATM OC12, \textit{Gigabit Ethernet}, and HIPPI;
	\item Latência: latência de 4 microseconds; latência do MPI é de 13 microseconds;
	\item Interoperabilidade: IP sob GSN, ST sob GSN, BDS sob GSN e ARP sob GSN;
	\item Biblioteca para diversos S.O.
	\end{itemize}

Mais informações podem ser obtidas no endereço: \www{http://hsi.web.cern.ch/HSI/gsn/gsnhome.htm}


\subsubsection{\textit{Quadrics Network (QSNET)}}

\textit{Quadrics Network}, também conhecida como QSNET, consiste de dois blocos. Um chamado de ``ELAN", que representa uma interface de rede programável, e outro chamado de ``ELITE"~ que é caracterizado pelo switch de alto desempenho e baixa latência. Os dispositivos ELITE são interligados em forma de topologia ``\textit{Flat-Tree}", alcançando a possibilidade de interligação da ordem de milhares de dispositivos de comutação.


\subsubsection{\textit{Scalable Coherent Interface (SCI)}}

SCI é um padrão recente de comunicação utilizado na interligação de componentes de um cluster. A abordagem cria um sistema de compartilhamento de memória global, através de um sistema de coerência de cache, baseado em diretórios distribuídos.


\input{parte3/protocolosderede.tex}
