License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECRTS.2023.1
URN: urn:nbn:de:0030-drops-180301
Go to the corresponding LIPIcs Volume Portal

Bourke, Timothy ; Bregeon, Vincent ; Pouzet, Marc

Scheduling and Compiling Rate-Synchronous Programs with End-To-End Latency Constraints

LIPIcs-ECRTS-2023-1.pdf (0.9 MB)


We present an extension of the synchronous-reactive model for specifying multi-rate systems. A set of periodically executed components and their communication dependencies are expressed in a Lustre-like programming language with features for load balancing, resource limiting, and specifying end-to-end latencies. The language abstracts from execution time and phase offsets. This permits simple clock typing rules and a stream-based semantics, but requires each component to execute within an overall base period. A program is compiled to a single periodic task in two stages. First, Integer Linear Programming is used to determine phase offsets using standard encodings for dependencies and load balancing, and a novel encoding for end-to-end latency. Second, a code generation scheme is adapted to produce step functions. As a result, components are synchronous relative to their respective rates, but not necessarily simultaneous relative to the base period. This approach has been implemented in a prototype compiler and validated on an industrial application.

BibTeX - Entry

  author =	{Bourke, Timothy and Bregeon, Vincent and Pouzet, Marc},
  title =	{{Scheduling and Compiling Rate-Synchronous Programs with End-To-End Latency Constraints}},
  booktitle =	{35th Euromicro Conference on Real-Time Systems (ECRTS 2023)},
  pages =	{1:1--1:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-280-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{262},
  editor =	{Papadopoulos, Alessandro V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-180301},
  doi =		{10.4230/LIPIcs.ECRTS.2023.1},
  annote =	{Keywords: synchronous-reactive, integer linear programming, code generation}

Keywords: synchronous-reactive, integer linear programming, code generation
Collection: 35th Euromicro Conference on Real-Time Systems (ECRTS 2023)
Issue Date: 2023
Date of publication: 03.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI