生活中难以察觉的高科技：海量数据实时处理靠的是什么数学？( 三 )
代数层面的分布式优化
图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
推荐阅读
- 全球超算500强：美蝉联冠军，中国数量增加
- 全国助残日手抄报内容 全国助残日手抄报内容画法
- 儒家三礼分别是 儒家经典中的三礼是指什么
- 中国超算服务，谁主沉浮？
- 国际助残日手抄报 国际助残日手抄报画法
- 离开我你会不会好一点优秀初中作文
- 那根被踹断的烧火棍初中优秀作文
- 一言一行总关情初中优秀作文650字
- 踏入初中优秀作文
- 我的初中时代作文