An adaptive global reduction algorithm for wormhole-routed 2D meshes |
| |
Affiliation: | 1. Shiraz University of Technology, Department of Mathematics, Shiraz, Iran;1. Department of Electrical Engineering, Sirjan Branch, Islamic Azad University, Sirjan, Iran;2. Young Researchers and Elite Club, Khomeinishahr Branch, Islamic Azad University, Khomeinishahr, Iran |
| |
Abstract: | This paper presents a global reduction algorithm for wormhole-routed 2D meshes. Well-known reduction algorithms that are optimized for short vectors have complexity O(M log N), where N = n × n is the number of nodes, and M the vector length. Algorithms suitable for long vectors have complexity O(√N + M). Previously known asymptotically optimal algorithms with complexity O(log N + M) incur inherent network contention among constituent messages. The proposed algorithm adapts to the given vector length, resulting in complexities O(M log N) for short vectors, O(log N + M) for medium-sized vectors, and O(√N + M) for sufficiently long vectors. The O(√N + M) version is preferred to the O(log N + M) version for long vectors, due to its small coefficient associated with M, the dominating factor for such vectors. The algorithm is contention-free in a synchronous environment. Under asynchronous execution models, depth contention (contention among message-passing steps) may occur. However, simulation studies show that the effect of depth contention on the actual performance is negligible. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|