Orientador: José Márcio Machado / Banca: Liria Matsumoto Sato / Banca: Aleardo Manacero Junior / Resumo: Devido a crescente quantidade de dados genômicos para comparação, a computação paralela está se tornando cada vez mais necessária para realizar uma das operaçoes mais importantes da bioinformática, o alinhamento múltiplo de sequências. Atualmente, muitas ferramentas computacionais são utilizadas para resolver alinhamentos e o uso da computação paralela está se tornando cada vez mais generalizado. Entretanto, embora diferentes algoritmos paralelos tenham sido desenvolvidos para suportar as pesquisas genômicas, muitos deles não consideram aspectos fundamentais da computação paralela. O MUSCLE [1] e uma ferramenta que realiza o alinhamento m ultiplo de sequências com um bom desempenho computacional e resultados biológicos signi cativamente precisos [2]. Embora os m etodos utilizados por ele apresentem diferentes versões paralelas propostas na literatura, apenas uma versão paralela do MUSCLE foi proposta [3]. Essa versão, entretanto, foi desenvolvida para sistemas de mem oria compartilhada. O desenvolvimento de uma versão paralela do MUSCLE para sistemas distribu dos e importante dado o grande uso desses sistemas em laboratórios de pesquisa genômica. Esta paralelização e o foco deste trabalho e ela foi realizada utilizando-se abordagens paralelas existentes e criando-se novas abordagens. Como resultado, diferentes estratégias paralelas foram propostas. Estas estratégias podem ser incorporadas a outras ferramentas de alinhamento que utilizam, em determinadas etapas, a mesma abordagem sequencial. Em cada método paralelizado, considerou-se principalmente a e ciência, a escalabilidade e a capacidade de atender problemas reais da biologia. Os testes realizados mostram que, para cada etapa paralela, ao menos uma estratégia de nida atende bem todos esses crit erios. Al em deste trabalho realizar um paralelismo in edito, ao viabilizar a execução da ferramenta MUSCLE em... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: Due to increasing amount of genetic data for comparison, parallel computing is becoming increasingly necessary to perform one of the most important operations in bioinformatics, the multiple sequence alignments. Nowadays, many software tools are used to solve sequence alignments and the use of parallel computing is becoming more and more widespread. However, although di erent parallel algorithms were developed to support genetic researches, many of them do not consider fundamental aspects of parallel computing. The MUSCLE [1] is a tool that performs multiple sequence alignments with good computational performance and biological results signi cantly precise [2]. Although the methods used by them have di erent parallel versions proposed in the literature, only one parallel version of the MUSCLE tool was proposed [3]. This version, however, was developed for shared memory systems. The development of a parallel MUSCLE tool for distributed systems is important given the wide use of such systems in laboratories of genomic researches. This parallelization is the aim of this work and it was done using existing parallel approaches and creating new approaches. Consequently, di erent parallel strategies have been proposed. These strategies can be incorporated into other alignment tools that use, in a given stage, the same sequential approach. In each parallel method, we considered mainly the e ciency, scalability and ability to meet real biological problems. The tests show that, for each parallel step, at least one de ned strategy meets all these criteria. In addition to the new MUSCLE parallelization, enabling it execute in a distributed systems, the results show that the de ned strategies have a better performance than the existing strategies. / Mestre

Orientador: Aleardo Manacero Junior / Coorientador: Miron Livny / Banca: Sergio Azevedo de Oliveira / Banca: Renata Spolon Lobato / Banca: Alfredo Goldman Lejbman / Banca: Henrique Mongelli / Resumo: Em sistemas distribuídos de larga escala; onde os recursos compartilhados são de propriedade de entidades distintas; existe a necessidade de refletir o fator propriedade dos recursos no processo de escalonamento de tarefas e alocação de recursos. Um sistema de gerenciamento de recursos apropriado deve garantir que os proprietários de recursos tenham acesso aos seus recursos ou ao menos a uma parcela de recursos que seja equivalente a eles. Diferentes políticas podem ser estabelecidas para que o sistema garanta esse direito aos proprietários de recursos; e nessa tese defende-se uma política de escalonamento e alocação de reucrsos chamada Owner-Share Enforcement Policy (OSEP) ou Política de Garantia da Porção do Proprietário; que tem por objetivo garantir o direito de acesso aos recursos através de um sistema de escalonamento baseado em preempção de tarefas e realocação de recursos. Avalia-se a política através da análise de testes e resultados envolvendo métricas de desempenho que descrevem fatores como violação da política; perdada capacidade de processamento; custo da política e satisfação do usuário. Os testes ainda envolveram a análise de desempenho da política em ambientes com a possibilidade de chekcpointing de tarefas; minimizando assim o desperdício de processamento. Fez-se ainda comparações com a política de compartilhamento justo Fair-Share; que permitiram estabelecer as vantagens e desvantagens de cada política e ainda identificar futuros problemas. Por fim; conclui-se a tese identificando as contribuições oferecidas por este trabalho e os trabalhos futuros que podem ser desenvolvidos. / Abstract: In large distributed systems, where shared resources are owned by distinct entities, there is a need to reflect resource ownership in resource allocation. An appropriate resource management system should guarantee that owners of resources have access to their resources or at least to a share of resources proportional to the share of resources they provide. Different policies can be established for guaranteeing the access to resources, and in this thesis we introduce a policy for scheduling and resource allocation named Owner Share Enforcement Policy (OSEP). This policy is based on the concept of distributed ownership and itguarantees the owner's right of accessing their share of resources in a distributed system with a preemptive share space. We evaluate this policy through tests and results analysis involving performance metrics that describe policy violation, loss of capacity, policy cost and user satisfaction. The tests were also conducted in environments withand without job checkpointing, and comparisons with the Fair-Share scheduling policy were made in order to capture the trade-offs of each policy. Finally, we conclude the thesis describing the contributions achieved with this work and pointing directions for future work. / Doutor