The Intel Paragon is a mesh-connected distributed memory parallel computer. The complete exchange is one such pattern.
Several approaches are available for carrying it out on the mesh.
We study an algorithm developed by Scott. This algorithm assumes that a communication link can carry one message at a time and that a node can only transmit one message at a time. It requires global synchronization to enforce a schedule of transmissions. Unfortunately global synchronization has substantial overhead on the Paragon. At the same time the powerful interconnection mechanism of this machine permits 2 or 3 messages to share a communication link with minor overhead.