面向可重构片上网络的缓存可靠性分析

李思照， 姜宏睿， 韩新宇， 赵 欢

1. 哈尔滨工程大学计算机科学与技术学院, 哈尔滨 150001

2. 北京轩宇信息技术有限公司, 北京 100190

0 引 言

目前学术界对芯片多处理器(CMP)的缓存一致性及其协议进行了大量的研究，在读取操作时如何确保写入的值是最新对于操作的正确性尤为重要[1].因此，当一致性问题被视为与编程模型相关的全局问题时，一致性协议对于确保硬件级别的正确性是很有必要的[2].

有人提出了几种基于总线的缓存一致性协议监控模型，它们通常采用写更新和写失效操作来保证数据的一致性[3-4].如新的状态记录一些处理器不需要更新的数据，并通知共享内存不更新这些处理器中的缓存行，从而减少了写入更新的次数，大大提高了总线效率[3].虽然此方案减少了写入更新的次数，但是无效的写入不一定会在总线上传输.当有学者提出了与记录无效缓存行有关的协议后，使用新状态记录无效的缓存行[4],这个方法可防止总线上的无效数据广播.上述两种方案都已在相应的多处理器体系结构上实现.

在之前的工作中已经提出了HCS结构[5]，但并没有讨论一致性协议在这个体系结构中的应用.因此，本文以HCS结构为例，建立数学模型，验证缓存一致性协议在HCS结构上的可行性.

现代微处理器的设计涉及3个关键方面：功率、片上存储和可靠性.在这项工作中，将建立数学模型来描述高速缓存一致性协议的可靠性，并利用这些模型来验证上述缓存一致性协议在HCS架构上是否可行.

为了计算缓存一致性协议的可靠性，文献[6]已经提出了一个模型.本着相似的精神，本文探讨了两种模型：故障树分析(FTA)和贝叶斯模型.两种模型都能描述网状结构的可靠性.由于根据失效过程的先后顺序，可靠性分析可分为事前分析、过程分析和事后分析，因此，在本文中选择过程分析法来分析系统可靠性.

本文的其余部分安排如下：第1节描述了多处理器体系结构的缓存一致性协议，并解释了HCS网络和EB网络之间的区别.第2节介绍了多处理器系统的可靠性分析.在第3节中，提出了多处理器上高速缓存一致性协议的可靠性模型.第4节是模拟结果和讨论.最后，第5节对全文进行总结.

1 多处理器体系结构的缓存一致性协议

本节讨论CMP体系结构.在早期的设计中，图1所示是一个普遍采用的总线架构.然而，随着核心数量的增加，总线体系结构的效率大大降低，促使研究者们多采用基于网络的体系结构.在这项工作中，分析了一个64核网格结构的可靠性.

图1 总线架构

1.1 多处理器网状结构

图2中显示了HCS网络结构.此网络由三个部分组成：网络接口(NI)、管道通道和交换机.

图2 HCS和缓存结构

在所示的体系结构中，每个生成数据包的网络接口都连接到L1本地缓存，并且所有处理器都有一个共享内存.管道通道通过先进先出(FIFO)通道存储网络接口生成的数据包.交换机由1个路由端口组成：一个用于网络接口，4个用于传输.数据仲裁器选择要传输的管道信道中的数据包.

HCS网络中的链路与EB网络中的链路不同.如图3(a)所示，EB网络中的链路使用的是串行触发器(FF)[7].相比之下，HCS方案的管道通道是通过并行FFs构建的，如图3(b)所示.EB和HCS通道控制器都使用4个FFs连接.需要注意的是，如果EB信道产生一个单点故障，也就是其中单个FF的故障可能会导致中断所有通信，而在HCS通道结构中，如果一个FF出现故障的话，是不会影响其他通路的控制.因此，链路RL的可靠性将基于此结构进行计算.

图3 串行触发器和并行触发器

1.2 缓存一致性协议

在HCS和EB网格结构中，如何保证数据一致性是一个关键问题.如果数据在LLC(低级缓存)中被修改，那么它也必须立即在HLC(高级缓存)中修改.在多处理器中，如果HLC没有传输到LLC，最终就会因为数据不一致而导致程序错误，这样系统会产生错误的结果，从而导致整个系统运行错误甚至崩溃.因此，解决缓存一致性问题是迈向可靠性的重要一步.在本文中，将分析不同协议下的系统可靠性.

1.2.1 Write-Once

Write-Once协议[8]是最早的写入无效协议之一.它包括写回和写通过.协议在每个节点中定义4种状态来标识缓存行的当前状态：无效状态(Invalid)、有效状态(Valid)、脏状态(Dirty)和保留状态(Reserved).无效状态表示当前缓存行不包含有效数据.有效状态表示当前数据是LLC中的最新数据，HLC中有缓存行的副本，其他核心的缓存行中可能有副本.保留状态也表示当前缓存的数据是最新的，HLC有一个缓存行的拷贝数据，但是在其他核心上并没有缓存行的拷贝数据.脏状态表示块中数据是唯一的副本，与主内存或任何其他缓存行都不一致.

在此协议当中，保留状态是一个对整体系统可靠性有所影响的不确定状态，此状态虽然是当前缓存中的最新数据，但是由于数据更新时可能会导致缓存数据中的数据没有及时地得到更新，CPU会认为当前缓存中的数据仍然是最新的，这样就会对最终的结果产生影响.

1.2.2 MESI和MOESI

MESI[9]是一种广泛用于支持回写策略的缓存一致性协议.顾名思义，它也定义了4种状态：修改状态(Modified)，共享状态(Shared)，独占状态(Exclusive)和无效状态(Invalid).

在修改状态下，数据只存在于当前LLC中，与HLC不同.独占状态下，数据仅存在于当前的LLC中，但数据与HLC是保持一致的.在共享状态下，数据可以存储在其他缓存中，并且与HLC一致.最后，无效状态描述了一条无效的缓存行，类似于Write-Once协议.MESI解决了Write-Once当中的保留状态的问题，但是却存在着当前缓存数据最新，但不能保证其他缓存中的数据最新的问题，因此，学者们根据这样的问题提出了MOESI协议.

MOESI协议[10]与MESI相似，但是它增加了另一个状态：自有状态(Owned).在这种状态下，块中的可用数据是最新的，并且在其他本地缓存或LLC中必须有此数据的副本.但是，只有状态为“自有”时的缓存才能修改数据.

2 系统可靠性分析

本文中探讨了CMP网络的可靠性.首先，使用故障树分析(FTA)来建立常见的多处理器模型的可靠性模型，例如总线结构，然后，利用贝叶斯公式对HCS网络进行了分析.

2.1 失效模式及可靠性函数

当一个处理器不能完成它的功能时，它被称为一个失效的处理器.可以用概率来描述系统的可靠性.

首先介绍了以下3个关键概念：

定义1.利用(t)函数来表示多处理器Rmp(t)的可靠性.如果T代表协议寿命，则事件(T>t)表示系统可以在[0，t]时间段内无故障工作.

(1)

如果事件指示系统寿命小于t，则在[0,t]中失效.因此，Fmp(t)=Pr(T≤t)称为多处理器的故障分布函数，

(2)

如果这个概率密度函数Fmp(t)已知，那么当给定值t时，可以计算Rmp(t).

(3)

式中，Rmp(t)是状态在时间间隔(0，t]内的无故障概率.特别需要注意以下几种特殊情况，Rmp(0)=1,Rmp(∞)=0,Fmp(0)=0，Fmp(∞)=1.注意，随着t值的增加，失效的可能性也随之增加，无故障工作时间也逐步减小.

定义2.系统故障率，是指在时间t时开始发生故障，经过Δt的时间间隔完成故障的发生，因此故障发生在时间间隔(t，t+Δt]内，表示为zmp(t).

(4)

定义3.系统寿命指的是故障发生前的总工作时间.因此，平均失效时间(MTTFmp)也是系统寿命的期望值，

(5)

假设缓存一致性协议的失效时间为T，如果它在tstart=0开始工作，并且一直工作到时间t，那么在时间x中，协议的可靠性就为

Rmp(x∣t)=Pr(R>x+t∣T>t)=

(6)

2.2 系统分析

该系统由许多组件组成，这些组件根据特定的生产目标进行连接.系统的可靠性取决于其组件和系统结构的可靠性.在给定组件故障数据和系统结构的情况下，系统分析的目的是通过可靠性指标(例如故障概率)来预测系统的可靠性.在本节中，使用FTA分析系统可靠性.

首先将讨论各个系统的拓扑结构分析：

2.2.1 串行系统

在串行系统中，任何单元的故障都可能导致整个系统的故障.以Write-Once为例，假设系统中第i个处理器的寿命为ti(i=1,2,…,n)，并且t1,t2,…,tn彼此独立.可以从等式(1)获得第i个处理器的可靠性

Rmp(t)=P|ti>t|(i=1,2,…,n)

(7)

式中，t是规定的工作时间.由于系统的连续性，它的寿命是τ=min(t1,t2,…,tn)，因此系统可靠性可表示为

Rmp(t)=P|τ>t|=

P|t1>t,t2>t,…,tn>t|=

(8)

如果第i个处理器的故障率为λi(t)，则单元可靠性为

(9)

由式(8)和(9)，系统可靠性可表示为

(10)

(11)

这一分析揭示了3个关键点.首先，串联系统的可靠性Rs(t)等于单元可靠性Ri的乘积.其次，串行系统的可靠性Rs(t)小于或等于系统中最不可靠单元的可靠性.最后，由式(11)可知，当元件数n增加时，MTTFs减小，即当串联系统中单元数增加时，系统可靠性降低.

2.2.2 并行系统

一个系统被称为并行系统，如果整个系统在所有单元发生故障时发生故障.

以MESI和MOESI为例，假设系统中第i个处理器的寿命是ti(i=1,2,…,n).它们彼此独立.第i个处理器的可靠性可以描述为Rmp(t)=P|ti>t|(i=1,2,…,n)，假定初始时间t=0，则所有装置正常，并在完全相同的时间开始运行.并联系统的寿命为τ=max(t1,t2,…,tn).因此，系统可靠性可以表示为：

Rmp(t)=P|τ>t|=

1-P|t1≤t,t2≤t,…,tn≤t|=

(12)

当第i个处理器故障率为zi时，系统可靠性为：

(13)

从式(13)展开，将得到

(-1)n-1e-(z1+z2+…+zn)t

(14)

因此，并联系统的平均故障时间为

(15)

因此，从式(13)可以看出，并联元件越多，可靠性越高.

2.2.3k-端可靠性功能描述

故障树模型不能准确描述网格结构，因此可以通过k-端可靠性模型来评估网络的可靠性.

图G=(U，E)由两个集合组成：U是节点集，E是边集.如果连接了两个节点u1,u2，则路径e正在工作.如果一组k节点(k⊆V,V是网络中的所有节点)中每对节点的路径都是有效的，如果这些节点是连接的.这些工作路径是：工作路径.k工作路径包括直接或间接连接到k节点的边.因此，k终端可靠性是每对k个节点之间至少存在一个k工作路径的概率.网络的可靠性为:R(G，Φ，ψ), Φ→[0,1]为节点发生故障的概率，ψ→[0,1]为边缘发生故障的概率.

3 缓存一致性协议的可靠性模型

通过对系统可靠性的定义，得到了可靠性模型所需的数值，同时，利用此方法建立了k-端网络模型.以下是建模过程，并进行了讨论，以确保模型的正确性.

3.1 基于HCS网络结构的可靠性模型分析

HCS是具有对称结构的，每个网络接口具有相同的权重，最小的子系统可视为2×2网格结构.在计算了该子系统的可靠性之后，可以将这四个节点视为一个新节点，可以继续使用此方法来计算4×4网格的可靠性，如图4所示.最后，可以计算出来一个8×8的可靠性网格.得出了网络的可靠性之后，可以在HCS或EB之上实现缓存一致性协议.

图4 网格构建过程

3.2 2-端可靠性模型

k-端可以描述k个节点之间的网络可靠性，因此2-端可以描述两个节点之间的可靠性.要计算系统可靠性(包括所有节点对的可靠性)，可以使用2-端的可靠性模型.图5描述了节点的可靠性的计算.在图5中，说明了各个网络接口的可靠性计算过程.其中，RL为网络结构中边通道的可靠性，RN为网络结构中节点的可靠性.

首先，计算网络接口1对网络接口2的可靠性：

第1步. 当所有链接均正常工作时，可靠性为：

R(1，2)1=R2×(RL1×RL2×RL3×RL4).

第2步. 仅链接X1工作，而链接X2，X3，X4出现故障，可靠性为：

R(1，2)2=R2×RL1×[(1-RL2)×(1-RL3)×(1-RL4)]

第3步. 当链接X1出现故障而其他链接正常时.

R(1，2)3=R2×(1-RL1)×RL2×RL3×RL4

下面计算网络接口1至网络接口3：

第4步. 与第一步类似，所有链接均正常工作，可靠性为：

R(1，3)1=R3×(RL1×RL2×RL3×RL4)

第5步. 从网络接口1到网络接口3有两条路径，当其中一条发生故障而另一条正在工作时，可靠性为：

R(1，3)2=R3×(RL1×RL2)×[(1-RL3)×

(1-RL4)]

第6步. 如果这两条路径的状态发生变化，则可靠性为：

R(1，3)3=R3×[(1-RL1)×(1-RL2)]×(RL3×RL4)

最后，网络接口1至网络接口4与网络接口1至网络接口2相同，如图5(g)(h)(i)所示.最后，整个系统的可靠性是所有节点的可靠性，因此该子系统的可靠性为Rs=4×RNI1.但是此计算过程具有重复的路径，因此在最后必须除以2以消除重复路径.

图5 2×2网格到4×4网格的过程

为了评估EB和HCS的可靠性，需要计算RL的值.由于EB通道具有串行触发器，因此其可靠性为RLE=(RF)4.对于HCS网络中的流水线通道，RLH=1-(1-RF)4.在这些网络中，所有节点和路径都相同，因此RN=R1=R2=R3=R4和RL=RL1=RL2=RL3=RL4.

4 仿真结果和讨论

本节将Write-Once，MESI和MOESI 3种一致性协议部署在HCS网络中，通过在Virtex-7 FPGA平台下进行验证比较.

图6和图7分别表示3种协议随着时间变化的可靠性和故障率.基于此模型，可在HCS网络结构中进行可靠性评估.

图6 可靠性功能曲线图

现在建立了HCS可靠性模型，并将其与总线结构进行比较.总线结构是串联系统，所以RB=R4×(RL1×RL2×RL3).

在不同的时间，通过图6提取了可靠性值.为每个节点选择的值(Write-once, MESI, MOESI)是：

RN1=(0.90,0.95,0.96),

RN2=(0.80,0.90,0.92),

RN3=(0.70,0.82,0.85)，

RN4=(0.60,0.79,0.83).

这些值代表的节点如图6所示，并假设RF=0.9.可以得到RLE=0.81和RLH=0.9999.图8显示了HCS中4节点中每个节点的可靠性.这4节点可以看作是一个新节点.其中4超级节点可用于分析16个节点的HCS.通过这个方法可以推论整个64个节点的可靠性.

图8 HCS中4个节点的子系统可靠性

图8所展示的是4节点的可靠性.

评估结果如图9所示.可以看到HCS结构的可靠性要优于EB和总线结构.同时MOESI的可靠性要比其他模型高的多，这也符合本文的分析.

图9 HCS，EB和Bus之间的缓存一致性协议的可靠性的比较

5 结 论

在这项工作中，提出了一个缓存一致性可靠性模型，而且也比较了HCS网络，EB网络，总线结构的可靠性.在以往的工作中，很少有人使用此方法来分析系统可靠性，因此，提出了一种基于高速缓存一致性的多核系统可靠性协议的模型.

在本文中，扩展了先前的研究，并通过一种数学方法，建立了3种高速缓存一致性协议的可靠性模型.这项工作将有助于提高硬件设计的可靠性.通过使用k-端面模型来分析片上网络结构，获得可靠性结果.结果显示在第4节的图6中，由图可知，MOESI可靠性最高.但在图7中，在t等于6.23×106之前，MESI的故障率要远低于MOESI.现在，尽管大多数硬件系统都使用MESI协议，但尚未进行数学验证.HCS网络比EB和总线结构更可靠.因此，基于这些结果，未来的工作将把研究重点放在HCS网络上，例如，将对内存管理，进程调度等方面进行研究.同时，在未来的工作中，将针对片上网络处理器有限资源问题，对其任务进行更加高效的调度，并且分析软件的行为特性，如何更加有效的在片上网络中运行也会成为研究重点.

致谢作者要感谢他们的实验室团队成员的帮助.这项研究得到了黑龙江省自然科学基金的资助.黑龙江省自然科学基金(优秀青年项目)，批准号：JJ2019YX0922.