Authors: Michael E. Houle, Gavin Turner
Source: GZipped PostScript (84kb); Adobe PDF
(357kb)
A solution to the token distribution problem is presented for the 2{-}dimensional mesh and torus, based on the dimension{-}exchange strategy. The approach is shown to reduce the discrepancy {\{\em s} between maximum and minimum processor loads to {\{\em d} in optimal Theta(({\{\em s}{-}{\{\em d})*{\{\em n}) time steps, where $2 \leq d < s$ for the mesh, and $4 \leq d < s$ for the torus.