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

Performance analysis of cluster computing systems using binary decision diagram

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

To analyze the performance of cluster computing systems with identical computing power but different failure distribution, a k-to-l-out-of-n structure was used to model system performance, and a new analytical method based on Binary Decision Diagram （BDD） was proposed for the performance analysis. A new and efficient BDD algorithm that makes full use of the special k-to-l-out-of-n structure was also proposed using a top-down manner, which solved the problem that the traditional bottom-up generation algorithm must generate a large number of intermediate redundant nodes. Then the proposed BDD was used to efficiently calculate the probability of the system being at a specific performance level. At last, some examples were provided to illustrate the proposed BDD-based performance analysis methodology as well as its efficiency in analyzing large- scale cluster computing systems.