| 1. |
- Chang, Shuangshuang, et al.
(author)
-
Towards minimum WCRT bound for DAG tasks under prioritized list scheduling algorithms
- 2022
-
In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - : IEEE. - 0278-0070 .- 1937-4151. ; 41:11, s. 3874-3885
-
Journal article (peer-reviewed)abstract
- Many modern real-time parallel applications can be modeled as a directed acyclic graph (DAG) task. Recent studies show that the worst-case response time (WCRT) bound of a DAG task can be significantly reduced when the execution order of the vertices is determined by the priority assigned to each vertex of the DAG. How to obtain the optimal vertex priority assignment, and how far from the best-known WCRT bound of a DAG task to the minimum WCRT bound are still open problems. In this paper, we aim to construct the optimal vertex priority assignment and derive the minimum WCRT bound for the DAG task. We encode the priority assignment problem into an integer linear programming (ILP) formulation. To solve the ILP model efficiently, we do not involve all variables or constraints. Instead, we solve the ILP model iteratively, i.e., we initially solve the ILP model with only a few primary variables and constraints, and then at each iteration, we increment the ILP model with the variables and constraints which are more likely to derive the optimal priority assignment. Experimental work shows that our method is capable of solving the ILP model optimally without involving too many variables or constraints, e.g., for instances with 50 vertices, we find the optimal priority assignment by involving 12.67% variables on average and within several minutes on average.
|
|
| 2. |
- Sun, Jinghao, et al.
(author)
-
A Capacity Augmentation Bound for Real-Time Constrained-Deadline Parallel Tasks Under GEDF
- 2018
-
In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 0278-0070 .- 1937-4151. ; 37:11, s. 2200-2211
-
Journal article (peer-reviewed)abstract
- Capacity augmentation bound is a widely used quantitative metric in theoretical studies of schedulability analysis for directed acyclic graph (DAG) parallel real-time tasks, which not only quantifies the suboptimality of the scheduling algorithms, but also serves as a simple linear-time schedulability test. Earlier studies on capacity augmentation bounds of the sporadic DAG task model were either restricted to a single DAG task or a set of tasks with implicit deadlines. In this paper, we consider parallel tasks with constrained deadlines under global earliest deadline first policy. We first show that it is impossible to obtain a constant bound for our problem setting, and derive both lower and upper bounds of the capacity augmentation bound as a function with respect to the maximum ratio of task period to deadline. Our upper bound is at most 1.47 times larger than the optimal one. We conduct experiments to compare the acceptance ratio of our capacity augmentation bound with the existing schedulability test also having linear-time complexity. The results show that our capacity augmentation bound significantly outperforms the existing linear-time schedulability test under different parameter settings.
|
|
| 3. |
- Sun, Jinghao, et al.
(author)
-
Capacity Augmentation Function for Real-Time Parallel Tasks With Constrained Deadlines Under GEDF Scheduling
- 2020
-
In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - : Institute of Electrical and Electronics Engineers (IEEE). - 0278-0070 .- 1937-4151. ; 39:12, s. 4537-4548
-
Journal article (peer-reviewed)abstract
- Capacity augmentation bound (CAB) is a widely used quantitative metric in theoretical analysis for directed acyclic graph (DAG) parallel real-time tasks, which reveals the key factors the schedulability of DAG tasks heavily depending on: the normalized utilization (the ratio of the total utilization to the core numbers) and the tensity (the maximum ratio of task's longest path length to task's deadline). However, CAB requires both factors of a schedulable task system to be capped by the same threshold. A task system with a normalized utilization slightly larger than that threshold but very small tensity, or very smaller normalized utilization but slightly larger than that threshold has good chance to be scheduled are both denied by CAB. To this end, we propose a new concept called capacity augmentation function (CAF) to better characterize the schedulability of parallel real-time tasks, which provides a more loose and different threshold for both factors. In particular, we derive a CAF-based linear-time schedulability test for real-time constrained-deadline DAG tasks under global EDF, which entirely dominates the state-of-the-art CAB-based test for constrained-deadline settings. Finally, we conduct experiments to compare the acceptance ratio of our CAF-based test with the existing schedulability tests also having linear-time complexity. The results show that CAF-based test significantly outperforms the existing linear-time schedulability test under different parameter settings.
|
|
| 4. |
- Sun, Jinghao, et al.
(author)
-
Feasibility of fork-join real-time task graph models : Hardness and algorithms
- 2016
-
In: ACM Transactions on Embedded Computing Systems. - : Association for Computing Machinery (ACM). - 1539-9087 .- 1558-3465. ; 15:1
-
Journal article (peer-reviewed)abstract
- In the formal analysis of real-time systems, modeling of branching codes and modeling of intratask parallelism structures are two of the most important research topics. These two real-time properties are combined, resulting in the fork-join real-time task (FJRT) model, which extends the digraph-based task model with forking and joining semantics. We prove that the EDF schedulability problem on a preemptive uniprocessor for the FJRT model is coNP-hard in the strong sense, even if the utilization of the task system is bounded by a constant strictly less than 1. Then, we show that the problem becomes tractable with some slight structural restrictions on parallel sections, for which we propose an exact schedulability test with pseudo-polynomial time complexity. Our results thus establish a borderline between the tractable and intractable FJRT models.
|
|
| 5. |
- Sun, Jinghao, et al.
(author)
-
On Computing Exact WCRT for DAG Tasks
- 2020
-
In: 57th ACM/IEEE Design Automation Conference, DAC 2020, San Francisco, CA, USA, July 20-24, 2020. - : IEEE. - 9781728110851 ; , s. 1-6
-
Conference paper (peer-reviewed)abstract
- Most current real-time parallel applications can be modeled as a directed acyclic graph (DAG) task. Existing worst-case response time (WCRT) bounds (e.g., Graham's bound) derived for DAGs may be very pessimistic. No one precisely knows the gap between the WCRT bound and the actual WCRT. In this paper, we aim to derive the exact WCRT of a DAG task under the list scheduling upon multi-core platforms. We encode the WCRT analysis problem into a satisfaction modular theoretical (SNIT) formulation based on insights into the list scheduling algorithm, and prove that our SMT program can solve the WCRT precisely, providing an accurate baseline to measure the tightness of the existing WCRT bounds. Experiments show that our method significantly improves the tightness of the WCRT bound, and is practically quite efficient, e.g., it can analyze DAGs with more than 40 vertices in a few seconds.
|
|
| 6. |
- Sun, Jinghao, et al.
(author)
-
On the Volume Calculation for Conditional DAG Tasks : Hardness and Algorithms
- 2020
-
In: PROCEEDINGS OF THE 2020 DESIGN, AUTOMATION & TEST IN EUROPE CONFERENCE & EXHIBITION (DATE 2020). - NEW YORK, USA. - 9783981926347 ; , s. 204-209
-
Conference paper (peer-reviewed)abstract
- The hardness of analyzing conditional directed acyclic graph (DAG) tasks remains unknown so far. For example, previous researches asserted that the conditional DAG's volume can be solved in polynomial time. However, these researches all assume well-nested structures that are recursively composed by single-source-single-sink parallel and conditional components. For conditional DAGs in general that do not comply with this assumption, the hardness and algorithms of volume computation are still open. In this paper, we construct counterexamples to show that previous work cannot provide a safe upper bound of the conditional DAG's volume in general. Moreover, we prove that the volume computation problem for conditional DAGs is strongly NP-hard. Finally, we propose an exact algorithm for computing the conditional DAG's volume. Experiments show that our method can significantly improve the accuracy of the conditional DAG's volume estimation.
|
|
| 7. |
- Sun, Jinghao, et al.
(author)
-
Real-Time Scheduling and Analysis of OpenMP DAG Tasks Supporting Nested Parallelism
- 2020
-
In: IEEE Transactions on Computers. - : IEEE COMPUTER SOC. - 0018-9340 .- 1557-9956. ; 69:9, s. 1335-1348
-
Journal article (peer-reviewed)abstract
- OpenMP is a promising framework to develop 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 OpenMP specifications. One of the most interesting features in OpenMP is the support for nested parallelism, enjoying benefits in enhancing performance transparency of parallel libraries and promoting reuse of black-box code. Previous researches on DAG task scheduling mainly restrict to only one level of parallelism. The problem whether OpenMP tasks with multiple levels of parallelism are suitable to real-time systems remains open. In this paper, we study the real-time scheduling and analysis of OpenMP task systems supporting nested parallelism. First, we show that under existing scheduling algorithms in OpenMP implementations, nested parallelism indeed may lead to extremely bad timing behaviors where the parallel workload is sequentially executed completely. To solve this problem, we propose a new scheduling algorithm and develop two sound response time bounds by considering the trade-off between simplicity and analysis precision. Experiments demonstrate the efficiency of our methods.
|
|
| 8. |
- Sun, Jinghao, et al.
(author)
-
Real-Time Scheduling and Analysis of OpenMP Task Systems with Tied Tasks
- 2017
-
In: 2017 IEEE Real-Time Systems Symposium (RTSS). - : IEEE. - 9781538614143 ; , s. 92-103
-
Conference paper (peer-reviewed)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.
|
|
| 9. |
- Sun, Jinghao, et al.
(author)
-
Schedulability Analysis for Timed Automata With Tasks
- 2021
-
In: ACM Transactions on Embedded Computing Systems. - : Association for Computing Machinery (ACM). - 1539-9087 .- 1558-3465. ; 20:5s
-
Journal article (peer-reviewed)abstract
- Research on modeling and analysis of real-time computing systems has been done in two areas, model checking and real-time scheduling theory. In model checking, an expressive modeling formalism such as timed automata (TA) is used to model complex systems, but the analysis is typically very expensive due to state-space explosion. In real-time scheduling theory, the analysis techniques are highly efficient, but the models are often restrictive. In this paper, we aim to exploit the possibility of applying efficient analysis techniques rooted in real-time scheduling theory to analysis of real-time task systems modeled by timed automata with tasks (TAT). More specifically, we develop efficient techniques to analyze the feasibility of TAT-based task models (i.e., whether all tasks can meet their deadlines on single-processor) using demand bound functions (DBF), a widely used workload abstraction in real-time scheduling theory. Our proposed analysis method has a pseudo-polynomial time complexity if the number of clocks used to model each task is bounded by a constant, which is much lower than the exponential complexity of the traditional model-checking based analysis approach (also assuming the number of clocks is bounded by a constant). We apply dynamic programming techniques to implement the DBF-based analysis framework, and propose state space pruning techniques to accelerate the analysis process. Experimental results show that our DBF-based method can analyze a TAT system with 50 tasks within a few minutes, which significantly outperforms the state-of-the-art TAT-based schedulability analysis tool TIMES.
|
|
| 10. |
- Wang, Yang, et al.
(author)
-
Benchmarking OpenMP Programs for Real-Time Scheduling
- 2017
-
In: 2017 IEEE 23Rd International Conference On Embedded And Real-Time Computing Systems And Applications (RTSCA). - : IEEE Computer Society. - 9781538618981
-
Conference paper (peer-reviewed)abstract
- Real-time systems are shifting from single-core to multi-core processors. Software must be parallelized to fully utilize the computation power of multi-core architecture. OpenMP is a popular parallel programming framework in general and high-performance computing, and recently has drawn a lot of interests in embedded and real-time computing. Much recent work has been done on real-time scheduling of OpenMP-based parallel workload. However, these studies conduct evaluations with randomly generated task systems, which cannot well represent the structure features of OpenMP workload. This paper presents a benchmark suite, ompTGB, to support research on real-time scheduling of OpenMP-based parallel tasks. ompTGB does not only collect realistic OpenMP programs, but also models them into task graphs so that the real-time scheduling researchers can easily understand and use them. We also present a new response time bound for a subset of OpenMP programs and use it to demonstrate the usage of ompTGB.
|
|
