%montar inclusoes de páginas no parte3.tex
\chapter{Alta Capacidade de Processamento (HPC)}
\label{clusterprocessamento}

Cluster de Processamento de alto desempenho (HPC - High Performace Cluster), essa categoria de cluster possui como principal característica o processamento de alta performance/desempenho, grandes usuários dessa tecnologia no brasil são: Universidades, centros de pesquisa, INPE, Petrobras.

% Pode ser dividida em 4 principais grupos:

\section{Beowulf}
\label{beowulf}
% \subsection{Descrição}

Beowulf é o nome de um projeto de cluster de computadores para computação paralela, usando computadores pessoais, não especializados e portanto mais baratos. O projeto foi criado por Donald Becker \footnote{Mais informações sobre Donald Becker podem ser encontradas na WikiPedia \www{http://en.wikipedia.org/wiki/Donald\_Becker}} da NASA, e hoje são usados em todo mundo, principalmente para programação científica.

Um cluster de Beowulf é um grupo de computadores, normalmente PCs idênticos que executam como sistema operacional o GNU/Linux ou BSD. Eles trabalham em uma rede LAN TCP/IP pequena, e tem bibliotecas e programas instalados que permitem o compartilhamento do processamento entre eles, mais informações sobre essas bibliotecas e ferramentas podem ser obtidas na sessão \ref{trocademensagens}.

Não existe nenhum \textit{software}, ou a utilização de algum \textit{software}, em particular que defina um cluster como cluster Beowulf. Existem bibliotecas de processamento paralelo que geralmente são usadas no cluster Beowulf, essas bibliotecas incluem: MPI\cite{MPI} (\textit{Message Passing Interface}) e PVM\cite{PVM} (\textit{Parallel Virtual Machine}). Ambos permitem o programador dividir uma tarefa entre um grupo de computadores conectados em rede, e recolher os resultados das tarefas processadas.

Assim o nome \textit{Beowulf} acaba sendo a descrição de ambientes de clusters de processamento paralelo freqüentemente encontrado. Existem várias distribuições e soluções em \textit{software livre} e aberto para esses ambientes. Pode-se citar como exemplos de soluções desenvolvidas para a criação de ambientes \textit{Beowulf}: Oscar, Rocks, Xcat (citadas na sessão \ref{ferramentasdecluster}).

Além das soluções que facilitam a instalação e configuração deste ambiente existem outras ferramentas de suporte, como ferramentas para o monitoramento, controle e execução de tarefas nos nós.



% \subsubsection{Características a serem Observadas para o Desenvolvimento de Sistemas/Softwares para Clusters.}
% 
% 
% - Mpi e PVM - principais características: Voltados para aplicações com demanda de grande capacidade de processamento, muito utilizadas em simulações e no meio científico, é necessário reescrever as aplicações para rodar nesse tipo de cluster.
%  

\section{Sistema de Imagem Única (SSI)}

Sistema de Imagem Única (SSI) são métodos utilizados para se esconder à complexidade dos sistemas distribuídos, permitindo que os mesmos pareçam uma única máquina ao usuário. Logo desta maneira os fatores como a heterogeneidade do \textit{hardware} implementado não será problema para o seu funcionamento, e questões como a gerência e utilização efetiva dos recursos serão facilmente solucionadas. Conseguindo assim a visão de uma máquina única, da mesma maneira que uma máquina SMP só que na verdade utilizando-se de um ambiente de rede distribuído, construídos de várias máquinas. \cite{BUYYA99}.

Em clusters, o SSI auxilia tanto na escalabilidade quanto na disponibilidade. Os recursos de um cluster SSI são a soma dos recursos disponíveis no cluster. Assim o sistema é visto como um único recurso, a adição ou subtração de alguns desses recursos não afeta potencialmente o funcionamento do cluster, permitindo muitas vezes, um incremento de recursos em tempo de execução, dependendo da escalabilidade suportada. Pode também assegurar que o sistema continue funcionando após alguma falha em um ou alguns de seus nós sem que haja perdas consideráveis, permitindo que o cluster fique sempre disponível para as aplicações do usuário.

A visualização dos nós como um SSI permite a monitoração centralizada dos recursos de cada um deles, tornando-se possível um balanceamento de carga efetivo, dividindo os processos entre os nós da melhor maneira fazendo com que os recursos sejam bem utilizados. Permite também uma hierarquia globalizada com múltiplos sistemas de arquivos e espaço único de
memória e de dispositivos de entrada e saída, além de um endereçamento global para os processos.

Embora a implementação do SSI ainda seja muito limitada nos clusters, já apresenta vários benefícios, e que estão evoluindo a todo o momento, permitindo um incremento tanto da escalabilidade quanto do sistema de imagem única, podendo  se gerar uma estrutura cada vez mais próxima da estrutura SMP, só que com uma excelente escalabilidade. O SSI pode ser implementado através de \textit{hardware}, multiprocessadores \ref{multiprocessadores}, ou por \textit{software}, este último geralmente é feito utilizando­se de uma camada de \textit{middleware} ou uma camada adicional (\textit{patch}) ao kernel \cite{BUYYA01}.


O \textit{middleware} é composto de uma camada de infra­estrutura de disponibilidade que fica acima da camada do sistema operacional e por uma camada de infra­estrutura de imagem única que fica logo acima da primeira, a camada de SSI é quem faz a interface com as aplicações dos usuários. Todos os pacotes trabalham em conjunto dando melhor suporte a essas camadas, providenciando também uma eficiente implementação para DSM, \textit{checkpoint} e migração de processos.


\subsection{As Principais Características de um Cluster SSI}

A seguir estão descritas as principais características que um cluster deve possuir para
ser considerado um Sistema de Imagem Única, segundo Buyya \cite{BUYYA01}:

\begin{itemize}
\item Ponto único de acesso: garantia de transparência ao usuário da máquina ao qual o mesmo está se logando em meio a todos os nós do cluster. Desse modo diferentes nós atendem diferentes usuários, dividindo a carga apresentada pelas requisições de cada usuário de forma transparente ao mesmo.

\item Interface única de usuário: os usuários devem acessar o cluster através de uma única interface gráfica de usuário, tal como uma página web onde se possam usufruir os serviços associados ao cluster. Essa interface deve possuir as mesmas características para todos os usuários.

\item Espaço de processo único: todos os processos, independemente do local onde se encontrem, devem poder se comunicar com processos de quaisquer nós; devem poder migrar para qualquer nó e podem geram novos processos. Um cluster SSI deve permitir a administração dos processos como se estivessem sendo executados localmente, isto é, deve­se garantir o controle dos processos independentemente do local onde estejam sendo executados.

\item Espaço de memória único: deve­se garantir ao usuário a ilusão de um espaço único de memória, de forma que os diversos espaços locais dos inúmeros nós que compõem o cluster fossem uma única grande memória. Para isso existem diferentes abordagens tais como o uso de \textit{software} garantindo uma camada acima da memória de cada nó, simulando a existência de um único espaço de memória; o outro modo é o desenvolvimento distribuído, isto é, implementação no próprio código através do uso de bibliotecas tais como MPI ou PVM, onde o compilador do sistema onde se executa a aplicação se encarrega de distribuir a estrutura dos dados entre os diversos nós do cluster.

\item Espaço de E/S único: garantir a execução de operações de entrada/saída a periféricos e discos tanto localmente quanto remotamente, de forma transparente ao usuário. Fazendo assim um único espaço de endereçamento formado pelos diversos discos associados aos nós do cluster, RAIDs anexados à rede e um exemplo.

\item Hierarquia única de arquivos: os usuários ao terem acesso ao sistema de arquivos do cluster SSI devem possuir uma visão única do mesmo, de modo com que todos identifiquem os diversos discos, periféricos e diretórios sob uma mesma raiz de uma única forma. Exemplos de hierarquia única para um sistema de arquivos são o NFS, o MFS e o GFS.

\item Rede virtual única: um nó deve possuir a capacidade de acessar qualquer conexão de rede através do domínio do cluster, mesmo que a rede não esteja conectada a todos os nós do cluster.

\item Sistema de administração de \textit{jobs} único: um \textit{job} de um usuário pode ser submetido de qualquer nó do cluster e pode requisitar quantos nós quiser para executá-lo.% Exemplos de sistemas para administração de \textit{jobs} são: GLUnix, LSF e CODINE.

\item Ponto de controle e administração único: todo o cluster, isto é, cada um dos nós que o compõe devem poder ser testados, configurados e monitorados através de um único conjunto de interfaces gráficas tais como uma página web.

\item Migração de processos e \textit{checkpointing}: deve­se fazer periodicamente a gravação das informações dos processos tais como estado e processo ou em memória ou em disco, garantindo em caso de falha do mesmo sua continuação em outro nó. Além disso devido à necessidade de balanceamento de carga deve­se garantir a migração de processos entre os diversos pontos do cluster.
\end{itemize}

\subsection{Os Principais Benefícios de um Sistema SSI}

Os principais benefícios que um sistema SSI proporciona ao funcionamento de um cluster, segundo Buyya \cite{BUYYA01}:

\begin{itemize}
    \item Provê uma simples e única visão de todos os recursos e atividades em execução no cluster;
	
    \item Exclui do usuário a necessidade de apontar onde se deve executar tal aplicação;
	
    \item Garante o uso de recursos independentemente da proximidade física aos mesmos;
	
    \item Permite maior facilidade para gerenciamento do sistema pelo administrador e uso do mesmo pelo usuário já que a interface e os comandos são um só para o acesso a todos os nós;
	
    \item Reduz a possibilidade de erros por parte do operador, por exemplo: utilizar uma sintaxe de comandos diferentes para o acesso a um mesmo nó, e outra sintaxe diferente para um outro nó. Desta maneira garantindo performance e confiabilidade ao sistema;
	\item Como o controle deve ser apresentado de forma centralizada, o uso do sistema por pessoas sem que essas tenham elevado conhecimento sobre como este funciona. Isto permite o seu uso por usuários ``comuns";
	\item Redução de gastos com a implantação/manutenção do sistema;

	\item Prove comunicação de mensagens independente de localização;

	\item Como os programadores não devem se preocupar com a distribuição da carga para suas aplicações garante­se mais tempo aos mesmos para aumentar a complexidade e qualidade de seus sistemas.

	\item Promove a padronização de ferramentas para o seu controle e administração.
\end{itemize}


\subsection{Memória Distribuída Compartilhada (DSM)}

Técnica utilizada para compartilhamento de memória física dos nós, dando a ilusão de que o cluster possui uma única e grande memória que é formada pela agregação das memórias de seus nós, implementando a abstração de um espaço comum de endereçamento agrupando as memórias isoladas em uma entidade lógica, podendo ser implementada por \textit{software} ou \textit{hardware}, permitindo a troca de dados através de uma memória globalizada a todos os nós processadores \cite{TANENBAUM02}.

Com essa técnica, não há mais a necessidade de usar paradigmas de passagem de mensagens explícitas como PVM ou MPI nos programas desenvolvidos especialmente para cluster, pois os programas que utilizam ''memória distribuída compartilhada'' têm acesso as variáveis em memória, da mesma forma como se faz em variáveis locais em sistemas que não tem memória compartilhada.

Cada processador tem uma visão de toda a memória, mas só tem acesso a parte que é destinada a ele, então, caso ele queira acessar dados que não estão localizados na parte onde ele é proprietário, deve fazer uma cópia para sua área, dando origem a cópias múltiplas da mesma porção de dados da memória compartilhada em diferentes memórias físicas, tendo assim, que manter a coerência destas cópias, permitindo que qualquer processador que acesse a memória compartilhada devolva a informação correta, sendo a comunicação e a sincronização feita através da própria memória.

Para se reduzir à latência de memória, ou seja, os tempos de acesso à memória e retorno da resposta, as \textit{caches} privadas a cada processador são utilizadas, pois em sistemas DSM há uma grande sobrecarga com a localização dos dados e acesso a memória distribuída, ficando esses \textit{caches} com a função de \textit{buffers} temporários, para que não se desperdice ciclos do processador.

Quando um programa é feito, existe uma ordem especifica de acesso a memória, chamada consistência seqüencial. Num cluster essa consistência é inviável pois os nós teriam que esperar a sua vez de acessar a memória para assim continuar processando, isso geraria perda de desempenho e tráfego excessivo na rede. Para isso foram desenvolvidos modelos de consistência que levam em consideração que nem todos os nós processadores precisam naquele momento do conteúdo atualizado.

Esses modelos implementam métodos que tentam evitar ao máximo as condições de corrida, ou seja, acesso simultâneo ao mesmo dado. Cada nó possui um mapeador de memória local onde ela é particionada em blocos, sendo a \textit{cache} utilizada para reduzir a latência de acesso à memória remota e sendo a memória principal dos nós um \textit{cache} da DSM, formando assim uma hierarquia simples de memória, ou seja, cada nó enxerga sua memória local como uma \textit{cache} da DSM sendo cada bloco da memória a unidade básica de \textit{cache}.



\subsection{OpenMosix}

O openMosix é um \textit{middleware} para \textit{clustering} ``open-source"~ que possui dois módulos de grande valia ao serviço de \textit{clustering}: um patch para memória compartilhada distribuída (migshm) e um módulo para \textit{checkpointing}.

Memória compartilhada é usada na maior parte das aplicações modernas, tais como bancos de dados, servidores WEB, editores de texto, planilhas, e processamento de imagens. A operação de compartilhamento de memória ajuda a facilitar a troca de dados entre os processos.

Por exemplo, quando dois clientes fazem um select e um update em uma coluna de uma tabela MySQL, o MySQL deve criar dois subprocessos e servir os comandos SQL. Os processos ``forked"~ se anexam ao processo MySQL principal que mantém os dados em memória. Usando esse esquema, não existe a necessidade de se criar um \textit{data mirror} e plugá-lo de volta à tabela real.

O benefício é que o servidor de banco de dados por reduzir a alocação de memória. Evidentemente, um mecanismo de ``locking"~ é necessário para evitar um ``deadlock"~ ou uma condição de corrida.
Uma ``thread"~ é uma versão leve de um mecanismo fork( ). Ao invés de duplicar todo um segmento de memória de um processo pai para um processo filho, o processo recém­criado  apenas precisa inicializar um pequeno segmento de dados e se anexar ao processo principal. Essa técnica (também chamada de ``LightWeight Process", ou LWP) oferece uma nova maneira de multiprocessamento usando o mínimo possível de memória. O apache, servidor WEB, utiliza \textit{threads} para aumentar a velocidade de suas tarefas de forma a permitir aumentar o número de hits sem afetar sua performance.

O Migshm é um patch DSM (\textit{Distributed Shared Memory}) para o openMosix. Ele permite a migração de processos que utilizam memória compartilhada no openMosix tais como o apache, entre outros.

``Checkpointing"~ é uma técnica que provê a possibilidade de se salvar contextos de processos em um arquivo de disco e dar um restore dos processos a partir do arquivo. Logo processos que tenham sofrido ``checkpointing"~ e que sejam reiniciados posteriormente deveriam funcionar como se não tivessem sido interrompidos. Essa funcionalidade é útil para tarefas que possuam longos períodos de execução (como simulações numéricas) no caso de instabilidade de sistema, falhas de energia, reinicializações do sistema, etc. ``Checkpointing"~ costuma ser um serviço de sistemas operacionais avançados de \textit{clustering}.

O CHPOX (\textit{Checkpointer for Linux}) é um módulo do kernel Linux que provê ``checkpointing"~ de processos. Ele foi criado por Olexander O. Sudakov e Eugeny S. Meshcheryakov no Information and Computing Center do National Taras Shevchenko University em Kyiv, Ucrânia. O CHPOX usa uma abordagem de módulo de kernel, logo ele é pouco relacionado à versão do kernel atual e é dinamicamente inserido e removido do espaço de kernel. Devido à sua integração com o Mosix/openMosix, o CHPOX se tornou rapidamente aceito pela comunidade openMosix.

{\bf Tecnologia openMosix}

O openMosix é um conjunto de algoritmos para compartilhamento dinâmico de recursos que são utilizados para fornecer escalabilidade e performance em um cluster CC (\textit{Cache Coherent}) de qualquer tamanho, onde o único componente compartilhado é a rede. A idéia principal da tecnologia do openMosix é a capacidade de múltiplos nós (\textit{workstations} e servidores, incluindo SMP's) de trabalharem em cooperação como parte de um sistema único.

Com o sentido de compreender o que o openMosix faz, devemos comparar multicomputador de memória compartilhada (SMP) a um CC. Em um sistema SMP, múltiplos processadores compartilham a memória. As principais vantagens  são o aumento do volume de processamento e a maior velocidade de comunicação entre os processos(através da memória compartilhada). Máquinas SMP podem suportar múltiplos processos trabalhando simultaneamente, com eficiente alocação e compartilhamento de recursos. A qualquer momento que um processo seja inicializado, finalizado, ou mude seu perfil computacional, o sistema  se  adapta  instantaneamente  ao  ambiente  de  execução  resultante.  O  usuário  não é envolvido diretamente e, na maior parte dos casos, nem sabe da existência de tais atividades.

Ao contrário do SMP, Clusters Computacionais (CC) são feitos de coleções de servidores (até mesmo SMP's) e \textit{workstations} que fisicamente nada compartilham, com diferentes velocidades e quantidades de memória, possivelmente de diferentes gerações. Na maioria das vezes, CC's são utilizados para ambientes ``time­sharing"~ e multi­usuário. Em sistemas CC o usuário é responsável por alocar os processos aos nós e a administrar os recursos do cluster. Em vários sistemas CC, mesmo estando todos os nós utilizando o mesmo sistema operacional, a cooperação entre os nós é consideravelmente limitada pois a maioria dos serviços do sistema operacional são localmente confinadas ao nó.

Os principais pacotes de \textit{software} para alocação de processos em CC's são PVM e MPI. Esses pacotes provêem um ambiente de execução que requer uma adaptação da aplicação e o conhecimento do usuário. Eles incluem ferramentas para alocação inicial (fixa) de processos para nós, os quais algumas vezes utilizam considerações sobre a carga, enquanto ignoram a disponibilidade de outros recursos tais como memória livre e ``overheads"~ de E/S. Esses pacotes ficam na camada de usuário, assim como as aplicações comuns, entretanto são incapazes de responder a mudanças no nível de carga ou mesmo de outros recursos, ou até de redistribuir a carga do trabalho (\textit{job}) de forma adaptativa.

Na prática, o problema de alocação de recursos é muito mais complexo pois existem vários tipos diferentes de recursos, tais como CPU, memória, E/S, IPC (Comunicação Inter-Processos), etc, onde cada recurso é utilizado de uma maneira diferente e na maior parte das vezes seu uso é imprevisível. Outras dificuldades surgem do fato que diferentes usuários não coordenam suas atividades. Entretanto mesmo que um usuário saiba otimizar a alocação de recursos aos processos, as atividades de outros usuários costumam interferir em sua otimização.

Para o usuário, os sistemas SMP garantem eficiência, uso balanceado de recursos entre os processos em execução, independentemente dos requisitos de recurso. SMP's são fáceis de usar pois eles empregam administração adaptativa de recursos, o que é completamente transparente ao usuário. Os atuais CC's não possuem tais capacidades. Eles se baseiam na alocação estática controlada pelo usuário, o que é inconveniente e pode levar a significativas perdas de performance devido a cargas mal distribuídas.

O openMosix é um conjunto de algoritmos que juntos suportam compartilhamento adaptativo de recursos em um CC escalável pela migração dinâmica de processos. Ele pode ser visto como uma ferramenta que torna plataformas CC  mais próximas de ambientes SMP. Ao  ter a  capacidade  de  alocar  recursos  globalmente,  e distribuir o ``workload"~ dinamicamente e de forma eficiente acaba por simplificar o uso de CC's ao tirar do usuário a responsabilidade de administrar os recursos do cluster. Isso é particularmente evidente em ambientes multi-usuários e ``time-sharing", além de CC's não uniformes.





\subsection{Kerrighed}

Kerrighed é uma base operacional para sistemas de imagem única (\textit{Single System Image Operating System} (SSI OS)) destinado para cluster construídos a partir de PCs padrões de mercado.

Um sistema operacional SSI dá a ilusão de uma máquina de SMP aos programas que são executados em cima dele. Kerrighed é uma extensão kernel do Linux. Não obstante, um cluster rodando Kerrighed não é uma máquina de SMP real.


As metas do Kerrighed são alto desempenho de aplicações, alta disponibilidade do cluster, administração de recursos eficientemente, alta poder de customização do sistema operacional e facilidade de uso.

Kerrighed é implementado como uma extensão a sistema operacional GNU/Linux (uma coleção de módulos e um pequeno \textit{patch} para o kernel Linux).


As principais características do Kerrighed são:

\begin{itemize}
\item Escalonador customizável para o cluster.\\
Processos e \textit{threads} são automaticamente escalonados através dos nós do cluster para balancear o uso de CPU através do escalonador padrão do Kerrighed. Porém, Kerrighed oferece um \textit{toolkit} para escrever escalonadores sob encomenda com facilidade, que podem serem adicionados ``a quente"~ nos módulos do kernel.

\item Memória Compartilhada.\\
\textit{Threads} e segmentos de memória do sistema podem ser operados através do cluster, como em uma máquina SMP.

\item Mecanismos de migração de fluxo de alta performance.\\
Podem ser migrados processos que usam fluxos (socket, pipe, fifo, char device, etc) sem penalidade no desempenho de comunicação depois de migração.

\item Sistema de arquivo distribuído.\\
   Um único espaço de nome de arquivo é visto no cluster. Todos os discos do cluster são fundidos em um único disco virtual em um customização parecida como um RAID.

\item Verificação de processos.\\
Os processos podem ser verificados e reiniciados em qualquer nó do cluster.

\item Interface de \textit{Thread} Posix completa.\\
A interface de \textit{Thread} Posix pode ser operada com \textit{threads} espalhadas pelos nós do cluster.

\item Interface de processos Unix visível em todo o cluster.\\
Toda a interface tradicional de comandos de gerenciamento de processos Unix (top, ps, kill, etc) são operados pelo cluster. Além disso, os identificadores de processos (pid) são únicos no cluster.

\item Características customizáveis da imagem única de sistema.\\
As características do SSI (memória compartilhada, escalonador global, migração de fluxos, etc) podem ser ativados ou não por base de processos.


\end{itemize}



Kerrighed não é:

\begin{itemize}
\item Um paralelizador automático.\\
Kerrighed não paraleliza automaticamente suas aplicações. Isso implica que caso você tenha um grande processo seqüencial, ele não rodará mais rápido no Kerrighed. Para rodar mais rápido, sua aplicação precisará ser paralelizada. Se sua aplicação roda mais rapidamente em uma maquina com vários processadores do que em uma máquina com apenas um processador, essa aplicação poderá rodar mais rápido com o Kerrighed. Se a aplicação não roda mais rápido em uma maquina com vários processadores, ela não rodará mais rápido com o Kerrighed.

\item Um Middleware.\\
Kerrighed é um sistema operacional, e não um \textit{middleware}. Ele roda dentro do kernel linux, e não em cima do kernel linux. Ele estende as funcionalidades do linux de gerenciamento de serviços de cluster.

\item Uma máquina virtual.\\
Kerrighed não tem correlação nenhuma com tecnologias de virtualização como VMWare ou XEN. Ele não cria um cluster virtual, ele dá a ilusão que um cluster físico de PCs são uma máquina SMP única.
\end{itemize}


