Detalhes bibliográficos
| Ano de defesa: |
1998 |
| Autor(a) principal: |
Saukas, Einar Luciano Gattoni |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Biblioteca Digitais de Teses e Dissertações da USP
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-014215/
|
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 |
