Dimension-exchange token distribution on the mesh and the torus

✍ Scribed by Michael E. Houle; Gavin Turner

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 688 KB
• Volume: 24
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(98)00006-4

✦ Synopsis

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 D ŽŽ . . between maximum and minimum processor loads to d in worst-case optimal Q Dy d P n time steps, where 2 F d -D in the case of an n-by-n mesh, and 4 F d -D in the case of an n-by-n torus.