A novel data-partitioning algorithm for performance optimization of data-parallel applications on heterogeneous HPC platforms

Hamidreza Khaleghzadeh, Ravi Reddy Manumachu, Alexey Lastovetsky

Research output: Contribution to journalArticlepeer-review


Modern HPC platforms have become highly heterogeneous owing to tight integration of multicore CPUs and accelerators (such as Graphics Processing Units, Intel Xeon Phis, or Field-Programmable Gate Arrays) empowering them to maximize the dominant objectives of performance and energy efficiency. Due to this inherent characteristic, processing elements contend for shared on-chip resources such as Last Level Cache (LLC), interconnect, etc. and shared nodal resources such as DRAM, PCI-E links, etc. This has resulted in severe resource contention and Non-Uniform Memory Access (NUMA) that have posed serious challenges to model and algorithm developers. Moreover, the accelerators feature limited main memory compared to the multicore CPU host and are connected to it via limited bandwidth PCI-E links thereby requiring support for efficient out-of-card execution. To summarize, the complexities (resource contention, NUMA, accelerator-specific limitations, etc.) have introduced new challenges to optimization of data-parallel applications on these platforms for performance. Due to these complexities, the performance profiles of data-parallel applications executing on these platforms are not smooth and deviate significantly from the shapes that allowed state-of-the-art load-balancing algorithms to find optimal solutions. In this paper, we formulate the problem of optimization of data-parallel applications on modern heterogeneous HPC platforms for performance. We then propose a new model-based data partitioning algorithm, which minimizes the execution time of computations in the parallel execution of the application. This algorithm takes as input a set of p discrete speed functions corresponding top available heterogeneous processors. It does not make any assumptions about the shapes of these functions. We prove the correctness of the algorithm and its complexity of O ( m 3 × p 3 ), where m is the cardinality of the input discrete speed functions. We experimentally demonstrate the optimality and efficiency of our algorithm using two data-parallel applications, matrix multiplication and fast Fourier transform, on a heterogeneous cluster of nodes where each node contains an Intel multicore Haswell CPU, an Nvidia K40c GPU, and an Intel Xeon Phi co-processor.
Original languageEnglish
Pages (from-to)2176-2190
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number10
Publication statusPublished - 16 Apr 2018


  • Heterogeneous HPC platforms
  • data-parallel applications
  • data partitioning
  • load balancing
  • multicore CPU
  • GPU
  • Intel Xeon Phi
  • performance optimization


Dive into the research topics of 'A novel data-partitioning algorithm for performance optimization of data-parallel applications on heterogeneous HPC platforms'. Together they form a unique fingerprint.

Cite this