3.7 Scheduling and Optimization

Time	Label	Presentation Title Authors
14:30	3.7.1	THE CONCEPT OF UNSCHEDULABILITY CORE FOR OPTIMIZING PRIORITY ASSIGNMENT IN REAL-TIME SYSTEMS Speaker: Yecheng Zhao, Virginia Polytechnic Institute and State University, US Authors: Yecheng Zhao and Haibo Zeng, Virginia Tech, US Abstract In the design optimization of real-time systems, the schedulability analysis is used to define the feasibility region within which tasks meet their deadlines, so that optimization algorithms can find the best solution within the region. However, the complexity of current schedulability analysis techniques often makes it difficult to leverage existing optimization frameworks and scale to large designs. In this paper, we consider the design optimization problems for real-time systems scheduled with fixed priority, where task priority assignment is part of the decision variables. We propose the concept of unschedulability core, a compact representation of the schedulability conditions, and develop efficient algorithms for its calculation. We present a new optimization procedure based on lazy constraint paradigm that leverages such a concept. Experimental results on two case studies show that the new optimization procedure provides optimal solutions, but is a few magnitudes faster than other exact algorithms (Branch-and-Bound, Integer Linear Programming). Download Paper (PDF; Only available from the DATE venue WiFi)
15:00	3.7.2	UTILIZATION DIFFERENCE BASED PARTITIONED SCHEDULING OF MIXED-CRITICALITY SYSTEMS Speaker: Saravanan Ramanathan, Nanyang Technological University, SG Authors: Saravanan Ramanathan and Arvind Easwaran, Nanyang Technological University, SG Abstract Mixed-Criticality (MC) systems consolidate multiple functionalities with different criticalities onto a single hardware platform. Such systems improve the overall resource utilization while guaranteeing resources to critical tasks. In this paper, we focus on the problem of partitioned multiprocessor MC scheduling, in particular the problem of designing efficient partitioning strategies. We develop two new partitioning strategies based on the principle of evenly distributing the difference between total high-critical utilization and total low-critical utilization for the critical tasks among all processors. By balancing this difference, we are able to reduce the pessimism in uniprocessor MC schedulability tests that are applied on each processor, thus improving overall schedulability. To evaluate the schedulability performance of the proposed strategies, we compare them against existing partitioned algorithms using extensive experiments. We show that the proposed strategies are effective with both dynamic-priority Earliest Deadline First with Virtual Deadlines (EDF-VD) and fixed-priority Adaptive Mixed-Criticality (AMC) algorithms. Specifically, our results show that the proposed strategies improve schedulability by as much as 28.1% and 36.2% for implicit and constrained-deadline task systems respectively. Download Paper (PDF; Only available from the DATE venue WiFi)
15:30	3.7.3	SCHEDULABILITY USING NATIVE NON-PREEMPTIVE GROUPS ON AN AUTOSAR/OSEK PLATFORM WITH CACHES Speaker: Leo Hatvani, Technische Universiteit Eindhoven, NL Authors: Leo Hatvani¹, Reinder J. Bril¹ and Sebastian Altmeyer² ¹Technische Universiteit Eindhoven (TU/e), NL; ²University of Amsterdam (UvA), NL Abstract Fixed-priority preemption threshold scheduling (FPTS) is a limited preemptive scheduling scheme that generalizes both fixed-priority preemptive scheduling (FPPS) and fixed-priority non-preemptive scheduling (FPNS). By increasing the priority of tasks as they start executing it reduces the set of tasks that can preempt any given task. A subset of FPTS task configurations can be implemented natively on any AUTOSAR/OSEK compatible platform by utilizing the platform's native implementation of non-preemptive task groups via so called internal resources. The limiting factor for this implementation is the number of internal resources that can be associated with any individual task. OSEK and consequently AUTOSAR limit this number to one internal resource per task. In this work, we investigate the impact of this limitation on the schedulability of task sets when cache related preemption delays are taken into account. We also consider the impact of this restriction on the stack size when the tasks are executed on a shared-stack system. Download Paper (PDF; Only available from the DATE venue WiFi)
16:00	IP1-18, 637	GPUGUARD: TOWARDS SUPPORTING A PREDICTABLE EXECUTION MODEL FOR HETEROGENEOUS SOC Speaker: Björn Forsberg, ETH Zürich, CH Authors: Björn Forsberg¹, Andrea Marongiu² and Luca Benini³ ¹ETH Zürich, CH; ²Swiss Federal Institute of Technology in Zurich (ETHZ), CH; ³Università di Bologna, IT Abstract The deployment of real-time workloads on commercial off-the-shelf (COTS) hardware is attractive, as it reduces the cost and time-to-market of new products. Most modern high-end embedded SoCs rely on a heterogeneous design, coupling a general-purpose multi-core CPU to a massively parallel accelerator, typically a programmable GPU, sharing a single global DRAM. However, because of non-predictable hardware arbiters designed to maximize average or peak performance, it is very difficult to provide timing guarantees on such systems. In this work we present our ongoing work on GPUguard, a software technique that predictably arbitrates main memory usage in heterogeneous SoCs. A prototype implementation for the NVIDIA Tegra TX1 SoC shows that GPUguard is able to reduce the adverse effects of memory sharing, while retaining a high throughput on both the CPU and the accelerator. Download Paper (PDF; Only available from the DATE venue WiFi)
16:01	IP1-19, 226	A NON-INTRUSIVE, OPERATING SYSTEM INDEPENDENT SPINLOCK PROFILER FOR EMBEDDED MULTICORE SYSTEMS Speaker: Lin Li, Infineon Technologies, DE Authors: Lin Li¹, Philipp Wagner², Albrecht Mayer¹, Thomas Wild² and Andreas Herkersdorf³ ¹Infineon Technologies, DE; ²Technical University of Munich, DE; ³TU München, DE Abstract Locks are widely used as a synchronization method to guarantee the mutual exclusion for accesses to shared resources in multi-core embedded systems. They have been studied for years to improve performance, fairness, predictability etc. and a variety of lock implementations optimized for different scenarios have been proposed. In practice, applying an appropriate lock type to a specific scenario is usually based on the developer's hypothesis, which could mismatch the actual situation. A wrong lock type applied may result in lower performance and unfairness. Thus, a lock profiling tool is needed to increase the system transparency and guarantee the proper lock usage. In this paper, an operating-system-independent lock profiling approach is proposed as there are many different operating systems in the embedded field. This approach detects lock acquisition and lock releasing using hardware tracing based on hardware-level spinlock characteristics instead of specific libraries or APIs. The spinlocks are identified automatically; lock profiling statistics can be measured and performance-harmful lock behaviors are detected. With this information, the lock usage can be improved by the software developer. A prototype as a Java tool was implemented to conduct hardware tracing and analyze locks inside applications running on the Infineon AURIX microcontrollers. Download Paper (PDF; Only available from the DATE venue WiFi)
16:00		End of session Coffee Break in Exhibition Area On all conference days (Tuesday to Thursday), coffee and tea will be served during the coffee breaks at the below-mentioned times in the exhibition area. Tuesday, March 28, 2017 Coffee Break 10:30 - 11:30 Coffee Break 16:00 - 17:00 Wednesday, March 29, 2017 Coffee Break 10:00 - 11:00 Coffee Break 16:00 - 17:00 Thursday, March 30, 2017 Coffee Break 10:00 - 11:00 Coffee Break 15:30 - 16:00

Time

Label

Presentation Title
Authors

14:30

3.7.1

THE CONCEPT OF UNSCHEDULABILITY CORE FOR OPTIMIZING PRIORITY ASSIGNMENT IN REAL-TIME SYSTEMS
Speaker:
Yecheng Zhao, Virginia Polytechnic Institute and State University, US
Authors:
Yecheng Zhao and Haibo Zeng, Virginia Tech, US
Abstract
In the design optimization of real-time systems, the schedulability analysis is used to define the feasibility region within which tasks meet their deadlines, so that optimization algorithms can find the best solution within the region. However, the complexity of current schedulability analysis techniques often makes it difficult to leverage existing optimization frameworks and scale to large designs. In this paper, we consider the design optimization problems for real-time systems scheduled with fixed priority, where task priority assignment is part of the decision variables. We propose the concept of unschedulability core, a compact representation of the schedulability conditions, and develop efficient algorithms for its calculation. We present a new optimization procedure based on lazy constraint paradigm that leverages such a concept. Experimental results on two case studies show that the new optimization procedure provides optimal solutions, but is a few magnitudes faster than other exact algorithms (Branch-and-Bound, Integer Linear Programming).
Download Paper (PDF; Only available from the DATE venue WiFi)

15:00

3.7.2

UTILIZATION DIFFERENCE BASED PARTITIONED SCHEDULING OF MIXED-CRITICALITY SYSTEMS
Speaker:
Saravanan Ramanathan, Nanyang Technological University, SG
Authors:
Saravanan Ramanathan and Arvind Easwaran, Nanyang Technological University, SG
Abstract
Mixed-Criticality (MC) systems consolidate multiple functionalities with different criticalities onto a single hardware platform. Such systems improve the overall resource utilization while guaranteeing resources to critical tasks. In this paper, we focus on the problem of partitioned multiprocessor MC scheduling, in particular the problem of designing efficient partitioning strategies. We develop two new partitioning strategies based on the principle of evenly distributing the difference between total high-critical utilization and total low-critical utilization for the critical tasks among all processors. By balancing this difference, we are able to reduce the pessimism in uniprocessor MC schedulability tests that are applied on each processor, thus improving overall schedulability. To evaluate the schedulability performance of the proposed strategies, we compare them against existing partitioned algorithms using extensive experiments. We show that the proposed strategies are effective with both dynamic-priority Earliest Deadline First with Virtual Deadlines (EDF-VD) and fixed-priority Adaptive Mixed-Criticality (AMC) algorithms. Specifically, our results show that the proposed strategies improve schedulability by as much as 28.1% and 36.2% for implicit and constrained-deadline task systems respectively.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:30

3.7.3

SCHEDULABILITY USING NATIVE NON-PREEMPTIVE GROUPS ON AN AUTOSAR/OSEK PLATFORM WITH CACHES
Speaker:
Leo Hatvani, Technische Universiteit Eindhoven, NL
Authors:
Leo Hatvani¹, Reinder J. Bril¹ and Sebastian Altmeyer²
¹Technische Universiteit Eindhoven (TU/e), NL; ²University of Amsterdam (UvA), NL
Abstract
Fixed-priority preemption threshold scheduling (FPTS) is a limited preemptive scheduling scheme that generalizes both fixed-priority preemptive scheduling (FPPS) and fixed-priority non-preemptive scheduling (FPNS). By increasing the priority of tasks as they start executing it reduces the set of tasks that can preempt any given task. A subset of FPTS task configurations can be implemented natively on any AUTOSAR/OSEK compatible platform by utilizing the platform's native implementation of non-preemptive task groups via so called internal resources. The limiting factor for this implementation is the number of internal resources that can be associated with any individual task. OSEK and consequently AUTOSAR limit this number to one internal resource per task. In this work, we investigate the impact of this limitation on the schedulability of task sets when cache related preemption delays are taken into account. We also consider the impact of this restriction on the stack size when the tasks are executed on a shared-stack system.
Download Paper (PDF; Only available from the DATE venue WiFi)

16:00

IP1-18, 637

GPUGUARD: TOWARDS SUPPORTING A PREDICTABLE EXECUTION MODEL FOR HETEROGENEOUS SOC
Speaker:
Björn Forsberg, ETH Zürich, CH
Authors:
Björn Forsberg¹, Andrea Marongiu² and Luca Benini³
¹ETH Zürich, CH; ²Swiss Federal Institute of Technology in Zurich (ETHZ), CH; ³Università di Bologna, IT
Abstract
The deployment of real-time workloads on commercial off-the-shelf (COTS) hardware is attractive, as it reduces the cost and time-to-market of new products. Most modern high-end embedded SoCs rely on a heterogeneous design, coupling a general-purpose multi-core CPU to a massively parallel accelerator, typically a programmable GPU, sharing a single global DRAM. However, because of non-predictable hardware arbiters designed to maximize average or peak performance, it is very difficult to provide timing guarantees on such systems. In this work we present our ongoing work on GPUguard, a software technique that predictably arbitrates main memory usage in heterogeneous SoCs. A prototype implementation for the NVIDIA Tegra TX1 SoC shows that GPUguard is able to reduce the adverse effects of memory sharing, while retaining a high throughput on both the CPU and the accelerator.
Download Paper (PDF; Only available from the DATE venue WiFi)

16:01

IP1-19, 226

A NON-INTRUSIVE, OPERATING SYSTEM INDEPENDENT SPINLOCK PROFILER FOR EMBEDDED MULTICORE SYSTEMS
Speaker:
Lin Li, Infineon Technologies, DE
Authors:
Lin Li¹, Philipp Wagner², Albrecht Mayer¹, Thomas Wild² and Andreas Herkersdorf³
¹Infineon Technologies, DE; ²Technical University of Munich, DE; ³TU München, DE
Abstract
Locks are widely used as a synchronization method to guarantee the mutual exclusion for accesses to shared resources in multi-core embedded systems. They have been studied for years to improve performance, fairness, predictability etc. and a variety of lock implementations optimized for different scenarios have been proposed. In practice, applying an appropriate lock type to a specific scenario is usually based on the developer's hypothesis, which could mismatch the actual situation. A wrong lock type applied may result in lower performance and unfairness. Thus, a lock profiling tool is needed to increase the system transparency and guarantee the proper lock usage. In this paper, an operating-system-independent lock profiling approach is proposed as there are many different operating systems in the embedded field. This approach detects lock acquisition and lock releasing using hardware tracing based on hardware-level spinlock characteristics instead of specific libraries or APIs. The spinlocks are identified automatically; lock profiling statistics can be measured and performance-harmful lock behaviors are detected. With this information, the lock usage can be improved by the software developer. A prototype as a Java tool was implemented to conduct hardware tracing and analyze locks inside applications running on the Infineon AURIX microcontrollers.
Download Paper (PDF; Only available from the DATE venue WiFi)

16:00

End of session
Coffee Break in Exhibition Area

On all conference days (Tuesday to Thursday), coffee and tea will be served during the coffee breaks at the below-mentioned times in the exhibition area.

Tuesday, March 28, 2017