Executing scheduled task graphs on message-passing architectures

Research output: Contribution to journalArticlepeer-review


A directed acyclic task graph (DAG) contains a set of tasks which access a set of data items and perform certain computations on those data items. The problem of DAG scheduling that optimizes the assignment of tasks onto the given processors has been studied extensively in the literature. We have developed a DAG scheduling system called PYRROS that maps the computation of task graphs onto message-passing machines [24]. In this paper we present a schedule executing model that incorporates several optimization strategies to reduce communication overhead and improve memory utilization. We study the correctness of task graph execution using this method and generalize this result to the iterative execution of a task graph and present experimental results on an nCUBE-2 parallel machine.

Original languageEnglish (US)
Pages (from-to)271-294
Number of pages24
JournalInternational Journal of High Speed Computing
Issue number3
StatePublished - Sep 1996

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics


  • Directed acyclic graphs
  • Iterative computation
  • Message-passing architectures
  • Schedule execution
  • Task scheduling


Dive into the research topics of 'Executing scheduled task graphs on message-passing architectures'. Together they form a unique fingerprint.

Cite this