A COMPARISON STUDY OF HEURISTICS FOR MAPPING PARALLEL ALGORITHMS TO MESSAGE-PASSING MULTIPROCESSORS

Autor:	Dikaiakos, Marios D., Rogers, A., Steiglitz, K.
Přispěvatelé:	Dikaiakos, Marios D. [0000-0002-4350-6058]
Rok vydání:	1995
Předmět:	Theoretical computer science General Computer Science Task flow graphs Interface (Java) Computer science Message passing Parallel algorithm Clustering Annotation Mapping Models of communication Comparison study Cluster analysis Heuristics
Zdroj:	Parallel Algorithms and Applications Parallel Algorithms Appl.
ISSN:	1063-7192
DOI:	10.1080/10637199508915537
Popis:	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 arc 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. © 1995, Taylor & Francis Group, LLC. All rights reserved. 7 3-4 283 302
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0d0da0a66f8e1855856325ef5913c669 https://doi.org/10.1080/10637199508915537 Zobrazit plný text záznamu