Texto completo
| |
| Autor(es): |
Einar Luciano Gattoni Saukas
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: | 1998-02-09 |
| Orientador: | Siang Wun Song |
| Resumo | |
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 (AU) | |
| Processo FAPESP: | 96/12535-9 - Algoritmos de seleção para máquinas paralelas com memória distribuída |
| Beneficiário: | Einar Luciano Gattoni Saukas |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |