Any plan to implement GPU using Cuda and thrust?

[WayneOuyang]

simplex algo implemented by Cuda shows great potential. Any plan?

[jjhforrest]

On modern computers in the simplex method, the main problem is random accessing data in level 1, 2, 3 cache and memory, so I would think that any cpu/gpu performance gains would be limited (but still possibly worthwhile). Intel vector instructions can be activated in Clp ( -DCOIN_AVX2=n (I have only tested n=4) and -mavx2 gcc flag).  To use vector instructions, the data has to be re-organized and this has only been done in a limited way - and can not be done for the more dynamic data of the factorization. Not having NVIDIA gpus, I may have a quick look at ZLUDA to see if there is any potential. John Forrest

…

On 19/10/2021 08:39, WayneOuyang wrote: simplex algo implemented by Cuda shows great potential. Any plan? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#210>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABWJYHBOWVAFWBYIZ56BJBTUHUODTANCNFSM5GIN4VMA>. Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.

[WayneOuyang]

Just look across this paper: https://homepages.laas.fr/elbaz/PCO11.pd. it shows around 12.5 times speedup. looks fascinating!

[WayneOuyang]

Just look across this paper: https://homepages.laas.fr/elbaz/PCO11.pd. it shows around 12.5 times speedup. looks fascinating!

https://homepages.laas.fr/elbaz/PCO11.pdf this link. Sorry.

[jjhforrest]

Looking at the abstract - "Computational tests have been carried out on randomly generated instances for non-sparse LP problems. The tests show a maximum speedup of 12.5 on a GTX 260 board." The key is "non-sparse" - 99% of problems solved by simplex are sparse.  Also I suspect that few LP problems modelling a real world situtaion would be classified as "randomly generated". For non-sparse problems, I would suspect that barrier methods would be better. Given that the paper does not claim impressive speed-up for small problems and that most models have fewer (normally many fewer) than 25 non-zero elements a variable - I do not think it worth pursuing  - others may. What are the statistics for the problems you are interested in solving? Joh Forrest

[WayneOuyang]

My application is actually very sparse. This report https://on-demand.gputechconf.com/gtc/2015/webinar/gtc-express-cuda7-performance-overview.pdf shows superior performance on sparse matrix manipulation using gpu. I saw possibilities that linear programming solver can be improved by these trends, even better pivotal rules trained by machine learning model.