交换交叉立方网络在PMC模型下的(t,k)-诊断度研究

doi:10.11959/j.issn.1000-436x.2019099

Abstract

Abstract:

Exchanged crossed cube(ECQ) is one of the latest achievements in the research of topology of novel interconnection networks.ECQ is a more optimized form of organization for multi-processor parallel computers,which retains the advantages of exchanged hypercube and crossed cube in terms of the smaller diameter,fewer links,and lower cost factor,and which indicates more balanced consideration.However,so far,ECQ hadn’t been formally introduced into multi-processor parallel computers.One of the main reasons was that its reliability research wasn’t yet systematic.Among them,the operational reliability represented by diagnosability was the most urgent.ECQ was taken as studying object,after topological analyzing,some important topological properties of ECQ were introduced,which determines the (t,k)-diagnosability of ECQ(s,t) under the PMC model by theoretical deduction and simulation experiments.Simulation results show that ECQ reliability complement and improvement,which provides strong technical support for subsequent application and popularization.

Key words: exchanged crossed cube, PMC model, (t,k)-diagnosable, (t,k)-diagnosability

CLC Number:

TP301

GUO Chen,XIAO Zhifang,LEMG Ming,PENG Shuo,WANG Bo. (t,k)-diagnosability of exchanged crossed cube under the PMC model[J]. Journal on Communications, 2019, 40(6): 190-202.

Figures/Tables 16

ECQ(s,)t		(t ₁,k)-可诊断（仿真结果）		$(⌊ 2^{\frac{s + t + 2 + δ}{4}} ⌋, s + 1)$ +可诊断（理论结果）
s	t	t₁	k	$⌊ 2^{\frac{s + t + 2}{4}} ⌋$	$⌊ 2^{\frac{s + t + 2 + 1}{4}} ⌋$	s+ 1
1	1	2	2	2	2	2
1	2	2	2	2	2	2
1	3	3	2	2	3	2
1	4	3	2	3	4	2
1	5	4	2	4	4	2
2	2	3	3	2	3	3
2	3	3	3	3	4	3
2	4	4	3	4	4	3
2	5	5	3	4	5	3
3	3	4	4	4	4	4
3	4	5	4	4	5	4
3	5	6	4	5	6	4
4	4	6	5	5	6	5
4	5	7	5	6	8	5
5	5	9	6	8	9	6

References 22

[1]	LAI P L , TAN J M , CHANG C P ,et al. Conditional diagnosability measures for large multiprocessor systems[J]. IEEE Transactions on Computers, 2005,54(2): 165-175.
[2]	PREPARATA F P , METZE G , CHIEN R T . On the connection assignment problem of diagnosable systems[J]. IEEE Transactions Electronic Computers, 1967,16(12): 848-854.
[3]	ARAKI T , SHIBATA Y . (t,k)-diagnosable system:a generalization of the PMC models[J]. IEEE Transactions on Computers, 2003,52(7): 971-975.
[4]	CHANG G Y . Conditional (t,k)-diagnosis under the PMC model[J]. IEEE Transactions Parallel and Distributed Systems, 2011,22(11): 1797-1803.
[5]	CHANG G Y , CHEN G H , CHANG G J . (t,k)-diagnosis for matching composition networks[J]. IEEE Transactions Computers, 2006,55(1): 88-92.
[6]	CHEN C A , HSIEH S Y . (t,k)-diagnosis for component-composition graphs under the MM* model[J]. IEEE Transactions Computers, 2011,60(12): 1704-1717.
[7]	CHEN C A , CHANG G Y , HSIEH S Y . Conditional (t,k)-diagnosis in graphs by using the comparison diagnosis model[J]. IEEE Transactions Computers, 2015,64(6): 1622-1632.
[8]	WEI C C , CHEN C A , HSIEH S Y . Conditional (t,k)-diagnosis in regular and irregular graphs under the comparison diagnosis model[J]. IEEE Transactions Dependable and Secure Computing, 2016,PP(99): 1-7.
[9]	CHEN C A , HSIEH S Y . Component-composition graphs:(t,k)-diagnosability and its application[J]. IEEE Transactions on Computers, 2013,62(6): 1097-1110.
[10]	熊茜, 梁家荣, 马强 . 交换超立方网络的(t,k)故障诊断度研究[J]. 通信学报, 2016,37(3): 190-198.
	XIONG X , LIANG J R , MA Q . Research on (t,k)-diagnosability for exchanged hypercube network[J]. Journal on Communications, 2016,37(3): 190-198.
[11]	梁家荣, 陈秒江 . 基于比较模型的扩展立方体网络的(t,k)-诊断度研究[J]. 通信学报, 2017,38(8): 9-18.
	LIANG J R , CHEN M J . Research on(t,k)-diagnosability for augmented cube network under the comparison model[J]. Journal on Communications, 2017,38(8): 9-18.
[12]	FENG N T . A survey of interconnection networks[J]. Computer, 1981,14(12): 12-27.
[13]	LI K , MU Y , K LI . Exchanged crossed cube:a novel interconnection network for parallel computation[J]. IEEE Transactions on Parallel and Distributed Systems, 2013,24(11): 2211-2219.
[14]	PETER K K , HSU W J , PAN Y . The exchanged hypercube[J]. IEEE Transactions on Parallel and Distributed Systems, 2005,6(9): 866-874.
[15]	EFE K . The crossed cube architecture for parallel compution[J]. IEEE Transactions on Parallel and Distributed Systems, 1992,3(5): 513-646.
[16]	PENG S L , LIN C K , TAN J J M ,et al. The g-good-neighbor conditional diagnosability of hypercube under PMC model[J]. Applied Mathematics and Computation, 2012,218(21): 10406-10412.
[17]	NING W , FENG X , WANG L . The connectivity of exchanged crossed cube[J]. Information Processing Letters, 2015,115(2): 394-396.
[18]	郭晨, 冷明, 彭硕 ,等. 交换交叉立方网络在MM模型下的条件诊断度研究[J]. 通信学报, 2017,38(9): 106-124.
	GUO C , LENG M , PENG S ,et al. Conditional diagnosability of exchanged crossed cube under the MM model[J]. Journal on Communications, 2017,38(9): 106-124.
[19]	HAKIMI S L , AMIN A T . Characterization of connection assignment of diagnosable systems[J]. IEEE Transactions on Computers, 1974,23(1): 86-88.
[20]	张大方, 江招生 . 基于集团的系统级故障诊断研究[J]. 计算机学报, 1998,21(4): 308-314.
	ZHANG D F , JIANG Z S . The research of the system-level fault diagnosis based on the body[J]. Chinese Journal of Computers, 1998,21(4): 308-314.
[21]	郭晨, 梁家荣, 葛志辉 ,等. 基于互测PMC模型的条件诊断算法[J]. 电子学报, 2015,43(2): 255-261.
	GUO C , LIANG J R , GE Z H ,et al. A conditional diagnosis algorithm based on ex-test PMC model[J]. ACTA Electronica Sinica, 2015,43(2): 255-261.
[22]	YE L C , LIANG J R . Five-round adaptive diagnosis in hamiltonian networks[J]. IEEE Transactions Parallel ＆ Distributed Systems, 2015,26(9): 2459-2464.

Metrics

Recommended 0

No Suggested Reading articles found!

u	v	σ (u,v)
00	01	0 1
1	0	0/1
1	1	0/1

节点编号	节点地址值	节点编号	节点地址值	节点编号	节点地址值	节点编号	节点地址值
0	00000	8	01000	16	10000	24	11000
1	00001	9	01001	17	10001	25	11001
2	00010	10	01010	18	10010	26	11010
3	00011	11	01011	19	10011	27	11011
4	00100	12	01100	20	10100	28	11100
5	00101	13	01101	21	10101	29	11101
6	00110	14	01110	22	10110	30	11110
7	00111	15	01111	23	10111	31	11111

(t,k)-diagnosability of exchanged crossed cube under the PMC model

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 16

References 22

Related Articles 2

Metrics

Recommended 0

序号																节点编号
序号	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1
3	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0
4	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1
5	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0
6	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	1
#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#
2³²-1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0
2³²	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1

[1]	Chen GUO,Ming LEMG,Shuo PENG,Bo WANG. Conditional diagnosability of exchanged crossed cube under the MM model [J]. Journal on Communications, 2017, 38(9): 106-124.
[2]	Xi XIONG,Jia-rong LIANG,Qiang MA. Research on(t,k)-diagnosability for exchanged hypercube network [J]. Journal on Communications, 2016, 37(3): 190-198.

序号																节点编号
序号	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1
2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0
3	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0
4	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
5	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0
#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#
5 178	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#
35 959	1	1	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
35 960	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0