Cache-Oblivious MPI All-to-All Communications Based on Morton Order

doi:10.1109/TPDS.2017.2768413

	Cache-Oblivious MPI All-to-All Communications Based on Morton Order
	Li, Shigang 1; Zhang, Yunquan 1; Hoefler, Torsten 2
	2018-03-01
发表期刊	IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
ISSN	1045-9219
卷号	29 期号:3 页码:542-555
摘要	Many-core systems with a rapidly increasing number of cores pose a significant challenge to parallel applications to use their complex memory hierarchies efficiently. Many such applications rely on collective communications in performance-critical phases, which become a bottleneck if they are not optimized. We address this issue by proposing cache-oblivious algorithms for MPI_Alltoall, MPI_Allgather, and the MPI neighborhood collectives to exploit the data locality. To implement the cache-oblivious algorithms, we allocate the send and receive buffers on a shared heap and use Morton order to guide the memory copies. Our analysis shows that our algorithm for MPI_Alltoall is asymptotically optimal. We show an extension to our algorithms to minimize the communication distance on NUMA systems while maintaining optimality within each socket. We further demonstrate how the cache-oblivious algorithms can be applied to multi-node machines. Experiments are conducted on different many-core architectures. For MPI_Alltoall, our implementation achieves on average 1.40X speedup over the naive implementation based on shared heap for small and medium block sizes (less than 16 KB) on a Xeon Phi KNC, achieves on average 3.03X speedup over MVAPICH2 on a Xeon E7-8890, and achieves on average 2.23X speedup over MVAPICH2 on a 256-node Xeon E5-2680 cluster for block sizes less than 1 KB.
关键词	cache-oblivious algorithms collective communication NUMA MPI_Alltoall MPI_Allgather neighborhood collectives
DOI	10.1109/TPDS.2017.2768413
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[61502450] ; National Natural Science Foundation of China[61432018] ; National Natural Science Foundation of China[61521092] ; National Key R&D Program of China[2016YFB0200800] ; National Key R&D Program of China[2017YFB0202302]
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Theory & Methods ; Engineering, Electrical & Electronic
WOS记录号	WOS:000425173200005
出版者	IEEE COMPUTER SOC
引用统计	被引频次：16[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/5656
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Li, Shigang
作者单位	1.Chinese Acad Sci, Inst Comp Technol, State Key Lab Comp Architecture, Beijing 100864, Peoples R China 2.ETH, Dept Comp Sci, CH-8092 Zurich, Switzerland
推荐引用方式 GB/T 7714	Li, Shigang,Zhang, Yunquan,Hoefler, Torsten. Cache-Oblivious MPI All-to-All Communications Based on Morton Order[J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,2018,29(3):542-555.
APA	Li, Shigang,Zhang, Yunquan,&Hoefler, Torsten.(2018).Cache-Oblivious MPI All-to-All Communications Based on Morton Order.IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,29(3),542-555.
MLA	Li, Shigang,et al."Cache-Oblivious MPI All-to-All Communications Based on Morton Order".IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 29.3(2018):542-555.