环网处理器阵列的容错重构技术

发布时间：2019-09-25 12:30

【摘要】：高效的容错技术对于提高多处理器系统的可靠性至关重要。环网(Torus)是连接多处理器阵列的重要网络结构,而环网处理器阵列上的容错重构技术目前尚属空白。针对环网阵列的特殊连接方式,将环网阵列重构问题转化为矛盾图上求解最大独立集问题。矛盾图上的结点表示故障处理器的替换方案,而边代表了不同替换方案之间的不可共存特性。主要是根据三种不同的冗余处理器分布方案,设计生成矛盾图算法,求解最大独立集算法,以及由独立集生成逻辑处理器阵列算法,取得了令人满意的结果。实验结果表明,当阵列规模较小或故障率较低时,一行一列和十字型的冗余单元分布的重构能力较好;而随着阵列规模或故障率的增大,三种冗余单元分布策略的重构成功率都随之下降,但可通过增加冗余单元以及调整冗余分布来改善容错效果。此外,从实验结果中还可以看出,环网处理器阵列的容错能力显然优于网格(Mesh)处理器阵列。
【图文】：

可重构结构

所示是一个规模为２×３的环网处理器阵列，在其上一行和左一列集成了冗余单元。容错重构的功能是通过向阵列中插入开关和连线实现的，开关和连线将每个处理单元连接在一起，从而使得阵列可以灵活地改变处理单元之间的连接方式。其中开关单元具有三种状态，这些状态可以根据阵列的需求进行切换。为了单独考虑处理单元的重构情况，本文做出了如下假设：（１）故障单元能够转化为连接单元，即连线；（２）开关单元、连线及冗余单元均不含故障。Ｆｉｇｕｒｅ１Ｒｅｃｏｎｆｉｇｕｒａｂｌｅａｒｃｈｉｔｅｃｔｕｒｅ图１可重构结构多数文献都采用假设（１）；而假设（２），因为开１４２４ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ＆Ｓｃｉｅｎｃｅ计算机工程与科学２０１５，３７（８）

补偿通道

布的不同，每个故障单元可能有着不同个数的补偿通道。当冗余单元的分布如图１所示时，每个故障单元在理论上有两个可能的补偿通道，其方向分别是向上、向左，用［ｘ－，ｙ］、［ｘ，ｙ－］来表示。类似地用［ｘ＋，ｙ］、［ｘ，ｙ＋］表示补偿通道的方向向下、向右。（２）相邻。所谓水平方向的相邻关系是指两个水平补偿通道［ｘ１，ｙ－１］、［ｘ２，ｙ＋２］满足｜ｘ１－ｘ２｜＝１，，且ｙ１＞ｙ２，同理可定义竖直方向的相邻关系。图２ａ所示的两条补偿通道为非相邻情况，而图２ｂ中所示的为相邻情况。Ｆｉｇｕｒｅ２Ｒｅｐｌａｃｅｍｅｎｔｐａｔｈｓ图２相邻和非相邻补偿通道（３）相交。包括两种情况：①两个故障单元不在同一行或同一列上；②两个故障单元位于同一行或同一列上。图３ａ所示为两个故障单元既非同一行，也非同一列，图３ｂ所示为两个故障单元位于同一行。Ｆｉｇｕｒｅ３Ｉｎｔｅｒｓｅｃｔ图３相交２．２问题描述及以往研究工作问题Ｒ给定一个规模为ｍ×ｎ的环网连接的物理阵列Ｈ，Ｈ中还包含一定数量的冗余处理器单元。当Ｈ中部分处理器发生故障时，利用冗余处理器单元对故障处理器单元进行替换，得到一个ｍ×ｎ逻辑阵列。为了构造有效的逻辑阵列，原始的ｍ×ｎ的物理阵列中所有故障单元都必须能够被冗余单元所替换，并且替换补偿通道间不能出现相交和相邻的情况。如图４所示，当故障单元ｕ向右进行补偿，故障单元ｖ向左进行补偿时，即为所定义的相邻情况，此时需要使用双通道进行布线才能实现（圆圈标记处），而本文所研究的是在单通道的情况下，因而不允许存在相邻情况。由于环网在水平和垂直方向上都
【作者单位】：天津工业大学计算机科学与软件学院;天津大学计算机科学与技术学院;
【基金】：国家自然科学基金资助项目(61173032);国家自然科学基金天元青年基金资助项目(11326211)
【分类号】：TP332;TP302.8

【共引文献】