Resource-Constrained Optimal Scheduling of Synchronous Dataflow Graphs via Timed Automata

W. Ahmad, Robert de Groote, P.K.F. Holzenspies, Mariëlle Ida Antoinette Stoelinga, Jan Cornelis van de Pol

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

20 Downloads (Pure)

Abstract

Synchronous dataflow (SDF) graphs are a widely used formalism for modelling, analysing and realising streaming applications, both on a single processor and in a multiprocessing context. Efficient schedules are essential to obtain maximal throughput under the constraint of available resources. This paper presents an approach to schedule SDF graphs using a proven formalism of timed automata (TA). TA maintain a good balance between expressiveness and tractability, and are supported by powerful verification tools, e.g. UPPAAL. We describe a compositional translation of SDF graphs to TA, and perform analysis and verification in the UPPAAL state-of-the-art tool. This approach does not require the (exponential) transformation of SDF graphs to homogeneous SDF graphs and helps to find schedules with a trade-off between the number of processors required and the throughput. It also allows quantitative model checking and verification of (preservation of) user-defined properties such as the absence of deadlocks, safety, liveness and throughput analysis. This translation also forms the basis for future work to extend this analysis of SDF graphs with new features such as stochastics, energy consumption and costs.
Original languageUndefined
Title of host publicationProceedings of the 14th International Conference on Application of Concurrency to System Design (ACSD 2014)
Place of PublicationUSA
PublisherIEEE Computer Society
Pages72-81
Number of pages8
ISBN (Print)978-1-4799-4281-7
DOIs
Publication statusPublished - Jun 2014
Event14th International Conference on Application of Concurrency to System Design, ACSD 2014 - Tunis, Tunisia
Duration: 23 Jun 201427 Jun 2014
Conference number: 14

Publication series

Name
PublisherIEEE Computer Society

Conference

Conference14th International Conference on Application of Concurrency to System Design, ACSD 2014
Abbreviated titleACSD
CountryTunisia
CityTunis
Period23/06/1427/06/14

Keywords

  • EWI-25361
  • IR-93343
  • EC Grant Agreement nr.: FP7/2007-2013
  • EC Grant Agreement nr.: FP7/318490
  • EC Grant Agreement nr.: FP7/610686
  • Timed Automata
  • Throughput
  • Data flow
  • Heterogeneous
  • Scheduling
  • MP3 decoder
  • MP3 playbackapplication
  • MPEG-4 Decoder
  • METIS-309688
  • audio echo canceller

Cite this

Ahmad, W., de Groote, R., Holzenspies, P. K. F., Stoelinga, M. I. A., & van de Pol, J. C. (2014). Resource-Constrained Optimal Scheduling of Synchronous Dataflow Graphs via Timed Automata. In Proceedings of the 14th International Conference on Application of Concurrency to System Design (ACSD 2014) (pp. 72-81). USA: IEEE Computer Society. https://doi.org/10.1109/ACSD.2014.13
Ahmad, W. ; de Groote, Robert ; Holzenspies, P.K.F. ; Stoelinga, Mariëlle Ida Antoinette ; van de Pol, Jan Cornelis. / Resource-Constrained Optimal Scheduling of Synchronous Dataflow Graphs via Timed Automata. Proceedings of the 14th International Conference on Application of Concurrency to System Design (ACSD 2014). USA : IEEE Computer Society, 2014. pp. 72-81
@inproceedings{78ef28d23ff645eaa87362a8e0a1686f,
title = "Resource-Constrained Optimal Scheduling of Synchronous Dataflow Graphs via Timed Automata",
abstract = "Synchronous dataflow (SDF) graphs are a widely used formalism for modelling, analysing and realising streaming applications, both on a single processor and in a multiprocessing context. Efficient schedules are essential to obtain maximal throughput under the constraint of available resources. This paper presents an approach to schedule SDF graphs using a proven formalism of timed automata (TA). TA maintain a good balance between expressiveness and tractability, and are supported by powerful verification tools, e.g. UPPAAL. We describe a compositional translation of SDF graphs to TA, and perform analysis and verification in the UPPAAL state-of-the-art tool. This approach does not require the (exponential) transformation of SDF graphs to homogeneous SDF graphs and helps to find schedules with a trade-off between the number of processors required and the throughput. It also allows quantitative model checking and verification of (preservation of) user-defined properties such as the absence of deadlocks, safety, liveness and throughput analysis. This translation also forms the basis for future work to extend this analysis of SDF graphs with new features such as stochastics, energy consumption and costs.",
keywords = "EWI-25361, IR-93343, EC Grant Agreement nr.: FP7/2007-2013, EC Grant Agreement nr.: FP7/318490, EC Grant Agreement nr.: FP7/610686, Timed Automata, Throughput, Data flow, Heterogeneous, Scheduling, MP3 decoder, MP3 playbackapplication, MPEG-4 Decoder, METIS-309688, audio echo canceller",
author = "W. Ahmad and {de Groote}, Robert and P.K.F. Holzenspies and Stoelinga, {Mari{\"e}lle Ida Antoinette} and {van de Pol}, {Jan Cornelis}",
note = "eemcs-eprint-25361",
year = "2014",
month = "6",
doi = "10.1109/ACSD.2014.13",
language = "Undefined",
isbn = "978-1-4799-4281-7",
publisher = "IEEE Computer Society",
pages = "72--81",
booktitle = "Proceedings of the 14th International Conference on Application of Concurrency to System Design (ACSD 2014)",
address = "United States",

}

Ahmad, W, de Groote, R, Holzenspies, PKF, Stoelinga, MIA & van de Pol, JC 2014, Resource-Constrained Optimal Scheduling of Synchronous Dataflow Graphs via Timed Automata. in Proceedings of the 14th International Conference on Application of Concurrency to System Design (ACSD 2014). IEEE Computer Society, USA, pp. 72-81, 14th International Conference on Application of Concurrency to System Design, ACSD 2014, Tunis, Tunisia, 23/06/14. https://doi.org/10.1109/ACSD.2014.13

Resource-Constrained Optimal Scheduling of Synchronous Dataflow Graphs via Timed Automata. / Ahmad, W.; de Groote, Robert; Holzenspies, P.K.F.; Stoelinga, Mariëlle Ida Antoinette; van de Pol, Jan Cornelis.

Proceedings of the 14th International Conference on Application of Concurrency to System Design (ACSD 2014). USA : IEEE Computer Society, 2014. p. 72-81.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Resource-Constrained Optimal Scheduling of Synchronous Dataflow Graphs via Timed Automata

AU - Ahmad, W.

AU - de Groote, Robert

AU - Holzenspies, P.K.F.

AU - Stoelinga, Mariëlle Ida Antoinette

AU - van de Pol, Jan Cornelis

N1 - eemcs-eprint-25361

PY - 2014/6

Y1 - 2014/6

N2 - Synchronous dataflow (SDF) graphs are a widely used formalism for modelling, analysing and realising streaming applications, both on a single processor and in a multiprocessing context. Efficient schedules are essential to obtain maximal throughput under the constraint of available resources. This paper presents an approach to schedule SDF graphs using a proven formalism of timed automata (TA). TA maintain a good balance between expressiveness and tractability, and are supported by powerful verification tools, e.g. UPPAAL. We describe a compositional translation of SDF graphs to TA, and perform analysis and verification in the UPPAAL state-of-the-art tool. This approach does not require the (exponential) transformation of SDF graphs to homogeneous SDF graphs and helps to find schedules with a trade-off between the number of processors required and the throughput. It also allows quantitative model checking and verification of (preservation of) user-defined properties such as the absence of deadlocks, safety, liveness and throughput analysis. This translation also forms the basis for future work to extend this analysis of SDF graphs with new features such as stochastics, energy consumption and costs.

AB - Synchronous dataflow (SDF) graphs are a widely used formalism for modelling, analysing and realising streaming applications, both on a single processor and in a multiprocessing context. Efficient schedules are essential to obtain maximal throughput under the constraint of available resources. This paper presents an approach to schedule SDF graphs using a proven formalism of timed automata (TA). TA maintain a good balance between expressiveness and tractability, and are supported by powerful verification tools, e.g. UPPAAL. We describe a compositional translation of SDF graphs to TA, and perform analysis and verification in the UPPAAL state-of-the-art tool. This approach does not require the (exponential) transformation of SDF graphs to homogeneous SDF graphs and helps to find schedules with a trade-off between the number of processors required and the throughput. It also allows quantitative model checking and verification of (preservation of) user-defined properties such as the absence of deadlocks, safety, liveness and throughput analysis. This translation also forms the basis for future work to extend this analysis of SDF graphs with new features such as stochastics, energy consumption and costs.

KW - EWI-25361

KW - IR-93343

KW - EC Grant Agreement nr.: FP7/2007-2013

KW - EC Grant Agreement nr.: FP7/318490

KW - EC Grant Agreement nr.: FP7/610686

KW - Timed Automata

KW - Throughput

KW - Data flow

KW - Heterogeneous

KW - Scheduling

KW - MP3 decoder

KW - MP3 playbackapplication

KW - MPEG-4 Decoder

KW - METIS-309688

KW - audio echo canceller

U2 - 10.1109/ACSD.2014.13

DO - 10.1109/ACSD.2014.13

M3 - Conference contribution

SN - 978-1-4799-4281-7

SP - 72

EP - 81

BT - Proceedings of the 14th International Conference on Application of Concurrency to System Design (ACSD 2014)

PB - IEEE Computer Society

CY - USA

ER -

Ahmad W, de Groote R, Holzenspies PKF, Stoelinga MIA, van de Pol JC. Resource-Constrained Optimal Scheduling of Synchronous Dataflow Graphs via Timed Automata. In Proceedings of the 14th International Conference on Application of Concurrency to System Design (ACSD 2014). USA: IEEE Computer Society. 2014. p. 72-81 https://doi.org/10.1109/ACSD.2014.13