交换交叉立方网络在MM模型下的条件诊断度研究

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

Abstract

Abstract:

Exchanged crossed cube (ECQ) was the latest achievement in the study of novel interconnection network topology.ECQ retained the advantages of hypercube such as recursive structure,high partitionability and strong connectivity,with better properties than other variations of hypercube in terms of the smaller diameter,fewer links,and lower cost factor,which indicated more balanced consideration among performance and cost.As the study object,after topological analyzing,some important topological properties and connectivity theorems of ECQ were introduced,then the conditional diagnosability of ECQ(s,t)was determined under the MM model,which was 3s 2? for t≥s≥2.The research results will provide the key parameters for the reliability evaluation of ECQ in the future.So it has important theoretical significance and application value.

Key words: exchanged crossed cube, conditional t-diagnosable, conditional fault set, MM model, conditional diagnosability

CLC Number:

TP301

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.

Figures/Tables 27

序号	s	t	\|F\|≤2s?1时ECQ(s,t)?F 的连通情况	F 是条件故障集合且\|F\|≤3s?3时ECQ(s,t)?F 的连通情况
			\|F\|≤2时连通；
1	2	2	2<\|F\|≤3时连通或只有2个连通分支	\|F\|≤3时连通
			（一个平凡、一个非平凡）
			\|F\|≤2时连通；
2	2	3	2<\|F\|≤3时连通或只有2个连通分支	\|F\|≤3时连通
			（一个平凡、一个非平凡）
			\|F\|≤2时连通；
3	2	4	2<\|F\|≤3时连通或只有2个连通分支	\|F\|≤3时连通
			（一个平凡、一个非平凡）
			\|F\|≤2时连通；
4	2	5	2<\|F\|≤3时连通或只有2个连通分支	\|F\|≤3时连通
			（一个平凡、一个非平凡）
			\|F\|≤3时连通；	\|F\|≤5时连通；
5	3	3	3<\|F\|≤5时连通或只有2个连通分支	5<\|F\|≤6时连通或只有2个连通分支
			（一个平凡、一个非平凡）	（其中之一是一条边）
			\|F\|≤3时连通；	\|F\|≤5时连通；
6	3	4	3<\|F\|≤5时连通或只有2个连通分支	5<\|F\|≤6时连通或只有2个连通分支
			（一个平凡、一个非平凡）	（其中之一是一条边）
			\|F\|≤3时连通；	\|F\|≤5时连通；
7	3	5	3<\|F\|≤5时连通或只有2个连通分支	5<\|F\|≤6时连通或只有2个连通分支
			（一个平凡、一个非平凡）	（其中之一是一条边）
			\|F\|≤4时连通；	\|F\|≤7时连通；
8	4	4	4<\|F\|≤7时连通或只有2个连通分支	7<\|F\|≤9时连通或只有2个连通分支
			（一个平凡、一个非平凡）	（其中之一是一条边）
			\|F\|≤4时连通；	\|F\|≤7时连通；
9	4	5	4<\|F\|≤7时连通或只有2个连通分支	7<\|F\|≤9时连通或只有2个连通分支
			（一个平凡、一个非平凡）	（其中之一是一条边）
			\|F\|≤5时连通；	\|F\|≤9时连通；
10	5	5	5<\|F\|≤9时连通或只有2个连通分支	9<\|F\|≤12时连通或只有2个连通分支
			（一个平凡、一个非平凡）	（其中之一是一条边）

网络结构	网络直径	连通度	条件连通度	诊断度(PMC)	条件诊断度(MM)
CQ _n	$⌈ \frac{n + 1}{2} ⌉$	n	2n?2	n	3n?5
ECQ (s,t)	$⌈ \frac{s + 1}{2} ⌉ + ⌈ \frac{t + 1}{2} ⌉ + 2$	s+ 1	2s	s+ 1	3s?2
Dragonfly	3	—	—	—	—
Slim Fly	2	—	—	—	—

References 28

[1]	SQUIRE G S , PALAIS S M . Physical and logical design of a highly parallel computer[R]. Tech Note, 1962,University of Michigan.
[2]	EL-AMAWY A , LATIFI S . Properties and performance of folded hypercubes[J]. IEEE Transactions on Parallel and Distributed Sys-tems, 1991,2(3): 31-42
[3]	EFE K . The crossed cube architecture for parallel computation[J]. IEEE Transactions on Parallel and Distributed Systems, 1992,3(5): 513-646.
[4]	LARSON S M , CULL P . The M?bius cubes[J]. IEEE Transactions on Computer, 1995,44(5): 647-659.
[5]	HUANG K , WU J . Area efficient layout of balanced hypercubes[J]. International Journal of High Speed Electronics and Systems, 1995,6(4): 631-646.
[6]	WANG D Q , ZHAO L C . The twisted-cube connected networks[J]. Computer Science and Technology, 1999,2(14): 181-186.
[7]	YANG X F , EVANS D J , MEGSON G M . The locally twisted cubes[J]. International Journal of Computer Mathematics, 2005,82(4): 401-413.
[8]	PETER K K , HSU W J , PAN Y . The exchanged hypercube[J]. IEEE Transactions on Parallel and Distributed Systems, 2005,6(9): 866-874.
[9]	LI K , MU Y , LI K ,et al. Exchanged crossed cube:a novel intercon-nection network for parallel computation[J]. IEEE Transactions on Parallel and Distributed Systems, 2013,24(11): 2211-2219.
[10]	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.
[11]	ZHU Q . On conditional diagnosability and reliability of the BC networks[J]. Journal of Supercomputing, 2008,45(2): 173-184.
[12]	XU M , THULASIRAMAN K , HU X D . Conditional diagnosability of matching composition networks under the PMC model[J]. IEEE Transactions on Circuits and Systems-II:Express Briefs, 2009,56(11): 875-879.
[13]	HSU G H , CHIANG C F , SHIH L M ,et al. Conditional diagnosability of hypercubes under the comparison diagnosis model[J]. Journal of Systems Architecture, 2009,55(2): 140-146.
[14]	YANG M C . Conditional diagnosability of matching composition networks under the MM ^?model[J]. Information Sciences, 2013,233(233): 230-243.
[15]	YANG M C . Conditional diagnosability of balanced hypercubes under the PMC model[J]. Information Sciences, 2013,222(222): 754-760.
[16]	YANG M C . Conditional diagnosability of balanced hypercubes under the MM ^?model[J]. The Journal of Supercomputing, 2013,65(3): 1264-1278.
[17]	MALEK M , . A comparison connection assignment for diagnosis of multiprocessor systems[C]// Seventh Int'l Symp,Computer Architecture. 1980: 31-36.
[18]	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.
[19]	NING W , FENG X , WANG L . The connectivity of exchanged crossed cube[J]. Information Processing Letters, 2015,115(2): 394-396.
[20]	FAN J , LIN X , JIA X . Node-pancyclicity and edge-pancyclicity of crossed cubes[J]. Information Processing Letters, 2005,93(3): 133-138.
[21]	SENGUPTA A , DAHBURA A T . On self-diagnosable multiprocessor systems:diagnosis by the comparison approach[J]. IEEE Transactions on Computers, 1992,41(11): 1386-1396.
[22]	LIN C , TAN J J M , HSU L ,et al. Conditional diagnosability of cayley graphs generalized by transposition tree under the comparison diagnosis model[J]. Journal of Interconnection Networks, 2008,9(1): 83-97.
[23]	郭晨, 梁家荣, 冷明 . 基于PMC模型的条件故障诊断[J]. 电子学报, 2015,43(11): 2331-2337.
	GUO C , LIANG J R , LENG M . The conditional fault diagnosis of PMC model[J]. Acta Electronica Sinica, 2015,43(11): 2331-2337.
[24]	KIM J , DALLY W J , SCOTT S ,et al. Technology-driven,highly-scalable dragonfly topology[J]. Acm Sigarch Computer Architecture News, 2008,36(3): 77-88.
[25]	BESTA M , HOEFLER T . Slim Fly:a cost effective low-diameter network topology[C]// High Performance Computing,Networking,Storage and Analysis,SC14:International Conference for. IEEE, 2014: 348-359.
[26]	KIM J . High-radix interconnection networks[D]. Palo Alto:Stanford University, 2008.
[27]	雷斐, 董德尊, 庞征斌 ,等. Paleyfly:一种可扩展的高速互连网络拓扑结构[J]. 计算机研究与发展, 2015,52(6): 1329-1340.
	LEI F , DONG D Z , PANG Z B ,et al. Paleyfly:a scalable topology in high performance interconnection network[J]. Journal of Computer Research and Development, 2015,52(6): 1329-1340.
[28]	廖湘科, 肖侬 . 新型高性能计算系统与技术[J]. 中国科学:信息科学, 2016,46(9): 1175-1210.
	LIAO X K , XIAO N . Emerging high-performance computing systems and technology[J]. Scientia Sinica Informations, 2016,46(9): 1175-1210.

Metrics

Recommended 0

No Suggested Reading articles found!

w	u	v	σ ((u,v)_w)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0或1
1	0	1	0或1
1	1	0	0或1
1	1	1	0或1

序号	s	t	拓扑性质
序号	s	t	节点三角	\|N(u)∩N(v)\|	A和B之间是否含有长度为4的环	N[u]和N[v]至多出现在几条相同的水平直线中，其中， u,v∈A	N[u]和N[v]至多出现在几条相同的水平直线中，其中， u∈A,v∈B
1	1	1	不含	≤1	不含	0	1
2	1	2	不含	≤2	不含	0	1
3	1	3	不含	≤2	不含	0	1
4	1	4	不含	≤2	不含	0	1
5	1	5	不含	≤2	不含	0	1
6	2	2	不含	≤2	不含	2	1
7	2	3	不含	≤2	不含	2	1
8	2	4	不含	≤2	不含	2	1
9	2	5	不含	≤2	不含	2	1
10	3	3	不含	≤2	不含	2	1
11	3	4	不含	≤2	不含	2	1
12	3	5	不含	≤2	不含	2	1
13	4	4	不含	≤2	不含	2	1
14	4	5	不含	≤2	不含	2	1
15	5	5	不含	≤2	不含	2	1

序号	s	t	\|F\|≤2s?1时ECQ(s,t)?F 的连通情况	F 是条件故障集合且\|F\|≤3s?3时ECQ(s,t)?F 的连通情况
			\|F\|≤2时连通；
1	2	2	2<\|F\|≤3时连通或只有2个连通分支	\|F\|≤3时连通
			（一个平凡、一个非平凡）
			\|F\|≤2时连通；
2	2	3	2<\|F\|≤3时连通或只有2个连通分支	\|F\|≤3时连通
			（一个平凡、一个非平凡）
			\|F\|≤2时连通；
3	2	4	2<\|F\|≤3时连通或只有2个连通分支	\|F\|≤3时连通
			（一个平凡、一个非平凡）
			\|F\|≤2时连通；
4	2	5	2<\|F\|≤3时连通或只有2个连通分支	\|F\|≤3时连通
			（一个平凡、一个非平凡）
			\|F\|≤3时连通；	\|F\|≤5时连通；
5	3	3	3<\|F\|≤5时连通或只有2个连通分支	5<\|F\|≤6时连通或只有2个连通分支
			（一个平凡、一个非平凡）	（其中之一是一条边）
			\|F\|≤3时连通；	\|F\|≤5时连通；
6	3	4	3<\|F\|≤5时连通或只有2个连通分支	5<\|F\|≤6时连通或只有2个连通分支
			（一个平凡、一个非平凡）	（其中之一是一条边）
			\|F\|≤3时连通；	\|F\|≤5时连通；
7	3	5	3<\|F\|≤5时连通或只有2个连通分支	5<\|F\|≤6时连通或只有2个连通分支
			（一个平凡、一个非平凡）	（其中之一是一条边）
			\|F\|≤4时连通；	\|F\|≤7时连通；
8	4	4	4<\|F\|≤7时连通或只有2个连通分支	7<\|F\|≤9时连通或只有2个连通分支
			（一个平凡、一个非平凡）	（其中之一是一条边）
			\|F\|≤4时连通；	\|F\|≤7时连通；
9	4	5	4<\|F\|≤7时连通或只有2个连通分支	7<\|F\|≤9时连通或只有2个连通分支
			（一个平凡、一个非平凡）	（其中之一是一条边）
			\|F\|≤5时连通；	\|F\|≤9时连通；
10	5	5	5<\|F\|≤9时连通或只有2个连通分支	9<\|F\|≤12时连通或只有2个连通分支
			（一个平凡、一个非平凡）	（其中之一是一条边）

Conditional diagnosability of exchanged crossed cube under the MM model

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 27

References 28

Related Articles 3

Metrics

Recommended 0

序号	s	t	t_c(ECQ(s,t))
1	2	2	4
2	2	3	4
3	2	4	4
4	2	5	4
5	3	3	7
6	3	4	7
7	3	5	7
8	4	4	10
9	4	5	10
10	5	5	13

[1]	Ximeng LIU, Yufang ZHANG, Shuming ZHOU, Xiaoyan LI. Reliability evaluation of hierarchical hypercube network [J]. Journal on Communications, 2021, 42(3): 111-121.
[2]	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.
[3]	Xiao-feng YANG,Ming-ming SUN,Xue-lei HU,Jing-yu YANG. Improved HMM model based method for detecting cyber attacks [J]. Journal on Communications, 2010, 31(3): 95-101.