Complete Exchange Algorithms in Wormhole-Routed Torus Networks

概要

論文の詳細を見る
We present efficient all-to-all personalized communication algorithms for a 2D torus in wormhole-routed networks. Our complete exchange algorithms reduce the number of start-up by a factor of up to 2, which is a good metric for network performance in wormhole networks. Our algorithms divide the whole network into 2×2 networks, giving two contention-free networks with N/2×N/2. After specially designated nodes called master nodes have collected messages, whose destinations are the rest of the basic cells, only master nodes perform complete exchange with a reduced network size. When finished with this complete exchange among master nodes, which results in the desired complete exchange. Then, we present a modified algorithm that further reduces the data transmission time sacrificing the start-up time. After we present our new algorithms, we analyze time complexities and compare several algorithms. We show that our practical algorithm is efficient by a factor of 2 in the required start-up time which means that our algorithms are suitable for wormhole-routed networks.
社団法人電子情報通信学会の論文
2000-04-25