Implementation Of Revised Simplex Method Based On GPU

Today's GPUs (Graphics Processing Units) outperform conventional CPUs, because of high-performance multiprocessor array, high memory bandwidth, and latency-hidden parallel pipeline mechanism. However, harvesting this computing power is not trivial as GPUs are designed and optimized for graphic operations. Originally, graphics display was acting as a kind of output. GPUs are supposed to assist CPUs in accelerating graphic operations to release CPUs from the burdensome graphics tasks. Then CPUs would focus on general purpose computation applications, while GPUs focus on shading and rendering. Recent years, GPUs underwent a dramatic increase in performance. The main reason behind such an evolution is that GPUs devote more transistors into data processing rather than data caching and flow control. Along with programmable interface became open and high-level shading languages became widespread, GPUs are capable of both graphics and non-graphics processing. A new concept: General-Purpose Computation on GPU (GPGPU) then came out.GPUs are specialized in processing large amounts of data in streaming and parallel fashion. Consequently, most GPGPU application appears in following disciplines: games, scientific computation, geology, biology, physical simulation and so on. In future, more development and research fields would benefit from it: sort and document classification in search engine, database query and data mining, data analysis in finance, statistics, biomedicine project, navigation recognition, military simulation, speech and image recognition, etc. In scientific computation, most research focus on algebraic calculation, such as operations on vector or matrix and Partial Differential Equations. Linear Programming Problem is one of its applications as an optimization technology. Simplex Method was presented in 1947, as a general method to solve Linear Programming Problem, which is exponential but not polynomial. Revised Simplex Method is a revision of Simplex Method, aiming at optimizing time complexity and space complexity when carried out on computer. In the method, most data structures are vectors or matrices, and most operations are matrices multiplication. This property happens to be GPUs'advantages: data parallel, compute intense and frequent memory access. Therefore, the paper implemented Revised Simplex Method as a GPGPU application.GPU couldn't work independently because incapable of startup and I/O by itself. Instead, a GPGPU application has a mechanism that GPUs act asCPUs'cooperator. After all, general-purpose processing is very different from graphics processing. GPUs are good at algebraic operations but not at dynamic flow control. Apparently, it's not feasible and not reasonable to make serial procedure on CPUs working in a parallel fashion on GPUs. This work redesigned a computation model, which rationally assign tasks to CPU and GPU. CPU took charge of what it's good at, such as conditions and sort. GPU took charge of matrices operations. Data copying between system memory and device memory is the most important performance bottleneck, which should be avoided. The calculate rules are also different. GPGPU differs from parallel computation because of some characters: transparentscheduler, SIMD (Single Instruction Multiple Data) pipelines, domain size, single texture size, etc. It should be not only functional but also efficient. There introduced two generations of general purpose GPUs in the paper: AMD ATI FireStream 2U and NVIDIA GeForce8800 GTX, with their programmable environment: CTM (Close To Metal) and CUDA (Compute Unified Device Architecture). The different hardware architecture and software interface result in different implement details.Testing samples are randomly generated normalized single precision floats. We compared the three versions of experiment results, which proved that the computation model is correct and efficient with obviously higher performance. Notice that, when the problem size is relatively small, GPU version is inferior to MATLAB version and CPU version. The calculation ratio is small and the transfer latency costs a lot; consequently the power can't be well utilized. Because the configuration environments are different, we can only compare the two GPUs through some parameters such as peak value of float computation, pipeline architecture, memory bandwidth, amount of processors, type of shaders, etc. In a word, the new generation NVIDIA's GPU is superior in every aspect.Through experiment, the computation model we presented is proved to be sound and correct. The hardware specialization of GPU restricted the solvable problem size. Since linear programming problem is often sparse with large amount of variables, we presented a compact strategy. Thecompact algorithm revised the primary computation model compressing both the data structure and compute rules. The optimization of both time and space complexities is proved in theory, also in practice.This paper has a profound comprehend in hardware architecture, programmable interface, development environment, shading language, memory system and peak performance of the two general purpose GPUs. The support from hardware and software became more mature. After the unified compute architecture came out, cooperation design of hardware and software is achieved. The next move is conformity of CPU hardware and GPU hardware. But making GPU a general purpose processor will repeat the development procedure of CPUs'. If the specialization disappears, superioritymay be lost. Based this paper, future work will focus on polynomialalgorithms of linear programming problems, even further on other optimization problems such as Integer Programming problems.