TY - JOUR
T1 - Design and analysis of pipelined broadcast algorithms for the all-port interlaced bypass torus networks
AU - Zhang, Peng
AU - Deng, Yuefan
N1 - Funding Information:
The study was funded by USM RUI grant 1001/PPSP/812097. We also want to thank Assoc Professor Dr Sarimah Abdullah for statistics consultation
PY - 2012
Y1 - 2012
N2 - Broadcast algorithms for the interlaced bypass torus networks (iBT networks) are introduced to balance the all-port bandwidth efficiency and to avoid congestion in multidimensional cases. With these algorithms, we numerically analyze the dependencies of the broadcast efficiencies on various packet-sending patterns, bypass schemes, network sizes, and dimensionalities and then strategically tune up the configurations for minimizing the broadcast steps. Leveraging on such analysis, we compare the performance of networks with one million nodes between two cases: one with an added fixed-length bypass links and the other with an added torus dimension. A case study of iBT(1000 2; b = (8, 32)) and Torus(1003) shows that the former improves the diameter, average node-to-node distance, rectangular and global broadcasts over the latter by approximately 80 percent. It is reaffirmed that strategically interlacing short bypass links and methodically utilizing these links is superior to adding dimensionalities to torus in achieving shorter diameter, average node-to-node distances and faster broadcasts.
AB - Broadcast algorithms for the interlaced bypass torus networks (iBT networks) are introduced to balance the all-port bandwidth efficiency and to avoid congestion in multidimensional cases. With these algorithms, we numerically analyze the dependencies of the broadcast efficiencies on various packet-sending patterns, bypass schemes, network sizes, and dimensionalities and then strategically tune up the configurations for minimizing the broadcast steps. Leveraging on such analysis, we compare the performance of networks with one million nodes between two cases: one with an added fixed-length bypass links and the other with an added torus dimension. A case study of iBT(1000 2; b = (8, 32)) and Torus(1003) shows that the former improves the diameter, average node-to-node distance, rectangular and global broadcasts over the latter by approximately 80 percent. It is reaffirmed that strategically interlacing short bypass links and methodically utilizing these links is superior to adding dimensionalities to torus in achieving shorter diameter, average node-to-node distances and faster broadcasts.
KW - Parallel computing
KW - broadcast
KW - collective communication
KW - interlaced bypass torus
KW - network performance
UR - http://www.scopus.com/inward/record.url?scp=84869479690&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84869479690&partnerID=8YFLogxK
U2 - 10.1109/TPDS.2012.93
DO - 10.1109/TPDS.2012.93
M3 - Article
AN - SCOPUS:84869479690
SN - 1045-9219
VL - 23
SP - 2245
EP - 2253
JO - IEEE Transactions on Parallel and Distributed Systems
JF - IEEE Transactions on Parallel and Distributed Systems
IS - 12
M1 - 6171171
ER -