skip to main content
Idioma:

Algoritmos probabilísticos de list ranking para máquinas paralelas com memória distribuída

Santana, Fabiana Soares

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

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

  • Título:
    Algoritmos probabilísticos de list ranking para máquinas paralelas com memória distribuída
  • Autor: Santana, Fabiana Soares
  • Orientador: Song, Siang Wun
  • Assuntos: Arquitetura E Organização De Computadores
  • Notas: Dissertação (Mestrado)
  • Descrição: Algoritmos paralelos teoricamente eficientes frequentemente apresentam resultados práticos que deixam a desejar. Nos últimos anos, a freqüente discrepância entre a complexidade teórica e os tempos experimentais obtidos, aliada ao igualmentefreqüente desapontamento face aos valores absolutos desses tempos (comparados aos tempos seqüenciais), fizeram com que a questão passasse a ser amplamente discutida, resultando no surgimento de novos modelos paralelos. Dos novos modelossurgidos, merecem destaque o Bulk-Synchronous Parallel de L. G. Valiant e o Coarse-Grained Multicomputer de F. Dehne, um caso particular do primeiro com ênfase no projeto de algoritmos. Ambos os modelos são para máquinas paralelas com memóriadistribuída e a complexidade dos algoritmos é dada principalmente pelo número de rodada e o número de operações locais também ser mensurado. O estudo destes modelos faz parte deste trabalho. Partindo do modelo Coarse-Grained Multicomputer,dedicamo-nos ao estudo do problema de list ranking, que consiste em determinar a distância de todos os nós de uma lista ligada em relação ao último nó desta lista. O 'list ranking' é um problema computacional básico e possui diversas aplicaçõesenvolvendo grafos e árvores, daí a sua importância. Esse estudo foi iniciado por F. Dehne e S.W. Song, resultando em um algoritmo paralelo que resolve o problema em O(log p+log log n) rodadas de comunicação, com alta probabilidade, e em umnúmero esperado de O(n/p) operações de computação local. Implementamos este algoritmo e observamos que os resultados obtidos coincidem com os valores teóricos resultantes da sua análise. No mesmo trabalho, os autores apresentaram outroalgoritmo, que resolve o problema com o mesmo número de operações locais mas em um número menor de rodadas, O(k log p), com alta probabilidade, onde k é um número muito pequeno, porém dependente de n. Apresentamos um outro algoritmo, igualmente ) probabilístico, que melhora ainda mais esta complexidade, resolvendo o problema com o mesmo número de operações locais mas em O(log p) rodadas. Note que este número de rodadas é independente do tamanho da entrada e que, portanto,este algoritmo constitui-se a na maior contribuição desta dissertação. Contamos com a colaboração do Prof. Yoshiharu Kohayakawa na sua formulação. Ele foi implementado e os resultados obtidos também coincidem com a sua análise. A partir dosresultados práticos obtidos com esses algoritmos, concluímos o trabalho com as nossas observações a respeito do modelo estudado e sugestões para trabalhos futuros envolvendo o modelo e o problema
  • DOI: 10.11606/D.45.1997.tde-20220712-114938
  • 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: 1997-12-18
  • 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.