skip to main content
Idioma:

Algoritmos de seleção para máquinas paralelas com memória distribuída

Saukas, Einar Luciano Gattoni

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

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

  • Título:
    Algoritmos de seleção para máquinas paralelas com memória distribuída
  • Autor: Saukas, Einar Luciano Gattoni
  • Orientador: Song, Siang Wun
  • Assuntos: Metodologia E Técnicas De Computação
  • Notas: Dissertação (Mestrado)
  • Descrição: O tema principal deste trabalho é o problema da seleção: determinar o k-ésimo menor elemento de uma seqüência de n elementos. Para o modelo CGM (Coarse Grained Multicomputer) com p processadores e memória local de tamanho O(n 1 p), apresentamos um novo algoritmo paralelo determinístico para o problema da seleção que requer O(log p) rodadas de comunicação. Além deste número pequeno de rodadas, o algoritmo também procura minimizar a quantidade total de informações transmitidas a cada rodada (apenas O(p) exceto na última rodada). O algoritmo básico é então adaptado para resolver o problema de q seleções simultâneas na mesma seqüência de entrada, também em O(log p) rodadas de comunicação e assintoticamente mesmo tempo de computação local, caso q = O(p). O algoritmo de seleção simultânea origina um algoritmo de ordenação de comunicação eficiente, com O(log p) rodadas de comunicação e um total de O('p POT.2') informações transmitidas em cada rodada exceto na última. Em complemento à análise teórica de complexidades, apresentamos as implementações destes algoritmos utilizando interfaces de comunicação padrão (PVM e MPI) e os resultados experimentais obtidos em duas máquinas paralelas diferentes. Estes resultados mostram ganhos de desempenho ('speedups') praticamente lineares, indicando a eficiência e escalabilidade dos algoritmos propostos
  • DOI: 10.11606/D.45.1998.tde-20210729-014215
  • 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: 1998-02-09
  • Formato: Adobe PDF
  • Idioma: Português
Links
Voltar para lista de resultados
Resultado  1 AvançarIr para próxima página

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

Buscando em bases de dados remotas. Favor aguardar.