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)
31 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