Executing scheduled task graphs on message-passing architectures

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume8
Issue number3
DOIs
StatePublished - Sep 1996

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Keywords

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

Fingerprint

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

Cite this