A repository containing examples and a benchmarking script for the upcoming paper entitled "Automatic Generation of GPU Kernels for Evaluators of McCormick-Based Relaxations and Subgradients"
Robert X. Gottlieb, Matthew D. Stuber
One approach to the global solution of (MI)NLPs involves computing convex and concave relaxations of nonlinear expressions in the optimization problem, such as with generalized McCormick relaxations. Typically, these calculations are performed using CPU resources. For many other computationally expensive tasks, graphics processing units (GPUs) have been used to great effect, but to the best of our knowledge, GPUs have not been used to calculate nonlinear relaxations. In this work, we develop a source code generation approach that enables the GPU acceleration of generalized McCormick relaxations, available as SourceCodeMcCormick.jl. Across a variety of benchmark test set problems, available in this repository, we are able to achieve speedups in the calculation of relaxations and their subgradients in the range of one-to-four orders-of-magnitude over a CPU-based implementation of these rules (McCormick.jl).
A TXT file containing the results may be reproduced using in the following fashion.
- Clone this git repository to you local machine.
- Install Julia 1.10 or greater, see https://julialang.org/downloads/ (v1.12.5 used in the paper)
- Install the following packages through the Julia package manager (versions used in the paper in parentheses):
- SourceCodeMcCormick.jl (v0.5.2)
- McCormick.jl (v0.14.0)
- CUDA.jl (v5.11.0)
- BenchmarkTools.jl (v1.6.3)
- MKL.jl (v0.9.1) [optional]
- Run the file RSParallelMcCormick\src\benchmark_script.jl to generate the results. By default, results will be saved in a new file called
new_benchmark_results.txt. Note that some problems are skipped by default due to high compile times. To run all problems, comment out lines 147--157.
- SourceCodeMcCormick.jl for GPU-accelerated calculation of McCormick relaxations.
- McCormick.jl for CPU-based calculation of McCormick relaxations.