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

**CS-TR-96-12**
**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]