在大數據時代，無論是生活中各種類型的傳感器，還是用戶規模龐大的網際網路，它們時時刻刻都在生產數據。從手機上的高清照片，到醫用 CT 圖像，再到遙感衛星拍攝的地球攝影，無論數據量如何增長，人們都期待實時獲得結果。而我們的生活之所以能夠如此便利，如此豐富多彩，背後依靠的重要技術就是分布式優化。
撰文 | 董干（中國科學院軟體研究所）、劉歆（中國科學院數學與系統科學研究院）
目前，市場上主流手機攝像頭的清晰度已經達到兩千萬像素，國內某著名手機製造商最新推出的一款環繞屏手機的清晰度更是超過了一億像素，一張照片的容量就要達到100MB。手機的電子防抖功能，手機軟體的去噪功能，這些最後都歸結為數學模型中的最優化問題，但是無論數據量如何增大，人們對這些功能的要求都是瞬時提供結果。
醫用CT機（電子計算機斷層掃描儀）拍攝的圖像容量更是可以達到GB量級。醫學工作者想依靠斷層掃描的結果重構人體三維結構需要求解一個幾何問題（可歸結為最優化問題）；想通過千千萬萬個病人的CT報告信息來總結疾病的規律，核心是統計問題（可歸結為最優化問題），這些數學模型的數據量超過了一般計算機可擁有的最大內存。
給咱們藍色的美麗地球攝影的遙感衛星，它拍攝的照片往往是以TB計，由於衛星自身容量、能量都有限，這些照片會在壓縮後實時傳回地球上的接收站。地面獲取數據後的解壓過程需要求解一個被稱為稀疏優化的數學模型。而實時不斷傳回的數據往往會使得用來處理數據的計算機不堪重負。
為了可以「瞬時」處理「實時」到來的「大規模」數據，人們想到了使用擁有多個計算單元的超級計算機來進行分布式、並行計算。下面我們就帶大家細細品味分布式優化的前世今生。
最優化問題是應用數學的一個分支，顧名思義，是指在一定的條件限制下，選取某種方案使得目標達到最優的一種方法。許多科學工程領域的核心問題最終都歸結為優化問題。隨著大數據、機器學習和人工智慧的迅猛發展，作為這些應用問題的核心數學模型，最優化問題遇到了千載難逢的發展機遇。
另一方面，隨著數據量的增大，問題複雜性提高，這給最優化方法的研究帶來了巨大的挑戰。傳統最優化方法的設計思想主要是通過傳統的串行計算實現的，無法與硬體的並行架構完美兼容，這降低了傳統最優化方法在具有大數據背景的應用領域的可適用性，限制了求解來源於相關應用領域的最優化模型的精度和效率。為了突破這一困境，以分布式存儲為基礎，以並行計算為核心的分布式優化應運而生，這也使得最優化方法得到了比以往任何時候都更加廣泛的應用。
隨著信息技術的跨越式發展，近年來，人工智慧迎來了一波噴涌式發展。在人工智慧的這次發展浪潮中，機器學習奠定了人工智慧在統計意義上的基礎和合理性，對應的優化算法和配套的硬體計算能力確保了人工智慧在實現上的正確性和有效性。
換句話說，目前圖像識別、目標檢測、語音識別等算法在準確性上所表現出的顯著提高離不開機器學習及其對大數據的訓練方法。而所謂的「訓練方法」，主要是指利用訓練數據集找到一組參數，使得由這組參數決定的函數或映射能夠儘可能匹配訓練數據的特徵標籤，同時能在一定範圍內對其它數據的特徵做出預測，給進一步決策提供參考。這裡的參數估計問題，就是一個以擬合度為目標的最優化問題。我們根據目標函數的函數值、梯度值等信息，設計求解最優參數的疊代算法，因為數據量極大，所以傳統的最優化方法往往不能勝任。最優化方法同人工智慧的關係可以參見圖1。
圖1 優化方法在人工智慧中的應用和體現
在這個大數據時代，一方面，數據的產生由手動方式轉變為自動化，各種類型的傳感器被人們應用到生產、生活以及科學研究中來獲取信息，數據的收集變得更加便捷經濟；另一方面，擁有龐大數量用戶的網際網路無時無刻不在產生規模巨大的數據。以上因素的聯合作用,導致了數據集規模的爆炸式增長，圖2[1]展示了全球數據量的增長趨勢（1PB=1024TB，1EB=1024PB）。
圖2 IDC預測的2020年全球數據量
單個的存儲單元數據的分布式採集以及數據量不斷擴張進一步催生數據分布式存儲結構的出現。然而，數據爆炸給傳統最優化方法帶來了巨大的挑戰。但是，傳統優化方法所處理的數據集規模較小，而且往往是串行算法。所以，對於求解目前大規模和分布式存儲的數據問題，一方面,對小規模數據集的傳統優化方法並不見得對大數據問題有效；另一方面，以目前單核處理器的計算能力,數據規模的爆炸使得串行算法難以在可忍受的時間內進行求解。
圖3 CPU發展歷史
幸運的是，現代計算機的並行架構為我們由傳統優化方法轉到發展分布式優化以求解上述問題帶來了機遇。從圖3[2]中可以發現，隨著電晶體電路逐漸接近性能極限，處理器（CPU）由單核逐漸過渡到多核。例如，圖4[3]中展示的Intel Xeon系列處理器中的一款CPU具有6個核心單元。
圖4 Intel Xeon系列處理器架構
不僅僅是CPU，近年來快速發展的圖形處理器（GPU）也具有眾多的計算單元，從而產生很強大的浮點運算、並行計算性能。例如，NVIDIA公司的TURING TU102 GPU內建4608顆CUDA核心，576顆Tensor核心,如圖5[4]所示。
圖5 Turing TU102 GPU 架構簡圖
當然，單個CPU或者GPU的計算能力依然十分有限。於是，利用多個CPU、GPU構建的大規模集群/超級計算機，成為目前主流的計算硬體資源，比如2015年百度利用36個服務節點搭建了深度學習專用伺服器Minwa[5]參加當年的計算機視覺挑戰賽（ILSVRC）。更多的全球超級計算機介紹及排名可見[6]。無論是多核CPU、GPU，還是超級計算機，都是並行的硬體架構。為充分有效利用計算資源的並行架構，我們需要結合這一架構特點進行並行程序的設計開發。
分布式優化方法屬於並行計算中的一類方法。與將一個問題分解成一系列離散的指令，由單個核心依次逐一執行這些指令的串行計算不同，並行計算是同時使用多個核心來求解一個計算問題，如圖6[3]。具體地說，並行計算要首先把一個問題分解成若干個可以同時計算的子問題（部分），並將每個子問題進一步細分為一系列離散的指令；然後，採用全面控制/協調機制，利用多個核心同時執行每個部分的指令。
圖6-1 串行計算示意圖
圖6-2 並行計算示意圖
而分布式優化，就是考慮如何把大任務分解成若干子任務，安排給多個核心、利用多個核心來實現對一個大問題的並行快速求解。目前，在算法設計上，分布式優化可以分成代數層面的分布式優化和模型層面的分布式優化兩類。相比於並行計算，分布式計算的概念要更加寬泛，用在事務處理和科學計算中；而並行計算一般出現在科學計算中。不過兩者之間並沒有明確的分界線,我們利用「分布式」來強調數據的分布式存儲以及分布式內存。
01）代數層面的分布式優化
圖7 數據矩陣的分塊方式
將已有的高效串行算法中的數據矩陣（如圖7所示）和對應的變量分塊，在代數運算層面上將可並行的運算進行並行化實現，這被稱為代數層面的分布式優化。這類方法是傳統並行計算與已有傳統優化方法的直接結合，優點是僅需要分析已有串行算法中的可並行部分，同時對於數據並行情形容易估計實際的計算量，進而利用傳統並行計算中的負載均衡技術，即適當分配每個核心的計算任務，使得核心之間分配大約相等數量的工作，以使所有核心始終保持忙碌，避免出現圖8中展示的多數進程空等待的情形[7]。
圖8 負載不均衡的情況
02） 模型層面的分布式優化
雖然上述分布式優化方法簡單易行，但是僅僅是基於已有的串行方法來實現數值計算上的並行，並不能得到新方法。另外，這種並行化的方式不僅依賴於算法的結構，其可擴展性與求解問題的特點有密切的關係。想要突破傳統並行算法僅在運算層面上並行的方式，就需要根據計算機的並行架構來設計模型層面上的分布式/並行算法。
模型層面上的分布式優化方法，其基本思想是將大規模問題分解成若干個小規模/子塊的子問題進行同時求解，實現算法的分布式/並行計算。與代數層面的傳統優化方法並行實現有著本質的不同，模型層面的分布式優化需要指定每個計算核心需要存儲的數據、處理的變量，以及各核心間的通信等，達到從模型層面將求解大任務劃分為並發執行的小任務的目標，使得算法的並行結構與硬體的並行架構之間一致、協調，從而發揮出現有計算資源的強大能力。
對於代數層次的分布式優化，容易通過並行數值計算方面的負載均衡技術，使得多個核心發揮出各自的計算性能，避免出現核心的空等待。然而，對於模型層次的分布式優化方法，在每個疊代步中，變量的更新是在所有進程求解完子問題之後再共同進行的。這時，如果每個進程所負責子問題的求解難度不一致，或者每個進程的計算能力不均，就會出現有些進程已經完成子問題的求解，從而等待其它進程完成子問題求解的情形，如圖9[8]左邊所示。
圖9 多進程的異步計算示意圖
由於從算法流程上子問題的求解過程無法再進行分割，所以模型層次的分布式優化方法無法像代數層次的分布式優化那樣直接利用並行數值計算方面的負載均衡技術。為了解決這一問題，異步計算近年來得到了廣泛關注，也即每步疊代中變量的更新只利用當前信息，而缺少了全局同步的過程。
本文從分布式優化的應用背景和硬體基礎入手，介紹了分布式優化的基本概念、主要方法和關鍵問題。不難看出，分布式優化是以大數據為基礎的人工智慧時代中優化領域不可或缺的研究方向；分布式優化的研究離不開背景問題和用來實現算法的計算機體系結構，包括硬體環境和軟體體系；它的研究需要結合模型設計、算法設計和並行程序開發，屬於跨學科的交叉研究方向，十分具有挑戰性。
參考文獻
[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.
特 別 提 示
1. 進入『返樸』微信公眾號底部菜單「精品專欄「，可查閱不同主題系列科普文章。
2. 『返樸』開通了按月檢索文章功能。關注公眾號，回復四位數組成的年份+月份，如「1903」，可獲取2019年3月的文章索引，以此類推。
版權說明：歡迎個人轉發，任何形式的媒體或機構未經授權，不得轉載和摘編。轉載授權請在「返樸」微信公眾號內聯繫後台。
《返樸》，科學家領航的好科普。國際著名物理學家文小剛與生物學家顏寧共同出任總編輯，與數十位不同領域一流學者組成的編委會一起，與你共同求索。關注《返樸》（微信號：fanpu2019）參與更多討論。二次轉載或合作請聯繫fanpusci@163.com。