PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Baraglia R., Ferrini R., Ritrovato P. A static mapping heuristics to map parallel applications to heterogeneous computing systems. In: Concurrency and Computation-Practice & Experience, vol. 17 (13) pp. 1579 - 1605. John Wiley & Sons, Ltd, 2005.
 
 
Abstract
(English)
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 Heterogeneous Multi-phase Mapping (HMM), that permits suboptimal mapping of a parallel application onto a heterogeneous 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 HC system is most suitable for executing a task. We compare HMM with four different 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 HMM performs well demonstrating the applicability of our approach.
URL: http://www3.interscience.wiley.com/cgi-bin/jissue/112096856
Subject Parallel processing
Static mapping
Task mapping
Performance evaluation
Metacomputing/Grid
D.4.1 Process Management


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional