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
Koek, Peter ; Geuns, S.J. ; Hausmans, J.P.H.M. ; Corporaal, Henk ; Bekooij, Marco Jan Gerrit. / CSDFa: a model for exploiting the trade-off between data and pipeline parallelism. Proceedings of the 19th International Workshop on Software and Compilers for Embedded Systems. New York : Association for Computing Machinery (ACM), 2016. pp. 30-39
@inproceedings{19c4086b67bb4ff4aa2e632140a56e43,
title = "CSDFa: a model for exploiting the trade-off between data and pipeline parallelism",
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.",
keywords = "Timed-dataflow analysis model, IR-100673, METIS-317223, EWI-27074",
author = "Peter Koek and S.J. Geuns and J.P.H.M. Hausmans and Henk Corporaal and Bekooij, {Marco Jan Gerrit}",
note = "eemcs-eprint-27074",
year = "2016",
month = "6",
day = "12",
doi = "10.1145/2906363.2906364",
language = "Undefined",
isbn = "978-1-4503-4320-6",
publisher = "Association for Computing Machinery (ACM)",
pages = "30--39",
booktitle = "Proceedings of the 19th International Workshop on Software and Compilers for Embedded Systems",
address = "United States",

}

Koek, P, Geuns, SJ, Hausmans, JPHM, Corporaal, H & Bekooij, MJG 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. Association for Computing Machinery (ACM), New York, pp. 30-39, 19th ACM International Workshop on Software and Compilers for Embedded Systems, SCOPES 2016, Sankt Goar, Germany, 23/05/16. https://doi.org/10.1145/2906363.2906364

CSDFa: a model for exploiting the trade-off between data and pipeline parallelism. / Koek, Peter; Geuns, S.J.; Hausmans, J.P.H.M.; Corporaal, Henk; Bekooij, Marco Jan Gerrit.

Proceedings of the 19th International Workshop on Software and Compilers for Embedded Systems. New York : Association for Computing Machinery (ACM), 2016. p. 30-39.

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

TY - GEN

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

AU - Koek, Peter

AU - Geuns, S.J.

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

AU - Corporaal, Henk

AU - Bekooij, Marco Jan Gerrit

N1 - eemcs-eprint-27074

PY - 2016/6/12

Y1 - 2016/6/12

N2 - 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.

AB - 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.

KW - Timed-dataflow analysis model

KW - IR-100673

KW - METIS-317223

KW - EWI-27074

U2 - 10.1145/2906363.2906364

DO - 10.1145/2906363.2906364

M3 - Conference contribution

SN - 978-1-4503-4320-6

SP - 30

EP - 39

BT - Proceedings of the 19th International Workshop on Software and Compilers for Embedded Systems

PB - Association for Computing Machinery (ACM)

CY - New York

ER -

Koek P, Geuns SJ, Hausmans JPHM, Corporaal H, Bekooij MJG. 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. New York: Association for Computing Machinery (ACM). 2016. p. 30-39 https://doi.org/10.1145/2906363.2906364