申威处理器上数据流运行时系统的设计与实现

张鹏飞，陈俊仕，郑 重，沈沛祺，安 虹，许 乐

（中国科学技术大学 计算机科学与技术学院，合肥 230026）

0 概述

近年来，摩尔定律不断放缓，通用处理器的性能增长受到了物理规律限制，如功耗、互连和设计复杂度等。随着半导体工艺的发展接近物理极限，芯片开始朝专用化、多样化方向发展，使得多核、众核成为现代高性能计算系统的主流设计。众核平台的主要特点是单个芯片上集成了大量异构的计算核心，且具有多层次的片上存储结构。为了充分利用片上的大量计算核心，提高多级存储的访存带宽，提高应用于高性能计算平台的编程效率和运行效率，工业界和学术界开发了众多的并行编程模型。

早期的并行编程模型是基于fork-join 的多线程模式，也称大同步模型［1］，如OpenMP［2］、OpenACC［3］、Cilk［4］、OmpSs［5］等，其本质上基于分治算法的思想：将应用中的计算任务分解成若干个相互独立、并行执行的子任务，并分配给多线程异步执行；一段时间后，再对并行计算的所有或部分线程进行同步操作并等待合并各子任务的计算结果。不同线程在执行过程中处理任务的速度可能有较大差距，例如可并行子任务的划分不均匀时，最慢的子任务（线程）就会成为性能瓶颈。为了解决粗粒度任务划分带来的同步等待问题，工业界和学术界又发展了基于异步任务的并行编程模型，如TBB［6］、DPC++［7］等，其可以进一步挖掘程序中的细粒度并行性，但依然采用join 同步方式，存在由同步带来的性能损失。

基于数据流的并行编程以数据为中心，将并行应用表示成有向无环的数据流图，其中节点表示具体计算，而边表示数据流动和任务间的依赖关系，数据在边上传递，由一个节点流向另一个节点。用这种更自然的风格来表示任务间关系，可以更好地挖掘程序中的细粒度并行性，充分消除同步带来的等待开销。在数据流抽象的数据流图中，当某个节点的依赖关系被满足时，其相应的计算任务即可被执行，提供了较高的并发度。节点所代表的任务采用异步执行和点对点通信方式［8-10］，可以解决计算资源间的负载均衡问题。当用户使用数据流方式将应用依赖关系描述完成之后，由运行时系统自动处理程序计算顺序、任务调度问题，减轻了程序员负担。

新一代国产申威处理器采用主从核异构众核架构，具有很高的峰值性能。该平台主要提供基于传统fork-join 执行模型的并行编程接口——athread，这需要用户基于特定硬件结构进行手动的复杂调优，才能实现计算资源的充分利用和任务负载均衡划分。数据流所具备的特性可以帮助解决新一代神威众核平台并行编程难的问题，充分挖掘不规则应用程序中的并行度，解决众核计算资源间的负载均衡问题，提高硬件资源的利用率。Codelet 模型［11-12］是美国特拉华大学的高光荣教授团队提出的一种基于数据流的、细粒度的程序执行模型。该模型已在通用多核平台上有相关实现［13］，本文则关注于将Codelet 程序模型部署到众核平台，实现其上的数据流运行时系统及编程接口。在新一代申威众核架构上实现基于Codelet 模型的并行编程运行时系统面临如下问题：

1）从核对原子操作的支持不完善。Codelet 程序执行模型的基本调度和执行单元称为Codelet。Codelet 之间依赖关系的同步需要用到原子操作，然而从核上对原子操作的支持并不完善且开销较大。

2）与现有从核计算库存在兼容问题。神威众核平台上的应用程序中往往需要调用从核计算库，而从核计算库通常会占用整个从核阵列，与运行时系统产生冲突。这要求数据流运行时系统不能够长时间地占用从核。

针对上述问题，本文设计并实现了一个面向申威众核架构的数据流运行时系统——swTasklet。用户可通过其提供的编程接口，将并行程序表示为数据流风格的细粒度并行任务，自动地完成计算任务在从核阵列上高并发的调度执行。本文提出将从核上的Codelet 分离为纯计算和同步操作两个部分，由从核完成纯计算部分，主核完成同步操作。由于从核不需要执行同步操作，对共享数据的操作维护在主存上，因此不需要原子操作的支持。相比于通用CPU 平台上将每个计算核心映射为一个具有独立的任务调度执行功能的计算单元（Computing Unit，CU），本文提出在众核平台上由主核完成从核数据流计算任务的调度执行。由主核将任务队列中的任务动态分配给从核，不需要从核检查任务队列。由于从核不会被长时间地使用，因此不会与已有从核计算库冲突。为了验证swTasklet 的有效性，本文以NPB LU 程序和向量-向量为实例，采用swTasklet 编程接口对其重构。

1 研究背景

1.1 申威异构众核处理器

新一代申威众核处理器采用异构融合体系结构，采用片上阵列集群和分布式共享存储融合的异构众核体系结构，使用64 位自主研发的申威指令系统。申威处理器芯片由6 个核组构成，每个核组包括1 个主核（运算控制核心，MPE）和64 个从核（运算核心，CPE）。图1 展示了申威异构众核处理器的体系结构。

图1 申威异构众核处理器体系结构Fig.1 Shenwei heterogeneous many-core processor architecture

神威超算平台采用异构加速编程模型，如图2所示，其平台程序由主核代码和从核代码两部分组成，其中：主核代码运行在运算控制核心上，负责数据和任务的分配和管理（即启动从核，调用从核代码，等待从核队列上的任务执行完成）；从核代码运行在运算核心上，实现对核心功能模块（即可并行任务）的加速。

图2 申威异构加速编程Fig.2 Shenwei heterogeneous acceleration programming

主核程序采用athread 加速线程库的相关接口对并行任务进行管理。根据接口功能的不同，并行任务可在一个或多个从核上执行，主核可在从核运行期间执行其他任务。athread 加速线程库属于fork-join 并行执行模型，使用athread_spawn 接口启动多个从核线程，在所有从核完成任务之后，再使用athread_join 接口等待所有从核线程完成。

申威处理器98%的计算性能来源于从核阵列，挖掘从核架构以充分利用计算资源十分重要。athread 编程采用fork-join 执行方式会产生以下3 个问题：

1）难以产生足够多的细粒度计算任务分配给众多的计算核心。采用athread 编程属于基于控制流的粗粒度任务分割，划分的任务计算粒度较大。当面对不规则任务时，任务难以划分，且任务之间粒度差距较大，使得从核空闲，效率不高。

2）难以平衡异构计算单元间的任务负载。申威处理器上主核和从核阵列之间是异构的，计算能力、体系结构和指令集均不相同。需要使两种计算单元获得的任务匹配其运行速度，避免一者空闲一者繁忙的情况。而一个从核阵列需要执行的从核任务往往也并不相同，不同从核执行任务的速度差异会严重影响应用的加速。

3）难以表达细粒度并行任务中的复杂数据依赖关系。一些非规则、数据依赖复杂的并行应用程序，使用athread 编程难以表达细粒度任务之间的点对点的数据依赖关系。

1.2 Codelet 程序执行模型

Codelet 程序执行模型是一种细粒度的、任务驱动的并行程序执行模型，支持在控制流机器上使用数据流模型组织计算［14-16］。

Codelet 执行模型中最基本的概念称为Codelet，即一些机器指令的集合或一段代码片段，Codelet 是该执行模型中的基本调度单位，是原子不可中断的。每一个Codelet 包含一个依赖计数，表示该任务在执行前需要完成的依赖任务。

在用Codelet 模型表示的应用程序中，一个Codelet 即表示一个计算任务，任务之间的依赖关系通过Codelet 之间的边来表示，则Codelet 及其上下游的依赖关系可以构成一张数据流图，称为CDG（Codelet Graph）。为了实现更好的并发性，根据数据局部性和Codelet 所实现的功能等，将CDG 分成多个子CDG，每个子CDG 被分配给一个Threaded Procedure（TP），它充当CDG 及其Codelets 所需数据的容器，还包括输入、输出和Codelet 共享的数据，TP为Codelet 模型提供了二级并行性，如图3 所示［13］。

图3 Codelet 程序执行模型Fig.3 Codelet program execution model

Codelet 程序执行模型的执行和调度依赖于抽象机器模型，如图4 所示。该抽象机器模型描述了Codelet 模型如何在硬件层进行分配、存储、调度和执行，由许多节点通过互连网络连接在一起，一个节点中包括多个芯片，每个芯片以高速开关或总线互连。在一个芯片中存在一组有共享内存和本地内存的核心（core），称为集群（cluster）。核心分为两种：CU 和SU。CU 是结构简单的计算核，每个cluster 上有若干个CU。CU 负责执行Codelet 以完成计算任务。SU 是结构较为复杂的调度核，每个cluster 上只有一个SU，SU 主要有3 个任务：1）管理cluster 内的所有硬件资源；2）负责在cluster 间调度TP；3）将处于就绪状态的Codelet 根据一定的调度策略调度给合适的CU 来执行。

图4 Codelet 抽象机器模型Fig.4 Codelet abstract machine model

1.3 相关研究

数据流因具有天然的并行性，可以更细粒度地表达程序，消除同步开销。越来越多的科学计算以及大数据处理开始使用数据流模型［17］，同时也出现了很多基于数据流的并行编程模型。

SWARM［18］是基于Codelet 模型的 一个商业实现。与Codelet 不同的是它没有TP 的概念。DARTS［13］是由特 拉华大 学CAPSL 开发的 完全基 于Codelet 模型的数据流运行时系统，可以在现有的共享存储模型的机器上运行。尽管使用硬件与软件结合可以达到更高的性能，但是为了节约开发时间和成本，DARTS 仅在现有的硬件上进行软件模拟，实现了动态的任务调度。通过面向对象的编程方式，用户可以方便地使用DARTS 的编程接口，定义自己的 Codelet Graph，然后将 Codelet Graph 交 给DARTS，自动地完成调度和执行，但只运行在多核上。

美国田纳西大学的Jacket Dongarra 开发了数据流编程模型Parsec［19］，目的是通过可移植的编程模型有效地利用异构众核系统。PaRSEC 由一个运行时和一组工具组成，用于构建、分析和预编译任务DAG 的中间表示。PaRSEC 可以接受多种形式的任务图表示，但其内部只有一种称为JDF 的任务图表示。它用与问题大小无关的方式表达应用程序的任务及其数据依赖关系。

Taskflow［20-21］是面向GPU 设计的一个轻量级并行和异构任务图计算系统，其引入了图内控制流，设计了一个新的条件任务模型。用户可以在任务图中加入控制流决策，是一个表达力良好的编程模型。它使用C++闭包设计任务图编程模型，采用异构工作窃取（work-stealing）方法。

AceMesh［22］是一个 针对网 格应用、数据驱动的并行任务编程框架，其底层有AceMesh 任务调度系统保证任务依赖图的执行过程。它基于athread 库设计了支持神威众核平台的版本，根据申威体系结构加入层次任务队列，支持主从任务协同调度，并对并行性和缓存重用进行相关优化。AceMesh 使用制导语句来表示程序中循环的并行区域。

SunwayFlow［23-24］是在神威·太湖之光上设计并实现的一种基于数据流的编程模型，其基于Codelet程序执行模型。该模型去除了TP 结构，设计和实现了数据流编程模型的运行时系统。但它将从核映射为完整功能的CU，导致从核硬件线程会被长期占用。从核代码不可避免地需要调用高性能从核计算库，需要显式地将从核运行时停止，然后在调用完库后再启动从核阵列来完成运行时的后续工作。

2 面向异构众核架构的数据流运行时系统

本节主要介绍swTasklet 数据流编程和运行时系统的设计，为用户提供面向基于Codelet 数据流模型的编程接口，将并行程序表示为数据流风格的细粒度并行任务，运行时系统自动地完成数据流计算任务在申威从核阵列上动态、高并发的调度执行。

2.1 Codelet 模型到申威众核的映射

为了在新一代申威众核平台上实现基于Codelet 模型的数据流运行时系统，首先需要将Codelet 模型映射到众核处理器上。

一个核组包含1 个结构复杂的主核（控制核心）和64 个结构简单的从核（运算核心）；核组可映射为Codelet 抽象机器模型中的集群，包含两种负责不同功能的计算核，其中：主核映射为调度单元，主要负责任务的分配和调度，也包括管理从核队列资源；从核负责任务计算，并映射为不完全的CU。使用主核分配、调度和管理从核中的计算任务可以有效实现单核组内的主从动态并行。

主核对应一个SU，负责Tasklet 任务队列的调度，管理核组内的计算和存储资源。从核相对主核结构简单，存储层次结构不适合维护复杂共享数据结构的一致性。如果从核被映射为SU，则需要频繁地访问主存，影响任务的执行速度，且SU 之前需要同步来进行任务调度，涉及共享数据结构，而维护共享数据结构需要使用互斥锁，会严重影响并行效率。因此，每个从核对应一个CU，负责完成Tasklet 任务计算，如图5 所示。CU 不维护任务队列，只提供固定容量的Tasklet 任务缓冲。CU 的任务缓冲存储在主存中，而不是存放在访存延迟更短的LDM 上。

图5 抽象机器模型映射Fig.5 Abstract machine model mapping

因为从核的一些结构特点，在swTasklet 中从核并不映射成具有完整功能的CU，一部分功能需要主核来完成。将从核映射成一个完整的CU，即拥有完整独立的Tasklet 任务调度功能，会产生以下两个问题：

1）与现有从核高性能计算库的兼容问题。应用程序中不可避免地要调用BLAS 或者FFT 等高度优化的计算库。采用SunwayFlow 的CU 映射方式，即任务缓冲放在LDM 中，会导致从核硬件线程被长期占用，从核硬件线程一直不停地检查任务缓冲是否为空，如果有就一直执行。如果调用高性能计算库，需要先手动将从核上的运行时暂停。调用完后，如果Tasklet 队列中仍有任务，要再一次启动从核阵列进行计算，这反而降低了用户应用开发的效率。

2）从核不完善的原子操作。将从核映射为CU，从核完成Tasklet 的计算任务之后，需要进行同步操作，即通知其他的Tasklet 按照数据依赖关系对依赖计数进行减1 操作。而依赖计数属于共享数据结构，因为存在多个从核完成计算任务之后对同一个Tasklet 的依赖计数进行减1 操作的情况，此时需要从核提供原子操作来保证数据一致性。然而从核上对原子操作的支持不完善且开销较大。

2.2 swTasklet 运行时系统设计和实现

swTasklet 运行时系统主要负责任务的分配调度和任务之间的同步。整个系统分为两层：第一层为用户层，为数据流编程框架提供描述，创建可执行任务的接口，用户通过接口对应用程序进行数据流风格的抽象，并将细粒度任务交给第二层——运行时执行层；第二层负责将已满足数据依赖关系的计算任务分配给空闲的硬件资源，将满足依赖关系的任务放入任务队列，并随之启动从核完成计算任务。

2.2.1 前端接口设计

该运行时系统主要用C++语言实现。用户定义细粒度计算任务主要使用3 个基本的数据结构：Task，Tasklet，CpeTasklet，其关系如图6 所示。

图6 swTasklet 主要类及其编程接口Fig.6 Main classes and their programming interfaces in swTasklet

Task 类是程序中所有任务的抽象基类，主要包含一个或多个细粒度Tasklet 计算任务及其所需要的上下文数据。它结合了Codelet 程序执行模型中的TP 和Codelet，当TP 创建时立即执行一段Tasklet 任务。这种结合的设计能够减少程序运行过程中创建的Tasklet 数目，降低一定的时间开销。

Tasklet 类对应Codelet 程序执行模型中的Codelet，是运行时系统中的基本执行和调度单元，一旦分配计算资源执行即不可中断。Tasklet 由依赖计数、执行函数和同步函数三部分组成。依赖计数记录该Tasklet 的任务依赖个数，执行函数为其需要完成的计算任务，同步函数是指当执行函数完成后Tasklet 通知其下游的Tasklet 依赖计数减1。

CpeTasklet 类是Tasklet 的子类，用于定义既可以运行在主核也可以运行在从核上的Tasklet 计算任务。CpeTaskelet 的功能分为两个部分：execute（）和synchornize（）。execute（）接口就是用来定义可以在主核或者从核上执行的计算任务。用户需要定义execute（）函数在主核和从核上两个版本的代码，且不包含同步操作，并针对各自的结构特征进行相应的优化。当CpeTasklet 被调度执行的时候，如果没有空闲的从核可用，则运行时系统会调用主核版本的execute（）代码执行。当有空闲从核时，则运行时系统会调用从核版本的execute（）代码执行。在从核完成计算任务后，由主核调用相应CpeTasklet 的同步操作，即synchornize（），释放相应Tasklet 的依赖计数。

2.2.2 运行时系统设计

运行时系统负责任务的分配调度和执行并启动、管理从核。运行时系统只运行在主核上，不在从核上。从核只负责Tasklet 子类中的计算函数execute（）的执行，不在LDM 中维护任何共享数据结构或任务状态。主核负责任务的分配和调度，以及维护从核的状态。

1）主核运行模式

主核主要负责任务的分配和调度。运行时系统在主存中维护两个任务队列，分别对应Task 和Tasklet。当计算单元完成Tasklet 的计算任务后，主核完成Tasklet 的同步操作并将下游满足依赖关系的任务添加到对应任务队列中，并释放刚完成的Tasklet 计算任务所占用的硬件资源。运行时循环检查Task 任务队列，将队首任务取出并执行，然后循环检查Tasklet 任务队列，将Tasklet 任务分配到计算资源上。

运行时通过检测Tasklet 状态转换来完成任务的调度执行。首先，Tasklet 接受必要的参数后，进入预备状态，即实例化；然后，当该Tasklet 的数据依赖满足，就会进入就绪状态，并被压入任务队列。接着，分配给主核，主核完成Tasklet 的计算任务。最后，进行同步操作，通知与其有数据依赖的Tasklet，表示数据已就绪，被通知的Tasklet 变为预备状态，其运行模式如图7 所示。

图7 swTasklet 主核运行模式Fig.7 Master core run mode in swTasklet

Tasklet 的计算任务可由主核完成，该情况适合计算任务数较多、计算量较少的情况，有效减少了任务上下文在主从核的切换。虽然从核阵列较多，但单个从核的计算能力比主核弱，当任务数量较少时，放在主核上，可以降低计算任务的执行时间，还可以有效节省不必要的调度开销，包括将Tasklet 分配给空闲从核和释放硬件资源等。当并行应用的并行度较低时，使用主核执行Tasklet 任务可有效覆盖运行时的调度开销，从而提升效能。

2）主从核协作模式

由于体系结构限制，在从核上无法实现完整功能的CU，需要主核一起参与协作完成。在编程接口上，swTasklet 将Tasklet 中计算操作和同步操作分离，从核只负责计算操作的执行，而同步操作由主核完成。主核通过一个从核阵列监测器（CpeMonitor）来实现对从核工作状态和CpeTasklet 执行状态的管理。

CpeMonitor 为从核阵列中的每个从核设置4 种状态：初始化，空闲，繁忙，完成。运行时系统采取按需启动策略，当用户向运行时系统提交第一个Task任务时才开始进行初始化操作。在运行时系统初始化过程中，每个从核状态被设置为初始化状态。当运行时系统初始化完成后，每个从核的状态转换为空闲状态。当从任务队列顶端取出就绪CpeTasklet任务时，调度器循环检查从核状态。当从核状态为空闲时，则将其状态改变为繁忙［图8 中步骤（1）］，并将该任务分配给从核异步执行［图8 中步骤（2）］，即CpeTasklet 类从核版本的execute（）函数［图8 中步骤（3）］。计算完成后，由从核将运行时系统中该从核的状态变量置为完成态［图8 中步骤（4）］。完成态指该从核上执行的CpeTasklet 完成了计算操作，但是同步操作尚未执行。当调度器检测到处于完成态的从核时，说明该从核上一个CpeTasklet 同步操作尚未完成。此时主核会执行该CpeTasklet 的synchnorize（）函数［图8 中步骤（5）］，进行同步操作。同步操作可能产生依赖满足的Tasklet，并将其添加到任务队列中。执行完同步操作后，调度器将任务队列顶端的CpeTasklet 分配给该完成态的从核，并将其状态改为繁忙。另外，当任务循环结束时，调度器会检测是否存在仍处于完成态的从核，如果存在，则执行对应CpeTasklet 的同步操作，并将从核状态由完成转换为空闲。

图8 swTasklet 主从协同运行模式Fig.8 Master-slave coordination run mode in swTasklet

主核和从核阵列以异步的方式运行，通过状态变量进行通信。主核主动地查询从核的状态变量，进行任务分配或资源释放；从核被动地等待任务，接受任务之后进行计算，计算完成后改变自己的状态变量并继续等待；对于主核和从核共享的一些数据结构，只由主核进行修改操作，避免使用互斥锁等。从核被动地接受计算任务，不需要检查任务队列，从核不会被长时间地占用，从而不会与已有从核计算库冲突。主核轮询地检查从核状态变量，而不是每次从0 号从核开始检查，这样可避免一些从核一直在做任务，而一些从核不能获得Tasklet 的情况，避免冗余检查状态变量。

从核每次最多处理一个CpeTasklet 的计算任务，并不维护缓冲队列，原因主要有两个：如果在主存上维护该队列，从核的访问代价会过大；也不能存放在LDM 中，因为LDM 容量过小。且该队列是主核和从核共享的数据资源，需要使用并发队列或者互斥锁来解决一致性问题，对性能影响较大。所以从核一段时间内最多处理一个计算任务，该计算任务由主核分配，采用生产者-消费者模式。这样调度开销较小，当任务较多时，每一个从核都能及时得到任务。

3 实验结果与分析

实验在新一代申威众核处理器单核组上进行。主核工作频率为2.1 GHz，从核工作频率为2.25 GHz。主存大小为16 GB，单个从核的LDM 大小为256 KB。在本节中，选取向量-向量加和NPB LU 程序用于验证swTasklet 数据流运行时系统的有效性。编译器使用系统提供的众核基础编译器swg++，编译选项都使用-O3，生成更高级优化的可执行代码。

3.1 向量-向量加

向量-向量加操作是完全可并行的，计算任务之间无数据依赖，分别使用athread 库和swTasklet 实现该算例。在该算例中，两种并行方式的性能均不受同步操作的影响，因此可以体现出swTasklet 运行时调度的开销。本实验将数据规模为N的计算分成M个子任务，每个任务的计算量相同。athread 版本和swTasklet 版本均通过DMA 将任务所需数据读取到从核LDM 中。

图9 是两种并行编程模型在任务数量为64 时不同规模下向量-向量加实现的加速比。横坐标为向量的元素个数，纵坐标为两种并行版本相较于主核实现的加速比。当数据量较小时，数据流框架实现的加速效果一般，此时主要开销在运行时系统的任务调度上。当数据规模增大时，运行时系统的调度开销所占比例逐渐降低，加速效果越来越显著，最高可超过athread 版本一倍。

图9 任务数量为64 时不同规模下向量-向量加实现加速比Fig.9 The speedup of vector-vector add achieved with different scales and fixed task number 64

图10 是两种并行编程模型在任务数量不同时所实现的加速比。实验结果表明，大部分情况下，swTasklet 实现的加速比与athread 手动优化相当。

图10 任务数量不同时向量-向量加实现加速比Fig.10 The speedup of vector-vector add achieves with different task numbers

3.2 NPB LU 程序

本节以NPB（NAS Parallel Benchmarks）中的LU程序为例来验证并行编程框架的有效性，它被广泛应用于CFD 模拟。LU 程序基于对称超松弛（SSOR）迭代法来求解一个三维系统。该系统由三维形式的Navier-Stokes 方程有限差分离散化产生，并将该三维系统分解为一个下三角系统和一个上三角系统，最终得到的结果是5 个非线性偏微分方程的数值解［25］。

分别使用athread 和swTasklet 对LU 程序中的核心代码进行并行化。LU 程序的数据依赖关系相对比较复杂，数据流模型较fork-join 模型能够更好地刻画任务间的点对点依赖关系。使用athread 编程表达LU 程序的数据依赖关系，需要用到复杂的同步操作和设置共享数据结构，在国产众核架构上实现复杂，且代码可移植性较差。

在LU 程序求解过程中，首先形成下三角形和对角线系统（JACLD 函数）并求解（BLTS 函数），然后是上三角系统（JACU 函数和BUTS 函数），最后再对结果更新（ADD）。在求解方程组时，（i，j，k）处的解依赖于（i+e，j，k）处的解（i，j+e，k）和（i，j，k+e）。对于三维系统中的每一个网格点，所完成的计算任务就是一次LU 分解再加上一次迭代更新工作，其依赖关系如图11 所示。

图11 上下三角系统中的数据依赖关系Fig.11 Data dependencies in the upper and lower triangular systems

可以将整个三维系统看成一个问题规模为N×N×N的三维空间。N是每一维方向上网格点的数目，而每一个网格点都表现为一个5×5 的矩阵。对于所有的三维格点来说，上下三角系统的构造是可以同时进行的，但是每一网格点的求解存在前驱后继的关系，且需要用到其临近的3 个点的解。以下三角系统求解为例，图12 是三维网格的侧视图，也可以看成是整个三维系统的计算依赖图，其中每个任务包含了垂直方向上的N个网格点。共有三层循环，循环方向为k-i-j；在此任务划分下，任务粒度为中间的i层循环，每个任务当依赖关系满足时，即被分配到空闲从核上进行k层循环的计算任务。当左下角的任务计算完成后，它会通知相邻的任务，并激活该任务。可以看出，在任务的调度、分配和执行过程中，满足依赖关系且可并行的任务数量先逐渐增大然后减小。在运行时系统工作的开始和结束阶段，任务数量较少。上三角系统的计算和下三角系统类似，只不过依赖顺序相反。

图12 fork-join 模型下LU 任务依赖关系Fig.12 LU task dependencies in fork-join model

在使用fork-join 模型表达LU 程序时，如图12 所示，将整个三维系统（三层循环）表示成一个二维超平面，平面中每一个点依赖其下方和左方的任务；在表达时，整个程序从左下方的任务向右上方任务推进，使用大同步来维护依赖关系，即每个迭代步完成斜线上的任务。而下一个迭代步的任务只能等待上一个迭代步的任务全部完成才能被分配执行。

使用数据流模型表达LU 程序时，也使将三维系统表示成一个二维平面，如图13 所示。但用点对点同步代替了大同步，每一个点都表示一个任务。当某个任务完成时，就通知其上方和右方任务，被通知任务将依赖计数减1，当依赖计数为0 时，即等待分配执行，不需要等斜线上所有任务完成才被分配执行。

图13 数据流模型下LU 任务依赖关系Fig.13 LU task dependencies in dataflow model

在本实验中，NPB 提供了5 种问题规模大小，分别 是S（12×12×12）、W（33×33×33）、A（64×64×64）、B（102×102×102）和C（162×162×162），每个数字是三维系统每一维方向上网格点的数目。在LU 分解中，主要的计算开销在计算上三角系统和下三角系统中，即将JACLD、BLTS、JACU 和BUTS 4 个函数任务抽象成上述数据流图形式，通过少量接口，将任务交给运行时系统。同时，通过athread 接口对4 个函数进行并行加速，区别于数据流编程模型，任务的分配调度需要手动完成，但算法并不改变。两种实现方法的从核实现采用相同的优化方法，如DMA 等，本文比较他们相较于主核单线程版本所达到的加速比。

由图14 可知，当算例规模较小时，athread 版本达到的加速比高于swTasklet 实现，这是因为当计算量和任务量较小时，任务在数据流实现中会被逐个调度到从核上，而在athread 实现中，可并行的任务会被一起预取到从核阵列上，节省了调度开销；而当规模增大时，任务较多，数据流运行时调度可以将大量任务更有效地分配给硬件资源运行，并有效平衡任务负载。当某个从核空闲，且任务队列有待执行任务时，即可立即分配执行，而athread 实现版本需要整个从核队列在某一点进行同步，然后才能进行下一次并行任务的预取和运行。实验结果表明，使用规模为B 和C 的数据集时，手动实现版本均加速13.28 倍，swTasklet 版本分别加速14.2 和15.4 倍。在C 规模下，swTasklet 版本比athread 版本快16%。由于athread 版本属于高度调优的手动优化版本，充分利用了从核阵列的计算资源，而swTasklet 与其计算性能相近，证明了swTasklet 的高效性。

图14 LU 在不同算例规模下的实现加速比Fig.14 The realize speedup of LU achieves at different problem sizes

4 结束语

本文设计并实现了新一代申威众核处理器上基于Codelet 数据流模型的运行时系统——swTasklet。用户可通过该系统提供的编程接口，将应用程序重构成基于数据流图执行方式的细粒度并行任务，交给运行时系统自动地完成任务的高并发执行和调度。本文将Codelet 机器模型中的CU 在功能上进一步细化，使主从核协作完成数据流计算任务的调度执行，解决了运行时与从核库的兼容问题，避免了从核执行开销较大的原子操作。实验证明了数据流运行时系统的有效性，采用swTasklet 提供的编程接口能够实现比athread 更高的执行效率。在未来工作中，将进一步完善该运行时系统，提高其性能和可用性，并将swTasklet 数据流运行时系统扩展到多核组上，设计性能开销更小的任务调度策略，支持使用多从核执行的计算任务。