Title :
Multi GPU Implementation of the Simplex Algorithm
Author :
Lalami, Mohamed Esseghir ; El-Baz, Didier ; Boyer, Vincent
Author_Institution :
LAAS, CNRS, Toulouse, France
Abstract :
The Simplex algorithm is a well known method to solve linear programming (LP) problems. In this paper, we propose an implementation via CUDA of the Simplex method on a multi GPU architecture. Computational tests have been carried out on randomly generated instances for non-sparse LP problems. The tests show a maximum speedup of 24.5 with two Tesla C2050 boards.
Keywords :
computer graphic equipment; coprocessors; linear programming; multiprocessing systems; parallel architectures; CUDA; Tesla C2050 boards; computational tests; linear programming; multi GPU architecture; nonsparse LP problem; randomly generated instances; simplex method; Computer architecture; Graphics processing unit; Indexes; Instruction sets; Kernel; Linear programming; Synchronization; CUDA; GPU computing; Simplex method; hybrid computing; linear programming; parallel computing;
Conference_Titel :
High Performance Computing and Communications (HPCC), 2011 IEEE 13th International Conference on
Conference_Location :
Banff, AB
Print_ISBN :
978-1-4577-1564-8
Electronic_ISBN :
978-0-7695-4538-7
DOI :
10.1109/HPCC.2011.32
