Paper Info
Title
A comparison of techniques used for mapping parallel algorithms to message-passing multiprocessors
Abstract
This paper presents a comparison study of popular clustering and mapping heuristics which are used to map task-flow graphs to message-passing multiprocessors. To this end, we use task-graphs which are representative of important scientific algorithms running on data-sets of practical interest. The annotation which assigns weights to nodes and edges of the task-graphs is realistic. It reflects current trends in processor, communication channel, and message-passing interface technology and takes into consideration hardware characteristics of state-of-the-art multiprocessors. Our experiments show that applying realistic models for task-graph annotation affects the effectiveness and functionality of clustering and mapping techniques. Therefore, new heuristics are necessary that will take into account more practical models of communication costs. We present modifications to existing clustering and mapping algorithms which improve their efficiency and running-time for the practical models adopted.
Year
DOI
Venue
1994
10.1109/SPDP.1994.346137
Dallas, TX
Keywords
Field
DocType
communication channel,parallel algorithm,parallel algorithms,software systems,computer science,message passing,clustering algorithms,message passing interface,clustering,astronomy,graph theory,hardware,parallel programming,concurrent computing,edges,nodes,communication channels
Graph theory,Computer science,Parallel algorithm,Parallel computing,Communication channel,Models of communication,Theoretical computer science,Heuristics,Message Passing Interface,Cluster analysis,Message passing,Distributed computing
Conference
ISBN
Citations 
PageRank 
0-8186-6427-4
5
0.62
References 
Authors
10
3
Name
Order
Citations
PageRank
Marios D. Dikaiakos169772.63
Kenneth Steiglitz21128660.13
Anne Rogers3529.44