據斯坦福大學(xué)報告顯示，自2003年以來(lái)，GPU性能提高了約7000倍，單位性能價(jià)格也提高了5600倍。GPU已經(jīng)是推動(dòng) AI 技術(shù)進(jìn)步的關(guān)鍵動(dòng)力。

H100 GPU（圖片來(lái)源：NVIDIA官網(wǎng)）

　　數周之前，芝加哥大學(xué)商學(xué)院的魯海昊教授發(fā)現，原本傳統依賴(lài)英特爾/AMD CPU（中央處理器）芯片進(jìn)行計算的數學(xué)規劃求解器（Solver，下稱(chēng)“求解器”），如今卻可以突破技術(shù)瓶頸。
　　具體來(lái)說(shuō)，魯海昊教授團隊通過(guò)實(shí)驗發(fā)現，求解器能夠通過(guò)英偉達GPU（圖形處理器）和CUDA庫函數，設計高效的數學(xué)規劃算法cuPDLP來(lái)求解超大規模問(wèn)題，并體現出了計算優(yōu)越性，其研發(fā)的cuPDLP軟件（Julia版本）也驗證了這一點(diǎn)。而該研究成果日前發(fā)表在arxiv上。
　　此后，魯海昊團隊與斯坦福大學(xué)博士、杉數科技首席科學(xué)家葛冬冬教授團隊進(jìn)行了緊密合作：在最頂級的計算設施，英偉達GPU H100多顯卡集群上，團隊對自己研發(fā)的cuPDLP-C求解軟件（C語(yǔ)言版本）進(jìn)行了實(shí)驗，驗證GPU能否實(shí)現線(xiàn)性規劃問(wèn)題求解的“彎道超車(chē)”。
　　鈦媒體App獲悉，2023年12月8日，杉數科技團隊在中國運籌學(xué)會(huì )算法軟件與應用分會(huì )成立大會(huì )上，報告了他們在英偉達H100 GPU顯卡上，成功驗證了cuPDLP-C求解超大規模線(xiàn)性規劃問(wèn)題（LP problem）的顯著(zhù)優(yōu)勢。在多個(gè)經(jīng)典測試集上，對于大規模問(wèn)題，算法體現出了不亞于傳統商業(yè)求解器的表現，并且在多個(gè)大問(wèn)題上有明顯求解優(yōu)勢。
　　例如，從求解效率來(lái)看，領(lǐng)域內著(zhù)名的測試問(wèn)題zib03，相比四年前用CPU求解的16.5個(gè)小時(shí)（用英特爾至強E7-8880 v4），如今在英偉達H100下，cuPDLP-C求解計算時(shí)間直接縮短至916秒，時(shí)間縮短了64倍。
　　相較于2009年的CPLEX，計算時(shí)間從139天到現在的15分鐘，這完全顛覆了數學(xué)規劃算法設計“只有CPU能做”的傳統認知，“降維打擊式”地提升了求解計算效率。同時(shí)，由于目前cuPDLP-C已經(jīng)在GitHub上開(kāi)源，因此整個(gè)成果也將讓更多人受益。
　　葛冬冬對鈦媒體App表示，“這件事意義重大，它將在未來(lái)3-5年對整個(gè)運籌學(xué)從科研到產(chǎn)業(yè)都會(huì )產(chǎn)生巨大改變。某種程度上，我認為它將開(kāi)啟一個(gè)運籌學(xué)科新的‘大航海時(shí)代’?！?br />　　“有四點(diǎn)對領(lǐng)域的可能沖擊吧。首先，這套算法思想推廣之后，不僅用在線(xiàn)性系統上，而且對整個(gè)連續優(yōu)化領(lǐng)域都會(huì )產(chǎn)生影響，進(jìn)而深刻影響整數規劃計算領(lǐng)域，這對應求解器應用場(chǎng)景中80%的問(wèn)題；第二，GPU相關(guān)的一階算法設計和執行相對簡(jiǎn)單，這將使得求解器社區部分模型對應的算法開(kāi)源化；而專(zhuān)業(yè)求解器以后可能跟目前許多toB的AI公司相似，在專(zhuān)業(yè)求解和基于GPU的函數定制服務(wù)方面都可以發(fā)力，帶來(lái)新的商業(yè)機會(huì )。第三，求解器會(huì )變得更加重視硬件，將需要大量適配的專(zhuān)用高精度計算顯卡，以及需要高效的庫函數實(shí)現。國內很多 AI 芯片也可以應用，形成一個(gè)軟硬一體化的生態(tài)；求解器以后的服務(wù)也更可能呈現一個(gè)軟硬一體化綁定的服務(wù)能力。第四，有鑒于求解能力限制，整個(gè)運籌學(xué)研究的核心之一其實(shí)就是如何將大問(wèn)題分解，分步驟，或者降維求解，而隨著(zhù)GPU求解算法的“暴力”求解大問(wèn)題能力劇增，可以預期運籌學(xué)領(lǐng)域，也包括相關(guān)的多個(gè)商科和工科領(lǐng)域的科研范式和產(chǎn)業(yè)形態(tài)也將隨之極大改變，甚至重塑?！备鸲嬖V鈦媒體App。
　　很顯然，通過(guò)GPU顯卡的算力加持，對已經(jīng)發(fā)展70余年、古老且嚴謹的運籌學(xué)科將會(huì )帶來(lái)革命性的沖擊。
　　計算時(shí)間縮短超過(guò)64倍，GPU芯片將加速求解更多復雜問(wèn)題
　　運籌學(xué)是近代應用數學(xué)的一個(gè)分支，主要是研究如何將生產(chǎn)、管理等事件中出現的優(yōu)化問(wèn)題加以提煉，然后利用數學(xué)方法進(jìn)行解決的學(xué)科。
　　美國物理學(xué)家，曾任加州大學(xué)柏克萊分校教授的Charles Kittel早在1947年首次提到“Operations Research”一詞，中國則在1957年由中國工程院院士許國志、清華大學(xué)基礎科部教授周華章正式定名為“運籌學(xué)”，并于1980年成立中國運籌學(xué)會(huì )（ORSC）。運籌學(xué)在全球發(fā)展至今已超過(guò)70年。
　　其中，數學(xué)規劃是將現實(shí)問(wèn)題轉化為數學(xué)模型并求解的過(guò)程。數學(xué)規劃求解器作為這一過(guò)程的核心軟件，專(zhuān)門(mén)針對多種線(xiàn)性、整數和非線(xiàn)性規劃模型進(jìn)行算法優(yōu)化。它可以被視為一個(gè)“黑盒子”系統，業(yè)界亦稱(chēng)之為算法領(lǐng)域的“芯片”。
　　求解器的重要意義在于，它能解決生活中非常復雜的應用數學(xué)問(wèn)題。例如，2018年平昌冬奧會(huì )的閉幕式上，中國接棒八分鐘展示里出現的無(wú)人倉機器人引起全球關(guān)注。但如何計算這些機器人的運行路線(xiàn)，為了確保這些機器人運行高效且避免碰撞，需要依賴(lài)最優(yōu)算法，而背后依靠的就是求解器。
　　在此之前，求解器的核心計算硬件大部分依賴(lài)于CPU（中央處理器）芯片，主要原因是CPU的通用能力可以更廣泛應用于眾多計算系統和 算法實(shí)現，而且英特爾、AMD相關(guān)軟件框架都非常齊全，特別是復雜高精度的各種矩陣運算，大大降低求解規劃成本，并提高計算效能。
　　葛冬冬指出，芯片這類(lèi)硬件是求解器底層的核心設施。
　　長(cháng)期以來(lái)，GPU采用與CPU不同的底層架構，計算核心數量、軟件和性能處理方案與CPU的底層邏輯差異極大。而國內外科研人員希望能夠通過(guò)GPU或是其他類(lèi)型芯片可實(shí)現線(xiàn)性規劃的加速計算，但多次實(shí)驗結果顯示，GPU一直無(wú)法高效求解算法中的“矩陣求逆”或者“矩陣分解“問(wèn)題，無(wú)論是計算精度（物理原因）還是并行計算，它都無(wú)法做到。
　　“未能突破的原因是，求解器的核心底層只要是這種連續優(yōu)化問(wèn)題，不管是線(xiàn)性還是非線(xiàn)性，傳統算法中都躲不開(kāi)如何高效求解‘矩陣分解’這一步。這個(gè)問(wèn)題解決不了，GPU幾千個(gè)計算單元并行加速的優(yōu)勢就無(wú)法體現?！备鸲瑢︹伱襟wApp表示，“矩陣分解”主要對應線(xiàn)性方程組求解，是計算最關(guān)鍵一步。一旦矩陣規模過(guò)大或者結構復雜，這個(gè)步驟往往會(huì )造成內存溢出或者求解時(shí)間極長(cháng)，成為求解桎梏。

杉數科技首席科學(xué)家葛冬冬教授

　　早在2016年，葛冬冬聯(lián)合幾位當年在斯坦福的博士同學(xué)，共同成立了杉數科技，研制了第一個(gè)國產(chǎn)專(zhuān)業(yè)求解器，避免受制于人。如今，作為智能決策技術(shù)服務(wù)公司，杉數科技以其自研大規模商用求解器COPT為核心引擎，打造了“計算引擎+決策技術(shù)中臺+業(yè)務(wù)場(chǎng)景”的端到端智能決策技術(shù)平臺，為消費零售、交通物流、能源電網(wǎng)、制造與供應鏈等多個(gè)行業(yè)提供數字化供應鏈解決方案，利用運籌優(yōu)化和機器學(xué)習找出更優(yōu)的決策方案，全面提升產(chǎn)業(yè)鏈和供應鏈運營(yíng)效率和效果。
　　葛冬冬此前向鈦媒體App透露，利用COPT數學(xué)優(yōu)化求解器這種優(yōu)化決策，可以使生產(chǎn)排程訂單滿(mǎn)足率提高20%，產(chǎn)能損失率降低30%，排產(chǎn)排程人工干預降低70%，非計劃維修降低15%。同時(shí)，杉數科技COPT數學(xué)優(yōu)化求解器一直在全球求解器榜單中名列前茅。
　　而此前葛冬冬團隊研發(fā)的COPT求解器系列，主要是利用CPU芯片進(jìn)行計算處理的。
　　“事實(shí)上，過(guò)去十幾年，這個(gè)領(lǐng)域內，包括我們，國內外學(xué)術(shù)界無(wú)數人，都在前赴后繼地努力，試圖回答這個(gè)問(wèn)題：GPU/CUDA架構能否對數學(xué)規劃求解器起到彎道超車(chē)的作用。此前的答案一直為‘否’?！备鸲硎?。
　　然而，2023年11月初，葛冬冬的合作伙伴，魯海昊教授在arXiv上發(fā)表了一篇論文，他們公開(kāi)的cuPDLP代碼，通過(guò)GPU硬件成功解決了線(xiàn)性規劃求解計算問(wèn)題，可用在這段Julia代碼中求解線(xiàn)性規劃。
　　葛冬冬說(shuō)：“魯老師突破這一長(cháng)期瓶頸的技術(shù)方案，是他們觀(guān)察到以前的CPU/GPU混合架構求解中，CPU/GPU之間的交互往往占用了絕大部分耗時(shí)，因此他們在此前他們與谷歌合作建立的PDLP求解器基礎上（此求解器可以很好解決GPU計算精度無(wú)法達到10^-8精度要求的限制），將整套算法搬到了GPU/CUDA架構下實(shí)現。捅破了最后一層窗戶(hù)紙！
　　此后，魯教授與葛冬冬教授領(lǐng)導的杉數COPT團隊緊密合作，提出開(kāi)源技術(shù)方案cuPDLP-C，即用一階方法在GPU上解決線(xiàn)性規劃問(wèn)題，也是Julia版本cuPDLP.jl的C語(yǔ)言加強版，算法上也做了進(jìn)一步的改善和提高。
　　與此同時(shí)，通過(guò)在目前最強的顯卡H100上的實(shí)驗發(fā)現，在運籌學(xué)最經(jīng)典的測試集MIPLIB2017的383個(gè)線(xiàn)性松弛測試問(wèn)題求解中，以10^-4 精度要求，cuPDLP-C已經(jīng)可以求解到379個(gè)問(wèn)題，而以嚴格收斂的標準10^-8 精度要求，cuPDLP-C也可以求解到369個(gè)問(wèn)題?？傮w求解時(shí)間與目前最好的商業(yè)求解器的差距也拉近到了2倍（10^-4精度）和6倍（10^-8）精度之內。在測試集那些大問(wèn)題中的差距明顯更小，在10^-4精度下甚至體現出了計算優(yōu)勢。此外，葛冬冬團隊還在多個(gè)更大規模問(wèn)題上進(jìn)行了廣泛測試，cuPDLP-C的優(yōu)勢明顯，例如zib03問(wèn)題加速了64倍，而多個(gè)更大規模的測試問(wèn)題，如在谷歌的Pagerank、某國內大企業(yè)供應鏈項目問(wèn)題、經(jīng)典的二次分配問(wèn)題（QAP）等問(wèn)題的測試上，傳統求解器都無(wú)法求解，而cuPDLP-C可以做到可行時(shí)間內求解。

　　很顯然，對于超大數學(xué)規劃問(wèn)題，在性能、計算速度、求解數量等方面，GPU都能比CPU都展現出了更好的前景。
　　杉數科技資深副總裁，技術(shù)負責人皇甫博士對鈦媒體App表示，利用GPU硬件，現在cuPDLP-C可以讓之前難以解決的大規模優(yōu)化問(wèn)題變得易于解決，推動(dòng)了模型建立的精確度和規模。以前因CPU限制而采用的非常精密復雜的一些求解技巧可能不再需要。此外，一旦GPU提速上百倍，cuPDLP-C求解優(yōu)勢可能拓展到其他連續優(yōu)化領(lǐng)域，極大加速求解過(guò)程，讓原本耗時(shí)的問(wèn)題快速得到解決，從而打開(kāi)新的應用可能性。
　　葛冬冬告訴鈦媒體App，“這很恐怖。對于運籌學(xué)來(lái)說(shuō)，這一技術(shù)意外打破了一個(gè)長(cháng)期以來(lái)的定論，即GPU在求解數學(xué)規劃問(wèn)題上沒(méi)什么加速效果。這一發(fā)現會(huì )讓整個(gè)學(xué)術(shù)和工業(yè)界感到驚訝，因為之前從未有人預料到這種情況?！?br />　　他強調，cuPDLP-C技術(shù)推翻了運籌學(xué)科長(cháng)期以來(lái)的一些共識和定式，超出人們預期，利用GPU提高了求解器的性能潛力，可能使運籌學(xué)實(shí)現從CPU到GPU計算帶來(lái)的“范式轉變”。
　　目前，cuPDLP-C技術(shù)代碼已經(jīng)開(kāi)源，相關(guān)論文也已經(jīng)公開(kāi)發(fā)表在arXiv上。
　　20年性能提高約7000倍，GPU成本過(guò)高是否將制約行業(yè)發(fā)展？
　　過(guò)去一年，以ChatGPT為代表的生成式 AI 技術(shù)風(fēng)靡全球。而作為以95%的市場(chǎng)占有率壟斷了全球 Al 訓練芯片的英偉達，成為了這輪 AI 混戰的最大贏(yíng)家，其研發(fā)的A100/A800、H100/H800等多款 AI 芯片成為 AI 熱潮中的“爆品”。
　　正如英偉達自己所說(shuō)：“GPU 已經(jīng)成為人工智能的稀有金屬，甚至是黃金，因為它們是當今生成式 AI 時(shí)代的基礎?！?br />　　從技術(shù)角度來(lái)說(shuō)，GPU優(yōu)于CPU，特別是在并行計算能力、能耗效率和CUDA生態(tài)等方面，它的高算力和可擴展性使英偉達GPU成為AI加速芯片市場(chǎng)的首選。
　　根據斯坦福大學(xué)最近發(fā)布的一項報告顯示，自2003年以來(lái)，GPU性能提高了約7000倍，單位性能價(jià)格也提高了5600倍。該報告還指出，GPU是推動(dòng) AI 技術(shù)進(jìn)步的關(guān)鍵動(dòng)力。
　　英偉達首席科學(xué)家Bill Dally也曾表示，NVIDIA GPU在過(guò)去十年中將 AI 推理性能提高了1000倍。
　　從運籌學(xué)角度來(lái)看，將CPU替換為GPU，計算能力、計算效率大幅提升。但問(wèn)題在于，國內可以買(mǎi)到的H100/H800、A100/A800的價(jià)格都已經(jīng)超過(guò)20萬(wàn)/張，再加上存儲、NVLink互連、運維成本等，相比CPU，基于GPU的求解成本將進(jìn)一步攀高。
　　那么，求解計算的基礎設施成本，是否會(huì )成為未來(lái)求解器乃至運籌學(xué)發(fā)展的重要制約因素？
　　葛冬冬對鈦媒體App表示，目前只是基于GPU架構的優(yōu)化算法的“拓荒期”。目前，他們已經(jīng)與多家國產(chǎn) GPU芯片廠(chǎng)商開(kāi)展了廣泛的測試合作，希望能夠利用國產(chǎn)算力推動(dòng)中國求解器行業(yè)發(fā)展。確實(shí)有部份國產(chǎn)GPU芯片已經(jīng)具備了跑通算法的能力，但是也確實(shí)，還需要在芯片速度和庫函數完備程度上做進(jìn)一步建設。
　　而且，他認為，杉數也已經(jīng)積極與商業(yè)伙伴開(kāi)始積極探索這一技術(shù)的落地與應用前景。目前已經(jīng)開(kāi)始在電力系統的出清調度問(wèn)題這一大規模復雜系統問(wèn)題上，與南網(wǎng)總調合作，探尋運用GPU架構的優(yōu)化求解算法來(lái)加速求解計算的研究。
　　談及開(kāi)源與商業(yè)化的話(huà)題，葛冬冬認為，把cuPDLP-C開(kāi)源可以推動(dòng)行業(yè)進(jìn)一步發(fā)展，對于商業(yè)化求解器來(lái)說(shuō)肯定會(huì )有一定沖擊，但GPU求解大規模問(wèn)題的新思路也帶來(lái)了巨大的機會(huì )，目前來(lái)看，杉數科技在核心技術(shù)、商業(yè)化等層面還有非常領(lǐng)先的市場(chǎng)競爭優(yōu)勢。
　　“新的大門(mén)已經(jīng)推開(kāi)。過(guò)去20年，大家一直在嘗試推開(kāi)，但門(mén)被‘鎖’死了?，F在等于是發(fā)現‘鎖’能打碎，門(mén)是能推開(kāi)的。這就意味著(zhù)運籌學(xué)算法又進(jìn)入了一個(gè)新的‘大航海時(shí)代’，一個(gè)堪比‘西部掘金熱’的時(shí)代。我們已經(jīng)走出（開(kāi)源）這一步。我們對自己的技術(shù)有信心，過(guò)去七年，從無(wú)到有，再到國際領(lǐng)先，杉數一直都在科研、技術(shù)和實(shí)踐應用上，是國內求解器市場(chǎng)的領(lǐng)航者。在這個(gè)經(jīng)我們的手打開(kāi)的新時(shí)代，我相信，我們是不會(huì )落后的?！备鸲硎?。