3.6 Timing Analysis and Measurement

Time	Label	Presentation Title Authors
14:30	3.6.1	CONSERVATIVE MODELING OF SHARED RESOURCE CONTENTION FOR DEPENDENT TASKS IN PARTITIONED MULTI-CORE SYSTEMS Speaker: Junchul Choi, Seoul National University, KR Authors: Junchul Choi, Donghyun Kang and Soonhoi Ha, Seoul National University, KR Abstract In a multi-core system with shared resources, the accesses to the shared resources from several cores may experience non-deterministic arbitration delay due to resource contention. Such delay should be considered conservatively in the worst case response time (WCRT) analysis of multi-core systems. Recently, several techniques have been proposed to account for arbitration delay for shared resource contention, based on the event stream modeling of resource access. While they all assume independent tasks, in this paper, we propose a conservative modeling technique of shared resource contention supporting dependent tasks. To find a tight upper bound of arbitration delay, we derive a shared resource demand bound for each processing element, considering the task dependency. The proposed technique is not specific to a particular WCRT analysis method, and supports both preemptive and non-preemptive scheduling policy. In the experiments, the significance of considering data dependency of parallel applications and the performance of our technique are verified by synthetic examples and a real-life example. Download Paper (PDF; Only available from the DATE venue WiFi)
15:00	3.6.2	FORMAL WORST-CASE TIMING ANALYSIS OF ETHERNET TSN'S BURST-LIMITING SHAPER Speaker: Daniel Thiele, Technische Universität Braunschweig, DE Authors: Daniel Thiele and Rolf Ernst, Technische Universität Braunschweig, DE Abstract Future in-vehicle networks will use Ethernet as their communication backbone. As many automotive applications are latency-sensitive and have strict real-time requirements, a key challenge in automotive network design is the deterministic low-latency transport of latency-critical Ethernet frames. Time-sensitive networking (TSN) is an upcoming set of Ethernet standards, which address these requirements by specifying new quality of service mechanisms in the form of different traffic shapers. One of these traffic shapers is the burst-limiting shaper (BLS). In this paper, we evaluate whether BLS is able to fulfill these strict timing requirements. We present a formal timing analysis for BLS in order to compute worst-case latency bounds. We use a realistic automotive Ethernet setup to compare BLS against Ethernet AVB and Ethernet following IEEE 802.1Q. Download Paper (PDF; Only available from the DATE venue WiFi)
15:30	3.6.3	REAL-TIME ANALYSIS OF ENGINE CONTROL APPLICATIONS WITH SPEED ESTIMATION Speaker: Alessandro Biondi, Scuola Superiore Sant'Anna, IT Authors: Alessandro Biondi and Giorgio Buttazzo, Scuola Superiore Sant'Anna, IT Abstract Engine control applications include computational activities that adapt their behavior as a function of the engine speed, referred to as adaptive variable-rate (AVR) tasks. Although a substantial amount of work has been done to analyze the timing behavior of real-time applications with AVR tasks, most of the authors assumed the knowledge of the instantaneous engine speed at any instant. In practice, however, the instantaneous engine speed is not known and can only be estimated by various techniques, which hence introduce an error with respect to the ideal case of perfect knowledge. If not properly handled, such an error can result in a potentially unsafe analysis. This paper proposes a general approach to include speed estimators in the analysis of engine control applications and shows two particular examples using common speed estimators. Finally, estimators are also characterized through a numerical evaluation and experimental results are presented to evaluate their impact in terms of system schedulability. Download Paper (PDF; Only available from the DATE venue WiFi)
15:45	3.6.4	TRACE-BASED ANALYSIS METHODOLOGY OF PROGRAM FLASH CONTENTION IN EMBEDDED MULTICORE SYSTEMS Speaker: Lin Li, Infineon Technologies, DE Authors: Lin Li and Albrecht Mayer, Infineon Technologies, DE Abstract Contention for shared resources is a major performance issue in multicore systems. In embedded multicore microcontrollers, contentions of program flash accesses have a significant performance impact, because the flash access has a large latency compared to a core clock cycle. Therefore, the detection and analysis of program flash contentions are necessary to remedy this situation. With a lack of existing tools being able to fulfill this task, a novel post-processing analysis methodology is proposed in this paper to acquire the information of program flash contentions in detail based on the non-intrusive trace. This information can be utilized to improve the overall performance and particularly to enhance the real-time performance of specific threads or functions for hard real-time multicore systems. Download Paper (PDF; Only available from the DATE venue WiFi)
16:00	IP1-17, 397	DESIGN OF AN EFFICIENT READY QUEUE FOR EARLIEST-DEADLINE-FIRST (EDF) SCHEDULER Speaker and Author: Risat Mahmud Pathan, Chalmers University of Technology, SE Abstract Although dynamic-priority-based EDF algorithm is known to be theoretically optimal for scheduling sporadic real-time tasks on uniprocessor, fixed-priority (FP) scheduling is mostly used in practice. One of the main reasons for FP scheduling being popular in the industry is its efficient implementation: operations on the ready queue can be done in constant time. On the other hand, ready queue of EDF scheduler is generally implemented as a priority queue, for example, using a binary min-heap data structure in which (insertion/deletion) operation cannot be done in constant time. This paper proposes a new design of ready queue for EDF scheduler: a simple data structure for the ready queue and efficient operations to insert and remove task control blocks (TCBs) to and from the ready queue are proposed. Insertion of a TCB of a newly released job (that cannot preempt the currently-executing job) is done in non-constant time. However, insertion of a TCB of a preempted job or the removal of the TCB of job having the highest EDF priority from the ready queue can be done in constant time. Simulation using randomly generated task sets shows that the overhead of managing jobs in our proposed ready queue for EDF scheduler is significantly lower than that of other approaches. We believe that theoretically optimal EDF algorithm implemented based on our proposed ready-queue data structure will make EDF popular in industry. Download Paper (PDF; Only available from the DATE venue WiFi)
16:00		End of session Coffee Break in Exhibition Area

Time

Label

Presentation Title
Authors

14:30

3.6.1

CONSERVATIVE MODELING OF SHARED RESOURCE CONTENTION FOR DEPENDENT TASKS IN PARTITIONED MULTI-CORE SYSTEMS
Speaker:
Junchul Choi, Seoul National University, KR
Authors:
Junchul Choi, Donghyun Kang and Soonhoi Ha, Seoul National University, KR
Abstract
In a multi-core system with shared resources, the accesses to the shared resources from several cores may experience non-deterministic arbitration delay due to resource contention. Such delay should be considered conservatively in the worst case response time (WCRT) analysis of multi-core systems. Recently, several techniques have been proposed to account for arbitration delay for shared resource contention, based on the event stream modeling of resource access. While they all assume independent tasks, in this paper, we propose a conservative modeling technique of shared resource contention supporting dependent tasks. To find a tight upper bound of arbitration delay, we derive a shared resource demand bound for each processing element, considering the task dependency. The proposed technique is not specific to a particular WCRT analysis method, and supports both preemptive and non-preemptive scheduling policy. In the experiments, the significance of considering data dependency of parallel applications and the performance of our technique are verified by synthetic examples and a real-life example.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:00

3.6.2

FORMAL WORST-CASE TIMING ANALYSIS OF ETHERNET TSN'S BURST-LIMITING SHAPER
Speaker:
Daniel Thiele, Technische Universität Braunschweig, DE
Authors:
Daniel Thiele and Rolf Ernst, Technische Universität Braunschweig, DE
Abstract
Future in-vehicle networks will use Ethernet as their communication backbone. As many automotive applications are latency-sensitive and have strict real-time requirements, a key challenge in automotive network design is the deterministic low-latency transport of latency-critical Ethernet frames. Time-sensitive networking (TSN) is an upcoming set of Ethernet standards, which address these requirements by specifying new quality of service mechanisms in the form of different traffic shapers. One of these traffic shapers is the burst-limiting shaper (BLS). In this paper, we evaluate whether BLS is able to fulfill these strict timing requirements. We present a formal timing analysis for BLS in order to compute worst-case latency bounds. We use a realistic automotive Ethernet setup to compare BLS against Ethernet AVB and Ethernet following IEEE 802.1Q.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:30

3.6.3

REAL-TIME ANALYSIS OF ENGINE CONTROL APPLICATIONS WITH SPEED ESTIMATION
Speaker:
Alessandro Biondi, Scuola Superiore Sant'Anna, IT
Authors:
Alessandro Biondi and Giorgio Buttazzo, Scuola Superiore Sant'Anna, IT
Abstract
Engine control applications include computational activities that adapt their behavior as a function of the engine speed, referred to as adaptive variable-rate (AVR) tasks. Although a substantial amount of work has been done to analyze the timing behavior of real-time applications with AVR tasks, most of the authors assumed the knowledge of the instantaneous engine speed at any instant. In practice, however, the instantaneous engine speed is not known and can only be estimated by various techniques, which hence introduce an error with respect to the ideal case of perfect knowledge. If not properly handled, such an error can result in a potentially unsafe analysis. This paper proposes a general approach to include speed estimators in the analysis of engine control applications and shows two particular examples using common speed estimators. Finally, estimators are also characterized through a numerical evaluation and experimental results are presented to evaluate their impact in terms of system schedulability.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:45

3.6.4

TRACE-BASED ANALYSIS METHODOLOGY OF PROGRAM FLASH CONTENTION IN EMBEDDED MULTICORE SYSTEMS
Speaker:
Lin Li, Infineon Technologies, DE
Authors:
Lin Li and Albrecht Mayer, Infineon Technologies, DE
Abstract
Contention for shared resources is a major performance issue in multicore systems. In embedded multicore microcontrollers, contentions of program flash accesses have a significant performance impact, because the flash access has a large latency compared to a core clock cycle. Therefore, the detection and analysis of program flash contentions are necessary to remedy this situation. With a lack of existing tools being able to fulfill this task, a novel post-processing analysis methodology is proposed in this paper to acquire the information of program flash contentions in detail based on the non-intrusive trace. This information can be utilized to improve the overall performance and particularly to enhance the real-time performance of specific threads or functions for hard real-time multicore systems.
Download Paper (PDF; Only available from the DATE venue WiFi)

16:00

IP1-17, 397

DESIGN OF AN EFFICIENT READY QUEUE FOR EARLIEST-DEADLINE-FIRST (EDF) SCHEDULER
Speaker and Author:
Risat Mahmud Pathan, Chalmers University of Technology, SE
Abstract
Although dynamic-priority-based EDF algorithm is known to be theoretically optimal for scheduling sporadic real-time tasks on uniprocessor, fixed-priority (FP) scheduling is mostly used in practice. One of the main reasons for FP scheduling being popular in the industry is its efficient implementation: operations on the ready queue can be done in constant time. On the other hand, ready queue of EDF scheduler is generally implemented as a priority queue, for example, using a binary min-heap data structure in which (insertion/deletion) operation cannot be done in constant time. This paper proposes a new design of ready queue for EDF scheduler: a simple data structure for the ready queue and efficient operations to insert and remove task control blocks (TCBs) to and from the ready queue are proposed. Insertion of a TCB of a newly released job (that cannot preempt the currently-executing job) is done in non-constant time. However, insertion of a TCB of a preempted job or the removal of the TCB of job having the highest EDF priority from the ready queue can be done in constant time. Simulation using randomly generated task sets shows that the overhead of managing jobs in our proposed ready queue for EDF scheduler is significantly lower than that of other approaches. We believe that theoretically optimal EDF algorithm implemented based on our proposed ready-queue data structure will make EDF popular in industry.
Download Paper (PDF; Only available from the DATE venue WiFi)

16:00

End of session
Coffee Break in Exhibition Area

Visit us at DATE 2016