Unified dataflow model for the analysis of data and pipeline parallelism, and buffer sizing

J.P.H.M. Hausmans, S.J. Geuns, M.H. Wiggers, Marco Jan Gerrit Bekooij

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

    3 Citations (Scopus)
    34 Downloads (Pure)

    Abstract

    Real-time stream processing applications such as software defined radios are usually executed concurrently on multiprocessor systems. Exploiting coarse-grained data parallelism by duplicating tasks is often required, besides pipeline parallelism, to meet the temporal constraints of the applications. However, no unified model and analysis method exists that can be used to determine the required amount of data and pipeline parallelism, and buffer sizes simultaneously. This paper presents an analysis method which can determine the required amount of data parallelism by describing data parallelism in a dataflow model without replicating dataflow actors. This allows to make a trade-off between the amount of data and pipeline parallelism that is required to meet the temporal constraints of the application. It is also shown how large the buffers need to be such that the determined amount of data and pipeline parallelism required for the satisfaction of the throughput constraint, can be realized. Furthermore, it is shown that the use of the applied circular buffers enables the proposed dataflow modeling. The presented analysis method is demonstrated using a WLAN 802.11p transceiver application. This application contains multi-rate behavior and has a cyclic data dependency because of a re-encoding loop. Given the real-time constraints of the application, sufficient buffer sizes and sufficient data parallelism are derived.
    Original languageUndefined
    Title of host publicationTwelfth ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2014
    Place of PublicationWashington, DC, USA
    PublisherIEEE Computer Society
    Pages12-21
    Number of pages10
    ISBN (Print)978-1-4799-5338-7
    DOIs
    Publication statusPublished - 19 Oct 2014

    Publication series

    Name
    PublisherIEEE Computer Society

    Keywords

    • EWI-25364
    • IR-92880
    • METIS-309689

    Cite this

    Hausmans, J. P. H. M., Geuns, S. J., Wiggers, M. H., & Bekooij, M. J. G. (2014). Unified dataflow model for the analysis of data and pipeline parallelism, and buffer sizing. In Twelfth ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2014 (pp. 12-21). Washington, DC, USA: IEEE Computer Society. https://doi.org/10.1109/MEMCOD.2014.6961839
    Hausmans, J.P.H.M. ; Geuns, S.J. ; Wiggers, M.H. ; Bekooij, Marco Jan Gerrit. / Unified dataflow model for the analysis of data and pipeline parallelism, and buffer sizing. Twelfth ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2014. Washington, DC, USA : IEEE Computer Society, 2014. pp. 12-21
    @inproceedings{27bc1d26699541aab13989dade144b2b,
    title = "Unified dataflow model for the analysis of data and pipeline parallelism, and buffer sizing",
    abstract = "Real-time stream processing applications such as software defined radios are usually executed concurrently on multiprocessor systems. Exploiting coarse-grained data parallelism by duplicating tasks is often required, besides pipeline parallelism, to meet the temporal constraints of the applications. However, no unified model and analysis method exists that can be used to determine the required amount of data and pipeline parallelism, and buffer sizes simultaneously. This paper presents an analysis method which can determine the required amount of data parallelism by describing data parallelism in a dataflow model without replicating dataflow actors. This allows to make a trade-off between the amount of data and pipeline parallelism that is required to meet the temporal constraints of the application. It is also shown how large the buffers need to be such that the determined amount of data and pipeline parallelism required for the satisfaction of the throughput constraint, can be realized. Furthermore, it is shown that the use of the applied circular buffers enables the proposed dataflow modeling. The presented analysis method is demonstrated using a WLAN 802.11p transceiver application. This application contains multi-rate behavior and has a cyclic data dependency because of a re-encoding loop. Given the real-time constraints of the application, sufficient buffer sizes and sufficient data parallelism are derived.",
    keywords = "EWI-25364, IR-92880, METIS-309689",
    author = "J.P.H.M. Hausmans and S.J. Geuns and M.H. Wiggers and Bekooij, {Marco Jan Gerrit}",
    note = "10.1109/MEMCOD.2014.6961839",
    year = "2014",
    month = "10",
    day = "19",
    doi = "10.1109/MEMCOD.2014.6961839",
    language = "Undefined",
    isbn = "978-1-4799-5338-7",
    publisher = "IEEE Computer Society",
    pages = "12--21",
    booktitle = "Twelfth ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2014",
    address = "United States",

    }

    Hausmans, JPHM, Geuns, SJ, Wiggers, MH & Bekooij, MJG 2014, Unified dataflow model for the analysis of data and pipeline parallelism, and buffer sizing. in Twelfth ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2014. IEEE Computer Society, Washington, DC, USA, pp. 12-21. https://doi.org/10.1109/MEMCOD.2014.6961839

    Unified dataflow model for the analysis of data and pipeline parallelism, and buffer sizing. / Hausmans, J.P.H.M.; Geuns, S.J.; Wiggers, M.H.; Bekooij, Marco Jan Gerrit.

    Twelfth ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2014. Washington, DC, USA : IEEE Computer Society, 2014. p. 12-21.

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

    TY - GEN

    T1 - Unified dataflow model for the analysis of data and pipeline parallelism, and buffer sizing

    AU - Hausmans, J.P.H.M.

    AU - Geuns, S.J.

    AU - Wiggers, M.H.

    AU - Bekooij, Marco Jan Gerrit

    N1 - 10.1109/MEMCOD.2014.6961839

    PY - 2014/10/19

    Y1 - 2014/10/19

    N2 - Real-time stream processing applications such as software defined radios are usually executed concurrently on multiprocessor systems. Exploiting coarse-grained data parallelism by duplicating tasks is often required, besides pipeline parallelism, to meet the temporal constraints of the applications. However, no unified model and analysis method exists that can be used to determine the required amount of data and pipeline parallelism, and buffer sizes simultaneously. This paper presents an analysis method which can determine the required amount of data parallelism by describing data parallelism in a dataflow model without replicating dataflow actors. This allows to make a trade-off between the amount of data and pipeline parallelism that is required to meet the temporal constraints of the application. It is also shown how large the buffers need to be such that the determined amount of data and pipeline parallelism required for the satisfaction of the throughput constraint, can be realized. Furthermore, it is shown that the use of the applied circular buffers enables the proposed dataflow modeling. The presented analysis method is demonstrated using a WLAN 802.11p transceiver application. This application contains multi-rate behavior and has a cyclic data dependency because of a re-encoding loop. Given the real-time constraints of the application, sufficient buffer sizes and sufficient data parallelism are derived.

    AB - Real-time stream processing applications such as software defined radios are usually executed concurrently on multiprocessor systems. Exploiting coarse-grained data parallelism by duplicating tasks is often required, besides pipeline parallelism, to meet the temporal constraints of the applications. However, no unified model and analysis method exists that can be used to determine the required amount of data and pipeline parallelism, and buffer sizes simultaneously. This paper presents an analysis method which can determine the required amount of data parallelism by describing data parallelism in a dataflow model without replicating dataflow actors. This allows to make a trade-off between the amount of data and pipeline parallelism that is required to meet the temporal constraints of the application. It is also shown how large the buffers need to be such that the determined amount of data and pipeline parallelism required for the satisfaction of the throughput constraint, can be realized. Furthermore, it is shown that the use of the applied circular buffers enables the proposed dataflow modeling. The presented analysis method is demonstrated using a WLAN 802.11p transceiver application. This application contains multi-rate behavior and has a cyclic data dependency because of a re-encoding loop. Given the real-time constraints of the application, sufficient buffer sizes and sufficient data parallelism are derived.

    KW - EWI-25364

    KW - IR-92880

    KW - METIS-309689

    U2 - 10.1109/MEMCOD.2014.6961839

    DO - 10.1109/MEMCOD.2014.6961839

    M3 - Conference contribution

    SN - 978-1-4799-5338-7

    SP - 12

    EP - 21

    BT - Twelfth ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2014

    PB - IEEE Computer Society

    CY - Washington, DC, USA

    ER -

    Hausmans JPHM, Geuns SJ, Wiggers MH, Bekooij MJG. Unified dataflow model for the analysis of data and pipeline parallelism, and buffer sizing. In Twelfth ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE 2014. Washington, DC, USA: IEEE Computer Society. 2014. p. 12-21 https://doi.org/10.1109/MEMCOD.2014.6961839