AN ADAPTIVE GLOBAL REDUCTION ALGORITHM FOR WORMHOLE-ROUTED 2D MESHES

This paper presents a global reduction algorithm for wormhole-routed 2 D meshes. Well-known reduction algorithms that are optimized for short vectors have complexity O(M log N), where N = n x n is the number of nodes, and M the vector length. Algorithms suitable for long vectors h ave complexity O(root N + M). Previously known asymptotically optimal algorithms with complexity O(log N + M) incur inherent network content ion among constituent messages. The proposed algorithm adapts to the g iven vector length, resulting in complexities O(M log N) for short vec tors, O(log N + M) for medium-sized vectors, and O(root N + M) for suf ficiently long vectors. The O(root N + M) versions preferred to the O( log N + M) version for long vectors, due to its small coefficient asso ciated with M, the dominating factor for such vectors. The algorithm i s contention-free in a synchronous environment. Under asynchronous exe cution models, depth contention (contention among message-passing step s) may occur. However, simulation studies show that the effect of dept h contention on the actual performance is negligible. (C) 1997 Elsevie r Science B.V.