Parallel execution and conditional execution are increasingly prevalent in modern embedded systems. In real-time scheduling, a fundamental problem is how to upper-bound the response times of a task. Recent work applied the multi-path technique to reduce the response time bound for tasks with parallel execution, but left tasks with conditional execution as an open problem. This paper focuses on upper-bounding response times for tasks with both parallel execution and conditional execution using the multi-path technique. By designing a delicate abstraction regarding the multiple paths of various conditional branches, we derive a new response time bound. We further apply this response time bound into the scheduling of multiple parallel tasks with conditional branches. Experiments demonstrate that the proposed bound significantly advances the state-of-the-art, reducing the response time bound by 9.4% and improving the schedulability by 31.2% on average.

This article studies the response time bound of a directed acyclic graph (DAG) task. Recently, the idea of using multiple paths to bound the response time of a DAG task, instead of using a single longest path in previous results, was proposed and led to the so-called multipath bound. Multipath bounds can greatly reduce the response time bound and significantly improve the schedulability of DAG tasks. This article derives a new multipath bound and proposes an optimal algorithm to compute this bound. We further present a systematic analysis on the dominance and the sustainability of three existing multipath bounds and the proposed multipath bound. Our bound theoretically dominates and empirically outperforms all existing multipath bounds. What is more, the proposed bound is the only multipath bound that is proved to be self-sustainable.

Abstract This paper considers the real-time scheduling of a parallel task with reclaiming computing resources, which can be utilized for soft real-time tasks or switching to low-energy mode to save energy. Existing works allocate a rectangular piece of computing resources based on the worst-case characterizations of the task to guarantee the deadline, which inherently incurs severe resource wasting due to coarse-grained resource allocation. To address this resource-wasting problem, this paper proposes the ladder-like resource allocation (i.e., a series of rectangular pieces of computing resources). To characterize the ladder-like resource allocation, we present two concepts called resource distribution and allocation vector, which serve as the interfaces between hard and soft real-time tasks. For the former, we derive schedulability tests under the given two interfaces; for the latter, we discuss the methods of determining the two interfaces to reclaim computing resources. This paper is the first work to fully explore the concept of ladder-like resource allocation and its potential consequences on computing resources, soft real-time tasks, and energy. Experiments demonstrate that the proposed approach can effectively reclaim more computing resources than existing approaches while maintaining hard real-time guarantees.

DAG (directed acyclic graph) tasks are widely used to model parallel real-time workload. The real-time performance of a DAG task not only depends on its total workload, but also its graph structure. Intuitively, with the same total workload, a DAG task with looser precedence constraints tends to have better real-time performance in terms of worst-case response time. However, this paper shows that actually we can shorten the worst-case response time of a DAG task by carefully adding new edges and constructing longer paths. We develop techniques based on the state-of-the-art DAG response time analysis methods to properly add new edges so that the worst-case response time bound guaranteed by formal analysis can be significantly reduced. An approach built upon the proposed techniques is also presented to handle the scheduling of multiple DAG tasks. Experiments under different parameter settings demonstrate the effectiveness of the proposed method.

There is an increasing move towards implementing embedded real-time systems upon multiprocessors with parallel applications, which are usually modeled as Directed Acyclic Graphs (DAGs). Plentiful work has been presented to optimize the bound of Worst-Case Response Time (WCRT) since the cornerstone work proposed by Graham in 1969. However, all these works are developed on the basis of Graham’s bound and failed to tackle the root of pessimism in it. In this work, we present a novel method to optimize the WCRT bound of a DAG task by designing mutually exclusive groups so that a sequential execution is enforced for some nodes, under which the problem of bounding WCRT becomes a problem of identifying a mutually exclusive path and thus does not suffer the pessimism in Graham’s bound. Experiments are conducted to evaluate the performance of our method against other WCRT optimization approaches in the state-of-the-art.

Real-time scheduling and analysis of parallel tasks modeled as directed acyclic graphs (DAG) have been intensively studied in recent years. The degree of parallelism of DAG tasks is an important characterization in scheduling. This paper revisits the definition and the computing algorithms for the degree of parallelism of DAG tasks, and clarifies some misunderstandings regarding the degree of parallelism which exist in real-time literature. Based on the degree of the parallelism, we propose a real-time scheduling approach for DAG tasks, which is quite simple but rather effective and outperforms the state-of-the-art by a considerable margin.

Heterogeneous multi-core platforms have been used in many fields to meet the increasing requirement of computation. In this paper, we study the response time bound of typed DAG (directed acyclic graph) tasks on heterogeneous multi-core platforms. The existing bound has exponential time complexity. In this paper, we propose a new bound that can be computed with complexity$O(\vert V\vert +\vert E\vert)$and is only slightly larger than the state-of-the-art. Experiments demonstrate that the computation of our bound is significantly more efficient than the existing bound and our bound has almost the same tightness as the existing bound.

The conditional directed acyclic graph (DAG) task model can represent the conditional execution flows that commonly exist in many real-time parallel applications. Previous work has shown that by properly assigning the priority among vertices inside a nonconditional DAG task, we can reduce the task response time and achieve better system schedulability. This article studies how to apply intra-task priority assignment to conditional DAG tasks. We develop a response time bound that theoretically dominates the state-of-the-art and present a novel algorithm to compute the bound in polynomial time. We further extend the proposed approach to the general setting of multiple conditional DAG tasks. Experiments with one conditional DAG task and multiple conditional DAG tasks demonstrate that our method consistently outperforms the state-of-the-art by a considerable margin.

Directed acyclic graph (DAG) becomes a popular model for modern real-time embedded software. It is really a challenge to bound the worst-case response time (WCRT) of DAG task. Parallelism, dependencies and mutual exclusion become three of the most critical properties of real-time parallel tasks. Recent work applied prioritizing techniques to reduce DAG task's WCRT bound, which has well studied the first two properties, i.e., parallelism and dependencies, but leaves the mutually exclusive property as an open problem. This paper focuses on all the three properties of real-time parallel software, and investigates how to estimate the WCRT of the DAG task model with mutually exclusive vertices and under prioritized list scheduling algorithms. We derive a reasonable WCRT bound for such a complicated DAG task, and prove that the corresponding WCRT bound computation problem is strongly NP-hard. It means that there are no pseudo-polynomial time algorithms to compute the WCRT bound. For the prioritized DAG with a constant number of mutual exclusive vertices, we develop a dynamic programming algorithm that is able to estimate the WCRT bound within pseudo-polynomial time. Experiments are conducted to evaluate the performance of our analysis method implemented with different priority assignment policies against the state-of-the-art.

In 1969, Graham developed a well-known response time bound for a DAG task using the total workload and the longest path of the DAG, which has been widely applied to solve many scheduling and analysis problems of DAG-based task systems. This paper presents a new response time bound for a DAG task using the total workload and the lengths of multiple long paths of the DAG, instead of the longest path in Graham's bound. Our new bound theoretically dominates and empirically outperforms Graham's bound. We further extend the proposed approach to multi-DAG task systems. Our schedulability test theoretically dominates federated scheduling and outperforms the state-of-the-art by a considerable margin.

In order to be deployed on storage-limited devices, blockchains generally provide lightweight clients which only store all the block headers rather than all blocks. However, a lightweight client is hard to verify a newly issued transaction, thus making the zero-confirmation transactions between lightweight clients impossible. In particular, transaction verification needs to verify that each referred output of the transaction is not previously spent. The conventional lightweight client design is unscalable as it can only support such an operation in the complexity of$O$($N_{T}$), where$N_{T}$is the total number of transactions in the system. The latest proposals suggest summarizing all the unspent outputs in an ordered Merkle tree. Therefore, a light client can request proof of presence and/or absence of an element in it to prove whether a referred output is previously spent or not, in the complexity of$O$(log($N_{U}$)), where$N_{U}$is the total number of unspent output in the system. However, updating such ordered Merkle tree is slow, thus making the system impractical—by our evaluation, when a new block is generated in Bitcoin, it takes more than one minute to update the ordered Merkle tree. We propose a practical client, TICK, to solve this problem. TICK uses the AVL hash tree to store all the unspent outputs. The AVL hash tree can be updated in the time of$O$($M$*log($N_{U}$)), where$M$is the number of elements that need to be inserted or removed from the AVL hash tree. By evaluation, when a new block is generated, the AVL hash tree can be updated within 1 s. Similarly, the proof can also be generated in the time of$O$(log($N_{U}$)). Therefore,${\textsf {TICK}}$is practical and scalable. Benefited by the AVL hash tree, a storage-limited device can efficiently and cryptographically verify transactions. In addition, rather than requiring new miners to download the entire blockchain before mining, TICK allows new miners to download only a small portion of data to start mining. We implement TICK for Bitcoin and provide an experimental evaluation on its performance by using the current Bitcoin blockchain data. Our result shows that the proof for verifying whether an output of a transaction is spent or not is only several kB. The verification is very fast—generating a proof generally takes less than 1 ms and verifying a proof even takes much less time. In addition, to start mining, new miners only need to download several GB data, rather than downloading over 230-GB data.

It becomes more and more common for people to have multiple mobile devices. This opens the opportunity of multi-surface computing in which users interact with an app using multiple devices simultaneously. Recently, a system called FLUID was developed, which can distribute User Interface (UI) elements of an app to multiple devices to support multi-surface computing. FLUID enables general, flexible and transparent multi-device interaction, which cannot be achieved by previous approaches such as screen mirroring, app migration, and customized app development on multiple devices. However, the practicality of FLUID is still severely limited because it requires that (1) the app source codes must be available and (2) the same app is pre-installed on all devices. This paper presents PRUID, a UI distribution system that is free from the above-mentioned limitations of FLUID. PRUID captures and extracts relevant information about UI elements to be distributed completely at run time, without requiring the app source code. An app-independent UI agent is designed to dock and render the UI components distributed to the guest device, so pre-installation of the app on guest devices is not required. We developed representative use cases to demonstrate the usage and evaluate the performance of PRUID. The evaluation results show that the extra overhead incurred due to the UI information extraction at run time is marginal and PRUID provides a smooth user experience.

Most parallel real-time applications can be modeled as directed acyclic graph (DAG) tasks. Intra-task priority assignment can reduce the nondeterminism of runtime behavior of DAG tasks, possibly resulting in a smaller worst-case response time. However, intra-task priority assignment incurs dependencies between different parts of the graph, making it a challenging problem to compute the response time bound. Existing work on intra-task task priority assignment for DAG tasks is subject to the constraint that priority assignment must comply with the topological order of the graph, so that the response time bound can be computed in polynomial time. In this paper, we relax this constraint and propose a new method to compute response time bound of DAG tasks with arbitrary priority assignment. With the benefit of our new method, we present a simple but effective priority assignment policy, leading to smaller response time bounds. Comprehensive evaluation with both single-DAG systems and multi-DAG systems demonstrates that our method outperforms the state-of-the-art method with a considerable margin.

In this paper, we propose a novel approach to schedule conditional DAG parallel tasks, with which we can derive safe response time upper bounds significantly better than the state-of-the-art counterparts. The main idea is to eliminate the notorious timing anomaly in scheduling parallel tasks by enforcing certain order constraints among the vertices, and thus the response time bound can be accurately predicted off-line by somehow “simulating” the runtime scheduling. A key challenge to apply the timing-anomaly free scheduling approach to conditional DAG parallel tasks is that at runtime it may generate exponentially many instances from a conditional DAG structure. To deal with this problem, we develop effective abstractions, based on which a safe response time upper bound is computed in polynomial time. We also develop algorithms to explore the vertex orders to shorten the response time bound. The effectiveness of the proposed approach is evaluated by experiments with randomly generated DAG tasks with different parameter configurations.

Heterogenerous multi-cores utilize the strength of different architectures for executing particular types of workload, and usually offer higher performance and energy efficiency. In this paper, we study the worst-case response time (WCRT) analysis of typed scheduling of parallel DAG tasks on heterogeneous multi-cores, where the workload of each vertex in the DAG is only allowed to execute on a particular type of cores. The only known WCRT bound for this problem is grossly pessimistic and suffers the non-self-sustainability problem. In this paper, we propose two new WCRT bounds. The first new bound has the same time complexity as the existing bound, but is more precise and solves its non-self-sustainability problem. The second new bound explores more detailed task graph structure information to greatly improve the precision, but is computationally more expensive. We prove that the problem of computing the second bound is strongly NP-hard if the number of types in the system is a variable, and develop an efficient algorithm which has polynomial time complexity if the number of types is a constant. Experiments with randomly generated workload show that our proposed new methods are more precise than the existing bound while having good scalability.

Real-time scheduling and analysis of parallel tasks modeled as directed acyclic graphs (DAG) have been intensively studied in recent years. However, no existing work has explored the execution order of eligible vertices within a DAG task. In this paper, we show that this intra-task vertex execution order has a large impact on system schedulability and propose to control the execution order by vertex-level priority assignment. We develop analysis techniques to bound the worst-case response time for the proposed scheduling strategy and design heuristics for proper priority assignment to improve system schedulability as much as possible. We further extend the proposed approach to the general setting of multiple recurrent DAG tasks. Experiments with both realistic parallel benchmark applications and randomly generated workload show that our method consistently outperforms state-of-the-art methods with different task graph structures and parameter configurations.

Heterogenerous multi-cores utilize the strength of different architectures for executing particular types of workload, and usually offer higher performance and energy efficiency. In this paper, we study the worst-case response time (WCRT) analysis of typed scheduling of parallel DAG tasks on heterogeneous multi-cores, where the workload of each vertex in the DAG is only allowed to execute on a particular type of cores. The only known WCRT bound for this problem is grossly pessimistic and suffers the non-self-sustainability problem. In this paper, we propose two new WCRT bounds. The first new bound has the same time complexity as the existing bound, but is more precise and solves its non-self-sustainability problem. The second new bound explores more detailed task graph structure information to greatly improve the precision, but is computationally more expensive. We prove that the problem of computing the second bound is strongly NP-hard if the number of types in the system is a variable, and develop an efficient algorithm which has polynomial time complexity if the number of types is a constant. Experiments with randomly generated workload show that our proposed new methods are significantly more precise than the existing bound while having good scalability.

Mixed-criticality models are an emerging paradigm for the design of real-time systems because of their significantly improved resource efficiency. However, formal mixed-criticality models have traditionally been characterized by two impractical assumptions: once any high-criticality task overruns, all low-criticality tasks are suspended and all other high-criticality tasks are assumed to exhibit high-criticality behaviors at the same time. In this paper, we propose a more realistic mixed-criticality model, called the flexible mixed-criticality (FMC) model, in which these two issues are addressed in a combined manner. In this new model, only the overrun task itself is assumed to exhibit high-criticality behavior, while other high-criticality tasks remain in the same mode as before. The guaranteed service levels of low-criticality tasks are gracefully degraded with the overruns of high-criticality tasks. We derive a utilization-based technique to analyze the schedulability of this new mixed-criticality model under EDF-VD scheduling. During run time, the proposed test condition serves an important criterion for dynamic service level tuning, by means of which the maximum available execution budget for low-criticality tasks can be directly determined with minimal overhead while guaranteeing mixed-criticality schedulability. Experiments demonstrate the effectiveness of the FMC scheme compared with state-of-the-art techniques.

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.

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 realtime 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.