In this project, called Peticodiac, we use many-core devices (such as GPUs) to accelerate the primitive operations of the general simplex procedure. The host program is implemented in C++, and the device kernels are implemented in either OpenCL or CUDA.
The primitive operations of the general simplex procedure include:
-
check bounds: finds "broken" variables by checking for bounds violations of the basic variables
-
find suitable: finds a suitable non-basic variable whose assignment may be tweaked in order to correct the violation
-
pivot: swaps the basic (broken) and non-basic (suitable) variables, updates the tableau, and updates the assignment of the broken variable
-
update assignment: computes the new assignment of all the basic variables
If you are using MacOS X, install the GNU gcc6 compiler first, and ensure the OpenMP library is installed.
brew install homebrew/versions/gcc6
Create an out-of-place build using CMake. Make sure the project directory is clean and the CMakeCache.txt does not exist. This builds the project with CUDA support
# At the project root: peticodiac
mkdir build
cd build
cmake ..
make
To build the project without CUDA support, pass in the CUDA flag.
cmake .. -DCUDA=OFF
make
The peticodiac binary is generated in peticodiac/bin
Usage:
./peticodiac NUM_OF_VARIABLES NUM_OF_CONSTRAINTS SOLVER_TYPE
NUM_OF_VARIABLES: specify the number of initial non-basic variables to be create
NUM_OF_CONSTRAINTS: specify the number of initial basic variables to be create
SOLVER_TYPE: specify the solver type
1: CPU_EAGER
2: CPU_LAZY
3: CUDA
Example:
# Determine feasibility for a linear equation with 3 non-basic variables
# and 1 constraint using the CPU-Eager solver
# x0 + x1 + x2 + s0 = 0
# l <= s0 <= u, where l and u are randomly generated
./peticodiac 3 1 1
This project is a current work-in-progress. In the near future, additional information will be provided for building and using the application, as well as providing benchmarks and links to other useful resources.