Optimal Partitioning of Square Computational Domains for Parallel Computing on Hybrid Servers With Heterogeneous Processors and Heterogeneous Communication Links

In this work, we formulate and solve the mathematical problem of optimal partitioning of a real-valued square computational domain across three heterogeneous processors connected by three heterogeneous communication links. The objective is to minimize the communication time of the data-parallel application processing this domain, assuming that its computation time is minimized by balancing the load of the processors. The state-of-the-art methods ignore the heterogeneity of the communication links and try to minimize the total amount of communicated data instead of the communication time. As a result, optimal partitions found by these methods may not minimize the communication time on mainstream heterogeneous hybrid servers with heterogeneous data links. We introduce a bandwidth-aware communication cost function, representing the communication time of parallel processing for each given partition. Using this function, we identify and prove the optimality of four partitioning shapes and 24 candidate partitions, which can potentially minimize the communication cost. We derive analytical formulas for the communication cost of each candidate partition and use them to find the optimal one for each given combination of bandwidths of communication links and ratio of processor speeds. The state-of-the-art bandwidth-oblivious methods only identify 3 optimal partitioning shapes and 3 candidate partitions. Through extensive simulations, we compare optimal partitioning shapes found by the bandwidth-aware and bandwidth-oblivious methods for the full range of processor speed ratios and realistic bandwidths of communication links. We also experimented on two real hybrid heterogeneous servers, each comprising a multi-core CPU and two accelerators. These experiments demonstrate the superior prediction accuracy of the bandwidth-aware communication model over its bandwidth-oblivious counterpart, resulting in truly optimal partitioning solutions in all conducted experiments.