Title :
Efficient Implementation of the Simplex Method on a CPU-GPU System
Author :
Lalami, Mohamed Esseghir ; Boyer, Vincent ; El-Baz, Didier
Author_Institution :
CNRS, LAAS, Toulouse, France
Abstract :
The Simplex algorithm is a well known method to solve linear programming (LP) problems. In this paper, we propose a parallel implementation of the Simplex on a CPU-GPU systems via CUDA. Double precision implementation is used in order to improve the quality of solutions. Computational tests have been carried out on randomly generated instances for non-sparse LP problems. The tests show a maximum speedup of 12:5 on a GTX 260 board.
Keywords :
coprocessors; linear programming; CPU-GPU system; CUDA; GTX 260 board; computational tests; double precision implementation; linear programming problems; nonsparse LP problems; parallel implementation; randomly generated instances; simplex method; Central Processing Unit; Computer architecture; Graphics processing unit; Indexes; Instruction sets; Kernel; Linear programming;
Conference_Titel :
Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on
Conference_Location :
Shanghai
Print_ISBN :
978-1-61284-425-1
Electronic_ISBN :
1530-2075
DOI :
10.1109/IPDPS.2011.362
