Performance limits of divisible load processing in systems with limited communication buffers

摘要

In this work, we study influence of limited size of communication buffer on the efficiency of divisible loads processing. Divisible loads are computations which can be divided into parts of arbitrary sizes, and these parts can be processed in parallel. To finish processing in the shortest possible time an optimum distribution of the load must be calculated. The method of determining load distribution must take into account not only computing speed, but also interconnection system topology, communication medium speed and startup time. In this work, we include one more parameter: communication buffer size. We propose a general method of studying the influence of the communication buffer size on the interaction between the communication and computations. Three archetypal interconnection topologies are examined: stars, ordinary trees, and binomial trees. The results of modeling the performance of parallel systems show that the influence of communication buffer size is indirect and qualitative in nature. Buffer size affects the performance by causing message fragmentation, or changing load balance among the processors. We analyze performance of several communication algorithms and their interaction with the computations. The simulations show that these classic algorithms are limited. (C) 2004 Elsevier Inc. All rights reserved.