Abstract
We can easily envision large-scale MIMD machines solving complex problems of unpredictable behavior in the area in artificial intelligence. Processor utilization is the key factor that decides the speedup of a parallel system. To maximize utilization, computations must be uniformly distributed to all processors. Due to the dynamic nature of such problems, the challenge is to allocate and distribute tasks dynamically with minimum run time overhead. We present a distributed and adaptive load-balancing scheme for medium-grain tasks in this context. The scheme attempts to balance load within a neighborhood by distributing tasks such that all neighbors have loads close to the neighborhood average. We describe such a neighborhood averaging scheme and compare to other two schemes that have been proposed in this context. The performance of these schemes on a 16-node Intel iPSC/2 demonstrates the effectiveness of our scheme.