Configurable complete exchanges in 2D torus-connected networks

Complete exchange communications are found necessary in many important parallel algorithms. This paper presents algorithms for complete exchange for 2D torus-connected multiprocessors. The proposed algorithms are unique in that they are configurable while trading the time for message startups against larger message sizes. At one extreme, the algorithm minimizes the number of message startups at the expense of increased message-transmission time. At the other extreme, the message-transmission time is reduced at the expense of increased number of message startups. The algorithms are structured such that intermediate solutions are feasible, i.e., the number of message startups can be increased slightly and the message-transmission time is correspondingly reduced. The ability to configure these algorithms makes the proposed algorithms distinct from others and leads to efficient portable implementation of complete exchange algorithms