Algoritmos de seleção para máquinas paralelas com memória distribuída (1998)
- Authors:
- Autor USP: SAUKAS, EINAR LUCIANO GATTONI - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: METODOLOGIA E TÉCNICAS DE COMPUTAÇÃO
- Language: Português
- Abstract: 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
- Imprenta:
- Data da defesa: 09.02.1998
-
ABNT
SAUKAS, Einar Luciano Gattoni. Algoritmos de seleção para máquinas paralelas com memória distribuída. 1998. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 1998. Disponível em: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-014215/. Acesso em: 01 nov. 2024. -
APA
Saukas, E. L. G. (1998). Algoritmos de seleção para máquinas paralelas com memória distribuída (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-014215/ -
NLM
Saukas ELG. Algoritmos de seleção para máquinas paralelas com memória distribuída [Internet]. 1998 ;[citado 2024 nov. 01 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-014215/ -
Vancouver
Saukas ELG. Algoritmos de seleção para máquinas paralelas com memória distribuída [Internet]. 1998 ;[citado 2024 nov. 01 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-014215/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
