Routing with Finite Speeds of Memory and Network

On practical parallel computers, the time for routing a distribution of sufficiently large packets can be approximated by $\max\{T_f, T_b\}$. Here $T_f$ is proportional to the maximum number of bytes a PU sends and receives, and $T_b$ is proportional to the maximum number of bytes a connection in the network has to transfer. We show that several important routing patterns can be performed by a sequence of balanced all-to-all routings and analyze how to optimally perform these under the above cost-model. We concentrate on dimension-order routing on meshes, and assume that the routing pattern must be decomposed into a sequence of permutations. The developed strategy has been implemented on the Intel Paragon. In comparison with the trivial strategy, in which $\mi{PU}_i$ routes to $\mi{PU}_{(i + t) \bmod P}$ in permutation~$t$, $1 \leq t < P$, one gains between $10$ and $20\%$