Dimension--exchange token distribution on the mesh and the torus

摘要

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 Δ between maximum and minimum processor loads to δ in worst--case optimal Θ((Δ -δ)·n) time steps, where 2≤δ＜Δ in the case of an n-by-n mesh, and 4≤δ＜Δ in the case of an n-by-n torus.