(242h) Using Functional Programming and GPU Parallel Computing to Improve Stochastic Optimization

Using Functional Programming and GPU Parallel Computing to Improve Stochastic Optimization

Peter F. Muehlebach Chemical and Petroleum Engineering Department, University of Kansas, Lawrence, KS, Andy Gil, Electrical Engineering and Computer Science, University of Kansas, Lawrence, KS, Kyle V. Camarda, Chemical and Petroleum Engineering, University of Kansas, Lawrence, KS

In chemical engineering, there is a need to isolate near-optimal solutions from large non-convex sets.  This work focuses on using functional programming and parallel computing on a GPU to decrease the computation time of stochastic optimization algorithms.  One way to implement optimization algorithms more efficiently is to apply parallel computing.  When computing algorithms in parallel, they are limited by the number of cores on a processor.  Even the highest level i7 processors can only run eight threads (two per core on four cores).  However, running programs on a graphics processing unit (GPU) rather than the more traditionally utilized central processing unit (CPU) can better utilize parallel computing.  Typically, GPUs have thousands of cores available to execute threads, but they cannot handle irregular calculations.  Since most stochastic optimization methods require repeated simple mathematical calculations, parallel GPU computing provides an opportunity to compute solutions quickly and efficiently.

Unrecognized runtime errors and side effects can make calculations within a stochastic optimization method more challenging to make parallel than they need to be.  To address these issues, this project implements Haskell, a very strongly typed, purely functional programming language.  The strict typing within Haskell will eliminate the chance of unrecognized runtime errors that are common in object oriented programming languages.  Since Haskell is a functional programming language, functions within Haskell do not produce side effects.  Therefore, Haskell is an appropriate candidate for writing optimization algorithms to be executed on GPUs.  This will improve parallelization efficiency, allowing for quicker and more comprehensive optimization solutions.

A Tabu search algorithm was written in Haskell and applied to a computational molecular design problem involving ionic liquids as mass separating agents.  Tabu search is a stochastic method that uses an adaptive memory strategy.  The method was first tested on a binary knapsack problem, and then adapted to fit the ionic liquid design problem. The Haskell version of the code was compared to the Microsoft VBA version of the program, which is currently implemented in Dr. Kyle Camarda’s research group at the University of Kansas.  In conclusion, the use of Haskell increased the efficiency of parallel computing with this algorithm.  Run time curves show a substantial decrease in computation time when the algorithm is run in parallel on a GPU rather than a CPU.