KernelHive: a new workflow-based framework for multilevel high PErformance computing using clusters and workstations wITh CPUs and GPUs

2. 相关工作

2.1 集群上的并行编程

• MPI（信息传递接口） 是真正的并行编程标准，包括多节点集群和多核 CPU 节点。

• MPI 基于分布式内存系统和并行处理的概念

• 进程间通信通过使用信息传递和大量通信 API 库

2.2 GPU上的并行编程

• 对于低级的通用 GPU 编程，最流行的是 CUDA 和 OpenCL。大致思路是

  • 以网格形式对处理过程进行建模。一个网格中包含线程块，线程块中包含若干个线程

  • 块中的线程并行执行，且可以相互之间进行同步

  • 块和块之间独立运行

• CUDA 在 GPU 方面只针对 NVIDIA 的 GPU， OpenCL 可以在多种 GPU 和 CPU 上运行

3. 动机和创新点

• 新的解决方案要满足的条件

  • 1. 一个新的统一的、多层次的、具有自适应能力的框架。该框架能够对简单的和复杂的处理流进行建模和执行，同时能够在由 CPU 和 GPU 组成的的节点组成的集群中实现跨集群计算

  • 1. 易于使用的 GUI。它能设计和重用并行应用

  • 1. 自动调度

  • 1. 能插入专用的调度算法

  • 1. 多种可重用的组件库。上至高级应用，下至底层的 CPU 和 GPU 内核

• 创新点

  • 框架更具有一般性 —— 考虑到了集群中的接入节点和计算节点

  • 在内部网络中，只有接入节点能访问多个节点

  • 能通过使用 GUI 将应用定义为一个工作流

  • 可以插入各种优化器，从而调节性能

4 KernelHive 框架

4.1 框架结构 （3层结构）

1. 应用模型层

以图形方式建立并行应用模型。图中节点对应计算任务，边代表任务间的依赖关系

2. 执行引擎层

负责将并行应用映射到底层集群

3. 集群和节点管理层

对集群网络暴露出一个统一的 API。其中，每个集群由一个或多个节点组成，每个节点包含一个或多个处理器和0个或多个 GPU

说明：用户将计算应用定义为工作流，这会用到用户图形界面，同时也可能会用到模板库中的可用组件。然后，应用被传送到执行引擎层。该层会为应用启动某个优化器。优化器通过给定的优化标准决定把哪个计算设备分配给该应用，同时根据计算和通信开销以及用电量等在优化器中定义的规则对应用的执行进行调度。集群和节点管理层负责特定集群中特定计算设备的应用执行。

4.2 应用模型

用户可以在 KernelHive 应用层中定义将要在该系统中运行的应用。

• 定义一个应用只需3步

  • 1. 将一个工作流定义为一个有向非循环图，图中的节点逻辑地连接着处理节点。每个节点都包含其需要执行的代码。整个过程可以看成一个计算流。一开始，数据来自数据服务器，然后通过一系列的节点传递到有向非循环图的最后 一个节点并保存到数据服务器中。值得注意的是， KernelHive 优化器根据给定的优化标准在每一个将要执行任务的工作流节点中选择特定的计算设备

  • 1. 为每一个在上一步中创建出来的节点选择一个模版。模版是一个通用的定义，它指出了在特定节点中应该执行何种计算。模版在输入和输出的数量上有所不同，因此，处理流可能是一个树形结构。

  • 1. 补全在上一步中选择出来的代码模版。这一步通过指定一个计算内核来实施。计算内核负责节点内真正的数据处理

• KernelHive 系统基于某个能让用户执行多种类型计算的计算模版的概念。模版本身提供了关于计算如何执行和用户如何自定义相关细节的通用思路。框架伴随着基本的和更高级的模版以及将来可能的额外扩展。

• 处理逻辑可以为多种多样的 workers 定义。不同的 workers 对应不同的 KernelHive 框架模版。模版已经通过用 C++ 实现由 worker 子系统定义的抽象类 Worker。基本模版最根本的区分仅仅在于被 worker 处理的输入和输出量。具体包含一下3部分：

  • 数据处理器 —— 一路输入，执行计算，一一路输出

  • 数据合并器 —— 多路输入，一路输出

  • 数据分割器 —— 把数据分割成多个部分

• 接着内核被上传到系统，并在某个设备运行 worker 前被编译。

• 每个基础模版只需要一个用户定义的内核。但另一方面，更高级的模版也许需要多个内核。例如，考虑 Master/Slave 模型。用户要提供3个源文件 —— 一个说明输入数据如何被分割到多个 slave 中，一个决定所有的 slave 计算说明内容，最后一个负责最终结果的合并。

• 用户可以使用上面提到的那些模版定义自己的计算流。模板库包括

  • 针对工作流图节点的模版集。每个模版定义节点的特点，例如内核的数量、名字和需要的输入输出数量。也可能用额外的模版来扩展系统

  • 针对处理的计算内核集。系统自带一套预定的资源文件。用户可以对其进行更改或添加自己的源文件。内核模版对应具体的工作流几点模版的要求。

• KernelHive GUI 应用通过图形化的方式帮助用户精心安排复杂的执行方案——节点代表任务，边代表任务间的时间关系。

4.3 系统组件(子系统)

HIVE_GUI

一个桌面应用。用于将 KernelHive 应用定义为一个工作流，可以用来查看计算设备的状态和计算结果

HIVE_ENginE

一个 Java EE 应用，其对运行在底层集群系统上的工作流进行优化和管理

HIVE_CLUSTER

一个 Java 守护进程。用来提供对单个集群资源的访问

HIVE_UNIT

一个 C++ 守护进程。用来提供对单个集群节点的资源访问。可用于控制节点中的计算设备

• 运行在每一个连接到系统的计算机器中

• 任务：

  • 更新机器状态

  • 监听传入的作业

HIVE_WORKER

一个 C++ 库。用来在某个 HIVE_UNIT 设备上执行计算

• 运行在操作系统级别

HIVE_COMMON

被以上子系统共享的 C++ 和 Java 库

典型的部署方案

• HIVE_GUI 和 HIVE_ENGINE 部署在一台机器上或分开部署在两台机器或两个集群上。

• HIVE_UNIT 部署在每个节点上

• 一个集群中只有一个节点部署有 HIVE_CLUSTER

4.4 使用 GUI 对并行工作流应用进行建模

• GUI 的作用：

  • 1.使用可用的应用模型创建一个有向非循环图执行方案。

    节点	计算任务的工作流
    边	任务间的时间关系

  • 2.监视已提交的工作流执行状态，例如：

    • 完成

    • 处理中

    • 已调度

    • 错误，等

  • 3.监视系统物理节点的硬件配置

• HIVE_GUI 应用于 KernelHive 系统的其他组件进行通信，尤其是 HIVE_ENGINE 和 TEMPLATES 库。

  HIVE_GUI	---	SOAP Web Services	--->	HIVE_ENGINE

  TEMPLATES 库 被打包为独立的 JAR 包放在 HIVE_ENGINE 中，在应用初始化时呗动态加载。这样就能保证 HIVE_ENGINE 和 HIVE_GUI 应用 使用的是相同版本的 TEMPLATES 库。

4.5 组件管理和计算流

• 集群和节点管理层的任务：

  • 为了开始调度过程进程，HIVE_ENGINE 需要收集关于可用的基础设施和他们内部状态的信息

  • 设法将被分配的作业发送到已经调度好的资源处，另外，发送部分或最终的计算结果。

  • 追踪正在进行的计算的状态。每一个 worker 定期地报告它的当前状态和当前计算的进度。

• 因为 HIVE_UNIT 组件，可以看到更多关于每个集群中特定计算节点的详细信息。这些信息中包括每个节点中可用的计算设备的数量，包括 CPU 和 GPU。OpenCL 框架允许这两种计算设备透明地使用。

• 为了知道作业的进度， HIVE_CLUSTER 通过监听 UDP 端口来接受 HIVE_WORKER 二进制文件发来的信息。 基于 JSVC 库实现的 HIVE_CLUSTER 作为系统守护进程被部署。

• HIVE_UNIT 通过一个 TCP 连接与 HIVE_CLUSTER 进行交互。HIVE_UNIT 汇报 可用设备，参数和状态。设备列表和参数通过 OpenCL 库的 utility 方法获得。

• 子系统监听 HIVE_CLUSTER 的 connection socket

• HIVE_WORKER 子系统包括多种预编译二进制文件。这些二进制文件被分配给对应的在应用层定义好的计算模版。二进制文件的执行顺序如下：

  • 1. 下载计算内核和输入数据

  • 1. 运行内核

  • 1. 报告计算进度

  • 1. 上传结果

  • 1. 向 HIVE_CLUSTER 子系统报告作业完成

• 每一个节点在计算上花的时间有可能是很大的，这对 CPU 来说不是问题，但 GPU 就会出现问题。原因是，通常，操作系统会给显卡分配一个 watchdog 计时器，这个计时器联系着每一个活动的播放任务。当显卡运行一个任务的时间超过了给定时间，操作系统会认为任务失败然后杀掉该应用。一些 KernelHive 模版已经通过被设计成在迭代批处理中执行计算任务来克服这个不足。 worker 能以一种标准方式被编译，就说，在一次运行中处理全部输入数据，或者按照以下方案进行处理：

  • 1. 从头开始或从之前保存的地方开始。一直处理输入直到算出结果或到达迭代极限

  • 1. 把当前作业的偏移量存入内存，根据当前计算状态设置进度标志

  • 1. 执行宿主机器中的代码，读取之前保存在内存中的进度标志。如果进度已经算出或已经处理完所有数据，则停止处理。否则，返回第一步

4.6 Data management

• KernelHive能使用多种数据服务器。

• 让KernelHive支持新的数据库或文件系统时，需要实现与所有相关子系统有关的相关编程接口。比如内存数据库和MongoDB。

• 因为系统的异构问题，数据格式的兼容性问题格外重要。

• OpenCL标准定义了一些数据类型，这些数据类型的长度与底层的系统架构无关。int类型总是4字节，long类型总是8字节

• 字节顺序问题也很重要。可以通过C++模版代码或OpenCL内核进行检查，在两种方法中，必须要能顺利进行合适的数据转换。

• KernelHive只传送数据地址，当相关组件需要数据时，再自行下载

• HIVE_ENGINE 决定是否需要存储数据包和是否能够删除数据。这使得数据直接在计算单元间传输，而无需HIVE_CLUSTER 或 HIVE_ENGINE 的干涉。也因此减少了网络流量。

• 数据包存放在分布式的数据服务器中，那些数据服务器有些是本地 HIVE_UNIT 的一部分，有些是 HIVE_CLUSTER 的子系统。

5. KernelHive中计算的并行和优化

5.1 计算并行

• 使用 CPU 和 GPU 并行计算的机制

  • 1. 针对调度和选择计算设备的可交换的插件

    • 调度依据：性能，耗电量，可靠性

  • 1. 选择最好的计算内核配置的能力

    • OpenCL 中网格大小的选择

      • block 中线程太少，资源利用不充分

      • block 中线程太多，降低并行性，运行时系统会减少 block 的线程数

  • 1. 任务分解和自适应数据产生

    • 要使某个节点具有分解任务的能力，用户必须指定数据分割和合并的方式。这要求用户必须实现 IDataPartitioner 和 IDataMerger 接口。DataPartition 产生的数据块的数量由系统决定使用的计算单元决定。因为不同的计算单元的计算能力不同，所以，系统为了均衡负载将产生最佳的数据块数量。

5.2 执行引擎和优化器

• HIVE_ENGINE 子系统是 KernelHive 的大脑和中心进入点。有关可用基础设施和内部状态的完整信息由 HIVE_ENGINE 收集，由 HIVE_CLUSTER 传送。同时， HIVE_ENGINE 向客户端运用暴露客户端接口，尤其是 HIVE_GUI

• 组件接受客户端准备好的工作流，并把他们转换为单个的作业，然后把它们部署在设备上。

• HIVE_ENGINE 必须能够被每一个 HIVE_CLUSTER 子系统实例访问。HIVE_CLUSTER 能更新集群的基础设施状态

5.2.1 调度

调度

• 调度进程使用一个优化器组件。该优化器组件能面向性能、耗电量、用户正当使用资源等方面进行扩展，每一个优化器都要实现 IOptimizer 接口。接口中唯一一个方法在每次有新的工作流提交时都会被执行。多个优化器可以联合起来工作。

• 开发的一个备选方案

  • 在给定耗电量的情况下，选出一个能使执行时间最小的节点配置。这就是一个背包问题，使用了贪心近似算法

• 为防止机器长期没有响应，执行引擎使用了 EJB 计时器服务。TimerBean 类会周期性的检查系统中工作流的状态，执行清理程序，触发工作流的再调度进程

• 标记为可拆分的工作流任务会有以下几种内核类型：

  • 分割器内核 —— 1进多出

  • 处理器内核 —— 1进1出

  • 合并内核 —— 多进1出

• 当一个节点准备好被执行时，节点的拆分就会发生。

  • 输入数据会被分割成一些数据块，这样就可以在 CPU 和 GPU 上进行负载均衡

  • 然后，每个计算设备上的一个分割器和多个处理器，一个合并任务，会使用已经定义的优化器以正确的顺序被创建和调度

  • 这样就使得动态并行程序能通过数据块的动态分配顺利执行，同时实现资源新能差异化情况下的负载均衡

5.2.2 优化方法

• 性能调优的机制

  • 1. 选择计算设备。考虑：设备性能，通信开销，耗电量

  • 1. 决定最好网格配置，主要是 GPU。系统测量不同配置下的执行时间，选择最好的配置

  • 1. 决定首选的数据分割颗粒度和系统配置

    • 通过机构内部开发的模拟器实现该功能，该模拟器的具体工作如下：

      • 将给定数量的分发到计算设备中，分发时使用轮询调度方式并考虑通信开销（启动时间、带宽）。要考虑到重叠的通信和计算，这样可以减少通信开销和获得较高的增速

      • 处理数据包

      • 发送中间结果

  • 1. 真正的并行执行

6. 使用数据分割和计算管理方法进行的实验和结果

6.1 实验平台

• 同时有 GPU 和 CPU

  • 每个 CUDA 服务器上有3个 GPU，CPU 不直接参与运算

6.2 实验应用程序

• 暴力破解 MD5 加密

  • 用于计算的代码使用 OpenCL 内核实现，这样就能同时在 CPU 和 GPU 上运行

  • 具有较高计算开销和通信开销的应用可用来评估系统的可扩展性和用于优化的技术

6.3测试和结果

6.3.1 针对 GPU 的网格设置

• GPU 内部

  • 一个 GPU 包含 一定数量的 SM （流多处理器）

  • 每个 SM 有一个允许驻留线程个数的最大值和留给 OpenCL 工作组的位置数量的最大值

  • 每个线程一定数量的私有内存和在 OpenCL 中定义的局部内存

  • 一个线程组中有多个线程，这使得每个线程组都需要一定数量的私有内存和局部内存

  • SM 会在这些并行的线程组中运行，所以总共使用的私有内存和局部内存不会超过 SM 规定的值

• 测试内容

  • 每个 block 中线程数量不同时的执行时间

  • 每个 grid 中 block 数量不同时的执行时间

• 测试结论

  • 当 block 中线程太少时，执行时间明显变长

  • 当 block 中线程数量超过一个特定值时，会造成不必要的开销

6.3.2 针对良好扩展性的数据颗粒度评估

• 异构环境下涉及到多种 CPU 和 GPU。每个处理器的计算能力不同，所以需要负载均衡

• 时间开销如下：

  • 调用 Web 服务的时间，从数据服务器下载数据包的时间，

  • 处理时间

  • 调用 Web 服务的时间，上传数据的时间

• 对于该测试而言，CPU 比 GPU 慢很多，结论：

  • 数据包太少，GPU 先完成，而 CPU 还没完成，那么总的执行时间会变长

  • 数据包太多，虽然数据包会变小，但是通信开销会变大，比如下载数据和上传数据的时间

  • 要权衡数据包的大小和数量

6.3.3 关于最小执行时间的实验

• 使用理论最优值时，执行时间直线下降。

• 选择最好的数据粒度从而找出最好的乘数是很有价值的

7. 提出方法与 MPI + OpenCL 方法的比较

7.2 测试应用

• 地理空间数据的反距离加权插值计算

  • 数据处理节点使用 OpenCL 实现反距离加权插值算法

  • master--slave 模型

    • master -- HIVE_ENGINE

    • slave -- HIVE_WORKER

    • 中间层 -- HIVE_CLUSTER 和 HIVE_UNIT

7.3 测试和结果

• KernelHive 框架的总开销比面向性能的 MPI + OpenCL 的总开销高出约11%

• KernelHive 框架开销主要包括：

  • 通信开销 —— web 服务

  • 运行时开销 —— HIVE_ENGINE 和 HIVE_CLUSTER 由 Java实现