流计算模型

流是不间断的、连续的、移动的元素队列，其中元素是指相关数据的集合组成。流计算模型简称流模型，是对流进行处理的模型，其主要思想是将应用分解成一连串对流进行操作的计算核心，流在计算核心之间传递，在计算核心内部完成对流中元素的处理。

简介流计算模型，是一种将一般应用转化为以流为基本处理对象的流应用的计算模型，其基本思想是把应用组织成流（stream）和计算核心（kernel）两级。从宏观角度看，流计算模型中被处理的基本数据单位是流，各个操作被视为对整条流的操作。在流计算模型中，对整条流的宏观操作包括流聚合（stream gather），流分散（stream scatter）和流计算，其中流计算是以计算核心（kernel）的形式体现的。 流计算模型摒弃了传统计算模型中计算和访存的紧密耦合形式，将应用中的计算和访存进行解耦合，它对一般应用的转化过程在计算和数据组织两个方面展开。在计算方面，流计算模型把应用分解为多个对流进行处理的计算核心，这些计算核心通过流链接起来共同完成整个应用的复杂功能。在数据组织方面，流计算模型通过 stream gather 操作将应用中需要被处理的数据组织成流，流进入计算核心，流中的元素在计算核心内部被处理后形成新的输出流。如此反复，流在计算核心之间不断传递，不断被计算核心处理，最终完成应用的功能，通过 stream scatter操作将输出流转化为应用的输出数据1。

流数据流数据，在通信领域中它常用来表示一连串的数字编码序列，但是，在实际应用中它用来表示某一设备所产生的连续事件信息。也可以看成是一组组离散事件集合体，由成千上万个数据源，源源不断的持续生成，生成的数据流以非传统意义上的系统日志方式传送。它代表了一种新的数据模式，与传统数据库模型不同，它是一种大量、连续、快速、随时间变化的数据流。这类事件流包含两个方面的特征：一是事件信息是连续不断的产生，在早期，这类数据一般在股票交易系统中出现的比较多，但是银行、互联网监控等领域也会产生大量持续的数据；二是需要实时的对更新的数据流进行分析（如趋势分析、预测）等，提取有用的信息2。

流计算是一种编程计算机编程范式。1966年美国计算机专家B.萨瑟兰(Bert Sutherland)在其博士论文中提出数据流编程框架。这是流计算的雏形。流计算利用并行处理程序可以同时处理多个应用，实现单指令多数据的工作，无需考虑计算单元间的分配、同步和通信问题。流计算通过限制并行计算，简化了软件和硬件的并行工作。对一组数据(流)中的每个元素，都有一系列的指令(核函数)进行应用操作。流计算是针对流数据的实时计算，合了大数据处理的高效性与实时性。其主要应用的场景是，流数据量较大且连续并且实时性要求较高。

流级程序基于流计算模型，应用程序向流程序的映射也自然地采用流和计算核心两级编程模式。流级程序与普通程序的框架不同，在数据类型和操作类型两个方面进行了扩展，并且在结构上有特殊要求。在数据类型方面的主要扩展就是增加了新的数据类型—流。根据前面对流概念的讨论，流级程序将一个数据队列定义为一条流。流这个新增的数据类型也相应地引起了流级程序中操作类型方面的扩展，即对流的操作。前面已经提到对流的操作主要包括三种，分别是流聚合 stream gather、流分散stream scatter 和流计算 kernel。流聚合负责从程序的各类数据结构中取数据，然后形成一条流。例如，可以将一个二维整型数组中的数组元素按照列顺序排列而形成一条流，也可以按照一定的规则从一个文件中读取数据来形成一条流。流分散与流聚合的过程相反，负责将流中的数据按照一定规则存入各类数据结构。在流聚合和流分散过程实际完成的是流与其他数据结构的转化，转化过程遵循一定的规则。流级程序的一般模式是通过流聚合组织输入流，然后调用计算核心对流进行处理，生成输出流，该输出流可能继续作为下一个计算核心的输入而被使用，如此反复直到全部计算核心执行完毕，生成最终的输出流，然后通过流分散将输出流的数据保存到普通的数据结构中去。 计算核心程序在流处理核心上执行，负责对流中元素的计算。计算核心程序与普通的函数类似，但是其参数包含流。另外，计算核心是为了并行处理而设计的，因此必须明确它是在多个并行处理单元上同时执行的。不过，大多数情况下这种并行化不是自动的，程序设计者必须自己为并行处理单元设计流数据的移动。

并行级别流体系结构是与流计算模型完全匹配的，因此流体系结构能够充分开发应用中的多级并行性和局域性。对并行性的开发包括 ILP、DLP 和 TLP 三种，局域性的开发主要指生产者-消费者局域性。

指令级并行（Instruction Level Parallelism, ILP）：运算簇内部多个ALU 单元的结构确保能够以 VLIW 打包的形式开发指令级并行。

数据级并行（Data Level Parallelism, DLP）：通过共用同一个微控制器，计算核心程序以 SIMD 的方式在多个结构相同的运算簇上并行执行。

任务级并行（Task Level Parallelism, TLP）：在流访存和 kernel 运行之间存在任务级并行，例如前一个 kernel 运行时，后一个 kernel 的流可以同时加载。另外，多个流处理器可以通过网络互联，并行执行不同 kernel，形成 kernel 间的任务级并行。

生产者-消费者局域性（Producer-consumer Locality）：对生产者-消费者局域性的有效开发得益于流体系结构中软件管理的片上存储层次。流调度器软件控制前一个 kernel 生成的中间流不向片外存回，而是只需要保存在片上存储中，后一个 kernel 以片上存储的中间流作为输入流即可。对生产者-消费者局域性的开发通过减少了片外访存的方式有效提高流计算性能。

本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学