Skip to Main content Skip to Navigation
Conference papers

Is Acyclic Directed Graph Partitioning Effective for Locality-Aware Scheduling?

Abstract : We investigate efficient execution of computations, modeled as Directed Acyclic Graphs (DAGs), on a single processor with a two-level memory hierarchy, where there is a limited fast memory and a larger slower memory. Our goal is to minimize execution time by minimizing redundant data movement between fast and slow memory. We utilize a DAG partitioner that finds localized, acyclic parts of the whole computation that can fit into fast memory, and minimizes the edge cut among the parts. We propose a new scheduler that executes each part one-by-one, obeying the dependency among parts, aiming at reducing redundant data movement needed by cut-edges. Extensive experimental evaluation shows that the proposed DAG-based scheduler significantly reduces redundant data movement.
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-02273122
Contributor : Equipe Roma <>
Submitted on : Friday, September 27, 2019 - 12:20:30 PM
Last modification on : Wednesday, February 26, 2020 - 11:14:13 AM
Long-term archiving on: : Monday, February 10, 2020 - 6:00:51 AM

File

PPAM-submitted.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02273122, version 1

Collections

Citation

Yusuf Özkaya, Anne Benoit, Umit Catalyurek. Is Acyclic Directed Graph Partitioning Effective for Locality-Aware Scheduling?. PPAM 2019 - 13th International Conference on Parallel Processing and Applied Mathematics, Sep 2019, Bialystok, Poland. ⟨hal-02273122⟩

Share

Metrics

Record views

145

Files downloads

395