Metal Acceleration for cuPDLP-C

[swiggyachint08]

FEATURE REQUEST

Would it be possible to get a Metal accelerated version of cuPDLP-C anytime sooner? I believe without creating a direct dependency on High cost Nvidia GPUs, it would give a way to accelerate the algorithms using GPU on Mac devices

[jajhall]

We will be writing our own version of PDLP, and will look to enable it to run on Macs

[mocenigo]

We will be writing our own version of PDLP, and will look to enable it to run on Macs

And this sounds glorious. Is there an ETA? Is this in the pdlp-raphael branch? I observed it is quite fast on some problems.

[jajhall]

Work has started on the new PDLP solver but it's not yet part of the repo. We've got external funding to develop it that will grease the wheels and will focus our minds on a delivery date of November. The pdlp-raphael branch is just a sandbox for an intern to develop his own PDLP solver. Any speed in that branch is the same as latest.

[mocenigo]

Work has started on the new PDLP solver but it's not yet part of the repo. We've got external funding to develop it that will grease the wheels and will focus our minds on a delivery date of November. The pdlp-raphael branch is just a sandbox for an intern to develop his own PDLP solver. Any speed in that branch is the same as latest.

By the way, how do I build the highspy package so that I can use "latest" in my python code?

[jajhall]

I thought we had this documented somewhere, but no...

I've done it many times, and have the following note (for Linux)

• Let . be the root of HiGHS, as checked out from GitHub, and ./build be your build folder
• Decide on your install folder ("install") for HiGHS and set CMAKE_INSTALL_PREFIX to its location by running

cd build; cmake .. -DCMAKE_INSTALL_PREFIX=install

• Install HiGHS by running (from ./build)

make install

• Go back to . and run

sudo pip install . --break-system-packages

• You may need to have run

sudo apt install python3-pip

If you're on Windows I don't know how to do it

[ichnograph]

Has there been any progress on this in the last months?

[jajhall]

Has there been any progress on this in the last months?

No, sorry, still working on the NVIDIA build

[galabovaa]

Converting this to a discussion, still focusing on NVIDIA and AMD until possibly a later stage.

[mocenigo]

I have seen that in the ZLUDA source tree, there is highs integration, https://github.com/vosen/ZLUDA/tree/master/ext/highs-sys but, since ZLUDA does not support metal, I am not sure how this performs. Have you done some performance testing there? (Or: does it work at all?)

OTOH, have you had a look into cuda-metal https://github.com/Lulzx/cuda-metal/ or CUDAM https://github.com/MEHDI342/CUDAM ?

[jajhall]

Thanks for the heads up. I didn't know about this rust binding for HiGHS. We've considered adding a metal facility to HiGHS, but it's not high on our list of priorities

[Lulzx]

I can take a look to see if it works with cuda-metal

[Lulzx]

@mocenigo I got the CUDA path running on an Apple GPU.

https://github.com/Lulzx/cuda-metal/tree/main/demos/highs

I tested it in two ways:

• One builds standalone cuPDLP-C, the PDLP implementation HiGHS vendors, through a CUDA-to-Metal translation layer and diffs it against its own CPU build.
• The other builds HiGHS v1.15.1 twice from one tree, differing only in -DCUPDLP_GPU, and runs the Mittelmann LPfeas set against both. This isolates the effect of enabling the GPU path.

On my M4 Pro, with presolve disabled to isolate the PDLP loop, datt256 solves in 3.16 s against 5.17 s for the CPU build, a 1.64x speedup at identical iteration counts.

Across the three LPfeas instances I measured, the aggregate speedup is about 1.3x. graph40-40 is slower on the GPU at 0.85x, so the win depends on problem shape.

With presolve enabled the end-to-end improvement falls to roughly 1.04x, since presolve runs on the CPU in both builds and dominates the runtime.

Worst-case objective disagreement between the two builds is 4e-8 relative, and with presolve off it drops to 5e-10.

FP64 is emulated: storage remains IEEE-754 binary64, while arithmetic uses an FP32 pair with about 48 significand bits. atomicAdd(double*) goes through an address-hashed lock bank.

cuPDLP is a good fit anyway, because Ax and A'y can both be implemented as gather SpMVs and therefore need no atomic scatter.

[mocenigo]

@Lulzx , I love you! This is absolutely glorious. I assume this is better than using ZLUDA?

@jajhall , can we please make this into an optional build option until you can make your own version? In the meantime, one could try to optimise this independently! It is a starting point.

[jajhall]

Let's see what @galabovaa thinks

[galabovaa]

Sounds good, I can look into it