Dimension Exchange Token Distribution on the Linear Array and Ring


Author: Gavin Turner
Source: GZipped PostScript (68kb); Adobe PDF (329kb)

We propose and analyse an algorithm to optimally solve the Token Distribution problem, a static variant of the load balancing problem, on the ring and linear-array. The algorithm has the added benefit that it is a dimension exchange algorithm. Dimension exchange algorithms use a colouring of the interconnection network to pair procesors for data exchange, are extremely simple, and totally scalable.

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