Authors: Heiko Schr\"oder, Gavin Turner
Source: GZipped PostScript (71kb); Adobe PDF
(332kb)
A solution to the token distribution problem is presented for the 2{-}dimensional reconfigurable mesh with restricted bus length. The algorithm is shown to be asymptotically worst-case optimal in r educing the discrepancy $\Delta$ between maximum and minimum processor loads to $\delta$ in optimal $\Theta((\Delta{-}\delta)\cdot n)$ time steps. The algorithm meets the time complexity of current state-of-the-art algorithms for sorting and permutation routing, but remains a factor of 2 from the bisection bound.