A new task graph model for mapping message passing applications

The exploitation of parallelism in a message-passing platform implies a previous modelling phase of the parallel application as a task graph, which properly reflects its temporal behaviour. In this paper, we analyse the classical task graph models of the literature and their drawbacks when modelling message-passing programs with arbitrary task structure. We define a new task graph model called TTIG (Temporal Task Interaction Graph) that integrates the classical models used in the literature. The TTIG allows to explicitly capture the ability of concurrency of adjacent tasks for applications where adjacent tasks can communicate at any point inside them. A mapping strategy is developed from this model, that minimizes the expected execution time by properly exploiting task parallelism. The effectiveness of this approach has been proved in different experimentation scopes for a wide range of message-passing applications. © 2007 IEEE.