Reconfiguration algorithms for synchronous communication on switch based degradable arrays

doi:10.1016/j.parco.2022.102901

	Reconfiguration algorithms for synchronous communication on switch based degradable arrays
	Wu, Yalan 1; Wu, Jigang 1; Liu, Peng 1; Han, Yinhe 2; Srikanthan, Thambipillai 3
	2022-07-01
发表期刊	PARALLEL COMPUTING
ISSN	0167-8191
卷号	111 页码:10
摘要	Synchronous communication is one of the most important issues in high performance architectures for large scale of parallel computing, such as matrix computing, image processing, etc. Mesh-connected processor array is characteristic of synchronous communication due to the same length of the interconnects between the neighboring processing elements (PEs) in rows/columns. But long interconnects caused by faulty PEs clearly impact the synchronous communication between the adjacent rows/columns. If long interconnects exist between two adjacent rows, we say that a synchronous communication delay is caused. This paper contributes algorithms to construct logical arrays with synchronous communication in a given host array. Specifically, an algorithm for synchronous communication array (ASCA) is firstly presented, to construct a maximum logical array with synchronous communication. When all of the long interconnects are independent each other, the proposed algorithm is proved to be optimal. After that, two heuristic algorithms are also proposed, to construct a logical array with given size, by integrating the proposed ASCA and two exclusion schemes. The proposed two exclusion schemes are based on strategies of divide-and-conquer and the longest logical column first, respectively. In addition, the lower bound of synchronous communication delay for a logical array is calculated by an algorithm also developed in this paper, in order to evaluate the synchronous performance of reconfiguration algorithms. Simulation results show that, the proposed two heuristic algorithms have their own advantages for different cases. The synchronous communication delay of the logical arrays is significantly reduced, and it is very close to the lower bound for the cases of small fault density and larger exclusion rate. For 32 x 32 physical arrays with exclusion rates that are larger than 15%, the synchronous communication delay of logical array is reduced from 11.09 to 6.97, which is more closer to the lower bound 4.43, for different fault densities on average.
关键词	Mesh-connected processor array Reconfiguration algorithm Fault-tolerance Synchronous communication
DOI	10.1016/j.parco.2022.102901
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[62072118] ; National Natural Science Foundation of China[62174038] ; GuangDong Basic and Applied Basic Research Foundation[2021B1515120010] ; GuangDong Basic and Applied Basic Research Foundation[2021A1515011962]
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000793751100008
出版者	ELSEVIER
引用统计	被引频次：1[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/19561
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Wu, Jigang
作者单位	1.Guangdong Univ Technol, Sch Comp Sci & Technol, Guangzhou 510006, Guangdong, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China 3.Nanyang Technol Univ, Sch Comp Sci & Engn, Singapore 639798, Singapore
推荐引用方式 GB/T 7714	Wu, Yalan,Wu, Jigang,Liu, Peng,et al. Reconfiguration algorithms for synchronous communication on switch based degradable arrays[J]. PARALLEL COMPUTING,2022,111:10.
APA	Wu, Yalan,Wu, Jigang,Liu, Peng,Han, Yinhe,&Srikanthan, Thambipillai.(2022).Reconfiguration algorithms for synchronous communication on switch based degradable arrays.PARALLEL COMPUTING,111,10.
MLA	Wu, Yalan,et al."Reconfiguration algorithms for synchronous communication on switch based degradable arrays".PARALLEL COMPUTING 111(2022):10.