Mapping of Modal Applications given Throughput and Latency Constraints

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

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

2 Citations (Scopus)

Abstract

Real-time applications such as software de﬿ned radios have different reception modes and their real-time requirements are a result of periodic sources and sinks in the form of ADCs and DACs. Tools are under development that automatically translate a sequential speci﬿cation of a radio application, that often includes nested while loops to describe the modes, into a parallel task graph and map this task graph onto an embedded multiprocessor system. However the speci﬿cation of strict periodic sources and sinks together with input and output buffers that can respectively overflow or underrun is currently not possible in a sequential programming language. In this paper we will introduce a nested loop program (NLP) language extension that enables the speci﬿cation of periodic sources and sinks and their buffers in a sequential program. We show that parallelization of such a sequential program poses challenges because the order in which different tasks access the input and output buffers should be maintained in the parallel program. Furthermore, the buffers at the sources and sinks allow destructive writes and non-destructive reads, which causes non-deterministic functional behavior in case the throughput and latency constraint of the application are not met. The other buffers in the task graph block in case no data or space is available. Therefore, the system internals remain functionally deterministic which signi﬿cantly simpli﬿es debugging and analysis. Furthermore, to guarantee real-time requirements, we show that it is possible to conservatively model an application with nested while loops as a Cyclo-Static Dataflow (CSDF) model. Using this model we can compute a mapping of the task graph, which includes a task to processor assignment, suitable scheduler settings and buffer capacities. By making use of this CSDF model, we can guarantee that sources and sinks can run periodically under the assumption that the used execution times of the tasks are upper bounds.
Original languageUndefined
Title of host publicationInternational Conference on Embedded Computer Systems, SAMOS 2011
Place of PublicationUSA
PublisherIEEE Computer Society
Pages372-379
Number of pages8
ISBN (Print)978-1-4577-0800-8
DOIs
Publication statusPublished - 20 Jul 2011
Event2011 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, IC-SAMOS XI - Institute of East Aegean, Samos, Greece
Duration: 18 Jul 201121 Jul 2011
Conference number: 11

Publication series

Name
PublisherIEEE Computer Society

Conference

Conference2011 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, IC-SAMOS XI
Abbreviated titleIC-SAMOS
CountryGreece
CitySamos
Period18/07/1121/07/11

Keywords

  • METIS-278762
  • EWI-20438
  • IR-78155

Cite this

Geuns, S. J., Hausmans, J. P. H. M., & Bekooij, M. J. G. (2011). Mapping of Modal Applications given Throughput and Latency Constraints. In International Conference on Embedded Computer Systems, SAMOS 2011 (pp. 372-379). USA: IEEE Computer Society. https://doi.org/10.1109/SAMOS.2011.6045487
Geuns, S.J. ; Hausmans, J.P.H.M. ; Bekooij, Marco Jan Gerrit. / Mapping of Modal Applications given Throughput and Latency Constraints. International Conference on Embedded Computer Systems, SAMOS 2011. USA : IEEE Computer Society, 2011. pp. 372-379
@inproceedings{fbee63ba9ed04c3aab91271195f149e2,
title = "Mapping of Modal Applications given Throughput and Latency Constraints",
abstract = "Real-time applications such as software de﬿ned radios have different reception modes and their real-time requirements are a result of periodic sources and sinks in the form of ADCs and DACs. Tools are under development that automatically translate a sequential speci﬿cation of a radio application, that often includes nested while loops to describe the modes, into a parallel task graph and map this task graph onto an embedded multiprocessor system. However the speci﬿cation of strict periodic sources and sinks together with input and output buffers that can respectively overflow or underrun is currently not possible in a sequential programming language. In this paper we will introduce a nested loop program (NLP) language extension that enables the speci﬿cation of periodic sources and sinks and their buffers in a sequential program. We show that parallelization of such a sequential program poses challenges because the order in which different tasks access the input and output buffers should be maintained in the parallel program. Furthermore, the buffers at the sources and sinks allow destructive writes and non-destructive reads, which causes non-deterministic functional behavior in case the throughput and latency constraint of the application are not met. The other buffers in the task graph block in case no data or space is available. Therefore, the system internals remain functionally deterministic which signi﬿cantly simpli﬿es debugging and analysis. Furthermore, to guarantee real-time requirements, we show that it is possible to conservatively model an application with nested while loops as a Cyclo-Static Dataflow (CSDF) model. Using this model we can compute a mapping of the task graph, which includes a task to processor assignment, suitable scheduler settings and buffer capacities. By making use of this CSDF model, we can guarantee that sources and sinks can run periodically under the assumption that the used execution times of the tasks are upper bounds.",
keywords = "METIS-278762, EWI-20438, IR-78155",
author = "S.J. Geuns and J.P.H.M. Hausmans and Bekooij, {Marco Jan Gerrit}",
year = "2011",
month = "7",
day = "20",
doi = "10.1109/SAMOS.2011.6045487",
language = "Undefined",
isbn = "978-1-4577-0800-8",
publisher = "IEEE Computer Society",
pages = "372--379",
booktitle = "International Conference on Embedded Computer Systems, SAMOS 2011",
address = "United States",

}

Geuns, SJ, Hausmans, JPHM & Bekooij, MJG 2011, Mapping of Modal Applications given Throughput and Latency Constraints. in International Conference on Embedded Computer Systems, SAMOS 2011. IEEE Computer Society, USA, pp. 372-379, 2011 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, IC-SAMOS XI, Samos, Greece, 18/07/11. https://doi.org/10.1109/SAMOS.2011.6045487

Mapping of Modal Applications given Throughput and Latency Constraints. / Geuns, S.J.; Hausmans, J.P.H.M.; Bekooij, Marco Jan Gerrit.

International Conference on Embedded Computer Systems, SAMOS 2011. USA : IEEE Computer Society, 2011. p. 372-379.

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

TY - GEN

T1 - Mapping of Modal Applications given Throughput and Latency Constraints

AU - Geuns, S.J.

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

AU - Bekooij, Marco Jan Gerrit

PY - 2011/7/20

Y1 - 2011/7/20

N2 - Real-time applications such as software de﬿ned radios have different reception modes and their real-time requirements are a result of periodic sources and sinks in the form of ADCs and DACs. Tools are under development that automatically translate a sequential speci﬿cation of a radio application, that often includes nested while loops to describe the modes, into a parallel task graph and map this task graph onto an embedded multiprocessor system. However the speci﬿cation of strict periodic sources and sinks together with input and output buffers that can respectively overflow or underrun is currently not possible in a sequential programming language. In this paper we will introduce a nested loop program (NLP) language extension that enables the speci﬿cation of periodic sources and sinks and their buffers in a sequential program. We show that parallelization of such a sequential program poses challenges because the order in which different tasks access the input and output buffers should be maintained in the parallel program. Furthermore, the buffers at the sources and sinks allow destructive writes and non-destructive reads, which causes non-deterministic functional behavior in case the throughput and latency constraint of the application are not met. The other buffers in the task graph block in case no data or space is available. Therefore, the system internals remain functionally deterministic which signi﬿cantly simpli﬿es debugging and analysis. Furthermore, to guarantee real-time requirements, we show that it is possible to conservatively model an application with nested while loops as a Cyclo-Static Dataflow (CSDF) model. Using this model we can compute a mapping of the task graph, which includes a task to processor assignment, suitable scheduler settings and buffer capacities. By making use of this CSDF model, we can guarantee that sources and sinks can run periodically under the assumption that the used execution times of the tasks are upper bounds.

AB - Real-time applications such as software de﬿ned radios have different reception modes and their real-time requirements are a result of periodic sources and sinks in the form of ADCs and DACs. Tools are under development that automatically translate a sequential speci﬿cation of a radio application, that often includes nested while loops to describe the modes, into a parallel task graph and map this task graph onto an embedded multiprocessor system. However the speci﬿cation of strict periodic sources and sinks together with input and output buffers that can respectively overflow or underrun is currently not possible in a sequential programming language. In this paper we will introduce a nested loop program (NLP) language extension that enables the speci﬿cation of periodic sources and sinks and their buffers in a sequential program. We show that parallelization of such a sequential program poses challenges because the order in which different tasks access the input and output buffers should be maintained in the parallel program. Furthermore, the buffers at the sources and sinks allow destructive writes and non-destructive reads, which causes non-deterministic functional behavior in case the throughput and latency constraint of the application are not met. The other buffers in the task graph block in case no data or space is available. Therefore, the system internals remain functionally deterministic which signi﬿cantly simpli﬿es debugging and analysis. Furthermore, to guarantee real-time requirements, we show that it is possible to conservatively model an application with nested while loops as a Cyclo-Static Dataflow (CSDF) model. Using this model we can compute a mapping of the task graph, which includes a task to processor assignment, suitable scheduler settings and buffer capacities. By making use of this CSDF model, we can guarantee that sources and sinks can run periodically under the assumption that the used execution times of the tasks are upper bounds.

KW - METIS-278762

KW - EWI-20438

KW - IR-78155

U2 - 10.1109/SAMOS.2011.6045487

DO - 10.1109/SAMOS.2011.6045487

M3 - Conference contribution

SN - 978-1-4577-0800-8

SP - 372

EP - 379

BT - International Conference on Embedded Computer Systems, SAMOS 2011

PB - IEEE Computer Society

CY - USA

ER -

Geuns SJ, Hausmans JPHM, Bekooij MJG. Mapping of Modal Applications given Throughput and Latency Constraints. In International Conference on Embedded Computer Systems, SAMOS 2011. USA: IEEE Computer Society. 2011. p. 372-379 https://doi.org/10.1109/SAMOS.2011.6045487