无线广播网络的可靠性分析

本文提出了一个计算无线广播网络的Ｋ－终点可靠度方法。因为ＲＢＮ的Ｋ－终点可靠度问题是个ＮＰ－困难问题,所以已有的结果只是一些近似算法和针对某些特殊ＲＢＮ的算法。     

一种计算Ad hoc网络K-终端可靠性的线性时间算法

研究计算Ad hoe网络K-终端可靠性的线性时间算法,可以快速计算Ad hoe网络K-终端可靠性。为了计算Ad hoe网络分级结构尽终端可靠性,可以采用无向概率图表示Ad hoe网络的分级结构。每个簇头由已知失效率的结点表示,并且当且仅当两个簇相邻时,两个结点间的互连由边表示。这个概率图的链路完全可靠,并且已知结点的失效率。此图的K-终端可靠性为给定K-结点集是互连的概率。文中提出了基于合适区间图计算尽终端可靠性的一种线性时间算法。本算法可用来计算Ad hoe网络的K-终端可靠性。其时间复杂度为O（｜V｜＋｜E｜）。     

Composite importance measures for multi-state systems with multi-state components

This paper presents & evaluates composite importance measures (CIM) for multi-state systems with multi-state components (MSMC). Importance measures are important tools to evaluate & rank the impact of individual components within a system. For multi-state systems, previously developed measures do not meet all user needs. The major focus of the study is to distinguish between two types of importance measures which can be used for evaluating the criticality of components in MSMC with respect to multi-state system reliability. This paper presents Type 1 importance measures that are involved in measuring how a specific component affects multi-state system reliability. A Monte Carlo (MC) simulation methodology for estimating the reliability of a MSMC is used for computing the proposed CIM metrics. Previous approaches (Type 2) have focused on investigating how a particular component state or set of states affects multi-state system reliability. For some systems, it is not clear how to prioritize system component importance, collectively considering all of its states, using the previously developed importance measures. That detracts from those measures. Experimental results show that the proposed CIM can be used as an effective tool to assess component criticality for MSMC. Examples are used to illustrate & compare the proposed CIM with previous multi-state importance measures.     

Distributed-program reliability analysis: complexity and efficientalgorithms

This paper investigates the problem of distributed-program reliability in various classes of distributed computing systems. This problem is computationally intractable for arbitrary distributed computing systems, even when it is restricted to the class of star distributed computing systems. One solvable case for star distributed computing systems is identified, in which data files are distributed with respective to a consecutive property; a polynomial-time algorithm is developed for this case. A linear-time algorithm is developed to test whether or not an arbitrary star distributed computing system has this consecutive file distribution property. Efficient algorithms may still be sought for computing lower and upper bounds on the distributed program reliability for arbitrary distributed computing systems     

A simple goodness-of-fit test for the power-law process, based on the Duane plot

The PLP (power-law process) or the Duane model is a simple model that can be used for both reliability growth and reliability deterioration. GOF (goodness-of-fit) tests for the PLP have attracted much attention. However, the practical use of the PLP model is its graphical analysis or the Duane plot, which is a log-log plot of the cumulative number of failures versus time. This has been commonly used for model validation and parameter estimation. When a plot is made, and the coefficient of determination, R/sup 2/, of the regression line is computed, the model can be tested based on this value. This paper introduces a statistical test, based on this simple procedure. The distribution of R/sup 2/ under the PLP hypothesis is shown not to depend on the true model parameters. Hence, it is possible to build a statistical GOF test for the PLP. The critical values of the test depend only on the sample size. Simulations show that this test is reasonably powerful compared with the usual PLP GOF tests. It is sometimes more powerful, especially for deteriorating systems. Implementing this test needs only the computation of a coefficient of determination. It is much easier than, for example, computing an Anderson-Darling statistic. Further study is needed to compare more precisely this new test with the existing ones. But the R/sup 2/ test provides a very simple and useful objective approach for decision making with regard to model validation.     

基于FPGA的零误差大数阶乘算法的设计与实现

随着大数据时代的到来,人们对超高精度科学计算的需求日益迫切,其中一个难点是大数阶乘问题.斯特林公式作为计算大数阶乘的传统近似方法,远不能在精度上满足要求,其它的阶乘算法可以实现较高的精度,但以牺牲大量存储空间为代价.本文提出一种具有零误差的大数阶乘算法,可以根据问题规模优化存储空间,利用并行计算的思想和FPGA的优势来提高计算速度,测试结果表明,所提出的算法具有较好的时空效率,可以应用在如大数阶乘计算器等诸多领域.     

Reliability evaluation for distributed computing networks withimperfect nodes

This paper examines two compensating methods that: (1) account for imperfect nodes, and (2) can be embedded in most symbolic network reliability algorithms that presume perfect nodes. The Aggarwal method can be exponential in time with the number of links, whereas the Torrieri method is always linear. However the Torrieri method can yield incorrect results for some undirected networks. This paper points out such incorrectness and then proposes an efficient reliability evaluation algorithm (ENR/KW) accounting for imperfect nodes in distributed computing networks. Based on the concept of network partition, ENR/KW exploits some simple efficient techniques to handle the unreliable nodes, for directly computing the network reliability expression considering imperfect nodes instead of using any compensating method. The basic idea of ENR/KW is to partition the network directly into a set of smaller disjoint subnetworks by only considering link elements as if all nodes are perfect. Each disjoint subnetwork is generated by maintaining a specific directed graph structure to consider the effect of imperfect nodes. Therefore, the reliability expression for imperfect nodes can be obtained directly from the disjoint subnetwork and the specific directed graph. ENR/KW can be generalized to evaluate various network reliability measures considering imperfect nodes such as terminal-pair reliability, K-terminal reliability, and distributed-program reliability. Many experiments for evaluating the terminal-pair reliability and distributed-program reliability were performed on a SUN workstation to show the efficiency of ENR/KW in terms of the number of generated subnetworks and overall computation time     

Approximate sensitivity analysis for acyclic Markov reliability models

Acyclic Markov chains are frequently used for reliability analysis of nonmaintained mission-critical computer-based systems. Since traditional sensitivity (or importance) analysis using Markov chains can be computationally expensive, an approximate approach is presented which is easy to compute and which performs quite well in test cases. This approach is presented in terms of a Markov chain which is used for solving a dynamic fault-tree, but the approach applies to any acyclic Markov reliability model.     

基于近似计算技术的FPRM电路面积优化

近似计算技术通过降低电路输出精度实现电路功耗、面积、速度等方面的优化.本文针对RM（Reed-Muller）逻辑中"异或"运算特点，提出了基于近似计算技术的适合FPRM逻辑的电路面积优化算法，包括基于不相交运算的RM逻辑错误率计算方法，及在错误率约束下，有利于面积优化的近似FPRM函数搜索方法等.优化算法用MCNC（Microelectronics Center of North Carolina）电路进行测试.实验结果表明，提出的算法可以处理输入变量个数为199个的大电路，在平均错误率为5.7%下，平均电路面积减少62.0%，并在实现面积优化的同时有利于实现电路的动态功耗的优化且对电路时延影响不大.     

计算无圈有向网络ST可靠性的一个新方法

本文考虑计算无圈有向网络的ＳＴ可靠性问题（至少存在一条从源点ｓ到汇点ｔ的正常运行道路的概率）。文章引进了深度优先搜索（Ｄｅｐｔｈ－ＦｉｒｓｔＳｅａｒｃｈ）有序根树的概念并提出一个新的计算无圈有向网络ＳＴ可靠性的拓扑公式。以该公式为基础,我们利用ＤＦＳ方法提出一个新的计算无圈有向网络ＳＴ可靠性算法,它能生成简洁的可靠性表达式,进而有效地计算无圈有向网络的ＳＴ可靠性。两个例子例证了我们的结论     

Two formulas for computing the reliability of incompletek-out-of-n:G systems

Reliability computation of highly redundant systems most commonly uses approximate methods. Except for k-out-of-n:G systems or consecutive k-out-of-n:G systems, exact reliability formulas offering a broader range of applicability are rare. This paper gives two new formulas for this purpose: the first handles k-out-of-n:G systems of which some paths are not present; the second allows for the reliability calculation of a coherent binary system in general. Both formulas express system reliability in terms of the reliabilities of k-out-of-n:G systems. In practice, these new formulas cope with highly redundant systems with certain similarities to k-out-of-n:G systems. For example, a reliability of the control-rod system of a nuclear reactor is computed. Although the paper is directed to system reliability, the results can be used for computing the failure probability of a system which in practical applications is sometimes more convenient. In which case, the formulas are to be changed such that a system is given by its minimal cut-sets instead of minimal path-sets, and p should be a component unreliability instead of its reliability. The first proof of formula uses domination theory and, in thus contributes to the state of the art in this field     

Reliability/performance evaluation for a multisystem with preventive maintenance

In general, a computing system with high reliability can be achieved by redundancy and/or maintenance. The sophisticated maintenance techniques are more and more important since a computing system can be operated by applying remote maintenance. In this paper we discuss a multisystem with preventive maintenance, which is one of the fault-tolerant computing systems. Making the suitable assumptions, we construct a stochastic model of such a computing system for evaluating reliability/performance. Applying Markov renewal and queueing theories, we analytically obtain several reliability/performance measures. Calculating such measures numerically, we show the impacts of preventive maintenance on such a computing system.     

云计算分布式缓存技术及其在物联网中的应用

物联网是信息技术发展到一定阶段的产物,而云计算平台是物联网应用的基础。文章从当前云计算应用所面临的问题和缺陷出发,介绍了云计算分布式缓存的部署方式、功能架构及关键技术,并说明了分布式缓存高性能、高吞吐、高可靠性、高扩展性等优势和特性。文章解决了物联网应用普遍面临的数据可靠性、大容量内存共享、多模块数据一致保障、线性扩容等难题,为物联网平台云化架构的底层支撑奠定了基础。     

云计算后台大规模数据处理技术探讨

云计算的后台处理技术是云计算系统的总体保障。本文主要介绍当前云计算中的后台大规模数据处理技术。大规模数据处理技术对于云计算的后台数据收集与整理起着关键的作用。在云计算中的大规模数据处理技术主要解决三个问题,即可靠性,可扩展性以及易编程性。本文结合Google的MapReduce编程方式,以及微软的Dryad编程方式,着重介绍在实践中,如何达到上述的目标。     

Censored software-reliability models

Nonfailure stops of software execution processes can be viewed as a type of censored data. They can occur in a wide range of computing systems (e.g., concurrent computing systems, data sampling systems, transaction processing systems) due to technical or nontechnical reasons. Using existing software reliability models to deal with this type of censored software reliability data, viz, successive inter-stop times, where a stop can be failure or nonfailure stop, means that nonfailure stops are disregarded. This paper develops censored software reliability models, or censored forms of existing software reliability models, to account for nonfailure stops and directly deal with censored data of software reliability. The paper shows how to develop censored forms for the models: Jelinski-Moranda, Schick-Wolverton, Moranda Geometric, and Littlewood-Verrall, and discusses the corresponding validation forms. Censored forms of other software reliability models can be developed in a similar way. Censored software reliability models reduce to noncensored software reliability models if no nonfailure stop occurs     

A genetic algorithm for reliability-oriented task assignment with k/spl tilde/ duplications in distributed systems

A distributed system is a collection of processor-memory pairs connected by communication links. The reliability of a distributed system can be expressed using the distributed program reliability, and distributed system reliability analysis. The computing reliability of a distributed system is an NP-hard problem. The distribution of programs & data-files can affect the system reliability. The reliability-oriented task assignment problem, which is NP-hard, is to find a task distribution such that the program reliability or system reliability is maximized. For example, efficient allocation of channels to the different cells can greatly improve the overall network throughput, in terms of the number of calls successfully supported. This paper presents a genetic algorithm-based reliability-oriented task assignment methodology (GAROTA) for computing the k/spl tilde/-DTA reliability problem. The proposed algorithm uses a genetic algorithm to select a program & file assignment set that is maximal, or nearly maximal, with respect to system reliability. Our numerical results show that the proposed algorithm may obtain the exact solution in most cases, and the computation time seems to be significantly shorter than that needed for the exhaustive method. When the proposed method fails to give an exact solution, the deviation from the exact solution is very small. The technique presented in this paper would be helpful for readers to understand the correlation between task assignment reliability, and distributed system topology.     

Reliability evaluation of multistage interconnection networks with multi-state elements

This paper presents a graph-theoretic method for the reliability evaluation of multistage interconnection networks with multistate elements. For the purpose of analysis, the generalized cube (GC), a unique-path MIN and an extra-stage cube (ESC), a fault-tolerant variation of GC, are considered. An algorithm is presented to evaluate three reliability measures, i.e. terminal reliability (TR), broadcast reliability (BR) and network reliability (NR) of MINs for different reliability values of links and switches. The proposed method is found to be simple and computationally efficient compared to the existing techniques, and therefore can be applied for reliability evaluation of other large interconnection networks used in parallel computing systems.     

网络端端可靠度的上下界计算研究

考虑精确计算较大规模网络的端端可靠度属于NP—hard问题,提出一种计算网络端端可靠度的近似方法,算法分别基于最小路集和不交最短路集来计算网络端端可靠度的上下界,并在此基础上给出了示例来阐明算法的有效性,该计算方法的算法实现简单,能快速计算出网络的端端相对可靠度。     

边失效概率不同情况下网络全终端可靠度的近似计算

用可靠性多项式计算网络全终端可靠度是评估网络拓扑结构德定程度的重要依据,精确计算可靠性多项式是一个NP-hard问题.本文通过对基于产生孤立点的概率随机事件的定义,运用概率不等式变换,给出了点可靠、边以不同的概率相互独立失效时,网络全终端可靠度的上界表达式,在可靠度近似计算过程中避免了对网络边割集和路集的搜索.最后,在...