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

    38 Downloads (Pure)


    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
    Number of pages8
    ISBN (Print)978-1-4799-4281-7
    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

    PublisherIEEE Computer Society


    Conference14th International Conference on Application of Concurrency to System Design, ACSD 2014
    Abbreviated titleACSD


    • 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