CSDFa: a model for exploiting the trade-off between data and pipeline parallelism

Peter Koek, S.J. Geuns, J.P.H.M. Hausmans, Henk Corporaal, Marco Jan Gerrit Bekooij

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

    1 Citation (Scopus)

    Abstract

    Real-time stream processing applications, such as SDR applications, are often executed concurrently on multiprocessor systems. A unified data flow model and analysis method have been proposed that can be used to simultaneously determine the amount of pipeline and coarse-grained data parallelism required to meet the temporal constraints of such applications. However, this unified model is only defined for SDF graphs. Defining a unified model for a more expressive model such as CSDF is not possible, because auto-concurrency can cause a time-dependent order of tokens and dependencies. This paper introduces the CSDFa model. In CSDFa, tokens have indices and the consumption order of tokens is static and time-independent. This allows expressing and trading off pipeline and coarse-grained data parallelism in a single, unified model. Furthermore, we introduce a new type of circular buffer that implements the same static order as is used by the CSDFa model. The overhead of operations on this buffer is independent of the amount of auto-concurrency, which corresponds to the constant firing durations in the CSDFa model. Exploiting the trade-off between data and pipeline parallelism with the CSDFa model is demonstrated with a part of a FMCW radar processing pipeline. We show that the CSDFa model enables optimizing the balance between processing units and memory, resulting in a significant reduction of silicon area. Additionally, it is shown that reducing the maximum allowed latency increases the minimum required amount of data parallelism by up to a factor of 16.
    Original languageUndefined
    Title of host publicationProceedings of the 19th International Workshop on Software and Compilers for Embedded Systems
    Place of PublicationNew York
    PublisherAssociation for Computing Machinery (ACM)
    Pages30-39
    Number of pages10
    ISBN (Print)978-1-4503-4320-6
    DOIs
    Publication statusPublished - 12 Jun 2016
    Event19th ACM International Workshop on Software and Compilers for Embedded Systems, SCOPES 2016 - Sankt Goar, Germany
    Duration: 23 May 201625 May 2016
    Conference number: 19
    http://www.scopesconf.org/scopes-16/

    Publication series

    Name
    PublisherACM

    Workshop

    Workshop19th ACM International Workshop on Software and Compilers for Embedded Systems, SCOPES 2016
    Abbreviated titleSCOPES
    CountryGermany
    CitySankt Goar
    Period23/05/1625/05/16
    Internet address

    Keywords

    • Timed-dataflow analysis model
    • IR-100673
    • METIS-317223
    • EWI-27074

    Cite this

    Koek, P., Geuns, S. J., Hausmans, J. P. H. M., Corporaal, H., & Bekooij, M. J. G. (2016). CSDFa: a model for exploiting the trade-off between data and pipeline parallelism. In Proceedings of the 19th International Workshop on Software and Compilers for Embedded Systems (pp. 30-39). New York: Association for Computing Machinery (ACM). https://doi.org/10.1145/2906363.2906364