The Transportation Primitives

This paper presents algorithms for implementing the transportation primitive on a distributed memory parallel architecture. The transportation primitive performs many-to-many personalized communication with bounded incoming and outgoing trac. We present a two-stage deterministic algorithm that decomposes the communication with possibly high variance in message size into two communication stages with low message size variance. If the maximum outgoing or incoming trac at any processor is t, transportation can be done in 2t time (+ lower order terms) when t O(p 2 + p=) ( is the inverse of the data transfer rate, is the startup overhead). If the maximum outgoing and incoming trac are r and c respectively, transportation can be done in (r+c) time when either r O(