DAG-Order: An Order-Based Dynamic DAG Scheduling for Real-Time Networks-on-Chip

This article considers a single task modeled as a DAG, which is a general setup in many fields (e.g., autonomous vehicles, industrial automation). Such a task can be represented by a computation-communication graph \(G\) = (V, E), where \(V = \lbrace v_1, v_2, \ldots , v_n\rbrace\) is a set of vertices (corresponding to computation workload) denoted by rectangles, and \(E \subseteq V \times V\) is a set of directed edges (corresponding to communication workload), shown in Figure 1. Each vertex \(v_i\) of \(G\) represents a segment of program (called subtask), and the number inside the vertex denotes the WCET \(c_i\) of the corresponding subtask. As for each directed communication edge \(m_{i,j} \in E\), it represents the data dependence between subtasks \(v_i\) and \(v_j\), and it has an associated worst-case message size also denoted by \(m_{i,j}\). The unit of this message is a flit [15] (i.e., NoC link width). To granularly consider the influence of shared cache/memory in NoCs, the DAG task model should be extended. Specifically, before and after task computation, the communication workloads from/to shared caches and memory banks (if local cache misses in the worst case) can be abstracted as a directed communication edge, whereas a memory-related access operation can be abstracted as a “computation” vertex into the DAG task model. Besides, we only consider a single DAG task with no conditional structures (e.g., switch-case statement). The frequent notations¹ used are summarized in Table 1.

The DAG task \(G\) is assigned a cluster of dedicated NoC by using federated scheduling [3], which is an effective method to provide theoretically and empirically guaranteed real-time services. The minimum NoC cluster is chosen from the whole platform until the deadline can be guaranteed. A subtask/message is assumed to be scheduled in a non-preemptive manner. Note that to reduce the transmission latency of each message, the processing cores communicate by using the message-passing communication paradigm like that of some commercial NoC products (e.g., Arteris FlexNoC and SonicsGN) instead of the shared-memory paradigm. In other words, the message is sent/received through the NoC to achieve direct core-to-core communication (peer-to-peer communication). Due to the pessimistic estimation of \(c_i\) and \(m_{i,j}\), the actual execution time \(c_i^{\prime }\) of each subtask \(v_i\) and the actual message size \(m_{i,j}^{\prime }\) of each message \(m_{i,j}\) can be potentially less than their estimated values (i.e., \(c_i^{\prime } \le c_i\), \(m_{i,j}^{\prime } \le m_{i,j}\)). To validate the schedulability of \(G\), let \(R\) refer to the estimated bound which is the maximum duration time between the start time of the first subtask and the finish time of the last subtask, and \(R^{\prime }\) be the actual total execution time at runtime. \(G\) is schedulable if the bound \(R\) is no more than its deadline. With high-quality and timing-predictable bounds, the DAG task’s safety can be ensured and resource allocation can be also well controlled to avoid resource overprovisioning.

Therefore, to ensure the response-time predictability, the goal is to generate a safe and tight bound for a real-time DAG task \(G\). Specifically, safe indicates the actual response time under any execution scenario is no more than the estimated bound (i.e., \(R^{\prime } \le R\)), whereas tight means the bound \(R\) should be minimized as possible without the violation of the safe condition under current resource budget constraints.

The wormhole NoCs [20] are widely utilized and generally developed for best-effort communications. Specifically, they can perform high performance in average latency, but demonstrate significant unsafety and pessimism of worst-case latency for time-critical communications. For example, the worst-case runtime behavior is difficult to identify due to the parallel transmission of multiple packets over a shared link. Such behavior will contribute to the notorious MPB [38] problem due to the limited router buffer size, and thus the generated latency bounds are usually overestimated.

For bounds predictability, rather than fix the erroneous patch of the current analysis for wormhole NoCs, we introduce SLT NoC, which is another kind of NoC (optical NoC, e.g., [17]; electrical NoC, e.g., [23]) featured with single-cycle long-range traversal. To be specific, among the SLT NoCs, in the rest of this article, we employ some terminology and techniques of the representative one, SMART NoC [8, 23], which has been proven as a promising NoC technique for many-core platforms.

SMART (Single-Cycle Multi-hop Asynchronous Repeated Traversal) [2, 23] is an advanced NoC architecture that enables single-cycle long-range (up to \({\it HPC}_{{\it max}}\) hops) traversal by dynamically building a direct bypass from the source to the destination. For long-range bypass traversal, low-swing clockless repeated link and bypass mechanisms are integrated into the on-chip routers. Before packet transmission, the long-range bypass path is pre-built by setting the control signals at runtime. If the bypass path is built, SMART enables the single-cycle exclusive transmission by avoiding buffering at intermediate routers. Recent research works (e.g., [8, 9, 13, 24, 39]) improve its communication performance and employ SMART techniques to develop new works (e.g., [7, 11, 21]).

For a source-destination link, different from wormhole NoC of Figure 2(a) with parallel traversal, a flit of \(\tau _1\) can exclusively traverse the Link \(1\rightarrow 4\) in SLT NoC of Figure 2(b). For example, when \({\it HPC}_{{\it max}}\) = 3, a flit of \(\tau _1\) can reach the destination (Router \(r_4\)) in a single cycle. Then, like a uniprocessor resource, the source-destination Link \(1\rightarrow 4\) can be regarded as a physically single resource without being shared and logically “1-hop” traversal. The observations of the non-preemptive low-latency SLT NoC are twofold. First, compared to the works (e.g., [20, 38]), MPB is naturally avoided since the flit-level preemption and parallel traversal on a source-destination link are eliminated. Note that for a single DAG task model considered in priority-preemptive wormhole NoCs and compared with the communication task model as in the work of Indrusiak et al. [20], the difference is that the formula of packet latency bounds is slightly different, but the MPB phenomenon still exists. Our proposed scheduling paradigm also shows benefits compared with the single DAG task considered in priority-preemptive wormhole NoCs. Second, in other work (e.g., [35]), the long-range source-destination link is considered as a logically single resource without being shared, which leads to large resource waste at runtime. By contrast, the links within \({\it HPC}_{{\it max}}\) [23] in SLT NoCs are naturally and physically single resources without being shared. Therefore, to ensure the real-time performance of NoCs, we introduce SLT NoC to real-time many-core systems.

On many-core systems, dynamic scheduling schemes [1] are widely utilized, where the scheduling decisions are conducted at runtime. In this article, we adopt the non-preemptive dynamic schedulers due to their advantages in some real cases compared with the preemptive ones. However, the non-preemption behaviors bring challenges to real-time systems, as the safety of estimated bounds may not be ensured due to timing anomalies. Timing anomaly is observed by Graham [16] when employing the non-preemptive dynamic scheduler on multi-core systems. Specifically, the actual response time at runtime can probably be more than the estimated bound under the same dynamic scheduler, when the actual execution time of subtasks is less than the designed WCET. Thus, this phenomenon may make the real-time tasks that are originally schedulable become unschedulable.

When dynamically scheduling the messages on SLT NoC in a non-preemptive manner, we observe that the execution-timing anomaly phenomenon can also occur. We use an example to illustrate such a phenomenon. As shown in Figure 3, the task is scheduled upon a \(3\times 3\) SLT NoC. Assume the allocated NoC resource and the DAG structure are given and fixed, whereas the actual transmission time of the message \(m_{1,3}\) is reduced from the designed WCET 3 to 1.5 at runtime. Counter-intuitively, the actual response time is increased from the design-time estimated bound 10 to 10.5 under the same dynamic scheduler (e.g., breadth-first scheduler). In this case, the originally schedulable real-time task can be potentially unschedulable if the specified deadline is set as 10.

The recent works [12, 30, 36] have addressed the timing anomaly problems for real-time task scheduling on multi-core systems, but their approaches cannot be trivially extended from multi-core to NoC scheduling due to direct and indirect contention in communication resources, showing pessimistic average-case runtime performance. Besides, when jointly scheduling the computation and communication subtasks, all of the possible runtime execution instances can be exponential. Deriving the optimal bound by enumerating all of the runtime instances can be computationally infeasible.

To facilitate analysis of computation and communication subtasks, we develop job and resource abstractions—that is, resource (e.g., computation PE, communication route) from SLT NoC and job (e.g., computation task, communication message) from the DAG structure. This indicates that each job can be mapped to the corresponding resource, like the relationship between task and core in uniprocessor scheduling.

For simplicity, only a part of PEs are shown in Figure 4, and SLT candidates refer to the candidates that can be reached via an SLT path from router \(r_{13}\). If \(v_p\) is mapped on \({\it PE}_{13}\), the route \(r_{13} \rightarrow r_{18} \rightarrow r_{23}\) or \({\it PE}_{23}\) is considered as a resource. We uniformly call such a computation PE or communication route as a resource.

For example, in Figure 4, inter-subtask message \(m_{p,s}\) or computation subtask \(v_s\) is considered as a job denoted by \(\tau _i\). In Figure 1, the task graph \(G\) can be divided into jobs \(\lbrace v_1\), \(m_{1,2}\), \(m_{1,3}\), \(v_2\), \(v_3\), \(m_{2,4}\), \(m_{2,5}\), \(m_{3,6}\), \(v_4\), \(v_5\), \(v_6\), \(m_{4,7}\), \(m_{5,7}\), \(m_{6,7}\), \(v_7\rbrace\). Note that \(G = (V, E)\) can generate \(n\) (i.e., \(n = |E|+|V|\)) jobs. For job \(\tau _i\) (e.g., \(m_{p,s}, v_s\)) and resource \(\Phi _j\) (e.g., \(\Xi _{p \rightarrow s}, {\it PE}_s\)), \(\tau _i\) can be “executed” on the exclusive \(\Phi _i\), in which \(v_s\) is allocated to \({\it PE}_s\) and \(m_{p,s}\) is transmitted to \({\it PE}_s\) via the route \(\Xi _{p \rightarrow s}\), respectively. \(\Phi _j\), which is assigned to \(\tau _i\), can be simply called \(\Phi _i\). For \(\tau _i\), let \(s_i^{\prime }\) and \(s_i\) be the execution start time points, \(f_i^{\prime }\) and \(f_i\) be the finish time points, and \(c_i^{\prime }\) and \(c_i\) (\(c_i^{\prime } \le c_i\)) be the execution/transmission time at the runtime and design-time estimation phases, respectively.

Before the execution of DAG tasks, configuration, such as the job-to-resource allocation and communication route, should be given. We define the configuration as follows.

The bound \(R\) must be compared with the deadline to validate the schedulability. In this article, assume \(G\) is scheduled by a certain non-preemptive dynamic scheduler and configured by \({\it Conf}\), and \(R\) is generated by “simulating” such scheduler, assuming the jobs are executed for their WCETs. Specifically, the simulated bound of \(G\) is \(R = 10\) in Figure 3(a). Intuitively, the actual response time \(R^{\prime }\) at runtime would be less than estimated bound \(R\) with the same scheduler, \(R^{\prime } \le R\), since some jobs may be executed for less than their WCETs. However, the actual schedule result may be the opposite.

In the previous subsection, the estimated bound \(R\) is generated by simulating the dynamic scheduler at design time. However, due to a variety of execution instances, \(R\) can be potentially unsafe. To uniquely identify a particular runtime execution instance of a DAG task, we introduce the following definition of schedule order of jobs.

For instance, the DAG task in Figure 3 can be divided into jobs \(\lbrace v_1\), \(m_{1,2}\), \(m_{1,3}\), \(v_2\), \(v_3\), \(m_{2,4}\), \(m_{3,5}\), \(v_4\), \(v_5\), \(m_{4,6}\), \(m_{5,6}\), \(v_6\rbrace\), sequentially denoted by \(\tau _1\), \(\tau _2\), ..., \(\tau _{12}\). In Figure 3(a), the design-time schedule order \({\it Sch}\) of \(G\) is as follows:

\({\it Sch} = \lbrace \tau _1 \rightsquigarrow \tau _2 \rightsquigarrow \tau _3 \rightsquigarrow \tau _4 \rightsquigarrow \tau _5 \rightsquigarrow \tau _6\) \(\rightsquigarrow \tau _7 \rightsquigarrow \tau _8 \rightsquigarrow \tau _9 \rightsquigarrow \tau _{10} \rightsquigarrow \tau _{11} \rightsquigarrow \tau _{12}\rbrace\).

Specifically, “\(\tau _2 \rightsquigarrow \tau _3\)” means that \(\tau _2\) (i.e., \(m_{1,2}\)) starts execution before or not later than \(\tau _3\) (i.e., \(m_{1,3}\)). The bound \(R\) of the DAG task in Figure 3(a) is 10, whereas in Figure 3(b), the runtime schedule order is as follows:

\({\it Sch}^{\prime } = \lbrace \tau _1 \rightsquigarrow \tau _2 \rightsquigarrow \tau _3 \rightsquigarrow \tau _5 \rightsquigarrow \tau _4 \rightsquigarrow \tau _7\) \(\rightsquigarrow \tau _6 \rightsquigarrow \tau _9 \rightsquigarrow \tau _8 \rightsquigarrow \tau _{11} \rightsquigarrow \tau _{10} \rightsquigarrow \tau _{12}\rbrace\).

In Figure 3(b), the actual response time \(R^{\prime } = 10.5\), which is more than the bound \(R = 10\). Thus, \(R\) is timing-anomaly and unsafe, and \(G\) that is originally regarded as schedulable becomes unschedulable if the deadline is set as 10, leading to a false-positive phenomenon. The observations are twofold:

In the following, we propose a polynomial-time approach, with which safe bounds can be obtained. Specifically, given configuration \({\it Conf}\) and any non-preemptive dynamic scheduler, we present a schedule order constraint \({\it Sch}\) among jobs to ensure safe execution. By the aforementioned observations, the timing-anomaly execution is caused by the change of schedule order used to estimate the bound. A feasible solution is to consistently keep the same schedule order of jobs at design time and runtime. Before that, motivated by the work [32] on priority-preemptive wormhole NoCs, we define the following resource contentions regarding the spatial relationship between computation/communication jobs, including direct, indirect contention, and contention-free relationships.

Note that since there is no resource contention (i.e., \(\Phi _i \cap \Phi _j == \emptyset\)) between computation job \(\tau _i\) and communication job \(\tau _j\), \(\tau _i\) and \(\tau _j\) have the contention-free relationship. To granularly judge the resource contention, we divide all of the jobs into multiple groups according to the spatial relationships defined earlier. Without loss of generality, \(\tau _i\) and \(\tau _j\) (\(\forall i, j \in \lbrace 1, 2, \ldots , |V|+|E|\rbrace (i \ne j)\) are mapped to the same group if \(\tau _j \in \textsf {dc}(\tau _i)\cup \textsf {ic}(\tau _i)\) or \(\tau _i \in \textsf {dc}(\tau _j)\cup \textsf {ic}(\tau _j)\). For example, in Figure 5(b), \(\tau _1\), \(\tau _2\), \(\tau _3,\) and \(\tau _4\) should belong to the same group due to the direct or indirect contention relationship, whereas in Figure 5(c), \(\tau _1\) and \(\tau _4\) belong to different groups due to the absence of direct and indirect contention. Suppose all jobs are divided into \(\chi\) groups (i.e., \({\it group}_1\), \({\it group}_2\), ..., \({\it group}_\chi\)), and the schedule order in \({\it group}_\chi\) is denoted by \({\it sch}({\it group}_\chi)\). Thus, the total schedule order consists of multiple independent partial orders (i.e., \({\it Sch}^{\prime }\) = \({\it sch}({\it group}_1)\cup {\it sch}({\it group}_2)\cup\) ... \(\cup {\it sch}({\it group}_\chi)\)). Let \(R^{\prime }\) be the actual response time of \(G\) enforced with a certain order constraint \({\it Sch}^{\prime }\).

With Theorem 1, the timing-anomaly-free execution can be ensured by enforcing the consistent order at design time and runtime, and thus the generic bounds (for any non-preemptive dynamic scheduler) are safe (i.e., \(R^{\prime } \le R\)).

Based on Theorem 1, the essential idea behind our runtime timing-anomaly-free guarantee of a DAG task is to insert extra schedule constraints between jobs if resource contention occurs. Even if the partial order constraint \({\it Sch}^{\prime }\) can guarantee the timing-anomaly-free execution, the inserted constraint in \({\it Sch}^{\prime }\) is pessimistic due to coarse-grained consideration (i.e., only in the spatial dimension).

We revisit the four jobs of Figure 5(b), meeting \((\tau _1 \rightsquigarrow \tau _2 \rightsquigarrow \tau _3 \rightsquigarrow \tau _4)\) due to the direct and indirect contention relationship. For \(\tau _4\), \(\textsf {dc}(\tau _4) = \lbrace \tau _3\rbrace\), \(\textsf {ic}(\tau _4) = \textsf {dc}(\tau _3) \cup \textsf {ic}(\tau _3) = \lbrace \tau _1, \tau _2\rbrace\). By Theorem 1, \(\tau _4\) starts execution after \(\tau _3\) that also after \(\tau _2\), whereas \(\tau _2\) starts execution after \(\tau _1\), resulting in a dependent order-chain, called the cascading effect. \(\tau _4\) finally starts execution after the distant \(\tau _1\) via intermediate jobs \(\tau _2\) and \(\tau _3\). Suppose three time points \(t_a\), \(t_b\), \(t_c\) meet \(t_a \lt t_b \le t_c\). \(t_a\) is the current scheduling point in which \(\tau _1\) and \(\tau _4\) are ready, whereas \(\tau _3\) becomes ready at \(t_c\). There is a chance that \(\tau _4\) can start execution at \(t_a\) (in parallel with \(\tau _1\)) and finish execution at \(t_b\) not later than \(t_c\). Although the time interval (\(t_a\), \(t_b\)) is idle and available, it cannot be utilized in the originally partial order, leading to poor communication link utilization.

To reduce such cascading effect, without loss of generality, assume \(\tau _j \in \textsf {ic}(\tau _i)\), \(\exists \tau _k \in \textsf {dc}(\tau _i), \tau _j \in \textsf {dc}(\tau _k)\). \(\tau _j \rightsquigarrow \tau _k \rightsquigarrow \tau _i\) (e.g., \(\tau _2 \in \textsf {ic}(\tau _4)\), \(\tau _3 \in \textsf {dc}(\tau _4), \tau _2 \in \textsf {dc}(\tau _3)\) in Figure 5(b)). The actual start time of the analyzed job \(\tau _i\) is indirectly dependent on \(\tau _j\) via \(\tau _k\), meaning that \(\Phi _i\) (i.e., Link \(r_4 \rightarrow r_5\) in Figure 5(b)) may not be utilized even if it is idle. In fact, the runtime performance can be strictly improved by allowing a part of idle resources, which will not cause temporal and spatial contentions to the unexecuted jobs \(\tau _k\) (i.e., \(\in \textsf {dc}(\tau _i)\)), to be utilized before \(s_k^{\prime }\) at runtime.

In this subsection, for the analyzed ready job \(\tau _i\) at scheduling point \(t_{\it sp}\), we conditionally remove the preceding partial order constraint \(\tau _k \rightsquigarrow \tau _i\) (i.e., \(\tau _i\) can instead start execution before \(\tau _k\)) under the following condition \(\xi _i^{\prime }\):

where

Note that we assume the notations attached with one and two apostrophes in the top right corner denote the runtime parameters when enforced with the original partial (i.e., \({\it Sch}^{\prime }\)) and relaxed partial (i.e., \({\it Sch}^{\prime \prime }\)) order constraints, respectively. Specifically, \(R^{\prime \prime }\) denotes the actual response time with the relaxed partial order \({\it Sch}^{\prime \prime }\), whereas \(R^{\prime }\) denotes the original partial order \({\it Sch}^{\prime }\). If the partial schedule order \(\tau _k \rightsquigarrow \tau _i\) is broken, \(\tau _k\) starts execution after the contending resources are released by \(\tau _i\). The new actual start time of \(\tau _k\) with the relaxed order \({\it Sch}^{\prime \prime }\) is denoted by \(s_k^{\prime \prime }\), where \(s_k^{\prime \prime } \ge t_{\it sp} (s_i^{\prime \prime }) + c_i^{\prime \prime }\), \(c_i^{\prime \prime } = c_i^{\prime }\).

Following Theorem 2, the runtime performance of the original partial order can be strictly improved (i.e., \(R^{\prime \prime } \lt R^{\prime }\)) without timing anomaly, when a part of order constraints (e.g., \(\tau _k \rightsquigarrow \tau _i \subseteq {\it Sch}^{\prime \prime }\)) is removed under the condition \(\xi _i^{\prime }\). This is because \(\tau _k\) will still start execution not later than \(s_k^{\prime }\) (i.e., \(s_k^{\prime \prime } \le s_k^{\prime }\)) when the original order is broken by \(\tau _i\). Moreover, there is a chance that the runtime performance can also be strictly improved when ignoring the second condition of \(\xi _i^{\prime }\) (i.e., Figure 6(a)) and removing part of orders. When the runtime execution time of the current DAG task is reduced, the computation/communication resources can be reassigned to other DAG tasks as early as possible if the workload is heavy, saving resource consumption.

To derive a specific tight bound \(R\), Section 5 has developed proper parameters \({\it Conf}\) and \({\it Sch}\) with a heuristic algorithm. In this subsection, we show how to adopt \({\it Conf}\) and \({\it Sch}\) to safely schedule DAG edges/vertices at runtime.

Without loss of generality, assume \(G\) starts execution at time point 0, and the assigned resources (i.e., decided by \({\it Conf}\)) are initially idle. According to the design-time schedule order \({\it Sch}\), the runtime order constraints could have different possible implementations. By Theorem 1, one solution is to set priorities for jobs according to the offline start time points generated at the design time. For example, “\(s_k \le s_i\)” denotes the order constraint “\(\tau _k \rightsquigarrow \tau _i\),” meaning that \(\tau _k\) (with higher priority) actually starts execution not later than \(\tau _i\) at runtime.

Even if some part of partial order constraints (e.g., \(\tau _k \rightsquigarrow \tau _i\)) are relaxed under the condition \(\xi _i^{\prime }\), the runtime performance \(R^{\prime \prime }\) of the relaxed order dominates \(R^{\prime }\) of the original order when \(s_k^{\prime \prime } \le s_k^{\prime }\) by Theorem 2. However, the runtime time parameters \(s_k^{\prime }, s_k^{\prime \prime }, c_i^{\prime \prime }\) in \(\xi _i^{\prime }\) cannot be known before a job starts execution. Instead, in runtime scheduling, the original order relaxing condition \(\xi _i^{\prime }\) are relaxed to the following \(\xi _i\) by using the design-time parameters \(c_i\) and \(s_k\):

Although the relaxed condition \(\xi _i\) cannot guarantee strict runtime performance improvement of the partial order in all cases, the runtime execution enforced with the relaxed order under \(\xi _i\) is free of timing anomaly by Lemma 2, since \(\tau _k\) that suffers order break from \(\tau _i\) starts execution not later than \(s_k\), namely \(s_k^{\prime \prime } \le s_k\). Besides, the observed cascading effect (see Section 4.3) can be reduced/eliminated, which thus will avoid extremely poor NoC resource utilization. Experimental results (see Section 7) demonstrate that the average-case runtime performance of the relaxed order under \(\xi _i\) is further improved in our test set, compared with that of the original order.

The runtime scheduler dispatches the ready job \(\tau _i\) on its assigned resource \(\Phi _i\) at the scheduling point \(t_{\it sp}\) if the condition \(\xi _i\) is met, shown in Algorithm 2. The procedure of the runtime scheduler stops when all the ready/eligible jobs are traversed and is repeated at the next scheduling point triggered by the completion of a job. In this article, we mainly focus on the strategic and theoretical design of the runtime scheduler and do not limit the actual implementation in the operating system layer. One possible solution is that the online scheduler is incorporated into the operating system of the NoC controller, consisting of one main scheduler and multiple sub-schedulers with threads. The main scheduler selects the highest-priority job from the ready queue \(\mathcal {Q}_{\it ready}\) and allocates a thread for such a job. Then, the thread sub-scheduler will check the scheduling condition \(\xi _i\) to see if the job is to be scheduled or put in \(\mathcal {Q}_{\it hp}\).

Specifically, in Algorithm 2, \(\mathcal {Q}_{\it ready}\) records the set of ready jobs. At each scheduling point \(t_{\it sp}\), if \(\mathcal {Q}_{\it ready}\) is not empty, \(\mathcal {Q}_{\it hp}\) is set as an empty set in line 3. According to the offline schedule order \({\it Sch}\), the job \(\tau _i\) with the earliest design-time start time (i.e., \((\tau _i \rightsquigarrow \tau _q) \subseteq {\it Sch}, \forall \tau _q \in \mathcal {Q}_{\it ready}, q \ne i\)) is selected. Before the execution of the selected job \(\tau _i\), the condition \(\xi _i\) is checked in line 5. If \(\xi _i\) is met, \(\tau _i\) starts execution on its assigned resource \(\Phi _i\). Note the condition \(t_{\it sp} + c_i \le s_k\) aims to guarantee \(s_k^{\prime \prime } \le s_k\), meaning that \(\tau _i\) can remove the order constraint \(\tau _k \rightsquigarrow \tau _i\) but the worst-case execution of \(\tau _i\) must finish before \(s_k\) to avoid timing anomaly. Thus, the time interval (\(t_{\it sp}, s_k^{\prime \prime }\)) that originally cannot be utilized in the original order can be utilized when enforcing the relaxed order at runtime, which can further improve the runtime performance of the original order. If \(\xi _i\) is violated, \(\tau _i\) is inserted into \(\mathcal {Q}_{\it hp}\) and removed from \(\mathcal {Q}_{\it ready}\).

The proposed DAG-Order is based on SLT NoC. SLT NoC is identified as a kind of single-cycle long-range traversal NoCs that are well developed and need not be designed from scratch. Thus, off-the-shelf NoCs characterizing such data transmission behavior are available, such as SMART [23]/optical [17] NoCs. To be scalable, an SLT NoC can be split into multiple cluster networks (e.g., [31]), in which the cluster size is defined by user requirements. The global control wires are limited to the cluster level instead of the whole NoC, and thus SLT NoC can be extended to a larger-size network and real-time system. On account of the requirement for job-to-resource allocation (from off-chip memory to NoC) and chip thermal distribution, each cluster in NoCs is necessarily equipped with a resource controller [6] to achieve the cluster-level global control in real-time guarantee and chip thermal reliability in the dark silicon era.

Specifically, given a DAG task \(G\), a suitable cluster (e.g., cluster size, voltage, and frequency) is selected from the whole SLT NoC until the required deadline is met. \(G\) is executed within the allocated cluster and scheduled with Algorithm 2. The proposed scheduling algorithm and arbitration is conducted in the operating system of the resource controller. For each computation/communication job, a thread is allocated by the main scheduler, whereas the scheduling decision is distributed through the dedicated control links within the cluster network. The information of each job \(\tau _i\) can be partly/fully stored in on-chip memories (e.g., private/shared cache) of the resource controller, encoded by a \(ready\) bit (i.e., eligible for execution), \(priority\) (i.e., design-time execution start time \(s_i\)), \(c_i\) (i.e., WCET), and assigned resource (i.e., \(core\_id\) for computation job, a bit vector \(route\) for communication job). Bit 1 represents the busy state of core/link, and 0 represents the idle state. The availability of the assigned route is checked by a bit-wise AND operation according to the resource occupation state. Similar to circuit switching, the contention-free “1-cycle” SLT path is established for the winners of the scheduler by sending a path-setup control packet along with the control layer. Once the resources are released by the finished jobs, the resource occupation state is updated immediately. This update operation of resource/job state can be conducted concurrently with the schedule processing from communications/computations, and thus cannot delay the schedule processing and schedule information delivery to the routers/PEs of communications/computations. Especially for the large-size real-time task, it can be divided into multiple moderate sub-tasks, with each sub-task assigned to one cluster network. Note that if a parent job and its child are assigned to different clusters, the control message of the dependence relationship is propagated through the control links between cluster controllers, whereas the generated data of parents is delivered to the border NoC node between clusters or shared cache where the child can fetch the data. Then, the child job will become ready and eligible to be executed if all input dependencies are met.

The overhead of the control layer (e.g., resource occupation update, control links) on SLT NoC is a necessary part of cluster-based control (e.g., [31]), in which the existing hardware resources can be reused. Since resource control is conducted in a cluster-based centralized manner, the existing router buffer of SLT NoC (e.g., SMART NoC) can be reduced to one flit to mitigate the overhead in this work, whereas the additional time overhead \(\mathcal {C}_{\it ctrl}\) of conducting job scheduling and NoC control operations for each DAG vertex/edge is assumed to be incorporated into the WCET of jobs, which should be accurately estimated in real implementation. As in the work of Krishna et al. [23], each core of SMART NoCs has 32KB private L1 cache and 1MB private/shared cache. The additional storage space for job information is acceptable when equipped with KB- and MB-level caches. Here, we mainly focus on the strategic design of the scheduling paradigm based on off-the-shelf SLT NoCs. Additional research such as accurate estimation of time deviation \(\mathcal {C}_{\it ctrl}\), exploration of more efficient designs of scheduling schemes, and cluster-based SLT NoC will be conducted in future work.

To derive the response time results and validate the effectiveness of the scheduling strategy, we build a high-level simulator by “simulating” (which is different from the critical-path-based analysis like in the work of He et al. [18]) the runtime execution according to the schedule order based on the abstracted SLT NoC in a C/C++ environment. Although the runtime behavior is not the actual execution behavior in realistic systems, it reflects the technical efficiencies of our scheduling approach to some extent, which is used for comparison of all approaches in experiments. Like recent DAG works [12, 18], the synthetic DAG tasks are generated by the Erdos-Renyi approach \(G(|V|, p)\) [14], which is a commonly experimental setup in real-time DAG scheduling. The DAG tasks are totally run on a \(4 \times 4\) mesh-based cluster of SLT NoC. Specifically, the parameters of the DAG tasks are generated as follows:

Since SLT NoCs (e.g., optical [17]/SMART [23] NoCs) have different implementations in real systems and we mainly focus on the theoretical design of the new real-time scheduling paradigm and do not limit the actual implementation in the hardware part, in the experiments, the simulator infrastructure only models the task graph, the assumed WCET of each edge/vertex, and the SLT NoC behavior. The response time of the DAG task begins with the corresponding necessary programming codes already loaded to the NoC private/shared cache/memory and ends with the execution finish of the last DAG vertex, including the time of vertex/PE execution and inter-vertex/PE message transmission, whereas the other influencing factors are kept the same. The additional time overhead of conducting job scheduling and NoC control operations for each job is assumed to be incorporated into the WCET of the corresponding jobs. The real instruction-level dependency generated at runtime and the memory/cache impact do not factor into the results being evaluated, as these operations (e.g., memory-/cache-related operations) can be embedded into the DAG task model by adding the corresponding vertices and edges at design time. Besides, we generate the task graphs from the realistic StreamIt benchmarks [29, 33] and AI applications. In the experiments, we collect three StreamIt benchmarks including Audiobeam (adm), FMRadio (fmr), and H264 (h264), and four AI applications including MobileNetV2 (mnt), UNet (unet), VGG16 (vgg), and ResNet50 (res). The employed benchmarks are representative, as they have different orders of magnitude in workloads, and cover audio processing, scientific processing, and AI applications, among others. In addition, the proposed scheduling scheme DAG-Order is applicable and extended to other benchmarks that can be modeled as DAG.

To facilitate quantitative comparison, we use the performance metrics response time bound and actual response time. Specifically, response time bound is estimated by “simulating” the runtime execution of DAG tasks at design time and assuming the jobs are executed for their WCETs, whereas actual response time is measured by varying the actual execution time of jobs within WCET. The proposed approaches and the corresponding baselines are as follows in our experiments:

Note that the task model of real-time communication analysis in other works [11, 20, 38] focuses on the independent periodic packet flows, priority-preemptive scheduling schemes, and traditional multi-hop transmission NoCs, whereas in this article, we adopt a general DAG task model of jointly considering the computation and communication workloads and the non-preemptive scheduling scheme in SLT NoCs. Similarly, the classical bounds (e.g., [18]) on multi-cores do not consider inter-core communication and thus cannot be fully applicable in SLT NoCs. Therefore, these related approaches [11, 18, 20, 38] are only qualitatively compared to demonstrate the advantages of the proposed NoC scheduling paradigm and are not adopted as quantitative baselines. Instead, we quantitatively compare our work with another SOTA related simulation-based approach [12] and the conference version [10] of this work.

Figure 7 demonstrates the comparison of bounds. Figure 7(a) shows the results under synthetic benchmarks by varying \(p_{\it con}\), Figure 7(b) shows the results by varying the \(N_{max}\), Figure 7(c) shows the results with the CCR, and Figure 7(d) shows the results under realistic benchmarks. Each point of all the results is averaged with multiple experiments and normalized to the bound \(R_{\it our}\) obtained by Algorithm 1 in this article. It can be observed that the bound \(R_{\it our}\) is consistently smaller or not more than the baseline bounds \(R_{\it base}\), indicating that Algorithm 1 can tighten the bounds.

Specifically, as shown in Figure 7(a), the bound gap between \(R_{\it our}\) and \(R_{\it base}\) increases with the increasing of \(p_{\it con}\). It indicates that the superiority of \(R_{\it our}\) is more apparent when the DAG structure is more complicated (i.e., more data/control dependence). This is because the number of runtime execution instances will be larger when enforcing the complicated dependence among vertices. Thus, the response time bound experiences high time variation due to a large number of instances. Without considering the criticality and dependence of jobs, \(R_{\it base}\) cannot produce tighter bounds. \(R_{\it our}\) conducts the critical remaining path scheduling (considers the inter-job dependence) and performs better. Similarly, as shown in Figure 7(b) through (d), the bound \(R_{\it our}\) also performs better, with no larger bounds compared with the baseline bound \(R_{\it base}\). By employing our bound \(R_{\it our}\), (i) if the DAG tasks are set as the same deadlines, less computation and communication resources are needed, in which the resource assignment is well controlled and the resource over-provisioning is avoided, and (ii) if the DAG tasks are assigned the same resources, \(R_{\it our}\) can produce a higher acceptance ratio in the schedulability test.

Figure 8 demonstrates the runtime performance (i.e., actual response time) by varying the execution time within WCET of jobs. Figure 8(a) shows the results under synthetic benchmarks by varying \(p_{\it con}\), Figure 8(b) shows the results with \(p_{\it vary}\), Figure 8(c) shows the results with the CCR, and Figure 8(d) shows the results under realistic benchmarks. All the results are averaged and normalized to the response time \(R_{\it base}^{\prime }\). It can be observed that \(R_{\it rpo}^{\prime }\) and \(R_{\it opo}^{\prime }\), which are enforced with the proposed order constraints, perform better compared with the SOTA related work \(R_{\it base}^{\prime }\) [12]. Meanwhile, it also reflects the communication performance/resource utilization of \(R_{\it rpo}^{\prime }\) and \(R_{\it opo}^{\prime }\) on SLT NoC is better than \(R_{\it base}^{\prime }\) under the same resource constraints.

Specifically, \(R_{\it rpo}^{\prime }\) and \(R_{\it opo}^{\prime }\) granularly consider the direct and indirect contention, and less schedule constraints are enforced among jobs. This means that the scheduling flexibility of \(R_{\it rpo}^{\prime }\) and \(R_{\it opo}^{\prime }\) is better than that of \(R_{\it base}^{\prime }\), while guaranteeing the timing-anomaly-free execution. When the jobs of \(R_{\it rpo}^{\prime }\) and \(R_{\it opo}^{\prime }\) are finished earlier than that of \(R_{\it base}^{\prime }\), the assigned resources are available and can be assigned to other jobs earlier, improving the resource utilization. Although \(R_{\it rpo}^{\prime }\) and \(R_{\it opo}^{\prime }\) both consider the direct and indirect contention relationship among jobs, they are slightly different in average-case runtime performance. The reason is that the observed cascading effect is reduced/eliminated. In other words, when the shared resources are available for an upcoming scheduled job while the contending higher-priority jobs have not been started execution on these shared resources, the upcoming scheduled ready job can conditionally start execution, further improving the resource utilization. When the actual response time of the current DAG task is reduced, the resources can be reassigned to other DAG tasks as early as possible if the remaining workload is heavy, reducing the resource consumption. Besides, all of the runtime execution instances are free of timing anomaly in the experiments (e.g., \(R_{\it rpo}^{\prime } \le R_{\it our}\)), also proved in Lemma 2.