Title :
Token distribution on reconfigurable d-dimensional meshes
Author :
Turner, Gavin ; Schröder, Heiko
Abstract :
We propose an algorithm to solve the Token Distribution problem, a static variant of the load balancing problem, on d-dimensional, reconfigurable meshes with toroidal connections and side length n. No other algorithms have been proposed under this model of computation. We show that for token size T, the discrepancy Δ between the maximum and minimum number of tokens per PE can be reduced to 1 in at most 2nΔ(T+4d) steps
Keywords :
multiprocessor interconnection networks; reconfigurable architectures; resource allocation; token networks; algorithm; load balancing; reconfigurable d-dimensional meshes; reconfigurable meshes; token distribution; toroidal connections; Computational modeling; Computer science; Control systems; Costs; Hardware; Joining processes; Load management; Switches;
Conference_Titel :
Algorithms and Architectures for Parallel Processing, 1995. ICAPP 95. IEEE First ICA/sup 3/PP., IEEE First International Conference on
Conference_Location :
Brisbane, Qld.
Print_ISBN :
0-7803-2018-2
DOI :
10.1109/ICAPP.1995.472203
