Folded Hypercubes 在PMC模型下的可诊断数

›› 2013, Vol. 26 ›› Issue (1): 16-.

Folded Hypercubes 在PMC模型下的可诊断数

李刚平,朱强,郭洋洋

(西安电子科技大学理学院,陕西西安 710071)

出版日期:2013-01-15 发布日期:2013-03-08
作者简介:李刚平(1987—),男,硕士研究生。研究方向:并行计算系统可靠性。E-mail:ligangpingchangan@126.com
基金资助:
国家自然科学基金资助项目(No.11101322)

Diagnosability of Folded Hypercube in the PMC Model

LI Gangping,ZHU Qiang,GUO Yangyang

(School of Science,Xidian University,Xi'an 710071,China)

Online:2013-01-15 Published:2013-03-08

摘要/Abstract

摘要：

可诊断数是衡量多处理器系统可靠性的一个重要参数。文中通过对折叠立方体的可诊断性研究,证明了在PMC模型下,折叠立方体是(n+2)-可诊断的(n≥3),且是(2n+2)/(2n+2)-可诊断的(n≥4)

关键词: 折叠立方体, 可诊断数, PMC模型, 精确策略, 悲观策略

Abstract:

Diagnosability plays an important role in measuring the reliability of multiprocessor systems.In this paper,it is proved that in the PMC model,the (n+1)-dimensional Folded Hypercube is (n+2)-diagnosable with the precise diagnosis strategy for n≥3,and (2n+2)/(2n+2)-diagnosable with the pessimistic strategy for n≥4.

Key words: folded Hypercube;diagnosability;PMC model;pessimistic strategy;pessimistic strategy

中图分类号:

O151.6

李刚平,朱强,郭洋洋. Folded Hypercubes 在PMC模型下的可诊断数[J]. , 2013, 26(1): 16-.

LI Gangping,ZHU Qiang,GUO Yangyang. Diagnosability of Folded Hypercube in the PMC Model[J]. , 2013, 26(1): 16-.

参考文献

［1］PREPARATA F P,METZE G,CHIEN R T.On the connection assignment problem of diagnosable systems［J］.IEEE Transactions on Electronic Computers,1967,16(12):848-854.

［2］JIANXI FAN.Diagnosability of the mobius cubes［J］.IEEE Transaction on Parallel and Diatributed Systems,1998,9(9):923-928.

［3］WANG D.Diagnosability of enhanced hypercubes［J］.IEEE Transactions on Computers,1994,43(9):1054-1061.

［4］KAVIANPOUR A,KIM K H.Diagnosability of hypercube under the pessimistic one-step disgnosis strategy［J］.IEEE Transactions on Computers,1991,40(2):232-237.

［5］CHANG G Y,CHANG G J,CHEN G H.Dianosability of regular networks［J］.IEEE Transcations on Parallel and Distributed Systems,2005,16(4):314-322.

［6］HSIEH S Y,LEE C W.Dianosability of two-matching composition networks［C］.Proceedings of the 14th Annual International Computing and Combinatorics Conference,Lecture Notes in Computer Science,2008:478-486.

［7］CHWA K Y,HAKIMI S L.On fault identification in diagnosable systems［J］.IEEE Transactions on Computer,1981,30(6):414-422.

［8］HAKIMI S L,AMIN A T.Characterization of connection assignment of diagnosable systems［J］.IEEE Transactions on Computers,1974,23(1):8-88.

［9］HSIEH S Y,CHEN Y S.Strongly diagnosability product networks under the comparison diagnosis mode［J］.IEEE Transactions on Computers,2008,57(6):721-732.

［10］SHEU J J,HUANG W T,CHEN C H.Strongly diagnosability of regular networks under the comparison model［J］.Information Processing Letters,2008,106:19-25.

［11］CHANG C P,LAI P L,TAN J M,et al.Diagnosability of t-connected Networks and Product Networks under the Comparision Diagnosis Model［J］.IEEE Transactions on Computers,2004,53(12):1582-1590.

［12］WANG Dajin.Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model［J］.IEEE Transactions on Computers,1999,48(12):1369-1374.

［13］EI-AMAWY A,LATIFI S.Properties and performance of folded hypercubes［J］.IEEE Transactions on Parallel and Distributed Systems,1991,2(3):31-42.

［14］ZHU Q,XU J M,HOU X M,et al.On reliability of the folded Hypercubes［J］.Information Sciences,2007,177(8):1782-1788.

［15］ZHU Q,XU J M.On restricted edge connectivity and extra edge connectivity of hypercubes and folded hypercubes［J］.Journal of University of Science and Technology of China,2006,36(3):246-253.

［16］XU J M,ZHU Q,HOU X M,et al.On restricted connectivity and extra connectivity of hypercubes and folded hypercubes［J］.Journal of Shanghai Jiaotong University:Science,2005,10(2):203-207.

［17］TAN X G.The t/k diagnosability of folded cubes［J］.Journal of Jinan University:Natural Science,2010,31(3):245-251.

［18］LAI C N,CHEN G H.w-rabin numbers and strong w-Rabin numbers of folded hypercubes［J］.Networks,2008,51(3):171-177.

［19］KAVIANPOUR A,KIM K H.Diagnosability of hypercubes under the pessimistic one-step diagnosis strategy［J］.IEEE Transactions on Computers,1991,40(2):232-237.

［20］徐俊明.组合网络理论［M］.北京:科学出版社,2007.