Mapping pipeline skeletons onto heterogeneous platforms

Mapping applications onto parallel platforms is a challenging problem, that becomes even more difficult when platforms are heterogeneous — nowadays a standard assumption. A high-level approach to parallel programming not only eases the application developer’s task, but it also provides additional information which can help realize an efficient mapping of the application.In this paper, we discuss the mapping of pipeline skeletons onto different types of platforms: Fully Homogeneous platforms with identical processors and interconnection links; Communication Homogeneous platforms, with identical links but different-speed processors; and finally, Fully Heterogeneous platforms. We assume that a pipeline stage must be mapped on a single processor, and we establish new theoretical complexity results for different mapping policies: a mapping can be required to be one-to-one (a processor is assigned at most one stage), or interval-based (a processor is assigned an interval of consecutive stages), or fully general. In particular, we show that determining the optimal interval-based mapping is NP-hard for Communication Homogeneous platforms, and this result assesses the complexity of the well-known chains-to-chains problem for different-speed processors. We provide several efficient polynomial heuristics for the most important policy/platform combination, namely interval-based mappings on Communication Homogeneous platforms. These heuristics are compared to the optimal result provided by the formulation of the problem in terms of the solution of an integer linear program, for small problem instances.