| 1. |
- Dai, Gaoyang, et al.
(författare)
-
Timing-Anomaly Free Dynamic Scheduling of Periodic DAG Tasks with Non-Preemptive Nodes
- 2021
-
Ingår i: 2021 IEEE 27th International Conference On Embedded And Real-Time Computing Systems And Applications (RTCSA 2021). - : Institute of Electrical and Electronics Engineers (IEEE). - 9781665441889 ; , s. 119-128
-
Konferensbidrag (refereegranskat)abstract
- Designing timing-anomaly free multiprocessor scheduling algorithms is a notoriously hard problem, especially for parallel tasks with non-preemptive execution regions. In this paper, we first propose a simple yet expressive model which abstracts a parallel task as a single computation unit, and then, present a sufficient condition for timing-anomaly free scheduling of such units. On top of this, we design an algorithm for scheduling a set of periodic parallel tasks, represented as DAG with non-preemptive subtasks, on multicore processors. The algorithm has several desirable properties, including timing-anomaly freedom, high resource utilization, and low memory requirement. Timing-anomaly freedom enables an exact schedulability test for the algorithm, which, as shown in our evaluations, provides a significantly high schedulability ratio compared to those state-of-the-art methods that suffer from timing anomalies.
|
|
| 2. |
- Friebe, Anna, et al.
(författare)
-
Adaptive Runtime Estimate of Task Execution Times using Bayesian Modeling
- 2021
-
Ingår i: Proceedings - 2021 IEEE 27th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2021. - : Institute of Electrical and Electronics Engineers Inc.. - 9781665441889 ; , s. 1-10
-
Konferensbidrag (refereegranskat)abstract
- In the recent works that analyzed execution-time variation of real-time tasks, it was shown that such variation may conform to regular behavior. This regularity may arise from multiple sources, e.g., due to periodic changes in hardware or program state, program structure, inter-task dependence or inter-task interference. Such complexity can be better captured by a Markov Model, compared to the common approach of assuming independent and identically distributed random variables. However, despite the regularity that may be described with a Markov model, over time, the execution times may change, due to irregular changes in input, hardware state, or program state. In this paper, we propose a Bayesian approach to adapt the emission distributions of the Markov Model at runtime, in order to account for such irregular variation. A preprocessing step determines the number of states and the transition matrix of the Markov Model from a portion of the execution time sequence. In the preprocessing step, segments of the execution time trace with similar properties are identified and combined into clusters. At runtime, the proposed method switches between these clusters based on a Generalized Likelihood Ratio (GLR). Using a Bayesian approach, clusters are updated and emission distributions estimated. New clusters can be identified and clusters can be merged at runtime. The time complexity of the online step is $O(N^{2}+ NC)$ where N is the number of states in the Hidden Markov Model (HMM) that is fixed after the preprocessing step, and C is the number of clusters.
|
|
