• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Disertación de Maestría
DOI
https://doi.org/10.11606/D.45.1997.tde-20220712-114938
Documento
Autor
Nombre completo
Fabiana Soares Santana
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 1997
Director
Título en portugués
Algoritmos probabilísticos de list ranking para máquinas paralelas com memória distribuída
Palabras clave en portugués
Arquitetura E Organização De Computadores
Resumen en portugués
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
Título en inglés
not available
Resumen en inglés
not available
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2022-07-13
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2023. Todos los derechos reservados.