【人工智能】面向机器学习的分布式并行计算关键技术及应用

吴文假人工智能科学技术奖十周年 庆祝专刊 吴文俊人工智能科技进步奖一等奖 成果名称：面向机器学习的分布式异构并行计算关键技术及应用 获奖人：唐卓、廖清、李肯立、肖国庆、曹嵘晖、谢鲲、蒋洪波、肖正、周旭、胡逸騉、宋柏森、杨建仁 完成单位：湖南大学、哈尔滨工业大学（深圳）、长沙证通云计算有限公司 唐卓 毕业于华中科技大学计算机学院，获工学博士学位。湖南大学信息科学与工程学院 岳麓学者特聘教授，博士生导师，国家超级计算长沙中心总工程师，数据中心与可信云 湖南省工程研究中心主任，湖南大学首届“东华软件学者”、长沙市大数据产业链“工 业科技特派员”，湖南省商用密码示范基地专家委员会委员，OpenStack云计算开源社 区CoreMember。.研究方向为分布式计算与云计算，研究兴趣为大数据并行处理体系 结构，分布式机器学习。专注于资源虚拟化池，OpenStacki私有云体系结构，基于 MapReduce和Spark的机器学习算法的并行化，面向数据特征的Spark和Hadoop任务 调度和体系结构优化等问题的研究。带领团队在OpenStack Q/R/S/T/U多个版本BP 贡献中均取得了全球第九，国内第三的成绩。以第一/通讯作者在IEEE/ACMTIFS、TPDS、TKDE、TCC、TSC TASL、TO1T、1OT等国内外重要刊物和会议上发表论文50余篇，获发明专利授权10余项。研发的云资源管理 软件和大数据并行处理与分析平台，已成功应用于智能制造、医疗、金融等应用领域， 提供数据存储、分析和 挖掘服务，实现科技成果转化逾干万元。 担任多个SC期刊的客座编辑，先后主持科技部国家重点研发计划课题一项，国家自然科学基金重点项目 (1项)、面上项目(2项)、国家自然科学基金应急项目(3项)、青年项目(1项)，广东省经信委项目、 产学研合作项目、中国博士后科学基金等国家及其他省部级课题十余项，同时作为任务负责人参与科技部国家 重点研发计划一项。研究成果获国家科技进步二等奖（第三）、吴文俊人工智能科技进步奖一等奖（第一）、 中国产学研合作创新成果一等奖（第一）、湖南省技术发明一等奖（第二），教育部科技进步二等奖及湖南省 自然科学奖，湖南省优秀博士后奖各一项。 918

第16卷第5期 智能系统学报 Vol.16 No.5 2021年9月 CAAI Transactions on Intelligent Systems Sep.2021 D0L:10.11992tis.202108010 面向机器学习的分布式并行计算关键技术及应用 曹嵘晖2，唐卓2，左知微2，张学东2 (1.湖南大学信息科学与工程学院，湖南长沙410082,2.国家超级计算长沙中心，湖南长沙410082) 摘要：当前机器学习等算法的计算、迭代过程日趋复杂，充足的算力是保障人工智能应用落地效果的关键。 本文首先提出一种适应倾斜数据的分布式异构环境下的任务时空调度算法，有效提升机器学习模型训练等任 务的平均效率：其次，提出分布式异构环境下高效的资源管理系统与节能调度算法，实现分布式异构环境下基 于动态预测的跨域计算资源迁移及电压/频率的动态调节，节省了系统的整体能耗：然后构建了适应于机器学 习深度学习算法迭代的分布式异构优化环境，提出了面向机器学习图迭代算法的分布式并行优化基本方法。 最后，本文研发了面向领域应用的智能分析系统，并在制造、交通、教育、医疗等领域推广应用，解决了在高效 数据采集、存储、清洗、融合与智能分析等过程中普遍存在的性能瓶颈问题。 关键词：机器学习；分布式计算；倾斜数据；任务时空调度：资源管理；节能调度：跨域资源迁移：并行优化：图迭 代算法：智能分析系统 中图分类号：TP18文献标志码：A文章编号：1673-4785(2021)05-0919-12 中文引用格式：曹蝾晖，唐卓，左知微，等.面向机器学习的分布式并行计算关键技术及应用.智能系统学报，2021,16(5)： 919-930. 英文引用格式：CAO Ronghui,.TANG Zhuo,ZUO Zhiwei,,etal.Key technologies and applications of distributed parallel comput- ing for machine learning J.CAAI transactions on intelligent systems,2021,16(5):919-930 Key technologies and applications of distributed parallel computing for machine learning CAO Ronghui,TANG Zhuo,ZUO Zhiwei,ZHANG Xuedong2 (1.College of Computer Science and Electronic Engineering,Hunan University,Changsha 410082,China;2.National Supercom- puter Center in Changsha,Changsha 410082,China) Abstract:At present,the calculation and iteration process of algorithms such as machine learning is becoming more and more complex.Sufficient computational power is the key to ensure the landing effect of artificial intelligence applica- tion.In view of this,this paper first puts forward a task space-time scheduling algorithm adapted to the distributed het- erogeneous environment of skew data,which effectively improves the average efficiency of tasks such as machine learn- ing model training.Then,the high-efficiency resource management system and energy-saving scheduling algorithm in distributed heterogeneous environment are proposed to realize the dynamic prediction based cross-domain computing re- source migration and voltage/frequency dynamic regulation in distributed heterogeneous environment,which saves the overall energy consumption of the system,and then,the distributed heterogeneous optimization environment adapted to the iteration of machine learning/deep learning algorithm is constructed,and the basic method of distributed parallel op- timization for machine learning/graph iteration algorithm is proposed.Finally,the intelligent analysis system for field- oriented applications is researched and developed,and popularized in manufacturing,transportation,education,medical and other fields,which solves the performance bottleneck problems that are common in the process of high-efficiency data collection,storage,cleaning,fusion and intelligent analysis. Keywords:machine learning;distributed computing;skew data;task space-time scheduling;resource management;en- ergy-saving scheduling;cross-domain resource migration;parallel optimization;graph iteration algorithm;intelligent analysis system 收稿日期：2021-08-11. 以超级计算、云计算为计算基础设施，以大 基金项目：国家重点研发计划项目(2018YFB1701400):国家自 然科学基金项目(92055213,61873090，L1924056, 数据分析、从海量经验数据中产生智能的人工智 62002114):金融及产业数据驱动下的智慧园区云平 台研发及产业化项目(XMHT20190205007):广东省 能2.0时代的浪潮正在袭来2。互联网、人工智 重点领域研发计划项目(XMHT20190205007)深圳 市科技计划项目(JSGG20180507183023239). 能应用的蓬勃发展，在海量数据的处理分析上面 通信作者：唐卓.E-mail:ztang@hnu.edu.cn. 临巨大的挑战：传统数据平台的并行计算能力

DOI: 10.11992/tis.202108010 面向机器学习的分布式并行计算关键技术及应用 曹嵘晖1,2，唐卓1,2，左知微1,2，张学东1,2 （1. 湖南大学 信息科学与工程学院, 湖南 长沙 410082; 2. 国家超级计算长沙中心, 湖南 长沙 410082） 摘 要：当前机器学习等算法的计算、迭代过程日趋复杂, 充足的算力是保障人工智能应用落地效果的关键。 本文首先提出一种适应倾斜数据的分布式异构环境下的任务时空调度算法，有效提升机器学习模型训练等任 务的平均效率；其次，提出分布式异构环境下高效的资源管理系统与节能调度算法，实现分布式异构环境下基 于动态预测的跨域计算资源迁移及电压/频率的动态调节，节省了系统的整体能耗；然后构建了适应于机器学 习/深度学习算法迭代的分布式异构优化环境，提出了面向机器学习/图迭代算法的分布式并行优化基本方法。 最后，本文研发了面向领域应用的智能分析系统，并在制造、交通、教育、医疗等领域推广应用，解决了在高效 数据采集、存储、清洗、融合与智能分析等过程中普遍存在的性能瓶颈问题。 关键词：机器学习；分布式计算；倾斜数据；任务时空调度；资源管理；节能调度；跨域资源迁移；并行优化；图迭 代算法；智能分析系统 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2021)05−0919−12 中文引用格式：曹嵘晖, 唐卓, 左知微, 等. 面向机器学习的分布式并行计算关键技术及应用 [J]. 智能系统学报, 2021, 16(5): 919–930. 英文引用格式：CAO Ronghui, TANG Zhuo, ZUO Zhiwei, et al. Key technologies and applications of distributed parallel comput￾ing for machine learning[J]. CAAI transactions on intelligent systems, 2021, 16(5): 919–930. Key technologies and applications of distributed parallel computing for machine learning CAO Ronghui1,2 ，TANG Zhuo1,2 ，ZUO Zhiwei1,2 ，ZHANG Xuedong1,2 (1. College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China; 2. National Supercom￾puter Center in Changsha, Changsha 410082, China) Abstract: At present, the calculation and iteration process of algorithms such as machine learning is becoming more and more complex. Sufficient computational power is the key to ensure the landing effect of artificial intelligence applica￾tion. In view of this, this paper first puts forward a task space-time scheduling algorithm adapted to the distributed het￾erogeneous environment of skew data, which effectively improves the average efficiency of tasks such as machine learn￾ing model training. Then, the high-efficiency resource management system and energy-saving scheduling algorithm in distributed heterogeneous environment are proposed to realize the dynamic prediction based cross-domain computing re￾source migration and voltage/frequency dynamic regulation in distributed heterogeneous environment, which saves the overall energy consumption of the system, and then, the distributed heterogeneous optimization environment adapted to the iteration of machine learning/deep learning algorithm is constructed, and the basic method of distributed parallel op￾timization for machine learning/graph iteration algorithm is proposed. Finally, the intelligent analysis system for field￾oriented applications is researched and developed, and popularized in manufacturing, transportation, education, medical and other fields, which solves the performance bottleneck problems that are common in the process of high-efficiency data collection, storage, cleaning, fusion and intelligent analysis. Keywords: machine learning; distributed computing; skew data; task space-time scheduling; resource management; en￾ergy-saving scheduling; cross-domain resource migration; parallel optimization; graph iteration algorithm; intelligent analysis system 以超级计算、云计算为计算基础设施，以大 数据分析、从海量经验数据中产生智能的人工智 能 2.0 时代的浪潮正在袭来[1-2]。互联网、人工智 能应用的蓬勃发展，在海量数据的处理分析上面 临巨大的挑战：传统数据平台的并行计算能力、 收稿日期：2021−08−11. 基金项目：国家重点研发计划项目（2018YFB1701400）；国家自 然科学基金项目（92055213，61873090，L1924056， 62002114）；金融及产业数据驱动下的智慧园区云平 台研发及产业化项目（XMHT20190205007）；广东省 重点领域研发计划项目（XMHT20190205007）深圳 市科技计划项目（JSGG20180507183023239）. 通信作者：唐卓. E-mail: ztang@hnu.edu.cn. 第 16 卷第 5 期 智 能 系 统 学 报 Vol.16 No.5 2021 年 9 月 CAAI Transactions on Intelligent Systems Sep. 2021

·920· 智能系统学报 第16卷 弹性存储能力以及智能化数据分析能力难以满足 行业提供数据存储、分析和挖掘的智能化云服 各行业海量数据在采集、存储和分析上对计算资 务，有效降低传统企业基于超级计算机、云服务 源的迫切需求。数据驱动的人工智能技术飞 集群等来实现大数据智能分析的使用门槛。该系 速发展，给互联网、智能制造、智慧城市等应用领 统有效地突破了数据采集、存储、压缩、分析、挖 域在数据采集、处理和分析框架上带来了巨大的 掘过程中在数据并行处理体系结构、人工智能算 机会。 法、并行编程模型方面存在的技术瓶颈，一方面 与此同时，近年来蓬勃发展的企业应用、互 有效发挥了课题组所依托的国家超级计算长沙中 联网应用在海量数据的处理分析上也面临巨大的 心作为高性能数据处理基础设施的公共服务能 挑战：传统数据平台的并行计算能力、弹性存 力，另一方面将为领域企业提供了行业数据并行 储能力以及智能化数据分析能力难以满足行业海 处理与智能分析的能力，提升了我国相关骨干企 量数据的采集、存储和分析的需求 业的创新能力。 而目前国内人工智能行业、大数据行业发展的 主要矛盾是：大多数企业看得到数据，但对数据 1 研究方案 如何采集)、存储、分析)、提供智能决策等方 本文的研究应用方案如图1所示。 面缺乏成熟有效的平台支撑，技术准入门槛高6m 智能制造智能交通 1)流数据、非结构化数据的处理和分析往往 智慧教育智慧医疗 需要动态可扩展的计算和存储能力，传统的以服 高效能数据并行处理与智能分析系统 务器集群、SQL数据库为主流架构的企业数据中 ◆研究内容四 色 机器学习/图迭代算法的分布式并行优化基本方法 心基础设施无论在硬件和软件容量上都不具备实 ●研究内容（三 时扩展的能力，很难满足企业数据处理应用对资 适应机器学习迭代的分布式异构环境构建 源的弹性需求19。 研究内谷一 2)现有的面向非结构化的数据存储架构基本 分布异构环境面向数据 高效的资源管理系统与 倾斜的任务时空调度 节能调度 上是基于NoSQL分布式文件系统，这给传统的 以SQL数据库编程为主要技能的程序员带来了 图1本文研究总体框架 困扰B2。 Fig.1 General introduction of the research 3)现有的传统企业基于数据库的分析和处理 研究应用方案具体包括： 的应用往往不具备按照数据分块进行并行处理的 1)首先针对大多数云环境中服务器内存资源 能力。而现有主流并行编程框架对于一般的企业开 平均使用率过低问题，提出了基于服务器内存预 发人员来说又难以短时间掌握。这使得以Hadoop/ 测的虚拟机动态预测部署及任务节能调度模型。 Spark、Flink等为代表的大数据并行存储和处理 在此基础上，针对Hadoop/Spark的数据处理过 框架的应用很难得到较大面积的推广和应用22。 程，设计并实现了一种面向倾斜数据Shuffle过程 4)以人工智能经典算法、机器学习模型为核 的任务调度策略：一方面通过Reduce任务放置策 心的数据挖掘框架是目前进行大数据分析的主要 略减少Spark/Hadoop集群的内部通信量，通过 手段。但对于传统企业的开发人员来说，同样面 Reducer放置算法来实现任务本地化，以减少系统 临着人工智能算法门槛太高，难于掌握的困境， 的中间数据传输量。 使得一般的软件公司很难组建面向行业数据分析 2)提出和研发了分布式异构环境下高效的资 处理和挖掘的研发团队s2 源管理系统与节能调度算法，针对各种迁移模型 课题组依托的国家超算长沙中心，作为我国 的场景，适配性能最优的计算资源迁移模型，并 在云计算、大数据及行业应用的重大战略基础设 基于OpenStack云平台实现了面向数据中心集群 施，其核心设备天河一号超级计算机与云服务器 的跨域计算资源迁移基础设施，能兼容多数云平 集群具备PB级的数据存储、并行处理和分析挖 台/数据中心虚拟机迁移算法，并支持目前流行的 掘的能力，能有效解决传统企业在面向海量数据 Ceph、KVM(kernel-based virtual machine)等存储和 处理中所遇到的计算、存储和算法瓶颈。 计算框架，实现了支持计算资源、存储资源调度 面向我国行业领域对大数据并行处理与智能 算法的独立封装和部署的多数据中心资源管理体 分析技术和服务能力提出的迫切需求，本文提出 系结构。在此基础上，针对当前云环境中服务器 了高效能数据并行处理与智能分析系统，为相关 内存资源平均使用率过低问题，提出了一种基于

弹性存储能力以及智能化数据分析能力难以满足 各行业海量数据在采集、存储和分析上对计算资 源的迫切需求[3-6]。数据驱动的人工智能技术飞 速发展，给互联网、智能制造、智慧城市等应用领 域在数据采集、处理和分析框架上带来了巨大的 机会[7-9]。 与此同时，近年来蓬勃发展的企业应用、互 联网应用在海量数据的处理分析上也面临巨大的 挑战：传统数据平台的并行计算能力[10] 、弹性存 储能力以及智能化数据分析能力难以满足行业海 量数据的采集[11] 、存储和分析的需求[12]。 而目前国内人工智能行业、大数据行业发展的 主要矛盾是：大多数企业看得到数据，但对数据 如何采集[13] 、存储[14] 、分析[15] 、提供智能决策等方 面缺乏成熟有效的平台支撑，技术准入门槛高[16-17]。 1）流数据、非结构化数据的处理和分析往往 需要动态可扩展的计算和存储能力，传统的以服 务器集群、SQL 数据库为主流架构的企业数据中 心基础设施无论在硬件和软件容量上都不具备实 时扩展的能力，很难满足企业数据处理应用对资 源的弹性需求[18-19]。 2）现有的面向非结构化的数据存储架构基本 上是基于 NoSQL 分布式文件系统，这给传统的 以 SQL 数据库编程为主要技能的程序员带来了 困扰[20-21]。 3）现有的传统企业基于数据库的分析和处理 的应用往往不具备按照数据分块进行并行处理的 能力。而现有主流并行编程框架对于一般的企业开 发人员来说又难以短时间掌握。这使得以 Hadoop/ Spark、Flink 等为代表的大数据并行存储和处理 框架的应用很难得到较大面积的推广和应用[22-24]。 4）以人工智能经典算法、机器学习模型为核 心的数据挖掘框架是目前进行大数据分析的主要 手段。但对于传统企业的开发人员来说，同样面 临着人工智能算法门槛太高，难于掌握的困境， 使得一般的软件公司很难组建面向行业数据分析 处理和挖掘的研发团队[25-26]。 课题组依托的国家超算长沙中心，作为我国 在云计算、大数据及行业应用的重大战略基础设 施，其核心设备天河一号超级计算机与云服务器 集群具备 PB 级的数据存储、并行处理和分析挖 掘的能力，能有效解决传统企业在面向海量数据 处理中所遇到的计算、存储和算法瓶颈。 面向我国行业领域对大数据并行处理与智能 分析技术和服务能力提出的迫切需求，本文提出 了高效能数据并行处理与智能分析系统，为相关 行业提供数据存储、分析和挖掘的智能化云服 务，有效降低传统企业基于超级计算机、云服务 集群等来实现大数据智能分析的使用门槛。该系 统有效地突破了数据采集、存储、压缩、分析、挖 掘过程中在数据并行处理体系结构、人工智能算 法、并行编程模型方面存在的技术瓶颈，一方面 有效发挥了课题组所依托的国家超级计算长沙中 心作为高性能数据处理基础设施的公共服务能 力，另一方面将为领域企业提供了行业数据并行 处理与智能分析的能力，提升了我国相关骨干企 业的创新能力。 1 研究方案 本文的研究应用方案如图 1 所示。 智能制造 研究内容 (一) 研究内容 (二) 研究内容 (三) 研究内容 (四) 智能交通 高效能数据并行处理与智能分析系统 机器学习/图迭代算法的分布式并行优化基本方法 适应机器学习迭代的分布式异构环境构建 分布异构环境面向数据 倾斜的任务时空调度 高效的资源管理系统与 节能调度 智慧教育 智慧医疗 图 1 本文研究总体框架 Fig. 1 General introduction of the research 研究应用方案具体包括： 1）首先针对大多数云环境中服务器内存资源 平均使用率过低问题，提出了基于服务器内存预 测的虚拟机动态预测部署及任务节能调度模型。 在此基础上，针对 Hadoop/Spark 的数据处理过 程，设计并实现了一种面向倾斜数据 Shuffle 过程 的任务调度策略：一方面通过 Reduce 任务放置策 略减少 Spark/Hadoop 集群的内部通信量，通过 Reducer 放置算法来实现任务本地化，以减少系统 的中间数据传输量。 2）提出和研发了分布式异构环境下高效的资 源管理系统与节能调度算法，针对各种迁移模型 的场景，适配性能最优的计算资源迁移模型，并 基于 OpenStack 云平台实现了面向数据中心集群 的跨域计算资源迁移基础设施，能兼容多数云平 台/数据中心虚拟机迁移算法，并支持目前流行的 Ceph、KVM(kernel-based virtual machine) 等存储和 计算框架，实现了支持计算资源、存储资源调度 算法的独立封装和部署的多数据中心资源管理体 系结构。在此基础上，针对当前云环境中服务器 内存资源平均使用率过低问题，提出了一种基于 ·920· 智 能 系 统 学 报 第 16 卷

第5期 曹嵘晖，等：面向机器学习的分布式并行计算关键技术及应用 ·921· 服务器内存预测的分配机制下的虚拟机动态预测 本文研制了分布异构环境面向数据倾斜的任务时 部署模型VM-DFS(virtual machine dynamic fore- 空调度策略，本地化任务放置算法，以及分布式并 cast scheduling)。同时针对虚拟机动态迁移问题， 行处理框架中的内部数据均匀分片方法。形成了 提出了一种基于动态预测的虚拟机迁移模型VM 面向机器学习训练任务的任务调度理论与方法。 DFM(virtual machine dynamic forecast migration), 2.1基于Spark平台的中间数据负载平衡设计 决了动态迁移过程中，如何从服务器上选择合适的 自然界中数据分布多数在理论上都是倾斜 虚拟机进行动态迁移，从而达到整体节能的目标。 的，导致倾斜的原因复杂且无法避免，因此在处 3)海量数据存储和高并发用户访问需要分布 理数据时，如果没有精心设计数据划分或任务调 式环境，但以异构众核等为主要计算部件的参数 度会极大程度地造成计算资源的浪费和系统整体 训练过程无法适应分布式系统。原生的Spark/ 性能偏差。由此可知，数据偏斜带来的负载均衡 Flink等分布式数据处理框架也无法高效适用于 问题是分布式计算平台中优化的难点和重点B1)。 深度学习的参数训练，GPU等高性能计算单元又 对于集群系统，数据对应任务，数据偏斜带来的 无法应对海量数据的分布存储和计算，且难以支 任务负载均衡问题会导致分布式系统的资源利用 撑高并发的数据访问。因此，本文针对深度学习 率低、计算执行时间长且能耗高。本文基于现有 增量迭代的运算过程，研究迭代过程中的中间共 的分布式计算框架Spark,优化Spark计算框架下 享结果在GPU内存及Cache内的存储和管理以 shuffle执行过程中bucket容器中的数据偏斜导致 及线程间的共享访问机制。针对现有流行的分布 的负载不平衡问题。本文提出了一种面向中间偏 式大数据处理框架，研究其在CPU/GPU异构环境 斜数据块的重新划分和再合并算法，通过两个重 中的体系结构扩展优化模型，突破Spark RDD等 要操作以缓解shuffle操作后reduce任务中的负载 在GPU环境中的数据结构和体系结构的重新设 不平衡问题。图2是SCID系统架构模块，该模 计，研究增量迭代过程中计算结果在GPU线程间 块包含系统中任务执行的流程和shuffle过程。 以及Spark进程间的共享模型，实现其在异构计 在这种分布式集群体系架构中，每一个小块 算环境下的缓存和持久化。 的分片数据是文件的组织单位，该分片在HDFS 4)本文针对DNN(deep neural networks) (hadoop distributed file system)中是默认的固定大 CNN(convolutional neural networks),RNN(recurrent 小。在执行一个map任务时，客户端的初始数据 neural network)等典型深度学习模型训练中的参 首先被加载到分布式文件系统(HDFS)中，每个 数迭代过程进行了深入研究，总结出增量迭代发 文件由多个大小相同的数据块组成，称为输入分 生的模型、数据特征，发现了其训练过程可以实 区。每个输入分区都被映射为一个map任务。 行增量迭代优化的条件和时机，提出了普适性的 在本文中，使用ISK×V来代表m个ma即任务的 深度学习增量迭代优化方法；针对现有Spark/ 中间结果，K和V分别代表键和值的集合。一个 Flink分布式大数据处理框架，提出了其在CPU/ cluster是某一个key值对应的对的集合 GPU异构环境中的体系结构扩展优化模型，设计 其一个子集为 并实现了一种在Spark/Flink计算容器与GPU核 Ck=(k,v∈I,k∈K,v∈V (1) 心间的高效通信方式，将传统分布式深度学习框 在图2中使用分区函数Ⅱ决定一个中间元组 架的运行效率提升数倍。在此基础上，提出了分 的分区号： Ⅱ：K→{1,2，…，pl (2) 布式环境中的并行条件随机场模型，将训练效率 因此，shuffle过程中map端输出的中间结果 提升了3.125倍：提出了一种并行维特比算法，减 被划分为P个大小不同的分区，分区号根据元组 少了计算步骤之间存在冗余的磁盘读写开销和多 的键值通过hash计算得到。因此所有key相同的 次资源申请的问题，加速比达到6.5倍。 元组都会被指向相同的分区，因为它们都属于一 分布异构环境面向数据倾斜的任 个cluster。分区是一个包含一个或多个clusters 务时空调度 的容器。因此，定义一个分区为 P()=c(k) (3) 倾斜是自然界与人类社会中数据属性客观存 kEK:(j 在，会造成集群计算节点负载不均衡、排队现象/ 基于以上定义，本文提出了一种新颖的Spark 空等待现象普遍存在，集群内部吞吐率低下，大 作业负载均衡方法，设计了一个负载均衡模块来 幅度降低了系统的实际应用效率270。鉴于此， 重新划分使之实现任务的均衡划分。该模块的执

服务器内存预测的分配机制下的虚拟机动态预测 部署模型 VM-DFS(virtual machine dynamic fore￾cast scheduling)。同时针对虚拟机动态迁移问题， 提出了一种基于动态预测的虚拟机迁移模型 VM￾DFM(virtual machine dynamic forecast migration)，解 决了动态迁移过程中，如何从服务器上选择合适的 虚拟机进行动态迁移，从而达到整体节能的目标。 3）海量数据存储和高并发用户访问需要分布 式环境，但以异构众核等为主要计算部件的参数 训练过程无法适应分布式系统。原生的 Spark/ Flink 等分布式数据处理框架也无法高效适用于 深度学习的参数训练，GPU 等高性能计算单元又 无法应对海量数据的分布存储和计算，且难以支 撑高并发的数据访问。因此，本文针对深度学习 增量迭代的运算过程，研究迭代过程中的中间共 享结果在 GPU 内存及 Cache 内的存储和管理以 及线程间的共享访问机制。针对现有流行的分布 式大数据处理框架，研究其在 CPU/GPU 异构环境 中的体系结构扩展优化模型，突破 Spark RDD 等 在 GPU 环境中的数据结构和体系结构的重新设 计，研究增量迭代过程中计算结果在 GPU 线程间 以及 Spark 进程间的共享模型，实现其在异构计 算环境下的缓存和持久化。 4）本文针对 DNN(deep neural networks)、 CNN(convolutional neural networks)、RNN(recurrent neural network) 等典型深度学习模型训练中的参 数迭代过程进行了深入研究，总结出增量迭代发 生的模型、数据特征，发现了其训练过程可以实 行增量迭代优化的条件和时机，提出了普适性的 深度学习增量迭代优化方法；针对现有 Spark/ Flink 分布式大数据处理框架，提出了其在 CPU/ GPU 异构环境中的体系结构扩展优化模型，设计 并实现了一种在 Spark/Flink 计算容器与 GPU 核 心间的高效通信方式，将传统分布式深度学习框 架的运行效率提升数倍。在此基础上，提出了分 布式环境中的并行条件随机场模型，将训练效率 提升了 3.125 倍；提出了一种并行维特比算法，减 少了计算步骤之间存在冗余的磁盘读写开销和多 次资源申请的问题，加速比达到 6.5 倍。 2 分布异构环境面向数据倾斜的任 务时空调度 倾斜是自然界与人类社会中数据属性客观存 在，会造成集群计算节点负载不均衡、排队现象/ 空等待现象普遍存在，集群内部吞吐率低下，大 幅度降低了系统的实际应用效率[27-30]。鉴于此， 本文研制了分布异构环境面向数据倾斜的任务时 空调度策略，本地化任务放置算法，以及分布式并 行处理框架中的内部数据均匀分片方法。形成了 面向机器学习训练任务的任务调度理论与方法。 2.1 基于 Spark 平台的中间数据负载平衡设计 自然界中数据分布多数在理论上都是倾斜 的，导致倾斜的原因复杂且无法避免，因此在处 理数据时，如果没有精心设计数据划分或任务调 度会极大程度地造成计算资源的浪费和系统整体 性能偏差。由此可知，数据偏斜带来的负载均衡 问题是分布式计算平台中优化的难点和重点[31-33]。 对于集群系统，数据对应任务，数据偏斜带来的 任务负载均衡问题会导致分布式系统的资源利用 率低、计算执行时间长且能耗高。本文基于现有 的分布式计算框架 Spark，优化 Spark 计算框架下 shuffle 执行过程中 bucket 容器中的数据偏斜导致 的负载不平衡问题。本文提出了一种面向中间偏 斜数据块的重新划分和再合并算法，通过两个重 要操作以缓解 shuffle 操作后 reduce 任务中的负载 不平衡问题。图 2 是 SCID 系统架构模块，该模 块包含系统中任务执行的流程和 shuffle 过程。 ⊆ 在这种分布式集群体系架构中，每一个小块 的分片数据是文件的组织单位，该分片在 HDFS (hadoop distributed file system) 中是默认的固定大 小。在执行一个 map 任务时，客户端的初始数据 首先被加载到分布式文件系统 (HDFS) 中，每个 文件由多个大小相同的数据块组成，称为输入分 区。每个输入分区都被映射为一个 map 任务。 在本文中，使用 I K × V 来代表 m 个 map 任务的 中间结果，K 和 V 分别代表键和值的集合。一个 cluster 是某一个 key 值对应的对的集合， 其一个子集为 Ck = (k, v) ∈ I, k ∈ K, v ∈ V (1) 在图 2 中使用分区函数 Π 决定一个中间元组 的分区号： Π : K → {1,2,··· , p} (2) 因此，shuffle 过程中 map 端输出的中间结果 被划分为 p 个大小不同的分区，分区号根据元组 的键值通过 hash 计算得到。因此所有 key 相同的 元组都会被指向相同的分区，因为它们都属于一 个 cluster。分区是一个包含一个或多个 clusters 的容器。因此，定义一个分区为 P(j) = ∪ k∈K:Π(k)=j C(k) (3) 基于以上定义，本文提出了一种新颖的 Spark 作业负载均衡方法，设计了一个负载均衡模块来 重新划分使之实现任务的均衡划分。该模块的执 第 5 期 曹嵘晖，等：面向机器学习的分布式并行计算关键技术及应用 ·921·

·922· 智能系统学报 第16卷 行流程如下：在Spak提交作业后，负载均衡器启 负载均衡模块在Spark基础上设计，主要包括两 动并分析作业特点给出均衡分区策略。该策略在 个重要过程，分别为数据的采样和cluster的分割 Spark作业shuffle阶段指导系统对中间结果数据 组合，其中在数据抽样阶段，重点的是对clusters 进行分割和重组，重组结果clusters到一个或多 大小的进行预测。图3代表了一种改进的工作流的 个buckers之中，从而实现均衡分区。本文提出的 Spark作业，其中的一个核心组件是负载均衡模块。 片段2 片段3 HDFS 分割T 分割3.分割n map cluster 1 cluster 2 cluster 3 cluster 4 cluster 5 cluster6 cluster 7 cluster 1 cluster4 cluster 2 cluster 3 cluster 7 cluster 5 cluster 6 分区1 分区2 分区3 bucket I bucket 2 bucket 3 图2 Spark中shuffle数据分布过程 Fig.2 Process of shuffle data distribution in Spark 数据分 抽样 split0 布策略 split 1 cluster bucket cluster split2 map-out cluster cluster bucket split 3 segement cluster split4 map-out 。。 cluster sege -ment cluster bucket splitn nap-out 分区 输入文件 图3架构与负载均衡 Fig.3 Architecture and load balancing 在cluster分割重组的过程中，第一要义是分 et大小的数据块，方便重组填充的过程。众所周 割以bucket的大小作为目标进行分割，特别是对 知，现有的分布式大数据处理平台如Hadoop/Spark 于一些超大的clusters应该尽量分成多个buck- 体系架构中在数据处理阶段缺乏对计算数据的真

行流程如下：在 Spark 提交作业后，负载均衡器启 动并分析作业特点给出均衡分区策略。该策略在 Spark 作业 shuffle 阶段指导系统对中间结果数据 进行分割和重组，重组结果 clusters 到一个或多 个 buckers 之中，从而实现均衡分区。本文提出的 负载均衡模块在 Spark 基础上设计，主要包括两 个重要过程，分别为数据的采样和 cluster 的分割 组合，其中在数据抽样阶段，重点的是对 clusters 大小的进行预测。图 3 代表了一种改进的工作流的 Spark 作业，其中的一个核心组件是负载均衡模块。 片段 1 分割 1 片段 2 片段 3 分区 1 分区 2 分区 3 分割 3 片段 n 分割 n HDFS ··· ··· map cluster 1 cluster 1 bucket 1 bucket 2 bucket 3 cluster 2 cluster 2 cluster 3 cluster 3 cluster 4 cluster 4 cluster 5 cluster 5 cluster 6 cluster 6 cluster 7 cluster 7 图 2 Spark 中 shuffle 数据分布过程 Fig. 2 Process of shuffle data distribution in Spark split 0 split 1 split 2 split 3 split 4 split n 输入文件 抽样 分区 数据分 布策略 bucket bucket bucket map-out map-out map-out cluster cluster cluster cluster cluster cluster cluster segement sege ··· -ment ··· ··· ··· 图 3 架构与负载均衡 Fig. 3 Architecture and load balancing 在 cluster 分割重组的过程中，第一要义是分 割以 bucket 的大小作为目标进行分割，特别是对 于一些超大的 clusters 应该尽量分成多个 buck￾et 大小的数据块，方便重组填充的过程。众所周 知，现有的分布式大数据处理平台如 Hadoop/Spark 体系架构中在数据处理阶段缺乏对计算数据的真 ·922· 智 能 系 统 学 报 第 16 卷

第5期 曹嵘晖，等：面向机器学习的分布式并行计算关键技术及应用 ·923· 实分布的清晰认知，抽样数据虽然不能保证真 题。目前，大数据处理主流框架中对抗数据偏斜 实地反映全体数据的分布特征，但基于其结果来 的能力都普遍较弱Bsm。普适性的分布式并行计 近似估计数据的整体分布也可以实现较好的结 算框架中通常假设数据在计算过程中是均匀分布 果。在此基础上，本文提出了一种改进分局均衡 的，这跟现实数据的分布特征背向而驰。严重的 策略来缓解现有分布式并行计算框架中的数据偏 数据偏斜程度会使集群计算系统的计算能力直线 斜问题。 下降，引发资源利用率低和任务执行过慢等问题。 22面向分布式处理的抗数据倾斜分片机制 鉴于此，本文提出了一种密钥重分配和分裂分区 随着大数据时代的到来，信息爆炸使得数据 算法(SKRSP)来解决分区倾斜，该算法同时考虑 的规模和复杂度都在增长，大数据并行计算中数 了中间数据的分区平衡和shuffle算子后的分区 据偏斜问题也日趋严重，成为一个亟需解决的问 平衡。SKRSP策略的整体架构如图4所示。 中间数据分布预测 分片策略生成及应用 ①采样 ②分布预测 采样任务0 ③分片策略生成 分片0 采样数据 e。。 基于hash的 采样任务1 key分配策略 N 分片0 分片1 KRHP 是否 排序 采样任务m-1 KSHP 分片m-1 带权重的key 分片1 分片边界数据 年年卡中年卡年年年专年年年专华年出 ④ 分片策略应用 ma即任务0 reduce任务0 分片m1 分片0 segement 0 reduce分片O segement 1 map任务1 k2 reduce任务1 分片1 egement 1 执行shuf印le-op reduce分片1 的RDD map任务m-】 中间数据 segement 0 reduce任务m-l1 分片m-1 egement广 reduce分片m-1 图4 SKRSP整体架构 Fig.4 General introduction to SKRSP SKRSP整体框架包含了两个主要部分：中间 策略。对于这些属于排序类的应用程序，提出了 数据分布预测、分片策略的生成与应用。 KSRP算法来确定加权边界。最终的key重新分 l)为了避免reduce任务之间的数据偏斜，需 配策略可以通过其他KRHP算法获得。具体来 要在shuffle阶段之前估计中间数据的key分布。 说，采样中间数据key的分布是系统用于决策分 因此，必须在常规作业之前输人地图任务时启动 区策略的依据。一方面，如果操作结果无需排序， 先前的示例作业。本文在不同的分区上并行实现 基于hash的key cluster分片方法将被采用；另一 了基于步骤的拒绝采样算法。所有的样本和对应方面，如果操作结果是需要进行排序，基于range 的采样率都是从不同的map splits中收集的，它们 的key cluster分片策略将被采用。因此，就得到 构成了通过采样率计算每个k©y的权重的输入。在 了不同的分片策略。在shuf的e写数据的阶段，在 此基础上，可以估计中间数据的一般ky分布。 上一个步骤中获得的分片策略会指导每个对其进行分区计算，从而获得其reduce端 作业的具体应用场景，采用不同的方法生成分配 的分区D号。该D号就是每个map任务计算后

实分布的清晰认知[34] ，抽样数据虽然不能保证真 实地反映全体数据的分布特征，但基于其结果来 近似估计数据的整体分布也可以实现较好的结 果。在此基础上，本文提出了一种改进分局均衡 策略来缓解现有分布式并行计算框架中的数据偏 斜问题。 2.2 面向分布式处理的抗数据倾斜分片机制 随着大数据时代的到来，信息爆炸使得数据 的规模和复杂度都在增长，大数据并行计算中数 据偏斜问题也日趋严重，成为一个亟需解决的问 题。目前，大数据处理主流框架中对抗数据偏斜 的能力都普遍较弱 [35-37]。普适性的分布式并行计 算框架中通常假设数据在计算过程中是均匀分布 的，这跟现实数据的分布特征背向而驰。严重的 数据偏斜程度会使集群计算系统的计算能力直线 下降，引发资源利用率低和任务执行过慢等问题。 鉴于此，本文提出了一种密钥重分配和分裂分区 算法（SKRSP）来解决分区倾斜，该算法同时考虑 了中间数据的分区平衡和 shuffle 算子后的分区 平衡。SKRSP 策略的整体架构如图 4 所示。 分片 0 分片 0 分片 1 分片 1 分片 m−1 分片 m−1 分片 0 分片 1 分片 m−1 reduce 分片 0 reduce 分片 1 reduce 分片 m−1 执行 shuffle-op 的 RDD 中间数据分布预测 分片策略生成及应用 基于 hash 的 key 分配策略 带权重的 key 分片边界数据 采样任务 0 采样任务 1 采样任务 m−1 采样数据 1 采样 2 分布预测 3 分片策略生成 4 分片策略应用 map 任务 0 map 任务 1 map 任务 m−1 reduce 任务 0 reduce 任务 1 reduce 任务 m−1 segement 0 segement 1 segement r−1 segement 0 segement r−1 中间数据 KRHP KSHP N Y 是否 排序 ··· ··· ··· ··· ··· ··· ··· ··· ··· 图 4 SKRSP 整体架构 Fig. 4 General introduction to SKRSP SKRSP 整体框架包含了两个主要部分：中间 数据分布预测、分片策略的生成与应用。 1）为了避免 reduce 任务之间的数据偏斜，需 要在 shuffle 阶段之前估计中间数据的 key 分布。 因此，必须在常规作业之前输入地图任务时启动 先前的示例作业。本文在不同的分区上并行实现 了基于步骤的拒绝采样算法。所有的样本和对应 的采样率都是从不同的 map splits 中收集的，它们 构成了通过采样率计算每个 key 的权重的输入。在 此基础上，可以估计中间数据的一般 key 分布。 2）分片策略的生成与应用。本系统根据 Spark 作业的具体应用场景，采用不同的方法生成分配 策略。对于这些属于排序类的应用程序，提出了 KSRP 算法来确定加权边界。最终的 key 重新分 配策略可以通过其他 KRHP 算法获得。具体来 说，采样中间数据 key 的分布是系统用于决策分 区策略的依据。一方面，如果操作结果无需排序， 基于 hash 的 key cluster 分片方法将被采用；另一 方面，如果操作结果是需要进行排序，基于 range 的 key cluster 分片策略将被采用。因此，就得到 了不同的分片策略。在 shuffle 写数据的阶段，在 上一个步骤中获得的分片策略会指导每个对其进行分区计算，从而获得其 reduce 端 的分区 ID 号。该 ID 号就是每个 map 任务计算后 第 5 期 曹嵘晖，等：面向机器学习的分布式并行计算关键技术及应用 ·923·

·924· 智能系统学报 第16卷 的中间输出结果，需要写到磁盘的顺序位置。最 将被一个对应的reduce任务处理。经过这样的过 终这些中间结果生成一个数据文件和索引文件。 程，上一步生成的分片策略便应用到了Shuffle过 在数据文件中，一个数据段(segement)是一块索 程中实际的数据划分中来。 引号相同的区域。接下来进入shuffle的读阶段， 在实际的Spark集群上对SKRSP算法进行了 每个reduce任务将从各个map任务执行的节点上 评估，并与其他算法进行了对比实验如表1。在 根据索引文件拉取数据。也就是说，具有相同re 采样率为3.3%的情况下，SKRSP算法明显优于 duce索引号的键值对数据组成一个reduce分区， 其他采样方法，且误差小于LIBRA,仅为70。 表1 采样精确度实验结果 Table 1 Experimental results of sampling accuracy 采样方法 采样率% 均匀分区5000keys 均匀分区50000keys 倾斜分区5000keys 倾斜分50000keys SKRSP 3.30 1311 296 581 207 Range采样器 3.30 1622 460 883 245 随机采样器 3.30 1897 361 743 218 SKRSP 20 288 110 232 78 3 分布式异构环境下高效的资源管 Cascading open stack 理系统与节能调度 Cascading manager B 3.1分布式异构环境下的计算资源跨域迁移 Nova 数据中心等分布式异构基础设施已经成为现 API-GW 代各行各业的基础建设，从为中小型公司提供业 ① 6 务支撑数据机房，到大型IT公司的IDC(internet Nova Nova data center)。然而服务中断、资源属性等特性 VM VM VM VM 对资源跨域迁移的需求越来越大。结合项目组提 Cinder Cinder 出的多云资源级联平台，本文基于OpenStack实 Keystone Shared keystone Keystone 现了一个面向数据中心集群的跨域计算资源迁移 Pod 1 Pod 2 基础设施，实现了多云环境下VM(virtual machine) 跨域迁移，有效地满足一种或多种用户、资源需 图5跨域VM迁移机制 Fig.5 Cross-domain VM migration mechanism 求，并在此基础上实现了支持计算资源、存储资 源调度算法的独立封装和部署的多数据中心资源 该架构在真实多云环境下进行了实验，实验 管理体系结构。该结构如图5所示。 结果证明了该架构的有效性和高效性，提升跨域 如图5所示，如若需要将VM从Pod1迁移到 资源的使用效率。此外，在多云平台上的用户使 多元环境下的Pod2下，首先Pod1的计算组件 用过程中，该架构也能有效地降低因虚拟机突发 Nova需要向顶层OpenStack云平台发送迁移消 迁移带来的用户宕机体验率。 息，顶层OpenStack收到该消息后交予Nova API-. 3.2基于服务器内存预测的虚拟机分配机制 GW处理，并发送给MSG.Bus,为发送给Cascad- 通过对云环境下虚拟机部署方式的研究，针 ing Manager其他模块做准备。随后，Nova API-- 对现有云服务器中的内存使用率低导致各类资源 GW通过消息队列将该迁移信息发送给数据库， 平均使用率过低04)，本文提出一种新型虚拟机 请求修改资源路由表中相关资源信息。同时，也 部署机制VM-DFS,基于云服务器内存预测下的 通过异步作业机制给迁移的目的云实例发送迁移 虚拟机动态部署模型。该模型考虑虚拟机运行过 消息。VM迁移的目的云实例接到该请求后发送 程对云服务器内存消耗的动态变化，结合虚拟机 给Pod2的计算组件Nova。在多云架构顶层为 部署已有的研究方案，将部署过程构建为某一类 迁移做资源管理信息修改时，底层的两个云实例 装箱模型，在此基础上，再结合FFD(first-fit decreasing) 之间完成虚拟机冷迁移所需镜像文件和内存数据 算法对虚拟机部署算法近似求解；与此同时，虚 的传输。 拟机部署过程中结合内容等资源的预测机制，通

的中间输出结果，需要写到磁盘的顺序位置。最 终这些中间结果生成一个数据文件和索引文件。 在数据文件中，一个数据段（segement）是一块索 引号相同的区域。接下来进入 shuffle 的读阶段， 每个 reduce 任务将从各个 map 任务执行的节点上 根据索引文件拉取数据。也就是说，具有相同 re￾duce 索引号的键值对数据组成一个 reduce 分区， 将被一个对应的 reduce 任务处理。经过这样的过 程，上一步生成的分片策略便应用到了 Shuffle 过 程中实际的数据划分中来。 在实际的 Spark 集群上对 SKRSP 算法进行了 评估，并与其他算法进行了对比实验如表 1。在 采样率为 3.3% 的情况下，SKRSP 算法明显优于 其他采样方法，且误差小于 LIBRA，仅为 70。 表 1 采样精确度实验结果 Table 1 Experimental results of sampling accuracy 采样方法 采样率/% 均匀分区5 000 keys 均匀分区50 000 keys 倾斜分区5 000 keys 倾斜分50 000 keys SKRSP 3.30 1 311 296 581 207 Range采样器 3.30 1 622 460 883 245 随机采样器 3.30 1 897 361 743 218 SKRSP 20 288 110 232 78 3 分布式异构环境下高效的资源管 理系统与节能调度 3.1 分布式异构环境下的计算资源跨域迁移 数据中心等分布式异构基础设施已经成为现 代各行各业的基础建设，从为中小型公司提供业 务支撑数据机房，到大型 IT 公司的 IDC(internet data center)[38-39]。然而服务中断、资源属性等特性 对资源跨域迁移的需求越来越大。结合项目组提 出的多云资源级联平台，本文基于 OpenStack 实 现了一个面向数据中心集群的跨域计算资源迁移 基础设施，实现了多云环境下 VM(virtual machine) 跨域迁移，有效地满足一种或多种用户、资源需 求，并在此基础上实现了支持计算资源、存储资 源调度算法的独立封装和部署的多数据中心资源 管理体系结构。该结构如图 5 所示。 如图 5 所示，如若需要将 VM 从 Pod 1 迁移到 多元环境下的 Pod 2 下，首先 Pod 1 的计算组件 Nova 需要向顶层 OpenStack 云平台发送迁移消 息，顶层 OpenStack 收到该消息后交予 Nova API￾GW 处理，并发送给 MSG.Bus ，为发送给 Cascad￾ing Manager 其他模块做准备。随后，Nova API￾GW 通过消息队列将该迁移信息发送给数据库， 请求修改资源路由表中相关资源信息。同时，也 通过异步作业机制给迁移的目的云实例发送迁移 消息。VM 迁移的目的云实例接到该请求后发送 给 Pod 2 的计算组件 Nova 。在多云架构顶层为 迁移做资源管理信息修改时，底层的两个云实例 之间完成虚拟机冷迁移所需镜像文件和内存数据 的传输。 Cascading open stack Cascading manager DB VM Nova Cinder Keystone Pod 1 Pod 2 Shared keystone VM VM Nova Cinder Keystone VM MSG.Bus Xjob Nova API-GW 1 2 6 3 4 5 ··· 图 5 跨域 VM 迁移机制 Fig. 5 Cross-domain VM migration mechanism 该架构在真实多云环境下进行了实验，实验 结果证明了该架构的有效性和高效性，提升跨域 资源的使用效率。此外，在多云平台上的用户使 用过程中，该架构也能有效地降低因虚拟机突发 迁移带来的用户宕机体验率。 3.2 基于服务器内存预测的虚拟机分配机制 通过对云环境下虚拟机部署方式的研究，针 对现有云服务器中的内存使用率低导致各类资源 平均使用率过低[40-41] ，本文提出一种新型虚拟机 部署机制 VM-DFS，基于云服务器内存预测下的 虚拟机动态部署模型。该模型考虑虚拟机运行过 程对云服务器内存消耗的动态变化，结合虚拟机 部署已有的研究方案，将部署过程构建为某一类 装箱模型，在此基础上，再结合 FFD(first-fit decreasing) 算法对虚拟机部署算法近似求解；与此同时，虚 拟机部署过程中结合内容等资源的预测机制，通 ·924· 智 能 系 统 学 报 第 16 卷

第5期 曹嵘晖，等：面向机器学习的分布式并行计算关键技术及应用 ·925· 过对各个虚拟机历史内存消耗数据的统计分析， Flink计算容器与GPU核心间的高效通信方式， 使用基于时间序列的自回归二阶模型进行内存动 在兼具各个节点GPU/MIC众核计算能力的同时， 态预测。在满足各个虚拟机对内存SLA(service 利用分布式组件间的通信协议完成了各个服务器 level agreement)要求的前提下减少服务器的启动 节点的协同运算。 数量。并对每个服务器的内存分配设置一个阈值 4.2分布式异构CPU/GPU集群体系结构的优化 Lm,设置平衡因子r作为超过阈值的过载比例。 设计方法 实验结果显示，VM-DFS算法能够在满足SLA要 考虑到目前Spark分布式框架无法有效利用 求的前提下，提高服务器内存资源使用率。 计算节点上的多GPU,本文提出了MGSpark系 在此基础上，为确保云环境中内存资源的Q0s 统：一个CPU-GPU分布式异构环境下多GPU工 要求，当物理服务器内存消耗值时，需要进行虚 作负载均衡的计算框架。MGSpark系统能有效地 拟机的动态迁移。鉴于此，本文提出一种新型虚 将GPUs融入到Spark框架中，充分挖掘计算节点 拟机动态迁移模型(virtual machine dynamic fore- 上的多GPU的计算能力，使集群中的GPUs工作 cast migration,VM-DFM),该算法解决了在虚拟 负载达到均衡，如图6所示。 机的动态迁移过程中，如何从“热点”服务器上待 Worker 0 迁移虚拟机列表中选择合适的虚拟机进行动态 Excutor 迁移。 Cache Client Task Task 4适应于机器学习/深度学习算法迭 MGSpark application MGScheduler ased on the HRDD 代的分布式异构环境构建 CPUs CPUs Master Shuffle parkContext 针对机器学习/深度学习算法迭代过程中的 Worker 0 GScbeduler Excutor 算力、架构瓶颈及计算效率低等问题24。提出 Cache 了普适性的深度学习增量迭代优化方法；针对现 Task Task 有Spark/Flink分布式大数据处理框架，在此基础 GScheduler 上提出了其在CPU/GPU异构环境中的体系结构 CPUs CPUs 扩展优化模型，设计并实现了一种在Spark/Flink 图6 MGSpark系统架构 计算容器与GPU核心间的高效通信方式，解决了 Fig.6 System architecture of MGSpark 分布式异构环境中的计算效率问题。 本文建立了与原有Spark RDD(resilient distrib- 4.1 机器学习/深度学习增量迭代优化方法 uted datasets)编程模型相兼容的GPU加速的编程 众所周知，算力一直以来是人工智能发展的 模型，使编程人员创建GPUs加速的Spark应用程 最大瓶颈。以异构众核等高性能处理器为主要计 序更加简便。为了优化主机端和设备端的数据通 算部件的机器学习/深度学习参数训练过程并不 信，MGSpark提出了一个多GPU环境下的异步 适用于分布式系统，传统的机器学习算法因其无 JVM-GPU数据传输方案。 法保证数据分片分开训练是否能与整体集中训练 MGSpark架构与Spark运行时相兼。因此 结果保持一致，需要在分布环境下进行并行优化 Spark的任务调度和错误恢复机制被保留下来。 与适应性改进。 Standalone模式下的MGSpark系统框架如图7所 鉴于此，本文针对分布式机器学习体系结构 示，保留着Spark运行时的所有组件(DAGSched- 中的并行优化问题，提出了机器学习/深度学习增 uler、TaskScheduler、excutor)。作者还扩展了RDD 量迭代优化模型及其分布式异构CPU/GPU集群 模型来融合GPU和Spark的计算模型，以方便编 体系结构的优化设计方法。在此基础上，针对DNNW 程人员使用扩展的RDD编程模型来创建MGS- CNN/RNN等典型深度学习模型训练中的参数迭 park应用程序，并使用GPUs进行加速。新增加 代过程，通过总结增量迭代发生的模型、数据特 的系统组件是MGTaskScheduler,.它驻留在每个 征，揭示了其训练过程可以实行增量迭代优化的 Worker节点上。MGTaskScheduler负责将excutor 条件和时机等客观规律，提出了普适性的深度学 上的Tasks卸载到节点上的GPUs上执行，进行 习增量迭代优化方法；提出并实现了一种在Spark/ 多GPUs工作负载均衡调度

过对各个虚拟机历史内存消耗数据的统计分析， 使用基于时间序列的自回归二阶模型进行内存动 态预测。在满足各个虚拟机对内存 SLA (service level agreement) 要求的前提下减少服务器的启动 数量。并对每个服务器的内存分配设置一个阈值 Lm ，设置平衡因子 r 作为超过阈值的过载比例。 实验结果显示，VM-DFS 算法能够在满足 SLA 要 求的前提下，提高服务器内存资源使用率。 在此基础上，为确保云环境中内存资源的 Qos 要求，当物理服务器内存消耗 r 值时，需要进行虚 拟机的动态迁移。鉴于此，本文提出一种新型虚 拟机动态迁移模型 (virtual machine dynamic fore￾cast migration, VM-DFM)，该算法解决了在虚拟 机的动态迁移过程中，如何从“热点”服务器上待 迁移虚拟机列表中选择合适的虚拟机进行动态 迁移。 4 适应于机器学习/深度学习算法迭 代的分布式异构环境构建 针对机器学习/深度学习算法迭代过程中的 算力、架构瓶颈及计算效率低等问题[42-43]。提出 了普适性的深度学习增量迭代优化方法；针对现 有 Spark/Flink 分布式大数据处理框架，在此基础 上提出了其在 CPU/GPU 异构环境中的体系结构 扩展优化模型，设计并实现了一种在 Spark/Flink 计算容器与 GPU 核心间的高效通信方式，解决了 分布式异构环境中的计算效率问题。 4.1 机器学习/深度学习增量迭代优化方法 众所周知，算力一直以来是人工智能发展的 最大瓶颈。以异构众核等高性能处理器为主要计 算部件的机器学习/深度学习参数训练过程并不 适用于分布式系统，传统的机器学习算法因其无 法保证数据分片分开训练是否能与整体集中训练 结果保持一致，需要在分布环境下进行并行优化 与适应性改进。 鉴于此，本文针对分布式机器学习体系结构 中的并行优化问题，提出了机器学习/深度学习增 量迭代优化模型及其分布式异构 CPU/GPU 集群 体系结构的优化设计方法。在此基础上，针对 DNN/ CNN/RNN 等典型深度学习模型训练中的参数迭 代过程，通过总结增量迭代发生的模型、数据特 征，揭示了其训练过程可以实行增量迭代优化的 条件和时机等客观规律，提出了普适性的深度学 习增量迭代优化方法；提出并实现了一种在 Spark/ Flink 计算容器与 GPU 核心间的高效通信方式， 在兼具各个节点 GPU/MIC 众核计算能力的同时， 利用分布式组件间的通信协议完成了各个服务器 节点的协同运算。 4.2 分布式异构 CPU/GPU 集群体系结构的优化 设计方法 考虑到目前 Spark 分布式框架无法有效利用 计算节点上的多 GPU[42] ，本文提出了 MGSpark 系 统：一个 CPU-GPU 分布式异构环境下多 GPU 工 作负载均衡的计算框架。MGSpark 系统能有效地 将 GPUs 融入到 Spark 框架中，充分挖掘计算节点 上的多 GPU 的计算能力，使集群中的 GPUs 工作 负载达到均衡，如图 6 所示。 Client Master Worker_0 Excutor Cache Task Task MGScheduler CPUs CPUs Worker_0 Excutor Cache Task Task MGScheduler CPUs CPUs Shuffle MGSpark application based on the HRDD SparkContext DAGScheduler TaskScheduler 图 6 MGSpark 系统架构 Fig. 6 System architecture of MGSpark 本文建立了与原有 Spark RDD(resilient distrib￾uted datasets) 编程模型相兼容的 GPU 加速的编程 模型，使编程人员创建 GPUs加速的 Spark 应用程 序更加简便。为了优化主机端和设备端的数据通 信，MGSpark 提出了一个多 GPU 环境下的异步 JVM-GPU 数据传输方案。 MGSpark 架构与 Spark 运行时相兼。因此 Spark 的任务调度和错误恢复机制被保留下来。 Standalone 模式下的 MGSpark 系统框架如图 7 所 示，保留着 Spark 运行时的所有组件（DAGSched￾uler、TaskScheduler、 excutor）。作者还扩展了 RDD 模型来融合 GPU 和 Spark 的计算模型，以方便编 程人员使用扩展的 RDD 编程模型来创建 MGS￾park 应用程序，并使用 GPUs 进行加速。新增加 的系统组件是 MGTaskScheduler，它驻留在每个 Worker 节点上。MGTaskScheduler 负责将 excutor 上的 Tasks 卸载到节点上的 GPUs 上执行，进行 多 GPUs 工作负载均衡调度。 第 5 期 曹嵘晖，等：面向机器学习的分布式并行计算关键技术及应用 ·925·

·926· 智能系统学报 第16卷 TNS2 TGR1.1 TGR1.2 TGR1.3 TGR1.m TNS2 TGR2.1 TGR2.2 TGR2.3 TGR2.m TGR TGR TGR 2.ml 2.m2 TNS3.1 TNS3.2 TNS3.3 TGR3.1 TGR3.2 TGR3.m TNS4.I TNS4.2 TNS4.3 TNS4.4 TNS4.5 TNS4.6 TNS4.7 图7PRF决策树模型训练过程的任务DAG模型 Fig.7 Task DAG model of PRF decision tree model training process 使用扩展的RDD编程模型所创建的MGS-执行，会造成计算节点上各个GPU之间的工作负 park应用程序在Client节点上被提交。Master为 载不均衡。为了能平衡计算节点上各个GPU之 应用程序分配所需的集群资源，主要包括内存和 间的工作负载，本文提出了一个任务分解执行模 CPU资源。一个DAG graph根据RDDs之间的依 型。该模型主要包括两个部分：自动数据切片机 赖关系被创建。DAG-Schedule将DAG图划分为 制和自动任务分解机制。 多个有先后顺序的stage。.每个stage划分为一系 5面向机器学习/图迭代算法的分布 列可以并发的Tasks通过Task-Scheduler。Task- 式并行优化 Scheduler根据集群每个节点资源状态调度Tasks 到workers的进程上执行。与源生Spark框架不 针对机器学习/图迭代算法过程中的分布式 同（在Spark中GPU不能被识别和使用，Tasks必 并行优化中的计算效率等问题434。提出了面向 须被调度到CPU),MGspark Tasks可以将计算与 机器学习算法的分布式并行优化模型、分布式环 将要处理的数据卸载到GPUs上去进行加速通过 境中的并行条件随机场模型、并行维特比算法 MGTaskScheduler组件。 基于冗余距离消除和极端点优化的数据聚类方 在此基础上，本文提出了基于CUDA流的异 法。解决了机器学习分布式优化的问题，突破了 构任务执行模型(MGMS),可以充分平衡GPUs工 大规模高效能数据并行处理系统的算力瓶颈。 作负载。并且将MGMS模型整合到最新版本的 5.1分布式环境中的并行条件随机场模型 Spark分布式计算框架中开发了MGSpark计算 条件随机场(conditional random fields)是一种 框架。 概率图模型s46。它是一种机器学习算法，需要 Task是Spark的最小调度和并发执行单元， 多次迭代。条件随机场在标记或分析序列数据方 每个Task需要顺序处理一个Partition的数据量。 面发挥了重要作用，并取得了显著的效果。条件随 但是由于各个Partition之间的数据量不一样，特 机场结合了最大熵模型和隐马尔可夫模型的特点， 别是执行完shuffle类的算子，partition之间的数 但隐马尔可夫模型不能直接看到其状态，不能应 据量差别更为明显。为了利用GPUs进行加速， 用复杂的特征。然而，根据这一思想，条件随机 将Tasks卸载到设备端形成GTasks。如果将 场模型可以很好地应用于依赖长距离和使用重叠 GTask作为一个最小执行单元分配设备资源：设 特征的特征。同时，条件随机场可以解决其他判 备内存资源和CUDA流资源，调度到GPUs上去 别模型中的标注偏差问题。为此，本文提出了一

stage1 stage2 stage3 TNS2 TGR1.1 TGR2.1 TGR2.2 TGR2.3 TGR2.m TGR 2.21 TGR3.1 TGR3.2 TGR3.m TGR 2.22 TGR 2.23 TGR 2.31 TGR 2.32 TGR 2.33 TGR 2.m1 TGR 2.m2 TGR1.2 TGR1.3 TGR1.m TNS2 TNS3.1 TNS4.1 TNS4.2 TNS4.3 TNS4.4 TNS4.5 TNS4.6 TNS4.7 TNS3.2 TNS3.3 ··· ··· ··· 图 7 PRF 决策树模型训练过程的任务 DAG 模型 Fig. 7 Task DAG model of PRF decision tree model training process 使用扩展的 RDD 编程模型所创建的 MGS￾park 应用程序在 Client 节点上被提交。Master 为 应用程序分配所需的集群资源，主要包括内存和 CPU 资源。一个 DAG graph 根据 RDDs 之间的依 赖关系被创建。DAG-Schedule 将 DAG 图划分为 多个有先后顺序的 stage。每个 stage 划分为一系 列可以并发的 Tasks 通过 Task-Scheduler。Task￾Scheduler 根据集群每个节点资源状态调度 Tasks 到 workers 的进程上执行。与源生 Spark 框架不 同（在 Spark 中 GPU 不能被识别和使用，Tasks 必 须被调度到 CPU），MGspark Tasks 可以将计算与 将要处理的数据卸载到 GPUs 上去进行加速通过 MGTaskScheduler 组件。 在此基础上，本文提出了基于 CUDA 流的异 构任务执行模型 (MGMS)，可以充分平衡 GPUs 工 作负载。并且将 MGMS 模型整合到最新版本的 Spark 分布式计算框架中开发了 MGSpark 计算 框架。 Task 是 Spark 的最小调度和并发执行单元， 每个 Task 需要顺序处理一个 Partition 的数据量。 但是由于各个 Partition 之间的数据量不一样，特 别是执行完 shuffle 类的算子，partition 之间的数 据量差别更为明显。为了利用 GPUs 进行加速， 将 Tasks 卸载到设备端形成 GTasks。如果将 GTask 作为一个最小执行单元分配设备资源：设 备内存资源和 CUDA 流资源，调度到 GPUs 上去 执行，会造成计算节点上各个 GPU 之间的工作负 载不均衡。为了能平衡计算节点上各个 GPU 之 间的工作负载，本文提出了一个任务分解执行模 型。该模型主要包括两个部分：自动数据切片机 制和自动任务分解机制。 5 面向机器学习/图迭代算法的分布 式并行优化 针对机器学习/图迭代算法过程中的分布式 并行优化中的计算效率等问题[43-44]。提出了面向 机器学习算法的分布式并行优化模型、分布式环 境中的并行条件随机场模型、并行维特比算法、 基于冗余距离消除和极端点优化的数据聚类方 法。解决了机器学习分布式优化的问题，突破了 大规模高效能数据并行处理系统的算力瓶颈。 5.1 分布式环境中的并行条件随机场模型 条件随机场 (conditional random fields) 是一种 概率图模型[45-46]。它是一种机器学习算法，需要 多次迭代。条件随机场在标记或分析序列数据方 面发挥了重要作用，并取得了显著的效果。条件随 机场结合了最大熵模型和隐马尔可夫模型的特点， 但隐马尔可夫模型不能直接看到其状态，不能应 用复杂的特征。然而，根据这一思想，条件随机 场模型可以很好地应用于依赖长距离和使用重叠 特征的特征。同时，条件随机场可以解决其他判 别模型中的标注偏差问题。为此，本文提出了一 ·926· 智 能 系 统 学 报 第 16 卷

第5期 曹嵘晖，等：面向机器学习的分布式并行计算关键技术及应用 ·927· 种基于Spark的改进条件随机场模型(SCRFs), Iog,因为对于很小或者很大的数值，直接计算会 重点提高算法处理大数据的效率。该模型有以下 溢出。相应的解决方法为 创新：为了加快速度，将迭代过程中多次使用的 中间数据缓存到内存中；利用特征哈希的方法降 log〉exp(x)=a+log〉exp(x-a) (9) 1 1 低特征的维数；对于梯度更新策略，本文选择 这对任意α都成立，这意味着可以自由地调节指 Batch-SGD。基于上述创新，可以有效地提高处理 数函数的指数部分，一个典型的做法是取x的最 的时间效率。 大值： 参数估计是条件随机场模型中最重要的阶 a=max(xi) (10) 段。在处理大规模数据时，模型的训练时间会大 这样就保证指数最大不会超过0，于是就不 大增加，需要花费大量的学习时间。大量实验表 会上溢。即便剩余的部分下溢了，也能够得到一 明，LBFGS的第一步是训练过程中的主要环节。 个合理的值。 LBFGS约90%的计算消耗处于第一步。如果能 52基于分布式机器学习的系统威胁感知模型 加快第一步，整个训练过程的时间就会明显减 为了提高RF算法的性能，有效解决分布式 少。因此，条件随机场训练过程的并行化主要是 计算环境下大规模RF算法执行过程中的数据通 并行计算目标梯度。 信开销和工作负载不均衡等问题，本文将改进的 aL(A) 随机森林分类算法在Apache Spark云计算平台上 (4) 进一步并行优化，提出一种基于Apache Spark的 22心水小合 并行随机森林(parallel random forest,,PRF)算法。 PR模型的每棵元决策树都是相互独立构建 通过式(3)可以得出第1部分是给定任意一 的，而且元决策树的每个树节点也是独立划分 个数据，特征的经验分布期望。可以描述为 的。PRF模型和各个决策树模型的结构使得它们 Eoi=∑i. T (5) 训练过程中的计算任务具有天然的可并行性。 =】 PRF的双层并行训练过程：在双层并行训练 第2部分是特征f的模型的期望分布： 方法中，并行训练随机森林模型中各元素决策树 ∑∑i0,xp0) 模型的构建过程和各元素决策树各节点的分裂过 (6) R=l yy 程。由于每个PRF模型中的每个元决策树都是 经过简单的替换，得到： 通过每个训练子集的独立训练来构建的，所以每 L(()- 个决策树之间不存在逻辑依赖和数据依赖。因 aλk (7) 此，在外部并行训练中，将训练数据集随机采样 在求特征的模型的期望分布的时候需要用 到K个训练子集中，分别对这些训练子集进行并 到前面的sum-product信念传播算法，sum- 行训练，构建相应的K元素决策树模型。在每个 product能推断出模型的各边际分布概率。 元决策树的构建过程中，通过计算当前特征子集 的信息增益率来完成每个节点的分裂过程，同一 E=∑ (8) 层次节点的分裂过程不存在逻辑依赖和数据依 然后根据式(7)可以直接求出各特征的模型 赖。因此，在内层并行训练中，对每棵决策树中 的期望分布。 的同一级节点，分别对当前训练子集的M个特征 但是当使用原生的sum-product信念传播算 变量同时计算，以实现节点并行分裂。 法的时候，会出现数值溢出的问题。这是因为条 在PRF模型的每棵元决策树的训练过程中有 件随机场拥有非常大的参数量，但是这些参数中 多种计算任务，本节根据各计算任务所需的数据 许多参数对应的权重系数却很小，这样就导致了 资源和数据通信成本，将这些计算任务分为信息 模型推断中不断进行sum-product操作，会因为数 增益率计算任务和节点分裂任务2类。 值过小溢出。为了解决这个问题，将原来的数值 每个决策树模型的训练任务DAG包含了对 空间转换到log空间，sum就变成了相应的log 应于决策树模型节点级的多个任务阶段。数据特 sumexp,.product就变成了求和。而且logsumexp 征降维后，操作阶段1将为m个输入特征变量生 不能直接简单地对各值先取exp再sum最后再取 成m个TGR任务(TGR1.1~TGR1.m)。这些

种基于 Spark 的改进条件随机场模型 (SCRFs)， 重点提高算法处理大数据的效率。该模型有以下 创新：为了加快速度，将迭代过程中多次使用的 中间数据缓存到内存中；利用特征哈希的方法降 低特征的维数；对于梯度更新策略，本文选择 Batch-SGD。基于上述创新，可以有效地提高处理 的时间效率。 参数估计是条件随机场模型中最重要的阶 段。在处理大规模数据时，模型的训练时间会大 大增加，需要花费大量的学习时间。大量实验表 明，LBFGS 的第一步是训练过程中的主要环节。 LBFGS 约 90% 的计算消耗处于第一步。如果能 加快第一步，整个训练过程的时间就会明显减 少。因此，条件随机场训练过程的并行化主要是 并行计算目标梯度。 ∂L(λ) ∂λk = ∑N i=1   ∑T t=1 fk(y i t−1 , y i t , x i t )− ∑T t=1 ∑ y ′y fk(y ′ , y, x i t ) p(y ′ , y   x i ) ) − λk σ2 (4) fk 通过式 (3) 可以得出第 1 部分是给定任意一 个数据，特征 的经验分布期望。可以描述为 EiD[fk] = ∑T t=1 fk(y i t−1 , y i t , x i t ) (5) f 第 2 部分是特征 k的模型的期望分布： Eiλ[fk] = ∑T t=1 ∑ y ′y fk(y ′ , y, x i t )p(y ′ , y   x i ) (6) 经过简单的替换，得到： ∂L(λ) ∂λk = ∑N i=1 (EiD[fk]− Eiλ[fk])− λk σ2 (7) f 在求特征 k的模型的期望分布的时候需要用 到前面 的 sum-produc t 信念传播算法， sum￾product 能推断出模型的各边际分布概率。 EiD [ fk ] = ∑T t=1 fk ( y i t−1 , y i t , x i t ) (8) 然后根据式 (7) 可以直接求出各特征的模型 的期望分布。 但是当使用原生的 sum-product 信念传播算 法的时候，会出现数值溢出的问题。这是因为条 件随机场拥有非常大的参数量，但是这些参数中 许多参数对应的权重系数却很小，这样就导致了 模型推断中不断进行 sum-product 操作，会因为数 值过小溢出。为了解决这个问题，将原来的数值 空间转换到 log 空间，sum 就变成了相应的 log￾sumexp，product 就变成了求和。而且 logsumexp 不能直接简单地对各值先取 exp 再 sum 最后再取 log，因为对于很小或者很大的数值，直接计算会 溢出。相应的解决方法为 log∑N i=1 exp(xi) = a+log∑N i=1 exp(xi −a) (9) xi 这对任意 a 都成立，这意味着可以自由地调节指 数函数的指数部分，一个典型的做法是取 的最 大值： a = max i (xi) (10) 这样就保证指数最大不会超过 0，于是就不 会上溢。即便剩余的部分下溢了，也能够得到一 个合理的值。 5.2 基于分布式机器学习的系统威胁感知模型 为了提高 RF 算法的性能，有效解决分布式 计算环境下大规模 RF 算法执行过程中的数据通 信开销和工作负载不均衡等问题，本文将改进的 随机森林分类算法在 Apache Spark 云计算平台上 进一步并行优化，提出一种基于 Apache Spark 的 并行随机森林 (parallel random forest，PRF) 算法。 PR 模型的每棵元决策树都是相互独立构建 的，而且元决策树的每个树节点也是独立划分 的。PRF 模型和各个决策树模型的结构使得它们 训练过程中的计算任务具有天然的可并行性。 PRF 的双层并行训练过程：在双层并行训练 方法中，并行训练随机森林模型中各元素决策树 模型的构建过程和各元素决策树各节点的分裂过 程。由于每个 PRF 模型中的每个元决策树都是 通过每个训练子集的独立训练来构建的，所以每 个决策树之间不存在逻辑依赖和数据依赖。因 此，在外部并行训练中，将训练数据集随机采样 到 K 个训练子集中，分别对这些训练子集进行并 行训练，构建相应的 K 元素决策树模型。在每个 元决策树的构建过程中，通过计算当前特征子集 的信息增益率来完成每个节点的分裂过程，同一 层次节点的分裂过程不存在逻辑依赖和数据依 赖。因此，在内层并行训练中，对每棵决策树中 的同一级节点，分别对当前训练子集的 M 个特征 变量同时计算，以实现节点并行分裂。 在 PRF 模型的每棵元决策树的训练过程中有 多种计算任务，本节根据各计算任务所需的数据 资源和数据通信成本，将这些计算任务分为信息 增益率计算任务和节点分裂任务 2 类。 每个决策树模型的训练任务 DAG 包含了对 应于决策树模型节点级的多个任务阶段。数据特 征降维后，操作阶段 1 将为 m 个输入特征变量生 成 m 个 TGR 任务 (TGR1.1~TGR1.m)。这些 第 5 期 曹嵘晖，等：面向机器学习的分布式并行计算关键技术及应用 ·927·