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 language | English (US) |
|---|---|
| Pages (from-to) | 271-294 |
| Number of pages | 24 |
| Journal | International Journal of High Speed Computing |
| Volume | 8 |
| Issue number | 3 |
| DOIs | |
| State | Published - Sep 1996 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Computational Theory and Mathematics
Keywords
- Directed acyclic graphs
- Iterative computation
- Message-passing architectures
- Schedule execution
- Task scheduling