Temporal analysis model extraction for optimizing modal multi-rate stream processing applications

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

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

5 Citations (Scopus)
16 Downloads (Pure)

Abstract

Modern real-time stream processing applications, such as Software Defined Radio (SDR) applications, typically have multiple modes and multi-rate behavior. Modes are often described using while-loops whereas multi-rate behavior is frequently described using arrays with pseudo-random indexing patterns. The temporal properties of these applications have to be analyzed in order to determine whether optimizations improve throughput. However, no method exists in which a temporal analysis model is derived from these applications that is suitable for temporal analysis and optimization. In this paper an approach is presented in which a concurrency model for the temporal analysis and optimization of stream processing applications is automatically extracted from a parallelized sequential application. With this model it can be determined whether a program transformation improves the worst-case temporal behavior. The key feature of the presented approach is that arrays with arbitrary indexing patterns can be described, allowing the description of multi-rate behavior, while still supporting the description of modes using while-loops. In the model, an over-approximation of the synchronization dependencies is used in case of arrays with pseudo-random indexing patterns. Despite the use of this approximation, we show that deadlock is only concluded from the model if there is also deadlock in the parallelized application. The relevance and applicability of the presented approach are demonstrated using an Orthogonal Frequency-Division Multiplexing (OFDM) transmitter application.
Original languageEnglish
Title of host publicationProceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2014)
Place of PublicationNew York
PublisherAssociation for Computing Machinery (ACM)
Pages21-39
Number of pages10
ISBN (Print)978-1-4503-2941-5
DOIs
Publication statusPublished - 10 Jun 2014
Event17th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2014 - St. Goar, Germany
Duration: 10 Jun 201411 Jun 2014
Conference number: 17
http://www.scopesconf.org/scopes-14/

Conference

Conference17th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2014
Abbreviated titleSCOPES
CountryGermany
CitySt. Goar
Period10/06/1411/06/14
Internet address

Fingerprint

Processing
Orthogonal frequency division multiplexing
Transmitters
Synchronization
Throughput

Keywords

  • EWI-24712
  • IR-91373
  • METIS-305873

Cite this

Geuns, S. J., Hausmans, J. P. H. M., & Bekooij, M. J. G. (2014). Temporal analysis model extraction for optimizing modal multi-rate stream processing applications. In Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2014) (pp. 21-39). New York: Association for Computing Machinery (ACM). https://doi.org/10.1145/2609248.2609252
Geuns, S.J. ; Hausmans, J.P.H.M. ; Bekooij, Marco Jan Gerrit. / Temporal analysis model extraction for optimizing modal multi-rate stream processing applications. Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2014). New York : Association for Computing Machinery (ACM), 2014. pp. 21-39
@inproceedings{fe7cfd50297b4ce4811673b1a8ed9e6f,
title = "Temporal analysis model extraction for optimizing modal multi-rate stream processing applications",
abstract = "Modern real-time stream processing applications, such as Software Defined Radio (SDR) applications, typically have multiple modes and multi-rate behavior. Modes are often described using while-loops whereas multi-rate behavior is frequently described using arrays with pseudo-random indexing patterns. The temporal properties of these applications have to be analyzed in order to determine whether optimizations improve throughput. However, no method exists in which a temporal analysis model is derived from these applications that is suitable for temporal analysis and optimization. In this paper an approach is presented in which a concurrency model for the temporal analysis and optimization of stream processing applications is automatically extracted from a parallelized sequential application. With this model it can be determined whether a program transformation improves the worst-case temporal behavior. The key feature of the presented approach is that arrays with arbitrary indexing patterns can be described, allowing the description of multi-rate behavior, while still supporting the description of modes using while-loops. In the model, an over-approximation of the synchronization dependencies is used in case of arrays with pseudo-random indexing patterns. Despite the use of this approximation, we show that deadlock is only concluded from the model if there is also deadlock in the parallelized application. The relevance and applicability of the presented approach are demonstrated using an Orthogonal Frequency-Division Multiplexing (OFDM) transmitter application.",
keywords = "EWI-24712, IR-91373, METIS-305873",
author = "S.J. Geuns and J.P.H.M. Hausmans and Bekooij, {Marco Jan Gerrit}",
year = "2014",
month = "6",
day = "10",
doi = "10.1145/2609248.2609252",
language = "English",
isbn = "978-1-4503-2941-5",
pages = "21--39",
booktitle = "Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2014)",
publisher = "Association for Computing Machinery (ACM)",
address = "United States",

}

Geuns, SJ, Hausmans, JPHM & Bekooij, MJG 2014, Temporal analysis model extraction for optimizing modal multi-rate stream processing applications. in Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2014). Association for Computing Machinery (ACM), New York, pp. 21-39, 17th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2014, St. Goar, Germany, 10/06/14. https://doi.org/10.1145/2609248.2609252

Temporal analysis model extraction for optimizing modal multi-rate stream processing applications. / Geuns, S.J.; Hausmans, J.P.H.M.; Bekooij, Marco Jan Gerrit.

Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2014). New York : Association for Computing Machinery (ACM), 2014. p. 21-39.

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

TY - GEN

T1 - Temporal analysis model extraction for optimizing modal multi-rate stream processing applications

AU - Geuns, S.J.

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

AU - Bekooij, Marco Jan Gerrit

PY - 2014/6/10

Y1 - 2014/6/10

N2 - Modern real-time stream processing applications, such as Software Defined Radio (SDR) applications, typically have multiple modes and multi-rate behavior. Modes are often described using while-loops whereas multi-rate behavior is frequently described using arrays with pseudo-random indexing patterns. The temporal properties of these applications have to be analyzed in order to determine whether optimizations improve throughput. However, no method exists in which a temporal analysis model is derived from these applications that is suitable for temporal analysis and optimization. In this paper an approach is presented in which a concurrency model for the temporal analysis and optimization of stream processing applications is automatically extracted from a parallelized sequential application. With this model it can be determined whether a program transformation improves the worst-case temporal behavior. The key feature of the presented approach is that arrays with arbitrary indexing patterns can be described, allowing the description of multi-rate behavior, while still supporting the description of modes using while-loops. In the model, an over-approximation of the synchronization dependencies is used in case of arrays with pseudo-random indexing patterns. Despite the use of this approximation, we show that deadlock is only concluded from the model if there is also deadlock in the parallelized application. The relevance and applicability of the presented approach are demonstrated using an Orthogonal Frequency-Division Multiplexing (OFDM) transmitter application.

AB - Modern real-time stream processing applications, such as Software Defined Radio (SDR) applications, typically have multiple modes and multi-rate behavior. Modes are often described using while-loops whereas multi-rate behavior is frequently described using arrays with pseudo-random indexing patterns. The temporal properties of these applications have to be analyzed in order to determine whether optimizations improve throughput. However, no method exists in which a temporal analysis model is derived from these applications that is suitable for temporal analysis and optimization. In this paper an approach is presented in which a concurrency model for the temporal analysis and optimization of stream processing applications is automatically extracted from a parallelized sequential application. With this model it can be determined whether a program transformation improves the worst-case temporal behavior. The key feature of the presented approach is that arrays with arbitrary indexing patterns can be described, allowing the description of multi-rate behavior, while still supporting the description of modes using while-loops. In the model, an over-approximation of the synchronization dependencies is used in case of arrays with pseudo-random indexing patterns. Despite the use of this approximation, we show that deadlock is only concluded from the model if there is also deadlock in the parallelized application. The relevance and applicability of the presented approach are demonstrated using an Orthogonal Frequency-Division Multiplexing (OFDM) transmitter application.

KW - EWI-24712

KW - IR-91373

KW - METIS-305873

U2 - 10.1145/2609248.2609252

DO - 10.1145/2609248.2609252

M3 - Conference contribution

SN - 978-1-4503-2941-5

SP - 21

EP - 39

BT - Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2014)

PB - Association for Computing Machinery (ACM)

CY - New York

ER -

Geuns SJ, Hausmans JPHM, Bekooij MJG. Temporal analysis model extraction for optimizing modal multi-rate stream processing applications. In Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2014). New York: Association for Computing Machinery (ACM). 2014. p. 21-39 https://doi.org/10.1145/2609248.2609252