Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/478
Tipo: Dissertação
Título: Algoritmos BSP/CGM para Ordenação
Autor(es): Gonda, Luciano
Abstract: O problema de ordenação é um assunto bastante estudado em computação. Ordenar uma seqüência S = (a1, a2, . . . , an), consiste em obter uma seqüência S' = (a'1, a'2, . . . , a'n), onde a'i ≤ a'j , se i < j. A paralelização de problemas é utilizada para reduzir o tempo de execução dos problemas que necessitam de alto poder de processamento. Neste trabalho descreveremos três algoritmos de ordenação paralelos desenvolvidos no modelo BSP/CGM, no qual cada processador possui memória de tamanho O(n/p), e em cada rodada de comunicação são enviados ou recebidos, no Maximo, O(n/p) dados. Neste modelo queremos sempre minimizar o número de rodadas de comunicação. Os algoritmos que descreveremos são: Ordenação-Bitonica, Ordenação-CD e Ordenação-por-Divisão. O algoritmo Ordenação-Bitonica utiliza O(log p) rodadas de comunicação e tempo de computação local O(nlogn/p). Os algoritmos Ordenação-CD Ordenação-por-Divisão utilizam O(1) rodadas de comunicação e tempo de computação local O(nlogn/p). A implementação do algoritmo Ordenação-CD apresenta resultados muito bons em relação ao tempo de execução, mostrando que este algoritmo é eficiente se executado para entradas grandes. Segundo os resultados experimentais, o algoritmo Ordenação-CD é o que apresenta os melhores resultados para todas as entradas.
Sorting is one of the most studied problems in Computer Science. Sorting a sequence S = (a1, a2, . . . , an), consists in obtaining another sequence S' = (a'1,a'2, . . . , a'n), where a'i ≤ a'j , se i < j. To reduce execution time of some problems that require high processing we can use parallel computing. In this work we describe three parallel sorting algorithms designed in BSP/CGM model, in which each processor has O(n/p) of local memory, and at most O(n/p) data are sent or received in each communication round. In this model, the number of communication rounds has to be as minimum as possible. The algorithms that we will describe are: Ordenação−Bitonica, Ordenação−CD and Ordenação−por−Divisão. The ordenação−Bitonica algorithm has O(log p) communication rounds and local time O(nlogn/p). Ordenação−CD and Ordenação−por−Divisão algorithms has O(1) communication rounds local time O(nlogn/p). The Ordenação−CD presents very good results, showing that this algorithm is efficient when executed with large entries. In agreement with experimental results, the Ordenação-CD algorithm presents better results for all entries.
Palavras-chave: Ordenação e Busca
Algoritmos Úteis e Específicos
Algoritmos e Estruturas de Dados
Programação Paralela
Tipo de Acesso: Acesso Aberto
URI: https://repositorio.ufms.br/handle/123456789/478
Data do documento: 2004
Aparece nas coleções:Programa de Pós-graduação em Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Luciano Gonda.pdf567,2 kBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.