Implementação Paralela Escalável e Eficiente do Algoritmo Simplex Padrão na Arquitetura Multicore
Escalabilidade Paralela, Algoritmo Simplex, Multicore, Programação Linear, Eficiência de software
Este trabalho apresenta uma implementação paralela escalável e eficiente do algoritmo simplex padrão na 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. A paralelização proposta é apresentada com destaque para os conceitos de paralelismo utilizados. Foram realizadas análises de desempenho, através da comparação dos tempos sequenciais utilizando o Simplex tableau e Simplex do CPLEX R da IBM . A análise de escalabilidade foi feita com problemas de diferentes dimensões, encontrando evidências de que o algoritmo simplex padrão tem melhor eficiência paralela para problemas com mais variáveis do que restrições. Para apoiar essas afirmações, este trabalho apresenta resultados de vários experimentos numa máquina de memória compartilhada com 24 núcleos.