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

P. Koek, S.J. Geuns, J.P.H.M. Hausmans, H. Corporaal, M.J.G. Bekooij

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

1 Citation (Scopus)

Abstract

Real-time stream processing applications, such as Software Defined Radio 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 coarsegrained data parallelism required to meet the temporal constraints of such applications. However, this unified model is only defined for Synchronous Data Flow (SDF) graphs. Defining a unified model for a more expressive model such as Cyclo-Static Data Flow (CSDF) is not possible, because auto-concurrency can cause a time-dependent order of tokens and dependencies. This paper introduces the Cyclo-Static Data Flow with Auto-concurrency (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 languageEnglish
Title of host publicationProceedings of the 19th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2016
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Pages30-39
Number of pages10
ISBN (Electronic)978-1-4503-4320-6
DOIs
Publication statusPublished - 23 May 2016
Event19th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2016) - St. Goar, Germany
Duration: 23 May 201625 May 2016
Conference number: 19

Conference

Conference19th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2016)
Abbreviated titleSCOPES 2016
CountryGermany
CitySt. Goar
Period23/05/1625/05/16

Fingerprint

Dive into the research topics of 'CSDFa: a model for exploiting the trade-off between data and pipeline parallelism'. Together they form a unique fingerprint.

Cite this