Made available in DSpace on 2014-12-17T14:56:18Z (GMT). No. of bitstreams: 1
DemetriusAMC_DISSERT.pdf: 2429364 bytes, checksum: 57aaf24560c189720b218dbca0ef1a56 (MD5)
Previous issue date: 2014-01-24 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / 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 / 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
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/15502 |
| Date | 24 January 2014 |
| Creators | Coutinho, Demetrios Ara?jo Magalh?es |
| Contributors | CPF:82838607472, http://lattes.cnpq.br/9892239670106361, Aloise, Daniel, CPF:03553729406, http://lattes.cnpq.br/5093210888872414, Lopes, Danniel Cavalvante, CPF:02878120493, Souza, Samuel Xavier de |
| Publisher | Universidade Federal do Rio Grande do Norte, Programa de P?s-Gradua??o em Engenharia El?trica, UFRN, BR, Automa??o e Sistemas; Engenharia de Computa??o; Telecomunica??es |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Unknown |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.002 seconds