Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/478
Registro completo de metadados
Campo DCValorIdioma
dc.creatorGonda, Luciano-
dc.date.accessioned2011-09-09T12:08:13Z-
dc.date.available2021-09-30T19:56:37Z-
dc.date.issued2004-
dc.identifier.urihttps://repositorio.ufms.br/handle/123456789/478-
dc.description.abstractO 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.pt_BR
dc.description.abstractSorting 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.pt_BR
dc.language.isoporpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectOrdenação e Buscapt_BR
dc.subjectAlgoritmos Úteis e Específicospt_BR
dc.subjectAlgoritmos e Estruturas de Dadospt_BR
dc.subjectProgramação Paralela-
dc.titleAlgoritmos BSP/CGM para Ordenaçãopt_BR
dc.typeDissertaçãopt_BR
dc.contributor.advisor1Mongelli, Henrique-
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.