The advent of Software-Defined Vehicles (SDVs) has revolutionized the automotive industry by enabling rapid innovation through the integration of software-driven functionalities. The Scalable Open Architecture for Embedded Edge (SOAFEE) framework, an innovative open software architecture, integrates cloud-native methodologies into in-vehicle environments. By leveraging this framework, the containerization of Robot Operating System (ROS) applications has gained widespread adoption for deploying and maintaining autonomous driving applications. However, real-time performance remains a critical challenge, particularly in addressing end-to-end (E2E) latency within ROS systems to ensure responsiveness and timely task execution. Existing tools, such as the Chain-Aware ROS Evaluation Tool (CARET), have contributed significantly to realtime performance evaluation. Nevertheless, these tools exhibit limitations when assessing E2E latency in containerized environments involving multiple containers. To address this gap, we introduce Distributed ROS Application Performance Profiler (DRAPP), a solution referenced CARET with enhancements, designed specifically to evaluate E2E latency in ROS-based applications. Our approach includes experiments using Autoware, deployed across multiple containers within the SOAFEE framework, with a primary focus on analyzing E2E processing latency. Preliminary empirical results demonstrate that DRAPP outperforms existing tools in both usability and effectiveness for latency evaluation, representing a significant step forward in the performance assessment of in-vehicle software for autonomous systems.

Autonomous machines often encounter complex timing constraints, such as those concerning end-to-end timing guarantees and real-time data fusion, etc. Tasks are often event-triggered or time-triggered at varying rates and exhibit data dependencies in between. Maintaining the real-time performance of autonomous machines becomes a highly challenging endeavor. In this paper, we formulate the workload of an autonomous machine as a hybrid Directed Acyclic Graph (DAG), which contains both time-trigger tasks and event-trigger tasks, with a distinct focus on the task of ensuring timing consistency in data fusion and adherence to end-to-end constraints within the DAG model. We design a concise mechanism to select suitable data received by a node and transmit them to successor nodes. This ensures both the timing disparity—as reflected by the differences in timestamps of the data used for fusion—and the end-to-end latency from the sensor to the controller is confined within a certain boundary. The proposed method is proven to be optimal as it always selects suitable data to guarantee the timing correctness of an autonomous machine as far as it (inherently) has the capacity. Experimental results show that our method can significantly improve the success rate of guaranteeing both timing consistency and end-to-end constraints of the autonomous machine.

Light propagation in underwater scenes is significantly hindered by wavelength- and distance-dependent attenuation and scattering, leading to low contrast and severe color distortion in underwater images. Recent advancements in diffusion models have shown impressive performance in image restoration by learning data distribution prior knowledge (diffusion prior) from large amounts of paired data. However, due to the difficulties in collecting paired underwater images, the available data for underwater image enhancement is limited in both quality and quantity. This scarcity leads to a biased diffusion prior and suboptimal performance of diffusion models. To address this issue, we propose a novel method, termed SeaDiff, to learn underwater diffusion prior with wavelength- and distance-dependent degradation awareness. Specifically, we introduce a Prior Knowledge Mining Model (PKMM), which includes two key components: (1) the Physical Prior Embedding Module (PPEM) that simulates the underwater imaging process through a distance-dependent physical model and embeds physical prior by incorporating generalizable distance-aware cues from a large vision foundation model; and (2) the Color Prior Embedding Module (CPEM) that extracts wavelength-dependent color distribution prior from a log-chroma color space. Additionally, we propose a Degradation-Aware Diffusion Model (DADM) that seamlessly integrates degradation prior with diffusion prior and enhances the underwater images with high visual quality. Extensive experiments on popular UIE benchmarks and downstream tasks demonstrate that the proposed SeaDiff achieves state-of-the-art performance in terms of both visual quality and quantitative metrics. The code will be released at https://github.com/Henry-Bi/SeaDiff.

In autonomous driving (AD) systems, complex data dependencies exist between tasks with different activation rates, making it very hard to analyze the system’s timing behaviors. This paper formulates an AD system as a multi-rate directed acyclic graph (DAG) and introduces a novel reaction time bound for critical chains within this multi-rate DAG. Furthermore, we introduce a priority assignment strategy tailored to optimize priority allocation, effectively minimizing the reaction time of critical task chains. This strategy comes with theoretical guarantees, ensuring that the achieved latency bound is only slightly higher than the ideal one. Our empirical work demonstrates that the newly proposed reaction time bound outperforms current standards, achieving an average improvement of $5.46 \%$. Furthermore, our strategy for priority assignment significantly enhances the success rate of achieving timing correctness in the AD system, exceeding the baseline method by a notable $19.24 \%$.

In the autonomous driving (AD) system, complex data dependencies exist between tasks with different activation rates, making it very hard to analyze systems’ real-time behaviors. This paper formulates the AD system as a multi-rate DAG and proposes an integrated framework to co-analyze the schedulability of individual tasks and the end-to-end latency of task chains in the multi-rate DAG. Integer linear programming (ILP) techniques are developed to guide how to drop redundant workload to increase the chance that timing requirements can be met. This paper proposed one analysis framework which enables an automated process in which designs of the AD system are created, analyzed and refined in an iterative way, i.e., the analysis result in the last iteration provides valuable guidance to redesign the AD system in the next iteration. Experiments are conducted to evaluate the performance of our analysis method.

In recent years, the maturation of modern multicore processor technology and its increasing adoption in critical industrial domains have posed significant challenges for real-time systems, primarily due to contention for shared cache resources and the resulting uncertainty. To address this issue, contemporary processors employ cache partitioning techniques, enhancing temporal predictability by isolating cache access among processor cores. However, this isolation technique may lead to real-time tasks missing their deadlines due to an insufficient number of cache partitions. Consequently, this paper investigates the schedulability of preemptive global Earliest Deadline First (EDF) real-time scheduling algorithms that support dynamic cache allocation. We propose an innovative LAG-based schedulability analysis method for these algorithms and present a utilization-based schedulability condition that reduces analysis time complexity while improving analysis accuracy. Lastly, the performance and efficiency of the proposed schedulability determination method are validated through simulation experiments with randomly generated tasks.

Autonomous machines are commonly subject to real-time constraints. ROS 2, a widely-used robotics framework, considers real-time capabilities as a critical factor and is constantly evolving to address these challenges, e.g., the end-to-end timing guarantee and the real-time data fusion, etc. This paper studies the ROS message synchronizer, an integral component for multi-sensor data fusion, and provides a potential direction for the synchronizer's evolution in future versions of ROS 2. For effective data fusion, input data from different sensors must be sampled at time points that align within a specific range. This paper proposes a novel message synchronization policy to meet this requirement, called the SEAM, which Synchronizes the Earliest Arrival Messages once they fall within the specified range. Unlike traditional ROS synchronizers, the SEAM does not rely on prediction information for complex optimization. Instead, it uses information from already-arrived messages to construct a feasible synchronization scheme. We demonstrate the optimality of the SEAM by proving that it always finds a feasible scheme if one indeed exists. We incorporate the SEAM into ROS 2 and conduct experiments to evaluate its effectiveness compared to traditional ROS synchronizers.

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.

Robot Operating System (ROS) is the most popular framework for developing robotics software. Typically, robotics software is safety-critical and employed in real-time systems requiring timing guarantees. Since the first generation of ROS provides no timing guarantee, the recent release of its second generation, ROS2, is necessary and timely, and has since received immense attention from practitioners and researchers. Unfortunately, the existing analysis of ROS2 showed the peculiar scheduling strategy of ROS2 executor, which severely affects the response time of ROS2 applications. This paper proposes a deadline-based scheduling strategy for the ROS2 executor. It further presents an analysis for an end-to-end response time of ROS2 workload (processing chain) and an evaluation of the proposed scheduling strategy for real workloads.

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.

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 article, 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.

OpenMP is a promising framework for developing parallel real-time software on multi-cores. Recently, many graph-based task models representing realistic features of OpenMP task systems have been proposed and analyzed. However, all previous studies did not model the loop structures, which is common in OpenMP task systems. In this paper, we formulate the workload of OpenMP task systems with loop structures as the cyclic graph model and study how to compute safe upper bounds for the worstcase response time (WCRT). The loop structures combined with the creation of tasks and conditional branches result in a large state space. Simply unrolling the loop and/or enumerating all the possible execution flows would be computationally intractable. As the major technical contribution, we develop a linear-time dynamic programming algorithm to compute the WCRT bound without unrolling loops or explicitly enumerating the execution flows. Experiments with both synthetic task graphs and realistic OpenMP programs are conducted to evaluate the performance of our method.

Multi-cores are becoming mainstream hardware platforms for embedded and real-time systems. To fully utilize the processing capacity of multi-cores, software should be parallelized. Recently, much work has been done on real-time scheduling of parallel tasks modeled as directed acyclic graphs (DAG), motivated by the parallel task structures supported by popular parallel programming frameworks such as OpenMP. The DAG-based task models in existing real-time scheduling research assume well-nested graph structures recursively composed by single-source-single-sink parallel and conditional components. However, realistic OpenMP task systems in general have more flexible structures that do not comply with those assumptions. In this article, we model the behavior of general OpenMP task systems with non-well-nested structures. The worst-case response time analysis problem for such systems is more difficult due to the flexible graph structure. As the major technical contribution, we develop two efficient algorithms to compute the worst-case response time bounds, with different trade-offs between efficiency and precision. Evaluation with both randomly generated task graphs and realistic OpenMP programs shows good performance of our approaches in terms of both precision and efficiency.

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.

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 (SMT) 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.

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 $\mathcal{N}\mathcal{P}$-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.

Challenging scheduling problems arise in the implementation of cyber-physical systems upon heterogeneous platforms with (serial) data offloading and (parallel) computation. In this paper, we adapt techniques from scheduling theory to model, analyze, and derive scheduling algorithms for real-time workloads on such platforms. We characterize the performance of the proposed algorithms, both analytically via the approximation ratio metric and experimentally through simulation experiments upon synthetic workloads that are justified via a case study on a CPU-GPU platform. The evaluation exposes some divergence between the analytical characterization and experimental one; recommendations that seek to balance such divergent characterizations are made regarding the choice of algorithmic approaches.

Utilization bound is a well-known concept in real-time scheduling theory for sequential periodic tasks, which can be used both for quantifying the performance of scheduling algorithms and as efficient schedulability tests. However, the schedulability of parallel real time task graphs depends on not only utilization, but also another parameter tensity, the ratio between the longest path length and period. In this paper, we use utilization-tensity bounds to better characterize the schedulability of parallel real-time tasks. In particular, we derive utilization-tensity bounds for parallel DAG tasks under global EDF scheduling, which facilitate significantly more precise schedulability analysis than the state-of-the-art analysis techniques based on capacity augmentation bound and response time analysis. Moreover, we apply the above results to the federated scheduling paradigm to improve the system schedulability by choosing proper scheduling strategies for tasks with different workload and structure features.

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.

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.

The demand bound function (DBF) is a powerful abstraction to analyze the feasibility/schedulability of real-time tasks. Computing the DBF for expressive system models, such as graph-based tasks, is typically very expensive. In this article, we develop new techniques to drastically improve the DBF computation efficiency for a representative graph-based task model, digraph real-time tasks (DRT). First, we apply the well-known quick processor-demand analysis (QPA) technique, which was originally designed for simple sporadic tasks, to the analysis of DRT. The challenge is that existing analysis techniques of DRT have to compute the demand for each possible interval size, which is contradictory to the idea of QPA that aims to aggressively skip the computation for most interval sizes. To solve this problem, we develop a novel integer linear programming (ILP)-based analysis technique for DRT, to which we can apply QPA to significantly improve the analysis efficiency. Second, we improve the task utilization computation (a major step in DBF computation for DRT) efficiency from pseudo-polynomial complexity to polynomial complexity. Experiments show that our approach can improve the analysis efficiency by dozens of times.

Synchronous parallel tasks are widely used in HPC for purchasing high average performance, but merely consider how to guarantee good timing predictabilities. OpenMP is a promising framework for multi-core real-time embedded systems. The synchronous OpenMP tasks are significantly more difficult to schedule and analyze due to constraints posed by OpenMP specifications. An important OpenMP feature is tied task, which must execute on the same thread during the whole life cycle. This paper designs a novel method, called group scheduling, to schedule synchronous OpenMP tasks, which divides tasks into several groups, and assigns some of them to dedicated cores, in order to isolate tied tasks. We derive a linear-time computable response time bound. Experiments with both randomly generated and realistic OpenMP tasks show that our new bound significantly outperforms the existing bound.

Existing DAG-based task models in real-time scheduling research assume well-nested structures recursively composed by single-source-single-sink parallel and conditional components. However, realistic OpenMP task systems in general have more flexible structures that do not comply with this assumption. In this paper, we model the behaviors of general OpenMP task systems with non-well-nested branching structures and study the problem of how to bound their worst-case response times (WCRT). A naive solution is to apply the established WCRT bound for DAG tasks without conditional branches to the exponentially many possible execution flows, which has exponential time complexity. In this paper, we develop a linear-time algorithm to efficiently calculate WCRT bounds for OpenMP task systems with non-well-nested branching structures. Experiments with both synthetic task graphs and realistic OpenMP programs are conducted to evaluate the performance of our method.

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.

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.

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.

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.

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.