| 1. |
- Jiang, Xu, et al.
(författare)
-
Semi-Federated Scheduling of Parallel Real-Time Tasks on Multiprocessors
- 2017
-
Ingår i: 2017 IEEE Real-Time Systems Symposium (RTSS). - : IEEE. - 9781538614143 ; , s. 80-91
-
Konferensbidrag (refereegranskat)abstract
- Federated scheduling is a promising approach to schedule parallel real-time tasks on multi-cores, where each heavy task exclusively executes on a number of dedicated processors, while light tasks are treated as sequential sporadic tasks and share the remaining processors. However, federated scheduling suffers resource waste since a heavy task with processing capacity requirement x + is an element of (where x is an integer and 0 < is an element of < 1) needs x+ 1 dedicated processors. In the extreme case, almost half of the processing capacity is wasted. In this paper we propose the semi-federate scheduling approach, which only grants x dedicated processors to a heavy task with processing capacity requirement x+ is an element of, and schedules the remaining is an element of part together with light tasks on shared processors. Experiments with randomly generated task sets show the semi-federated scheduling approach significantly outperforms not only federated scheduling, but also all existing approaches for scheduling parallel real-time tasks on multi-cores.
|
|
| 2. |
- Joshi, Prachi, et al.
(författare)
-
Offset Assignment to Signals for Improving Frame Packing in CAN-FD
- 2017
-
Ingår i: 2017 IEEE REAL-TIME SYSTEMS SYMPOSIUM (RTSS). - : IEEE. - 9781538614143 ; , s. 167-177
-
Konferensbidrag (refereegranskat)abstract
- Controller Area Network (CAN) is a widely used protocol that allows communication among Electronic Control Units (ECUs) in automotive electronics. It was extended to CAN-FD (CAN with Flexible Data-rate) to meet the increasing demand for bandwidth utilization caused by the growing number of features in modern automobiles. The signal-to-frame packing problem has been studied in literature for both CAN and CAN-FD. In this work, we propose and formulate, for the first time, the signal offset assignment problem (SOAP) in a frame in order to improve the bus bandwidth utilization. We prove that SOAP is NP-complete. We propose a general approximation framework (GAF) for SOAP which can use any approximation algorithm for the makespan minimization problem (MMP) in multiprocessor systems. We derive the performance guarantee provided by GAF as a function of the performance guarantee of the approximation algorithm for MMP and the number of signal periods in the frame. We demonstrate the efficacy of our approach through experiments using three different algorithms (two approximation algorithms and an integer linear programming formulation) for MMP in GAF. Our results indicate that by using offsets for signals in frame packing schemes, one can achieve about 10.54% improvement in bandwidth utilization (on a single bus) in CAN-FD systems.
|
|
| 3. |
- Specht, Johannes, et al.
(författare)
-
Synthesis of Queue and Priority Assignment for Asynchronous Traffic Shaping in Switched Ethernet
- 2017
-
Ingår i: 2017 IEEE REAL-TIME SYSTEMS SYMPOSIUM (RTSS). - : IEEE. - 9781538614143 ; , s. 178-187
-
Konferensbidrag (refereegranskat)abstract
- Real-time switched Ethernet communication is of increasing importance in many cyber-physical and embedded systems application areas such as automotive electronics, avionics, and industrial control. The IEEE 802.1 Time-Sensitive Networking (TSN) task group develops standards for real-time Ethernet, for example a time-triggered traffic class (IEEE 802.1Qbv-2015). New application areas, such as active safety and autonomous driving using radar, lidar, and camera sensors, which do not fall into the strictly periodic, time-triggered communication model, require a flexible traffic class that can accommodate various communication models while still providing hard real-time guarantees. In our previous work, we developed such a traffic class, Urgency-Based Scheduler (UBS), and its worst-case latency analysis. UBS is currently under standardization (P802.1Qcr) in the TSN task group. In this paper, we introduce and solve the UBS synthesis problem of assigning hard real-time data flows to queues and priority levels to queues, the main parameters that determine communication latencies. The synthesis problem is particularly challenging due to the flexibility offered by UBS to aggregate flows and assign individual priority levels per network hop. We present an SMT approach, a cluster-based heuristic, and an extensive experimental evaluation.
|
|
| 4. |
- Sun, Jinghao, et al.
(författare)
-
Real-Time Scheduling and Analysis of OpenMP Task Systems with Tied Tasks
- 2017
-
Ingår i: 2017 IEEE Real-Time Systems Symposium (RTSS). - : IEEE. - 9781538614143 ; , s. 92-103
-
Konferensbidrag (refereegranskat)abstract
- OpenMP is a promising framework for developing parallel real-time software on multi-cores. Although similar to the DAG task model, OpenMP task systems are significantly more difficult to analyze due to constraints posed by the OpenMP specification. An important feature in OpenMP is tied tasks, which must execute on the same thread during the whole life cycle. Although tied tasks enjoy benefits in simplicity and efficiency, it was considered to be not suitable to real-time systems due to its complex behavior. In this paper, we study the real-time scheduling and analysis of OpenMP task systems with tied tasks. First, we show that under the existing scheduling algorithms in OpenMP, tied tasks indeed may lead to extremely bad timing behaviors where the parallel workload is sequentially executed completely. To solve this problem, we proposed a new scheduling algorithm and developed two response time bounds for it, with different trade-off between simplicity and analysis precision. Experiments with both randomly generated OpenMP task systems and realistic OpenMP programs show that the response time bounds obtained by our approach for tied task systems are very close to that of untied tasks.
|
|
| 5. |
- Tang, Yue, et al.
(författare)
-
Revisiting GPC and AND Connector in Real-Time Calculus
- 2017
-
Ingår i: 2017 IEEE Real-Time Systems Symposium (RTSS). - : IEEE. - 9781538614143 ; , s. 255-265
-
Konferensbidrag (refereegranskat)abstract
- Real-Time Calculus (RTC) is a powerful framework for modeling and worst-case performance analysis of networked systems. GPC and AND are two fundamental components in RTC, which model priority-based resource arbitration and synchronization operations, respectively. In this paper, we revisit GPC and AND. For GPC, we develop tighter output arrival curves to more precisely characterize the output event streams. For AND, we first identify a problem in the existing analysis method that may lead to negative values in the output curves, and present corrections to the problem. Then we generalize AND to synchronize more than two input event streams. We implement our new theoretical results and conduct experiments to evaluate their performance. Experiment results show significant improvement of our new methods in analysis precision and efficiency.
|
|
