Busca avançada
Ano de início
Entree

Algoritmos paralelos escaláveis para list ranking

Processo: 96/01251-0
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de abril de 1996
Vigência (Término): 31 de março de 1997
Área do 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)

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)