3-D data partitioning for 3-level perfectly nested loops onrnheterogeneous distributed systems

摘要

Nested loops are the largest source of parallelism in many data-parallel scientific applications.rnHeterogeneous distributed systems are popular computing platforms for data-parallel applications.rnData partitioning is critical in exploiting the computational power of such systems, andrnexisting data partitioning algorithms try tomaximize performance of data-parallel applications byrnfinding a data distribution that balances the workload between the processing nodes while minimizingrncommunication costs.This paper addresses theproblemof3-dimensionaldata partitioningrnfor 3-level perfectly nested loops on heterogeneous distributed systems. The primary aim is tornminimize the execution time by improving the load balancing and minimizing the internode communications.rnWe propose a new data partitioning algorithm using dynamic programming, build arntheoretical model to estimate the execution time of each partition, and select a partitionwith minimumrnexecution time as a near-optimal solution. We demonstrate the effectiveness of the newrnalgorithm for 2 data-parallel scientific applications on heterogeneous distributed systems. Thernnew algorithm reduces the execution time by between 7% and 17%, on average, compared withrnleading data partitioning methods on 3 heterogeneous distributed systems.