masterThesis
Implementação paralela escalável e eficiente do algoritmo simplex padrão em arquitetura multicore
Fecha
2014-01-24Registro en:
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.
Autor
Coutinho, Demetrios Araújo Magalhães
Resumen
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