双终端可靠性问题的内存效率算法

可在www.sciencedirect.com在线获取理论计算机科学电子笔记291（2013）15-25www.elsevier.com/locate/entcs双终端可靠性问题的记忆效率定界算法MinhLea，1MaxWalterb，2JosefWeidendorfera，3aLehrstuhlfurRechnertechnikunndRechnerororganisationTUMünchen慕尼黑bSiemensAGNuürnberg，德国摘要终端对可靠性问题，即确定存在的概率，已知连接终端节点的工作边的至少一条路径是NP难的。因此，边界算法被用来处理大的图尺寸。然而，它们在内存方面仍然有巨大的需求。我们提出了一个内存效率的实现Gobien-Dotson边界算法的扩展。在不增加运行时间的情况下，相关数据结构的压缩允许我们使用低带宽高容量存储。这样，可用的硬盘空间就成为限制因素。 根据输入结构，具有数百条边的 图 （即， 系统组件）可以被处理。关键词：终端对可靠性，划分，内存迁移，因子分解1引言自20世纪60年代以来，端子对可靠性问题得到了广泛的研究[12]。它确定了冗余结构用组合图表示的二状态系统的可靠性。边对应于系统组件，可以处于两种状态之一：故障或工作，而节点被假定为完美的互连点。虽然所有组件在统计上都不独立，但该问题被证明是NP完全的[9]。随着时间的推移，已经开发了许多算法。它们可分为以下几类：(i) 不交积和（SDP）[6，14]1电子邮件：lem@in.tum.de2电子邮件：www.example.commax.walter @ siemens.com3电子邮件：weidendo@in.tum.de1571-0661 © 2012 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2012.11.01516M. Lê等人/理论计算机科学电子笔记291（2013）15(ii) 基于割和路径的状态枚举（带有约简）[15，10，17](iii) 带约简的因式分解算法[1，7，11](iv) 使用有序二叉决策图（OBDD）的边扩展图（EED）[4]使用SDP的方法需要预先枚举网络的最小路或割.因此，类别（i）与类别（ii）相关 。 从 类 （ i ） 的 方 法 的 重 要 缺 点 是 ， 在 分 离 的 最 小 路 径 或 割 集 的 计 算 的EQUARORT迅速增长的网络规模。相反，更建议应用（iii）或（iv）[4]。通过利用同构子图结构，(iv)对于大型递归网络结构来说是非常有效的。然而，基于OBDD的方法的效率在很大程度上取决于BDD变量排序，其本身具有O（n2·3n）的时间复杂度[5]。不幸的是，上述方法缺乏提供任何有价值结果的能力非终止。考虑到可靠性工程师通常会对良好的近似结果（达到一定数量级）感到满意，Gobien和Dotson [15]建议的边界算法使用约简证明是一种合适的方法。它以布尔代数为基础，确定互不相交的故障事件和失效事件。Yoo和Deo在与其他四种有效算法的直接比较中强调了这种方法的有效性[16]。然而，没有注意到这种方法快速增加的内存消耗。换句话说，计算的边界的准确性受限于可用内存的大小。因此，在这项工作中，我们提出了一种克服这种限制的方法，而不会显着这是通过将内存中保存的相关数据结构迁移到低带宽高容量存储器来实现的。因此，我们可以处理更大维度的输入，并获得更准确的边界。此外，存储器消耗可以被看作是可忽略的，因为只有初始输入图和概率图被存储在存储器中。在第2节中给出了两端可靠性问题的定义和适当的Gobien Dotson算法的思想之后，我们将首先解释如何优化这种方法的内存消耗，然后在第3节中将内存内容迁移到硬盘。在第4节中，我们展示了在几个基准网络上执行的改进算法的一些结果。最后对研究结果进行了总结，并在最后一节中对研究进行了展望在整个文件中，我们使用以下缩略语：RBD可靠性框图bfs广度优先搜索带宽2初步定义2.1待评估系统的冗余结构由无向多重图G：=（V，E）建模，其中V代表一组M. Lê等人/理论计算机科学电子笔记291（2013）1517顶点或节点，E是无序顶点对的多集，称为边。在G中，我们指定两个节点s和t来表征终端节点。我们定义了两个不一定内射的映射f和g，其中f：E→C指定边并且g：E→V2将每条边分配给一对节点。每个分量c∈C代表一个随机变量，有两种状态：失效或工作。对于每个c∈C，给出了失效概率qc= 1−pc。系统的终端对可靠度Rs，t是两个指定终端节点通过至少一条仅由与工作组件相关联的边组成的在这个模型中，我们要求统计独立的组件故障。然而，我们指出，第3节中提出的方法可以很容易地适应相关故障[8]。此外，我们只停留在串联和并联约简上，以便与其他约简技术（如链到链[7]或三角形约简[13]）无法应用的方法进行比较，例如。当考虑节点故障时[3，11]。它们肯定会导致计算时间和子问题数量的显着减少，但我们的主要重点是传达在不影响运行时间的情况下绕过内存限制的想法。2.1Gobien Dotson方法设P是路径P = [e1，e2，.，e r]，且ei∈E，其中1 ≤i≤r.根据[10]，G的可靠性表达式可以通过递归地对路径P中的r条边中的每一条应用因子分解定理来获得。从第一条边e1开始，我们定义映射到与e1相同的分量的边的集合：E1 ={e∈E|f（e）= f（e1）}。因此，我们有：Rs，t（G）=p1·Rs，t（G−E1）+q1·Rs，t（G−E1），其中f/−表示E1中所有边的收缩/删除，qi= 1−pi， 1≤i≤r是分量f（ei）的失效概率然后，Rs，t（G∈E1）项将再次通过在E2中的边上因式分解而展开，这是类似定义的。总体而言，可以得出以下结论：（一）Rs，t（G）=q1·Rs，t（G-E1）+ p1q2·Rs，t（GE1−E2）+ ......这是什么？+p1p2· · ·pr−1qr·Rs，t（GE1E2. . . Er−1−Er）R+pkk=1所以我们有r个子问题，分别从路径P导出子图。如果存在i，j∈{1，2， . ，r}，i j但f（ei）=f（ej），则Ei=Ej. 因此，子问题的个数会减少一个同样，对于每个子问题，可以递归地应用。因此，对于每个子问题，我们都在寻找拓扑最短路径，以保持子问题的数量较少。这是通过广度优先搜索完成的，因为所有边的长度都是1。在每个子图约简中18M. Lê等人/理论计算机科学电子笔记291（2013）15Σk=1Σi=1i=1如果可能的话，可以执行。根据[15]，所有s-t路径对应于成功事件（系统处于工作状态），所有s-t切割对应于失败事件（系统处于失败状态）。设S是G中成功事件Si的不交穷举成功集，1≤i≤N.G的终端对可靠性则表示为：NRs，t（G）= P（Si）.i=1等式1的最后一个加数是第一个成功事件S1的概率，因此P（S1）=rpk. 所有其他的P（Si），2≤i≤N是在子图中找到剩余的s-t路径类似地，失败集合F：={Fi， 1≤i≤M}MRs，t（G）= 1− P（Fi），i=1其中P（Fi）项是s-t切割的概率。 For u<|S|，v<|F|且u，v∈N，则可靠度的上、下界为u vG（S i）≤ R s，t（G）≤ 1 −P（F i）.根据这个不等式，每次发现一条新的s-t路径时，下界增加，而每次增加s-t切割时，上界减小。一旦找到所有的s-t割和路，它就变成一个方程。我们参考[8]，将所描述的方法应用于一个简短的例子网络。3Gobien Dotson记忆法在本节中，我们将首先解释如何保持这种方法的内存消耗尽可能低。据我们所知，在事件队列的帮助下，子图是递归创建的（参见[10]），而不是存储的。每个事件都包含一系列边，在这些边之后，原始图被划分。不幸的是，这种方法不包含任何减少。此外，事件通过共享相同的先前边缘序列而包含冗余信息为了弥补这种冗余和缺乏减少，我们建议使用所谓的三角树。它跟踪由于缩减和分区而对原始图所做的所有更改。尽管内存消耗保持尽可能低，但由于该问题的指数增长，大图尺寸很快就会达到限制。主要思想是将delta树迁移到硬盘上。要写入的数据以某种方式排列，以符合硬盘M. Lê等人/理论计算机科学电子笔记291（2013）1519ΔΔΔΔ3.1三角树该方法的所有中间结果都可以存储在称为delta树的递归树中，其结构如下：从根节点开始，我们将在原始输入图上执行的所有约简存储在此处。一般来说，树的每个节点存储在特定子图上的所有连续执行的约简子节点的数量等于在父节点处找到的最短s-t路径的长度。连接父节点与子节点的边包含用于划分由父节点表示的相应子图的信息。在算法的过程中，树根据广度优先搜索顺序逐层出现。树的每一个叶子代表一个子图或要进行的任务。这个子图可以通过追溯从叶到根的delta路径PΔ除了子图之外，可以在PΔ的帮助下重建适当的边缘概率图EdgeProbMap（epm）和累积的路径/切割项。下面，我们将展示如何将相关信息存储在TΔ中。每个串联或并联约简涉及两条边e1和e2，而第一条边的概率pe 1相对于所执行的约简边e2在串联约简的情况下将被收缩，在并联约简的情况下将被删除一般来说，边e的收缩包含以下步骤：首先删除e，然后将e的边界节点合并为一个节点。在这两种情况下（串联和并联），边缘e2从图中删除边e1保留在图中，并且在EdgeProbMap中捕获pe1。引入操作是为了区分收缩（=+）和删除（=-）。为了区分e1和e2，任何约简项red都包含一个子串，其字符串表示如下：红色：=包含l个约简的图的任何delta树节点n表示为：n ： =“ 红 色 j 1 红 色 j 2.redJl“缩比用尖重音分隔。基于长度为r的最短路径，r个子问题分别由边删除和收缩操作导出。 所有要收缩的边缘 最前面的是最后一条边er，它将被删除（通过-操作）。同样，这些边可以由一个分隔符分隔。假设我们在三角树的节点n上找到了一条长度为r的路径，那么从父节点n出来的r条三角树边eΔ定义如下：1 ：=：=“e 1 ; − e 2“.e r：=“e1;e2;. . . ;er−1;−er递归层m的每一条δ路PΔ是TΔ-节点ni（从根n0开始）和TΔ-边ei，0≤i≤m：PΔ：=“n 0 > e 0 > n 1 > e 1 >. . .>em−1>nm>emΔ ΔΔΔe20M. Lê等人/理论计算机科学电子笔记291（2013）15Δ3.2修改后的算法在这一部分中，我们描述了整个修改后的算法，该算法通过在每个递归级别取一个输入文件FPrev来生成一个输出文件FNext。在过程1中初始化输入图、文件和所有适当的映射之后，调用过程2来处理初始图。首先，我们检查图的连通性。如果图是连通的，我们在第12行寻找可能的减少。在epm的第13行更新了因降低而发生的概率另外，在如上所述的字符串中捕获由归约引起的所执行的图形操纵，并且再次将该字符串贡献给行（行14）。根据最短路径sp，将直线问题扩展为相应的子问题。最后，line被写入FNext。现在我们定义将TΔ写入FNext的规则。FNext（linebranch）中的每条线表示包括k个叶的TΔ的分支。因此，字符串表示定义如下线性随机数：=“n 0 > e 0 > n 1 > e 1 >。 . .>em−1>nm：esub0，esub1， . ，esubkΔ ΔΔ Δ Δ Δ由此，k个增量树边esub由逗号分隔并由冒号附接。在过程2中，linebranch的第一部分--冒号的左边--被aggregateLeaf（e）与相应的子问题聚合。在for循环结束时，完成的linebrench被写入文件FNext。在当前TΔ级别的所有行分支都被写入之后，FNext文件被重命名为FPrev，然后作为过程3中下一个递归的输入。一个delta路径（任务PΔi），i∈ {0，1，.，k}是从linebranchor导出的，表示如下PΔ：=“n 0 > e 0 > n 1 > e 1 >. . .>em−1>nm>esubiiΔ在过程3中，从linebrench推导出的每个PΔ由过程4处理，该过程4读取PΔ并重建子图和适当的累积项acc。在TΔ的每个水平结束时，打印出当前边界。程序1主程序一曰：Init（）; //初始化inputGraph，epmInit，FNext，FPrev2：FPrev=computeRel（inputGraph，newList（），epmInit，第三节： newFile;第四章：bfsLevel（FPrev）;4实验结果修改后的方法在JAVA中实现，并在Intel Xeon 2.97 GHz机器上的九个示例网络上进行了测试。每个网络（nw.）在表1中，用其边数表示。末端节点以黑色着色。Nw.4-6的特征在于参数N，其代表每行中的水平边缘的数量，并且N-1是每列中的垂直边缘的数量在nw.9中，NM. Lê等人/理论计算机科学电子笔记291（2013）1521步骤2computeRel输入：RBD图形，列表访问，EdgeProbMapepm，字符串行，文件FNext1：boolPorC;//用于确定路径/切割的条件变量第二章： boolb =String. getString（）;第三节： 如果b==false，则2：doubletmp =computeProduct（acc）;5：如果PorC==true，则6：路径=路径+tmp;7：否则8：Cuts=Cuts+tmp;9：如果结束10：返回十一日： end if12：SPRed = Graph.reduce（）//预处理：Reduce graph。十三： epm=red.getEdgeProbMap（）; //更新边缘概率14：line=line+red.getString（）;//使用减少的项扩展行十五： Listsp =BFS.shortestPath（Graph）; //查找最短路径16：对于每个e∈spdo17：line=line+aggregateLeaf（e）;18：结束19：FNext.write（line）;二十： returnFNext程序3bfsLevel输入： 文件FPrev一曰： 对于每个分支线∈FPrev，2：//处理每个子问题（路径）3：对于每个子∈linebranchor，RBDrbd =readTaskBranch（sub）;5：FNext=computeRel（rbd，parallel，epm，line，FNext）;6：结束7：结束第八章： 如果FNext.IsEmpty（），则9：返回10点整： end if十一日： FPrev=FNext;十二： newFile;13：print14：print十五：bfsLevel（FPrev）;表示K4阶梯中的平方数（参见[2]）。为了与相关文献的结果进行比较，我们声称每个边缘都以0.1在所有网络中。表2显示了相对准确度为10%时计算的界限。最后一列d（TΔ）指22M. Lê等人/理论计算机科学电子笔记291（2013）15示所述深度或水平。M. Lê等人/理论计算机科学电子笔记291（2013）1523过程4readTaskBranch输入：Stringsub1：String[]deltapath=sub.split（>）;2：对于每个i∈deltapath，3：processNode（deltapath[i]）;//减少4：i=i+1;5：processEdge（deltapath[i]）; //合并删除操作6：结束7：epm.update（）; //重新创建EdgeProbMap8：acc.update（）; //重新创建映射列表9：返回rbd; //重建图三角树，在此之后获得各自的边界还列出了文件大小、可以观察到，除了组件的数量之外，运行时间高度依赖于网络的结构。比较表2中nw.3和nw.4的结果，它们的运行时间大致相同。这是一个错误的结论，期望一个更快的解决方案为nw.4关于其1.5倍以上的带宽。因此，其原因在于它们的图结构：nw.3的最短s-t路径是nw.4的两倍长，这意味着nw.3通常在每个层次上产生的子问题比nw.4多。这导致处理每个级别的所有任务的计算时间更长。因此，对于nw.3，必须花费更多的时间来等待数据写入硬盘，从而导致较低的带宽。关于图结构的影响的另一个观察是在nw.6和nw.9之间：nw.6比nw.9少20个分量虽然我们在nw.6中从较少的子问题（最短s-t路径的长度）开始，但在TΔ中的许多子节点的几个递归级别之后，这个数字仍然很高，导致每个级别的任务数量很高。对于nw.6，2.72亿个子问题存储在21。4 GB，这意味着平均需要84 GB来编码任务。 比较nw.4-6的带宽，我们注意到网络越大，平均磁盘带宽就越低。简单的原因是，在较大的图上执行图操作需要更多的时间，并且由于最短s-t路径的长度增加而导致更高的延迟，因此会出现更多的子问题对于一些网络，不可能在两天内获得确切的结果。表3列出了我们可以完成的任务。dmax（TΔ）表示delta树的最大深度（或总层数）。 注意，树的深度受到原始输入图的边的数量的限制，因为在每个递归中，边的数量dw（TΔ）是树的最宽层。 的此级别的文件大小也表示整个计算所需的最大磁盘空间。通过比较这两个表，我们可以得出以下结论：对于大型网络，我们只需要总时间的一小部分，以及最大所需磁盘空间的一小部分，就可以达到令人满意的界限。例如，对于nw.3，所需磁盘空间的比例为0.071%，花费的时间仅为总时间的0.018%类似地，对于nw.5可以观察到这一点24M. Lê等人/理论计算机科学电子笔记291（2013）15.........我们注意到，对于更小的故障概率值--对于高可靠系统为10−5的量级--可以在更短的时间内获得边界，需要更少的硬盘空间。为了将基于delta树和磁盘存储的实现与扩展了串行和并行reduc- tions的方法[15]的旧实现进行比较，我们添加了另一个时间列。对于nw.5-9，在达到相应的界限之前，2GB的内存已经耗尽。对于所有其他网络，我们可以观察到，小型网络nw.1和nw.2的运行时间较短，但大型网络3和4的运行时间明显更多。这是由于所有子图的保持和通过方法[15]执行的内存减少：对于小尺寸的问题，需要较少的内存来存储每个生成的子图。此外，更少的子问题演变。当问题达到一定规模时，每个子图需要更多的存储空间，并且预计会有更多的子问题因此，内存需求的快速增长会对运行时产生负面影响。表1基准网络1-9西北2Nw. 3#24西北4......N=5#41...Nw. 7.. .3x 12第五十七.. .5结论Nw. 5......N=6#61...Nw.8.. .3x16第七十六章.. .西北.6......N= 7#81...西北9N=20 #。1.一、01.在这项工作中，我们强调的问题，高内存消耗的Gobien Dotson算法。由于终端对可靠性问题的指数性质，对内存的需求增长不可接受的网络的大小由于内存不足，计算必须中断，因此这对达到良好的可靠性界限施加了限制因素因此，我们建议将内存内容迁移到硬盘。增量树以某种方式编码，以符合硬盘这种方法甚至允许中断，因为在中断点之前创建的文件可以在稍后的时间重新使用以继续计算我们发现Nw.1#45第六十名M. Lê等人/理论计算机科学电子笔记291（2013）1525表2边界（相对精度=0。第一章NWlbUB时间时间[15]文件（MB）#任务你好公司简介SD11 .一、99·10−9二、05·10−90。68秒0。41 s0。1414640。64112二、47·10−2二、50·10−20。26 S0。20岁0。012820。1053二、42·10−2二、47·10−2八、00s26岁17 S五、55一百二十一，六百二十二0。7874第九章12·10−5第九章14·10−5第七章68秒十一岁53s第七章26九十七○三十六1 .一、161051 .一、32·10−51 .一、36·10−5180 s-183. 78第2、 631、226页0。601161 .一、88·10−61 .一、91·10−6第七章73 H-2192428272 012 6330。401473 .第三章。81·10−23 .第三章。85·10−2第四十九章。16 S-54号10六九七五九二0。7588四、36·10−2四、38·10−21 .一、39 H-四千八百九十九。35五十三、一八四、六八三0。5689四、34·10−3四、41·10−31 .一、91小时-九千零一十一。6450、 958、4180。7810表3精确结果NW不可靠时间时间[15]DMaxDw文件（MB）#任务你好公司简介S1二、00·10−9第九章79秒第六章26S36201 .一、65一万二千五百七十四1 .一、992二、49·10−20。35 S0。17 S950。012820。103二、43·10−212个。45 H-251620，429。3962、 358、421二、434第九章13·10−5第四十一章。75 S47岁。52秒201214个。52一三八，八百一十四1 .一、6551 .一、33·10−5第三十九章。55小时-302030，613。73203， 132，9391 .一、4373 .第三章。83·10−20。61小时-2212521号654，135，0841 .一、25仅需要完整运行时间的一小部分和最大所需空间来获得合理且准确的必须指出，这一事实在很大程度上取决于系统部件的故障概率，并且与高度可靠的系统有关。大部分额外的时间只对边界的微小改进人们可能会认为，通过将内存内容迁移到硬盘，之后硬盘本身可能会成为瓶颈。然26M. Lê等人/理论计算机科学电子笔记291（2013）15而，通过查看测量的带宽值，情况绝对不是这样。相反，仅为2.43 MB/s的最大平均磁盘带宽表明，存在进一步利用当今硬盘的写入速度（约150 MB/s）的空间在这种情况下，我们打算将顺序算法并行化，并利用所有任务PΔ都是独立的这一特性M. Lê等人/理论计算机科学电子笔记291（2013）1527确认我们非常感谢A。感谢你支持我们的工作。我们的感谢也献给M。来自Universit？tderBundes的Siegle与Mu？n？chen进行了许多有见地的讨论。我们还要感谢三位匿名评论者提供的有用和详细的评论。引用[1] A.Satyanarayana和M.K.Chang.网络可靠性与因子分解定理。网络，第13卷，第1期，107-120页，1983年。[2] C.Tanguy.大型递归网络的渐近平均失效时间和高阶矩。 在2008年[3] D.Torrieri.具有不可靠节点的大型网络中节点对可靠性的计算。在IEEE Trans. Reliability，vol.43，no.3，375-377，1994中。[4] 叶方明， 卢锡基，和 S.Y.Kuo.基于OBDD的边扩展图确定端对可靠性。在IEEE Trans.Reliability，vol.48，no.3，234-246，1999中。[5] S. J. Friedman和K. J. Supowit. 寻找二元决策图的最佳变量排序。 在SIAM Journal on Computing，vol.39，no.5，710-713，1990中。[6] J.M.Wilson.一种改进的不交积和极小化算法。在IEEE Trans. Reliability，vol.39，no.1，42-45，1990中。[7] K.Wood.一种使用链到链归约计算k-终端网络可靠性的因子分解算法。网络，第15卷，第2期，173-190页，1985年。[8] M. L e和M. Walter. 具有独立基本变量的两次试验网络可靠性的界. 在计算机科学讲义，vol.7201/2012，31-45，2012。[9] M.O.Ball.网络可靠性分析的计算复杂性：概述。在IEEE Trans. Reliability，vol.35，no.3，230-239，1986中。[10] 作者声明：Dr.终端对可靠性的并行算法。在IEEE Trans. Reliability，vol.41，no.2，201-209，1992中。[11] O.R.Theologou和J.G. Carlier。不完美顶点网络的因子分解和约简。 在IEEE Trans.可 靠 性，第40卷，第2期，210-217页，1991年。[12] 作者声明：by R.可靠性数学理论约翰·威利父子出版社1965年[13] 作者单位Author Agencies：网络管理中利用三角形归约法快速计算终端对可靠性。载于《国际商会通讯》，第1卷，281-285，1998年。[14] S.Soh和S.Rai。不交积和技术中路径/割项预处理的实验结果。在IEEE Trans. Reliability，vol.42，no.1，24-33，1993中。[15] 作者声明：by J. 一种新的概率图分析技术。 在IEEE Trans. Circuit中&系统，第26卷，第10期，855-865，1979年。[16] Y.B.Yoo 和 N.Deo.端子对可靠度算法的比较。在IEEE Trans. Reliability，vol.37，no.2，210-215，1988中。[17] Y.G.Chen和M.C.Yuang.一 基于切割的 方法为 终端对 可靠性在IEEE Trans. Reliability，vol.45，no.3，413-416，1996中。