许美玲，乔 莹，莫毓昌，钟发荣

(浙江师范大学 数理与信息工程学院，浙江 金华 321004)

(*通信作者电子邮箱1933785432@qq.com)

基于二元决策图的集群计算系统性能分析

许美玲*，乔 莹，莫毓昌，钟发荣

(浙江师范大学 数理与信息工程学院，浙江 金华 321004)

(*通信作者电子邮箱1933785432@qq.com)

针对节点计算能力相同但故障分布不同的集群系统的性能分析问题，基于k-to-l-out-of-n结构对集群系统的性能进行建模，并提出了一种基于二元决策图(BDD)的分析方法。针对k-to-l-out-of-n结构的BDD模型生成问题，分析了BDD的结构特征并设计自顶向下生成算法,克服了传统的自底向上生成算法必须生成大量中间冗余节点的缺陷；然后利用生成的BDD模型高效地计算出系统处于一个特定性能级别的概率；最后通过实例说明了BDD方法能够有效分析节点具有不同故障分布的集群系统性能。

集群计算系统；k-to-l-out-of-n模型；二元决策图

0 引言

现代计算机集群系统包含大量计算节点，这些节点可以是处于分布式环境下或不同管理域中的独立计算机，例如云计算系统或网格计算系统[1-2]，也可以是由Infiniband或三维torus 互联系统连接的单独处理器，例如超级计算系统[3-5]。

假设pi表示节点Ni的计算能力，由n个节点组成的计算系统，其计算能力MP表示为MP=p1+p2+…+pn。节点出现故障会导致计算系统性能降低，即节点Ni出现故障，系统的计算能力将变为MP-pi。若节点具有相同的计算能力p，则系统所能呈现的状态数量共有n+1种情况，计算能力分别为0,p,2p, …,np，其中：0表示所有节点都发生故障，np表示所有节点都正常运行。……