A new task graph model for mapping message passing applications

Concepció Roig, Ana Ripoll, Fernando Guirado

Research output: Contribution to journalArticleResearchpeer-review

27 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)1740-1753
JournalIEEE Transactions on Parallel and Distributed Systems
Publication statusPublished - 1 Dec 2007


  • Mapping algorithms
  • Modelling message-passing programs
  • Program behaviour
  • Static mapping
  • Task concurrency
  • Task graphs

Fingerprint Dive into the research topics of 'A new task graph model for mapping message passing applications'. Together they form a unique fingerprint.

Cite this