Thumbnail
Access Restriction
Open

Author Houle, Michael E. ♦ Symvonis, Antonios ♦ Wood, David R.
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Token Distribution ♦ Tree-connected Architecture ♦ Underlying Topology ♦ System Cannot ♦ Scalable Method ♦ Improved Analysis ♦ Token-distribution Problem ♦ Token Distributio ♦ Arbitrary Graph ♦ Atomic Element ♦ Multi-processor System ♦ Simple Local Exchange Protocol ♦ Load Balancing Problem ♦ Dimension-exchange Token Distribution Algorithm ♦ New Dimension-exchange Algorithm ♦ Arbitrary Tree ♦ Static Variant ♦ So-called Dimension-exchange Approach ♦ Repetitive Application ♦ Distributed-memory Parallel Architecture
Abstract Load balancing on a multi-processor system involves redistributing tasks among processors so that each processor has roughly the same amount of work to perform. The token-distribution problem is a static variant of the load balancing problem for the case in which the workloads in the system cannot be divided arbitrarily; that is, where each token represents an atomic element of work. A scalable method for distributing tokens over a distributed-memory parallel architecture is the so-called dimension-exchange approach, which is based on the repetitive application of extremely simple local exchange protocols. Our results include improved analysis of two existing dimension-exchange token distribution algorithms on arbitrary graphs and on arbitrary trees, respectively. These algorithms require no knowledge of the underlying topology, but do not always determine a `perfectly balanced' distribution of tokens. We then present a new dimension-exchange algorithm for token distributio...
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2000-01-01