This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in Web of Science Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Beaumont, O. Articles by Robert, Y. Search for Related Content Social Bookmarking                         What's this?

Complexity Results for Collective Communications on Heterogeneous Platforms

LABRI, UMR CNRS 5800 BORDEAUX, FRANCE

L. Marchal

Y. Robert

LIP, UMR CNRS-INRIA 5668 ENS LYON, FRANCE YVES.ROBERT{at}ENS-LYON.FR

In this paper, we consider the communications involved in the execution of a complex application, deployed on a heterogeneous platform. Such applications extensively use macro-communication schemes, for example to broadcast data items, either to all resources (broadcast) or to a restricted set of targets (multicast). Rather than aiming at minimizing the execution time of a single collective communication, we focus on the steady-state operation. We assume that there is a large number of messages to be broadcast or multicast in pipelined fashion, and we aim at maximizing the throughput, i.e. the (rational) number of messages which can be broadcast or multicast every timestep. We target heterogeneous platforms, modeled by a graph where resources have different communication and computation speeds. Achieving the best throughput may well require that the target platform is used in totality: different messages may need to be transferred along different paths.

The main focus of the paper is on complexity results. We aim at presenting a unified framework for analyzing the complexity of collective communication schemes. We concentrate on the classification (whether maximizing the throughput is a polynomial or NP-hard problem), rather than actually providing efficient polynomial algorithms (when such algorithms are known, we refer to bibliographical pointers).

Key Words: scheduling • collective communications • NPcompleteness • broadcast • heuristics • heterogeneous • clusters • grids

International Journal of High Performance Computing Applications, Vol. 20, No. 1, 5-17 (2006)
DOI: 10.1177/1094342006061877


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?