The Case for Network Coding for Collective Communication on HPC Interconnection Networks

Ahmed SHALABY  Ikki FUJIWARA  Michihiro KOIBUCHI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.3   pp.661-670
Publication Date: 2015/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2014EDP7255
Type of Manuscript: PAPER
Category: Information Network
Keyword: 
interconnection networks,  collective communication,  network coding,  high-performance computing,  

Full Text: FreePDF(1.7MB)


Summary: 
Recently network bandwidth becomes a performance concern particularly for collective communication since bisection bandwidths of supercomputers become far less than their full bisection bandwidths. In this context we propose the use of a network coding technique to reduce the number of unicasts and the size of data transferred in latency-sensitive collective communications in supercomputers. Our proposed network coding scheme has a hierarchical multicasting structure with intra-group and inter-group unicasts. Quantitative analysis show that the aggregate path hop counts by our hierarchical network coding decrease as much as 94% when compared to conventional unicast-based multicasts. We validate these results by cycle-accurate network simulations. In 1,024-switch networks, the network reduces the execution time of collective communications as much as 70%. We also show that our hierarchical network coding is beneficial for any packet size.