---
_id: '66150'
abstract:
- lang: eng
text: |-
Releasing jobs and performing scheduling decisions in real-time operating systems (RTOSes) is often realized within tick interrupts. In each tick interrupt, a set of tasks that are waiting to release new jobs, namely, the waiting set, is inspected to determine the jobs that should be released at this tick. Such a waiting set is sorted whenever a job has finished, by which the release process can be efficiently achieved. However, the overhead of sorting can vary vastly depending on the task set, which has to be taken into account in the worst-case timing analysis. Moreover, the tick interrupt in common practices is backed by a single hardware timer that is configured to trigger interrupts, either with a fixed period or reconfigured to the next release time (so-called one-shot timer). Since not necessarily at every interrupt a job will be released, several tick interrupts might be redundant. For the one-shot timers, the reconfiguration during runtime also incurs overheads at a variable interval. To reduce such variability and amount of overhead, in this work, we propose
LazyTick
which partitions the task set and distributes the subsets over multiple timers. Specifically, we propose two job release procedures with constant operations overhead—one for harmonic task sets and one for non-harmonic task sets. We implemented the support for multiple hardware timers in FreeRTOS and conducted intensive experimental evaluations. The evaluation shows that
LazyTick
can reduce the variability in overhead by up to ≈ 5 × in peak and ≈ 3× on average in comparison to the default implementation. Additionally, the combined overhead of the job release process is reduced by up to ≈ 6.1 × in peak and ≈ 3.6× on average.
author:
- first_name: Kay
full_name: Heider, Kay
last_name: Heider
- first_name: Christian
full_name: Hakert, Christian
last_name: Hakert
- first_name: Kuan-Hsun
full_name: Chen, Kuan-Hsun
last_name: Chen
- first_name: Jian-Jia
full_name: Chen, Jian-Jia
last_name: Chen
citation:
ama: 'Heider K, Hakert C, Chen K-H, Chen J-J. LazyTick: Lazy and Efficient Management
of Job Release in Real-Time Operating Systems. ACM Transactions on Embedded
Computing Systems. 2025;24(5s):1-25. doi:10.1145/3762651'
apa: 'Heider, K., Hakert, C., Chen, K.-H., & Chen, J.-J. (2025). LazyTick: Lazy
and Efficient Management of Job Release in Real-Time Operating Systems. ACM
Transactions on Embedded Computing Systems, 24(5s), 1–25. https://doi.org/10.1145/3762651'
bibtex: '@article{Heider_Hakert_Chen_Chen_2025, title={LazyTick: Lazy and Efficient
Management of Job Release in Real-Time Operating Systems}, volume={24}, DOI={10.1145/3762651}, number={5s}, journal={ACM
Transactions on Embedded Computing Systems}, publisher={Association for Computing
Machinery (ACM)}, author={Heider, Kay and Hakert, Christian and Chen, Kuan-Hsun
and Chen, Jian-Jia}, year={2025}, pages={1–25} }'
chicago: 'Heider, Kay, Christian Hakert, Kuan-Hsun Chen, and Jian-Jia Chen. “LazyTick:
Lazy and Efficient Management of Job Release in Real-Time Operating Systems.”
ACM Transactions on Embedded Computing Systems 24, no. 5s (2025): 1–25.
https://doi.org/10.1145/3762651.'
ieee: 'K. Heider, C. Hakert, K.-H. Chen, and J.-J. Chen, “LazyTick: Lazy and Efficient
Management of Job Release in Real-Time Operating Systems,” ACM Transactions
on Embedded Computing Systems, vol. 24, no. 5s, pp. 1–25, 2025, doi: 10.1145/3762651.'
mla: 'Heider, Kay, et al. “LazyTick: Lazy and Efficient Management of Job Release
in Real-Time Operating Systems.” ACM Transactions on Embedded Computing Systems,
vol. 24, no. 5s, Association for Computing Machinery (ACM), 2025, pp. 1–25, doi:10.1145/3762651.'
short: K. Heider, C. Hakert, K.-H. Chen, J.-J. Chen, ACM Transactions on Embedded
Computing Systems 24 (2025) 1–25.
date_created: 2026-07-03T21:07:51Z
date_updated: 2026-07-05T14:48:51Z
doi: 10.1145/3762651
intvolume: ' 24'
issue: 5s
language:
- iso: eng
page: 1-25
publication: ACM Transactions on Embedded Computing Systems
publication_identifier:
issn:
- 1539-9087
- 1558-3465
publication_status: published
publisher: Association for Computing Machinery (ACM)
status: public
title: 'LazyTick: Lazy and Efficient Management of Job Release in Real-Time Operating
Systems'
type: journal_article
user_id: '128464'
volume: 24
year: '2025'
...
---
_id: '66166'
author:
- first_name: Liang
full_name: Shi, Liang
last_name: Shi
- first_name: Jingtong
full_name: Shi, Jingtong
last_name: Shi
- first_name: Hussam
full_name: Amrouch, Hussam
last_name: Amrouch
- first_name: Kuan-Hsun
full_name: Chen, Kuan-Hsun
last_name: Chen
- first_name: Mengying
full_name: Zhao, Mengying
last_name: Zhao
- first_name: Weichen
full_name: Liu, Weichen
last_name: Liu
citation:
ama: Shi L, Shi J, Amrouch H, Chen K-H, Zhao M, Liu W. Introduction to Special Issue
on In/Near Memory and Storage Computing for Embedded Systems. ACM Transactions
on Embedded Computing Systems. 2024;23(6):1-3. doi:10.1145/3677018
apa: Shi, L., Shi, J., Amrouch, H., Chen, K.-H., Zhao, M., & Liu, W. (2024).
Introduction to Special Issue on In/Near Memory and Storage Computing for Embedded
Systems. ACM Transactions on Embedded Computing Systems, 23(6),
1–3. https://doi.org/10.1145/3677018
bibtex: '@article{Shi_Shi_Amrouch_Chen_Zhao_Liu_2024, title={Introduction to Special
Issue on In/Near Memory and Storage Computing for Embedded Systems}, volume={23},
DOI={10.1145/3677018}, number={6},
journal={ACM Transactions on Embedded Computing Systems}, publisher={Association
for Computing Machinery (ACM)}, author={Shi, Liang and Shi, Jingtong and Amrouch,
Hussam and Chen, Kuan-Hsun and Zhao, Mengying and Liu, Weichen}, year={2024},
pages={1–3} }'
chicago: 'Shi, Liang, Jingtong Shi, Hussam Amrouch, Kuan-Hsun Chen, Mengying Zhao,
and Weichen Liu. “Introduction to Special Issue on In/Near Memory and Storage
Computing for Embedded Systems.” ACM Transactions on Embedded Computing Systems
23, no. 6 (2024): 1–3. https://doi.org/10.1145/3677018.'
ieee: 'L. Shi, J. Shi, H. Amrouch, K.-H. Chen, M. Zhao, and W. Liu, “Introduction
to Special Issue on In/Near Memory and Storage Computing for Embedded Systems,”
ACM Transactions on Embedded Computing Systems, vol. 23, no. 6, pp. 1–3,
2024, doi: 10.1145/3677018.'
mla: Shi, Liang, et al. “Introduction to Special Issue on In/Near Memory and Storage
Computing for Embedded Systems.” ACM Transactions on Embedded Computing Systems,
vol. 23, no. 6, Association for Computing Machinery (ACM), 2024, pp. 1–3, doi:10.1145/3677018.
short: L. Shi, J. Shi, H. Amrouch, K.-H. Chen, M. Zhao, W. Liu, ACM Transactions
on Embedded Computing Systems 23 (2024) 1–3.
date_created: 2026-07-03T21:11:12Z
date_updated: 2026-07-05T14:47:57Z
doi: 10.1145/3677018
intvolume: ' 23'
issue: '6'
language:
- iso: eng
page: 1-3
publication: ACM Transactions on Embedded Computing Systems
publication_identifier:
issn:
- 1539-9087
- 1558-3465
publication_status: published
publisher: Association for Computing Machinery (ACM)
status: public
title: Introduction to Special Issue on In/Near Memory and Storage Computing for Embedded
Systems
type: journal_article
user_id: '128464'
volume: 23
year: '2024'
...
---
_id: '66182'
abstract:
- lang: eng
text: Real-time systems require the formal guarantee of timing constraints,
not only for the individual tasks but also for the end-to-end latency of data
flows. The data flow among multiple tasks, e.g., from sensors to actuators, is
described by a cause-effect chain, independent from the priority order of the
tasks. In this article, we provide an end-to-end timing-analysis for cause-effect
chains on asynchronized distributed systems with periodic task activations, considering
the maximum reaction time (MRT) (i.e., the duration of data processing) and the
maximum data age (MDA) (i.e., the worst-case data freshness). We first provide
an analysis of the end-to-end latency on one local electronic control unit (ECU)
that has to consider only the jobs in a bounded time interval. We extend our analysis
to globally asynchronized systems by exploiting a compositional property to combine
the local results. Throughout synthesized data based on an automotive benchmark
as well as on randomized parameters, we show that our analytical results improve
the state-of-the-art.
author:
- first_name: Mario
full_name: Günzel, Mario
last_name: Günzel
- first_name: Kuan-Hsun
full_name: Chen, Kuan-Hsun
last_name: Chen
- first_name: Niklas
full_name: Ueter, Niklas
last_name: Ueter
- first_name: Georg von der
full_name: Brüggen, Georg von der
last_name: Brüggen
- first_name: Marco
full_name: Dürr, Marco
last_name: Dürr
- first_name: Jian-Jia
full_name: Chen, Jian-Jia
last_name: Chen
citation:
ama: Günzel M, Chen K-H, Ueter N, Brüggen G von der, Dürr M, Chen J-J. Compositional
Timing Analysis of Asynchronized Distributed Cause-effect Chains. ACM Transactions
on Embedded Computing Systems. 2023;22(4):1-34. doi:10.1145/3587036
apa: Günzel, M., Chen, K.-H., Ueter, N., Brüggen, G. von der, Dürr, M., & Chen,
J.-J. (2023). Compositional Timing Analysis of Asynchronized Distributed Cause-effect
Chains. ACM Transactions on Embedded Computing Systems, 22(4), 1–34.
https://doi.org/10.1145/3587036
bibtex: '@article{Günzel_Chen_Ueter_Brüggen_Dürr_Chen_2023, title={Compositional
Timing Analysis of Asynchronized Distributed Cause-effect Chains}, volume={22},
DOI={10.1145/3587036}, number={4},
journal={ACM Transactions on Embedded Computing Systems}, publisher={Association
for Computing Machinery (ACM)}, author={Günzel, Mario and Chen, Kuan-Hsun and
Ueter, Niklas and Brüggen, Georg von der and Dürr, Marco and Chen, Jian-Jia},
year={2023}, pages={1–34} }'
chicago: 'Günzel, Mario, Kuan-Hsun Chen, Niklas Ueter, Georg von der Brüggen, Marco
Dürr, and Jian-Jia Chen. “Compositional Timing Analysis of Asynchronized Distributed
Cause-Effect Chains.” ACM Transactions on Embedded Computing Systems 22,
no. 4 (2023): 1–34. https://doi.org/10.1145/3587036.'
ieee: 'M. Günzel, K.-H. Chen, N. Ueter, G. von der Brüggen, M. Dürr, and J.-J. Chen,
“Compositional Timing Analysis of Asynchronized Distributed Cause-effect Chains,”
ACM Transactions on Embedded Computing Systems, vol. 22, no. 4, pp. 1–34,
2023, doi: 10.1145/3587036.'
mla: Günzel, Mario, et al. “Compositional Timing Analysis of Asynchronized Distributed
Cause-Effect Chains.” ACM Transactions on Embedded Computing Systems, vol.
22, no. 4, Association for Computing Machinery (ACM), 2023, pp. 1–34, doi:10.1145/3587036.
short: M. Günzel, K.-H. Chen, N. Ueter, G. von der Brüggen, M. Dürr, J.-J. Chen,
ACM Transactions on Embedded Computing Systems 22 (2023) 1–34.
date_created: 2026-07-03T21:14:05Z
date_updated: 2026-07-05T14:46:55Z
doi: 10.1145/3587036
intvolume: ' 22'
issue: '4'
language:
- iso: eng
page: 1-34
publication: ACM Transactions on Embedded Computing Systems
publication_identifier:
issn:
- 1539-9087
- 1558-3465
publication_status: published
publisher: Association for Computing Machinery (ACM)
status: public
title: Compositional Timing Analysis of Asynchronized Distributed Cause-effect Chains
type: journal_article
user_id: '128464'
volume: 22
year: '2023'
...
---
_id: '66183'
abstract:
- lang: eng
text: |-
In many embedded systems, for instance, in the automotive, avionic, or robotics domain, critical functionalities are implemented via chains of communicating recurrent tasks. To ensure safety and correctness of such systems, guarantees on the reaction time, that is, the delay between a cause (e.g., an external activity or reading of a sensor) and the corresponding effect, must be provided.
Current approaches focus on the maximum reaction time, considering the worst-case system behavior. However, in many scenarios, probabilistic guarantees on the reaction time are sufficient. That is, it is sufficient to provide a guarantee that the reaction does not exceed a certain threshold with (at least) a certain probability.
This work provides such probabilistic guarantees on the reaction time, considering two types of randomness: response time randomness and failure probabilities. To the best of our knowledge, this is the first work that defines and analyzes probabilistic reaction time for cause-effect chains based on sporadic tasks.
author:
- first_name: Mario
full_name: Günzel, Mario
last_name: Günzel
- first_name: Niklas
full_name: Ueter, Niklas
last_name: Ueter
- first_name: Kuan-Hsun
full_name: Chen, Kuan-Hsun
last_name: Chen
- first_name: Georg
full_name: von der Brüggen, Georg
last_name: von der Brüggen
- first_name: Jian-Jia
full_name: Chen, Jian-Jia
last_name: Chen
citation:
ama: Günzel M, Ueter N, Chen K-H, von der Brüggen G, Chen J-J. Probabilistic Reaction
Time Analysis. ACM Transactions on Embedded Computing Systems. 2023;22(5s):1-22.
doi:10.1145/3609390
apa: Günzel, M., Ueter, N., Chen, K.-H., von der Brüggen, G., & Chen, J.-J.
(2023). Probabilistic Reaction Time Analysis. ACM Transactions on Embedded
Computing Systems, 22(5s), 1–22. https://doi.org/10.1145/3609390
bibtex: '@article{Günzel_Ueter_Chen_von der Brüggen_Chen_2023, title={Probabilistic
Reaction Time Analysis}, volume={22}, DOI={10.1145/3609390},
number={5s}, journal={ACM Transactions on Embedded Computing Systems}, publisher={Association
for Computing Machinery (ACM)}, author={Günzel, Mario and Ueter, Niklas and Chen,
Kuan-Hsun and von der Brüggen, Georg and Chen, Jian-Jia}, year={2023}, pages={1–22}
}'
chicago: 'Günzel, Mario, Niklas Ueter, Kuan-Hsun Chen, Georg von der Brüggen, and
Jian-Jia Chen. “Probabilistic Reaction Time Analysis.” ACM Transactions on
Embedded Computing Systems 22, no. 5s (2023): 1–22. https://doi.org/10.1145/3609390.'
ieee: 'M. Günzel, N. Ueter, K.-H. Chen, G. von der Brüggen, and J.-J. Chen, “Probabilistic
Reaction Time Analysis,” ACM Transactions on Embedded Computing Systems,
vol. 22, no. 5s, pp. 1–22, 2023, doi: 10.1145/3609390.'
mla: Günzel, Mario, et al. “Probabilistic Reaction Time Analysis.” ACM Transactions
on Embedded Computing Systems, vol. 22, no. 5s, Association for Computing
Machinery (ACM), 2023, pp. 1–22, doi:10.1145/3609390.
short: M. Günzel, N. Ueter, K.-H. Chen, G. von der Brüggen, J.-J. Chen, ACM Transactions
on Embedded Computing Systems 22 (2023) 1–22.
date_created: 2026-07-03T21:14:22Z
date_updated: 2026-07-05T14:46:59Z
doi: 10.1145/3609390
intvolume: ' 22'
issue: 5s
language:
- iso: eng
page: 1-22
publication: ACM Transactions on Embedded Computing Systems
publication_identifier:
issn:
- 1539-9087
- 1558-3465
publication_status: published
publisher: Association for Computing Machinery (ACM)
status: public
title: Probabilistic Reaction Time Analysis
type: journal_article
user_id: '128464'
volume: 22
year: '2023'
...
---
_id: '66188'
abstract:
- lang: eng
text: |-
In many embedded systems, for instance, in the automotive, avionic, or robotics domain, critical functionalities are implemented via chains of communicating recurrent tasks. To ensure safety and correctness of such systems, guarantees on the reaction time, that is, the delay between a cause (e.g., an external activity or reading of a sensor) and the corresponding effect, must be provided.
Current approaches focus on the maximum reaction time, considering the worst-case system behavior. However, in many scenarios, probabilistic guarantees on the reaction time are sufficient. That is, it is sufficient to provide a guarantee that the reaction does not exceed a certain threshold with (at least) a certain probability.
This work provides such probabilistic guarantees on the reaction time, considering two types of randomness: response time randomness and failure probabilities. To the best of our knowledge, this is the first work that defines and analyzes probabilistic reaction time for cause-effect chains based on sporadic tasks.
author:
- first_name: Mario
full_name: Günzel, Mario
last_name: Günzel
- first_name: Niklas
full_name: Ueter, Niklas
last_name: Ueter
- first_name: Kuan-Hsun
full_name: Chen, Kuan-Hsun
last_name: Chen
- first_name: Georg
full_name: von der Brüggen, Georg
last_name: von der Brüggen
- first_name: Jian-Jia
full_name: Chen, Jian-Jia
last_name: Chen
citation:
ama: Günzel M, Ueter N, Chen K-H, von der Brüggen G, Chen J-J. Probabilistic Reaction
Time Analysis. ACM Transactions on Embedded Computing Systems. 2023;22(5s):1-22.
doi:10.1145/3609390
apa: Günzel, M., Ueter, N., Chen, K.-H., von der Brüggen, G., & Chen, J.-J.
(2023). Probabilistic Reaction Time Analysis. ACM Transactions on Embedded
Computing Systems, 22(5s), 1–22. https://doi.org/10.1145/3609390
bibtex: '@article{Günzel_Ueter_Chen_von der Brüggen_Chen_2023, title={Probabilistic
Reaction Time Analysis}, volume={22}, DOI={10.1145/3609390},
number={5s}, journal={ACM Transactions on Embedded Computing Systems}, publisher={Association
for Computing Machinery (ACM)}, author={Günzel, Mario and Ueter, Niklas and Chen,
Kuan-Hsun and von der Brüggen, Georg and Chen, Jian-Jia}, year={2023}, pages={1–22}
}'
chicago: 'Günzel, Mario, Niklas Ueter, Kuan-Hsun Chen, Georg von der Brüggen, and
Jian-Jia Chen. “Probabilistic Reaction Time Analysis.” ACM Transactions on
Embedded Computing Systems 22, no. 5s (2023): 1–22. https://doi.org/10.1145/3609390.'
ieee: 'M. Günzel, N. Ueter, K.-H. Chen, G. von der Brüggen, and J.-J. Chen, “Probabilistic
Reaction Time Analysis,” ACM Transactions on Embedded Computing Systems,
vol. 22, no. 5s, pp. 1–22, 2023, doi: 10.1145/3609390.'
mla: Günzel, Mario, et al. “Probabilistic Reaction Time Analysis.” ACM Transactions
on Embedded Computing Systems, vol. 22, no. 5s, Association for Computing
Machinery (ACM), 2023, pp. 1–22, doi:10.1145/3609390.
short: M. Günzel, N. Ueter, K.-H. Chen, G. von der Brüggen, J.-J. Chen, ACM Transactions
on Embedded Computing Systems 22 (2023) 1–22.
date_created: 2026-07-03T21:15:09Z
date_updated: 2026-07-05T14:47:08Z
doi: 10.1145/3609390
intvolume: ' 22'
issue: 5s
language:
- iso: eng
page: 1-22
publication: ACM Transactions on Embedded Computing Systems
publication_identifier:
issn:
- 1539-9087
- 1558-3465
publication_status: published
publisher: Association for Computing Machinery (ACM)
status: public
title: Probabilistic Reaction Time Analysis
type: journal_article
user_id: '128464'
volume: 22
year: '2023'
...
---
_id: '66203'
abstract:
- lang: eng
text: For timing-sensitive edge applications, the demand for efficient lightweight
machine learning solutions has increased recently. Tree ensembles are among the
state-of-the-art in many machine learning applications. While single decision
trees are comparably small, an ensemble of trees can have a significant memory
footprint leading to cache locality issues, which are crucial to performance in
terms of execution time. In this work, we analyze memory-locality issues of the
two most common realizations of decision trees, i.e., native and if-else trees.
We highlight that both realizations demand a more careful memory layout to improve
caching behavior and maximize performance. We adopt a probabilistic model of decision
tree inference to find the best memory layout for each tree at the application
layer. Further, we present an efficient heuristic to take architecture-dependent
information into account thereby optimizing the given ensemble for a target computer
architecture. Our code-generation framework, which is freely available on an open-source
repository, produces optimized code sessions while preserving the structure and
accuracy of the trees. With several real-world data sets, we evaluate the elapsed
time of various tree realizations on server hardware as well as embedded systems
for Intel and ARM processors. Our optimized memory layout achieves a reduction
in execution time up to 75 % execution for server-class systems, and up to 70
% for embedded systems, respectively.
author:
- first_name: Kuan-Hsun
full_name: Chen, Kuan-Hsun
last_name: Chen
- first_name: Chiahui
full_name: Su, Chiahui
last_name: Su
- first_name: Christian
full_name: Hakert, Christian
last_name: Hakert
- first_name: Sebastian
full_name: Buschjäger, Sebastian
last_name: Buschjäger
- first_name: Chao-Lin
full_name: Lee, Chao-Lin
last_name: Lee
- first_name: Jenq-Kuen
full_name: Lee, Jenq-Kuen
last_name: Lee
- first_name: Katharina
full_name: Morik, Katharina
last_name: Morik
- first_name: Jian-Jia
full_name: Chen, Jian-Jia
last_name: Chen
citation:
ama: Chen K-H, Su C, Hakert C, et al. Efficient Realization of Decision Trees for
Real-Time Inference. ACM Transactions on Embedded Computing Systems. 2022;21(6):1-26.
doi:10.1145/3508019
apa: Chen, K.-H., Su, C., Hakert, C., Buschjäger, S., Lee, C.-L., Lee, J.-K., Morik,
K., & Chen, J.-J. (2022). Efficient Realization of Decision Trees for Real-Time
Inference. ACM Transactions on Embedded Computing Systems, 21(6),
1–26. https://doi.org/10.1145/3508019
bibtex: '@article{Chen_Su_Hakert_Buschjäger_Lee_Lee_Morik_Chen_2022, title={Efficient
Realization of Decision Trees for Real-Time Inference}, volume={21}, DOI={10.1145/3508019},
number={6}, journal={ACM Transactions on Embedded Computing Systems}, publisher={Association
for Computing Machinery (ACM)}, author={Chen, Kuan-Hsun and Su, Chiahui and Hakert,
Christian and Buschjäger, Sebastian and Lee, Chao-Lin and Lee, Jenq-Kuen and Morik,
Katharina and Chen, Jian-Jia}, year={2022}, pages={1–26} }'
chicago: 'Chen, Kuan-Hsun, Chiahui Su, Christian Hakert, Sebastian Buschjäger, Chao-Lin
Lee, Jenq-Kuen Lee, Katharina Morik, and Jian-Jia Chen. “Efficient Realization
of Decision Trees for Real-Time Inference.” ACM Transactions on Embedded Computing
Systems 21, no. 6 (2022): 1–26. https://doi.org/10.1145/3508019.'
ieee: 'K.-H. Chen et al., “Efficient Realization of Decision Trees for Real-Time
Inference,” ACM Transactions on Embedded Computing Systems, vol. 21, no.
6, pp. 1–26, 2022, doi: 10.1145/3508019.'
mla: Chen, Kuan-Hsun, et al. “Efficient Realization of Decision Trees for Real-Time
Inference.” ACM Transactions on Embedded Computing Systems, vol. 21, no.
6, Association for Computing Machinery (ACM), 2022, pp. 1–26, doi:10.1145/3508019.
short: K.-H. Chen, C. Su, C. Hakert, S. Buschjäger, C.-L. Lee, J.-K. Lee, K. Morik,
J.-J. Chen, ACM Transactions on Embedded Computing Systems 21 (2022) 1–26.
date_created: 2026-07-03T21:17:45Z
date_updated: 2026-07-05T14:45:39Z
doi: 10.1145/3508019
intvolume: ' 21'
issue: '6'
language:
- iso: eng
page: 1-26
publication: ACM Transactions on Embedded Computing Systems
publication_identifier:
issn:
- 1539-9087
- 1558-3465
publication_status: published
publisher: Association for Computing Machinery (ACM)
status: public
title: Efficient Realization of Decision Trees for Real-Time Inference
type: journal_article
user_id: '128464'
volume: 21
year: '2022'
...
---
_id: '66209'
abstract:
- lang: eng
text: For timing-sensitive edge applications, the demand for efficient lightweight
machine learning solutions has increased recently. Tree ensembles are among the
state-of-the-art in many machine learning applications. While single decision
trees are comparably small, an ensemble of trees can have a significant memory
footprint leading to cache locality issues, which are crucial to performance in
terms of execution time. In this work, we analyze memory-locality issues of the
two most common realizations of decision trees, i.e., native and if-else trees.
We highlight that both realizations demand a more careful memory layout to improve
caching behavior and maximize performance. We adopt a probabilistic model of decision
tree inference to find the best memory layout for each tree at the application
layer. Further, we present an efficient heuristic to take architecture-dependent
information into account thereby optimizing the given ensemble for a target computer
architecture. Our code-generation framework, which is freely available on an open-source
repository, produces optimized code sessions while preserving the structure and
accuracy of the trees. With several real-world data sets, we evaluate the elapsed
time of various tree realizations on server hardware as well as embedded systems
for Intel and ARM processors. Our optimized memory layout achieves a reduction
in execution time up to 75 % execution for server-class systems, and up to 70
% for embedded systems, respectively.
author:
- first_name: Kuan-Hsun
full_name: Chen, Kuan-Hsun
last_name: Chen
- first_name: Chiahui
full_name: Su, Chiahui
last_name: Su
- first_name: Christian
full_name: Hakert, Christian
last_name: Hakert
- first_name: Sebastian
full_name: Buschjäger, Sebastian
last_name: Buschjäger
- first_name: Chao-Lin
full_name: Lee, Chao-Lin
last_name: Lee
- first_name: Jenq-Kuen
full_name: Lee, Jenq-Kuen
last_name: Lee
- first_name: Katharina
full_name: Morik, Katharina
last_name: Morik
- first_name: Jian-Jia
full_name: Chen, Jian-Jia
last_name: Chen
citation:
ama: Chen K-H, Su C, Hakert C, et al. Efficient Realization of Decision Trees for
Real-Time Inference. ACM Transactions on Embedded Computing Systems. 2022;21(6):1-26.
doi:10.1145/3508019
apa: Chen, K.-H., Su, C., Hakert, C., Buschjäger, S., Lee, C.-L., Lee, J.-K., Morik,
K., & Chen, J.-J. (2022). Efficient Realization of Decision Trees for Real-Time
Inference. ACM Transactions on Embedded Computing Systems, 21(6),
1–26. https://doi.org/10.1145/3508019
bibtex: '@article{Chen_Su_Hakert_Buschjäger_Lee_Lee_Morik_Chen_2022, title={Efficient
Realization of Decision Trees for Real-Time Inference}, volume={21}, DOI={10.1145/3508019},
number={6}, journal={ACM Transactions on Embedded Computing Systems}, publisher={Association
for Computing Machinery (ACM)}, author={Chen, Kuan-Hsun and Su, Chiahui and Hakert,
Christian and Buschjäger, Sebastian and Lee, Chao-Lin and Lee, Jenq-Kuen and Morik,
Katharina and Chen, Jian-Jia}, year={2022}, pages={1–26} }'
chicago: 'Chen, Kuan-Hsun, Chiahui Su, Christian Hakert, Sebastian Buschjäger, Chao-Lin
Lee, Jenq-Kuen Lee, Katharina Morik, and Jian-Jia Chen. “Efficient Realization
of Decision Trees for Real-Time Inference.” ACM Transactions on Embedded Computing
Systems 21, no. 6 (2022): 1–26. https://doi.org/10.1145/3508019.'
ieee: 'K.-H. Chen et al., “Efficient Realization of Decision Trees for Real-Time
Inference,” ACM Transactions on Embedded Computing Systems, vol. 21, no.
6, pp. 1–26, 2022, doi: 10.1145/3508019.'
mla: Chen, Kuan-Hsun, et al. “Efficient Realization of Decision Trees for Real-Time
Inference.” ACM Transactions on Embedded Computing Systems, vol. 21, no.
6, Association for Computing Machinery (ACM), 2022, pp. 1–26, doi:10.1145/3508019.
short: K.-H. Chen, C. Su, C. Hakert, S. Buschjäger, C.-L. Lee, J.-K. Lee, K. Morik,
J.-J. Chen, ACM Transactions on Embedded Computing Systems 21 (2022) 1–26.
date_created: 2026-07-03T21:18:32Z
date_updated: 2026-07-05T14:45:55Z
doi: 10.1145/3508019
intvolume: ' 21'
issue: '6'
language:
- iso: eng
page: 1-26
publication: ACM Transactions on Embedded Computing Systems
publication_identifier:
issn:
- 1539-9087
- 1558-3465
publication_status: published
publisher: Association for Computing Machinery (ACM)
status: public
title: Efficient Realization of Decision Trees for Real-Time Inference
type: journal_article
user_id: '128464'
volume: 21
year: '2022'
...
---
_id: '66202'
abstract:
- lang: eng
text: |-
In-memory wear-leveling has become an important research field for emerging non-volatile main memories over the past years. Many approaches in the literature perform wear-leveling by making use of special hardware. Since most non-volatile memories only wear out from write accesses, the proposed approaches in the literature also usually try to spread write accesses widely over the entire memory space. Some non-volatile memories, however, also wear out from read accesses, because every read causes a consecutive write access. Software-based solutions only operate from the application or kernel level, where read and write accesses are realized with different instructions and semantics. Therefore different mechanisms are required to handle reads and writes on the software level. First, we design a method to approximate read and write accesses to the memory to allow aging aware coarse-grained wear-leveling in the absence of special hardware, providing the age information. Second, we provide specific solutions to resolve
access hot-spots
within the compiled program code (text segment) and on the application stack. In our evaluation, we estimate the cell age by counting the total amount of accesses per cell. The results show that employing all our methods improves the memory lifetime by up to a factor of 955×.
author:
- first_name: Christian
full_name: Hakert, Christian
last_name: Hakert
- first_name: Kuan-Hsun
full_name: Chen, Kuan-Hsun
last_name: Chen
- first_name: Horst
full_name: Schirmeier, Horst
last_name: Schirmeier
- first_name: Lars
full_name: Bauer, Lars
last_name: Bauer
- first_name: Paul R.
full_name: Genssler, Paul R.
last_name: Genssler
- first_name: Georg
full_name: von der Brüggen, Georg
last_name: von der Brüggen
- first_name: Hussam
full_name: Amrouch, Hussam
last_name: Amrouch
- first_name: Jörg
full_name: Henkel, Jörg
last_name: Henkel
- first_name: Jian-Jia
full_name: Chen, Jian-Jia
last_name: Chen
citation:
ama: Hakert C, Chen K-H, Schirmeier H, et al. Software-Managed Read and Write Wear-Leveling
for Non-Volatile Main Memory. ACM Transactions on Embedded Computing Systems.
2022;21(1):1-24. doi:10.1145/3483839
apa: Hakert, C., Chen, K.-H., Schirmeier, H., Bauer, L., Genssler, P. R., von der
Brüggen, G., Amrouch, H., Henkel, J., & Chen, J.-J. (2022). Software-Managed
Read and Write Wear-Leveling for Non-Volatile Main Memory. ACM Transactions
on Embedded Computing Systems, 21(1), 1–24. https://doi.org/10.1145/3483839
bibtex: '@article{Hakert_Chen_Schirmeier_Bauer_Genssler_von der Brüggen_Amrouch_Henkel_Chen_2022,
title={Software-Managed Read and Write Wear-Leveling for Non-Volatile Main Memory},
volume={21}, DOI={10.1145/3483839},
number={1}, journal={ACM Transactions on Embedded Computing Systems}, publisher={Association
for Computing Machinery (ACM)}, author={Hakert, Christian and Chen, Kuan-Hsun
and Schirmeier, Horst and Bauer, Lars and Genssler, Paul R. and von der Brüggen,
Georg and Amrouch, Hussam and Henkel, Jörg and Chen, Jian-Jia}, year={2022}, pages={1–24}
}'
chicago: 'Hakert, Christian, Kuan-Hsun Chen, Horst Schirmeier, Lars Bauer, Paul
R. Genssler, Georg von der Brüggen, Hussam Amrouch, Jörg Henkel, and Jian-Jia
Chen. “Software-Managed Read and Write Wear-Leveling for Non-Volatile Main Memory.”
ACM Transactions on Embedded Computing Systems 21, no. 1 (2022): 1–24.
https://doi.org/10.1145/3483839.'
ieee: 'C. Hakert et al., “Software-Managed Read and Write Wear-Leveling for
Non-Volatile Main Memory,” ACM Transactions on Embedded Computing Systems,
vol. 21, no. 1, pp. 1–24, 2022, doi: 10.1145/3483839.'
mla: Hakert, Christian, et al. “Software-Managed Read and Write Wear-Leveling for
Non-Volatile Main Memory.” ACM Transactions on Embedded Computing Systems,
vol. 21, no. 1, Association for Computing Machinery (ACM), 2022, pp. 1–24, doi:10.1145/3483839.
short: C. Hakert, K.-H. Chen, H. Schirmeier, L. Bauer, P.R. Genssler, G. von der
Brüggen, H. Amrouch, J. Henkel, J.-J. Chen, ACM Transactions on Embedded Computing
Systems 21 (2022) 1–24.
date_created: 2026-07-03T21:17:30Z
date_updated: 2026-07-05T14:45:36Z
doi: 10.1145/3483839
intvolume: ' 21'
issue: '1'
language:
- iso: eng
page: 1-24
publication: ACM Transactions on Embedded Computing Systems
publication_identifier:
issn:
- 1539-9087
- 1558-3465
publication_status: published
publisher: Association for Computing Machinery (ACM)
status: public
title: Software-Managed Read and Write Wear-Leveling for Non-Volatile Main Memory
type: journal_article
user_id: '128464'
volume: 21
year: '2022'
...
---
_id: '66222'
abstract:
- lang: eng
text: |-
Dynamic power management (DPM) reduces the power consumption of a computing system when it idles, by switching the system into a low power state for hibernation. When all processors in the system share the same component, e.g., a shared memory, powering off this component during hibernation is only possible when all processors idle at the same time. For a real-time system, the schedulability property has to be guaranteed on every processor, especially if idle intervals are considered to be actively introduced.
In this work, we consider real-time systems with hybrid shared-memory architectures, which consist of shared volatile memory (VM) and non-volatile memory (NVM). Energy-efficient execution is achieved by applying DPM to turn off all memories during the hibernation mode. Towards this, we first explore the hybrid memory architectures and suggest a task model, which features configurable hibernation overheads. We propose a multi-processor procrastination algorithm (HEART), based on partitioned earliest-deadline-first (pEDF) scheduling. Our algorithm facilitates reducing the energy consumption by actively enlarging the hibernation time. It enforces all processors to idle simultaneously without violating the schedulability condition, such that the system can enter the hibernation state, where shared memories are turned off. Throughout extensive evaluation of HEART, we demonstrate (1) the increase in potential hibernation time, respectively the decrease in energy consumption, and (2) that our algorithm is not only more general but also has better performance than the state of the art with respect to energy efficiency in most cases.
author:
- first_name: Mario
full_name: Günzel, Mario
last_name: Günzel
- first_name: Christian
full_name: Hakert, Christian
last_name: Hakert
- first_name: Kuan-Hsun
full_name: Chen, Kuan-Hsun
last_name: Chen
- first_name: Jian-Jia
full_name: Chen, Jian-Jia
last_name: Chen
citation:
ama: Günzel M, Hakert C, Chen K-H, Chen J-J. HEART: <u>H</u>
ybrid Memory and <u>E</u> nergy-
<u>A</u> ware <u>R</u>
eal- <u>T</u> ime Scheduling
for Multi-Processor Systems. ACM Transactions on Embedded Computing Systems.
2021;20(5s):1-23. doi:10.1145/3477019
apa: Günzel, M., Hakert, C., Chen, K.-H., & Chen, J.-J. (2021). HEART:
<u>H</u> ybrid Memory and <u>E</u>
nergy- <u>A</u> ware
<u>R</u> eal- <u>T</u>
ime Scheduling for Multi-Processor Systems. ACM Transactions on
Embedded Computing Systems, 20(5s), 1–23. https://doi.org/10.1145/3477019
bibtex: '@article{Günzel_Hakert_Chen_Chen_2021, title={HEART: <u>H</u>
ybrid Memory and <u>E</u> nergy-
<u>A</u> ware <u>R</u>
eal- <u>T</u> ime Scheduling
for Multi-Processor Systems}, volume={20}, DOI={10.1145/3477019},
number={5s}, journal={ACM Transactions on Embedded Computing Systems}, publisher={Association
for Computing Machinery (ACM)}, author={Günzel, Mario and Hakert, Christian and
Chen, Kuan-Hsun and Chen, Jian-Jia}, year={2021}, pages={1–23} }'
chicago: 'Günzel, Mario, Christian Hakert, Kuan-Hsun Chen, and Jian-Jia Chen. “HEART:
<u>H</U> Ybrid Memory and <u>E</U>
Nergy- <u>A</U> Ware
<u>R</U> Eal- <u>T</U>
Ime Scheduling for Multi-Processor Systems.” ACM Transactions on
Embedded Computing Systems 20, no. 5s (2021): 1–23. https://doi.org/10.1145/3477019.'
ieee: 'M. Günzel, C. Hakert, K.-H. Chen, and J.-J. Chen, “HEART: <u>H</u>
ybrid Memory and <u>E</u> nergy-
<u>A</u> ware <u>R</u>
eal- <u>T</u> ime Scheduling
for Multi-Processor Systems,” ACM Transactions on Embedded Computing Systems,
vol. 20, no. 5s, pp. 1–23, 2021, doi: 10.1145/3477019.'
mla: Günzel, Mario, et al. “HEART: <u>H</U>
Ybrid Memory and <u>E</U> Nergy-
<u>A</U> Ware <u>R</U>
Eal- <u>T</U> Ime Scheduling
for Multi-Processor Systems.” ACM Transactions on Embedded Computing Systems,
vol. 20, no. 5s, Association for Computing Machinery (ACM), 2021, pp. 1–23, doi:10.1145/3477019.
short: M. Günzel, C. Hakert, K.-H. Chen, J.-J. Chen, ACM Transactions on Embedded
Computing Systems 20 (2021) 1–23.
date_created: 2026-07-03T21:21:20Z
date_updated: 2026-07-05T14:44:23Z
doi: 10.1145/3477019
intvolume: ' 20'
issue: 5s
language:
- iso: eng
page: 1-23
publication: ACM Transactions on Embedded Computing Systems
publication_identifier:
issn:
- 1539-9087
- 1558-3465
publication_status: published
publisher: Association for Computing Machinery (ACM)
status: public
title: |-
HEART:
H
ybrid Memory and
E
nergy-
A
ware
R
eal-
T
ime Scheduling for Multi-Processor Systems
type: journal_article
user_id: '128464'
volume: 20
year: '2021'
...
---
_id: '66217'
abstract:
- lang: eng
text: |-
Dynamic power management (DPM) reduces the power consumption of a computing system when it idles, by switching the system into a low power state for hibernation. When all processors in the system share the same component, e.g., a shared memory, powering off this component during hibernation is only possible when all processors idle at the same time. For a real-time system, the schedulability property has to be guaranteed on every processor, especially if idle intervals are considered to be actively introduced.
In this work, we consider real-time systems with hybrid shared-memory architectures, which consist of shared volatile memory (VM) and non-volatile memory (NVM). Energy-efficient execution is achieved by applying DPM to turn off all memories during the hibernation mode. Towards this, we first explore the hybrid memory architectures and suggest a task model, which features configurable hibernation overheads. We propose a multi-processor procrastination algorithm (HEART), based on partitioned earliest-deadline-first (pEDF) scheduling. Our algorithm facilitates reducing the energy consumption by actively enlarging the hibernation time. It enforces all processors to idle simultaneously without violating the schedulability condition, such that the system can enter the hibernation state, where shared memories are turned off. Throughout extensive evaluation of HEART, we demonstrate (1) the increase in potential hibernation time, respectively the decrease in energy consumption, and (2) that our algorithm is not only more general but also has better performance than the state of the art with respect to energy efficiency in most cases.
author:
- first_name: Mario
full_name: Günzel, Mario
last_name: Günzel
- first_name: Christian
full_name: Hakert, Christian
last_name: Hakert
- first_name: Kuan-Hsun
full_name: Chen, Kuan-Hsun
last_name: Chen
- first_name: Jian-Jia
full_name: Chen, Jian-Jia
last_name: Chen
citation:
ama: Günzel M, Hakert C, Chen K-H, Chen J-J. HEART: <u>H</u>
ybrid Memory and <u>E</u> nergy-
<u>A</u> ware <u>R</u>
eal- <u>T</u> ime Scheduling
for Multi-Processor Systems. ACM Transactions on Embedded Computing Systems.
2021;20(5s):1-23. doi:10.1145/3477019
apa: Günzel, M., Hakert, C., Chen, K.-H., & Chen, J.-J. (2021). HEART:
<u>H</u> ybrid Memory and <u>E</u>
nergy- <u>A</u> ware
<u>R</u> eal- <u>T</u>
ime Scheduling for Multi-Processor Systems. ACM Transactions on
Embedded Computing Systems, 20(5s), 1–23. https://doi.org/10.1145/3477019
bibtex: '@article{Günzel_Hakert_Chen_Chen_2021, title={HEART: <u>H</u>
ybrid Memory and <u>E</u> nergy-
<u>A</u> ware <u>R</u>
eal- <u>T</u> ime Scheduling
for Multi-Processor Systems}, volume={20}, DOI={10.1145/3477019},
number={5s}, journal={ACM Transactions on Embedded Computing Systems}, publisher={Association
for Computing Machinery (ACM)}, author={Günzel, Mario and Hakert, Christian and
Chen, Kuan-Hsun and Chen, Jian-Jia}, year={2021}, pages={1–23} }'
chicago: 'Günzel, Mario, Christian Hakert, Kuan-Hsun Chen, and Jian-Jia Chen. “HEART:
<u>H</U> Ybrid Memory and <u>E</U>
Nergy- <u>A</U> Ware
<u>R</U> Eal- <u>T</U>
Ime Scheduling for Multi-Processor Systems.” ACM Transactions on
Embedded Computing Systems 20, no. 5s (2021): 1–23. https://doi.org/10.1145/3477019.'
ieee: 'M. Günzel, C. Hakert, K.-H. Chen, and J.-J. Chen, “HEART: <u>H</u>
ybrid Memory and <u>E</u> nergy-
<u>A</u> ware <u>R</u>
eal- <u>T</u> ime Scheduling
for Multi-Processor Systems,” ACM Transactions on Embedded Computing Systems,
vol. 20, no. 5s, pp. 1–23, 2021, doi: 10.1145/3477019.'
mla: Günzel, Mario, et al. “HEART: <u>H</U>
Ybrid Memory and <u>E</U> Nergy-
<u>A</U> Ware <u>R</U>
Eal- <u>T</U> Ime Scheduling
for Multi-Processor Systems.” ACM Transactions on Embedded Computing Systems,
vol. 20, no. 5s, Association for Computing Machinery (ACM), 2021, pp. 1–23, doi:10.1145/3477019.
short: M. Günzel, C. Hakert, K.-H. Chen, J.-J. Chen, ACM Transactions on Embedded
Computing Systems 20 (2021) 1–23.
date_created: 2026-07-03T21:20:35Z
date_updated: 2026-07-05T14:45:23Z
doi: 10.1145/3477019
intvolume: ' 20'
issue: 5s
language:
- iso: eng
page: 1-23
publication: ACM Transactions on Embedded Computing Systems
publication_identifier:
issn:
- 1539-9087
- 1558-3465
publication_status: published
publisher: Association for Computing Machinery (ACM)
status: public
title: |-
HEART:
H
ybrid Memory and
E
nergy-
A
ware
R
eal-
T
ime Scheduling for Multi-Processor Systems
type: journal_article
user_id: '128464'
volume: 20
year: '2021'
...
---
_id: '66246'
abstract:
- lang: eng
text: |-
A cause-effect chain is used to define the logical order of data dependent tasks, which is independent from the execution order of the jobs of the (periodic/sporadic) tasks. Analyzing the worst-case End-to-End timing behavior, associated to a cause-effect chain, is an important problem in embedded control systems. For example, the detailed timing properties of modern automotive systems are specified in the AUTOSAR Timing Extensions.
In this paper, we present a formal End-to-End timing analysis for distributed systems. We consider the two most important End-to-End timing semantics, i.e., the button-to-action delay (termed as the
maximum reaction time
) and the worst-case data freshness (termed as the
maximum data age
). Our contribution is significant due to the consideration of the sporadic behavior of job activations, whilst the results in the literature have been mostly limited to periodic activations. The proof strategy shows the (previously unexplored) connection between the reaction time (data age, respectively) and immediate forward (backward, respectively) job chains. Our analytical results dominate the state of the art for sporadic task activations in distributed systems and the evaluations show a clear improvement for synthesized task systems as well as for a real world automotive benchmark setting.
author:
- first_name: Marco
full_name: Dürr, Marco
last_name: Dürr
- first_name: Georg Von Der
full_name: Brüggen, Georg Von Der
last_name: Brüggen
- first_name: Kuan-Hsun
full_name: Chen, Kuan-Hsun
last_name: Chen
- first_name: Jian-Jia
full_name: Chen, Jian-Jia
last_name: Chen
citation:
ama: Dürr M, Brüggen GVD, Chen K-H, Chen J-J. End-to-End Timing Analysis of Sporadic
Cause-Effect Chains in Distributed Systems. ACM Transactions on Embedded Computing
Systems. 2019;18(5s):1-24. doi:10.1145/3358181
apa: Dürr, M., Brüggen, G. V. D., Chen, K.-H., & Chen, J.-J. (2019). End-to-End
Timing Analysis of Sporadic Cause-Effect Chains in Distributed Systems. ACM
Transactions on Embedded Computing Systems, 18(5s), 1–24. https://doi.org/10.1145/3358181
bibtex: '@article{Dürr_Brüggen_Chen_Chen_2019, title={End-to-End Timing Analysis
of Sporadic Cause-Effect Chains in Distributed Systems}, volume={18}, DOI={10.1145/3358181}, number={5s}, journal={ACM
Transactions on Embedded Computing Systems}, publisher={Association for Computing
Machinery (ACM)}, author={Dürr, Marco and Brüggen, Georg Von Der and Chen, Kuan-Hsun
and Chen, Jian-Jia}, year={2019}, pages={1–24} }'
chicago: 'Dürr, Marco, Georg Von Der Brüggen, Kuan-Hsun Chen, and Jian-Jia Chen.
“End-to-End Timing Analysis of Sporadic Cause-Effect Chains in Distributed Systems.”
ACM Transactions on Embedded Computing Systems 18, no. 5s (2019): 1–24.
https://doi.org/10.1145/3358181.'
ieee: 'M. Dürr, G. V. D. Brüggen, K.-H. Chen, and J.-J. Chen, “End-to-End Timing
Analysis of Sporadic Cause-Effect Chains in Distributed Systems,” ACM Transactions
on Embedded Computing Systems, vol. 18, no. 5s, pp. 1–24, 2019, doi: 10.1145/3358181.'
mla: Dürr, Marco, et al. “End-to-End Timing Analysis of Sporadic Cause-Effect Chains
in Distributed Systems.” ACM Transactions on Embedded Computing Systems,
vol. 18, no. 5s, Association for Computing Machinery (ACM), 2019, pp. 1–24, doi:10.1145/3358181.
short: M. Dürr, G.V.D. Brüggen, K.-H. Chen, J.-J. Chen, ACM Transactions on Embedded
Computing Systems 18 (2019) 1–24.
date_created: 2026-07-05T14:35:33Z
date_updated: 2026-07-05T14:43:49Z
doi: 10.1145/3358181
intvolume: ' 18'
issue: 5s
language:
- iso: eng
page: 1-24
publication: ACM Transactions on Embedded Computing Systems
publication_identifier:
issn:
- 1539-9087
- 1558-3465
publication_status: published
publisher: Association for Computing Machinery (ACM)
status: public
title: End-to-End Timing Analysis of Sporadic Cause-Effect Chains in Distributed Systems
type: journal_article
user_id: '128464'
volume: 18
year: '2019'
...