CuPDLPの高速化は難しい

 ソースを詳しく検証してみました。

GitHub - COPT-Public/cuPDLP-C: Code for solving LP on GPU using first-order methods

PDLPは、メジャーループとマイナーループをもっています。

マイナーループでは、下で示したブロックが時間を食います。

＜時間計測する場合は、DeviceSynchronoize（）で挟む＞

最初に嵌ったのは、ボトルネック部を見極めるための時間計測の誤りでした。

各ブロック間に、DeviceSynchronoizeを入れないと、時間計測が正しくありません。上図は、DeviceSynchronoizeを各ブロックにいれたものですが、トータルの時間が大きくなってしまいます。 cudaSetDeviceFlags(cudaDeviceScheduleSpin);は、行ってもこれは効いていないようで、終了を待たずに次のブロック処理に入るためのようです。

で、各ブロックを自分なりに手を入れてみたものの、速くなるどころか、オリジナル（COPT)の数分の１の速度にしか出ず、既に最適化したソースになっている、ということが分かりました。

＜double /singleは、２倍程度以下＞

次に行ったのは、double ⇒single float にすることでした。これによる効果は２倍以下でした。

<ボトルネックは、DOTとSPMV>

DOT処理部は、別に検討することにして、メジャーループ・マイナーループ共に必要なのは、SPMVです。余談ですが、PDLPの前身は、PDHGです。

Primal-Dual Hybrid Gradient Algorithm (PDHG) — odl 0.8.1 documentation

PDHGにAdptiveStepSize等を加えたのが、PDLPになります。

2501.07018

＜SPMV時間の検討＞

SPMV処理に関わる転送時間を計算してみます。

　(ＮＮＺ数ｘ３＋ＸＣｏｌｓ数x2 +YRows数x2)*sizeof(cupd_float)

これにＶＲＡＭ帯域

Ｐ１０００：８０ＧＢ／Ｓｅｃ

４０６０：２７０ＧＢ／Ｓｅｃ

を考えると、数us以下になるはずです。しかし、実際に観測されるのは、この10倍程度以上の値です。CUDAの起動時間もあるのですが、それにしてもキャッシュミス等、未だ何かあると考えざるをえません。

ということで、未だ検討の余地は、あると考えます。ＣＯＰＴが使っているＳＰＭＶは、NVidia cusparse で、これ以上に高速でないと意味がありません。

＜高速ＳＰＭＶの検討＞

サーベイ論文が参考になります。

A Systematic Literature Survey of Sparse Matrix-Vector Multiplication

具体的な実装例は、次です。

https://github.com/PAA-NCIC/AlphaSparse/tree/main

https://github.com/KaHIP/HeiStream?tab=readme-ov-file

いずれも、グラフパーティションテクニックを駆使して、キャッシュが効く程度のブロックに分割するというところは共通です。そうなると、コンパイル時間がプラスされるので、普通に考えると使えません。が、その発想は、使えると思います。

とりあえずは、上記の発想が正しいか？検証してみようと思います。