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.
A mapping heuristic for minimizing network contention
Raffaele Perego
1998
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
prod_267987-doc_160788.pdf
non disponibili
Descrizione: A mapping heuristic for minimizing network contention
Tipologia:
Versione Editoriale (PDF)
Dimensione
1.13 MB
Formato
Adobe PDF
|
1.13 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.