大数据的流动之美

1、专题大数据的流动之美数据流与大数据：挑战与机遇高光荣关键词：大数据数据流美国特拉华大学CCF海外杰出贡献奖专稿作者题记：本文是应中国计算机学会的邀请，在2013中国计算机大会上所作主题报告的 摘要。演讲的题目围绕中国计算机大会的中心议题一一大数据进行。就个人而言，这是第一次 就大数据这个热门题目作公开演讲，同时也是第一次把大数据和数据流两个题目结合起来。数据流创始于麻省理工学院Jack B. Dennis教授的实验室，在国际上产生了深远的影响， 从Dennis荣获2013年IEEE约翰冯诺依曼奖(IEEE John von Neumann Meda就可见一斑。 我于1980年赴美留学，在Den

2、nis的指导下以数据流为题分别在1982年及1986年完成了 硕士和博士论文。就本文的侧重而言，数据流主旨的通俗解释如下：程序的并行执行要避免静态的、死板的中心控制；数据的并行处理和程序的并行执行必须是一种顺其自然、互 动与互补的过程，否则庞大数据的存储和处理就会产生许多瓶颈及资源浪费。我的报告和这篇文章就是希望把这个道理讲明，以供国内各界同行和年轻学子探讨与 分享。以下内容由郑龙、涂浩根据我的讲话整理而成，特此表示感谢。高光荣 二0三年一月二十七日于特拉华数据流模型数据驱动并 行程序执行模型的提出，是冯诺 依曼计算机并行化历史上的一项 划时代的突破。数据流程序逻辑 基于图表达，是一种优美、直

3、 观、强大的并行计算模型。其思 路最初由麻省理工学院的Jack B. Dennis和他的学生们在上世纪60 年代末至70年代初提出。Dennis 启发了所有后来的数据流研究者 (包括麻省理工学院著名的数据流大师Arvind教授),而Dennis 本人也因为在数据流研究上的贡 献被授予2013年的IEEE约翰冯 诺依曼奖(最近十年，超过一半 的此奖项获得者也获得了 ACM 图灵奖)。经过近半个世纪的研 究，数据流理论不断完善、成熟， 由于其独特的性能、功耗表现， 对计算机的众多领域产生了深远 的影响，直到目前仍然是前沿研 究的热点。数据流研究的发展可以分为 两个主要阶段：1980年代中期之 前的

4、指令级并行的数据流以及从 1980年代末开始的线程级并行的 数据流。传统的控制流程序基于 程序计数器(program counter, PC) 控制对数据的计算，而指令级并 行的数据流的基本思想则是通 过数据之间的依赖关系来控制计 算。图1表示了计算f= (1+3) * (3+4)的数据流实现方式。数据BEIOiEEHQ0EDDQaoaa图i指令级并行的数据流程序图小圆点表示数据，大圆点表示数据流的逻辑计算节点，箭头表示数 据依赖关系，小图a-e分别表示计算的不同阶段。指令级并行的数 据流的基本思想则是数据控制计算，即一旦得到计算所需的所有数 据，逻辑计算节点即可被调度到硬件运算单元上进行计算

5、。以计算 f=(1+3)*(4+3)为例，乘法操作依赖于两个加法操作的结果，而加法操 作赖于相加的两个数据。因此，一旦“ 1 ”、“ 3”两个数据到达，加 法逻辑计算节点就开始计算，得到结果“ 4”(如小图b),此时乘 法逻辑计算节点所需的两个数据只得到一个，只能保持等待，直到另 一个加法运算的结果“ 7”的到达，才能进行乘法操作，得到结果 28(如小图d)。而在乘法操作进行的同时，如果新的数据到达，加法 运算单元又可以进行新的运算操作，如此，数据流程序图中的多个数 据流逻辑计算节点即可通过软件流水线的方式实现并行操作。一个程 序往往由多个不同f组成，多个f之间也是通过软件流水线实现并行。图2

6、数据流和控制流的结合流用图的方式来体现f计算中的 数据之间的依赖关系，乘法操作 依赖于两个加法操作。在数据流 中，每个计算操作(如图1中的 “加”、“乘”)被称为逻辑计算节 点(actor)，一旦数据依赖关系被 满足，逻辑计算节点即可被调度 到硬件运算单元，开始运算。如 图所示，一旦“1”、“3”两个数 据到达，加法运算的依赖关系即 满足，于是进行加法操作；而当 两个加法计算完毕，即“ 4”、“ 7” 两个数据到达，乘法运算的依赖 关系得到满足，即进行乘法操作。 基于数据流的控制思路，处理芯 片上的多个运算单元即可通过流 水线的方式对逻辑计算节点中的 计算进行并行操作。非常明显， 不仅在f=(

7、1+3)*(3+4)内部，多个 f之间也是通过流水线实现并行 计算的。这种基于数据流控制的 并行方式由高光荣教授提出，并 命名为数据流软件流水(dataflow software pipeli nin g)。1980年代末，随着多线程 (multi-threadi ng)的概念被提出， 数据流也吸取了控制流的一些思 路，从而变为数据流与控制流相 结合的混合方式。图2表示了这 一时期的数据流的变化。由于数 据流善于处理步骤间有多重、复 杂依赖的程序逻辑，对于标准的 串行逻辑(如图2左半部)，基 于程序计数器的控制流思路更善 于解决此问题。因此这一时期的 数据流将这些标准的串行逻辑计 算节点包装成

8、为一个宏数据流节 点，宏数据流节点内是控制流，处理有多重、复杂依赖关系的程序逻辑是数据流的优势，而对于标准 的串行逻辑，基于程序计数器的控制流处理效率更高。一个自然的思 路是结合两者的优势，因此，借助多线程技术，宏数据流节点的概念 被提出。通过将程序中多个标准的串行逻辑计算节点(左边绿色椭圆 中的k个白色圆点)包装成为一个宏数据流节点(图中用绿色椭圆表 示)，在宏数据流节点内部，串行逻辑使用控制流方式作为一个线程 执行计算；而在多个宏数据流节点之间，利用多线程的信号机制使用 数据流方式进行并行计算。17专题作为一个线程（thread）执行计算； 宏数据流节点间存在多重、复杂 并行依赖，通过线程

9、的信号机制 使用数据流进行并行计算。需要 指出的是，数据流的基本思想是 控制数据如何流过逻辑计算节点， 其本质是数据流过逻辑计算节点 进行计算。之前的数据流强调数 据的绝对运动，而逻辑计算节点 绝对静止；然而运动可以是相对 的，这使当代数据流发展得更加 灵活，仅强调数据与逻辑计算节 点的相对运动即可，即或数据运 动、或逻辑计算节点运动、或数 据与逻辑计算节点一起运动、互 动，这样的思路为基于处理器架 构的优化提供了更广泛的空间。在这一时期，高光荣教授 和其在麦吉尔大学、特拉华大学 的实验室的20余名博士、数十 名硕士经过20余年的努力，在 政府和工业界的相关项目的支持 下，从软件、硬件两个方面

10、，在 计算机系统结构、芯片、操作系 统、编译器等各个方面通过模拟 器及真机系统实现、验证了基于 数据流的并行处理模型。这一系 列的研究使得特拉华大学成为传 承、发扬数据流技术，培养数据 流人才的重要、核心基地。2005年下半年，Intel宣布 放弃原有的奔腾系列处理器，全 面转向片上多核处理器的消息， 引起业界的极大震动，这也等于 宣告“并行计算”再也不是科学 计算、高性能计算的独家秘诀；从高性能计算、桌面计算、嵌 入式一直到移动计算，“并行计算”变成了计算机系统的最基本 需求，变得无处不在。在这样的 环境下，虽然硬件已经可以设计 制造多核芯片，并支持线程级并 行，但软件特别是操作系统、并 行

11、系统软件仍然相对滞后，成为 制约计算性能提高、优化的主要 瓶颈。众多厂商、研究者仍在探 索更好的并行解决方案。而在此 时，数据流以其对算法支持的弹 性好，具备很强的扩展性，性能 功耗比高的特点，吸引了来自学 术界、工业界各方的关注，被视 为传统并行计算模型的升级方 案，数据流迎来了第二春。在这 一时期，数据流也有了进一步的 发展，提出了 Codelet编程模型 及相对应的执行模式。这个时期 的研究，结合多核、众核的架构 特点，Codelet模型中加入了对 资源的依赖，提出了弹性的粒度 大小，明确了 Codelet与线程的 关系。同时强调在多核、众核系 统中，运行时的环境应该与操作 系统有更明确

12、的分工，操作系统 应该负责基本的硬件管理；而运 行时的环境应该成为更为重要的 角色，负责多核、众核上的任务 调度、内存管理、负载平衡、能 耗管理等；并基于此，提出了基 于数据流的Codelet模型的运行 时环境的设计方案，一些研究成 果已经开始应用于实际项目中。 2000年始，美国联邦政府十分重 视高性能计算的基础研究，支持 了多个重大项目，2010年明确地 提出执行模型（execution model） 是并行系统设计的最根本问题。其中在由In tel领导的X-Stack项 目中，Codelet是整个项目的基 础执行模型，数据流在其中所起 的作用不言而喻。当前，对大数据处理的需 求日益增加，

13、大数据将成为未 来若干年计算机学科的主要挑战 之一。虽然Hadoop系统为大数 据处理提供了一个解决方案，但 是其性能越来越难以满足日益增 长的数据处理需求；且Hadoop 使用的MapReduce模型过于简 单，无法高效地支持更多的算法 逻辑。而大数据处理的需求也已 经从简单的统计变为复杂的商 业数据智能分析（bus in ess in telli- gence，对多次迭代、实时性能及 数据管理都提出了更多要求，这 些目前的Hadoop都无法很好的 应对。因此工业界及学术界都在 寻找下一代的解决方案。数据流模型针对当前大数据 的挑战，有着自己的理解。大数 据的特点在于“大”，如果将大 数据比

14、作洪水，那么传统的控制 流的解决思路就是通过修筑河堤 对数据进行划分、静态分配计算 资源；修筑水坝来对数据进行缓 存（在硬盘或在内存中）、对处 理进行同步。这种“堵”的思路 虽然可以一时缓解“洪水”冲击， 但是随着数据量的迅速增加，需 要修筑更高的河堤和水坝（更多 的计算和存储资源），而河堤和 水坝不可能无限增高，最终无法 避免决堤。数据流的基本思路是 让数据自适应地决定如何流动、 何时流动，其目标是让数据流动#得更为快速，因此数据流实际上是消除了滥用水坝 的瓶颈，解决了数据计算的同步与缓存 ；在河道之 间增加了分流以优化资源的利用、负载均衡；以增 加流速加速泄洪到入海口的思路，加快数据在处理

15、 单元的流动，优化内存计算性能。通过流水线的方 式缩减数据从计算开始到数据结果输出过程中所驻 留在系统的时间一一以一个字概括即为“疏”。“堵”、In ternatio nal)也在大会上展示了数据流与大数据结合、 创新的最新成果，吸引了来自各界的关注。我们有理 由相信，数据流技术在未来的几年中会成为下一代大 数据解决方案的重要支撑技术。(本文根据CNCC 2013特邀报告整理而成。更 多参考文献详见高光荣教授个人主页。)“疏”这两种截然不同的治“大数据洪水”的思路， 与“大禹治水”的故事何其相似，而两种方式的优 劣也已经被几千年前“鲧”、“禹”所验证。此外， 数据流基于图的程序模型、流水线的形

16、式天然支持 更为复杂的程序逻辑，实时计算、内存计算，MapReduce 模型、批处理模式都是数据流模式进行简 化后的特例。数据流的大数据处理模式从原理上领 先当前以控制流为基础的大数据处理模式。目前基 于数据流的大数据解决方案已经形成原型系统，并 快速地进行产业化，其性能相比目前的 Hadoop有 着大幅度的提升。这些工业化成果，得到了美国工 业界先驱的认可，吸引了众多关注，并与若干系统 厂商一起，正在针对下一代大数据解决方案进行研 究、商业合作。今年在美国丹佛刚刚结束的超级计算大会(SC13) 上，可以发现在数据流的前沿研究中，如前文提到 的Codelet模型已成为学术界、工业界共同瞩目的亮

17、 点；此外，高光荣教授创立了十余年的科技公司(ET作者：高光荣2013 CCF海外杰出贡献奖获得者。美国特拉 华大学终身教授;ACM IEEE Fellow 清华 大学、上海交通大学、华中科技大学等特聘 客座教授；中科院计算所特聘研究员。主要 研究方向为高级编译、体系结构与并行系统。ggao. capsl龙美国特拉华大学博士后，日本学术振兴会 特别研究员(JSPS Research Fellow) 方向为分布式与并行计算、异构计算、数 据流-大数据处理。涂浩CCF会员。华中科技大学讲师。主要研究 方向为互联网与大数据处理。tuhao主要研究CCF发布“计算机职业资格认证”计划2013年10月25日，常务理事王震代表CCF在CNCC颁奖大会上正式对外发布“ CCF计算机职 业资格认证”计划，这是CCF在对专业人士的专业能力评价方面，为企业和高校提供服务的重大举措， 它的成功实施必将在业界产生重要影响。该计划首先对进入软件职场的人士进行软件编程能力上机