基于架构的众核软件可靠性建模与分析

2022-06-23覃志东郝四明韦俊银肖芳雄

智能计算机与应用 2022年6期

关键词：调度可靠性处理器

覃志东，郝四明，韦俊银，肖芳雄

（1 东华大学计算机科学与技术学院，上海 201620；2 金陵科技学院软件工程学院，南京 211169）

0 引言

随着芯片制程技术的不断进步，处理器设计技术已进入到众核（Many-Core）时代。如MIT 早在2008 年就设计出64 核心的Tile64 处理器。

一方面，当晶体管的特征尺寸进入到纳米尺度并不断缩小时，生产缺陷、工艺偏差、温升和老化等因素将导致处理器的成品率和预期可靠性不断降低。所以，为构建高可靠的众核系统，需要高可靠的众核软件系统进行支撑。

但另一方面，为充分发挥众核处理器的并行计算能力，众核软件系统一般都是由很多具有通信依赖关系的任务模块构成，按照特定的优化算法映射到处理器核心上并发执行。由于任务数量众多，并发性将导致各任务及系统的执行状态更加不可预计，使得众核软件系统的可靠性预期也变差。

软件由于逻辑抽象性，其可靠性设计、测试与评估技术是滞后于硬件的。虽然软件可靠性工程已经发展了几十年了，但软件可靠性仍然是导致系统可靠性提升的瓶颈。传统单核处理器执行的软件所面临的可靠性难题，众核软件依然存在。而且，由于众核软件架构和并发执行方式的不同，原来基于单核处理器软件所建立的可靠性模型、可靠性测试方法和评估技术用于众核软件已不合适。

基于这种现状，本文在分析众核软件模型和剖析众核软件映射流程的基础上，对众核软件进行了可靠性建模。模型揭示了各任务模块和软件系统之间的可靠性关系，为后续的可靠性设计、测试与评估方法的研究打下了基础。

1 基于软件架构的典型可靠性模型介绍

为了说明不同的软件架构导致不同的软件系统与任务模块的可靠性关系，下面介绍2 种典型的基于软件架构的可靠性模型。

1.1 串并行软件系统的可靠性模型

串并行模块软件系统是一种用硬件结构来模拟软件架构的模型。其基本结构是由个并行模块组（每个模块组包括k个模块）和个串行模块组成，如图1 所示。

图1 串并行模块软件系统基本架构Fig.1 Basic architecture of a parallel-series modular software system

假设软件系统中模块的失效强度为λ（T），表示为：

其中，a、b是常量，分别表示模块中错误的平均值和检测到的错误率。

模块持续工作时长的可靠性为：

联合式（1）、（2）可以得图1 所示软件系统的可靠性：

1.2 马尔可夫链执行状态软件可靠性模型

这里，设（）为一随机过程，若（t）的状态只取决于（t）的状态，而与之前的（t）、（t）、…、（）的状态都无关，则称（）为马尔可夫链。若为离散时间变量，则为离散时间马尔可夫链（Discrete Time Markov Chain，DTMC）。一些软件在执行时，对CPU 的控制权在不同的软件模块之间转移的过程便是DTMC，如图2 所示。

图2 DTMC 执行状态软件基本架构Fig.2 Basic architecture of the DTMC executing state transition software system

用p表示模块到模块的单步控制传递概率，p∈［0，1］。因此对于模块软件系统，可得到软件的控制传递矩阵：

对于带吸收状态DTMC，吸收状态和分别表示系统执行成功和失败。在软件系统的实际运行中，当软件模块存在的缺陷被触发后就会导致系统运行的失败，使得控制由模块以概率q转向吸收状态。相反地，若软件系统执行成功，则控制由模块以概率p转向吸收状态。且控制传递概率满足：

进一步可得，在运行中的模块软件系统的运行控制传递矩阵为：

因此，可得到该系统的可靠性R为：

2 众核软件映射流程剖析

众核软件往往基于吞吐率、通信量、功耗等优化目标和限制条件，映射到各处理核心上并发执行。任务映射就是离线任务分配、调度和绑定。处于并发执行状态的众核软件的架构是不同于单处理器上经操作系统动态调度的序贯执行架构。现有的基于架构的可靠性模型不适用于众核软件。

本节首先介绍众核软件映射流程和平衡调度算法，为可靠性建模提供知识基础。

2.1 众核软件映射流程剖析

众核软件映射的基本流程如下。

（1）逻辑处理器抽象。图3（a）是一个具有4 核心的物理处理器。根据各核心的个数、互联方式、缓存的设置方式等，可以把物理处理器抽象为逻辑处理器，如图3（g）所示。其中，物理核心Core1 抽象为逻辑核心，物理核心Core3 被抽象为逻辑核心，而物理核心Core2 被抽象为逻辑核心，物理核心Core4 被抽象为逻辑核心。处理器核心很多、甚至有些坏掉了，可以根据具体情况选择一些核心使用，并将其抽象成逻辑处理器。

图3 众核软件映射流程Fig.3 Mapping process of the many-core software system

（2）数据流图分析与转换。同步数据流图（Synchronous Data Flow Graph，SDFG）常用来表示一个众核软件，如图3（b）所示。该软件由6 个任务、、、、和组成，分别实现低通滤波、傅里叶变换、数据分发、数据快插和数据融合。其中，运行一次要消耗1 单元的数据，并产生1 单元数据。运行一次要消耗32 单元的数据，并产生32 单元数据。所以，为满足软件系统的正常运行，需要连续运行32 次，才运行1 次，而需16 次，、和各需1 次；此时，通信量为32。这种调度平衡后的负载与通信常用有向无循环图（Directed Acyclic Graph，DAG）表示，见图3（c）。已有成熟算法解决SDFG 的平衡调度，平衡调度好的SDFG 可以直接用DAG 表示，供划分映射。

（3）软件向逻辑处理器分配与调度。此阶段由映射算法把图3（c）中的DAG 向逻辑处理器进行分配与调度。由图3（d）可知，假定：、、分配到，、分配到，分配到，便构成了一个3 段流水线。系统可以基于最大化该条流水线吞吐率的优化目标进行分配。单个处理核心上的任务集分配结束后，可以基于某种优化方式离线安排好相应的执行顺序，即静态调度。

（4）软件任务向处理器核心绑定。由图3 中（e）至（h）可知，分配好的任务集需要绑定到逻辑核心所对应的物理核心。如、对应的是逻辑核心，要绑定到物理核心Core3。此时，需要根据任务间的相对位置，建立通信。若2 个任务在一个核心上，那么定义数组变量，完成数据通信，如［32］便是对的通信。若两者不在一个核心上，那么要定义数据发送/接收函数；如（［1：16］，Core3）便是向所在的Core3 的缓存写数据，而（［1：16］，Core3）便是把写在本地缓存的数据读出来。显然函数是跨越处理器核心的，其通信时间是受具体通信链路决定的。为了让任务利用以及产生通信数据，还要对任务加上封装函数，如（［1：32］，［1：32］）。

（5）众核软件的流水执行模式。假定映射到的、、及其封装函数为，映射到的、及其封装函数为，映射到的及其封装函数为。那么、、所绑定的物理核心Core1、Core3 和Core4 就构成处理器核心执行流水线，处理器上的、、是并行执行的。其中，流水周期由、、三者的最大执行时间决定，即：max｛，，｝；当流水线充满后，每隔一个周期便有一个系统输出。该流水线的时空图如图4 所示。

图4 众核软件流水线执行的时空图Fig.4 Executed spatio-temporal diagram of the pipeline for many-core software

2.2 SDFG 的周期平衡调度

SDFG 描述的众核软件如图5 所示。图5 中，节点代表任务，任务按字母顺序编号；箭头代表弧（任务之间的输出输入关系），弧的箭尾上的数字，代表前一个任务执行一次产生的数据资源，箭尖的数字代表下一个任务执行一次所需要消耗的数据资源。弧上方框里的数字代表了弧的编号。

图5 多链结构SDFGFig.5 Structure of the multi-chains SDFG

显然，当满足产生与消耗的数据量平衡时，这个SDFG 表示的众核软件才能正常执行下去。所以，当众核软件执行时，每个任务需要按照一定的次数重复执行；而单个任务重复执行的次数越多，代表分配到处理核心的执行负载越大。则在任务向处理核心分配前，需要对SDFG 进行平衡调度，从而得到满足通信量平衡时每个任务模块具体执行次数，并间接得到负载量。

SDFG 的周期平衡调度已有多种成熟算法。本文介绍文献［8］中方法。首先，SDFG 用与有向图相关联的拓扑矩阵来表示：行对应弧；对应任务节点。第（，）项表示第个任务节点调用一次，其在弧上产生的数据流。若是消耗，数值为负；若没有在弧上，则为0。图5 的拓扑矩阵如式（8）所示：

若拓扑矩阵的秩-1（为节点的数量），则表示该SDFG 上能构造周期性可允许的顺序调度。对图5 的拓扑矩阵矩进行初等行变换，得：

矩阵的秩5。等于-1，则可以构造周期性均衡循环调度。具体构造方法是求解满足0的向量。例如，拓扑矩阵（9）对应的向量为：

向量中对应的元素为相应任务调度在一个循环周期中被激发执行的次数。

3 众核软件可靠性建模

3.1 SDFG 向DAG 转换

显然，只有对SDFG 进行均衡调度后，才能知道一个具体的任务在一个循环周期中对处理核心产生的负载量是多少。可以把调度好的软件转换为由DAG 来刻画。例如图5 给出的SDFG 向DAG 转化结果如图6 所示。其中，任务在一个周期循环中，需要激发执行8 次，每次占用处理核心5 单位时间，总共占用40 单位时间；那么用任务来代表整体执行8 次的，于是就形成了右边的DAG 图。

图6 SDFG 转化为DAGFig.6 Conversion of SDFG to DAG

3.2 众核软件可靠性建模

当流水充满后，每过时间便会有个输出。定义核心上任务集运行一次的时间与周期的比：

核心上任务是分时独占处理核心资源的，第个任务占用比例为：

当处理器稳定工作一段时间以后，处理核心上任务集运行的总时间为：

整个软件系统在时间段内不失效，则必须满足所有核心上工作的任务集在其执行期间不失效。则系统可靠性可以表示为：

将式（15）代入式（17），可得：

将式（18）代入式（16），可得：

又因为，R()＝e，则有：

又因为，R()＝e，R()＝e，所以：

将式（14）代入式（12）得到：

式（23）便是SDFG 所示软件系统的可靠性模型。

设任务A在一个周期内被调度执行的次数为d（可由得到），运行一次的时间为T，则有：

将式（24）代入式（13），可得k：

4 实验及结果分析

图7 即为一SDFG 表示的众核软件系统，及其被映射到的逻辑处理器核心的情况。表1 是其各个任务模块的参数。

图7 一个众核软件系统例子Fig.7 An example of the many-core software system

表1 众核软件的任务模块参数Tab.1 Parameters of task modules in the many-core software system

由表1 可知，模块的执行时间比例是最高的，而模块的执行时间比例是最低的。将其它模块的总失效率之和设为0.0001 个/h，利用R（）＝e和式（23），分别对模块和的失效率变化所导致对系统可靠性的影响进行了数值模拟，结果如图8 所示。

图8 系统对任务模块可靠性变化的敏感性仿真Fig.8 Sensitivity simulation of the system to reliability change of a task module

由图8 可知，随着任务模块失效率的增加，系统可靠性R降低得更快，表明R对的失效率变化非常敏感。但是，随着任务模块的失效率的增加，系统可靠性R基本没有变化，说明R对的失效率变化不敏感。由于执行时间比例是远远大于的，也就表明了执行时间比例高的任务模块对系统可靠性影响大。所以，可以通过本文所建立的众核软件可靠性模型，识别出对系统可靠性影响大的模块，并采取措施切实提高这些任务模块的可靠性，如此就可以有效确保整个软件系统的可靠性。