skip to main content
Idioma:

Algoritmos paralelos de granularidade grossa para problemas de alinhamento de cadeias

Alves, Carlos Eduardo Rodrigues

Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística 2002-12-06

Acesso online. A biblioteca também possui exemplares impressos.

  • Título:
    Algoritmos paralelos de granularidade grossa para problemas de alinhamento de cadeias
  • Autor: Alves, Carlos Eduardo Rodrigues
  • Orientador: Song, Siang Wun
  • Assuntos: Arquiteturas E Programação Paralelas
  • Notas: Tese (Doutorado)
  • Descrição: Problemas de alinhamento de cadeias são fundamentais em aplicações diversas, das quais se destacam as relacionadas à Biologia Molecular. O alinhamento de duas cadeias A e B indica quão semelhantes elas são ou quais operações são necessárias para transformar uma em outra. Uma variação do problema de alinhamento de cadeias envolve comparar a cadeia A com todas as subcadeias de B. Para este problema, são conhecidos algoritmos seuqenciais que o resolvem em tempo O(|A||B|log(|A|+|B|)), um dos quais é apresentado nesta tese. É também apresentado um algoritmo seqüencial de tempo O(|A||B|) para um caso especial de alinhamento de todas as subcadeias, que envolve a busca pela maior subseqüência comum a duas cadeias. Propomos novos algoritmos paralelos para estes problemas, utilizando um modelo próprio para máquinas de memória distribuída, o CGM (Coarse Grained Multicomputers). Um dos objetivos fundamentais no desenvolvimento de algoritmos CGM é a redução do número de rodadas de comunicação, se possível tornando-o dependente apenas do número de processadores (p). Os algoritmos aqui propostos apresentam aceleração (speed-up) linear e apenas O(log p) etapas de comunicação. Não há algoritmos do nosso conhecimento com tais características na literatura
  • DOI: 10.11606/T.45.2002.tde-20210729-131306
  • Editor: Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística
  • Data de criação/publicação: 2002-12-06
  • Formato: Adobe PDF
  • Idioma: Português
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.