Jean Rodrigo dos Santos Rafael Caetano Pinto

Valdemárcio Fernandes dos Santos

BioCluster

Comparação de Seqüências de DNA em Sistemas Distribuídos Clusterizados

Osasco Dezembro de 2005

2

Jean Rodrigo dos Santos Rafael Caetano Pinto

Valdemárcio Fernandes dos Santos

BioCluster

Comparação de Seqüências de DNA em Sistemas Distribuídos Clusterizados

Trabalho de Conclusão de Curso para o curso de Engenharia de Computação do Centro Universitário FIEO como requisito parcial para a obtenção do título de bacharel em Engenharia de Computação.

Orientadores: Prof. Antonio Fernando Nunes Guardado Prof. Francisco Isidro Massetto

Osasco Dezembro de 2005

3

Persevera na tua determinação.

4

Agradecemos às pessoas abaixo que contribuíram para a conclusão desse projeto:

Antonio Fernando Nunes Guardado,

Celso Silva,

Gabriela M. de Azevedo Souza,

Jean M. Laine,

Jonas Santiago de Oliveira,

Maisa Barros de Oliveira,

Maria Clara de Carvalho Silva,

Martin R. Whittle,

Paulo Cunha,

Pedro Rosa,

Sidney da Silva Viana.

Em especial, agradecemos a Francisco Isidro Massetto, pois sem sua ajuda e boa vontade, esse projeto não seria possível.

iv

5

Resumo

Esse projeto visa a construção e a configuração de um Sistema Distribuído aplicado para a comparação de seqüências de DNA. Será mostrada neste trabalho toda a especificação necessária para a construção e implementação do mesmo.

Um dos objetivos principais abordados nesse trabalho é a preocupação na elaboração de uma solução menos custosa financeiramente em relação aos Sistemas Centralizados Proprietários sem que haja uma queda significativa no desempenho da aplicação.

Para se alcançar esse objetivo, será utilizada uma estrutura de rede FastEthernet e alguns micro-computadores interconectados sobre o protocolo TPC/IP. Como exemplo para a implementação deste sistema clusterizado, foi escolhido o algoritmo CGM/BSP de similaridade de seqüências, devido ao fato de que nessa aplicação, dependendo do conjunto de dados a se comparar, é necessário um alto poder computacional para se realizar a comparação entre seqüências.

Palavras-chave: Cluster. DNA. RMI. Sistemas Distribuídos.

v

6

Abstract

This project aims the construction and the configuration of a Distributed System suitable for a DNA sequences comparation. All specifications needed for its construction and implementation will be shown at this project.

One of the main subjects approached at this work is the concern about a cheaper solution elaboration in relation to an Owner Centralized Systems without a deep fall on the application s performance.

A basic net structure with one switch and a few personal computers interconnected using the TPC/IP protocol will be created to reach the subject of this project. As an example for the clustered system implementation, a comparative between DNA s has been chosen, due to the needed of a high computational power, in order to carry this comparison out between sequences, although it can depend on the data group to be compared.

Keywords: Cluster. DNA. RMI. Distributed Systems.

vi

7

Sumário

Resumo ................................................................................................................................. 5

Abstract ................................................................................................................................. 6

Sumário ................................................................................................................................. 7

Capítulo 1 ............................................................................................................................ 10 Objetivos.......................................................................................................................... 11 Justificativa ...................................................................................................................... 12 Metodologia ..................................................................................................................... 13

Capítulo 2 ............................................................................................................................ 14 Introdução a Sistemas Distribuídos................................................................................. 15

Comparação dos Sistemas Distribuídos com os Sistemas Centralizados.................. 15 Mudança de paradigma de programação ................................................................ 17

Modelo Cliente-Servidor .............................................................................................. 17 Simplicidade ............................................................................................................. 18 Baixa taxa de overhead na rede .............................................................................. 18 Níveis de protocolos................................................................................................. 18 Bloqueadas ou não-bloqueadas .............................................................................. 18 Bufferizadas e não-bufferizadas .............................................................................. 19 Confiáveis e não-confiáveis ..................................................................................... 19

Clusters............................................................................................................................ 19 Características de um Cluster ..................................................................................... 19

Alto desempenho ..................................................................................................... 19 Escalabilidade .......................................................................................................... 20 Confiabilidade e tolerância à falha........................................................................... 20 Alta disponibilidade .................................................................................................. 20 Independência.......................................................................................................... 20 Transparência .......................................................................................................... 21

Comunicação entre processos no Cluster................................................................... 22 Cluster Homogêneo e Heterogêneo............................................................................ 23 Tipos de Cluster........................................................................................................... 24

Cluster de Alto Desempenho ................................................................................... 24 Clusters de Alta Disponibilidade .............................................................................. 24 Clusters de Balanceamento de Cargas ................................................................... 24 Exemplos de Clusters .............................................................................................. 24

Cluster Beowulf..................................................................................................... 24 Invocação Remota de Métodos (RMI) ......................................................................... 27

RMI-Registry.................................................................................................................... 28 Exemplo de programa em RMI ................................................................................ 28

Ola.java (interface) ............................................................................................... 28 OlaImpl.java (implementação do servidor)........................................................... 29 OlaCliente.java (cliente) ....................................................................................... 29

Sistema de Arquivo de Rede (NFS Network File System) ....................................... 30

Capítulo 3 ............................................................................................................................ 31 Biologia Computacional................................................................................................... 32

Conceitos de Biologia .................................................................................................. 32 Comparação de seqüências e Alinhamento................................................................ 33

Uma breve explicação de como foi montada a matriz............................................. 36

v

vi

8

Algoritmo para validação de sequências de DNA ....................................................... 38 Similaridade distribuída (CGM/BSP) ........................................................................... 38

Algoritmos de alinhamento e similaridade utilizados como base neste projeto.............. 40 Algoritmo básico do método alignment() da classe DNA ............................................ 40 Algoritmo básico do método similarity() da classe DNA.............................................. 41 Algoritmo básico do método CGM/BSP() da classe DNA ........................................... 42

Capítulo 4 ............................................................................................................................ 43 Especificações do projeto................................................................................................ 44

Conceitualização do projeto ........................................................................................ 44 Modularização e divisão de responsabilidades ........................................................... 44

Módulo Interface Web .............................................................................................. 45 Módulo Gerenciador................................................................................................. 45 Módulo Executor ...................................................................................................... 45

Estratégia de Comparação CGM/BSP utilizando RMI ......................................... 46 Módulo ClusterKnoppix ............................................................................................ 48

Especificações do sistema........................................................................................... 49 Rede ......................................................................................................................... 49 Características dos nós do sistema ......................................................................... 49 Armazenamento dos dados ..................................................................................... 49 Sistema Operacional ................................................................................................ 50 Linguagem de programação .................................................................................... 50 Pacote para aplicação de computação distribuída .................................................. 50 Características do Cluster ........................................................................................ 50 Tratamento de erros................................................................................................. 52 Testes....................................................................................................................... 52

Casos de Uso .................................................................................................................. 54 Caso de Uso Nv0 Sistema distribuído clusterizado para comparação de seqüências de DNA......................................................................................................................... 55 Caso de Uso Nv1 Funcionalidades Gerais............................................................... 56 Caso de Uso Nv2a - Comparar Seqüências de DNA.................................................. 57 Caso de Uso Nv2b - Inserir nova máquina no sistema ............................................... 59 Caso de Uso Nv2c - Inserir seqüência de DNA no banco de dados .......................... 60 Caso de Uso Nv2d - Remover seqüência de DNA do banco de dados...................... 61 Caso de Uso Nv2e Inicializar sistema distribuído .................................................... 62

Diagrama de Classes ...................................................................................................... 63 Parte 1.......................................................................................................................... 63 Parte 2.......................................................................................................................... 64

Diagramas de Seqüência ................................................................................................ 65 Inicialização do Executor ............................................................................................. 65 Inicialização do Gerenciador ....................................................................................... 66 Comparando DNA: Visão do módulo ClusterInterface................................................ 67

Comparando DNA: Visão do módulo Gerenciador ......................................................... 68 Comparando DNA: Visão do módulo Executor: Primeiro Executor ................................ 69 Comparando DNA: Visão do módulo Executor: Executores centrais............................. 70 Comparando DNA: Visão do módulo Executor: Último Executor ................................... 71 Diagramas de Transição de Estado ................................................................................ 72

Executor ....................................................................................................................... 72 Gerenciador ................................................................................................................. 72

Diagramas de Atividade .................................................................................................. 73 Método Similarity ......................................................................................................... 73 Método CGM/BSP ....................................................................................................... 74

Banco de dados............................................................................................................... 75 Diagrama Entidade Relacionamento ........................................................................... 75

9

Domínios .................................................................................................................. 75 Modelo do Banco de dados ......................................................................................... 75 Dicionário de dados ..................................................................................................... 75

tbldna........................................................................................................................ 75 tblrelaction ................................................................................................................ 76

Script de criação de tabelas ........................................................................................ 76 Tabela tblDNA .......................................................................................................... 76 Tabela tblRelaction................................................................................................... 76

Arquivo de configuração do MySQL............................................................................ 76 Interface do Sistema........................................................................................................ 79

Arquitetura da interface:............................................................................................... 79 Interface Web............................................................................................................... 79 Estrutura de comunicação da interface Web............................................................... 80

Evento na página "Tela Principal": Entrada ............................................................. 80 Evento na página "Tela Principal": Clique em Comparar ........................................ 80 Evento na página "Relacionamento": Clique em Pesquisar .................................... 80 Evento na página "Relacionamento": Clique em Relacionar................................... 80

Capítulo 5 ............................................................................................................................ 81 Caracteristicas do Ambiente............................................................................................ 82

Configurações fisicas:.................................................................................................. 82 Máquinas: ................................................................................................................. 82 Rede: ........................................................................................................................ 82

Configurações lógicas:................................................................................................. 82 Máquina Gerenciadora:............................................................................................ 82 Máquina do Repositório de dados: .......................................................................... 82 Máquinas Executoras:.............................................................................................. 82

Metodologia.................................................................................................................. 83

Conclusão ........................................................................................................................... 89

Recomendações para projetos futuros ............................................................................... 90

Referências ......................................................................................................................... 91

Anexo A Implementação do ClusterKnoppix ................................................................... 93 Planejamento................................................................................................................... 93 Instalação ........................................................................................................................ 94 BOOT Remoto................................................................................................................. 95 Aplicação ....................................................................................................................... 101 Resultados..................................................................................................................... 102 Customização................................................................................................................ 103

10

Capítulo 1

Esse capítulo preza a contextualização do projeto, nele serão definidos a justificativa, os objetivos e a metodologia utilizada no desenvolvimento deste trabalho.

11

Objetivos

Elaborar o projeto de um Sistema Distribuído Clusterizado utilizando

algoritmos paralelizáveis existentes para uma aplicação específica e assim, testar o funcionamento desta plataforma distribuída.

Utilizaremos como aplicação o sequenciamento físico de DNA devido a suas características escaláveis e paralelizáveis. Dessa forma poderemos analisar o comportamento do Sistema Distribuído em uma aplicação mediante alterações de configuração com a finalidade de otimizar o processamento como um todo. Obtendo assim, um desempenho no mínimo satisfatório (um desempenho semelhante ao de um sistema centralizado em uma máquina mono-processada com as mesmas características das máquinas utilizadas no cluster).

Os principais objetivos a serem alcançados no projeto são:

Escalabilidade

Incluir ou retirar máquinas do sistema facilmente de forma a manter o sistema escalável conforme a necessidade de desempenho da aplicação;

Custo

Objetiva-se utilizar microcomputadores padrão IBM - PC e uma rede LAN Fast Ethernet TCP/IP por serem mais acessíveis economicamente. Também é decisão de projeto a utilização de uma linguagem multiplataforma (Java) de modo que se obtenha mais versatilidade, minimizando as limitações ocasionadas pelo uso de sistemas operacionais proprietários que geralmente possuem custo elevado.

Acessibilidade

Será desenvolvido um sistema de código aberto que seja economicamente viável em comparação às tecnologias centralizadas proprietárias.

Desempenho

Em um primeiro estágio do projeto, o objetivo é de se projetar um sistema clusterizado com desempenho comparável ao de um sistema centralizado mono-processado. Atingido esse objetivo primário, serão verificadas novas alternativas de projeto para melhorar o desempenho do sistema.

12

Justificativa

Em função do crescente desenvolvimento de Sistemas Distribuídos,

impulsionado pela demanda de alto poder computacional, explorar seus recursos torna-se cada vez mais imprescindível [ERA04]. Com base nesta afirmação, e pelo objetivo de obter um sistema de baixo custo financeiro, este projeto se destina à construção de um cluster para executar tarefas que requeiram um alto poder computacional.

Um cluster é um sistema de processamento paralelo alternativo, que apresenta um desempenho computacional análogo aos sistemas centralizados. Uso de clusters nas soluções de determinados projetos, tais como processamento de imagens ou de massas de dados, torna-se economicamente mais viável que em sistemas centralizados, mantendo um desempenho igual ou superior dependendo da implementação.

Neste projeto, será implementado e testado o algoritmo CGM/BSP, que é uma versão paralela para um algoritmo que compara graus de similaridade entre seqüências de genes. Para uma maior compreensão sobre o assunto, primeiramente será apresentada uma introdução aos conceitos básicos de sistemas distribuídos e clusters, assim como uma breve abordagem dos conceitos da biologia e das aplicações da computação na área biológica, inclusive com os algoritmos para sequenciamento e comparação de DNA, assim como o algoritmo CGM/BSP, que é a base deste trabalho.

Todas as etapas de evolução do projeto, tais como contextualização, especificações, modelagens, desenvolvimento e fase de testes serão documentadas. Há a preocupação inclusive em documentar alguns tratamentos de falhas que podem ser interessantes para desenvolvimentos futuros.

13

Metodologia

Como metodologia abordada, será adotado basicamente o Modelo em Espiral,

também denominado por vários autores como Modelo Evolutivo, em que a cada etapa concluída repete-se o processo de averiguação por meio de protótipos para o aperfeiçoamento do projeto.

Para a documentação, será adotado o conceito de Orientação a Objetos, que melhor atende aos requisitos do projeto uma vez que será utilizada uma linguagem orientada a objeto (Java). Portanto, utilizar-se-á dos padrões da linguagem UML.

14

Capítulo 2

Esse capítulo objetiva apresentar a introdução conceitual sobre sistemas distribuídos, modelos de comunicação, clusters e suas aplicações.

15

Introdução a Sistemas Distribuídos

Neste projeto, a definição de sistema distribuído será uma combinação de

ambas as definições, ou seja, um sistema distribuído é um agrupamento de computadores que se apresenta ao usuário como um sistema único, compartilhando recursos. Desta forma, o Sistema Distribuído apresenta muitas diferenças em relação a um sistema centralizado.

Desde 1945 quando se iniciou a era da computação moderna, os computadores têm sofrido grandes transformações tecnológicas [TAN95]. Durante o período de 1945 a 1980, a necessidade de compartilhar informações era praticamente nula e devido ao pequeno número de computadores nas organizações, as quais muitas faziam uso somente de um computador, quase sempre mainframes.

A necessidade de comunicação foi se intensificando a medida que os computadores foram se tornando mais acessíveis financeiramente, passando a aparecer no cenário empresarial (comercial/industrial) tornando-se umas das principais ferramentas da indústria. Para sanar a deficiência da comunicação, foram desenvolvidas nos anos 80, as redes locais de alta velocidade (LAN). Tais tipos de redes em conjunto com os avanços tecnológicos dos microcomputadores, culminaram no desenvolvimento dos sistemas distribuídos.

Diferentes autores definem de maneira distinta o conceito de sistema distribuído. Segundo Tanembaum [TAN95], Sistemas Distribuídos são definidos como uma coleção de computadores independentes que se apresentam ao usuário como um

sistema único e consistente . Já Couloris [COU01] define sistema distribuído como sendo uma coleção de computadores autônomos interligados através de uma rede de

computadores e equipados com software que permita o compartilhamento dos recursos dos sistemas: hardware, software e dados .

Neste projeto, a definição de sistema distribuído será uma combinação de ambas as definições, ou seja, um sistema distribuído é um agrupamento de computadores que se apresenta ao usuário como um sistema único, compartilhando recursos. Desta forma, o Sistema Distribuído apresenta muitas diferenças em relação a um sistema centralizado.

Comparação dos Sistemas Distribuídos com os Sistemas Centralizados

Atualmente instituições acadêmicas e industriais de modo geral, vêm desenvolvendo aplicações que exigem cada vez mais um alto poder computacional. Entretanto o custo para adquirir tais máquinas com essa característica é extremamente alto em muitos casos proibitivos, fazendo com que essas organizações migrem para outras alternativas.

Uma saída encontrada por especialistas para esse problema foi uma arquitetura de "Sistema Distribuído", que consiste em um aglomerado de microcomputadores mono ou multiprocessados e que executam uma tarefa como se fosse um único sistema.

Enquanto que em um Sistema Centralizado, uma aplicação é executada por um ou vários processadores localizados em um mesmo computador, um Sistema distribuído conte com um certo número de nós (computadores conectado em uma rede

16

comum) onde cada um deles executa uma aplicação ou parte dela.

Em um Sistema Centralizado existem limitações que torna os Sistema distribuídos potencialmente superiores em poder computacional. Por exemplo, um Sistema Centralizado é limitado em espaço físico não podendo comportar muitos processadores numa mesma placa mãe, enquanto que a escalabilidade de um Sistema distribuído o permite a superar a quantidade de processadores em um Sistema Centralizado.

Outra vantagem é o uso da memória (principal) em um Sistema Centralizado multiprocessado, pois as tarefas precisam entrar em uma fila para o uso da memória principal, ao passo que nos Sistemas Distribuídos, cada nó conta com a sua própria memória para uso independente das aplicações.

Entre as vantagens de um Sistema Distribuído em relação a um Sistema Centralizado pode-se citar [Tanenbaum]:

- Custo: o valor financeiro para implementação de um Sistema distribuído é geralmente muito inferior ao valor de um Sistema Centralizado com um poder computacional equivalente, e utilizando um sistema Open Source e linguagem de programação Java, por ser livre e gratuito, no que diz respeito a Softwares, não existe despesas com Licenças;

- Desempenho: Sistema com altíssimo índice de processamento, tais como o Blue Gene (www.top500.org) são capazes de processar 280600 Gflops (consultada em 13/12/2005), tal capacidade atualmente só é possível em plataformas distribuídas;

- Tolerância a Falhas: Um Sistema distribuído pode contar com algoritmos que detectam a falha em um nó e redirecione as tarefas a serem executadas para outro nó. Dessa forma a capacidade de índices de confiabilidade de um Sistema distribuído é superior a um Sistema Centralizado;

- Flexibilidade: os recursos oferecidos por um nó podem ser migrados para outros nós, mantendo assim uma redundância dos recursos e maior disponibilidade dos serviços;

- Escalabilidade: é a característica de um Sistema distribuído tem de acoplar mais computadores à sua rede mantendo a estabilidade e aumentando a eficácia do Sistema.

Entretanto, há desvantagens, que alguns autores consideram desafios, tais como:

- Transparência: um dos objetivos é manter oculto os aspectos distribuídos dos usuários do Sistema. O acesso a arquivos distribuídos por diversos computadores remotos não deve ser diferente a um acesso a arquivos locais. Um usuário deve poder acessar arquivos do Sistema sem precisar saber de sua localização ou comunicação entre processos;

- Segurança: é muito difícil estabelecer um protocolo de segurança eficiente para Sistemas Distribuídos, pois todos os nós possuem acessos entre eles, então algoritmos de segurança para garantir a integridade dos dados devem ser implementados;

- Viabilidade: nem todos as aplicações que executam de maneira eficiente

17

em um Sistema Centralizado irão executar na mesma maneira em um Sistema distribuído. Deve-se verificar se os algoritmos das aplicações são paralelizáveis, pois um Sistema distribuído só é viável se suas aplicações permitirem que sejam fragmentadas e distribuídas entre os nós.

Para esse projeto, a viabilidade do uso de um Sistema distribuído ao invés de um Sistema Centralizado se dá através das vantagens já apresentadas neste capítulo. Justificamos o uso pelo propósito da pretensão de utilizar um sistema robusto para manipular uma grande quantidade de dados e que apresente um baixo custo financeiro em relação aos sistemas mono-processados. Assim, utilizando técnicas de fragmentação de dados e paralelização da aplicação, uma implementação distribuída tende a obter resposta satisfatórias para o nosso intento.

Mudança de paradigma de programação

Uma das dificuldades que envolve a implementação de um Sistema Distribuído é o paradigma da programação distribuída. Programação distribuída prevê as chamadas de métodos localizados em máquinas diferentes através da troca de mensagens e sincronização.

As trocas de mensagens são realizadas através de algoritmos que fazem uso de primitivas como send e receive, essas primitivas podem ser organizadas de forma síncronas ou assíncronas. O que difere uma da outra é o grau de dificuldade que as primitivas assíncronas exigem na implementação de algoritmos de armazenamento de mensagens e temporização. Quando um cliente faz uma requisição a um servidor este pode não estar pronto para receber a mensagem enviada. Para que a mensagem não seja perdida, podem ser implementado algoritmos de armazenamento de mensagens (mail-box).

Para esse projeto, a viabilidade do uso de um Sistema distribuído ao invés de um Sistema Centralizado se dá através das vantagens já apresentadas neste capítulo. Justificamos o uso pelo propósito da pretensão de utilizar um sistema robusto para manipular uma grande quantidade de dados e que apresente um baixo custo financeiro em relação aos Sistemas Centralizados. Assim, utilizando técnicas de fragmentação de dados e paralelização da aplicação, uma implementação distribuída tende a obter resposta satisfatórias para o nosso intento.

Modelo Cliente-Servidor

O objetivo do modelo cliente-servidor é configurar o Sistema Operacional com um conjunto de processos que colaboram entre si para a execução de uma tarefa, denominados servidores e clientes. Servidores, como o próprio nome sugere, são processos que oferecem serviços e acesso a recursos. Os clientes possuem processos que requisitam os recursos e serviços oferecidos pelos servidores. Uma máquina pode executar vários processos, servidores, clientes ou então uma combinação de ambos.

O modelo cliente-servidor utiliza um protocolo simples para comunicação do tipo solicitação/resposta, isto evita a sobrecarga causada pelos protocolos dos modelos OSI e TCP/IP devido ao tamanho cabeçalho e rotinas de controle de mensagens. Neste tipo de protocolo, o cliente envia uma mensagem de solicitação de serviço ao servidor que por sua vez recebe a mensagem, executa o serviço e devolve a resposta ao cliente ou

18

uma mensagem de erro informando o motivo pelo qual a solicitação não foi atendida. Veja figura 2.1.1.

Figura 2.1.1 Modelo Cliente-Servidor

As vantagens deste modelo são:

Simplicidade

Não é necessário estabelecer ou finalizar conexão, pois basta o cliente enviar uma solicitação ao servidor e aguardar pela resposta.

Baixa taxa de overhead na rede

As respostas enviadas pelo servidor em decorrência das solicitações dos clientes servem como confirmação de recebimento da mesma.

Níveis de protocolos

No caso de protocolos idênticos entre as máquinas que estão interagindo (cliente/servidor), são necessários apenas três níveis de protocolos (físico, enlace e request/reply).

Um exemplo de um servidor pode ser observado abaixo:

servidor() sempre faça

recebe(endereço de origem, mensagem) processa(mensagem) envia(endereço de origem, mensagem)

Figura 2.1.2 Exemplo de um servidor

Um exemplo de cliente para o servidor acima está demonstrado abaixo:

cliente() faça

envia(endereço de origem, mensagem) recebe(endereço de origem, mensagem)

Figura 2.1.3 Exemplo de um cliente

Dentre as primitivas que podem ser utilizadas, podem se destacar:

Bloqueadas ou não-bloqueadas

Por ser uma operação de E/S, tanto o cliente quanto o servidor podem ficar

19

bloqueados enquanto o Sistema Operacional envia e recebe uma mensagem. Neste aspecto, se houver alguma falha, tanto o cliente quanto o servidor podem ficar indefinidamente suspensos. Para evitar este tipo de situação, mecanismos de cronômetro (timeout) são utilizados para interromper a operação, caso ela não seja completa.

Bufferizadas e não-bufferizadas

Bufferizadas

as mensagens enviadas são armazenadas de forma

semelhante a uma caixa de e-mails, sendo assim, não há risco de perder alguma mensagem enquanto o processo não está disponível para recebê-la. Assim que o processo fica apto a receber mensagens, ele verifica a existência delas na caixa de e-mails e as executa.

Não-bufferizadas

as mensagens enviadas não ficam armazenadas, ou seja, se o processo não estiver apto a receber, a mensagem é perdida. Esse tipo de primitiva é mais simples de se implementar, porém, dependendo do caso, é necessário a inserção de mecanismos de controle para evitar perda de mensagens.

Confiáveis e não-confiáveis

Confiáveis

Há garantia de que a mensagem sempre será entregue, portanto não é necessário nenhum tipo de tratamento especial para elas.

Não-confiáveis

Não há garantia na entrega de mensagens entre os processos. Para se tratar isso, existem basicamente três abordagens:

Admitir que a primitiva é não-confiável e deixar a responsabilidade de se implementar uma comunicação confiável ao usuário;

Forçar o kernel a enviar mensagens de confirmação de recebimento (ACK);

Estabelecimento de um temporizador (timeout) para cada requisição enviada, assim, se não houver resposta em um determinado período de tempo, a mensagem é enviada novamente.

Clusters

Clusters, também chamados de Aglomerados, são uma implementação de Sistemas Distribuídos que consiste em nós (computadores) de interconexão, podendo ser monoprocessados ou multiprocessados, dentro de uma rede (LAN) de alta velocidade. Esse aglomerado têm por objetivo processar tarefas como um único sistema, tirando proveito do multiprocessamento fornecendo um sistema de grande capacidade de processamento [DEI05].

Características de um Cluster

Segundo Tanenbaum [TAN95], as características fundamentais de um cluster são:

Alto desempenho

A soma das capacidades de processamento de cada computador (nó) incluso

20

na rede pode atingir escala jamais possíveis para Sistema Centralizados. Mesmo fazendo uso de multiprocessadores e de processadores vetoriais, somente será possível utilizar milhares de processadores ao construir sistemas, sobre a forma de um enorme aglomerado.

Escalabilidade

A escalabilidade diz respeito ao fato de ser possível acoplar ou desacoplar

máquinas no cluster, dependendo da necessidade de processamento. Existem algumas características de escalabilidade a serem respeitadas:

Nenhuma máquina tem informação completa sobre o estado do sistema: Nenhuma máquina tem informações completas sobre o estado do Sistema, devido a sua independência de hardware e software das demais máquinas e também pelo modo de comunicação através de mensagens que pode causar congestionamento na rede se todas as máquinas começarem a trocar informações o tempo todo.

Não existe uma sincronização de tempo global: Não existe uma sincronização de tempo global real, ou seja, linear no tempo, apenas uma sincronização lógica utilizada na troca de mensagens entre os nós. Porque com tantas máquinas seria impossível sincronizar o relógio interno do sistema com exatidão.

A falha de uma máquina não compromete o cluster: A falha de uma máquina não deve comprometer o processo como um todo para isso algoritmos de redirecionamento de serviços devem ser implementados.

As máquinas tomam decisões baseadas nas informações locais: As máquinas devem tomar decisões segundo as informações locais devido ao seu modo de comunicação ser através de troca de mensagens. Porque manter um nó atualizado com informações sobre todo o sistema poderia causar muito tráfego na rede e conseqüentemente congestionamento na rede e lentidão no sistema, o que foge da característica de um cluster.

Confiabilidade e tolerância à falha

Se uma máquina falhar isso não deve comprometer o sistema como um todo, sendo para isso implementado algoritmos de redirecionamento de tarefas para outros nós da rede.

Alta disponibilidade

Hardware e software podem ser replicados de modo a assegurar o serviço oferecido.

Independência

21

Cada elemento possui um ou mais processadores, memória, dispositivos de

entrada/saída e seu próprio Sistema Operacional. Este elemento geralmente pode ser desligado e até mesmo removido do cluster sem que isto afete o funcionamento dos demais.

Transparência

O cluster deve se comportar como se fosse um único sistema, passando para

o usuário a imagem de um recurso único. Existem alguns tipos de transparências:

Locação

o usuário não deve saber onde estão localizados os recursos tanto de hardware quanto de software

Replicação

o usuário não toma conhecimento das replicações do Sistema Operacional, arquivos e outros recursos.

Migração

os recursos podem ser removidos de um nó para outro sem a necessidade de trocar seus nomes

Concorrência múltiplos usuários pode compartilhar recursos automaticamente

Paralelismo

atividades distintas podem ocorrer em paralelo sem o conhecimento do usuário

22

Comunicação entre processos no Cluster

Em um cluster, os nós são independentes, possuindo sua própria memória, espaço de armazenamento e processador. A forma de comunicação entre eles é através de troca de mensagens. A mensagem é um arranjo de parâmetros encapsulados enviado através da rede de um computador a outro.

Entretanto a sincronização entre os nós é determinada pela lógica utilizada na troca das mensagens [DEI05].

Para que haja interação entre recursos disponíveis no cluster, são necessárias as implementações de alguns mecanismos de memória compartilhada distribuída [DEI05]. Esses mecanismos consistem na existência de uma variável comum entre todas as máquinas, permitindo que sempre que um processo modifique o valor desta variável, esta seja atualizada nas demais máquinas. Um dos modelos mais comuns de comunicação através de troca de mensagens entre processos é utilizando as primitivas send e receive para envio e recebimento de mensagens, como ilustra a figura 2.2.1.

Figura 2.2.1 - Modelo de comunicação com send e receive. A atualização de uma variável a processos em máquinas diferentes utilizando as primitivas send/receive.

Esta comunicação é viabilizada através da Invocação Remota de Método (RMI) que ajuda o programador neste tipo de aplicação.

23

Cluster Homogêneo e Heterogêneo

Segundo Marcos Pitanga [PIT03], um cluster é homogêneo quando todos os seus nós são dotados das mesmas características (software e hardware) e compartilham a mesma rede de comunicação. E um cluster é heterogêneo quando os seus nós se diferenciam em características ou rede de comunicação.

A característica de um cluster ser ou não homogêneo reflete nas regrar a serem utilizadas para o balanceamento de carga das tarefas que devem ser executadas. Eventualmente, no particionamento de uma tarefa, ao se balancear a carga em um cluster homogêneo, todos os nós receberam cargas iguais, já que compartilham das mesmas características. Evidentemente, possuem o mesmo poder de processamento.

Em um cluster heterogêneo deve-se ter cautela ao distribuir as cargas entre os nós, pois sendo máquinas diferentes umas das outras, seu poder de processamento também difere, Isto exige que seja implementado um algoritmo gerenciador, que analise o poder de processamento de cada nó atribuindo-lhe um peso que servirá de parâmetro e fator decisório para que seja distribuída uma carga compatível com a capacidade de processamento de cada nó.

Embora um cluster homogêneo seja mais atraente por não se preocupar em balancear a carga de tarefas distribuídas, é fato que com a sua ampliação ele se tornará heterogêneo salvo os casos em que não mais será modificado ou encontre máquinas exatamente iguais para a ampliação.

24

Tipos de Cluster

Segundo Deitel [DEI05], há três tipos principais de clusters: cluster de alto desempenho, de alta disponibilidade e de balanceamento. Estes clusters seguem um padrão de características distintos que depende da aplicação.

Cluster de Alto Desempenho

Neste tipo de cluster, todos os nós são utilizados para executar o serviço. Ele é aplicado em problemas computacionais de grande escala que podem se divididos e executados paralelamente.

Clusters de Alta Disponibilidade

Em clusters de alta disponibilidade, alguns nós são usados para executar serviços, enquanto que outros são reservados para assumir o lugar de uma máquina no caso de falha assumindo a execução da tarefa. Este modelo de cluster é muito utilizado em tarefas de missão crítica onde não pode haver falhas de sistema e para se conseguir este nível de confiabilidade é necessário que haja redundância de hardware e software. Esta característica é oferecida pelos clusters de alta disponibilidade onde há replicação de software e hardware.

Clusters de Balanceamento de Cargas

Nesse tipo de cluster existe um nó coordenador que distribui as tarefas entre os demais nós do cluster, de modo que cada um receba uma quantidade de tarefas à executar compatível com o seu poder computacional. Para tanto é necessário que seja atribuído a cada máquina um peso que represente o seu desempenho computacional para que sirva de parâmetros de algoritmos de balanceamento que tomarão decisões com base nestes dados. Os Clusters de Balanceamento de Cargas são utilizados em aplicações de e-business com grandes volumes de usuários.

Exemplos de Clusters

Cluster Beowulf

Desenvolvidos nos laboratórios da NASA, o projeto Beowulf [PIT03][BEO05](1994), liderado por Thomas Sterling, tinha como objetivo proporcionar uma ferramenta de baixo custo financeiro que pudesse resolver grandes tarefas computacionais em ciências espaciais e terrestres do Goddard Space Flight Center (NASA). Na sua primeira versão o cluster Beowulf era dotado de 16 computadores com processador Intel DX 4 ligados via rede Ethernet.

O Beowulf utiliza o modelo cliente/servidor como acesso a todos o nós através de uma conexão remota ao nó servidor.

O nó servidor tem como objetivo controlar o cluster, monitorando e distribuindo tarefas. Os demais nós (escravos) são exclusivamente dedicados para o

25

processamento das tarefas enviadas pelo servidor, podendo ou não ter dados ou discos rígidos. Abaixo segue uma ilustração de um cluster Beowulf (Figura 2.2.3).

Figura 2.2.3 - Cluster Beowulf

Devido ao fato de clusters Beowulf poderem ser construídos com uma variedade de componentes de hardware e software distintos, foi proposto em 1998 um esquema de classificação com o intuito de simplificar as referências sobre o Beowulf e responder aos diferentes tipos de hardware e software:

Beowulf classe 1:

Cluster Beowulf de classe 1 são construídos com componentes comuns do mercado encontrados em pelo menos 3 catálogos nacionais e globais de venda de componentes.

As vantagens do cluster Beowulf são:

Hardware disponível de vários fornecedores (preço baixo, fácil manutenção);

Independência quanto ao fornecedor dos equipamentos;

Apoio a drivers Linux comuns;

Normalmente baseado em padrões (SCSI, EIDE, PCI, Ethernet, etc.).

Desvantagem de um cluster Beowulf classe 1:

Desempenho inferior ao cluster Beowulf classe 2.

Beowulf classe 2:

Cluster Beowulf de classe 2 são simplesmente quaisquer máquinas que não passe no teste de certificação de disponibilidade. Esta classe geralmente oferece maior desempenho a um custo financeiro maior em relação ao cluster Beowulf classe 1.

Vantagens:

Desempenho geralmente maior em relação aos clusters Beowulf classe 1

26

dependendo da configuração (uso de uma LAN de 12 Gb/s só aumentaria o desempenho de aplicações altamente acopladas).

Desvantagens:

Suporte a drivers de dispositivos variados;

Dependência de um único fornecedor de hardware;

Geralmente apresentam um custo financeiro bem mais elevado que os Beowulf classe 1.

Uma classe não necessariamente melhor que a outra depende exclusivamente do custo/desempenho que o sistema requer.

27

Invocação Remota de Métodos (RMI)

A RMI é uma tecnologia desenvolvida pela Sun Microservice, que habilita um processo que está executando em uma máquina invocar um método de um objeto em uma máquina remota [HOR01] [DEI01]. Essa tecnologia trata-se de um protocolo que permite que uma invocação a um método remoto seja feita nos mesmos moldes de uma chamada local, deixando os detalhes de montagem dos parâmetros e transporte transparente para o programa de emite a chamada [HOR01] [DEI01]. A figura 2.4.1 mostra a arquitetura básica de um RMI, composta pelo RMIRegistry, o Server e o Client.

Figura 2.4.1 Arquitetura Básica RMI

A RMI possibilita o desenvolvimento de aplicações distribuídas sem ter programas sockets explicitamente, ou seja, torna toda a parte de sockets transparente ao usuário programador. A sua arquitetura é caracterizada pelas camadas de software a seguir [DEI01]:

Stub: o stub Java é uma interface entre o processo cliente e o objeto remoto. Quando o processo cliente faz uma invocação de um método remoto a camada stub é chamada primeiro, que recebe os parâmetros, serializa-os para montar a mensagem e os envia para a camada RRL (Remote Reference Layer). A serialização de objeto permite que programas em Java possam enviar e receber objetos.

RRL (Remote Reference Layer): a camada RRL recebe os parâmetros, já serializados, do stub e através da camada de transporte envia a mensagem (parâmetros) para o servidor. A RRL do lado do servidor recebe a mensagem e dirige ao Skeleton.

Skeleton: o skeleton é uma estrutura análoga ao stub cliente, que recebe os parâmetros da RRL, de-serializa, identifica o método a ser invocado e faz a chamada para esse método. Ao concluir o método, o skeleton serializa o resultado e o envia ao cliente através da RRL e o stub.

Para a implementação de RMI, é necessário que exista uma classe servidor, na qual está a implementação dos métodos RMI a serem disponibilizados para os clientes. Ao ser inicializado, o servidor deve se registrar no RMIRegistry para que os clientes possam utilizar os seus serviços.

Um cliente RMI, ao tentar executar um método implementado por RMI, faz uma consulta de nome (lookup) no RMIRegistry e este retorna o endereço IP do servidor RMI que contém o método que se deseja. Com isso, o cliente pode enviar diretamente os parâmetros através do stub ao skeleton do servidor que executará a função e retornará o resultado ao cliente.

28

RMI-Registry

Para tornar o objeto servidor disponível para as chamadas remotas, eles

devem ser registrados no RMI-Registry. O RMI-Registry é o servidor de nomes padrão na plataforma Java.

Quando um nó é acoplado a rede de um sistema distribuído, este informa ao RMI-Registry o seu endereço de IP e o nome do objeto que estará disponível para executar as tarefas, de modo que ao solicitar, o cliente obtenha através do RMI-Registry a localização do servidor e o objeto remoto.

Fig. 2.4.2 Arquitetura de um cluster usando RMI-Registry.

1

O servidor é conectado à rede e/ou o sistema operacional é iniciado, então o sistema localiza o servidor de nomes ( RMI-Registry) e se registra informando seu IP e o nome do método que estará disponível para o cliente;

2 O cliente requisita ao RMI-Registry a localização do método que esta necessitando;

3

O RMI-Registry retorna uma resposta com a localização da máquina que tem o método disponível;

4 O cliente faz uma requisição de serviço ao servidor;

5 O servidor responde à requisição;

Exemplo de programa em RMI

Abaixo será mostrado um exemplo de utilização do RMI extraído de [MAS04] com todos os códigos fontes necessários:

Ola.java (interface) /* * Esse programa implementa a interface dentro do RMIRegistry */

import java.rmi.*;

public interface Ola extends Remote{

Cliente

RMI-Registry

Servidor

REDE

2 Requisição da Localização

3 Localização

1 Registry/ método

4 Requisição de serviço

5 - Resposta

29

public String getMensagem() throws RemoteException; }

OlaImpl.java (implementação do servidor) /* * Esse programa implementa o servidor RMI */

import java.rmi.*; import java.rmi.server.UnicastRemoteObject;

public class OlaImpl extends UnicastRemoteObject implements Ola{ public OlaImpl() throws RemoteException{ super(); } public String getMensagem(){ return("Ola - Meu primeiro exemplo RMI"); } public static void main(String args[]){ try{ OlaImpl obj = new OlaImpl(); Naming.rebind("localhost/OlaServer",obj); System.out.println("Servico registrado. Servidor no ar. Ok!"); } catch (Exception e){ System.out.println("Problemas no registro do objeto no servidor"); System.out.println("Erro:"+e.getMessage()); } } }

OlaCliente.java (cliente) /* * Esse programa implementa um cliente RMI */

import java.rmi.*;

public class OlaCliente{ public static void main(String args[]){ Ola o; String msg; System.out.println("Cliente no ar... conectando com servidor"); try{ o = (Ola)Naming.lookup("localhost/OlaServer"); msg = o.getMensagem(); System.out.println("Recebido="+msg); } catch (Exception e){ System.out.println("Problemas ao conectar com servidor"); System.out.println("Erro:"+e.getMessage()); } } }

30

Sistema de Arquivo de Rede (NFS Network File System)

O sistema de Arquivo de Rede (NFS) é um padrão de compartilhamento de arquivo de rede suportado pela maioria das plataformas Linux [DEI05]. Seu funcionamento se dá através da comunicação entre cliente e servidor.

Antes de um cliente NFS acessar um arquivo remoto, ele deve usar o protocolo de montagem (um mecanismo que traduz um endereço de arquivo para um manipulador de arquivo) para montar o diretório que retém o arquivo remoto. Um manipulador de arquivo identifica um arquivo remoto por seu tipo, localização e permissões de acesso. Montar implica em mapear um diretório de arquivo remoto para o diretório local de um cliente.

Para montar o sistema de arquivo o cliente NFS faz uma chamada local ao stub do cliente e ao receber a solicitação de montagem, o skeleton do servidor passa a chamada ao servidor NFS. O servidor NFS examina o seu local de arquivos e exporta o diretório local de arquivos que satisfaz a requisição do cliente, o que significa que o servidor torna o diretório local de arquivos disponível para o cliente. Então o skeleton do servidor retorna um manipulador de arquivos ao diretório local de arquivo, o que permite que o cliente acesse remotamente o diretório de arquivos exportado. O cliente remoto usa esse manipulador de arquivos em todas as requisições subseqüentes de arquivos no diretório de arquivos exportado.

O NFS prevê delegações ao cliente para a manipulação de arquivos. Quando o servidor concede uma delegação de leitura, nenhum outro cliente pode escrever para aquele arquivo a um cliente. Se um outro cliente requisitar acesso de escrita a um arquivo com a delegação de leitura ou de escrita ou se o cliente requisita acesso de leitura com delegação de escrita, o servidor revogará a delegação e requisitará que o cliente original descarregue o arquivo para o disco.

Para uma maior segurança na comunicação entre o cliente e o servidor, o NFS suporta diversos algoritmos de criptografia, usados quando estabelece sessões de comunicação, criptografando cada requisição. O NFS também oferece uma autenticação de clientes por meio das chamadas remotas, evitando que clientes não autorizados acessem os dados.

31

Capítulo 3

Este capítulo apresenta uma introdução à biologia, biologia computacional e aos algoritmos computacionais para comparação de DNAs que serão utilizados no projeto.

32

Biologia Computacional

Segundo Setúbal [SET94], Biologia Computacional pode ser entendida como

sendo a aplicação de técnicas e ferramentas da computação aos problemas da biologia e entre as diversas áreas da biologia, aquela que a aplicação de técnicas computacionais tem sido mais necessária é a biologia molecular, em particular na sua interface com a genética. Ele afirma também que diversas áreas da computação contribuem para o estudo da biologia molecular, como teoria da computação, através da formulação de algoritmos para diversos problemas que surgiram recentemente. A teoria e prática de banco de dados, também se faz necessária, para lidar com enormes massas de informações oriundas dos avanços em técnicas laboratoriais.

O objetivo deste capítulo será desenvolver e demonstrar como algumas das ferramentas computacionais podem auxiliar com o trabalho dos biólogos, como comparação e similaridade que precisa ser efetuados no DNA. Existem outras aplicações que são de grande utilidade para a biologia, porem não serão comentada neste trabalho.

Conceitos de Biologia

As proteínas e ácidos nucléicos são as moléculas fundamentais para todo o ser vivo. O ácido desoxirribonucléico (DNA) é o constituinte básico dos genes. Os genes por sua vez, contém todas as informações necessárias para o desenvolvimento desse organismo. O conjunto de todos os genes de um indivíduo é chamado de genoma. Então, pode-se dizer que o genoma é a especificação primaria e fundamental de um ser vivo.

[ROB03] afirma que os genes podem ser analisados sob três ângulos, porem, para a justificativa desse projeto utilizaremos o ponto de vista molecular, que define o gene como: a seqüência de DNA que contém a informação necessária para sintetizar uma molécula de RNA, e a partir dele construir uma proteína. Os Genes são os segmentos funcionais do DNA e calcula-se que existam cerca de 100.000 genes distribuídos nos 23 pares de cromossomos.

As proteínas são cadeias de aminoácidos necessárias nos organismos para o seu bom funcionamento. A falta de alguma proteína no organismo pode causar sérios problemas e possivelmente a sua morte. Então podemos afirmar que uma mutação nesse DNA pode causar o comprometimento do organismo.

Com a aplicação do conhecimento sobre o DNA, poderemos sintetizar novos remédios a fim de curar ou minimizar os efeitos de doenças até então sem tratamento. Também a aplicação na engenharia genética como pode ser citado o caso de clonagem de animais como ovelhas, vacas, cachorros e primatas. Outra área importante que podemos observar nos tempos modernos é o emprego desse conhecimento na agricultura, no desenvolvimento de produtos de consumo com maior qualidade, mais resistentes a pragas e condições do tempo e em maior quantidade para atender a população que tende ao crescimento.

Se fossemos capazes de ler um genoma, poderíamos predizer todas as características que o seu possuidor terá ou será capaz de ter. O problema é que os genomas são muito extensos, na Tabela 3.1 é demonstrado o tamanho do genoma de diversas espécies.

Espécie Nome Popular Tamanho total do Genoma(pares de base)

33

Bacteriófago vírus 5 x 10 4

Escherichia coli Bactéria 5 x 10 6

Saccharomyces cerevisiae Levedura 1 x 10 7

Caenorhaditis elegans Verme 6 x 10 8

Drosophila melanogaster Mosca 2 x 10 8

Homo sapiens Homem 3 x 10 9

Tabela 3.1: Tamanho do genoma de algumas espécies

Ao contrário do que muitos pensam, biologia computacional não se resume à comparação de seqüências ou casamento aproximado de padrões, embora o resultado deste trabalho seja exatamente isso, porém utilizando um Sistema Distribuído. Existem diversos outros problemas biológicos nos quais algoritmos da computação são utilizados, como: união de conjunto disjuntos, ordenação topológica, tabelas de hashing entre outros. Novos problemas da biologia computacional exigem a criação de novas técnicas e novos algoritmos que em muitos casos são úteis em outras aplicações.

Para tal auxílio, não abordaremos temas da biologia molecular e bioquímica, pois acabaria fugindo do foco, e sim trataremos os dados biológicos como apenas um alfabeto de 4 letras, sendo elas: A (Adenina), C (Citosina), G (Guanina) e T (Timina). Essas letras são as bases encontradas no DNA. Dependendo da aplicação que poderá ser usada após o término deste projeto à base U (uracil) poderá ser utilizada no lugar do T (Timina) caso seja trabalhado com RNA (ácido ribonucléico), mas para isso será necessário efetuar modificações na codificação do projeto, que poderá ser feito em futuros trabalhos.

Comparação de seqüências e Alinhamento

Segundo Setúbal [SET94], a operação de comparação é a mais básica em biologia computacional e apresenta duas seqüências de DNA, por exemplo: GACGGATTAG e GATCGGAATAG. Pode-se notar a semelhança entre as duas seqüências se as colocarmos alinhadas conforme apresentado abaixo:

GA-CGGATTAG GATCGGAATAG

As únicas diferenças são um T a mais na segunda seqüência e uma troca de A por T na quarta posição da direita para esquerda. Também foi necessário introduzir um buraco (indicado pelo hífen) na primeira seqüência para que as bases iguais antes e depois do buraco se alinhassem nas duas seqüências.

O alinhamento entre as seqüências mostra a similaridade entre elas, ou seja, poderemos afirmar com um determinado numero (que é a pontuação total do alinhamento entre as seqüências) quanto uma determinada espécie é similar à outra. No caso deste projeto, como focaremos apenas essa similaridade, os biólogos poderão utilizar essa ferramenta para classificação de possíveis espécies novas que forem descobertas.

Definiremos com base em [SET94], o entendimento do alinhamento. As duas seqüências não precisam ser do mesmo tamanho e alinhamentos podem conter buracos em qualquer seqüência. Então um alinhamento é a inserção de buracos em pontos arbitrários ao longo das seqüências de modo que elas fiquem com o mesmo comprimento, entretanto um buraco de uma seqüência não pode ser alinhado com um buraco de outra seqüência e por fim, buracos podem ser colocados tanto no início como

34

no final das seqüências.

Dado um alinhamento entre duas seqüências, podemos atribuir uma pontuação, esta pontuação é definida pelo pesquisador da área biológica dependendo de como ele deseja ponderar a comparação. Neste projeto, utilizaremos como padrão os mesmos valores ponderados utilizados em [SET94]. Por ex:

Cada coluna do alinhamento receberá um certo numero de pontos e a pontuação total do alinhamento será a soma dos pontos atribuídos à suas colunas. Se a coluna tiver duas bases iguais receberá 1 ponto, se a coluna tiver duas bases diferentes receberá 1 e finalmente se a coluna possuir uma base e um buraco receberá 2. O alinhamento ótimo será aquele que tiver pontuação máxima. Esta pontuação máxima chamaremos de similaridade entre as duas seqüências. Em geral pode haver mais de um alinhamento com pontuação máxima.

Por exemplo, a pontuação da seqüência anterior onde nove colunas com bases iguais, uma coluna com bases desiguais e uma coluna com buraco, então a sua pontuação é a seguinte:

9 * 1 + 1 * (-1) + 1 * (-2) = 6

Para melhor entendimento do algoritmo que calcula o alinhamento, será utilizada a seguinte seqüência:

AAAC AGC

Para encontrar um alinhamento ótimo para esse par de bases há três possibilidade relacionadas abaixo:

AAA C AG C

AAAC - AG C

AAA C AGC -

Com este raciocínio, usaremos um método recursivo para achar o valor de um alinhamento ótimo, define-se uma função similarity(s1, s2) que corresponde à similaridade entre s1 e s2

Calcule similarity (AAA, AG) + 1 Calcule similarity (AAAC, AG) - 2 Calcule similarity (AAA, AGC) - 2

O problema deste método é que se aplicado diretamente, vai gerar um número exponencial de chamadas recursivas e se cada chamada gera outras três, sendo em duas delas o número total de caracteres envolvidos juntando as duas seqüências diminui apenas de um, teremos no mínimo 2 m / n chamadas, onde m e n representam os comprimentos das seqüências originais.

Contudo, muitas destas chamadas são redundantes, portanto não há necessidade de serem calculadas duas vezes, desde que sejam guardadas de maneira

35

que possam ser consultados rapidamente como mostrado na figura 3.2.1.

AAA

AAACAGC

AAAAG

AAACAG

AAAAGC

AAAA

AAG

AAAA

AAAC A

AAAAG

AAAG

AAAAG

AAAG

C

Figura 3.2.1 Árvore de Chamadas recursivas

Será utilizada a técnica de programação dinâmica, cuja qual deve-se observar que embora um método gere um número muito grande de chamadas recursivas, o numero total de instancias de entrada é limitado, de modo que o calculo pode ser feio uma só vês e armazenado para consultas posteriores, se necessário. Na maioria dos casos, uma matriz é usada para guardar resultados parciais.

Se observarmos as chamadas recursivas, podemos afirmar que o método da figura 3.2.1 utiliza sempre um prefixo da primeira seqüência e um prefixo da segunda seqüência. Há m +1 prefixos de s1 e n + 1 prefixos de s2, incluindo os vazios. Dessa forma, há apenas (m + 1 ) (n + 1) possíveis combinações de argumentos

Toda a recursão tem seus casos base, e neste determinado problema, os casos bases são aqueles em que a seqüência vazia é comparada a outra, isto é, o prefixo vazio de uma seqüência é comparado a um prefixo da outra. Nestes casos, o único alinhamento possível é colocar-se tantos buracos na seqüência vazia quantos necessários para igualar o comprimento da outra seqüência, resultando em uma pontuação de -2k, onde k é o comprimento da outra seqüência.

A figura 3.2.2 ilustra uma matriz bidimensional usada para a comparação da seqüência AAAC com AGC. Cada célula contém a pontuação de um alinhamento ótimo entre prefixos das seqüências dadas. Se chamarmos AAAC de s1 e AGC de s2, e se convencionarmos que s[1...j] indica o prefixo com tamanho j de s1, então cada célula (i,j) contem o resultado da comparação de s1[1...i] com s2[1...j]. Na matriz da figura 3.2.2, as células das bordas superior e esquerda foram inicializadas com -2 vezes a posição da célula, de acordo com a observação sobre casos base que fizemos anteriormente.

36

0 -2 -4 -6

1 -1 -3

-1 0 -2

-3 -2 -1

-8 -5 -4 -1

-2

-4

-6

1

1

1

1

-1 -1

-1 -1

-1 -1

-1 -1

A G C

A

A

A

C

Figura 3.2.2 Matriz Bidimensional de similaridade entre as seqüências S1 e S2

Uma breve explicação de como foi montada a matriz

Na matriz da figura 3.2.2, as células das bordas superior (primeira linha) e esquerda (primeira coluna) foram inicializadas com -2 vezes a posição da célula, de acordo com a observação sobre casos base que fizemos anteriormente. Ou seja, para as células da primeira linha fixa o valor do j e calcula-se utilizando o valor de i ficando:

posição C(1,0), -2*1= -2; posição C(2,0), -2*2= -4; posição C(3,0), -2*3= -6

O procedimento foi semelhante às células da primeira coluna, ou seja, fixando o valor de i e utilizando o valor de j para o calculo, ficando:

posição C(0,1), -2*1= -2; posição C(0,2), -2*2= -4; posição C(0,3), -2*3= -6; posição C(0,4), -2*4= -8

Nas células com i=>1 e j =>1 são acrescentados índices, que são calculados da seguinte forma:

As células em que o cruzamento das mesmas bases se coincidem, possuem o índice 1, caso contrario o índice é 1. Então podemos verificar esse método observando as células C(1,1), C(1,2), C(1,3) e C(3,4) possuem o índice 1 enquanto as demais células possuem o índice -1. Os valores das células i = j => 1 é definido como o valor máximo

37

entre : (i-1,j) + b, ou seja, o valor da célula à esquerda mais b (onde valor de b é -2) (i-1,j-1) + índice, ou seja, o valor da célula diagonal esquerda superior mais o

índice da própria célula (i,j-1) + b, ou seja, o valor da célula acima mais b (onde valor de b é -2)

O resultado que possuir o maior valor, será o valor da célula. Podemos acompanhar esse método a partir da célula (1,1), onde:

o valor da célula superior (célula (0,1)) é -2 mais o valor de b o resultado é 4; o valor da célula diagonal esquerda superior (célula (0,0)) é 0 mais o índice o resultado é 1; o valor da célula esquerda (célula (1,0)) é -2 mais o valor de b o resultado é -4

Comparamos e verificamos que o maior resultado obtido pelo método é 1, portanto o valor desta célula (célula (1,1)) será 1. Prosseguindo com o algoritmo, será possível calcular tanto a célula abaixo (célula(2,1)) ou a célula à direita (célula(1,2)). Vamos prosseguir a explicação com o calculo da célula à direita (célula (1,2)):

o valor da célula superior (célula (0,2)) é -4 mais o valor de b o resultado é 6 o valor da célula diagonal esquerda superior (célula (0,1)) é -2 mais o índice o

resultado é 3 o valor da célula esquerda (célula (1,1)) é 1 mais o valor de b o resultado é 1.

Portanto, o maior valor entre os três comparados é -1, ficando esse o valor da célula.Agora calcularemos a célula (2,1):

o valor da célula superior (célula (0,1)) é 1 mais o valor de b o resultado é -1 o valor da célula diagonal esquerda superior (célula (1,0)) é -2 mais o índice o resultado é -1 o valor da célula esquerda (célula (2,0)) é -4 mais o valor de b o resultado é -6

Neste caso podemos observar que para esta célula existem duas possibilidades de valores máximos, que é -1, então este será o valor da célula.

Agora podemos calcular o valor de três células que podem ser: célula (1,3); célula(2,2); e célula(1,3)

É por esse motivo que temos o paralelismo, várias células podem ser calculadas ao mesmo tempo, porem como as seqüências possuem um tamanho elevado o projeto será paralelizar blocos de células a serem processadas. Não daremos continuidade, pois o texto ficaria muito extenso e cansativo.

As setas que são apresentadas na figura 3.2.2 apontam para as células de onde foram obtidos os maiores valores como é o caso das células: c(2,1); c(2,3); c(3,1); c(3,2) e c(4,2). Ou seja, existe mais de uma possibilidade de valor máximo para a célula e essas setas são utilizadas para verificar o melhor alinhamento entre as duas seqüências.

Um outro detalhe importante, é que toda seqüência inserida nos algoritmos, tanto de alinhamento, quanto de similaridade, devem ser validadas antes de começar a comparação, a validação é feita conforme o algoritmo abaixo:

38

Algoritmo para validação de seqüências de DNA Descrição: Verifica se a sequência de DNA é uma sequência válida Nome do método: isValid() Classe a que pertence: DNAString

Atributos do método: Private

Argumentos do método:

Sequencia de caracteres a ser validada

Retorno do método: 1 se validado, 0 se falhou.

Português estruturado do método isValid():

s1: vetor da seqüência de DNA (vetor de caracteres) |s1|: número de elementos do vetor da seqüência de DNA (inteiro) m, i: inteiros

isValid() - Supomos |s1| = m. para i = 0 a m faça

se s1[i] != 'A' ou s1[i] != 'a' então se s1[i] != 'T' ou s1[i] != 't' então

se s1[i] != 'C' ou s1[i] != 'c' então se s1[i] != 'G' ou s1[i] != 'g' então

se s1[i] != '-' então retorna 0;

retorna 1;

Similaridade distribuída (CGM/BSP)

Em [SON02], é demonstrado um algoritmo de granularidade grossa chamado de BSP, que afirma melhorar o desempenho razoavelmente se for implementado em máquinas paralelas com memória principal distribuída. O Algoritmo BSP consiste em uma seqüência de várias etapas, separadas por um controle de sincronização. Nessas etapas, cada processador executa um conjunto de operações independentes que usam dados locais disponíveis para cada processador no começo da etapa, que consiste também na comunicação (envio e recebimento de mensagens). N processadores em uma etapa corresponde a enviar ou receber n mensagens em cada processador.

Outro algoritmo apresentado por [SON02] é o CGM, onde os processadores são interconectados por qualquer tipo de conexão e consiste em um conjunto de execuções enquanto alternam entre processamento local e processamento global (troca de mensagens). Normalmente durante a execução é utilizado o algoritmo que melhor processa os dados localmente. O algoritmo CGM é um caso especial do BSP onde todas as operações de comunicação das etapas são terminadas em n processadores. Estes algoritmos são apresentados na seção de Algoritmos de alinhamento e similaridade utilizados neste projeto. Com a implementação deste algoritmo teremos uma ordem de complexidade de O(mn/p) onde m e n são o tamanho das seqüências e p o numero de processadores disponíveis e, comparamos esta complexidade através das medidas de tempo obtidas com os testes de desempenho.

Para resolver o problema de similaridade sobre o modelo CGM/BSP, divide-se uma seqüência C de tamanho n(onde C é a segunda seqüência) em p partes, de tamanhos n/p, e cada processador Pi, 1<=i<=p, recebe a seqüência A e a i-ésima parte de C (c(i-1) n/p+1...ci n/p).

Cada processador Pi computa os elementos Si(r,s) da submatriz Si, onde

39

1<=r<=i n/p usando apenas 3 elementos pré-computados Si(r-1,s), Si(r-1,s-1), Si(r,s-1), pois há somente 3 formas de se calcular um alinhamento entre A[1..r] e C[1..s]. Pode-se alinhar A[1..r] com C[1..s-1] e marcar um espaço com C[s], ou alinhar A[1..r-1] com C[1..s-1] e marcar A[r] com B[s], ou alinhar A[1..r-1] com C[1..s] e marcar um espaço com A[r].

Para calcular a submatriz Si, cada processador Pi usa o melhor algoritmo seqüencial local. É fácil de ver que o processador Pi, i>1, pode somente iniciar a computação de elementos Si(r,s) após o processador Pi-1 ter computado parte da submatriz Si-1(r,s).

Denotado por Rki, 1<=i, k<=p, todos os elementos do limite direito (ultima coluna a direita) da k-ésima parte da submatriz Si. Mais precisamente, Rki = {Si(r,i n/p), (k-1)m/p +1<=r<=km/p}.

A idéia do algoritmo é a seguinte: Após computar a k-ésima parte da submatriz Si, o processador Pi envia para o processador Pi+1 os elementos de Rki. Usando Rki, o processador Pi+1 pode computar a k-ésima parte da submatriz Si+1. Após p-1 turnos, o processador Pp recebe R1p-1 e computa a primeira parte da submatriz Sp. No turno 2p-2, o processador Pp recebe Rpp-1 e computa a p-ésima parte da submatriz Sp e finaliza o processamento.

Figura 3.2.3 Comunicação entre as etapas, semelhante ao Scheduling

Usando esta programação (figura 3.2.3), pode-se ver que na primeira iteração somente o processador P1 trabalha. Na segunda iteração, os processadores P1 e P2 trabalham. É fácil verificar que na iteração k, todos os processadores Pi trabalham, onde 1<=i<=k.

40

Algoritmos de alinhamento e similaridade utilizados como base neste projeto

Algoritmo básico do método alignment() da classe DNA

Descrição: Traça o alinhamento ótimo entre duas seqüências de DNA utilizando a

matriz gerada pelo método similarity() Nome do método: alignment() Classe a que pertence: DNA Atributos do método: Private Argumentos do método: Inteiro FirstSequenceCount

Inteiro SecondSequenceCount Inteiro AuxiliarCount

Retorno do método: Inteiro AuxiliarCount caso não ocorra erro ou inteiro 0 caso ocorra erro.

Os parâmetros do método alignment() ao ser invocado devem ser:

FirstSequenceCount: tamanho do vetor da primeira seqüência de DNA;

SecondSequenceCount: tamanho do vetor da segunda seqüência de DNA;

AuxiliarCount: indiferente. Português estruturado do método alignment(): s1: vetor da primeira seqüência de DNA (vetor de caracteres) s2: vetor da segunda seqüência de DNA (vetor de caracteres) i: primeiro parâmetro do método, representa o marcador do vetor da primeira seqüência de DNA (inteiro) j: segundo parâmetro do método, representa o marcador do vetor da segunda seqüência de DNA (inteiro) t: terceiro parâmetro do método, representa o marcador das seqüências alinhadas (inteiro) alin1: vetor alinhado da primeira seqüência de DNA inserida. (vetor de caracteres) alin2: vetor alinhado da segunda seqüência de DNA inserida. (vetor de caracteres) a: matriz[|s1|][|s2|] que representa o número de similaridades entre a primeira e a segunda seqüências de

DNA. (matriz de inteiros) b: custo do buraco vazio (inteiro) c: Custo de tipos iguais (inteiro) d: Custo de tipos diferentes (inteiro)

alignment(i,j,t) se i = 0 e j = 0 então

t 0 senão se i > 0 e a[i,j] = a[i-1,j] + b então

alignment(i-1,j,t) t t + 1 alin1[t] s1[i-1] alin2[j]

-

senão se i > 0 e j > 0 e a[i,j] = a[i-1,j-1] + pontuação(i,j) então alignment(i-1,j-1,t) t t + 1 alin1[t] s1[i-1] alin2[j] s2[j-1]

senão se j > 0 e a[i,j] = a[i,j-1] + b então alignment(i,j-1,t) t t + 1 alin1[t]

-

alin2[j] s2[j-1] retorna t

pontuação(i,j) se s1[i] = s2[j] então

retorna c senão

retorna d

41

Algoritmo básico do método similarity() da classe DNA

Descrição: Gera a pontuação de um alinhamento ótimo em matriz Nome do método: similarity() Classe a que pertence: DNA

Atributos do método: Private

Argumentos do método: Nenhum

Retorno do método: Inteiro 1 caso não ocorra erro ou inteiro 0 caso ocorra erro.

Português estruturado do método similarity():

s1: vetor da primeira seqüência de DNA (vetor de caracteres) s2: vetor da segunda seqüência de DNA (vetor de caracteres) |s1|: número de elementos do vetor da primeira seqüência de DNA (inteiro) |s2|: número de elementos do vetor da segunda seqüência de DNA (inteiro) a: matriz[|s1|][|s2|] que representa o número de similaridades entre a primeira e a segunda seqüências de

DNA. (matriz de inteiros) b: custo do buraco vazio (inteiro) c: Custo de tipos iguais (inteiro) d: Custo de tipos diferentes (inteiro) m, n, i, j, valor1, valor2, valor3: inteiros

similarity() - Supomos |s1| = m e |s2| = n. para i 0 a m faça

a[i,0] i * b para j 0 a n faça

a[j,0] j * b para i 0 a m faça

para j 0 a n faça a[i,j] maximo(a[i-1,j] + b,

a[i-1,j-1] + pontuação(i,j), a[i,j-1] + b)

retorna a[m,n]

pontuação(i,j) se s1[i] = s2[j] então

retorna c senão

retorna d

maximo(valor1, valor2, valor3) se valor1 > valor2 e valor1 > valor3 então

retorna valor1 senão se valor2 > valor3 então

retorna valor2 senão

retorna valor3

42

Algoritmo básico do método CGM/BSP() da classe DNA Descrição: Gera a pontuação de um alinhamento ótimo de forma distribuída Nome do método: CGM/BSP() Classe a que pertence: DNA

Atributos do método: Public

Argumentos do método:

Nenhum

Retorno do método: Fragmento da matriz de alinhamento.

Português estruturado do método CGM/BSP():

s1: vetor da primeira seqüência de DNA (vetor de caracteres) s2: vetor da segunda seqüência de DNA (vetor de caracteres) |s1|: número de elementos do vetor da primeira seqüência de DNA (inteiro) |s2|: número de elementos do vetor da segunda seqüência de DNA (inteiro) a: matriz[|s1|][|s2|] que representa o número de similaridades entre a primeira e a segunda seqüências de DNA. (matriz de inteiros) b: custo do buraco vazio (inteiro) c: Custo de tipos iguais (inteiro) d: Custo de tipos diferentes (inteiro) p: número de processadores k, r, s, i, j, m, n, valor1, valor2, valor3: inteiros

CGM/BSP() - Supomos |s1| = m e |s2| = n. para k = 1 a p faça

se i = 1 então para r = ((k-1)*m/p)+1 a k*m/p e s = 1 a n/p faça

a[i,j] = maximo(a[i-1,j] + b, a[i-1,j-1] + pontuação(i,j), a[i,j-1] + b)

enviar (Matriz k de i, processador i+1); se i != 0 então

receber (Matriz k de i-1, processador p-1); para r = ((k-1)*m/p)+1 a k*m/p e s= 1 a n/p faça

a[i,j] = maximo(a[i-1,j] + b, a[i-1,j-1] + pontuação(i,j), a[i,j-1] + b)

se i != p então enviar(Matriz k de i, processador i+1);

pontuação(i,j) se s1[i] = s2[j] então

retorna c senão

retorna d

maximo(valor1, valor2, valor3) se valor1 > valor2 e valor1 > valor3 então

retorna valor1 senão se valor2 > valor3 então

retorna valor2 senão

retorna valor3

43

Capítulo 4

Neste capítulo será apresentada a documentação do projeto. Assim sendo, através deste conteúdo pretende-se passar uma visão clara e objetiva da proposta e do funcionamento do cluster para processamento de comparação de seqüências de DNA utilizando algoritmos computacionais paralelizáveis.

44

Especificações do projeto

Este capítulo tratará de toda a especificação e o desenvolvimento do projeto.

Sendo assim, antes de começar a documentação UML, serão introduzidos alguns conceitos abordados nesse projeto em conjunto com suas especificações.

Conceitualização do projeto

Esse projeto tem como objetivo a implementação de um sistema distribuído clusterizado baseado no algoritmo CGM/BSP, no qual operará através de uma máquina principal denominada Gerenciador (Manager) ou servidor do sistema. Este gerenciador, como o próprio nome sugere, gerenciará as requisições de comparação de seqüências entre os outros nós da rede, também chamados de Executores. Os Executores possuem uma identificação que lhes é atribuída pelo Gerenciador ao se conectarem ao cluster.

O cluster terá a função de comparar uma determinada seqüência de DNA, denominada DNA principal, com uma ou mais outras seqüências de DNA, denominadas de DNA secundário(s). Assim, após concluir a comparação, será gravado o grau de similaridade entre as seqüências comparadas em um banco de dados para futuras consultas. Para essa comparação, como visto no capitulo 3, será utilizada uma matriz de similaridade, a qual indicará o grau de similaridade entre as seqüências.

O sistema possuirá apenas uma máquina gerenciadora para controle das requisições de comparação e para o armazenamento do repositório de dados, além de máquinas Executoras para realizar a comparação.

Sempre que algum Executor for inserido no cluster, ele envia uma solicitação de inserção ao Gerenciador que verifica a quantidade de executores ativos e retorna ao Executor o número de registro imediatamente superior ao do último executor pré-registrado, e este passa a ser o último Executor (a posição de último executor é importante para a propagação de requisições de configuração e comparação, como será descrito posteriormente neste capítulo).

Ao receber alguma solicitação para comparação de similaridade entre duas seqüências de DNA, o Gerenciador envia a identificação (ID) de cada uma das seqüências de DNA junto aos parâmetros de ponderação (pesos para bases iguais, bases diferentes e inserção de lacunas) ao último Executor, e este envia solicitação ao Executor imediatamente anterior e assim sucessivamente em cascata, até o Executor 0. O Executor 0, ao receber a solicitação, inicializa a comparação e envia sua resposta ao Executor imediatamente superior, que também compara e envia sua resposta. Essa seqüência de ações cascateadas ocorrerão até o cálculo completo das seqüências de DNAs. Ao terminar de processar a comparação, o último Executor envia a resposta da comparação ao Gerenciador que se encarrega de gravá-la no repositório de dados.

Modularização e divisão de responsabilidades

Essa sessão descreverá os módulos existentes no projeto, assim as iterações que eles realizam com os outros módulos do sistema. O projeto do cluster foi dividido em quatro grandes módulos, que serão chamados aqui de Interface Web, Gerenciador, Executor, e ClusterKnoppix. Cada módulo será tratado de forma separada e exclusiva,

45

após a descrição de todos os módulos, será mostrada a integração entre eles.

Módulo Interface Web

Este módulo tratará da interface com o usuário, além de possuir ferramentas

para a manipulação de dados no repositório de dados. Suas principais funcionalidades são:

Manipulação de inserção, modificação e remoção de registros de seqüências de DNA no repositório de dados.

Tela para listagem das seqüências que já foram comparadas.

Tela para listagem das seqüências que ainda não foram comparadas, com a possibilidade envio de requisição para comparação.

Na tela de listagem das seqüências comparadas, ao escolher uma seqüência de DNA (o DNA principal), haverá uma lista que exibirá todas as outras seqüências de DNAs (DNAs secundários) que já foram comparadas com o DNA escolhido. Nesta lista também será exibida a pontuação e o valor dos pesos de bases e lacuna escolhidos.

Na tela de listagem das seqüências que ainda não foram comparadas, ao escolher uma seqüência de DNA (o DNA principal), uma lista exibirá todas as outras seqüências de DNA que ainda não foram comparadas com o DNA escolhido. Nessa tela haverá um botão para o envio de solicitações de comparação (esse botão é uma interface applet que enviará as solicitações ao Gerenciador).

O módulo de Interface Web será implementado em PHP sendo executado em um servidor Apache instalado na mesma máquina do repositório de dados, porém, há possibilidade de instalá-lo em qualquer outra máquina que tenha serviço de servidor de Web com suporte a PHP e Java (caso precise executar o applet).

Módulo Gerenciador

Este módulo é o responsável pelo controle inserções de Executores no cluster, pelo controle de pedidos de comparação de DNAs e pela gravação dos resultados dessas comparações no repositório de dados.

Ao receber o endereço IP de um Executor solicitando registro no cluster, o Gerenciador verifica na lista de Executores válidos o números dos executores registrados e retorna ao Executor solicitante um número imediatamente posterior ao número do último executor registrado. Após isso, o Gerenciador insere o IP e o número do novo Executor na lista de Executores e o Executor se registra no RMIRegistry com o número recebido.

Ao receber algum pedido de comparação de DNA, o Gerenciador o insere em uma fila de requisições. Caso os Executores não estejam comparando nenhuma outra requisição, o Gerenciador envia a requisição ao último Executor da lista de executores para começar a comparação. Ao terminar a comparação, o Gerenciador recebe a resposta do último Executor, remove a requisição da fila de requisições e grava o valor da comparação e dos pesos no repositório de dados.

Módulo Executor

Este módulo é o responsável pela execução do algoritmo CGM/BSP para o

46

cálculo da pontuação na comparação das seqüências de DNA. Os executores possuem basicamente três papéis distintos dentro do Cluster:

Primeiro Executor: Executor responsável por iniciar a comparação do CGM/BSP. Ele só possui elo com o segundo Executor registrado (caso haja mais de um Executor).

Executores centrais: Executores que se localizam nas posições entre o primeiro e o último Executores. Estes executores possuem elo com seus respectivos executores adjacentes, ou seja, o Executor N possui um elo com o Executor N-1 e com o Executor N+1.

Último Executor: Executor responsável por iniciar o processo de comparação das seqüências solicitadas pelo Gerenciador. Ele possui elo com o Gerenciador e com o penúltimo Executor.

Caso só haja um único Executor ativo, este só possuirá elo com o Gerenciador e terá as responsabilidades somadas do primeiro e do último Executores.

Estratégia de Comparação CGM/BSP utilizando RMI

Ao receber uma requisição para comparação de DNA, o último executor envia essa requisição ao penúltimo executor, e este para o seu vizinho anterior, e assim sucessivamente até o primeiro Executor. Conforme a a requisição é recebida pelos Executores, eles armazenam o identificador das seqüências de DNA, configuram seus parâmetros de base iguais, bases diferentes e lacuna para a comparação, além de zerarem o contador de turno e atualizarem o número total de executores disponíveis no sistema e inicializarem a thread de comparação (CGMBSPMatrix). Ao receber essa solicitação e os parâmetros iniciais forem configurados, o primeiro Executor inicializa sua CGMBSPMatrix que inicializa a primeira coluna e a linha da primeira sub-seqüência do DNA secundário.

A thread de comparação (CGMBSPMatrix) é uma thread interna de cada Executor e ela é responsável pela comparação do DNA principal com a sub-seqüência do DNA secundário. Essa sub-seqüência é determinada pela seguinte fórmula:

TindexInicial = parteInteiraDe(TseqSec / TExe)*NExe

Onde: TindexInicial Valor do índice inicial da sub-seqüência; TseqSec - Tamanho da seqüência do DNA secundário; TExe - Total de Executores; NExe Número do Executor;

TindexFinal = parteInteiraDe(TseqSec / TExe)*(NExe + 1)

Onde: TindexFinal Valor do índice final da sub-seqüência; TseqSec - Tamanho da seqüência do DNA secundário; TExe - Total de Executores; NExe Número do Executor;

Assim:

subSequencia = parte da seqüência inteira de TindexInicial a TindexFinal.

47

Porém, essa função abrange apenas casos nos quais a divisão TseqSec / TExe é

exata. Para que o sistema possa dividir de forma correta as seqüências de divisão inexata, deve-se adicionar o resto de TseqSec / TExe ao valor de TindexFinal no último Executor.

Após determinar o tamanho da sub-seqüência, o cálculo da sub-matriz (|DNAprincipal| x |subSequenciaDNAsecundário|) é dividido em T partes ou turnos, onde T = TExe. Assim que uma parte da sub-matriz é calculada, se o Executor não for o último, sua última coluna é enviada ao Executor imediatamente posterior junto ao número do turno. Depois, o contador de turno é incrementado e a próxima parte da sub-matriz é calculada enquanto o contador de turno for menor que T.

Haviam duas formas de se implementar a comparação descrita acima, a primeira seria criar uma sub-matriz (|DNAprincipal| x |subSequenciaDNAsecundario|), e a segunda forma é criar uma sub-matriz da sub-matriz(|DNAprincipal| x |subSequenciaDNAsecundario|).

A estratégia do primeiro método baseia-se em manter uma sub-Matriz de tamanho (|DNAprincipal| x |subSequenciaDNAsecundario|) além dos vetores auxiliares da primeira coluna e da última coluna (que possuem o tamanho igual a a |DNA principal| / TExe), assim, conforme calcula um sub-Bloco (um conjunto de linhas da sub-matriz igual a |DNA principal| / TExe), o Executor envia a resposta (última coluna) ao Executor seguinte, incrementa o contador de turnos e calcula o próximo bloco, até finalizar.

A vantagem desse primeiro método está na simplicidade na implementação e menor uso de processamento, que não exige manipulação de muitas variáveis e não precisa de controle de fluxo de turnos. Porém, utiliza-se mais memória que o segundo método. Neste primeiro processo, a quantia de memória utilizada é a seguinte:

Tmen1 = subMatrizmen + |PrimeiraColuna| + |UltimaColuna|

onde: Tmem - Total de memória; TprincSec - Tamanho do DNA principal; |PrimeiraColuna| - Tamanho da primeira coluna = TprincSec/TExe; |UltimaColuna| - Tamanho da última coluna = TprincSec/TExe; subMatrizmen Memória da subMatriz: TprincSec*[(TseqSec/TExe)+(TseqSec%TExe)];

Assim, no pior caso (Último turno do último Executor):

Tmen1 = TprincSec* [(TseqSec/TExe) + (TseqSec % TExe) + 2 /TExe]

No segundo método, a estratégia está em utilizar o mínimo de memória possível. Para isso, ao invés da seqüência ser comparada em uma sub-matriz que possui a quantidade de linhas igual ao tamanho do DNA principal, a nova sub-matriz terá o tamanho do DNA principal dividido pelo total de Executores.

A vantagem do segundo método concentra-se no uso mais otimizado da memória. Desta forma, embora o sistema processe mais e possua mais variáveis, ele consegue calcular tamanhos maiores de matrizes com a mesma quantia de máquinas do primeiro método. A idéia por trás deste método está em utilizar o contador de turnos e o total de turnos T para dividir a memória em blocos otimizados nos quais são totalmente liberados e refeitos a cada turno, eliminando assim o excesso no uso da memória.

Para esse método funcionar, é necessário utilizar, além das variáveis normais,

48

um vetor de caracteres de tamanho igual à quantia de linhas da submatriz. Sendo assim, a quantia de memória utilizada neste processo é contabilizada da seguinte forma:

Tmen2 = subMatrizmen + |UltimaLinha| + |PrimeiraColuna| + |UltimaColuna|

onde: Tmem - Total de memória; TprincSec - Tamanho do DNA principal; |PrimeiraColuna| - Tamanho da primeira coluna = TprincSec/TExe; |UltimaColuna| - Tamanho da última coluna = TprincSec/TExe; |UltimaLinha| - Tamanho da última Linha = [(TseqSec / TExe) + (TseqSec % TExe)]; subMatrizmen - Memória da subMatriz:

[(TprincSec/TExe)+(TprincSec%TExe)]*[(TseqSec/TExe)+(TseqSec%TExe)];

Assim, no pior caso (último turno do último Executor):

Tmen2=[(TseqSec/TExe)+(TseqSec%TExe)]*{1+[(TprincSec/TExe)+(TprincSec%TExe)]}+2*(TprincSec/TExe)

Para uma melhor comparação entre os dois métodos, será pego como estudo um caso ideal no qual as divisões tanto entre o tamanho do DNA principal com o total de Executores quanto entre o tamanho do DNA secundário com o total de Executores são exatas:

Tmen1 = (TprincSec / TExe) * (TseqSec + 2)

Tmen2 = (TseqSec/TExe) +(TseqSec/TExe2)*TprincSec+2*(TprincSec/TExe)

Sendo assim, a razão Tmen2 / Tmen1 é:

TTTTTTTT

TT

princSecseqSecprincSec

ExeseqSecprincSecprincSecseqSec

men

men

2

1

1

2

Como o método é aplicado em cima do tamanho da seqüência principal, para mostrar teoricamente o melhor uso de memória do segundo método em relação ao primeiro, será utilizado limite com TprincSec tendendo a infinito:

TTTT

TTTTTTTT

TT

ExeseqSec

ExeseqSec

princSecseqSecprincSec

ExeseqSecprincSecprincSecseqSec

men

men

TT princSecprincSec

1

2

2

2

2limlim

11

1

2

Sendo TExe > 0 (Para o sistema funcionar, deve haver pelo menos 1 Executor), conclui-se que utilizando o segundo método, obtemos um rendimento de razão 1/TExe em cima do primeiro método. Neste projeto foi implementado o segundo método.

Módulo ClusterKnoppix

Este módulo é o próprio sistema operacional Knoppix adaptado para aplicações distribuídas em clusters utilizando o algoritmo openmosix. Maiores detalhes sobre essa distribuição pode ser encontrado em http://bofh.be/clusterknoppix/. Maiores detalhes deste projeto encontram-se no anexo A.

49

Sua função no projeto está na distribuição de imagens (ISO) na rede através

de inicialização remota (remote boot), desta forma, além de garantir softwares iguais e com a mesma configuração para todas as máquinas da rede, qualquer alteração pode ser rapidamente propagada para todos os nós. Outra ferramenta importante que será utilizada é o gerenciamento e monitoramento distribuído que o programa openmosixviewer proporciona. Com este programa, pode-se verificar vários fatores importantes dos nós da rede, tais como o processamento, a memória utilizada e o histórico de utilização dos nós entre outros aspectos.

Especificações do sistema

A meta principal deste trabalho é a implementação de um sistema clusterizado de baixo custo que mantenha um desempenho no mínimo similar ao de um mesmo sistema, porém centralizado. Entende-se sistema centralizado neste ponto, como o mesmo algoritmo base de comparação sendo executado em uma única máquina. Para esse objetivo, será utilizada a linguagem de programação JAVA que será testada em um sistema operacional (ClusterKNOPPIX) de plataforma Linux.

Rede

O projeto está desenvolvido para uma rede dedicada Fast Ethernet com switches 10/100 Mbps, cabos CAT 5 e trabalhando sobre o protocolo TCP/IP. Essa rede foi escolhida por se tratar de uma rede de custo relativamente baixo e por ser de ampla utilização atualmente.

Características dos nós do sistema

Para a implementação, serão utilizadas estações dedicadas com configuração de hardware e software homogêneas, ou seja, com os mesmos hardwares e softwares instalados. Configurações de softwares heterôgeneas, tais como diferentes versões de sistemas operacionais e/ou JVM (JAVA Virtual Machine) poderão ser aceitas, porém o sistema não será testado tendo em vista essas características.

Armazenamento dos dados

Como repositório de armazenamento, será utilizado um banco de dados MySQL. A escolha de MySQL foi realizada por ele ser um banco de dados estável, já consolidado e gratuito.

As seqüências de DNA são arquivos texto geralmente grandes, com pequenos fragmentos de DNA com apenas alguns kilobytes de tamanho a sequências inteiras na ordem de megabytes, podendo chegar a ter 20 ou mais megabytes. Devido a essa característica dos arquivos de seqüência, o banco de dados conterá basicamente um campo longtext para o armazenamento da seqüência e outras informações para caracterização da mesma.

O acesso a esse repositório será permitido a todos os módulos do sistema. Em projetos futuros que foquem mais segurança, sugere-se que o acesso para leitura seja permitido a qualquer nó do cluster, o acesso para escrita seja permitido ao Gerenciador e à Interface Web, além disso, só poderá ser realizado se algumas

50

condições forem verdadeiras (Mais detalhes nos casos de uso Nv2c e Nv2d).

Sistema Operacional

O sistema operacional do gerenciador poderá ser qualquer um que utilize

plataforma Linux e suporte a NFS. O cluster pode operar sobre qualquer sistema operacional com rede pré-configurada. Outro requisito ao sistema operacional, é que ele deve possuir uma máquina virtual JAVA pré-instalada, de preferência a JRE 1.5 ou superior (pré-requisitos para a instalação da JRE são encontrados no sítio da SUN: www.sun.com).

Linguagem de programação

A linguagem de programação escolhida foi o JAVA por se tratar principalmente de uma linguagem multi-plataforma e orientada a objetos com uma ampla quantidade de pacotes e serviços distribuídos disponibilizados, além de possuir tipagem forte, sem ponteiros, garantindo isolamento e segurança.

O problema da perda de desempenho ocasionado pela máquina virtual é compensado pelo baixo custo para implementação do sistema e pela versatilidade do mesmo quanto à arquitetura pré-existente nas máquinas da rede.

Pacote para aplicação de computação distribuída

Utilizaremos RMI (Invocação de método remoto) para realizar a comunicação entre os nós do sistema clusterizado por se tratar de uma plataforma já bem consolidada, orientada a objetos e própria para o ambiente JAVA, além de permitir a transferência de objetos de tipos de dados complexos, diferentemente da RPC.

Características do Cluster

O cluster proposto neste projeto utiliza-se de padrões de rede TCP/IP implementados através de RMI em cima de uma plataforma JAVA. Sua estrutura básica é composta por uma máquina gerenciadora, uma máquina para o banco de dados (que será a mesma do Gerenciador) e máquinas para os Executores. O Gerenciador conterá a lista de registros, o Programa de Gerenciamento (openmosixviewer). O repositório pode estar localizado tanto em uma máquina servidora dedicada quanto na própria máquina do gerenciador. Os Executores possuirão os códigos implementados para o processamento. Ao se solicitar uma comparação pelo Gerenciador, este enviará a solicitação aos Executores que processarão suas respectivas submatrizes. A figura 4.1.1 abaixo demonstra a arquitetura básica do cluster:

51

Figura 4.1.1 Estrutura do Cluster

A representação básica de troca de mensagens do cluster é melhor visualizada na figura 4.1.2, na qual ilustra o envio das principais mensagens entre os diversos componentes do sistema.

Figura 4.1.2

Modelo do sistema representando a troca de mensagens entre os componentes

Desempenho

Para o sistema, o objetivo é alcançar um desempenho semelhante ao de um sistema centralizado executando o mesmo algoritmo, este sistema será descrito no capítulo de testes.

Conectividade

Conforme visto anteriormente, a maioria dos componentes deste cluster (Executores, Gerenciador e Interface Web) terão alcance restrito de comunicação, ou seja, eles só poderão se comunicar diretamente com vizinhos adjacentes (no caso dos Executores), com o Último executor e a Interface Web (no caso do Gerenciador, exceto no registro de Executores) ou com o Gerenciador (no caso da Interface Web). Esta restrição, embora limite a versatilidade do cluster no nível de confiabilidade, pois pode acarretar em uma desmodularização do cluster se algum componente falhar, permite que

52

tenha-se um tráfego de pacotes de controle reduzido em relação a outras técnicas de comunicação utilizando-se comunicação global entre os Executores, além de reduzir possíveis conflitos inerentes de falhas na comunicação, travamentos por deadlock ou inconsistências [DEI05]. O único componente do sistema que se comunicará com todos os outros componentes será o SGBD (Sistema gerenciador do Banco de Dados) para poder enviar as seqüências e suas informações e gravar os resultados das comparações.

Confiabilidade e tolerância a falhas

Com o objetivo de não tornar esse projeto muito

complexo com a parte de controle e tratamento de erros, em um primeiro momento não será implantado um sistema de tratamento de falhas para o gerenciamento da comunicação do cluster. Mas caso haja interesse futuro em uma implementação anti-falhas, será interessante implantá-la por meio de temporizadores (O RMI facilita essa implementação). Caso um temporizador exceda o limite de tempo, o executor no qual o tempo excedeu seria excluído da lista de executores do cluster e este poderia alocar outra máquina para continuar o processamento (neste caso, seria interessante haver pelo menos uma máquina de backup capaz de suportar cada um dos serviços do cluster). Para a máquina que teve seu Executor removido da lista, ao perceber que ele foi excluído da lista, o Executor aguarda um tempo pré-determinado e verifica seu estado de processamento, caso esteja em um certo limite pré-estabelecido de processamento, envia uma requisição de estou vivo ao Gerenciador.

Transparência

Devido ao nosso projeto ser um sistema clusterizado que objetiva adquirir um bom desempenho para uma dada aplicação, nosso projeto adotará poucos níveis de transparência, para que possamos analisar melhor o funcionamento do cluster. Adotaremos Transparência de transação, que manterá a consistência do sistema mascarando a coordenação entre um conjunto de recursos.

Sincronização entre processos

Toda a sincronização será realizada de forma restrita entre os serviços do cluster (conforme visto acima, em Conectividade) evitando inconsistências ou deadlocks no sistema. Assim, adotaremos uma ordenação causal entre processos para assegurar que todos os processos reconheçam que um evento causalmente dependente deve ocorrer apenas após o evento do qual é dependente.

Tratamento de erros

Como apresentado anteriormente, não se implementará quaisquer tratamentos de erros referentes a falhas de comunicação no cluster. Sendo assim, quaisquer erros que ocorram no processo de comparação provavelmente obrigará o usuário a refazer a comparação. No entanto, idéias para tratamento de erros serão apontadas no decorrer da documentação deste projeto visando uma possível continuação do mesmo em trabalhos futuros.

Testes

Após a construção do cluster básico, o mesmo será implantado e a seguir, realizar-se-á uma bateria de testes. Para que se possa comparar, serão anotadas as características de ambiente abaixo:

Tamanho das duas seqüências de DNA escolhidas para a comparação;

Características da rede, tais como velocidade de transmissão, quantidade de nós e características dos equipamentos.

53

Características de hardware dos nós, tais como a quantidade de memória RAM das máquinas, velocidade do processador e quantia de memória cache.

Características de software, tais como o sistema operacional instalado, lista de processos (caso haja) sendo executados em segundo plano.

Características de configuração do cluster, tais como nível de prioridade das threads, quantidade de nós executores envolvidos, valor médio de processamento dos executores individualmente e como um todo.

Inicialmente, será testado o desempenho de uma única máquina realizando o a comparação de seqüências utilizando o algoritmo de comparação de similaridade mostrado no Capítulo 3. Após isso, será testado o desempenho do cluster com uma única máquina como Executora (o Repositório de dados, o Gerenciador e um Executor) contra várias outras máquinas executoras (o Repositório de dados, o Gerenciador e N executores). Após os testes iniciais, será testado o comportamento do cluster mediante algumas condições, tais como a alteração da quantia de executores do cluster. Assim, a conclusão deste trabalho dar-se-á tendo como base a análise destes testes.

54

Casos de Uso

55

Caso de Uso Nv0 Sistema distribuído clusterizado para comparação de seqüências de DNA

Descrição do cenário principal:

1. O sistema BioCluster recebe seqüências de DNA. 2. O Gerenciador insere a requisição de comparação na fila de requisições. 3. Assim que a requisição for inserida, se não houver alguma comparação sendo

computada, o Gerenciador envia a nova requisição ao último Executor 4. O Último Executor distribui estes fragmentos entre seus diversos nós executores. 5. Os executores processam o trecho de seqüência recebido. 6. Após o processamento, os executores enviam os resultados da comparação ao

Gerenciador. 7. O gerenciador, com base no retorno, grava resposta no repositório, exibe um

relatório com a pontuação da comparação e o tempo de processamento e remove a requisição da lista de requisições.

Descrição do cenário alternativo:

1 Caso não seja uma seqüência válida. O sistema valida todas seqüência a fim de detectar se existe algum(s)

caracteres que não fazem parte do conjunto DNA = {A, T, C, G, -}. Caso não seja válido, o sistema retorna informando que a seqüência está incorreta. 3 Caso o Gerenciador não consiga enviar requisição.

Será apresentado o erro e sua origem no terminal. 4 Caso o executor não consiga enviar solicitações aos outros Executores.

Será apresentado o erro e sua origem no terminal e o aviso deste erro será emitido ao Gerenciador. 5 Caso ocorra estouro de memória ou de pilha.

Será apresentado o aviso de erro na tela e a comparação será abortada.

56

Caso de Uso Nv1 Funcionalidades Gerais

Objetivo: Inicializar o sistema distribuído.

Ator iniciante: Pesquisador ou Administrador de rede

Critério de parada: Quando ator fecha o sistema.

Casos de uso relacionados: Caso de uso Nv2a

Comparar Seqüências de DNA; Caso

de Uso Nv2b

Inserir nova máquina no sistema; Nv2c

Inserir seqüência de DNA no banco de dados; Caso de Uso Nv2d Remover seqüência de DNA do banco de dados

Atores: Pesquisador, Administrador de rede.

Pré-condição: nenhuma

Curso normal dos eventos: 1. Ator inicializa servidor. 2. Ator inicializa RMIRegistry e o ManagerImpl (módulo Gerenciador). 3. ManagerImpl conecta-se ao Repositório de dados e registra-se no RMIRegistry. 4. ManagerImpl pronto para receber solicitações de registro no sistema e requisições

para comparação.

Pós-condição: nenhuma

Alternativas: nenhuma

Interfaces:

Tela de configuração do sistema.

Tela de inserção / remoção de seqüências no bando de dados.

Tela de comparação de seqüências.

57

Caso de Uso Nv2a - Comparar Seqüências de DNA

Objetivo: Comparar uma seqüência de DNA com outras seqüências e determinar o grau de similaridade entre elas.

Ator iniciante: Pesquisador.

Critério de parada: ao terminar a comparação de seqüências ou se não houver nenhum executor disponível ou se for abortado pelo ator Pesquisador.

Casos de uso relacionados: Caso de uso Nv2e Inicializar sistema distribuído.

Atores: Pesquisador, Executor, Servidor.

Pré-condição: Pré-existência de seqüências de DNA no banco de dados e haver pelo menos um executor disponível

Curso normal dos eventos: 1. Pesquisador escolhe ou insere a primeira seqüência a comparar (seqüência

principal). Caso ele tenha inserido a seqüência, o sistema verifica a seqüência conforme o algoritmo de verificação de seqüências (este algoritmo será descrito em detalhes na sessão do diagrama de atividades).

2. Pesquisador marca conjunto de seqüências secundárias no banco de dados a se comparar com a seqüência principal.

3. Pesquisador libera sistema para prosseguir a comparação e servidor verifica quantas máquinas validadas (executores) estão disponíveis no momento.

4. O Gerenciador elabora uma lista de seqüências de DNA (de acordo com o conjunto selecionado no item 2) que devem ser comparadas com a seqüência principal e bloqueia no banco de dados as seqüências utilizadas na comparação.

5. Servidor fragmenta a seqüência principal de acordo com o algoritmo CGM/BSP desenvolvido por Siang (este algoritmo é discutido no capítulo 3).

6. Para cada seqüência da lista de seqüências de DNA, o sistema fragmenta a seqüência de acordo com o algoritmo CGM/BSP, criando uma lista de fragmentos por seqüência de DNA onde cada Executor tem uma cópia de um dos fragmentos da seqüência secundária e uma cópia da seqüência principal completa. Ao distribuir esses fragmentos de seqüências, o sistema poderá em projetos futuros, ativar um dispositivo de verificação de travamento por estouro de tempo (timeout) para cada pacote de fragmento de seqüência enviado a cada máquina.

7. Cada Executor, com suas seqüências de comparação, aguarda até o executor anterior enviar a última coluna da submatrix e assim, realizar a comparação entre elas. (No capítulo 3 foi explicado a comparação utilizando a última linha, porém para implementação foi adotada a última coluna por convenção).

8. Assim que um Executor termina de processar o resultado da comparação entre seqüências, ele envia a resposta do processamento ao executor imediatamente posterior e o último Executor envia o resultado da comparação para o Gerenciador que se encarrega de gravar no repositório de dados.

9. O Gerenciador ao receber a resposta de algum dos executores, a armazena no repositório de dados, desbloqueia, no repositório, o DNA que já tiver sido comparado e envia um outro fragmento de DNA da lista de seqüências marcadas (se houver).

10. Quando todas as seqüências tiverem suas respostas enviadas para o Gerenciador, o cluster pára de processar e aguarda por novas requisições.

11. Pesquisador pode pesquisar pelas seqüências novamente para ter acesso às

58

respostas da comparação e imprimir resultado ou salvá-lo em arquivo.

Alternativa: Falha na validação da seqüência 1 A seqüência possui alguma característica que está fora dos padrões de entrada (discutido anteriormente no capítulo 3). O sistema retorna uma tela de erro acusando "seqüência inválida" e permite a nova inserção da seqüência ou o cancelamento da operação.

Alternativa: Nenhuma máquina validada disponível 4 O sistema poderia retornar ao pesquisador uma tela de erro acusando "Nenhuma máquina validada disponível" e permitir repetir a tentativa ou cancelar o processo.

Alternativa: Dispositivo de verificação de travamento por estouro de tempo indica estouro de tempo 8 O Executor poderia ter um agente para controle de "tempo excedido" assim, em conjunto com um tratamento de erros que salva os dados processados, poder-se-ia haver um sistema mais robusto capaz de se recuperar de falhas com intervenção externa mínima.

Pós-condição: Os resultados entre a seqüência principal e todas as outras secundárias é salvo no repositório de dados.

Interfaces:

Tela de comparação de seqüências

59

Caso de Uso Nv2b - Inserir nova máquina no sistema

Objetivo: Inserir uma nova máquina configurada no cluster.

Ator iniciante: Administrador de rede.

Critério de parada: ao terminar de validar a máquina na rede ou ao ter falha em serviços principais.

Casos de uso relacionados: nenhum.

Ator: Administrador de rede, Servidor, Executor.

Pré-condição: Uma máquina não configurada na rede

Curso normal dos eventos: 1. Administrador de rede Insere nova máquina (nó) na rede do sistema. 2. Administrador de rede instala o software do sistema (ExecutorImpl) no nó. 3. Administrador de rede configura os parâmetros do cluster no nó. 4. Nó envia mensagem de registro ao Gerenciador e aguarda resposta. 5. Gerenciador insere ExecutorImpl do nó na lista na lista de Executores e retorna o

número do registro ao nó (O nó validado passa a ser chamado de "Executor" no sistema).

6. Ao receber o número de registro, o ExecutorImpl registra-se no RMIRegistry utilizando o número recebido.

Alternativa: Falha no envio/recebimento de mensagens 4 A máquina não consegue enviar mensagem. Ocorre erro por acesso negado ou falha de comunicação e o erro é exibido no terminal da estação.

Pós-condição: Uma nova máquina verificada é adicionada ao sistema.

Interfaces:

Tela de configuração de executores

Tela de monitoramento do Sistema

60

Caso de Uso Nv2c - Inserir seqüência de DNA no banco de dados

Objetivo: Inserir uma seqüência de DNA no banco de dados.

Ator iniciante: Pesquisador.

Critério de parada: ao terminar de inserir a seqüência ou ao ser cancelado pelo ator.

Casos de uso relacionados: nenhum.

Ator: Pesquisador, Executor, Servidor.

Pré-condição: nenhuma.

Curso normal dos eventos: 1. Pesquisador localiza o arquivo da seqüência a ser inserida no sistema. 2. Pesquisador insere a nova seqüência, em conjunto com outros dados para

identificação e confirma. 3. Sistema verifica validação da seqüência conforme o algoritmo de verificação de

seqüências (este algoritmo foi descrito no capítulo 3). 4. Sistema insere a seqüência validada no banco de dados.

Alternativa: Falha na verificação do algoritmo 3 A seqüência possui alguma característica que está fora dos padrões de entrada (discutido anteriormente no capítulo 3). O sistema retorna uma tela de erro acusando "seqüência inválida" e permite a nova inserção da seqüência ou o cancelamento da operação.

Pós-condição: Uma nova seqüência é adicionada no banco de dados do sistema.

Interfaces:

Tela de inserção de seqüências no repositório de dados

61

Caso de Uso Nv2d - Remover seqüência de DNA do banco de dados

Objetivo: Remover uma seqüência de DNA do banco de dados.

Ator iniciante: Pesquisador.

Critério de parada: ao terminar de remover a seqüência ou ao ser cancelado pelo ator.

Casos de uso relacionados: nenhum.

Ator: Pesquisador.

Pré-condição: Não estar comparando a seqüência a ser removida.

Curso normal dos eventos: 1. Pesquisador localiza a seqüência a ser removida do sistema. 2. Pesquisador marca a seqüência e confirma exclusão. 3. Sistema verifica seqüência e a remove do banco de dados.

Alternativa: Nenhuma seqüência marcada 2 Sistema avisa que nenhuma seqüência de DNA foi marcada para exclusão e permite que alguma seqüência seja marcada ou cancele a operação.

Pós-condição: Uma seqüência de DNA é removida do banco de dados do sistema.

Interfaces:

Tela de remoção de seqüências do repositório de dados

62

Caso de Uso Nv2e Inicializar sistema distribuído

Objetivo: Inicializar o sistema distribuído.

Ator iniciante: Pesquisador.

Critério de parada: verificar a validação de todas as máquinas configuradas.

Casos de uso relacionados: nenhum.

Ator: Pesquisador, Servidor, Nó.

Pré-condição: Máquinas ligadas com sistema e pré-configuradas.

Curso normal dos eventos: 1. Administrador de rede configura os parâmetros do cluster no nó. 2. Gerenciador verifica Executores ativos na lista de Executores. 3. Gerenciador adiciona referência do último Executor da lista e torna-se apto a

receber solicitações de comparação.

Alternativa: Nenhum Executor registrado 2 Sistema avisa que não há Executores registrados.

63

Diagrama de Classes

Parte 1

64

Parte 2

65

Diagramas de Seqüência

Inicialização do Executor

66

Inicialização do Gerenciador

67

Comparando DNA: Visão do módulo ClusterInterface

68

Comparando DNA: Visão do módulo Gerenciador

69

Comparando DNA: Visão do módulo Executor: Primeiro Executor

70

Comparando DNA: Visão do módulo Executor: Executores centrais

71

Comparando DNA: Visão do módulo Executor: Último Executor

72

Diagramas de Transição de Estado

Executor

Gerenciador

73

Diagramas de Atividade

Método Similarity

74

Método CGM/BSP

75

Banco de dados

Diagrama Entidade Relacionamento

DNA (Identificador

(chave primária):D1, Espécie:D3, Seqüência:D2, estáBloqueado:D4, Tamanho:D6, Descrição:D7)

Relação (Identificador1(chave estrangeira):D1, Identificador2

(chave estrangeira):D1, ValorDoBuracoVazio

(chave primária):D8, ValorDasBasesIguais

(chave primária):D8, ValorDasBasesDiferentes(chave primária):D8, TempoDeProcessamento:D9, Pontuação:D5)

Domínios

dom(D1): Código único de identificação da seqüência de DNA. dom(D2): Seqüência de DNA, abrange apenas caracteres do conjunto DNA

(T,G,C,A,-). dom(D3): Espécie animal na qual pertence a seqüência de DNA. dom(D4): Sinalizador binário que indica se o campo está bloqueado (1) ou não (0)

para modificação. dom(D5): Indica a pontuação obtida na comparação de duas seqüências de DNA. dom(D6): Indica o tamanho da seqüência de DNA. dom(D7): Descrição e observações sobre a seqüência de DNA. dom(D8): Valor inteiro indicando o peso de uma comparação. dom(D9): Tempo total de processamento entre duas seqüências de DNA, em

milisegundos.

Modelo do Banco de dados

Dicionário de dados

tbldna

Armazena as seqüências de DNA

76

Campo Tipo Nulo Padrão

ID

int(10) Não

Specie text Não Insira a espécie aqui Length int(10) Não 0 isLock (1) Não 0 Description text Sim DNA sem descrição DNA longtext Não

tblrelaction

Armazena o relacionamento entre as Seqüências de DNA Campo Tipo Nulo Padrão

IDFirstDNA

int(10) Não IDSecondDNA

int(10) Não ScoreDifferentBases

int(11) Não -1 ScoreEmptyHole

int(11) Não -2 ScoreEqualBases

int(11) Não 1 Punctuation int(11) Não 0 Time bigint(20) Não 0

Script de criação de tabelas

Tabela tblDNA

DROP TABLE `tblDNA`; CREATE TABLE `tblDNA` ( `ID` INT NOT NULL AUTO_INCREMENT, `Specie` TEXT DEFAULT 'Insira a espécie aqui' NOT NULL , `Length` INT DEFAULT '0' NOT NULL , `isLock` BINARY NOT NULL , `Description` TEXT DEFAULT 'DNA sem descrição', `DNA` LONGTEXT NOT NULL , PRIMARY KEY ( `ID` ) ) COMMENT = 'Armazena as seqüências de DNA';

Tabela tblRelaction

DROP TABLE `tblRelaction`; CREATE TABLE `tblRelaction` ( `IDFirstDNA` INT NOT NULL , `IDSecondDNA` INT NOT NULL , `ScoreDifferentBases` INT DEFAULT '-1' NOT NULL , `ScoreEmptyHole` INT DEFAULT '-2' NOT NULL , `ScoreEqualBases` INT DEFAULT '1' NOT NULL , `Punctuation` INT DEFAULT '0' NOT NULL , `Time` BIGINT DEFAULT '0' NOT NULL , PRIMARY KEY ( `IDFirstDNA` , `IDSecondDNA` , `ScoreDifferentBases` , `ScoreEmptyHole` , `ScoreEqualBases` ) ) COMMENT = `Armazena o relacionamento entre as Seqüências de DNA`;

Arquivo de configuração do MySQL

# Mysql config file. # Copy this file to c:\my.cnf to set global options # One can use all long options that the program supports.

77

# Run the program with --help to get a list of available options

# This will be passed to all mysql clients [client] #password=my_password port=3306 socket=MySQL

# Here is entries for some specific programs # The MySQL server [mysqld] port=3306 socket=MySQL skip-locking set-variable = key_buffer=16M set-variable = max_allowed_packet=1M set-variable = table_cache=64 set-variable = sort_buffer=512K set-variable = net_buffer_length=8K set-variable = myisam_sort_buffer_size=8M server-id = 1

# Uncomment the following if you want to log updates #log-bin

# Uncomment the following rows if you move the MySQL distribution to another # location basedir = c:/mysql/ datadir = c:/mysql/data/

# Uncomment the following if you are NOT using BDB tables #skip-bdb

# Uncomment the following if you are using BDB tables #set-variable = bdb_cache_size=4M #set-variable = bdb_max_lock=10000

# Uncomment the following if you are using Innobase tables #innodb_data_file_path = ibdata1:400M #innodb_data_home_dir = c:\ibdata #innodb_log_group_home_dir = c:\iblogs #innodb_log_arch_dir = c:\iblogs #set-variable = innodb_mirrored_log_groups=1 #set-variable = innodb_log_files_in_group=3 #set-variable = innodb_log_file_size=5M #set-variable = innodb_log_buffer_size=8M #innodb_flush_log_at_trx_commit=1 #innodb_log_archive=0 #set-variable = innodb_buffer_pool_size=16M #set-variable = innodb_additional_mem_pool_size=2M #set-variable = innodb_file_io_threads=4 #set-variable = innodb_lock_wait_timeout=50

[mysqldump] quick set-variable = max_allowed_packet=16M

[mysql] no-auto-rehash # Remove the next comment character if you are not familiar with SQL #safe-updates

[isamchk] set-variable = key_buffer=20M

78

set-variable = sort_buffer=20M set-variable = read_buffer=2M set-variable = write_buffer=2M

[myisamchk] set-variable = key_buffer=20M set-variable = sort_buffer=20M set-variable = read_buffer=2M set-variable = write_buffer=2M

[mysqlhotcopy] interactive-timeout

79

Interface do Sistema

Arquitetura da interface:

A interface com o usuário se constituirá de uma página de web. Sua construção está baseada em HTML, JavaScript e PHP para proporcionar o acesso ao banco de dados do cluster, o Gerenciador será a interface direta entre a página web e o cluster. Segue abaixo o esquema dessa estrutura:

Arquitetura do sistema com a interface Web

Interface Web

A Interface http para a comunicação com o Repositório de Dados e com o BioCluster dar-se-á através desta Interface Web. Sua principal função é interfacear o acesso ao Repositório de dados para gerenciamento dos dados.

Abaixo estão algumas das especificações desta interface:

Ao carregar o navegador da Tela principal, há uma pesquisa no Banco de Dados para retornar todas as Espécies existentes. DNA1:ComboBox: Campo onde há um LookUp de todos os DNAs existentes no Banco de

Dados. Neste local, seleciona-se o DNA principal. Mostra apenas o campo Espécie. DNA2:ListBox: Lista de todos os DNAs. Seleciona lista de DNAs secundários. Mostra apenas o

campo Espécie. Configuração padrão permite que a comparação seja feita pelos valores padrões do programa. Configuração personalizada permite que a comparação seja feita através de valores inteiros

definidos pelos campos Valor para seqüências iguais, Valor para seqüências diferentes e Valor para lacunas. Botão Comparar: Envia DNA principal e a lista de DNAs secundários para comparação no

cluster. Ao clicar no botão, são enviados os identificadores das seqüências de DNA selecionadas que ainda não possuem relação na tabela Relação. Após enviar, há uma caixa de diálogo confirmando ou não o envio da lista a ser comparada. Botão Relacionar: Abre a janela Relacionamento.

A interface para a os relacionamentos entre as seqüências de DNA são montadas abaixo:

80

Inicialmente, apenas Espécie:TextBox e o botão Pesquisar ficam habilitados. Espécie:TextBox: Campo para pesquisar no campo Espécie da tabela DNA. Botão Pesquisar: Faz Query na tabela DNA, retornando todas as espécies que contenham algo de

TextBox. Habilita Espécie:ListBox.. Espécie:ListBox: Visualiza a lista das espécies retornadas pelo botão Pesquisar. Pode-se

selecionar a espécie a se comparar a similaridade. Habilita botão Relacionar. Botão Relacionar: Executa uma query que pesquisa todos os DNAs das espécies selecionadas em

Espécie:ListBox com a tabela Relação, retornando todas as espécies que já possuem relacionamento com o DNA selecionado. Permite a seleção de apenas um item. Espécie:LabelBox: Mostra Espécie do DNA selecionado. Espécie:ListBox de Relações: Mostra espécies que já foram comparadas com DNA selecionado

em Espécie:ListBox. Pontuação:ListBox: Mostra a Pontuação de similaridade existente entre os 2 DNAs. VII, VID e VL são respectivamente os valores para índices iguais, índices diferentes e lacunas

das respectivas comparações.

Estrutura de comunicação da interface Web

Evento na página "Tela Principal": Entrada

Envia Pedido da lista de DNAs existentes

Recebe Identificador e Espécie dos DNAs do Banco de Dados

Evento na página "Tela Principal": Clique em Comparar

Envia Identificador do DNA1, Identificador dos DNAs selecionados e que não possuem

relacionamento com DNA1 na tabela de Relacionamento no Banco de Dados Recebe

Mensagem de sucesso de envio

Evento na página "Relacionamento": Clique em Pesquisar

Envia Dados do TextBox

Recebe Identificador e Espécies que tenham a seqüência de caracteres de TextBox em algum

lugar de Espécie

Evento na página "Relacionamento": Clique em Relacionar

Envia Identificador da Espécie selecionada em ListBox

Recebe Identificador, Espécie e Pontuação de todos os DNAs que possuam na tabela de

Relacionamento no Banco de Dados, alguma relação com o Identificador enviado

81

Capítulo 5

Neste capítulo será apresentado o BioCluster em funcionamento e o seu comportamento na comparação de seqüências em um ambiente pré-determinado. Também será comparado o desempenho do BioCluster variando o número de Executores e o tamanho das seqüências.

82

Caracteristicas do Ambiente

Os testes do sistema BioCluster foram executados em um ambiente com as

seguintes configurações:

Configurações físicas:

Máquinas:

Processador Intel P4 2.8 GHz ;

1MB de Cache;

256 MB Memória RAM;

Placa de rede 10/100 Mb.

Rede:

Hub ENH924-AUT+ 10/100Mbps Switching Hub da Encore

Configurações lógicas:

Máquina Gerenciadora:

Sistema Operacional ClusterKNOPPIX 3.6 (Distribuição Linux);

Kernel 2.4;

KDE 3.2.3;

Java JDK 1.5.0_05;

RMIRegistry;

ManagerImpl (Gerenciador);

OpenMosix View1.5;

Máquina do Repositório de dados:

Sistema Operacional Windows XP Professional com SP2;

Banco de Dados MySQL 4.1.9;

Apache 1.3.33;

PHP 4.3.10;

PHPAdmin 2.6.1.

Máquinas Executoras:

Sistema Operacional ClusterKNOPPIX 3.6 (Distribuição Linux); (Detalhes no Anexo A)

Kernel 2.4;

Java JDK 1.5.0_05;

RMIRegistry;

ExecutorImpl (Executor);

OBS: Máquina com kernel reduzido para aplicação com Java, sem interface gráfica.

83

Metodologia

Para a comparação do rendimento do sistema BioCluster em relação à

comparação em uma única máquina, será utilizada a mesma configuração em todas as etapas de teste. Com o objetivo de melhorar o desempenho geral, foram realizadas algumas configurações explanadas abaixo:

Para otimizar o desempenho das máquinas executoras, implantamos um script que implementa a inicialização automática do rmiregistry e das máquinas virtuais java com parâmetros extensivos de memória para os módulos ExecutorImpl's. O script sc1.sh está descrito abaixo:

#!/bin/bash #remove algum arquivo que comeca com ip, pois como inicia via DHCP e possivel ter varios arquivos cd / rm -f ip*

#apresenta o ultimo octeto do ip na tela dos nos MAQUINA=$(/sbin/ifconfig | grep Bcast | cut -d: -f2 | cut -d' ' -f1 | cut -d. -f4) echo "Numero da maquina ... $MAQUINA"

# Grava no arquivo ip.address o IP completo do no echo "Gravado Arquivo ip.address em / " /sbin/ifconfig | grep Bcast | cut -d: -f2 | cut -d' ' -f1 > ip.address

#Inicia o executor echo "Iniciando o rmiregisty.Por Favor Aguarde " cd /cdrom/SequenciamentodeDNAemclustercomRMI nice -15 /usr/local/jdk1.5.0_05/bin/rmiregistry & #Aguardando 5 segundos devido a demora do rmregistry subir, assim evitamos problema caso a aplicacao inicie primeiro sleep 5s cd /cdrom/SequenciamentodeDNAemclustercomRMI echo "Iniciando a Aplicacao" nice -15 /usr/local/jdk1.5.0_05/bin/java -Xmaxjitcodesize5m -Xms240M -Xss240M -Xmx890M -XX:LargePageSizeInBytes=8m -XX:ThreadStackSize=512 -XX:MinHeapFreeRatio=10 -XX:MaxHeapFreeRatio=100 -server -client ExecutorImpl -g192.168.0.1

Script sc1.sh

O script acima é chamado pelo arquivo /etc/rc5.d/S99Configura com o conteúdo abaixo:

#!/bin/bash cd /cdrom ./sc1.sh

Script S99Configura

Para a otimização do repositório de dados, além do script citado na sessão Banco de Dados no Capítulo 4, a prioridade do processo foi incrementada para "Tempo Real" em uma máquina dedicada com sistema operacional Windows XP e 256MB Ram.

O sistema BioCluster foi testado havendo uma máquina para gerenciamento e

84

uma para repositório de dados. Segue abaixo a tabela com o tempo em milisegundos de processamento para os diferentes tamanhos de seqüências de DNA comparadas:

Tamanho das Seqüências Total de Máquinas 1kB x 1kB 5KB x 5KB 10KB x

10KB 20KB x 20KB

50KB x 50KB 100KB x 100KB

1 10272 11922 *

3 ** 182336 195040 281525 *

5 ** 957604 595718 629994 1917702*** *

15 ** 7301617

Tabela 5.1

* Não suportado - Erro: Exception in thread "CGMBSPMethod" java.lang.OutOfMemory Error: java heap space ** Valor Pequeno para verificação do tempo de comparação ***Alto valor de tempo de comparação devido ao alto índice de acesso à memória Swap, em uma segunda verificação, foi obtido o tempo 29030437ms.

Teste efetuado com 1 maquina Executora, 1 maquina Gerenciadora e 1 máquina repositora de dados.

Tamanho das Seqüências Tempo (ms) 50B x 50B 10093 100B x 100B 10067 200B x 200B 10073 500B x 500B 10109 2KB x 2KB 10373 5KB x 5KB 11922

Tabela 5.2

Durante a comparação das seqüências utilizando o algoritmo CGM/BSP, foram retiradas algumas imagens do cluster em ação, abaixo está o cluster para 5 máquinas (mais detalhes sobre o openMosixView no Anexo A):

Figura 5.3.1

85

Figura 5.3.2

Com essas figuras, percebe-se que não são todas as máquinas que estão com carga máxima. Na tela, a máquina 1 é o Gerenciador, a máquina em vermelho (244) está sendo localizada pelo openMosixView, porém está desligada, por isso ela está desabilitada. As demais máquinas estão processando sendo utilizando o CGM/BSP. Devido a isso a essa diferença de carga grande entre as figuras 5.3.1 e 5.3.2. A figura 5.3.1 ocorreu no começo da comparação, enquanto que a 5.3.2 ocorreu aproximadamente no meio da operação.

Ao inserirmos 15 máquinas (para computar seqüências grandes (100kB x 100KB), o sistema apresentou o seguinte:

Figura 5.4.1

Assim, o openMosixView exibe uma mista das Máquinas do cluster.

86

Figura 5.4.2

Figura 5.4.3

87

A figura 5.4.3 demonstra o período de maior pico de utilização da capacidade

de processamento na rede pelas 15 máquinas nela contida. Note que o reflesh foi marcado a cada 22 segundos para evitar comprometer o desempenho da rede durante a comparação.

O tempo de processamento em relação ao tempo de ociosidade (por envio ou aguado de requisições) é muito maior. Gerando tempos totais de processamento muito altos para comparações, de forma proporcional ou até mesmo quadrático ao número de máquinas.

Figura 5.4.4

A figura 5.4.4 mostra o excesso de pacotes UDP na rede no começo da comparação com 15 máquinas. Essa comunicação UDP em excesso ocasiona parte da lentidão da rede na comparação.

88

Figura 5.4.5

Outro motivo de lentidão foi o fato da rede não estar dedicada para os testes. Na figura 5.4.5, O programa analisador de protocolos Ethereal verificou um excesso de pacotes da outra rede compartilhada via broadcast pelo Hub, além de um excesso de pacotes ARP.

89

Conclusão

Verificando os valores na tabela 5.1, na comparação 5k x 5k, constata-se que aumentando o número de máquinas, o tempo de resposta aumenta drasticamente. Com base nas análises experimentais, concluímos que esse aumento ocorre devido principalmente aos seguintes fatores: Banco de dados (Atraso na conexão proporcional ao número de máquinas), Rede (Rede experimental não dedicada com hub), RMI (Demora excessiva na comunicação entre suas instâncias quando estão em máquinas distintas, este foi o maior fator da demora nos resultados).

Ao comparar as seqüências de 50kx50k verifica-se que o tempo também aumenta significativamente em relação às outras seqüências para o mesmo número de Executores (5 Executores). Isso ocorreu pelo fato das máquinas terem 256MBRAM fazendo uso excessivo da memória Swap.

Devido às limitações da memória principal e de Swap das máquinas utilizadas, as seqüências maiores só foram possíveis de serem computadas distribuindo as em um número maior de Executores. Assim, com máquinas com maior recurso de memória, o tempo do processamento dos resultados apresentados poderia diminuir.

O RMI merece um destaque especial, pois foi o maior responsável pelos elevados valores no tempo devido a grande quantidade de seus pacotes de comunicação UDP transmitidos (vistos experimentalmente com a ferramenta analisadora de protocolos) e à lentidão na resposta de solicitações remotas. Pois o processamento nos Executores ocorria em poucos segundos, enquanto essas estações ficavam longos períodos bloqueadas para envio ou recebimento de mensagens.

Com essas considerações, concluímos que embora o RMI seja uma boa tecnologia para Sistemas Distribuídos de Serviços, ele não é apropriado para Sistemas Distribuídos de Alto Desempenho. Em relação ao Sistema Operacional escolhido, ele demonstrou-se ser uma importante ferramenta para a administração e coleta de dados sobre o desempenho geral do cluster, por ter softwares específicos e suporte a boot remoto, além de poder ser customizado para melhor adequar-se ao projeto.

A implementação do algoritmo CGM/BSP foi satisfatória pois em testes com múltiplos Executores locais (Executores na mesma máquina que o Gerenciador) o algoritmo demonstrou-se rápido e eficiente quando comparado a um único Executor local. Para uma futura implementação melhor sucedida do algoritmo CGM/BSP, sugerimos a utilização de sockets em ambientes dedicados.

90

Recomendações para projetos futuros

Através da experiência adquirida no decorrer do desenvolvimento deste projeto, para dar continuidade ao mesmo, pode-se seguir as idéias abaixo:

Aplicar um controle de falhas mais aprimorando, com a inserção de controle de épocas e com os executores salvando o resultado de seu processamento caso ocorra falha de comunicação. Assim, se for solicitado novamente a mesma comparação ao executor, ele simplesmente devolverá o resultado já salvo.

Aprimorar o gerenciamento do cluster pelo módulo gerenciador, de forma que a maioria dos problemas relativos a gestão e controle de processos possa ser feita de forma centralizada.

Criar módulo de controle remoto para gerenciar o cluster via Internet.

Aplicar aperfeiçoamentos à técnica do algoritmo CGM/BSP aumentando a granularidade em ambientes com máquinas heterogêneas para redes mais rápidas, como a Gigabit Ethernet, e assim otimizar o tempo de processamento nestes ambientes.

Aplicar um controle de confiabilidade e tolerância a falhas mais complexo de modo que o sistema ganhe mais disponibilidade.

Quando há muitas máquinas, poderia-se utilizar duas máquinas para repositório de dados com replicação. Fazendo com que o sistema tenha dois caminhos alternativos para buscar dados. Pode-se também fazer balanceamento de carga simples para a busca de dados dos Executores nos repositório. Por exemplo: Executores pares buscam no primeiro repositório e os ímpares no segundo.

Trabalhar de forma mais profunda na redução do kernel Linux para otimizar o sistema operacional para o BioCluster.

Aplicar níveis maiores de transparência para tornar o sistema mais amigável e auto-gerenciável ao usuário final.

Salvar subrespostas (respostas da subMatriz), tais como a primeira e a última coluna em arquivos texto, para liberar espaço em memória e ao mesmo tempo criar um mecanismo de contingência a falhas.

Modificar a tecnologia utilizada para a comunicação do sistema. O RMI mostrou-se impróprio para aplicações clusterizadas que visam alto desempenho, pois a medida que são inseridas novas máquinas na rede, a alta taxa de comunicação entre os nós causa tráfego na rede e demora na comunicação.

91

Referências

[BEO05] Beowulf. Disponível em: www.beowulf.org; acessado em 19 de abr. 2005.

[COU01] COULORIS, G. F.; Distributed systems: concepts and design. 3º ed. London: Addison-Wesley, 2001.

[DEI01] DEITEL, H.M.; DEITEL, P.J.; JAVA Como programar. 3º ed. Porto Alegre: Bookman, 2001.

[DEI05] DEITEL, H.M.; DEITEL, P.J.; CHOFFNES, David R. Sistemas Operacionais 3ª ed. São Paulo: Pearson 2005.

[ERA04] ERAD Escola Regional de Alto Desempenho, Simpósio realizado de 13 a 17 de janeiro de 2004 Pelotas RS

[FOW00] FOWLER, M.; KOBRYN C.; BOOCH, G.; UML Essencial. 3º ed. Porto Alegre: Bookman, 2000.

[HOR01] HORSTMANN, S.C.; CORNELL, G. Core Java 2. 1ª ed. São Paulo: Makron Books 2001

[MAS04] MASSETO, F.I.; Sistemas Distribuídos: Java RMI

Tutorial. Osasco, 24 ago. 2004. RMI.ppt (104kbytes).

[OMG03] OMG Unified Modeling Language Specification. Unified Modeling Language. v. 1.5, formal/03-03-01.pdf, Março 2003.

[PIT03] PITANGA, M. Computação em Cluster 1ª ed. São Paulo: Brasport, 2003

[REW98] EL-REWINI, H.; LEWIS, G.T.; Distributed and ParallelComputing, Manning. 1998. Disponível em: <www.eproinfo.mec.gov.br/webfolio/ Mod80177/15_DesempenhoEmMultiprocessamento_1x1.pdf> Acesso em 17 jun. 2005.

[SET94] MEIDANIS, J.; SETUBAL, J. C. Departamento de Ciências da Computação Universidade Estadual de Campinas

acervo IME. Uma introdução à biologia computacional. Recife: REDALUS, 1994.

[SOA95] SOARES, L.F.G.; LEMOS, G.; COLCHER S. Redes de computadores: Das LANs MANs e WANs às Redes ATM. 2º ed. Rio de Janeiro: Campus, 1995.

[SON02] ALVES, C. E. R., CÁCERES, E. N., DEHNE, F. e SONG, S. W. A CGM/BSP Parallel Similarity Algorithm. Proceedings I Brazilian Workshop on Bioinformatics. Gramado, RS, 18 de Outubro, 2002, pgs. 1-8.

[TAN95] TANENBAUM, A.S.; Sistemas Operacionais Modernos. 1º ed. Rio de Janeiro: LTC Livros Técnicos e Científicos Editora S.A., 2005.

WSC[04] WSCAD

Work Shop em Sistemas Computacionais de Alto Desempenho 5ª ed. Foz do Iguaçu, Paraná

[WWW05] IBM/DOE. BlueGene/L DD2 beta-System (0.7 GHz PowerPC 440). Disponível

92

em: <http://www.top500.org/sublist/System.php?id=7101> Acesso em 17 jun. 2005.

93

Anexo A Implementação do ClusterKnoppix

Planejamento

A escolha do Sistema Operacional Linux se deve ao fato de ser gratuita,

evitando assim gasto com o uso de software proprietário, possuir o código fonte aberto, ou seja, qualquer pessoa pode estar efetuando modificações de forma a melhor atender a suas necessidades e sem se preocupar com licenças, por possuir código aberto, existe milhares (se não milhões) de desenvolvedores de toda a parte do mundo que contribui com a melhoria do sistema como um todo, doando algumas horas livres, dessa forma podemos concluir que se possui muitas pessoas que trabalham e contribuem pela melhora do Linux é que ele adquiriu grande importância nas instituições, e pelo motivo de tantas pessoas contribuírem é um Sistema confiável. Poderia citar inúmeras outras vantagens, mas essas são as principais.

A distribuição escolhida para a finalidade de desenvolver um cluster foi Clusterknoppix versão 3.6 que é uma modificação do Knoppix e utiliza o kernel Openmosix e possui alguns serviços muito úteis para tal objetivo como :

Terminal OpenMosix

DHCP

TFTP

suporte a PXE

NFS

DNS - Apache

Banco de Dados MySQL

O ClusterKNOPPIX é live CD, ou seja, basta apenas colocar o CD de instalação no drive de CD e reiniciar o computador (lembrando que é necessário a BIOS estar configurada corretamente), e automaticamente inicializará com o Linux sem a necessidade formatar o HD, criar partições ou correr o risco de perder dados. Para sair do Linux basta reiniciar o computador e tirar o CD do drive de CD que voltará como era antes.

Os servidores citados acima serão muito úteis para a configuração de BOOT Remoto e controle dos nós escravos quando o cluster está em funcionamento.

A arquitetura será semelhante a distribuição Beowulf ( que pode ser acessada em: http://www.beowulf.org/overview/index.html), ou seja, nos nós escravos não será necessário HD, drive de disquete/CD, monitor, mouse e teclado. Só será necessário placa mãe, placa de rede (com suporte a PXE), processador e memória. O suporte a PXE pode ficar na placa mãe, pois atualmente a maioria dessas placas já estão vindo de fábrica com placa de rede on-bord e suporte ao PXE. Essas descrições ajudam a baixar o custo do projeto. Uma das diversas aplicações possíveis que foi implementada e podemos colher bons resultados foi a de renderização.

94

Instalação

Para a instalação do Sistema Operacional, utilizamos os computadores do

laboratório 11 (mais precisamente o computador patrimônio 013247). A configuração dos computadores são:

Pentium 4 de 2.8 GHz, 1 MB de cache, 256 MB de memória RAM e 40 GB de HD. Como nestes computadores estão instalados o Windows XP e o Linux, não tinha nenhum espaço livre para a instalação do ClusterKNOPPIX, então foi colocado um HD de outro computador e feito um backup neste segundo HD. Formatei a partição Linux utilizando p comando do Linux fdisk e criei duas partições, uma para o Linux que já estava instalado e outra para posteriormente colocar o ClusterKNOPPIX.

Anteriormente estava:

HDA1 NTFS

HDA2 SWAP

HDA3 ReiserFS

Após o procedimento ficou:

HDA1 NTFS

HDA2 SWAP

HDA3 ReiserFS

HDA4 ReiserFS

Ocorria problemas com a placa de vídeo no momento em que está inicializando pelo CD o ClusterKNOPPIX, para resolver foi passado o parâmetro:

Knoppix screen=800x600 depth=16

O parâmetro screen é para definir o tamanho da tela em que o Linux será executado, no caso, 800 por 600, e o parâmetro depth é a quantidade de cores, no caso 16 significa 16 milhões de cores.

Como já foi dito, primeiramente inicializa-se do CD e posteriormente é instalado no HD. Para instalar o comando a der digitado no terminal é:

knoppix-installer

Porem foi necessário passar dois parâmetros adicionais, ficando:

IGNORE_CHECK=1 sudo knoppix-installer

Onde o parâmetro IGNORE_CHECK=1 é para pular o particionamento no momento da instalação desde que ele já tenha sido feito e o parâmetro sudo significa executar em modo de super usuário.

Na tela que aparece posteriormente que questiona o tipo de instalação foi selecionado Beginner, ou seja, com detecção de hardware e multi-usuário. Indicado para ser instalado na partição /dev/hda4 . Posteriormente é adicionado um usuário e a senha (ou seja, alem do usuário root é preciso mais um usuário) que no caso o usuário criado foi: admin. Configurado o nome do computador para server-cluster. A partir disso pode-se

95

inicar a copai dos arquivos do CD para o computador.

BOOT Remoto

BOOT Remoto é de forma didática, iniciar o Sistema Operacional a partir de

um HD que não seja local, ou seja, o Sistema Operacional completo fica em outro computador da rede. Mas para o computador chegar a encontrar o outro computador do qual deverá carregar o Linux é preciso de algumas configurações iniciais. Nos computadores do laboratório 11as placas mãe têm suporte a iniciar pela rede, ou seja, quando liga o computador.

Segue a tradução de como funciona o PXE retirada do site: http://www.ltsp.org/README.pxe

Para usar o Kernel do PXE, será necessário configurar o 'nome da imagem PXE' no arquivo /etc/dhcpd.conf para apontar ao bootloader do pxe.

Um exemplo do que será necessário configurar no dhcpd.conf segua abaixo:

host ws001 { hardware ethernet 00:E0:06:E8:00:84; fixed-address 192.168.0.1; filename "/lts/2.4.22-ltsp-1/pxelinux.0"; }

Normalmente para um kernel de boot remoto, o kernel é colocado em /tftpboot/lts. Porem para kernel PXE nós criamos um subdiretório que possua um nome da versão do Kernel. Para exemplificar, nós criamos : '/tftpboot/lts/2.4.22-ltsp-1 '

Dentro deste diretório, nós colocamos o kernel, a imagem initrd, o bootloader do PXE e um subdiretório de configuração

Como trabalha:

1) Quando o bootrom do PXE inicia, emite uma transmissão do pedido do dhcp à rede.

2) O servidor DHCP responde com diversas informações, como: endereço IP da estação de trabalho, Gateway e o nome do arquivo para download o root-path

3) O PXE bootrom usa então o protocolo TFTP para o download do bootfile (arquivo de inicialização). O PXE bootrom possui uma limitação de somente carregar arquivos de no máximo 32 KB, não é possível carregar um Kernel do Linux inteiro. Assim nós ajustamos para carregar um bootloader pequeno, chamado pxelinux.0 . Esse bootloader, pode então carregar imagens maiores, tais como o Kernel do Linux e a imagem initrd

4) O pxelinux.0 inicia a execução procurando o arquivo de configuração. Procura por um subdiretório chamado pxelinux.conf , no mesmo diretório onde o pxelinux.0 foi encontrado. Primeiramente procura por um arquivo com o nome do endereço IP da estação de trabalho conventido em hexadecimal. Se não localizar o arquivo com esse nome, retira-se o ultimo digito do nome hexadecimal do arquivo a localizar, até que não haja mais nenhum digito a esquerda. Então procura pelo arquivo pxelinux.cfg/default Conseqüentemente se o endereço IP da estação for 192.168.0.1, o pxelinux.0

96

procura na seguinte seqüência:

pxelinux.cfg/C0A80001 pxelinux.cfg/C0A8000 pxelinux.cfg/C0A800 pxelinux.cfg/C0A80 pxelinux.cfg/C0A8 pxelinux.cfg/C0A pxelinux.cfg/C0 pxelinux.cfg/C pxelinux.cfg/default

O formato do arquivo de configuração é muito parecido com o arquivo /etc/lilo.conf

prompt=0 label linux kernel bzImage-2.4.22-ltsp-1 append init=/linuxrc rw root=/dev/ram0 initrd=initrd-2.4.22-ltsp-1.gz

As opções que podem ser passadas para o kernel atraves do append line

5) O pxelinux.0 usa o TFTP para o download de imagem do kernel e da imagem initrd 6) Os controles são então passados para o kernel

Se você quiser modificar os parâmetros para uma estação de trabalho especifica, você precisa criar o arquivo de configuração especifico para aquela estação de trabalho, criando o arquivo de configuração com o nome que combine com todos os endereços de IP das estações de trabalho convertidos em hexadecimal. Se você quiser modificar os parâmetros para todas as estações de trabalho você precisa simplesmente modificar o arquivo default

Tive problemas em iniciar o Servidor da imagem com todos os serviços automaticamente, ou seja, o Cluster não se auto-configura, é precisava iniciar o servidor de imagem, subir os serviços de DHCP, TFTP e NFS manualmente para depois ligar as demais máquinas.

O caminho para configurar no modo gráfico é:

K > Knoppix > Services > Start KnoppixTerminalServer

Clicar em (Re) Configurar Servidor e (Re) Iniciar conforme apresentado na figura abaixo

97

Configurar a placa de rede disponível no Servidor (no caso, temos apenas uma placa de rede disponível).

Em seguida configurar o range de endereçamento IP no qual o DHCP irá fornecer aos nós. (No caso, o range de endereços IP será de 192.168.0.201 a 192.168.0.250).

Configurar o que deverá ser exportado aos nós, que temos as seguintes opções:

CDROM, diretório ou Partição. Selecionamos um diretório, porem será preciso corrigir, explicarei mais adiante os detalhes.

98

Seguindo, teremos que especificar qual é o modulo da placa de rede dos nós, onde escolheremos dentre centenas de módulos disponíveis como mostrado abaixo.

Depois, configuramos o que deveremos executar nos nós como: acesso root, modo texto, roteamento, DNS e proxy.

Na tela seguinte é possível passar parâmetros ao Kernel, porem não utilizaremos essa funcionalidade.

E por fim, se desejamos iniciar os serviços no momento como apresentado abaixo.

99

Vou explicar alguns detalhes particulares que tive que fazer para essa implementação. O diretório a ser exportado precisa ser corrigido, pois por algum erro no script as opções disponíveis apontam para uma partição que no caso apontava para /dev/hda3. Não foi escolhido CDROM, pois o acesso seria mais lento e também como um dos objetivos apresentados é o baixo custo, é um dispositivo a menos em uma máquina. Exportar uma partição até seria possível, porem para cada alteração que efetuasse no SO, teria que ser criada outra partição e apontá-la.

Como inicialmente estamos utilizando o mesmo arquivo do CD ClusterKnoppix criamos um diretório /export na raiz, e copiamos para dentro dele o arquivo da mesma forma que inicia no CD, ou seja, o diretório /KNOPPIX/KNOPPIX, ficando o caminho correto como:

/export/KNOPPIX/KNOPPIX

Porém, como descrito acima é preciso efetuar algumas correções, pois o script cria um link simbólica chamada diskless apontando para /dev/hda3 então temos que remove-lo e apontar esse link para /export.

Fazemos isso com os seguintes comandos:

rm diskless ln s /export/ diskless

Então se digitarmos ls na raiz irá aparecer:

Diskless -> /export/

Caso o serviço NFS esteja executando quando apagarmos e criarmos novamente o link simbólico é preciso reiniciar o serviço, caso contrario não funcionara corretamente, pois perdeu a referencia. Para reiniciar executamos o seguinte comando:

/etc/init.d/nfs-kernel-server restart

Com isso simulamos os nós que estão acessando um drive de CDROM, porem sem a necessidade de possuir o dispositivo físico e com acesso mais rápido.

Esse procedimento alterou os seguintes arquivos:

/tftpboot/pxelinux.cfg/default /etc/exports /etc/dhcp3/dhcp.conf /etc/sysconfig/knoppix-terminalserver

Ainda tínhamos o problema de demorar a os nós bootarem e para diminuir

100

esse tempo editamos o arquivo:

/tftpboot/pxelinux.cfg/default

O parâmetro TIMEOUT300 ficou TIMEOUT30 O parâmetro vga = 791 ficou vga=normal

O primeiro parâmetro diminuiu o tempo de espera procurando o DHCP na rede, e o segundo parâmetro tivemos que mudar, pois os micros do laboratório XI não carregam o framebuffer (por não possuírem placa de vídeo off board).

Verificado que o problema de perder a configuração não ocorria somente quando reiniciava o computador, mas também se parar os serviços e iniciá-los novamente já era motivo para perder toda a configuração. Para corrigir esse problema foi necessário alterar os seguintes arquivos:

/etc/init.d/knoppix-terminalopenmosixserver /etc/init.d/knoppix-terminalserver

Foi alterado nos dois arquivos, pois eles são muito semelhantes nas suas funções. Existe uma função que faz uma copia de dispositivos. Então aproximadamente na linha 339, tem um comando:

cp cloop

corrigido para:

cp cloop*

Pois provavelmente em versões anteriores, é possível que o cloop era um arquivo e não um link simbólico como é nessa versão.

Também na função mkexport, foi colocado um return logo quando esta na função (aproximadamente linha 91) assim não altera mais o arquivo /etc/export. Obs: desde de que o arquivo /etc/export esteja correto.

Outra demora que tínhamos era que demorava muito aos nós localizarem o pxelinux. 0, então, nos arquivos /etc/host.allow e /etc/host.deny removemos (também poderia ser comentado) as linhas onde dizia qual host tinha permissão ou negação de acesso, assim todos ficam com permissão geral.

Também para agilizar o processo de inicialização dos nós, no arquivo /etc/hosts criamos um nome fictício para todos os micros e em /etc/dhcp3/dhcpd.conf comentado a linha onde iniciava o serviço de DNS. Ou seja, esses procedimentos foram feitos para os nós não precisarem ficar procurando nome de servidor na rede e desabilitado o DNS, assim é um serviço a menos executando e menos trafego na rede. Outro procedimento foi em /etc/dhcp3/dhcpd.conf apontar como máquina roteadora o próprio servidor, no IP: 192.168.0.1, mesmo a máquina servidora tendo apenas uma placa de rede.

Um detalhe que ocorria quando iniciávamos os servidor, ao iniciar os processos, com o comando:

/etc/init.d/knoppix-terminalserver start

Aparecia uma mensagem dizendo que o serviço já estava executando, porem,

101

verificando todos os processos ativos ele não aparecia na lista. Mas se parar o processo e inicia-lo novamente não aparece mensagens. Então para iniciar o servidor executando os serviços corretamente, criamos um script chamado S99knoppix-terminalStartStop no diretório /etc/rc5.d, que executa os seguintes comando: com o seguinte conteúdo: #!/bin/bash /etc/init.d/knoppix-terminalserver stop /etc/init.d/knoppix-terminalserver start

Com esse script executando na inicialização, os serviços de DHCP, TFTP e NFS já sobem automaticamente.

Aplicação

Uma aplicação para essa estrutura do cluster é a renderização de imagens de modelos vetoriais. Como modelos produzidos pelo Blender ou PovRay. Para tal entrei no fórum do site www.blender.com.br e o tópico Reduzindo tempo de renderização com Cluster (http://blender.com.br/portugues/modules.php?op=modload&name=Forums&file=viewtopic&topic=2671&forum=1) sugeria a animação de um modelo chamado blacksmith onde pode se retirar do site http://download.blender.org/demo/old_demos/blacksmith.tgz. Também utilizei um script chamado render.sh que ajuda na distribuição dos processos, retirado do site http://pubwww.fhzh.ch/~mgloor/mosix-blender.html que também explica como separar os processos manualmente e como utilizar o script que possui os seguintes parâmetros: ./render cenas.blend 0 5000 8

Quantidade de máquinas

para renderizar Ultimo frame

Primeiro frame Arquivo a renderizar

Após baixar o arquivo, e descompactá-lo no diretório /blacksmith colocamos o script de renderização no mesmo diretório e modificamos para executável com o comando:

chmod 755 render.sh ou chmod +x render.sh

Segue trecho do código do script (sem os comentário):

#!/bin/sh if [ $# -lt 1 ]; then echo "syntax: render.sh blenderscene startimage endimage nodes" exit 1 fi

BIN=/usr/local/bin/blender # blender path SCN=$1 # name of blender scene DIF=`expr \( $3 - $2 \)` # no. of images to render RPN=`expr \( $DIF / $4 \)` # no. of images per node LOP=`expr \( $4 - 1 \)` # loop counter

for i in `seq 0 $LOP` ; do BEG=`expr \( $i \* $RPN \) \+ \( $2 + 1 \)` END=`expr \( $i \+ 1 \) \* $RPN \+ $2`

102

$BIN -b $SCN -s $BEG -e $END -a > /dev/null 2> /dev/null & done

echo " " echo "Rendering" $DIF "images from" $1 "on" $4 "nodes." echo "Tasks forked, network rendering in progress." echo -n "Job started at: " ; date '+%d-%m-%y %H:%M:%S' echo "Please wait while rendering..." wait echo "Rendering successfully finished." echo -n "Job ended at: " ; date '+%d-%m-%y %H:%M:%S' echo " "

A escolha dessa aplicação (Modelos em Blender) foi determinada pelos mesmo fatores no qual escolhemos a distribuição Linux, ou seja, o Blender é um aplicativo de código aberto, assim toda a comunidade de programação pode utilizar livremente e efetuar melhorias e distribuir a todos, tornando assim um software robusto, confiável e livre. Também por ser livre, não temos problema com licença. É uma ferramenta amplamente utilizada para a criação de modelos e animações.

Resultados

Para os resultados de renderização apresentados a seguir utilizamos o modelo que se encontra em: http://download.blender.org/demo/old_demos/blacksmith.tgz e o script render.sh

como já mencionado anteriormente. Por ser uma modelo relativamente simples foi possível mapear os nós que executaram e em seguida os respectivos tempo.

A configuração das maquinas são as seguintes:

M1 = P4 2.8 GHz 256 MB RAM M2 = P4 2.8 GHz 128 MB RAM M3 = P4 2.8 GHz 256 MB RAM M4 = P4 2.8 GHz 128 MB RAM M5 = P4 2.8 GHz 382 MB RAM M6 = P4 2.8 GHz 256 MB RAM M7 = P4 2.8 GHz 256 MB RAM M8 = P4 2.8 GHz 256 MB RAM

Resultados:

M1 = 3 min 45 s M1 + M2 = 2 min 9 s M1 + M2 + M3 + M4 = 1 min 11 s M1 + M2 + M3 + M4 + M5 = 1 min 7 s M1 + M2 + M3 + M4 + M5 + M6 = 1 min 2 s M1 + M2 + M3 + M4 + M5 + M6 + M7 = 59 s M1 + M2 + M3 + M4 + M5 + M6 + M7 + M8 = 1 min 14 s

Podemos notar neste teste que o aumento de 1 para 2 máquinas executando teve um resultado muito satisfatório e de 2 para 4 maquinas também. Porem a partir daí o aumento de máquinas para o processamento não obteve resultado tão melhor, ou seja, a partir de um ponto não vale a pela aumentar a capacidade de processamento, pois pelos resultados apresentados podem até piorar. Isso se dá pelos seguintes aspectos:

103

Latência de rede, mais nós acessando um disco e o algoritmo do Open Mosix leva de 30 a 40 segundos para distribuir os processos, chamado de tempo de setup. Para esse modelo, a quantidade de maquinas ideal é 7, porem para modelos mais complexos a quantidade pode ser maior.

No fórum do Blender Brasil (também já mencionado) os participantes disseram que existe um modelo chamado vidros.blend que demora cerca de 31 horas em uma máquina Athlon XP 2400+. Solicitei e me passaram esse arquivo por e-mail, assim achei que seria um modelo relativamente complexo para testar o Cluster. Então foi efetuado dois testes distintos:

1º Teste com o modelo vidros.blend 16 nós demorou 28 min 36 s 20 nós demorou 23 min 38 s 24 nós demorou 20 min 13 s

Esse primeiro teste foi efetuado nos nós iniciando em modo gráfico.

2º Teste com o modelo vidros.blend 24 nós demorou 19 min 19 s 26 nós demorou 17 min 47 s 28 nós demorou 16 min 56 s

Esse, segundo teste os nós, iniciaram em modo texto

Customização

Esta etapa se faz necessária quando queremos obter o melhor desempenho possível como poderá ser observado na seção de resultados do trabalho. Se obtém melhor desempenho pois as máquinas que executarão o processo (os nós) iniciarão somente processos essenciais carregando menos memória possível.

Como descrito na etapa de Boot Remoto, em /export/KNOPPIX existe um arquivo chamado KNOPPIX que é a imagem Linux compactada onde ele é exportado. Porem antes da customização o arquivo que era exportado tinha 598 MB, e após a remoção dos pacotes que desnecessário o arquivo a ser exportado ficou com 384 MB. Antes de remover os pacotes precisa ser copiado o conteúdo do arquivo imagem compactado para um diretório, que é feito com o seguinte comando:

# mkdir ~/damnsmall # mount /export/KNOPPIX/KNOPPIX ~/damnsmall -o loop # cd ~/damnsmall/KNOPPIX # modprobe cloop file=/export/KNOPPIX/KNOPPIX # mkdir /iso # cp ~/damnsmall/KNOPPIX/* /iso a

Com esses comandos copiamos a estrutura de arquivo p/ o diretório /iso.Na seqüência digitamos os comandos:

cd /iso chroot .

O comando chroot engana o Sistema Operacional, fazendo com que o diretório /iso seja entendido como apenas / . Agora podemos executar o programa apt-get

104

com o parâmetro remove, ficando dessa maneira:

apt-get remove

Originalmente são 1314 pacotes que faz parte da Distribuição ClusterKnoppix, então verificando o nome de cada pacote fui removendo os que aparentemente não são de extrema necessidade para a execução do Sistema Operacional, ficando disponível apenas 870 pacotes instalados. Até é possível diminuir ainda mais a quantidade de pacotes, porem é uma tarefa para alguém com profundo conhecimento em Linux ou com mais tempo hábil para esta tarefa.

Agora é só colocar o conteúdo do diretório /iso em um arquivo .ISO e compactá-lo. Este procedimento foi efetuado com o seguinte comando:

# mkisofs -R -V "cluster" -hide-rr-moved -pad /root/iso | create_compressed_fs - 65536 > /export/KNOPPIXcustomizado

Note que o | (pipe) é utilizado para a saído do comando mkisofs ser utilizada na entrada do comando create_compressed_fs onde o arquivo pronto será criado dentro do diretório /export com o nome de KNOPPIXcustomizado

Uma outra abordagem é buscar na Internet uma distribuição já customizada e com tamanho menor, porem tem a dificuldade de instalar o algoritmo do Open Mosix nessa Distribuição passando pelos passos explicados.

This document was created with Win2PDF available at http://www.win2pdf.com.The unregistered version of Win2PDF is for evaluation or non-commercial use only.