Communication-Aware Scheduling Algorithms for Synchronous Dataflow Graphs on Multicore Systems

Mingze Ma; Rizos Sakellariou

doi:10.1145/3229631.3229643

Communication-Aware Scheduling Algorithms for Synchronous Dataflow Graphs on Multicore Systems

Mingze Ma, Rizos Sakellariou

Information Management

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

Abstract

Synchronous dataflow graphs are widely used to model digital signal processing and multimedia applications. Self-timed execution is an efficient methodology for the analysis and scheduling of synchronous dataflow graphs. In this paper, we propose a communication-aware self-timed execution approach to solve the problem of scheduling synchronous dataflow graphs on multicore systems with communication delays. Based on this communication-aware self-timed execution approach, four communication-aware scheduling algorithms are proposed using different allocation rules. The proposed algorithms are experimentally evaluated in terms of throughput and runtime using realistic applications.

Original language	English
Title of host publication	SAMOS '18: Proceedings of the 18th International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation
Pages	55-64
Number of pages	10
DOIs	https://doi.org/10.1145/3229631.3229643
Publication status	Published - 14 Jan 2019
Event	2018 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation - Duration: 15 Jul 2018 → …

Conference

Conference	2018 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation
Period	15/07/18 → …

Keywords

Multicore systems
Scheduling
Self-timed execution
Synchronous dataflow graphs

Access to Document

10.1145/3229631.3229643

Cite this

@inproceedings{e453f3d055654716bf3c1a95f4e9b6f0,

title = "Communication-Aware Scheduling Algorithms for Synchronous Dataflow Graphs on Multicore Systems",

abstract = "Synchronous dataflow graphs are widely used to model digital signal processing and multimedia applications. Self-timed execution is an efficient methodology for the analysis and scheduling of synchronous dataflow graphs. In this paper, we propose a communication-aware self-timed execution approach to solve the problem of scheduling synchronous dataflow graphs on multicore systems with communication delays. Based on this communication-aware self-timed execution approach, four communication-aware scheduling algorithms are proposed using different allocation rules. The proposed algorithms are experimentally evaluated in terms of throughput and runtime using realistic applications.",

keywords = "Multicore systems, Scheduling, Self-timed execution, Synchronous dataflow graphs",

author = "Mingze Ma and Rizos Sakellariou",

year = "2019",

month = jan,

day = "14",

doi = "10.1145/3229631.3229643",

language = "English",

pages = "55--64",

booktitle = "SAMOS '18: Proceedings of the 18th International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation",

note = "2018 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation ; Conference date: 15-07-2018",

}

Ma, M & Sakellariou, R 2019, Communication-Aware Scheduling Algorithms for Synchronous Dataflow Graphs on Multicore Systems. in SAMOS '18: Proceedings of the 18th International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation. pp. 55-64, 2018 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, 15/07/18. https://doi.org/10.1145/3229631.3229643

Communication-Aware Scheduling Algorithms for Synchronous Dataflow Graphs on Multicore Systems. / Ma, Mingze; Sakellariou, Rizos.
SAMOS '18: Proceedings of the 18th International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation. 2019. p. 55-64.

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Communication-Aware Scheduling Algorithms for Synchronous Dataflow Graphs on Multicore Systems

AU - Ma, Mingze

AU - Sakellariou, Rizos

PY - 2019/1/14

Y1 - 2019/1/14

N2 - Synchronous dataflow graphs are widely used to model digital signal processing and multimedia applications. Self-timed execution is an efficient methodology for the analysis and scheduling of synchronous dataflow graphs. In this paper, we propose a communication-aware self-timed execution approach to solve the problem of scheduling synchronous dataflow graphs on multicore systems with communication delays. Based on this communication-aware self-timed execution approach, four communication-aware scheduling algorithms are proposed using different allocation rules. The proposed algorithms are experimentally evaluated in terms of throughput and runtime using realistic applications.

AB - Synchronous dataflow graphs are widely used to model digital signal processing and multimedia applications. Self-timed execution is an efficient methodology for the analysis and scheduling of synchronous dataflow graphs. In this paper, we propose a communication-aware self-timed execution approach to solve the problem of scheduling synchronous dataflow graphs on multicore systems with communication delays. Based on this communication-aware self-timed execution approach, four communication-aware scheduling algorithms are proposed using different allocation rules. The proposed algorithms are experimentally evaluated in terms of throughput and runtime using realistic applications.

KW - Multicore systems

KW - Scheduling

KW - Self-timed execution

KW - Synchronous dataflow graphs

UR - http://www.scopus.com/inward/record.url?scp=85060996685&partnerID=8YFLogxK

U2 - 10.1145/3229631.3229643

DO - 10.1145/3229631.3229643

M3 - Conference contribution

SP - 55

EP - 64

BT - SAMOS '18: Proceedings of the 18th International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation

T2 - 2018 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation

Y2 - 15 July 2018

ER -

Communication-Aware Scheduling Algorithms for Synchronous Dataflow Graphs on Multicore Systems

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this