Algoritmos paralelos escaláveis para list ranking

• Processo: 96/01251-0
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de abril de 1996
• Data de Término da vigência: 31 de março de 1997
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Metodologia e Técnicas da Computação
• Pesquisador responsável: Siang Wun Song
• Beneficiário: Fabiana Soares Santana
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Algoritmos Memória (eletrônica digital)
• Palavra(s)-Chave do Pesquisador: Algoritmo Escalavel | Algoritmo Paralelo | Granularidade Grossa | List Ranking

Resumo

O objetivo do projeto é o desenvolvimento de algoritmos paralelos escaláveis para "list ranking" para máquinas de memória distribuída, baseado no modelo de granularidade grossa de F. Dehne. Estudamos dois algoritmos recentes para este problema. O primeiro requer, com alta probabilidade, log(3p) + log ln(n) rodadas de comunicação ( n sendo tamanho da entrada e p o número de processadores). O segundo requer apenas r ≤ (4k + 6) log(2/3 p) + 8 rodadas de comunicação, onde k ≤ (n*(n) é um número extremamente pequeno. Dados experimentais serão obtidos para mostrar a eficiência dos algoritmos do ponto de vista prático, usando-se a máquina Parsytec PoweXplorer; (AU)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

SANTANA, Fabiana Soares. Algoritmos probabilísticos de list ranking para máquinas paralelas com memória distribuída. 1997. Dissertação de Mestrado - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.