3‐D data partitioning for 3‐level perfectly nested loops on heterogeneous distributed systems. (10th November 2016)

• Record Type: Journal Article
• Authors: Zarei Zefreh, Ebrahim; Lotfi, Shahriar; Mohammad Khanli, Leyli; Karimpour, Jaber
• Is Part Of: Concurrency and computation. Volume 29:Number 5(2017)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2016-11-10
• Subjects: communication -- data partitioning -- heterogeneous distributed systems -- load balancing -- nested loop; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.3976
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: Nested loops are the largest source of parallelism in many data‐parallel scientific applications. Heterogeneous distributed systems are popular computing platforms for data‐parallel applications. Data partitioning is critical in exploiting the computational power of such systems, and existing data partitioning algorithms try to maximize performance of data‐parallel applications by finding a data distribution that balances the workload between the processing nodes while minimizing communication costs. This paper addresses the problem of 3‐dimensional data partitioning for 3‐level perfectly nested loops on heterogeneous distributed systems. The primary aim is to minimize the execution time by improving the load balancing and minimizing the internode communications. We propose a new data partitioning algorithm using dynamic programming, build a theoretical model to estimate the execution time of each partition, and select a partition with minimum execution time as a near‐optimal solution. We demonstrate the effectiveness of the new algorithm for 2 data‐parallel scientific applications on heterogeneous distributed systems. The new algorithm reduces the execution time by between 7% and 17%, on average, compared with leading data partitioning methods on 3 heterogeneous distributed systems.