Allocation of computations with dynamic structures on hypercube based distributed systems

A dual-level dynamic load distribution strategy is proposed for allocating parallel computations with unpredictable structures to hypercube based distributed systems. Computations with dynamic structures represent a wide range of recursive and divide/conquer algorithms. The allocation strategy supports dynamic partitioning of these computations into communicating sub-tasks. Using the topological characteristics of hypercube networks, the system is divided into multiple regions of processors. The first level allocation is done by the central computer that spreads out the initial computations into these regions to reduce processor contention. The second level allocation is done by the median processors of these regions which enable the processors of their regions to optimally balance the dynamically created load and to communicate with each other with reduced overhead. The results of a simulation study are presented illustrating numerous examples that exhibit the performance of the proposed strategy under different loading conditions, varying degrees of depth and parallelism in the task graphs. The proposed allocation strategy is shown to outperform distributed load distribution