Total-exchange on wormhole k-ary n-cubes with adaptive routing
Fabrizio Petrini · 2002
The total exchange is one of the most dense communication patterns and is at the heart of numerous applications and programming models in parallel computing. We present a simple randomized algorithm to efficiently schedule the total exchange on the family of k-ary n-cubes with adaptive routing and wormhole switching. This algorithm is based on an important property of the wormhole networks that reach high throughput under uniform traffic. The experimental results, conducted on a 256-node bidimensional cube using an adaptive routing algorithm based on J. Duato's (1993) methodology, show that the proposed exchange algorithm reaches a very high throughput with small and medium sized packers, around 85% of the optimal bound, and is more efficient than other algorithms presented in the literature.