RD-Gen: Random DAG Generator Considering Multi-rate Applications for Reproducible Scheduling Evaluation

arXiv:2608.19460v1 [cs.SE] 19 Aug 2026

RD-Gen: Random DAG Generator Considering Multi-rate Applications for Reproducible Scheduling Evaluation Atsushi Yano

Takuya Azumi

Tier IV, Inc atsushi.yano.2@tier4.jp

Tier IV, Inc Graduate School of Science and Engineering, Saitama University

Abstract—Real-time systems have various requirements such as the deadline and resource constraints. In addition, real-time systems are becoming larger and more complex, and studies on performance analysis and efficient scheduling algorithms are becoming increasingly important. Directed acyclic graph (DAG) models, which can express task dependencies and parallelism, are used for such studies. Random DAG sets are used to demonstrate the effectiveness and objectivity of methods proposed for realtime systems. However, there is no random DAG generation tool available that can generate a DAG set that considers the latest multi-rate applications. Therefore, researchers need to generate random DAG sets on their own, leading to additional effort and reduced reliability and reproducibility. To solve this problem, we propose a random DAG generator considering multi-rate applications for reproducible scheduling evaluation (RD-Gen). RD-Gen also enables batch generation of random DAG sets with different parameters. Case studies are used to demonstrate that RD-Gen can manage various problem settings and DAG study requirements. Index Terms—DAG, Random generation tool, Multi-rate applications

I. I NTRODUCTION Real-time systems, such as self-driving systems, need to successfully execute while meeting various requirements such as producing an output within a pre-determined time (i.e., meeting deadlines), having low power consumption, and meeting resource constraints [1]. To fulfill these constraints, many studies have been conducted on task allocation and scheduling, as well as on analyzing the end-to-end latency and the response time of a system [2]. Systems are increasingly becoming larger and more complex, and many studies use models, such as directed acyclic graphs (DAGs), to represent the complex dependencies and parallelism of the tasks in these systems. DAGs are used in many allocations, scheduling, and latency analysis studies [3], [4] because they express the process flow from system input to output and can represent various types of information such as the dependencies between tasks, the task execution time, and the period. To evaluate the performance of proposed methods, it is important to compare them with existing methods using task sets. Accordingly, in method This paper is based on results obtained from a project subsidized by the New Energy and Industrial Technology Development Organization (NEDO).

© 2023 IEEE. Personal use of this material is permitted. DOI: 10.1109/ISORC58943.2023.00015

evaluations using DAGs, randomly generated DAGs are used to ensure objectivity and demonstrate generality [1], [5], [6]. To aid in such evaluations, random DAG generation tools, such as task graph for free (TGFF) [7] and GGen [8], have been proposed and utilized in the latest publications [9], [10]. These tools allow the user to parametrically specify the shape of a DAG and the properties assigned to the tasks and edges. However, TGFF and GGen were proposed in 1999 and 2010, respectively, and cannot meet the requirements of multi-rate DAGs considering state-of-the-art real-time systems. Because embedded systems in automobiles and avionics, as well as in self-driving systems, contain multiple tasks that operate over different periods (e.g., sensors [11] and localization [6]), studies targeting multi-rate DAGs are becoming increasingly important [2], [12]. In studies of such multi-rate DAGs, not only the shape of the DAG but also the ratio of the execution time to the task period has a significant impact on the performance of the method (e.g., implicit deadlines [13], [14] and task utilization [15]). However, TGFF cannot generate multi-rate DAGs, and GGen can only randomly set the period and the execution time of tasks. Therefore, most researchers who consider multi-rate DAGs have to implement their own random DAG sets [15]–[17]. It is laborious for researchers to prepare their own random DAG sets, and this practice further reduces the reliability and reproducibility of the evaluation results. To solve these problems, this paper proposes a random DAG generator considering multi-rate applications for reproducible scheduling evaluation (RD-Gen). RD-Gen extends existing DAG generation methods and provides a flexible evaluation platform. Because RD-Gen uses a pseudo-random number generator, other researchers can reproduce the DAG sets used in an evaluation by specifying the same options. Contributions: Our primary contributions are summarized as follows. • RD-Gen extends existing random DAG construction methods, Fan-in/Fan-out [7] and G(n, p) [8] methods, to meet researchers’ requirements. • RD-Gen proposes a new Chain-based method to flexibly construct state-of-the-art chain-based multi-rate DAGs.

User

Proposed tool Random DAG generate

Configura�on file

Input

User-specified all combina�on Construct graph Set proper�es

Performance evalua�on e.g.,

Output All random DAGs used in the evalua�on

Scheduling algorithm

Input

schedulability analysis

Figure

DAG descrip�on file

・ ・ ・

・ ・ ・

Fig. 1. System model. TABLE I DAG N OTATIONS DAG Types

Common

Multi, Chain

Chain

Symbols G V |V | E vi Ci ei,j commi,j CCR D(G) vitd ϕi Ti ui U vied Γi |Γ| CΓi uΓi TΓi

Descriptions DAG Set of all nodes of G Total number of nodes of G Set of all edges of G i-th node Worst-case execution time (WCET) of vi Edge from vi to vj Communication time of ei,j Communication-to-computation ratio (CCR) of G End-to-end deadline i-th timer-driven node Offset of vitd Period of vitd Utilization of vitd Total utilization of G i-th event-driven node i-th chain Total number of chains of G WCET of Γi Utilization of Γi Period of the head timer-driven node of Γi

RD-Gen reduces implementation effort through the automatic setting of complex parameters and batch generation of random DAG sets. The remainder of the paper is organized as follows. Section II describes a system model. Section III explains the design and implementation of RD-Gen. Section IV presents case studies. Section V compares RD-Gen with existing random DAG generation methods. Section VI discusses related work. Finally, Section VII presents the conclusions and future work. II. S YSTEM MODEL This section describes the system model of this paper. The overview of this paper is shown in Fig. 1. First, Section II-A describes the basic single-rate DAG. Next, Section II-B presents a multi-rate DAG in which all nodes are timerdriven nodes. Finally, Section II-C explains multi-rate DAGs consisting of timer-driven and event-driven nodes found in self-driving systems. For clarity, a multi-rate DAG consisting of only timer-driven nodes is simply called a multi-rate DAG, while a DAG consisting of a chain of timer-driven and eventdriven nodes is called a chain-based DAG hereafter. The DAG notations in this paper are listed in Table I. •

A. Single-rate DAG Single-rate DAGs are DAGs with either a single source node or, all source nodes entering at the same time. A DAG consists of a node set and an edge set, denoted G = (V, E). Nodes represent tasks in the system, and edges represent communication and dependencies between nodes and precedence constraints. V is the set of all nodes, expressed as V = {v1 , ..., v|V | }, where |V | is the total number of nodes. Each node has a worst-case execution time (WCET), and the WCET of vi is denoted as Ci . E is the set of all edges, where each edge ei,j ∈ E represents communication between vi and vj and a precedence constraint. When ei,j exists in the DAG, vj cannot be executed until vi has completed its execution and the output of vi has arrived. If the communication time is given as an assumption, the communication time at ei,j is denoted as commi,j . The ratio of the sum of the communication times of all edges to the sum of the execution times of all nodes is called the communication-to-computation ratio (CCR) and is P commi,j defined by Eq. (1). CCR =

ei,j ∈E

P

Ci

(1)

vi ∈V

An end-to-end deadline D(G) is set at the sink node when the safety of hard real-time systems [18] or the cloud computing the quality of service [19] must be guaranteed. B. Multi-rate DAG Multi-rate DAGs are DAGs consisting of timer-driven nodes that operate at different periods. In multi-rate DAGs, while the basic definitions of node and edge are the same as in those given in Section II-A, the meaning of edge is different. Edges indicate communication between nodes using shared memory, where each node reads data at the start of execution and writes data at the end of execution [2], [4], [6]. Although undersampling and oversampling occur due to differences in periods, the latest data are used according to last-is-best semantics [4]. Each timer-driven node in such multi-rate DAGs is denoted by vitd , and vitd is characterized by the tuple (ϕi , Ci , Ti , Di ), where ϕi , Ci , Ti , and Di represent the offset, the WCET, the period, and the relative deadline respectively. Relative deadlines are called implicit deadlines when Ti = Di , constrained deadlines when Ti < Di , and arbitrary deadlines when Di is independent of Ti . The utilization of vitd is denoted as ui , such that ui = Ci /Ti . The P total utilization U of a multi-rate DAG is defined by U = vtd ∈V ui . i

C. Chain-based DAG A chain-based DAG is a DAG consisting of chains of multiple event-driven nodes connected to a head timer-driven node, as shown in the left side of Fig. 2. There are two types of nodes in the chain-based DAG: (i) timer-driven nodes that are triggered at predetermined periods, denoted by vitd , and (ii) event-driven nodes that are triggered by receiving data from predecessor nodes, denoted by vied . The definition of timerdriven nodes is the same as in Section II-B. ed Each chain Γi is denoted as Γi = {vitd , vked , ..., v|Γ }, where i| |Γi | is the number of nodes that compose Γi . The head vitd

【Legend】

：Timer-driven node ：Event-driven node

Chain-based DAGs (a) Chains are merged

Chain Triggered periodically by �mer

trigger

(b) Chain is branched

trigger (c) Chains are ver�cally linked

Seed: 0 Number of DAGs: 100 Graph structure: Generation method: Fan−in/Fan−out Number of nodes: Combination: [10, 20] In−degree: Random: (start=1, stop=3, step=1) Out−degree: Random: (1, 3, 1) Number of entry nodes: Combination: [1, 3] Number of exit nodes: Fixed: 1

【Legend】

DAGs

NN：Number of nodes NEN：Number of entry nodes

NN_10_NEN_1 dag_1.yaml dag_1.eps ・ ・ ・

NN_10_NEN_3 dag_1.yaml dag_1.eps ・ ・ ・

NN_20_NEN_1 dag_1.yaml dag_1.eps ・ ・ ・

NN_20_NEN_2

Fig. 2. Chain-based DAGs.

in the chain is triggered periodically, and subsequent eventdriven nodes vked are triggered by their direct predecessors. This definition is the same as that used in existing studies [20]. The WCET of Γi is denoted by CΓi and defined by CΓi = P vj ∈Γi Cj . Because the chain is executed in a manner dependent on the period of the head timer-driven node, the utilization of the C chain uΓi is calculated in uΓi = TΓΓi . i Here, TΓi is the period of the head timer-driven node vitd of the chain. ThePtotal utilization of the chain-based DAG is defined by U = Γi ∈V uΓi . Chain-based DAGs primarily exist in robot operating system (ROS)-based and AUTOSAR-adaptive systems [3], [21]. In a typical ROS-based system, such as a self-driving system, different sensor data are processed and merged by multiple chains to output the final command. When modeling ROSbased systems as DAGs, it is necessary to consider DAGs in which multiple chains merge ((a) in Fig. 2), where the chain branches ((b) in Fig. 2), and those in which multiple chains are vertically linked ((c) in Fig. 2). When an event-driven node has multiple predecessor nodes, as in (a) in Fig. 2, the node is triggered when the data from all the predecessor nodes are available. III. D ESIGN AND IMPLEMENTATION This section describes the design and implementation of RD-Gen. RD-Gen iterates over the construction of the graph and the set of properties for all parameter combinations described by the user in the configuration file as shown in the upper right of Fig. 1. RD-Gen is an open-source tool and is publicly available1 . A. Common Functionality RD-Gen receives as input a YAML file written by the user, and with a single command, RD-Gen generates an entire set of random DAGs with different parameter combinations. An example of an input parameter file in the YAML format is shown on the left side of Fig. 3. Because RD-Gen allows the user to specify seed values for pseudo-random number generation (the Seed parameter in Fig. 3), the same random DAG set can be generated by entering the same YAML file into RD-Gen. Number of DAGs in Fig. 3 indicates the number of DAGs randomly generated for each combination. The shape 1 https://github.com/azu-lab/RD-Gen

Properties: Execution time: Random: (1, 50, 1)

dag_1.yaml dag_1.eps ・ ・ ・

Fig. 3. Example of generating all combinations.

of the generated DAGs is determined by the parameters under Graph structure, and the properties of the nodes and edges are determined by the parameters under Properties. For parameters that require a numeric input, users can specify values in the following three ways. 1) Fixed: Only one value is specified, and this value is always used when a DAG is generated. This specification method can be used for DAGs in which end-to-end deadlines are considered, and one sink node is always desired, as in the Number of exit nodes parameter in Fig. 3. 2) Random: When a DAG is generated, one value is randomly selected using uniform distribution from an input range. This is the most basic specification method that is used when there is no special intended value and when it is desirable to have a variety of values, as shown in the In-degree, Out-degree, and Execution time parameters in Fig. 3. 3) Combination: RD-Gen generates DAGs for all combinations of all lists of parameters for which Combination is specified. This specification method allows all DAG sets used in random evaluations in DAG studies to be generated in single command execution. Therefore, RD-Gen can significantly reduce the time and effort required by researchers to generate DAGs. For example, when Combination of Number of nodes is [10, 20] and Combination of Number of source nodes is [1, 3], RD-Gen generates 100 DAGs for each combination, as shown on the right side of Fig. 3. When specifying ranges for Random and Combination in RD-Gen, the following two intuitive descriptions are possible. 1) List format: The user specifies their choices in a list (array) format (such as [10, 20] for Number of nodes in Fig. 3). 2) Tuple format: The user specifies a start value, a stop value, and a step (such as (start=1, stop=3, step=1) for In-degree in Fig. 3). The tuple format is internally expanded into a list format of values that are sequentially added from the start value to the stop value at an interval of size step (e.g., (start=1, stop=3, step=1) expands to a list of [1, 2, 3]). Here, “start=,” “stop=,” and “step=” are optional, as in Out-degree in Fig. 3.

TABLE II A LL PARAMETERS OF THE Graph structure IN RD-G EN Generation methods

Parameters Number of nodes Number of source nodes Number of sink nodes Ensure weakly connected In-degree Out-degree Probability of edge existence Number of chains Main sequence length Number of sub sequences Number of source nodes

Fan-in/Fan-out G(n, p) Fan-in/Fan-out G(n, p)

Vertically link chains

Chain-based

Main sequence tail Sub sequence tail Number of sink nodes

Merge chains

Middle of chain Sink node

Descriptions Number of nodes in a single DAG Number of source nodes in a single DAG Number of sink nodes in a single DAG When True is specified, the generated DAGs are always weakly connected Number of edges input to one node Number of edges output from one node Probability of an edge presents between any nodes Number of chains in a single chain-based DAG Length of the main sequence in a single chain Number of branches from the main sequence in a single chain Number of source nodes in a single DAG When True is specified, the tail of the main sequence is randomly connected to the head of another chain When True is specified, the tail of the sub sequence is randomly connected to the head of another chain Number of sink nodes in a single DAG When True is specified, merge from a tail node of a random chain to a node other than the head and tail of another chain When True is specified, merge a head node of a random chain with the sink node

TABLE III H ELPER FUNCTIONS IN THE ALGORITHMS Symbols Random(a, b) | a, b ∈ N In(vi ) Out(vi ) Sequence({vi , ..., vk })

Descriptions Function that returns a random natural number between a and b. Function that returns the in-degree of vi Function that returns the out-degree of vi Function that returns a linear sequence of nodes connected by edges consisting of input nodes. For example, when the input is {v1 , v2 , v3 }, it returns {v1 , e1,2 , v2 , e2,3 , v3 }.

RD-Gen can output DAG description files in the YAML, JSON, XML, and DOT formats. The DOT format is a plain text format used in Graphviz that allows a simple description of graph structure and properties associated with nodes and edges. EPS, PDF, SVG, and PNG formats can be specified for the DAG images output by RD-Gen. B. Graph Construction RD-Gen extends the Fan-in/Fan-out [7] and G(n, p) [8] methods widely used in the scheduling field by DAG researchers. In addition, RD-Gen provides a Chain-based method for generating state-of-the-art chain-based DAGs as shown in Fig. 2. The Chain-based method is a new method proposed in this paper to generate chain-based DAGs with flexibility. The parameters that can be specified in the Graph structure of RD-Gen are listed in Table II. 1) Fan-in/Fan-out Method: Fan-in/Fan-out is a random DAG generation method proposed by Dick et al. that is provided by TGFF [7]. The Fan-in/Fan-out method can specify the in-degree (i.e., the number of edges to be input) and outdegree (i.e., the number of edges to be output) ranges for a single node; a DAG is then generated in which all nodes satisfy this condition. The Fan-in/Fan-out method extends the graph by randomly repeating the Fan-in and Fan-out phases. However, the original Fan-in/Fan-out method cannot completely satisfy the requirements of researchers using DAGs. The DAG generated by the Fan-in/Fan-out method has just one source node, while in-vehicle and self-driving systems have multiple sensors [6], [11] and require a DAG with multiple source nodes. Even though the latest version of TGFF allows multiple source nodes, it may generate DAGs that are not weakly connected. Weakly connected graphs are

Algorithm 1: Fan-in/Fan-out method in RD-Gen Input: n ← Number of nodes nsnk ← Number of source nodes nsrc ← Number of sink nodes id ← In-degree od ← Out-degree Output: A DAG that satisfies user-specified parameters 1 Initialize G ← (V, E), with V ← {v1 , ..., vnsnk } and E ← {∅} 2 while |V |̸= n − nsrc do 3 if Random(0, 1) = 1 then /* Fan-in phase */ 4 S ← Set of nodes in V whose out-degree is less than or equal to od 5 r ← Random(1, id) 6 T ← Randomly choose r nodes from S 7 V ← V ∪ {v|V |+1 } 8 foreach vi ∈ T do 9 E ← E ∪ {ei,|V | } 10 end 11 end 12 else /* Fan-out phase */ 13 vi ← The node with the largest difference between od and its out-degree in V 14 dif f ← od − Out(vi ) 15 r ← Random(1, dif f ) 16 for k ← |V |+1 to |V |+r + 1 do 17 V ← V ∪ {vk } 18 E ← E ∪ {ei,k } 19 end 20 end 21 if |V |> n − nsrc then 22 Initialize G ← (V, E), with V ← {v1 , ..., vnsnk } and E ← {∅} 23 end 24 end 25 G ← add sink nodes(G, nsrc) 26 G ← weakly connect(G) 27 return G

Algorithm 2: add sink nodes(G, nsrc) Input: G: A DAG, nsrc: Number of sink nodes Output: DAG with sink nodes added 1 N SRC ← {v|V |+1 , ..., v|V |+nsrc+1 } 2 CEX ← Set of current sink nodes of G 3 while ∃n ∈ N SRC, In(vn ) = 0 ∨ ∃c ∈ CEX, out(vc ) = 0 do 4 vi ← The node with the smallest out-degree in CEX 5 vj ← The node with the smallest in-degree in N SRC 6 E ← E ∪ {ei,j } 7 end 8 V ← V ∪ N SRC 9 return G

graphs that any two nodes are reachable without regard to the orientation of the edges, and DAGs that are not weakly connected are separated. Therefore, such DAGs may cause

Algorithm 3: weakly connect(G) Input: G: A DAG Output: A weakly connected DAG 1 while G is not weakly connected do 2 M C ← Weakly connected component with the maximum number of nodes in G 3 RC ← Randomly selected a weakly connected component other than M C 4 vi ← Randomly choose one of the sink nodes in RC 5 vj ← Randomly choose one node other than source nodes in MC 6 E ← E ∪ {ei,j } 7 end 8 return G

unintended evaluation results and must be avoided. It is also necessary to be able to specify the number of sink nodes because many studies consider DAGs with a single sink node [14], [19]. In addition, because scheduling and allocation methods using DAGs affect the performance depending on the number of nodes in a DAG, evaluations are performed with various changes in the number of nodes [1]. However, TGFF does not allow a user to completely control the number of nodes to be generated in a DAG. To meet these requirements, RD-Gen allows the specification of the number of nodes, source nodes, and sink nodes in a single DAG and ensures that the DAG is weakly connected. The Fan-in/Fan-out method procedure provided by RD-Gen is shown in Algorithm 1, and the helper functions used in the algorithms are listed in Table III. First, the DAG is initialized with a specified number of source nodes (line 1 in Algorithm 1). RD-Gen then iteratively expands the graph until the number of nodes fits within a user-specified value (line 2 in Algorithm 1). Next, the graph is randomly extended in the Fan-in phase or Fan-out phase (lines 3–20 in Algorithm 1). If the number of nodes exceeds the user-specified value, the DAG is initialized (lines 21–23 in Algorithm 1). After the loop ends, the add sink nodes function is called, and nodes with no output edges are merged into a user-specified number of sink nodes with the minimum number of edges (Algorithm 2). Finally, the weakly connect function is called to add edges until the DAG is weakly connected (Algorithm 3). With these extensions, the Fan-in/Fan-out method implemented by RDGen allows the user to fully control the number of nodes, source nodes, and sink nodes in a single DAG and guarantees that the DAG is weakly connected. 2) G(n, p) Method: G(n, p) is a well-known graph construction method proposed by Paul Erdős, and Alfréd Rényi et al. [8] that constructs a graph according to the number of nodes and the probability of an edge existing between any two nodes. Many of the random DAG sets used in evaluations in the latest studies using DAGs have been constructed based on the G(n, p) method [5], [16], [17]. However, there are problems with the original G(n, p) method, such as the possibility of a cycle in a graph and the inability to guarantee that the graph is weakly connected. Accordingly, in RD-Gen, the G(n, p) method is extended for direct use in the evaluation of DAG studies. The procedure for the G(n, p) method in RD-Gen is shown in Algorithm 4. First, nodes other than the source and sink nodes are added to the graph (lines 1 and 2 in Algorithm 4). Then, for any two nodes,

Algorithm 4: G(n, p) method in RD-Gen Input: n ← Number of nodes p ← probability of edge existence nsnk ← Number of source nodes nsrc ← Number of sink nodes Output: A DAG that satisfies user-specified parameters 1 n ← n − nsnk − nsrc 2 Initialize G ← (V, E), with V ← {v1 , ..., vn } and E ← {∅} 3 for i ← 1 to |V | do 4 for j ← 1 to |V | do 5 if (Random(0, 100) ≤ p ∗ 100) ∧ i < j then 6 E ← E ∪ {ei,j } 7 end 8 end 9 end /* Add source nodes */ 10 N SN K ← {v|V |+1 , ..., v|V |+nsnk+1 } 11 CEN ← Set of current source nodes of G 12 while ∃n ∈ N SN K, Out(vn ) = 0 ∨ ∃c ∈ CEN , in(vc ) = 0 do 13 vi ← The node with the smallest in-degree in CEN 14 vj ← The node with the smallest out-degree in N SN K 15 E ← E ∪ {ei,j } 16 end 17 V ← V ∪ N SN K 18 G ← add sink nodes(G, nsrc) 19 G ← weakly connect(G) 20 return G

Algorithm 5: Chain-based method in RD-Gen Input: nc ← Number of chains ml ← Main sequence length ns ← Number of sub sequences nsnk ← Number of source nodes nsrc ← Number of sink nodes Output: A DAG that satisfies user-specified parameters 1 Initialize G ← (V, E), with V ← {∅} and E ← {∅} /* Construct each chain */ 2 for i ← 1 to nc do 3 main ← Sequence({v|V |+1 , ..., v|V |+ml+1 }) 4 G ← main 5 for j ← 1 to ns do 6 r ← Random(|V |+1, |V |+ml) 7 sl ← Random(1, ml − r) 8 sub ← Sequence({v|V |+1 , ..., v|V |+sl+1 }) 9 E ← E ∪ {er,|V |+1 } 10 G ← sub 11 end 12 end /* Vertically link chains */ 13 while Number of source nodes of G ̸= nsnk do 14 vi ← Randomly choose one of the sink nodes in V 15 vj ← Randomly choose one node from the head of the chains 16 E ← E ∪ {ei,j } 17 end /* Merge chains */ 18 while Number of sink nodes of G ̸= nsrc do 19 vi ← Randomly choose one of the sink nodes in V 20 vj ← Randomly choose one node from other than the head of the chains 21 E ← E ∪ {ei,j } 22 end 23 return G

the addition of an edge is tried with 50% probability. Here, if the index of the destination node is smaller than the index of the source node, the edge addition is canceled (line 5 in Algorithm 4). This condition results in no cycles being present in the graph [16]. After the loop ends, a user-specified number of source nodes and a node with an in-degree of zero are connected with the smallest edge. Finally, the add sink nodes and weakly connect functions are called in the same manner as in the Fan-in/Fan-out method.

TABLE IV A LL PARAMETERS OF Properties IN RD-G EN Parameters Execution time Communication time CCR End-to-end deadline

Multi-rate

Additional properties

Output formats

Ratio of deadline to critical path Periodic type Period Source node period Sink node period Offset Total utilization Maximum utilization Node properties Edge properties YAML JSON DAG XML DOT Draw legend PNG Figure SVG EPS PDF

Descriptions Execution time of nodes Communication time of edges CCR of a single DAG Ratio of the end-to-end deadline to the critical path of DAG Specify a group of nodes to be timer driven Period of timer-driven nodes Period of source timer-driven nodes Period of exit timer-driven nodes Offset of timer-driven nodes Total utilization of a single DAG Maximum utilization of one timer-driven node User-defined numeric parameters with any name for nodes User-defined numeric parameters with any name for edges

Main sequence (i.e., Maximum hops path in this chain)

𝜏1

𝜏2

Number of sub sequences: 1

𝜏5

𝜏3

Main sequence length: 4

【Legend】

：Event-driven node ：Timer-driven node

𝜏4

Outputs DAG description files in the format specified by True If True, a legend is drawn on the output DAG figure

Fig. 4. Example of parameters that determine the shape of a single chain.

Outputs DAG figures in the format specified by True

3) Chain-based Method: The Chain-based method designed is a new random DAG generation method proposed in this paper to meet the requirements of modern chain-based DAGs. The Chain-based method can easily and reproducibly generate chain-based random DAGs used to evaluate existing studies [3], [20]. In the Chain-based method, multiple chains are combined to construct a single DAG. The parameters that determine the shape of a single chain are explained here using Fig. 4. The user can determine the shape of a given chain by specifying the main sequence length and the Number of subsequences. The main sequence is the path that has the largest number of hops from the head timer-driven node to the tail event-driven node in a single chain ({v1 , v2 , v3 , v4 } in Fig. 4), and subsequences are straight lines of nodes branching off from the main sequence ({v5 } in Fig. 4). In the Chain-based method, two different ways of connecting chains can be specified. The first is to link chains vertically, i.e., the event-driven node at the end of each chain is randomly connected to the timer-driven node at the head of another chain (e.g., (c) in Fig. 2). The second method is to merge multiple chains into one specific node. The Chain-based method allows nodes other than the head node of the chain to be specified as integration nodes, and the event-driven node at the tail of each chain is merged into a randomly selected integration node (e.g., (a) in Fig. 2). The procedure for the Chain-based method is shown in Algorithm 5. First, chains are constructed for the Number of chains specified by the user (lines 2–12 in Algorithm 5). In the construction of each chain, the main sequence is generated (lines 3 and 4 in Algorithm 5). Subsequences branch from random nodes other than the tail of the main sequence and are coordinated to not exceed the length of the main sequence (lines 6–10 in Algorithm 5). After all the chains are constructed, the chains are linked vertically until the number of source nodes in the DAG is equal to the user specification (lines 13–17 in Algorithm 5). Finally, the chain is randomly merged until the number of sink nodes in the DAG matches the specified number (lines 18–22 in Algorithm 5). Consequently, the Chain-based method can flexibly construct DAGs consisting of multiple chains.

Algorithm 6: Set properties based on the total utilization Input: G ← DAG pt ← Periodic type U ← Total utilization p ← Period Output: A DAG that satisfies user-specified parameters 1 if pt = “All” then 2 u[1, ..., |V |] ← UUniFast(|V |, U ) [22] 3 for i ← 1 to |V | do 4 Ti ← p 5 Ci ← u[i] × Ti 6 end 7 end 8 else if pt = “Chain” then 9 u[1, ..., |Γ|] ← UUniFast(|Γ|, U ) 10 for i ← 1 to |Γ| do 11 TΓi ← p 12 CΓi ← u[i] × TΓi 13 g ← Number of nodes in Γi 14 c[i, ..., i + g] ← Grouping randomly into g with total equal to CΓi 15 for j ← i to i + g do 16 Cj ← c[j] 17 end 18 end 19 end 20 return G

C. Property Setting RD-Gen automatically sets the typical properties that characterize the nodes and edges of a DAG to meet the user requirements. All of the properties that can be set automatically in RD-Gen are listed in Table IV. RD-Gen can generate (i) single-rate DAGs, (ii) multi-rate DAGs, and (iii) chainbased DAGs depending on the Periodic type parameter. If the Periodic type is not specified, DAGs of type (i) are generated; if the Periodic type is “All” DAGs of type (ii) are generated, and if the Periodic type is “Chain” DAGs of type (iii) are generated. Periodic type “Chain” can only be used in the chain-based method. Here, even in a graph constructed by a chain-based method, all nodes can be timer-driven nodes if Periodic type “All” is specified. This design is intended to improve the flexibility of RD-GEN. In RD-Gen, all properties described in Section II can be specified using “Fixed,” “Random,” or “Combination.” Even though existing random DAG generation tools such as TGFF and GGen provide the functionality to randomly assign proper-

[0] C: 1

Seed: 0 Number of DAGs: 100

1

Graph structure: Generation method: Fan−in/Fan−out Number of nodes: Combination: (10, 1000, 10) In−degree: Random: [1, 2, 3] Out−degree: Random: [1, 2, 3] Number of entry nodes: Random: [1, 2, 3, 4, 5] Number of exit nodes: Fixed: 1 Ensure weakly connected: True

[2] C: 21

[0] C: 20

[3] C: 15

2

3

[6] C: 13

[1] C: 4

[2] C: 19

[4] C: 11

11

3

2

51

[1] C: 12 39

[5] C: 27 34

1

19

[7] C: 17 5

[8] C: 12

3

1

[4] C: 20

[9] C: 27

[3] C: 7

Number of nodes: 10, CCR: 1.0

Properties: Execution time: Random: (1, 30, 1) CCR: Combination: [0.1, 0.2, 0.5, 1.0, 2.0, 5.0, 10.0]

1

[5] C: 27

1

[8] C: 13

1

[6] C: 19

1

1

1

[0] C: 17

[7] C: 4

[2] C: 11 277

164

[8] C: 26

1

120

115

Number of nodes: 10, CCR: 0.1

[3] C: 22 1

[4] C: 24

65

[6] C: 12

[9] C: 3

Input YAML file

[1] C: 11

210

[5] C: 3 150

101

555

[7] C: 29 58

[9] C: 27

Number of nodes: 10, CCR: 10.0

Fig. 5. Example of generating a random DAG set with varying CCR, the number of nodes, the execution time, and the communication time using the Fan-in/Fan-out method. [0] C: 1 T: 87

Seed: 0 Number of DAGs: 100 Graph structure: Generation method: G(n, p) Number of nodes: Random: (10, 100, 10) Probability of edge: Random: (0.1, 0.9, 0.1) Number of entry nodes: Random: [1, 2, 3, 4, 5] Number of exit nodes: Random: [1, 2, 3, 4, 5] Ensure weakly connected: True Properties: Multi−rate: Periodic type: All Period: Random: (1, 100, 1) Total utilization: Combination: (0.05, 0.95, 0.05)

[0] C: 1 T: 66

[1] C: 1 T: 40

[3] C: 1 T: 48

[4] C: 1 T: 88

[2] C: 1 T: 96

[5] C: 3 T: 95

[6] C: 1 T: 88

[7] C: 1 T: 23

[8] C: 1 T: 10

[1] C: 3 T: 74

[6] C: 1 T: 77

[2] C: 1 T: 48

[3] C: 5 T: 45

[4] C: 3 T: 65

[7] C: 1 T: 32

[8] C: 1 T: 45

[9] C: 3 T: 20

Number of nodes: 10, Total utilization: 0.5 [0] C: 11 T: 98

[2] C: 2 T: 72

[9] C: 2 T: 73

[4] C: 7 T: 80

[6] C: 1 T: 28

[7] C: 1 T: 38

Number of nodes: 10, Total utilization: 0.3

Input YAML file

[5] C: 2 T: 26

[1] C: 5 T: 38

[3] C: 4 T: 82

[5] C: 2 T: 40

[8] C: 17 T: 61

[9] C: 11 T: 70

Number of nodes: 10, Total utilization: 0.95 Fig. 6. Example of generating multi-rate DAGs of various total utilization.

ties, they do not allow the user to control the values calculated by multiple properties such as CCR and the total utilization. Because CCR and the total utilization have a significant impact on the performance of the scheduling algorithms and the analysis methods, evaluations are performed by varying these values [1], [5]. Therefore, RD-Gen also supports the specification of such complex property values. An example of the property setting based on the total utilization in RD-Gen is shown in Algorithm 6. RD-Gen uses the UUniFast method [22] to set the utilization to each node in a uniform distribution (lines 2 and 9 in Algorithm 6). If the Periodic type is “All,” the utilization for each node is determined based on the Total utilization specified by the user, and the period and the execution time are set to satisfy this utilization (lines 1–7 in Algorithm 6). Here, when Maximum utilization is specified, RD-Gen allocates utilization to each node not to exceed Maximum utilization. To support unique implementations of existing studies [3], [20] with RD-Gen, this paper proposes an extension of the UUniFast method to chains. If the Periodic type is “Chain,” the utilization of each chain is determined based on the Total utilization, and the

period of each chain and the sum of the execution time are calculated accordingly (lines 8–12 in Algorithm 6). The total execution time is randomly divided by the number of nodes in the chain to set the execution time for each node (lines 13–17 in Algorithm 6). In this way, RD-Gen randomly and automatically sets properties according to complex parameters specified by the user. RD-Gen provides other parameters that allow for setting the ratio of the end-to-end deadlines to the critical path length and the period of source and sink nodes. In addition, users can define unique parameters for simple properties that randomly assign numerical values to nodes or edges. IV. C ASE S TUDY This section illustrates that RD-Gen can generate the random DAG sets used in the evaluation of existing studies based on DAGs. Case studies of a single-rate DAG, a multi-rate DAG, and a chain-based DAG are shown, respectively. 1) Case Study 1: Single-rate DAGs with Various CCR: Since CCR changes the nature of DAGs and affects the performance of scheduling algorithms, existing studies of single-rate

DAGs have used random DAG sets with different CCR values in their evaluations. An example of the generation in RD-Gen of a random DAG set with varying CCR, the number of nodes, the execution time, and the communication time using the Fan-in/Fan-out method as used in existing studies [23]–[25] is shown in Fig. 5. Because the Combination is specified for the Number of nodes and CCR in Fig. 5, RD-Gen generates 100 random DAGs each for all combinations of these parameters (i.e., {10, 20, 30, ..., 1000}×{0.1, 0.2, 0.5, 1.0, 2.0, 5.0, 10.0}). For each DAG, after graph construction, the execution time is randomly assigned to each node in the range of 1 to 30 (the Execution time parameter in Fig. 5). Then, the total communication time is calculated from the CCR and the sum of the execution time using Eq. (1), and the total communication time is randomly distributed to each edge. Thus, the user can generate all DAG sets used in the evaluation with a single command, without adjusting the number of nodes and CCR. 2) Case Study 2: Multi-rate DAGs with Various Total Utilization: Random DAG sets with different total utilization are used in the evaluation of most studies considering multi-rate DAGs. An example of generating a multi-rate DAG with a random period and the execution time for each node based on the total utilization of the DAG, as used in existing studies [12], [13], is shown in Fig. 6. Here, timer-driven nodes are drawn as squares. Because Combination is specified for Total utilization in Fig. 6, RD-Gen generates 100 DAGs for each 5% increment in total utilization from 5% to 95%. For each DAG, the utilization of each node is determined by the UUniFast method to satisfy the total utilization, and the execution time is calculated from the utilization and a randomly selected period from a uniform distribution ranging from 1 to 100. 3) Case Study 3: Chain-based DAGs with Various Total Utilization: In the evaluation of chain-based DAGs, a random DAG set is used with varying total utilization for the entire system and each chain. An example of generating a random DAG set, as used in existing studies [3], [20], in which the utilization of each chain is determined from the total utilization of the entire system, and the chain period and the execution time of each node is randomly assigned to satisfy the utilization of the chain is shown in Fig. 7. RD-Gen randomly sets the utilization of each chain using the UUniFast method to achieve a determined total utilization. Here, since Maximum utilization is specified as 1.0 in Fig. 7, RD-Gen never generates a chain with utilization greater than 1.0. The period of each chain is randomly set in the range of 50 to 1,000, and the execution time of each node is calculated based on the utilization and period (lines 10–18 in Algorithm 6). V. E VALUATION This section shows that compared to existing random DAG generation tools, RD-Gen can generate a random DAG set with fewer lines of code and no unique user implementation. Table V shows the processes that must be implemented by the user and the number of lines of code in our implementation. Here, the process in Table V is written in Python and shell

TABLE V P ROCESSES THAT MUST BE IMPLEMENTED BY THE USER Symbols (a) (b) (c) (d) (e) (f ) (g) (h) (i) (j) (k)

AND LINES OF CODE Processes Loop with different parameter values Separate DAGs generated for each parameter into directories Load .tgff file as DAG Construct a DAG using G(n, p) method Construct a DAG using chain-based method Merge the sink nodes to a specific number Add edges to be weakly connected Set the properties randomly within a specific range Set the execution time for each node and the communication time for each edge based on the CCR Set the utilization for a multi-rate DAG consisting of only timer-driven nodes (lines 1–7 in Algorithm 6) Set the utilization for a chain-based DAG (lines 8–19 in Algorithm 6)

Lines of code 3 5 40 10 80 10 15 10 25 30 50

TABLE VI E FFORT REQUIRED TO GENERATE RANDOM DAG SETS FOR Case Study 1 [23]–[25] Lines of description for tool options TGFF [7]

6

GGen [8]

3

RD-Gen

20

Lines of code (a) × 2 + (b) + (c) + (f ) + (g) + (i) = 101 (a) × 2 + (b) + (g) + (i) = 51 0

TABLE VII E FFORT REQUIRED TO GENERATE RANDOM DAG SETS FOR Case Study 2 [12], [13] Lines of description for tool options TGFF [7]

-

GGen [8]

2

RD-Gen

20

Lines of code (a) + (b) + (d) + (g) + (j) = 63 (a) + (b) + (g) + (j) = 53 0

scripts, and the Python NetworkX library is used for processes related to DAGs. The amount of description required to generate a random DAG set for the case studies in Section IV-1 is shown in Table VI. In this case, while TGFF and GGen require the user to implement more than 50 lines, RD-Gen can generate all random DAG sets using only the tool’s functionality. Since TGFF and GGen do not have the functionality to generate DAGs with different parameter settings at once, the user must execute the generation command many times while changing the parameters, using shell scripts or other means. In contrast, RD-Gen generates DAGs with all parameter combinations by specifying Combination as a parameter and automatically divides them into directories. Although TGFF uses the Fanin/Fan-out method to construct DAGs, the .tgff files output by TGFF are in a proprietary format and require users to implement a reading process. Furthermore, since TGFF and GGen do not guarantee that the graph is weakly connected, users may unintentionally use a non-weakly connected DAG for evaluation. TGFF and GGen cannot specify parameters such as CCR that are calculated from multiple properties. Therefore, the CCR must be adjusted for the DAG set after it is generated. In RD-Gen, users can automate all of the above processes by inputting the YAML file as shown on the left side of Fig. 5. The effort required to generate a random DAG set for the case studies in Section IV-2 is shown in Table VII. TGFF does not support the G(n, p) method and multi-rate DAG. GGen allows properties to be randomly set to nodes or edges within a user-specified range after graph construction.

Seed: 0 Number of DAGs: 100 Graph structure: Generation method: Chain−based Number of chains: Random: [2, 3, 4, 5, 6, 7, 8, 9, 10] Main sequence length: Random: (2, 7, 1) Merge chains: Number of exit nodes: Random: [1, 2, 3, 4, 5] Middle of chain: False Exit node: True Properties: Multi−rate: Periodic type: Chain Period: Random: (50, 1000, 1) Total utilization: Combination: (0.5, 4.0, 0.5) Maximum utilization: Fixed: 1.0

[0] C: 50 T: 847

[2] C: 7 T: 691

[6] C: 12 T: 925

[11] C: 24 T: 358

[1] C: 37

[3] C: 30

[7] C: 18

[12] C: 6

[4] C: 44

[8] C: 12

[13] C: 2

[5] C: 51

[9] C: 1

[0] C: 68 T: 505

[17] C: 29 T: 83

[23] C: 2 T: 77

[18] C: 5

[24] C: 5

[1] C: 2

[6] C: 12 T: 474

[13] C: 95

[2] C: 13

[7] C: 1

[14] C: 47

[30] C: 106 T: 903

[19] C: 1

[25] C: 2

[3] C: 24

[8] C: 47

[32] C: 38 T: 249

[15] C: 18

[31] C: 107

[20] C: 16

[26] C: 5

[4] C: 1

[9] C: 63

[33] C: 89

[21] C: 13

[27] C: 1

[5] C: 98

[10] C: 77

[34] C: 6

[22] C: 4

[28] C: 20

[14] C: 2

[10] C: 15

[15] C: 3

[16] C: 8

[16] C: 47

[11] C: 40

Number of chains: 4, Total utilization: 0.5

Input YAML file

[12] C: 67 T: 293

[29] C: 1

Number of chains: 7, Total utilization: 4.0

Fig. 7. Example of generating chain-based DAGs of various total utilization. TABLE VIII E FFORT REQUIRED TO GENERATE RANDOM DAG SETS FOR Case Study 3 [3], [20] Lines of description for tool options TGFF [7]

-

GGen [8]

-

RD-Gen

22

Lines of code (a) + (b) + (d) + (k) = 138 (a) + (b) + (d) + (k) = 138 0

However, GGen does not allow users to specify the total utilization used in the evaluation of most studies that consider multi-rate DAGs. Therefore, the user has to go through the trouble of implementing such as lines 1–7 in Algorithm 6. In contrast, RD-Gen uses the UUniFast method to randomly and automatically set the period and the execution time for each node to meet the specified total utilization. The amount of description to generate a chain-based random DAG set, as in the case study in Section IV-3, is shown in Table VIII. Chain-based DAGs, which are considered in research on state-of-the-art self-driving systems, cannot be generated by the classic random DAG generation tools, TGFF and GGen. RD-Gen can generate a batch of random chainbased DAG sets with different total utilization without any user implementation by inputting a YAML file as shown in Fig. 7. The evaluation results demonstrated that RD-Gen could generate the random DAG sets used in the evaluation with only an intuitive YAML file description, regardless of the singlerate and multi-rate cases. Therefore, RD-Gen is a flexible evaluation platform that can be adapted to various requirements and provides reliability and reproducibility for the latest DAG studies. VI. R ELATED WORK This section describes existing random DAG generation tools and existing studies using random DAGs and compares them with RD-Gen. Table IX shows a comparison of RD-Gen with existing methods. A. Random DAG Generation Tools Random DAG generation tools provide reliability and reproducibility for evaluations of scheduling and latency analysis

TABLE IX RD-G EN VS. EXISTING METHODS TGFF [7] GGen [8] DAGEN [26] MRTG [27] Voronov et al. [16] Dong et al. [17] He et al. [5] Yang et al. [15] Gunzel et al. [12] Ueter et al. [13] Verucchi et al. [6] Klaus et al. [4] Kordon et al. [2] Tang et al. [20] Choi et al. [3] RD-Gen

RSD ✓ ✓ ✓ ✓

RMD

RCD

✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

RDT ✓ ✓ ✓ ✓

OCG

✓

✓

✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

✓

✓

RPU

✓

✓ ✓ ✓

✓ ✓ ✓

RSD: Random generation of single-rate DAGs RMD: Random generation of multi-rate DAGs RCD: Random generation of chain-based DAGs RPU: Random property settings based on total utilization RDT: Random DAG generation tool OCG: One-command batch generation of random DAGs

studies. TGFF [7] is the first tool proposed for this purpose and has been used to evaluate recent studies [28]–[30]. TGFF determines the shape of a DAG primarily by specifying either or both the maximum and minimum input degree and maximum (first) output degree for a single node (the Fan-in/Fan-out method). TGFF can quickly generate many DAGs, and the task set can be easily reproduced by other researchers by inputting the same parameters. However, TGFF was released in 1998 and has many problems, such as its output format (.tgff), which is difficult to handle, and it cannot generate multi-rate DAGs. GGen [8] is a unified implementation of classical task graph generation methods used in the scheduling domain. GGen allows the user to add properties such as the period and the communication time to nodes and edges after generating DAGs using a user-specified generation method. However, GGen does not allow constraints to be specified between different properties, such as implicit deadlines (i.e., the execution time of a node must not exceed its period). Therefore, users with such requirements must adjust these values themselves. Other random DAG generation tools such as DAGEN [26] and MRTG [27] have also been proposed. DAGEN generates

random workflow applications by specifying the node load balancing, edge connection probability, and workflow shape. MRTG is a random DAG generation tool with a module-based implementation for user extensibility. However, these tools are not capable of generating multi-rate DAGs. Conversely, RDGen can flexibly generate multi-rate DAGs of various types. In addition, RD-Gen can automatically set properties calculated by multiple values such as CCR and the total utilization. B. Unique Implementation of Random DAG Generation This section presents existing studies in which the authors generated random DAG sets to evaluate their own implemented algorithms and settings. Because there are no random DAG generation tools that can generate multi-rate DAGs by specifying the total utilization, as described in Section VI-A, most studies that consider multi-rate DAGs include unique implementations. In real-time systems such as in-vehicle systems and selfdriving systems, multi-rate DAGs consisting of only timerdriven nodes are considered. Many real-time system researchers use the G(n, p) method to construct DAGs and generate random task sets with different numbers of nodes, different total utilizations, and different periods [5], [16], [17]. While proprietary algorithms may be used to construct graphs, the approach is similar in that the utilization is determined using the UUniFast method, and the WCET value of the nodes is assigned based on the utilization and the periods [12], [13], [15]. In a multi-rate DAG, as considered in automotive systems, a period is randomly assigned to each node based on the period observed in the automotive application. Verucchi et al. [6] randomly extended the automotive benchmark proposed by BOSCH in the 2015 WATERS Challenge [31] to analyze the performance of their proposed method. Verucchi et al. randomly set the task period from the values [1, 5, 10, 20, 50, 100, 200, 1000] in milliseconds, as found in automotive applications, for DAG utilization. Klaus et al. [4] set the utilization, the period, and the number of nodes for each DAG node. Verucchi et al. and Klaus et al. create random task sets based on node chains consisting of only timerdriven nodes. RD-Gen can also generate chains consisting of only timer-driven nodes using the Chain-based method and by specifying the Periodic type as “All.” Using the Python NetworkX library, Kordon et al. [2] randomly set the period, the number of edges per task, the release time, and the number of source nodes for their DAG sets. RD-Gen can automatically set all combinations of the total utilization, periods, and the number of nodes as described above. Studies of chain-based DAGs, such as the latest ROS-based systems, have also been evaluated using random task sets. Tang et al. [20] allocated a value of the utilization to each chain based on the total utilization of the entire system and the number of chains and then assigned the utilization to the execution units in the chain. Choi et al. [3] similarly assigned a utilization value to each chain using the UUniFast method based on the total system-wide utilization. Multi-rate DAGs based on such chains can be generated flexibly with the Chain-

based method in RD-Gen. In addition, because RD-Gen allows the utilization to be automatically set based on the chain, researchers do not need to implement this functionality on their own. VII. C ONCLUSIONS In this paper, we have proposed a random DAG generator considering multi-rate applications for reproducible scheduling evaluation called RD-Gen that can generate both single-rate DAGs and state-of-the-art multi-rate DAGs. RD-Gen extended the existing random graph generation methods for DAGs and provided a new chain-based method. RD-Gen could automatically set complex properties such as CCR and the total utilization. Case studies indicated that RD-Gen could meet the requirements of DAG studies in a variety of problem settings. In future work, we plan to extend RD-Gen to cover additional graph generation methods and more complex properties. R EFERENCES [1] Debabrata Senapati, Arnab Sarkar, and Chandan Karfa. HMDS: A makespan minimizing DAG scheduler for heterogeneous distributed systems. TECS, 20(5s), 2021. [2] Alix Kordon and Ning Tang. Evaluation of the age latency of a real-time communicating system using the LET paradigm. In Proc. of ECRTS, 2020. [3] Hyunjong Choi, Yecheng Xiang, and Hyoseung Kim. PiCAS: New design of priority-driven chain-aware scheduling for ROS2. In Proc. of RTAS, 2021. [4] Tobias Klaus, Matthias Becker, Wolfgang Schröder-Preikschat, and Peter Ulbrich. Constrained data-age with job-level dependencies: How to reconcile tight bounds and overheads. In Proc. of RTAS, 2021. [5] Qingqiang He, Mingsong Lv, and Nan Guan. Response time bounds for DAG tasks with arbitrary intra-task priority assignment. In Proc. of ECRTS, 2021. [6] Micaela Verucchi, Mirco Theile, Marco Caccamo, and Marko Bertogna. Latency-aware generation of single-rate DAGs from multi-rate task sets. In Proc. of RTAS, 2020. [7] R. P. Dick, D. L. Rhodes, and W. Wolf. TGFF: task graphs for free. In Proc. of Workshop on CODES/CASHE, 1998. [8] Daniel Cordeiro, Grégory Mounié, Swann Perarnau, Denis Trystram, Jean-Marc Vincent, and Frédéric Wagner. Random graph generation for scheduling simulations. In Proc. of SIMUTools, 2010. [9] Penghao Sun, Zehua Guo, Junchao Wang, Junfei Li, Julong Lan, and Yuxiang Hu. Deepweave: Accelerating job completion time with deep reinforcement learning-based coflow scheduling. In Proc. of IJCAI, 2021. [10] Chun-Hsian Huang. HDA: Hierarchical and dependency-aware task mapping for network-on-chip based embedded systems. JSA, 108, 2020. [11] Liu Shaoshan, Yu Bo, Guan Nan, Dong Zheng, and Akesson Benny. Industry challenge. In Proc. of Industry Session (part of RTSS), 2021. [12] Mario Günzel, Niklas Ueter, and Jian-Jia Chen. Suspension-aware fixedpriority schedulability test with arbitrary deadlines and arrival curves. In Proc. of RTSS, 2021. [13] Niklas Ueter, Mario Günzel, Georg von der Brüggen, and Jian-Jia Chen. Hard real-time stationary GANG-scheduling. In Proc. of ECRTS, 2021. [14] Youngeun Cho, Dongmin Shin, Jaeseung Park, and Chang-Gun Lee. Conditionally optimal parallelization of real-time DAG tasks for global EDF. In Proc. of RTSS, 2021. [15] Kecheng Yang and Zheng Dong. Mixed-criticality scheduling in compositional real-time systems with multiple budget estimates. In Proc. of RTSS, 2020. [16] Sergey Voronov, Stephen Tang, Tanya Amert, and James H Anderson. AI meets real-time: Addressing real-world complexities in graph responsetime analysis. In Proc. of RTSS, 2021. [17] Zheng Dong and Cong Liu. An efficient utilization-based test for scheduling hard real-time sporadic DAG task systems on multiprocessors. In Proc. of RTSS, 2019.

[18] Atsushi Yano and Takuya Azumi. Work-in-progress: Reinforcement learning-based DAG scheduling algorithm in clustered many-core platform. In Proc. of RTSS, 2021. [19] Longxin Zhang, Liqian Zhou, and Ahmad Salah. Efficient scientific workflow scheduling for deadline-constrained parallel tasks in cloud computing environments. J. Inf. Sci., 531, 2020. [20] Yue Tang, Zhiwei Feng, Nan Guan, Xu Jiang, Mingsong Lv, Qingxu Deng, and Wang Yi. Response time analysis and priority assignment of processing chains on ROS2 executors. In Proc. of RTSS, 2020. [21] Atsushi Yano and Takuya Azumi. Multi-rate cluster scheduling method for mixed timer-driven and event-driven DAG tasks. IEEE Access, 2021. [22] Enrico Bini and Giorgio C Buttazzo. Measuring the performance of schedulability tests. J. Real-Time Syst., 30(1), 2005. [23] Saroja Subbaraj, Revathi Thiagarajan, and Madavan Rengaraj. Multiobjective league championship algorithm for real-time task scheduling. J. Neural. Comput. Appl., 32(9), 2020. [24] Jing Liu, Kenli Li, Dakai Zhu, Jianjun Han, and Keqin Li. Minimizing cost of scheduling tasks on heterogeneous multicore embedded systems. TECS, 16(2), 2016. [25] Hafiz Fahad Sheikh and Ishfaq Ahmad. Sixteen heuristics for joint optimization of performance, energy, and temperature in allocating tasks to multi-cores. TOPC, 3(2), 2016. [26] DI George Amalarethinam and GJ Joyce Mary. DAGEN-a tool to generate arbitrary directed acyclic graphs used for multiprocessor scheduling. IJRIC, 2011. [27] Mishra Ashish, Sharma Aditya, Verma Pranet, Abhijit R Asati, and Raju Kota Solomon. A modular approach to random task graph generation. Indian J. Sci. Technol., 8, 2016. [28] Julius Roeder, Benjamin Rouxel, Sebastian Altmeyer, and Clemens Grelck. Energy-aware scheduling of multi-version tasks on heterogeneous real-time systems. In Proc. of SAC, 2021. [29] Mahdi Mohammadpour Fard, Mahmood Hasanloo, and Mehdi Kargahi. Analytical program power characterization for battery depletion-time estimation. TECS, 20(2), 2021. [30] Chu-ge Wu, Wei Li, Ling Wang, and Albert Y Zomaya. An evolutionary fuzzy scheduler for multi-objective resource allocation in fog computing. J. Future Gener. Comput. Syst., 117, 2021. [31] Simon Kramer, Dirk Ziegenbein, and Arne Hamann. Real world automotive benchmarks for free. In Proc. of WATERS, 2015.

Related documents

• RD-Gen: Random DAG Generator Considering Multi-rate Applications for Reproducible Scheduling Evaluation#987794
• TimeMark: A Trustworthy Time Watermarking Framework for Exact Generation-Time Recovery from AIGC#13030
• BASIC Tools. BASIC Calendar Generator.#333115
• Incast-Free MoE Rate-Based Scheduling#410983
• Accurate Simulation of Distributed Training Jobs with Network Contention Modeling#1049022