k元n树互联网络的2-终点可靠性研究  

Research on Two-terminal Reliability of k-ary n-tree Interconnection Networks

作　　者：黄江洪[1] 肖子枫[1] 韩承德[1] 

机构地区：[1]中国科学院计算技术研究所

出　　处：《计算机工程》2008年第11期32-34,共3页Computer Engineering

基　　金：国家“973”计划基金资助项目(2004CB318202);国家自然科学基金资助项目(60303017)

摘　　要：k元n树是一种用于大规模并行处理的高性能互联网络的拓扑结构。该文提出计算k元n树的2-终点可靠性的递归算法,其计算复杂度为O(n)。结合市场上网络元器件可靠性的实际情况,对k元n树的2-终点可靠性进行了分析。当n趋于无穷大时,计算出k元n树的2-终点可靠性的下限。k-ary n-tree is a kind of topology of high performance interconnection networks for parallel architectures. A recursive algorithm is prerSented to calculate two-terminal reliability of k-ary n-tree. Its computational complexity is O（n）. Taking the reliability Of commercial network components into consideration, this paper analyzes two-terminal reliability of k-ary n-trees. When n tends to be infinite, the lower bound of two-terminal reliability of k-ary n-tree is given.

关 键 词：k元n树 2-终点可靠性 计算复杂度 下限 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]