NMR系统通信复杂性的分析与优化
范剑波1，徐利浩 2
(1.宁波高等专科学校 电子技术系，浙江 宁波 315016；2. 美国华盛顿大学
计算机科学系，MO 63130，USA )
摘要：本文针对传统表决算法通信复杂性高的问题，提出了将现有的ECC（Error Correcting Codes）用于表决问题的算法，极大地减少了通信复杂性，取得了与传统表决算法同样的效果，从而实现了NMR（N Modular Redundant）系统通信复杂性的优化。
关键词：NMR系统；通信复杂性；表决算法
1. 引言
分布式表决的通信复杂性在可靠性计算中是一个重要的问题。在一个NMR系统中，N个计算模块执行同一个任务，并且需要在当前计算状态上通过表决周期地进行同步，然后所有模块将当前计算状态设置为多数表决结果。若多数结果不存在，则所有模块也可从先前结果中进行重新计算。表决技术对基于任务复制检查点[12]来说是一个必要的工具，在分布式存储系统中也能用来保持复制数据的一致性。
表决算法的许多方面已经被研究，如：数据逼近、可重置的表决、表决权的动态修改和基于元数据的动态表决[3][5][9]，本文主要研究表决问题的通信复杂性。一些传统的表决算法已经被提出用来减少通信复杂性[4][7]，这些算法之所以是非确定性的是因为他们在本地计算结果的签名上执行表决。近年来，Noubir等人[8] 提出了基于错误控制码的多数表决模式：每一模块先将本地结果编码成EDC（Error Detecting Codes）的码字且发送码字的一部分，再使用检错码来检测本地结果的差异，最后通过重新传输完全的本地结果来作出多数表决决定。基于EDC的多数表决模式可以减少通信复杂性，但是EDC本身并不能帮助来减少表决算法的通信复杂性，它只是具有码的检错能力。而ECC本身具有码的纠错能力，所以它能用来帮助减少表决算法的通信复杂性。虽然EDC在许多方面得到了应用，如：可靠分布式的数据复制[1]等，但考虑到ECC较EDC有更好的特性，因此我们将ECC用于表决问题来减少通信复杂性，并能取得与传统表决算法同样的效果。
本文主要解决：（1）利用码的纠错和检错能力来极大地减少每个模块重新传输全部本地结果的机会，从而可以极大地减少通信复杂性；（2）证明ECC表决算法可以象传统表决算法那样获得同样的表决结果；（3）通过选择纠错和检错码的参数，可以取得最优的平均通信复杂性。
2. 传统表决算法的通信复杂性
2.1 NMR系统的几个概念
（1）通常一个NMR系统包含N个经通信介质相连的计算模块。对一给定的计算任务，每一模块执行同样一组具有独立计算错误概率p的指令。通信介质可能是总线、共享内存、点到点网络或广播网络。这里我们取通信介质为一个可靠的广播网络，即：每一模块能用无差错通信操作发送它的计算结果到所有其它的模块。
（2）NMR系统的通信复杂性被定义为：在一个任务的整个执行过程中经过通信介质发送的二进制总位数。在一个广播网络，令mij为第i个模块在一个任务执行的第j轮通信时所发送的位数，N是该NMR系统的模块数，k是完成这个任务所需要执行通信的轮数，则该任务的通信复杂性为：
（3）在一个NMR系统中，为得到给定任务的最终结果，需在每一模块分别完成各自的计算后与其它模块就结果通过表决进行同步。记Xi为第i个模块的本地计算结果，N为奇自然数，Ф是一个不同于所有可能计算结果的任一事先定义的值，则表决函数被定义为：
2.2传统表决算法的通信复杂性
一个NMR系统的表决结果是每一模块得到Majority(X1,···,XN)作为它的最终结果，这里Xi（i=1,···,N）是第i个模块的本地计算结果。表决问题的一个简单算法就是在每一模块计算此任务以后广播它自己的结果到所有其它的模块。当一个模块收到所有其它模块的结果时，此模块就在本地执行表决函数来得到结果。此算法描述如下：
算法1 传送-全部表决
For Module Pi ，i ∈ [1:N] :
Broadcast（Xi）;
Wait Until Receive all Xj , j ∈ [1:N] \i ; （其中\i表示不包括i）
X : = Majority(X1,···,XN);
Return(X);
在多数情况下，一个模块有计算错误的概率是相当低的，即：在多数情况下，所有模块将有同样的结果，这样每一模块只需广播它结果的一部分。若所有的结果是相同的，则每一模块将同意这个结果。若否，则模块仍使用算法1。这样得到改进的表决算法如下：
算法2 传送-部分表决
For Module Pi ，i ∈ [1:N] :
Partition the local result Xi into N symbols: Xi[1:N];
Broadcast（Xi[i]）;
Wait Until Receive all Xj[j]
, j ∈ [1:N] \i ;
X : = X1[1] *···* XN[N]; （其中*表示字符串的串联操作）
Fi : =（X = Xi ）;
Broadcast（Fi）;
If Majority(F1,···,FN)
= TRUE
Return(X);
Else
Broadcast（Xi[j]），j
∈ [1:N] \i ;
Wait Until Receive all Xj , j ∈ [1:N] \i ;
Return(Majority(X1,···,XN));
[例1] 若X1= X2= X3= X4=00000，X5=10000，则采用算法1需做一轮通信且总计要传送25位。另外若采用算法2，需做二轮通信且总计要传送10位。若X5=00001且其它Xi不变，则采用算法2需做三轮通信且总计要传送30位。
从上可知：算法1只需要一轮通信且通信复杂性总是Nm。算法2根据Xi的不同而需要二轮或三轮通信且通信复杂性可能是m+N或Nm+N；算法2的Else部分实际上是算法1；在算法2中，通过在表决标记Fi上的广播和表决去除了得到错误表决结果的机会。如果算法2的Else部分不是太经常地被执行，则通信复杂性能从Nm减少到m+N，并且在大多数情况下m>>N，这样m+N≈m。因此减少通信复杂性的主要思想在于减少执行算法1的机会。在大多数计算环境中，每一模块有很低的计算错误概率p，这样最可能的是：所有模块或者（1）得到同样的结果或者（2）只有少数得到不同结果。在情形（1），算法2有低的通信复杂性（即：m+N），但在情形（2），实际执行了算法1且通信复杂性是高的（即：Nm+N），但如果我们能检测并纠正这些局部模块结果的差异，则算法2的Else部分就不需要被执行，这样通信复杂度还是低的。这个检测和纠正的能力可通过使用纠错码[6][10][11]来实现。
3．ECC表决算法及其通信复杂性
在表决问题上使用纠错码能减少通信复杂性。其基本思想是不直接广播它自己的计算结果Xi，而是第i个模块首先将它的结果Xi编码成某种码的码字Yi，然后广播该码字的一个符号到所有其它的模块。在收到所有其它码字的符号后，再将它们重组成一个矢量。若所有模块有同样的结果，即：所有Xi是相等的，则接受的矢量就是结果的码字，这样它能再被译码成结果。若多数结果存在，即：Majority(X1,···,XN)≠Ф，并且存在t（不超过N/2的整数部分）个其结果不同于多数结果X的模块，则来自所有这些模块的符号被当作关于多数结果的错误符号。只要码被设计成能纠正直到t个错误，这些错误符号就能被纠正得到相应于多数结果的码字，这样算法1就不需要被执行。若多数结果不存在，即：Majority(X1,···,XN)=Ф，则每一模块得到的矢量还是能被译码成一个结果。
3.1 基于ECC的表决算法
借助于一个恰当设计的能检测直到d个且纠正直到t个错误符号（0≤t≤d）的纠错码，则其相应的表决算法可以描述如下：
算法3：ECC表决
For Module Pi ，i ∈ [1:N] :
Yi : = Encode(Xi)，Partition Yi into N
symbols: Yi[1:N];
Broadcast（Yi[i]）;
Wait Until Receive all Yj[j] , j ∈ [1 : N ] \i ;
Y : = Y1[1] *···* YN[N];
If Y is undecodable
Execute Algorithm 1; ---------------------分支③
Else
X : = Decode(Y);
Fi : =（X = Xi）;
Broadcast（Fi）;
If Majority(F1,···,FN)=TRUE
Return(X); ----------------------------分支①
Else
Execute Algorithm 1; ------------------分支②
注意到这里在运行算法1时，每个模块Pi并不需要发送它的整个结果Xi，而只需要发送它的码字Yi的另外N-(d+t)-1个符号。因为码被设计成可检测直到d个和纠正直到t个符号，所以它能纠正直到d+t个疑符，这样Yi未发送的d+t个符号能被当作疑符且可被恢复，因此原始的Xi可从Yi通过译码得到。下面的例子将说明该算法是如何工作的。
[例2] 在一个NMR系统中有五个模块，且任务结果有6位，即：N=5，m=6。这里使用具有ECC特性的奇偶码[2]将6位信息划分成3个符号并且将信息符号编码成一个5符号的码字。这种码能纠正1个错误符号，即：d=t=1。现在如果Xi=000000（i=1,2,3,4），X5=000011，则采用奇偶码得到：Yi=0000000000（i=1,2,3,4）,Y5=0000111101。在每一模块广播该码字的一个符号（即：2位）后，重新装配的矢量是Y=0000000001。因Y只有一个错误符号，故它能被译码成X=000000。从算法3我们能看到：Fi=1（i=1,2,3,4），F5=0，这样Majority(F1,···,F5)=1，因此X=000000就是多数表决结果。在这种情况下，算法3需要二轮通信且通信复杂性为15，而算法1总是需要一轮通信且通信复杂性为30，算法2则需要三轮通信且通信复杂性为35。
3.2 算法的正确性
从算法3可以看出，在Fi上进行表决可确保不会抵达一个错误的表决结果，并且在最坏的情况下可转向执行算法1，从而保证可以得到存在的表决结果。这样算法3就能给出一个正确的多数表决结果，其正确性证明如下：
定理1：对于给定的一组本地计算结果Xi（i=1,···,N），算法3给出了多数表决结果Majority(X1,···,XN)。
证明：从算法3容易看到，该算法终止在下列二种情况：
（1）运行传送-全部表决的算法：这正确的多数表决结果一定可以达到。
（2）返回一个X：在此情况下，因为Majority(F1,···,FN)=TRUE，即：Xi的多数等于X，X就是多数表决结果。
为了看清在不同本地结果Xi的情况下算法3是如何工作的，我们给出了该算法的二种观察情形，这也有助于分析算法3的通信复杂性。
观察1：若Majority(X1,···,XN)=φ，则算法3输出φ，即：算法3决不会给出一个错误的表决结果。
证明：从算法3容易看到在完成第一轮通信后，每一模块得到同样的表决矢量Y。根据Y的译码能力可分为二种情况：
（1）
若Y是不可译码的，则运行传送-全部表决的算法，并且输出将是φ；
（2） 若Y是可译码的，则现在的译码结果X能被当作参考结果。但是由于不存在一个多数表决结果，故Xi的多数不会等于X，即：Majority(F1,···,FN)=FALSE，因此传送-全部表决的算法被运行且输出还是φ。
观察2：若Majority(X1,···,XN)=X（≠φ），则算法3输出就是X，即：算法3一定会得到多数表决结果。
证明：假设存在e个其本地结果不同于多数结果X的模块，则有
（1） 若e≤t，则在关于多数结果X的相应码字的表决矢量Y中存在e个错误符号，所以Y能被正确译码成X，并且Xi的多数等于X，即：Fi的多数为1，因此输出的就是正确的多数结果X。
（2） 若e>t，则Y或者不可译码或者不正确地译码成其它的X′，这里X′≠ X。在每一种情况均执行传送-全部表决的算法且达到正确的多数结果X。
4．通信复杂性分析
4.1 算法3的通信复杂性
从算法3可以看出：若算法终止在分支①，即：算法得到多数结果，则通信复杂性为N(k+1)；若算法终止在分支②，则通信复杂性为N(m+1)；最后若算法终止在分支③，则通信复杂性为Nm，这样最坏情形的通信复杂性Cw为N(m+1)。当m>>1时，Cw≈Nm。
4.2 算法3的平均通信复杂性
记Ca为算法3的平均通信复杂性，定义平均减少因子α=Ca/(Nm)，则下列定理给出了α与NMR系统的参数和相应代码之间的关系：
定理2：对一个具有N个模块的NMR系统，每一模块运行同一个有m位结果的任务且有独立于其它模块活动的计算错误概率p，若算法3使用能检测直到d个和纠正直到t个错误
符号的纠错码的话，并且m>>N>1，则下列关系表示算法3的平均减少因子：
证明：为了得到算法3的平均通信复杂性Ca，我们需要分析在分支①②③算法终止的概率Pi(i=1,2,3)。首先假设若一个模块有一个错误的结果Xi，则它将一个错误符号传送给表决矢量Y。从观测2的证明中可以看出：若算法3终止在分支①，则至多t个模块有计算错误，这样此事件的概率就是P1。而算法3终止在分支②的概率P2可表示为：
因为上面不等式右边第二项正好是可纠正错误所发生的事件的概率。最终P3是译码失败事件的概率，即：P3=1-P1-P2。现在算法3的平均通信复杂性可表示为：
Ca=P1N(k+1)+P2N(m+1)+P3Nm
从而平均减少因子α=Ca/(Nm)=kP1/m+(1-P1)+(P1+P2)/m，注意到0<P1+P2<1，则（*）式得证。
从定理2的估计式，我们可以计算[例2]的平均通信复杂性。因N=5，m=6，d=t=1，k=2，且假定p=0.01，故P1≈0.9990，α<0.5007，从而Ca=αNm<15.02，即：平均通信复杂性不会超过15.02。
4.3 通信复杂性的优化
从上述定理及证明可以看到：对一个给定的NMR系统，P1（0<P1<1）是t唯一的函数，P1随着t的增加而增加，α随着P1的增加而减少，Ca随着α的减少而减少，故当错误符号纠正个数t增加时，平均通信复杂性Ca可以减少。另外，算法3的通信复杂性由代码设计参数(d,t)来确定，在一个NMR系统中，我们只需要考虑至多不超过一半的模块具有与多
的通信复杂性。最后在一个分布式的NMR系统中，是否存在一种多数表决算法：其平均通信复杂性小于Nm而只需一轮通信，这有待于进一步研究和探讨。
参考文献
[1]
K.A.S.
Abdel-Ghaffar and A.El Abbadi, ”An Optimal Strategy for Computing File Copies”, IEEE Trans. On
Parallel and Distributed System, 5(1), Jan.1994.
[2]
M.Blaum,J.Brady,J.Bruck
and J.Menon, “EVENODD:
An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures”, IEEE Trans. On
Computer, 44(2), 192-202, Feb.1995.
[3]
D.M.Blough and
G.F.Sullivan, ”Voting
Using Predispositions”,
IEEE Trans. On Reliability, 43(4):604-616,1994
[4]
K.Echtle, “Fault-Masking with
Reduced Redundant Communication”, 16th Annual International Symp. On Fault-Tolerant
Computing System, vol.16, 178-183, 1986.
[5]
Darrell D.E.Long
and Jehan-Francois Paris, ”Voting Without Version Numbers”, Proceedings of the International
Conference on Performance, Computing and Communication,139-145,Feb. 1997
[6]
F.J.MacWilliams
and N.J.A.Sloane, The Theory of Error Correcting Codes, Amsterdam:
North-Holland, 1977.
[7] J.F.Nebus, “Parallel Data Compression for Fault
Tolerance”,
Computer Design, 127-134, Apr.1983
作者简介
范剑波，男，副教授，计算机应用与维护教研室主任，主要研究方向：网络数据库和MIS、人工神经网络及应用、CAI和Internet应用；
通讯地址：浙江省宁波市后河巷20号，宁波高等专科学校电子技术系
邮政编码：315016
Email地址：fjb@mail.nbc.net.cn
或 jbfan@263.net
本论文《NMR系统通信复杂性的分析与优化》已发表在《计算机工程与应用》 (第一作者) ，刊号：CN 11-2127/TP，ISSN
1002-8331，时间： 2001年4月第37卷第8期，此期刊的封面内容为：
（1）全国计算机类中文核心期刊
（2）信息产业部优秀电子科技期刊
（3）中国电子学会一级会刊
（4）中国计算机学会会刊
（5）计算机工程与应用学会学报