Multithreading vs DPCC SYCL Programming for OR computational implementations

Question

While well-known IP/LP solvers such as CPLEX and Gurobi have capabilities to run their solver on multiple threads, is there any tool that helps exploit the availability of not only multiple threads on a single CPU, but also increasingly, the availability of multiple processing units themselves? For instance, my laptop has one CPU with 8 threads and two other GPUs.

(a) Are there solvers that exploit the presence of multiple processing units -- CPU + additional GPUs on a machine?

(b) Is there any benefit to learning DC++ and SYCL (and other options such as Open CL / CUDA) programming for operations research computations?

(c) Are there any open source template code bases in C/C++ that someone can use to build their own OR models?

Answer 1

(a) Are there solvers that exploit the presence of multiple processing units -- CPU + additional GPUs on a machine?

Many solvers can work with multiple CPUs. Fewer can do distributed optimization. GPUs have been used in some academic studies, but in general, GPUs don't work very well when dealing with large sparse LP/MIP models. So there is, as of yet, not much commercial interest. Of course, GPUs are much more popular in dense linear algebra and machine learning.

(b) Is there any benefit to learning DC++ and SYCL (and other options such as Open CL / CUDA) programming for operations research computations?

If you want to develop your own high-performance algorithms, this may be of some interest. For modeling, not so much (often better to just use readily available tools -- writing your own tools is often not a good investment: buying good tools is much cheaper than developing them).

(c) Are there any open source template code bases in C/C++ that someone can use to build their own OR models?

Most model development is not done in C++ but in higher-level languages such as Python or using modeling languages such as AMPL and GAMS. C++ is more for developing high-performance algorithms than for model building. Modelers like to be efficient (they often work under time pressure), and using more low-level languages does not help there. Also, model maintenance may be more difficult when using low-level languages. Performance is usually less of an issue when doing modeling (opposed to when running solvers to solve these models: solvers are often written in C or C++).

It seems you are mixing model development and solver development. These are two very different crafts. At least for traditional mathematical programming (e.g. LP/MIP) and for constraint programming (CP). When writing your own tailored heuristic algorithms, the difference may be a bit more blurred.

Answer 2

There at least 4 to 5 companies building and selling software for solution of (mixed) linear optimization problems. All these companies has many very clever employees that have put many man years into the software.

I am pretty sure if any of those companies thought they could make their software be much better than the competitors by using GPUs then they would do it. Simply because they could make of lot of money that way.

I have been working on Mosek for almost 25 years and based on that experience then there is no simple trick like using a GPU that will make the software much better. Rather if all optimization software vendors is not doing something then it is most likely impossible or not worthwhile.

Regarding multithreading as asked in the comments after the initial post. I only have experience with parallelizing interior-point methods. My conclusion is that parallelizing something like an inner product provides little benefit, because the computation is memory bound. Parallelizing something like big dense matrix multiplication is fairly easy because you parallelize O(n^3) computations but only read O(n^2) data. Therefore, the benefit from solving an LP parallel will highly depend on what type computations are dominating and that is problem dependent.