Exploiting Geometric Partitioning in Task Mapping for Parallel Computers
Citations Over TimeTop 10% of 2014 papers
Abstract
We present a new method for mapping applications' MPI tasks to cores of a parallel computer such that communication and execution time are reduced. We consider the case of sparse node allocation within a parallel machine, where the nodes assigned to a job are not necessarily located within a contiguous block nor within close proximity to each other in the network. The goal is to assign tasks to cores so that interdependent tasks are performed by "nearby" cores, thus lowering the distance messages must travel, the amount of congestion in the network, and the overall cost of communication. Our new method applies a geometric partitioning algorithm to both the tasks and the processors, and assigns task parts to the corresponding processor parts. We show that, for the structured finite difference mini-app Mini Ghost, our mapping method reduced execution time 34% on average on 65,536 cores of a Cray XE6. In a molecular dynamics mini-app, Mini MD, our mapping method reduced communication time by 26% on average on 6144 cores. We also compare our mapping with graph-based mappings from the LibTopoMap library and show that our mappings reduced the communication time on average by 15% in MiniGhost and 10% in MiniMD.
Related Papers
- → Architecture independent parallel selection with applications to parallel priority queues(2003)13 cited
- → Node Selection Model for Block Transmission in a Blockchain Network(2021)1 cited
- → Integrating parallel algorithm design with parallel machine models(1995)5 cited
- Research on Parallel Algorithm and Related Problems(2008)
- Communication-Efficient Bulk Synchronous Parallel Algorithms(2001)