Please use this identifier to cite or link to this item: https://repositorio.ufrn.br/jspui/handle/123456789/15502
Title: Implementação paralela escalável e eficiente do algoritmo simplex padrão em arquitetura multicore
Authors: Coutinho, Demetrios Araújo Magalhães
Keywords: Simplex. CPLEXR. Eficiência Paralela. Escalabilidade Paralela. Programação Linear;Simplex. CPLEXR. Parallel Efficiency. Parallel Scalability. Linear Programming
Issue Date: 24-Jan-2014
Publisher: Universidade Federal do Rio Grande do Norte
Citation: COUTINHO, Demetrios Araújo Magalhães. Implementação paralela escalável e eficiente do algoritmo simplex padrão em arquitetura multicore. 2014. 96 f. Dissertação (Mestrado em Automação e Sistemas; Engenharia de Computação; Telecomunicações) - Universidade Federal do Rio Grande do Norte, Natal, 2014.
Portuguese Abstract: Este trabalho apresenta uma implementação paralela escalável e eficiente do algoritmo Simplex padrão em arquitetura de processadores multicore para resolver problemas de programação linear de grande escala. Apresenta-se um esquema geral explicando como foi paralelizado cada passo do algoritmo simplex padrão, apontando pontos importantes da implementação paralela. Foram realizadas análises de desempenho através da comparação dos tempos sequenciais utilizando o Simplex tableau e Simplex do CPLEXR da IBM. Os experimentos foram realizados em uma máquina de memória compartilhada com 24 núcleos. A análise de escalabilidade foi feita com problemas de diferentes dimensões, encontrando evidências de que a implementação paralela proposta do algoritmo simplex padrão tem melhor eficiência paralela para problemas com mais variáveis do que restrições. Na comparação com CPLEXR , o algoritmo proposto paralelo obteve uma eficiência de até 16 vezes maior
Abstract: This work presents a scalable and efficient parallel implementation of the Standard Simplex algorithm in the multicore architecture to solve large scale linear programming problems. We present a general scheme explaining how each step of the standard Simplex algorithm was parallelized, indicating some important points of the parallel implementation. Performance analysis were conducted by comparing the sequential time using the Simplex tableau and the Simplex of the CPLEXR IBM. The experiments were executed on a shared memory machine with 24 cores. The scalability analysis was performed with problems of different dimensions, finding evidence that our parallel standard Simplex algorithm has a better parallel efficiency for problems with more variables than constraints. In comparison with CPLEXR , the proposed parallel algorithm achieved a efficiency of up to 16 times better
URI: https://repositorio.ufrn.br/jspui/handle/123456789/15502
Appears in Collections:PPGEE - Mestrado em Engenharia Elétrica e de Computação

Files in This Item:
File Description SizeFormat 
DemetriusAMC_DISSERT.pdf2,37 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.