A mapping heuristic for minimizing network contention
Raffaele Perego
Greedy algorithms Mapping heuristics Wormhole routing Hardware and Architecture Software Network contention
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.
Source: Journal of systems architecture 45 (1998): 65–82. doi:10.1016/S1383-7621(97)00073-8
Publisher: Elsevier, Oxford ;, Paesi Bassi
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:267987,
title = {A mapping heuristic for minimizing network contention},
author = {Raffaele Perego},
publisher = {Elsevier, Oxford ;, Paesi Bassi},
doi = {10.1016/s1383-7621(97)00073-8},
journal = {Journal of systems architecture},
volume = {45},
pages = {65–82},
year = {1998}
}
0000-0001-7189-4724DOIAlso available from
