In order to minimize the execution time of a parallel application running on a heterogeneously distributed computing system, an appropriate mapping scheme is needed to allocate the application tasks to the processors. The general problem of mapping tasks to machines is a well-known NP-hard problem and several heuristics have been proposed to approximate its optimal solution. In this paper we propose a static graph-based mapping algorithm, called HeterogeneousMulti-phase Mapping (HMM), which permits suboptimal mapping of a parallel application onto a eterogeneous computing distributed system by using a local search technique together with a tabu search meta-heuristic. HMM allocates parallel tasks by exploiting the information embedded in the parallelism forms used to implement an application, and considering an affinity parameter, that identifies which machine in the heterogeneous computing system is most suitable to execute a task.We compare HMM with some leading techniques and with an exhaustive mapping algorithm.We also give an example of mapping of two real applications using HMM. Experimental results show that HMMperforms well demonstrating the applicability of our approach.
A Static Mapping Heuristics to Map Parallel Applications to Heterogeneous Computing Systems
RITROVATO, Pierluigi
2005
Abstract
In order to minimize the execution time of a parallel application running on a heterogeneously distributed computing system, an appropriate mapping scheme is needed to allocate the application tasks to the processors. The general problem of mapping tasks to machines is a well-known NP-hard problem and several heuristics have been proposed to approximate its optimal solution. In this paper we propose a static graph-based mapping algorithm, called HeterogeneousMulti-phase Mapping (HMM), which permits suboptimal mapping of a parallel application onto a eterogeneous computing distributed system by using a local search technique together with a tabu search meta-heuristic. HMM allocates parallel tasks by exploiting the information embedded in the parallelism forms used to implement an application, and considering an affinity parameter, that identifies which machine in the heterogeneous computing system is most suitable to execute a task.We compare HMM with some leading techniques and with an exhaustive mapping algorithm.We also give an example of mapping of two real applications using HMM. Experimental results show that HMMperforms well demonstrating the applicability of our approach.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
