PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Baraglia R., Ferrini R., Ritrovato P. A Static Mapping Heuristic for Mapping Parallel Applications to Heterogeneous Computing Systems. Submitted to "Concurrency and Computation: Practice and Experience" (International Journal), Technical report, 2003.
 
 
Abstract
(English)
To minimize the execution time of a parallel application running on a heterogeneous computing distributed system, an appropriate mapping scheme to allocate the application tasks to the processors is needed. 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 a 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. We compare HMM with three different leading techniques and with an exhaustive mapping algorithm. We also give an example of mapping of a pratical application where HMM verified its usefulness. Experimental results show that HMM performs well demonstrating the applicability of our approach.
Subject Parallel processing
Static mapping
Task mapping
Optimization
Performance evaluation
D.4.1 Process Management
D.4.1 Process Management : Metacomputing / Grid computing / Heterogeneous


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