Over the past few years, many algorithms have been proposed to support collective communication operations for large-scale multicomputers. When proposing any new such algorithm operation, it is critical to determine its precise scope and evaluate it with accurate modelling of the underlying routing and communication mechanisms. However, there has been comparatively little activity in the area of analytical modelling of these operations. As a result, most existing studies have relied on simulation to evaluate the performance merits of collective communication algorithms. This paper presents a new analytical model for predicting broadcast latency in the wormhole-routed torus, which is one of the most common networks used in multicomputers. The broadcast algorithm considered in this study is based on the Bose's broadcast algorithm [Bose, B., Broeg, B., Younggeun, K. and Ashir, Y., 1995, Lee distance and topological properties of k-ary n-cubes, IEEE Transaction on Computers, 44(8), 1021-1030]. Results obtained through simulation experiments show that the model exhibits a good degree of accuracy in predicting message latency under different working conditions.
|Journal||International Journal of Parallel, Emergent and Distributed Systems|
|Publication status||Published - 1 Mar 2005|
- interconnection networks
- broadcast operation
- wormhole routing