Layer based partition for matrix multiplication on heterogeneous mesh networks

While many approaches have been proposed to analyze the problem of matrix multiplication parallel computing, few of them address the problem on heterogeneous networks. It still remains an open question on heterogeneous networks to find the optimal schedule that balances the load within the heterogeneous processor set while minimizing the communication volume. A great many studies are based on rectangular partition, whereas the optimality of rectangular partition as the basis has not been well justified. In this paper, we propose an alternative approach called layer based partition (LBP), which jointly optimizes the total communication volume and task completion time. We also take network topology into account, by applying LBP on mesh networks. Simulation shows LBP reduces the total communication volume by 81%, while balancing load among all heterogeneous processors in mesh networks.