.png){kind=icon}
Return
Optimization-based mapping framework for parallel applications
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jpdc.2011.06.005.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The mapping of tasks of a parallel program onto nodes of a parallel computing system has a remarkable impact on application performance. In this paper we propose an optimization framework to solve the mapping problem, which takes into account the communication matrix of the application and a cost matrix that depends on the topology of the parallel system. This cost matrix is usually a distance matrix (the classic approach), but we propose a novel definition of the cost criterion, applicable to torus networks, that tries to distribute traffic evenly over the different axes; we call this the Traffic Distribution criterion. As the mapping problem can be seen as a particular instance of the Quadratic Assignment Problem (QAP), we can apply any QAP solver to this problem. In particular, we use a greedy randomized algorithm. Using simulation, we test the performance levels of the optimization-based mappings, and compare them with those of trivial mappings (consecutive, random), in two different environments: single application (one application uses all system resources all the time) and space sharing (several applications run simultaneously, on different system partitions), using systems with 2D and 3D topologies and real application traffic. Experimental results show that some applications do not benefit from optimization-based mappings: those in which there is a match between virtual and physical topologies, and those that carry out massive all-to-all communications. In other cases, optimization-based mappings with the TD criterion provide excellent performance levels. (C) 2011 Elsevier Inc. All rights reserved.
Keywords:
Optimization-based mapping of parallel applications
Mapping as an instance of the Quadratic Assignment Problem
Scheduling for supercomputers
Mappings on 2D and 3D cubes
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K
Organization
Cited Papers
Stability of Reference Genes for Messenger RNA Quantification by Real-Time PCR in Mouse Dextran Sodium Sulfate Experimental Colitis.png)
PLOS ONE
OAAI
PLOS ONEIF0
OAAIShareSaveReduced white matter microstructural integrity correlates with cognitive deficits in minimal hepatic encephalopathyGut
GutIF0
PREAI
ShareSaveShareSave
SIMULATED ANNEALING FOR THE QAP - OPTIMAL TRADEOFF BETWEEN SIMULATION TIME AND SOLUTION QUALITY
PREAI
ShareSaveShareSave
View more