Texto completo
| |
| Autor(es): |
Fabiana Soares Santana
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | São Paulo. |
| Instituição: | Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) |
| Data de defesa: | 1997-12-18 |
| Orientador: | Siang Wun Song |
| Resumo | |
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 (AU) | |
| Processo FAPESP: | 96/01251-0 - Algoritmos paralelos escaláveis para list ranking |
| Beneficiário: | Fabiana Soares Santana |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |