Divisible Nonlinear Load Distribution on Heterogeneous Single-Level Trees

This work studies the divisible nonlinear load distribution problem on heterogeneous single-level tree networks with a collective communication model. The goal is to find a feasible distribution that minimizes the parallel processing time. The classical model of nonlinear computational loads omits many processing steps, and yields only an approximate solution to distribute fractional loads. This work considers a new model of nonlinear computational loads that includes all of processing steps of the load. This model can simplify recursive equation for the size of fractional loads and yield a practical solution to distribute fractional loads. This work proposes two new methods which incorporates a new nonlinear computational model to distribute a divisible nonlinear load on heterogeneous single-level tree networks. Closed-form expressions for the parallel processing time and speedup for single-level tree networks are derived. This work demonstrates that the asymptotic speed-up of the proposed algorithm ism + 1 where m is the number of child processors in a single-level tree network. We show that our algorithm improved the previous method in terms of speed-up.