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

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

通信学报 ›› 2017, Vol. 38 ›› Issue (9): 106-124.doi: 10.11959/j.issn.1000-436x.2017187

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

郭晨^1,²,冷明^1,³,彭硕¹,王博¹

¹ 井冈山大学电子与信息工程学院，江西吉安 343009
² 广西大学电气工程学院，广西南宁 530004
³ 清华大学计算机科学与技术系，北京100084

修回日期:2017-07-10 出版日期:2017-09-01 发布日期:2017-10-18
作者简介:郭晨（1979-），男，江西泰和人，博士，井冈山大学副教授，主要研究方向为网络分析与控制、新型互连网络和系统级故障诊断等。|冷明（1975-），男，江西高安人，博士，井冈山大学教授，主要研究方向为网络分析与控制、云计算和大数据等。|彭硕（1982-），男，江西吉安人，井冈山大学讲师，主要研究方向为智能算法、数据挖掘和数据分析等。|王博（1980-），男，江西吉安人，井冈山大学副教授，主要研究方向为神经网络和进化算法。
基金资助:
国家自然科学基金资助项目(61562046);江西省教育厅科技基金资助项目(GJJ150777);江西省教育厅科技基金资助项目(GJJ160742)

Conditional diagnosability of exchanged crossed cube under the MM model

Chen GUO^1,²,Ming LEMG^1,³,Shuo PENG¹,Bo WANG¹

¹ School of Electronic and Information Engineering,Jinggangshan University,Ji’an 343009,China
² School of Electrical Engineering,Guangxi University,Nanning 530004,China
³ Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China

Revised:2017-07-10 Online:2017-09-01 Published:2017-10-18
Supported by:
The National Natural Science Foundation of China(61562046);Science and Technology Project of Jiangxi Provincial Education Department(GJJ150777);Science and Technology Project of Jiangxi Provincial Education Department(GJJ160742)

摘要/Abstract

摘要：

交换交叉立方网络（ECQ）是新型互连网络拓扑结构研究的最新成果，交换交叉立方网络在保留超立方网络的递归结构、高可划分性和高连通性等优点的基础上，具有相对较小的网络直径、更少的连通边和构建成本，表现出更高的性价比。以交换交叉立方网络为研究对象，通过对交换交叉立方网络拓扑结构的研究，得出交换交叉立方网络的一系列拓扑性质与连通度定理。进而，根据连通度与诊断度的关联关系首次得出交换交叉立方网络ECQ(s,t)在MM模型下的条件诊断度为3 s?2，其中，t≥s≥2。研究成果将为交换交叉立方网络的可靠性评价提供关键性参数，具有重要的理论价值和现实意义。

关键词: 交换交叉立方网络, 条件t-可诊断, 条件故障集合, MM模型, 条件诊断度

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

中图分类号:

TP301

郭晨,冷明,彭硕,王博. 交换交叉立方网络在MM模型下的条件诊断度研究[J]. 通信学报, 2017, 38(9): 106-124.

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.

图/表 27

表1

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

图15

图16

图17

图18

图19

表2

表3

表4

ECQ(s,t) (2≤s≤t≤5)连通性质仿真实验结果"

序号	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个连通分支
			（一个平凡、一个非平凡）	（其中之一是一条边）

表4

表5

表6

CQn、ECQ(s,t)、Dragonfly和Slim Fly的拓扑性质"

网络结构	网络直径	连通度	条件连通度	诊断度(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	—	—	—	—

表6

图20

图21

参考文献 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.

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个连通分支
			（一个平凡、一个非平凡）	（其中之一是一条边）

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

Conditional diagnosability of exchanged crossed cube under the MM model

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 27

参考文献 28

相关文章 2

Metrics

推荐阅读 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]	刘西蒙, 张郁芳, 周书明, 李小燕. 分层超立方网络的可靠性评估[J]. 通信学报, 2021, 42(3): 111-121.
[2]	郭晨,肖志芳,冷明,彭硕,王博. 交换交叉立方网络在PMC模型下的(t,k)-诊断度研究[J]. 通信学报, 2019, 40(6): 190-202.