Efficient Token Distribution and Load Balancing on Reconfigurable Meshes with Restricted Bus Length


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.

[Up to Computer Science Technical Report Archive: Home Page]