5HETEROGENEOUS PLATFORMS COMPLEXITY RESULTS FOR COLLECTIVE COMMUNICATIONS ON HETEROGENEOUS PLATFORMS

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 broad-cast 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 com-munication, 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 time-step. 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: dif-ferent messages may need to be transferred along differ-ent 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 con-centrate 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 bibliograph-ical pointers)