Istituto di Scienza e Tecnologie dell'Informazione     
Perego R. A Mapping Heuristic for Minimizing Network Contention. In: Journal of Systems Architecture, vol. 45 (1) pp. 65 - 82. Elsevier, 1998.
The combinatorial optimization problem of assigning tasks of a parallel program to processing nodes (pn's) of a parallel system is a well-known NP-hard problem. In this paper a new greedy heuristic for compile-time mapping of tasks without precedence constraints is proposed. The solution is addressed to modern multicomputers based on k-ary n-cube direct interconnection networks exploiting the e-cube routing algorithm and the wormhole flow control strategy. The proposed algorithm takes into account communication delays due to network blocking of colliding messages. Results achieved on several program-derived graphs with up to 784 tasks demonstrate the effectiveness of the approach followed.
Subject Mapping heuristics
Greedy algorithms
Wormhole routing
C.2 Computer-Communication Networks

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