原创： 董乾、刘歆 返朴

在大数据时代，无论是生活中各种类型的传感器，还是用户规模庞大的互联网，它们时时刻刻都在生产数据。从手机上的高清照片，到医用 CT 图像，再到遥感卫星拍摄的地球摄影，无论数据量如何增长，人们都期待实时获得结果。而我们的生活之所以能够如此便利，如此丰富多彩，背后依靠的重要技术就是分布式优化。

撰文 | 董乾（中国科学院软件研究所）、刘歆（中国科学院数学与系统科学研究院）

目前，市场上主流手机摄像头的清晰度已经达到两千万像素，国内某著名手机制造商最新推出的一款环绕屏手机的清晰度更是超过了一亿像素，一张照片的容量就要达到100MB。手机的电子防抖功能，手机软件的去噪功能，这些最后都归结为数学模型中的最优化问题，但是无论数据量如何增大，人们对这些功能的要求都是瞬时提供结果。

医用CT机（电子计算机断层扫描仪）拍摄的图像容量更是可以达到GB量级。医学工作者想依靠断层扫描的结果重构人体三维结构需要求解一个几何问题（可归结为最优化问题）；想通过千千万万个病人的CT报告信息来总结疾病的规律，核心是统计问题（可归结为最优化问题），这些数学模型的数据量超过了一般计算机可拥有的最大内存。

给咱们蓝色的美丽地球摄影的遥感卫星，它拍摄的照片往往是以TB计，由于卫星自身容量、能量都有限，这些照片会在压缩后实时传回地球上的接收站。地面获取数据后的解压过程需要求解一个被称为稀疏优化的数学模型。而实时不断传回的数据往往会使得用来处理数据的计算机不堪重负。

为了可以“瞬时”处理“实时”到来的“大规模”数据，人们想到了使用拥有多个计算单元的超级计算机来进行分布式、并行计算。下面我们就带大家细细品味分布式优化的前世今生。

1

优化方法是人工智能的数学基础

最优化问题是应用数学的一个分支，顾名思义，是指在一定的条件限制下，选取某种方案使得目标达到最优的一种方法。许多科学工程领域的核心问题最终都归结为优化问题。随着大数据、机器学习和人工智能的迅猛发展，作为这些应用问题的核心数学模型，最优化问题遇到了千载难逢的发展机遇。

另一方面，随着数据量的增大，问题复杂性提高，这给最优化方法的研究带来了巨大的挑战。传统最优化方法的设计思想主要是通过传统的串行计算实现的，无法与硬件的并行架构完美兼容，这降低了传统最优化方法在具有大数据背景的应用领域的可适用性，限制了求解来源于相关应用领域的最优化模型的精度和效率。为了突破这一困境，以分布式存储为基础，以并行计算为核心的分布式优化应运而生，这也使得最优化方法得到了比以往任何时候都更加广泛的应用。

随着信息技术的跨越式发展，近年来，人工智能迎来了一波喷涌式发展。在人工智能的这次发展浪潮中，机器学习奠定了人工智能在统计意义上的基础和合理性，对应的优化算法和配套的硬件计算能力确保了人工智能在实现上的正确性和有效性。

换句话说，目前图像识别、目标检测、语音识别等算法在准确性上所表现出的显著提高离不开机器学习及其对大数据的训练方法。而所谓的“训练方法”，主要是指利用训练数据集找到一组参数，使得由这组参数决定的函数或映射能够尽可能匹配训练数据的特征标签，同时能在一定范围内对其它数据的特征做出预测，给进一步决策提供参考。这里的参数估计问题，就是一个以拟合度为目标的最优化问题。我们根据目标函数的函数值、梯度值等信息，设计求解最优参数的迭代算法，因为数据量极大，所以传统的最优化方法往往不能胜任。最优化方法同人工智能的关系可以参见图1。

图1 优化方法在人工智能中的应用和体现

2

传统最优化方法受到数据爆炸的冲击

在这个大数据时代，一方面，数据的产生由手动方式转变为自动化，各种类型的传感器被人们应用到生产、生活以及科学研究中来获取信息，数据的收集变得更加便捷经济；另一方面，拥有庞大数量用户的互联网无时无刻不在产生规模巨大的数据。以上因素的联合作用,导致了数据集规模的爆炸式增长，图2[1]展示了全球数据量的增长趋势（1PB=1024TB，1EB=1024PB）。

图2 IDC预测的2020年全球数据量

单个的存储单元数据的分布式采集以及数据量不断扩张进一步催生数据分布式存储结构的出现。然而，数据爆炸给传统最优化方法带来了巨大的挑战。但是，传统优化方法所处理的数据集规模较小，而且往往是串行算法。所以，对于求解目前大规模和分布式存储的数据问题，一方面,对小规模数据集的传统优化方法并不见得对大数据问题有效；另一方面，以目前单核处理器的计算能力,数据规模的爆炸使得串行算法难以在可忍受的时间内进行求解。

3

现代计算机的并行架构推动分布式优化方法的发展

图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，还是超级计算机，都是并行的硬件架构。为充分有效利用计算资源的并行架构，我们需要结合这一架构特点进行并行程序的设计开发。

4

分布式优化与并行计算

分布式优化方法属于并行计算中的一类方法。与将一个问题分解成一系列离散的指令，由单个核心依次逐一执行这些指令的串行计算不同，并行计算是同时使用多个核心来求解一个计算问题，如图6[3]。具体地说，并行计算要首先把一个问题分解成若干个可以同时计算的子问题（部分），并将每个子问题进一步细分为一系列离散的指令；然后，采用全面控制/协调机制，利用多个核心同时执行每个部分的指令。

图6-1 并行计算示意图

图6-2 串行计算示意图

而分布式优化，就是考虑如何把大任务分解成若干子任务，安排给多个核心、利用多个核心来实现对一个大问题的并行快速求解。目前，在算法设计上，分布式优化可以分成代数层面的分布式优化和模型层面的分布式优化两类。相比于并行计算，分布式计算的概念要更加宽泛，用在事务处理和科学计算中；而并行计算一般出现在科学计算中。不过两者之间并没有明确的分界线,我们利用“分布式”来强调数据的分布式存储以及分布式内存。

01）

代数层面的分布式优化

图7 数据矩阵的分块方式

将已有的高效串行算法中的数据矩阵（如图7所示）和对应的变量分块，在代数运算层面上将可并行的运算进行并行化实现，这被称为代数层面的分布式优化。这类方法是传统并行计算与已有传统优化方法的直接结合，优点是仅需要分析已有串行算法中的可并行部分，同时对于数据并行情形容易估计实际的计算量，进而利用传统并行计算中的负载均衡技术，即适当分配每个核心的计算任务，使得核心之间分配大约相等数量的工作，以使所有核心始终保持忙碌，避免出现图8中展示的多数进程空等待的情形[7]。

图8 负载不均衡的情况

02

模型层面的分布式优化

虽然上述分布式优化方法简单易行，但是仅仅是基于已有的串行方法来实现数值计算上的并行，并不能得到新方法。另外，这种并行化的方式不仅依赖于算法的结构，其可扩展性与求解问题的特点有密切的关系。想要突破传统并行算法仅在运算层面上并行的方式，就需要根据计算机的并行架构来设计模型层面上的分布式/并行算法。

模型层面上的分布式优化方法，其基本思想是将大规模问题分解成若干个小规模/子块的子问题进行同时求解，实现算法的分布式/并行计算。与代数层面的传统优化方法并行实现有着本质的不同，模型层面的分布式优化需要指定每个计算核心需要存储的数据、处理的变量，以及各核心间的通信等，达到从模型层面将求解大任务划分为并发执行的小任务的目标，使得算法的并行结构与硬件的并行架构之间一致、协调，从而发挥出现有计算资源的强大能力。

5

分布式优化中的异步计算问题

对于代数层次的分布式优化，容易通过并行数值计算方面的负载均衡技术，使得多个核心发挥出各自的计算性能，避免出现核心的空等待。然而，对于模型层次的分布式优化方法，在每个迭代步中，变量的更新是在所有进程求解完子问题之后再共同进行的。这时，如果每个进程所负责子问题的求解难度不一致，或者每个进程的计算能力不均，就会出现有些进程已经完成子问题的求解，从而等待其它进程完成子问题求解的情形，如图9[8]左边所示。

图9 多进程的异步计算示意图

由于从算法流程上子问题的求解过程无法再进行分割，所以模型层次的分布式优化方法无法像代数层次的分布式优化那样直接利用并行数值计算方面的负载均衡技术。为了解决这一问题，异步计算近年来得到了广泛关注，也即每步迭代中变量的更新只利用当前信息，而缺少了全局同步的过程。

6

结语

本文从分布式优化的应用背景和硬件基础入手，介绍了分布式优化的基本概念、主要方法和关键问题。不难看出，分布式优化是以大数据为基础的人工智能时代中优化领域不可或缺的研究方向；分布式优化的研究离不开背景问题和用来实现算法的计算机体系结构，包括硬件环境和软件体系；它的研究需要结合模型设计、算法设计和并行程序开发，属于跨学科的交叉研究方向，十分具有挑战性。

参考文献

[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.

版权说明：欢迎个人转发，任何形式的媒体或机构未经授权，不得转载和摘编。转载授权请在「返朴」微信公众号内联系后台。

阅读原文