Journal
MULTIMEDIA TOOLS AND APPLICATIONS
Volume 77, Issue 22, Pages 30035-30050Publisher
SPRINGER
DOI: 10.1007/s11042-018-5947-z
Keywords
CUDA; GPU; Revised simplex algorithm; SIMD
Categories
Funding
- National Natural Science Foundation of China [51679105, 61672261,51409117]
- Jilin Province Department of Education Thirteen Five science and technology research projects [432, JJKH20170804KJ]
Ask authors/readers for more resources
The revised simplex algorithm (RSA) is a typical algorithm for solving linear programming problems. Many theoretical modifications have been done to make the algorithm more efficient, but almost all of them were based on single-instruction single-data architecture processors (CPUs), which could not make full use of the inherent parallel characteristics of RSAs. We propose a novel single-instruction multiple-data architecture processor (GPU) based on the RSA in this paper. The intensive matrix manipulations of a traditional RSA are offloaded to the GPU, which helps to make full use of its powerful parallel processing ability. We implemented the GPU-based RSA on compute unified device architecture (CUDA). Numerical experiments on randomly generated linear programs show that the GPU-based RSA can not only find the correct optimal solutions, but can also reach a speed of up to 100 times as fast as that of a CPU-based RSA: it also runs 3 to 11 times as fast as MATLAB.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available