在大數(shù)據(jù)時代，無論是生活中各種類型的傳感器，還是用戶規(guī)模龐大的互聯(lián)網(wǎng)，它們時時刻刻都在生產(chǎn)數(shù)據(jù)。從手機上的高清照片，到醫(yī)用 CT 圖像，再到遙感衛(wèi)星拍攝的地球攝影，無論數(shù)據(jù)量如何增長，人們都期待實時獲得結(jié)果。而我們的生活之所以能夠如此便利，如此豐富多彩，背后依靠的重要技術(shù)就是分布式優(yōu)化。
撰文 | 董乾（中國科學(xué)院軟件研究所）、劉歆（中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院）
目前，市場上主流手機攝像頭的清晰度已經(jīng)達到兩千萬像素，國內(nèi)某著名手機制造商最新推出的一款環(huán)繞屏手機的清晰度更是超過了一億像素，一張照片的容量就要達到100MB。手機的電子防抖功能，手機軟件的去噪功能，這些最后都歸結(jié)為數(shù)學(xué)模型中的最優(yōu)化問題，但是無論數(shù)據(jù)量如何增大，人們對這些功能的要求都是瞬時提供結(jié)果。
醫(yī)用CT機（電子計算機斷層掃描儀）拍攝的圖像容量更是可以達到GB量級。醫(yī)學(xué)工作者想依靠斷層掃描的結(jié)果重構(gòu)人體三維結(jié)構(gòu)需要求解一個幾何問題（可歸結(jié)為最優(yōu)化問題）；想通過千千萬萬個病人的CT報告信息來總結(jié)疾病的規(guī)律，核心是統(tǒng)計問題（可歸結(jié)為最優(yōu)化問題），這些數(shù)學(xué)模型的數(shù)據(jù)量超過了一般計算機可擁有的最大內(nèi)存。
給咱們藍色的美麗地球攝影的遙感衛(wèi)星，它拍攝的照片往往是以TB計，由于衛(wèi)星自身容量、能量都有限，這些照片會在壓縮后實時傳回地球上的接收站。地面獲取數(shù)據(jù)后的解壓過程需要求解一個被稱為稀疏優(yōu)化的數(shù)學(xué)模型。而實時不斷傳回的數(shù)據(jù)往往會使得用來處理數(shù)據(jù)的計算機不堪重負。
為了可以“瞬時”處理“實時”到來的“大規(guī)?！睌?shù)據(jù)，人們想到了使用擁有多個計算單元的超級計算機來進行分布式、并行計算。下面我們就帶大家細細品味分布式優(yōu)化的前世今生。
優(yōu)化方法是人工智能的數(shù)學(xué)基礎(chǔ)
最優(yōu)化問題是應(yīng)用數(shù)學(xué)的一個分支，顧名思義，是指在一定的條件限制下，選取某種方案使得目標(biāo)達到最優(yōu)的一種方法。許多科學(xué)工程領(lǐng)域的核心問題最終都歸結(jié)為優(yōu)化問題。隨著大數(shù)據(jù)、機器學(xué)習(xí)和人工智能的迅猛發(fā)展，作為這些應(yīng)用問題的核心數(shù)學(xué)模型，最優(yōu)化問題遇到了千載難逢的發(fā)展機遇。
另一方面，隨著數(shù)據(jù)量的增大，問題復(fù)雜性提高，這給最優(yōu)化方法的研究帶來了巨大的挑戰(zhàn)。傳統(tǒng)最優(yōu)化方法的設(shè)計思想主要是通過傳統(tǒng)的串行計算實現(xiàn)的，無法與硬件的并行架構(gòu)完美兼容，這降低了傳統(tǒng)最優(yōu)化方法在具有大數(shù)據(jù)背景的應(yīng)用領(lǐng)域的可適用性，限制了求解來源于相關(guān)應(yīng)用領(lǐng)域的最優(yōu)化模型的精度和效率。為了突破這一困境，以分布式存儲為基礎(chǔ)，以并行計算為核心的分布式優(yōu)化應(yīng)運而生，這也使得最優(yōu)化方法得到了比以往任何時候都更加廣泛的應(yīng)用。
隨著信息技術(shù)的跨越式發(fā)展，近年來，人工智能迎來了一波噴涌式發(fā)展。在人工智能的這次發(fā)展浪潮中，機器學(xué)習(xí)奠定了人工智能在統(tǒng)計意義上的基礎(chǔ)和合理性，對應(yīng)的優(yōu)化算法和配套的硬件計算能力確保了人工智能在實現(xiàn)上的正確性和有效性。
換句話說，目前圖像識別、目標(biāo)檢測、語音識別等算法在準確性上所表現(xiàn)出的顯著提高離不開機器學(xué)習(xí)及其對大數(shù)據(jù)的訓(xùn)練方法。而所謂的“訓(xùn)練方法”，主要是指利用訓(xùn)練數(shù)據(jù)集找到一組參數(shù)，使得由這組參數(shù)決定的函數(shù)或映射能夠盡可能匹配訓(xùn)練數(shù)據(jù)的特征標(biāo)簽，同時能在一定范圍內(nèi)對其它數(shù)據(jù)的特征做出預(yù)測，給進一步?jīng)Q策提供參考。這里的參數(shù)估計問題，就是一個以擬合度為目標(biāo)的最優(yōu)化問題。我們根據(jù)目標(biāo)函數(shù)的函數(shù)值、梯度值等信息，設(shè)計求解最優(yōu)參數(shù)的迭代算法，因為數(shù)據(jù)量極大，所以傳統(tǒng)的最優(yōu)化方法往往不能勝任。最優(yōu)化方法同人工智能的關(guān)系可以參見圖1。
圖1 優(yōu)化方法在人工智能中的應(yīng)用和體現(xiàn)傳統(tǒng)最優(yōu)化方法受到數(shù)據(jù)爆炸的沖擊
在這個大數(shù)據(jù)時代，一方面，數(shù)據(jù)的產(chǎn)生由手動方式轉(zhuǎn)變?yōu)樽詣踊?，各種類型的傳感器被人們應(yīng)用到生產(chǎn)、生活以及科學(xué)研究中來獲取信息，數(shù)據(jù)的收集變得更加便捷經(jīng)濟；另一方面，擁有龐大數(shù)量用戶的互聯(lián)網(wǎng)無時無刻不在產(chǎn)生規(guī)模巨大的數(shù)據(jù)。以上因素的聯(lián)合作用,導(dǎo)致了數(shù)據(jù)集規(guī)模的爆炸式增長，圖2[1]展示了全球數(shù)據(jù)量的增長趨勢（1PB=1024TB，1EB=1024PB）。圖2 IDC預(yù)測的2020年全球數(shù)據(jù)量單個的存儲單元數(shù)據(jù)的分布式采集以及數(shù)據(jù)量不斷擴張進一步催生數(shù)據(jù)分布式存儲結(jié)構(gòu)的出現(xiàn)。然而，數(shù)據(jù)爆炸給傳統(tǒng)最優(yōu)化方法帶來了巨大的挑戰(zhàn)。但是，傳統(tǒng)優(yōu)化方法所處理的數(shù)據(jù)集規(guī)模較小，而且往往是串行算法。所以，對于求解目前大規(guī)模和分布式存儲的數(shù)據(jù)問題，一方面,對小規(guī)模數(shù)據(jù)集的傳統(tǒng)優(yōu)化方法并不見得對大數(shù)據(jù)問題有效；另一方面，以目前單核處理器的計算能力,數(shù)據(jù)規(guī)模的爆炸使得串行算法難以在可忍受的時間內(nèi)進行求解。現(xiàn)代計算機的并行架構(gòu)推動分布式優(yōu)化方法的發(fā)展
幸運的是，現(xiàn)代計算機的并行架構(gòu)為我們由傳統(tǒng)優(yōu)化方法轉(zhuǎn)到發(fā)展分布式優(yōu)化以求解上述問題帶來了機遇。從圖3[2]中可以發(fā)現(xiàn)，隨著晶體管電路逐漸接近性能極限，處理器（CPU）由單核逐漸過渡到多核。例如，圖4[3]中展示的Intel Xeon系列處理器中的一款CPU具有6個核心單元。圖4 Intel Xeon系列處理器架構(gòu)不僅僅是CPU，近年來快速發(fā)展的圖形處理器（GPU）也具有眾多的計算單元，從而產(chǎn)生很強大的浮點運算、并行計算性能。例如，NVIDIA公司的TURING TU102 GPU內(nèi)建4608顆CUDA核心，576顆Tensor核心,如圖5[4]所示。圖5 Turing TU102 GPU 架構(gòu)簡圖當(dāng)然，單個CPU或者GPU的計算能力依然十分有限。于是，利用多個CPU、GPU構(gòu)建的大規(guī)模集群/超級計算機，成為目前主流的計算硬件資源，比如2015年百度利用36個服務(wù)節(jié)點搭建了深度學(xué)習(xí)專用服務(wù)器Minwa[5]參加當(dāng)年的計算機視覺挑戰(zhàn)賽（ILSVRC）。更多的全球超級計算機介紹及排名可見[6]。無論是多核CPU、GPU，還是超級計算機，都是并行的硬件架構(gòu)。為充分有效利用計算資源的并行架構(gòu)，我們需要結(jié)合這一架構(gòu)特點進行并行程序的設(shè)計開發(fā)。分布式優(yōu)化與并行計算
分布式優(yōu)化方法屬于并行計算中的一類方法。與將一個問題分解成一系列離散的指令，由單個核心依次逐一執(zhí)行這些指令的串行計算不同，并行計算是同時使用多個核心來求解一個計算問題，如圖6[3]。具體地說，并行計算要首先把一個問題分解成若干個可以同時計算的子問題（部分），并將每個子問題進一步細分為一系列離散的指令；然后，采用全面控制/協(xié)調(diào)機制，利用多個核心同時執(zhí)行每個部分的指令。而分布式優(yōu)化，就是考慮如何把大任務(wù)分解成若干子任務(wù)，安排給多個核心、利用多個核心來實現(xiàn)對一個大問題的并行快速求解。目前，在算法設(shè)計上，分布式優(yōu)化可以分成代數(shù)層面的分布式優(yōu)化和模型層面的分布式優(yōu)化兩類。相比于并行計算，分布式計算的概念要更加寬泛，用在事務(wù)處理和科學(xué)計算中；而并行計算一般出現(xiàn)在科學(xué)計算中。不過兩者之間并沒有明確的分界線,我們利用“分布式”來強調(diào)數(shù)據(jù)的分布式存儲以及分布式內(nèi)存。將已有的高效串行算法中的數(shù)據(jù)矩陣（如圖7所示）和對應(yīng)的變量分塊，在代數(shù)運算層面上將可并行的運算進行并行化實現(xiàn)，這被稱為代數(shù)層面的分布式優(yōu)化。這類方法是傳統(tǒng)并行計算與已有傳統(tǒng)優(yōu)化方法的直接結(jié)合，優(yōu)點是僅需要分析已有串行算法中的可并行部分，同時對于數(shù)據(jù)并行情形容易估計實際的計算量，進而利用傳統(tǒng)并行計算中的負載均衡技術(shù)，即適當(dāng)分配每個核心的計算任務(wù)，使得核心之間分配大約相等數(shù)量的工作，以使所有核心始終保持忙碌，避免出現(xiàn)圖8中展示的多數(shù)進程空等待的情形[7]。雖然上述分布式優(yōu)化方法簡單易行，但是僅僅是基于已有的串行方法來實現(xiàn)數(shù)值計算上的并行，并不能得到新方法。另外，這種并行化的方式不僅依賴于算法的結(jié)構(gòu)，其可擴展性與求解問題的特點有密切的關(guān)系。想要突破傳統(tǒng)并行算法僅在運算層面上并行的方式，就需要根據(jù)計算機的并行架構(gòu)來設(shè)計模型層面上的分布式/并行算法。模型層面上的分布式優(yōu)化方法，其基本思想是將大規(guī)模問題分解成若干個小規(guī)模/子塊的子問題進行同時求解，實現(xiàn)算法的分布式/并行計算。與代數(shù)層面的傳統(tǒng)優(yōu)化方法并行實現(xiàn)有著本質(zhì)的不同，模型層面的分布式優(yōu)化需要指定每個計算核心需要存儲的數(shù)據(jù)、處理的變量，以及各核心間的通信等，達到從模型層面將求解大任務(wù)劃分為并發(fā)執(zhí)行的小任務(wù)的目標(biāo)，使得算法的并行結(jié)構(gòu)與硬件的并行架構(gòu)之間一致、協(xié)調(diào)，從而發(fā)揮出現(xiàn)有計算資源的強大能力。分布式優(yōu)化中的異步計算問題
對于代數(shù)層次的分布式優(yōu)化，容易通過并行數(shù)值計算方面的負載均衡技術(shù)，使得多個核心發(fā)揮出各自的計算性能，避免出現(xiàn)核心的空等待。然而，對于模型層次的分布式優(yōu)化方法，在每個迭代步中，變量的更新是在所有進程求解完子問題之后再共同進行的。這時，如果每個進程所負責(zé)子問題的求解難度不一致，或者每個進程的計算能力不均，就會出現(xiàn)有些進程已經(jīng)完成子問題的求解，從而等待其它進程完成子問題求解的情形，如圖9[8]左邊所示。由于從算法流程上子問題的求解過程無法再進行分割，所以模型層次的分布式優(yōu)化方法無法像代數(shù)層次的分布式優(yōu)化那樣直接利用并行數(shù)值計算方面的負載均衡技術(shù)。為了解決這一問題，異步計算近年來得到了廣泛關(guān)注，也即每步迭代中變量的更新只利用當(dāng)前信息，而缺少了全局同步的過程。結(jié)語
本文從分布式優(yōu)化的應(yīng)用背景和硬件基礎(chǔ)入手，介紹了分布式優(yōu)化的基本概念、主要方法和關(guān)鍵問題。不難看出，分布式優(yōu)化是以大數(shù)據(jù)為基礎(chǔ)的人工智能時代中優(yōu)化領(lǐng)域不可或缺的研究方向；分布式優(yōu)化的研究離不開背景問題和用來實現(xiàn)算法的計算機體系結(jié)構(gòu)，包括硬件環(huán)境和軟件體系；它的研究需要結(jié)合模型設(shè)計、算法設(shè)計和并行程序開發(fā)，屬于跨學(xué)科的交叉研究方向，十分具有挑戰(zhàn)性。[1] John Gantz and David Reinsel. The digital universe in 2020: Big data, bigger digital shadows, and biggest growth in the far east. IDC iView, 2007:1–16, 2012.[2] John Hennessy and David Patterson. Computer Architecture: A Quantitative Approach. Elsevier, 2011.[3] https://computing.llnl.gov/tutorials/parallel_comp/#Whatis[4] https://www.nvidia.com/content/dam/en-zz/Solutions/design-visualization/technologies/turing-architecture/NVIDIA-Turing-Architecture-Whitepaper.pdf[5] https://blog.csdn.net/lynnandwei/article/details/44411465[6] https://www.top500.org[7] https://computing.llnl.gov/tutorials/parallel_comp/#DesignLoadBalance[8] Zhimin Peng, Yangyang Xu, Ming Yan, and Wotao Yin. ARock: an algorithmic framework for asynchronous parallel coordinate updates. SIAM Journal on Scientific Computing, 38-5(2016), A2851–A2879.
本站僅提供存儲服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請
點擊舉報。
