Manar Qamhieh
email: manar.qamhiehsalous@univ-mlv.fr

Serge Midonnet
email: serge.midonnet@univ-mlv.fr

Simulation-Based Evaluations of DAG Scheduling in Hard Real-time Multiprocessor Systems

Keywords: J.7 [Computers in Other Systems]: Real time F.1.2 [Theory of Computation]: Computation by Abstract Devices-Parallelism and concurrency I.6.m [Simulation and Modeling]: Miscellaneous Real-time systems, hard real-time scheduling, parallel tasks, Directed Acyclic Graphs, global preemptive scheduling, DM and EDF scheduling algorithms

The scheduling of parallel real-time tasks on multiprocessor systems is more complicated than the one of independent sequential tasks, specially for the Directed Acyclic Graph (DAG) model. The complexity is due to the structure of DAG tasks and the precedence constraints between their subtasks. The trivial DAG scheduling approach is to directly apply common real-time scheduling algorithms on DAGs despite their lack of compatibility with the parallel model. Another scheduling approach, which is called the stretching method, aims at transforming each parallel DAG task in the set into a collection of independent sequential threads that are easier to be scheduled.

In this paper, we are interested in analyzing global preemptive scheduling of DAGs using both approaches by showing that they are not comparable when associated with Deadline Monotonic (DM) and Earliest Deadline First (EDF) scheduling algorithms. Then we use extensive simulations to evaluate their schedulability performance. To this end, we use our simulation tool YARTISS to generate random DAG tasks with many parameter variations so as to guarantee reliable experimental results.

INTRODUCTION

Chip manufacturers are tending to build multi-processors and multi-core processors as a solution to overcome the physical constrains of the manufacturing process, such as chip's size and heating. Many practical examples of shifting towards multiprocessors can be found nowadays, such as the Intel Xeon processor with up to 18 cores and the 72-core processor from Tilera. Because of that, parallel programming has gained a higher importance although it has been used for many years. The concept of parallel programming is to write a code that can be executed simultaneously on different processors. Usually these programs are harder to be written than sequential ones, since it is necessary to keep the parallel partitions independent in order to execute them correctly on different processors at the same time.

From practical implementation's point of view, there exist certain libraries, APIs and models created specially for parallel programming like OpenMP [START_REF]OpenMP Application Program Interface version 3.1[END_REF] and POSIX threads [START_REF]POSIX threads programming[END_REF]. In this paper, we are interested in a particular family of parallelism called the inter-subtask parallelism, in which a parallel task consists of a collection of subtasks under precedence constraints. The most general model is the Directed Acyclic Graph (DAG) model, which is our task model in this paper.

In hard real-time systems, the correctness of results depends on the respect of certain timing parameters assigned to tasks. We consider that each task generates an unlimited number of jobs (copies) based on its timing parameters. A scheduler is responsible of choosing which job to execute on which processor at all times. The problem of hard realtime scheduling on uniprocessor and multiprocessor systems have been studied thoroughly for many years, and many researches and scheduling algorithms have been proposed for such platforms [START_REF] Davis | A Survey of Hard Real-time Scheduling Algorithms and Schedulability Analysis Techniques for Multiprocessor Systems[END_REF].

The extension of real-time scheduling w.r.t. parallel dependent tasks is not trivial. The real-time scheduler has to take into consideration the internal dependencies of tasks when it schedules them. For a given DAG task, the execution order of its subtasks is not known prior to the scheduling process, i.e., a subtask can start its execution when all of its predecessors have finished their own, and a subtask can execute either sequentially or in parallel with its siblings based on the decisions of the scheduler. To solve this problem, there are two DAG scheduling approaches that are presented in the state-of-the-art: the Direct scheduling and the Model Transformation approaches. The Direct Scheduling approach represents the parallel execution form of DAG tasks in which the scheduling process is done based on the internal dependencies of DAGs. The Model Transformation approach aims at converting the dependent parallel model of DAG tasks into independent sequential model so as to simplify its scheduling. The latter approach represents the sequential execution form of DAG tasks since it converts parallel tasks into sequential threads. Both approaches are used to determine the execution order to subtasks and they are associated with other real-time scheduling algorithms, such as Earliest Deadline First (EDF) and Deadline Monotonic (DM).

DAG scheduling approaches have been studied recently in many researches and schedulability analyses were provided. But they have never been compared to each other w.r.t. schedulability performance. In this paper, we show that both approaches are incomparable, i.e., there exist task sets that are schedulable using one scheduling approach while they are unschedulable when the other one is used, and vice versa. Due to this incomparability, we analyze their performance by performing extensive simulations. In this work, we consider global preemptive scheduling of periodic implicitdeadline DAGs on identical processors when EDF and DM algorithms are used. To the best of our knowledge, there is no similar analysis presented previously in the state-of-theart.

The remainder of this paper is organized as follows. Section 2 presents related works w.r.t. to the problem of scheduling real-time DAG tasks on multiprocessor systems. In Section 3, we introduce our task model. In Section 4, we describe in details the two DAG scheduling approaches and we prove their incomparability. Simulation results are provided in Section 5 to evaluate the performance of these scheduling algorithms with brief description of our simulation tool YARTISS. Finally, Section 6 concludes this work.

RELATED WORK

The scheduling of dependent real-time tasks of different models has been studied on both uniprocessor and multiprocessor systems. In uniprocessor systems which consists of a single processing unit, a dependent parallel task is transformed into a sequential chain, and subtasks are assigned local timing parameters which are used in the scheduling process (e.g., [START_REF] Harbour | Fixed Priority Scheduling Periodic Tasks with Varying Execution Priority[END_REF][START_REF] Richard | Contraintes de Precedences et Ordonnancement Monoprocesseur[END_REF][START_REF] Zhao | Worst-Case Response Time Analysis of Sporadic Graph Tasks with Fixed Priority Scheduling on a Uniprocessor[END_REF][START_REF] Jayachandran | Transforming Distributed Acyclic Systems into Equivalent Uniprocessors under Preemptive and Non-Preemptive Scheduling[END_REF][START_REF] Stigge | The Digraph Real-Time Task Model[END_REF]). The DAG model on uniprocessor systems was considered in [START_REF] Chetto | Dynamic Scheduling of Real-time Tasks Under Precedence Constraints[END_REF]. The authors proposed an algorithm to modify the timing parameters of DAGs (by adding intermediate offsets and deadlines to subtasks) in order to get rid of their internal dependencies.

In the case of multiprocessor systems, preemptive scheduling of jobs with precedence constraints has been proved NP-Hard in the strong sense in [START_REF] Ullman | NP-Complete Scheduling Problems[END_REF]. However, many researches targeted the scheduling of parallel tasks of different models, as in [START_REF] Han | Scheduling Parallelizable Jobs on Multiprocessors[END_REF][START_REF] Feitelson | A Survey of Scheduling in Multiprogrammed Parallel Systems[END_REF][START_REF] Kato | Gang EDF Scheduling of Parallel Task Systems[END_REF][START_REF] Goossens | Gang FTP Scheduling of Periodic and Parallel Rigid Real-time Tasks[END_REF][START_REF] Collette | Algorithm and Complexity for the Global Scheduling of Sporadic Tasks on Multiprocessors with Work-Limited Parallelism[END_REF]. Regarding the DAG model and as mentioned above, there are two approaches for its scheduling in hard real-time systems. The Direct Scheduling was introduced in [START_REF] Baruah | A Generalized Parallel Task Model for Recurrent Real-time Processes[END_REF], in which a taskset of a single sporadic DAG is scheduled on multiprocessor systems using EDF algorithm. The authors provided polynomial and pseudo-polynomial schedulability tests for EDF scheduling algorithm.

Later on, many works have considered the scheduling of multiple DAG tasks on multiprocessor systems, e.g., [START_REF] Bonifaci | Feasibility Analysis in the Sporadic DAG Task Model[END_REF][START_REF] Li | Analysis of Global EDF for Parallel Tasks[END_REF][START_REF] Li | Analysis of Federated and Global Scheduling for Parallel Real-Time Tasks[END_REF]. In these researches, the scheduling analyses are performed based on the general timing parameters of DAG tasks, such as their total Worst-Case Execution Time (WCET), deadline and critical path length. In [START_REF] Qamhieh | Global edf scheduling of directed acyclic graphs on multiprocessor systems[END_REF], the internal dependencies of DAGs and the execution order of their subtasks were included in the analysis of global EDF scheduling. A Subtask-Level scheduling of DAG tasks was proposed in [START_REF] Qamhieh | Schedulability analysis for directed acyclic graphs on multiprocessor systems at a subtask level[END_REF], in which scheduling decisions were taken based on the local timing parameters of subtasks rather than the timing parameters of DAGs.

The Model Transformation approach was introduced in [START_REF] Lakshmanan | Scheduling Parallel Real-Time Tasks on Multi-core Processors[END_REF], in which a stretching algorithm of Fork-Join (FJ) task model was proposed. The stretching algorithm avoided the parallel structure of FJ tasks by executing them as sequentially as possible. Then a DAG Stretching (DAG-Str) algorithm was proposed in [START_REF] Qamhieh | A Stretching Algorithm for Parallel Real-time DAG Tasks on Multiprocessor Systems[END_REF] to consider the general model DAG tasks. In the stretching algorithms, the DAG tasks are stretched up to their deadline and their dependent subtasks are transformed into a set of independent sequential threads. Intermediate offsets and deadlines are assigned to threads so as to determine their execution interval. In this paper, we analyze the schedulability performance of the DAG-Str algorithm when compared to Direct Scheduling approach of DAGs.

The Decomposition algorithm [START_REF] Saifullah | Multi-core Real-Time Scheduling for Generalized Parallel Task Models[END_REF][START_REF] Saifullah | Parallel Real-Time Scheduling of DAGs[END_REF] is another example of the Model Transformation approach for DAG tasks. It aims at distributing the slack time of each DAG task, which is the difference between its relative deadline and its minimum sequential execution time, on its subtasks. Accordingly, the subtasks are assigned intermediate offsets and deadlines which guarantee their independent execution.

TASK MODEL

We consider a taskset τ of n periodic parallel real-time Directed Acyclic Graph (DAG) tasks run on a system of m identical processors. The taskset τ is represented by {τ1, ..., τn}. Each DAG task τi, where 1 ≤ i ≤ n, is a periodic implicit-deadline graph which consists of a set of subtasks under precedence constraints. A DAG task τi is characterized by (ni, {1 ≤ j ≤ ni|τi,j}, Gi, Di), where ni is the number of its subtasks, the second parameter represents the set of subtasks of τi, Gi is the set of directed relations between these subtasks and Di is τi's relative deadline. Since each DAG task has an implicit deadline, its period Ti (interval time between its successive jobs) is the same as its deadline Ti = Di.

Let τi,j denote the j th subtask of the set of subtasks forming the DAG task τi, where 1 ≤ j ≤ ni. Each subtask τi,j is a single-threaded sequential task which is characterized by a WCET Ci,j. All subtasks respect the absolute deadline and period of their respective DAG. The total WCET Ci of DAG τi is defined as the sum of WCETs of its subtasks, where Ci = n i j=1 Ci,j. Let Ui denote the utilization of τi where Ui = Ci/Ti.

The directed relations Gi of DAG τi define the dependencies between its subtasks. A directed relation between subtasks τi,j and τ i,k means that τi,j is a predecessor of τ i,k , and the latter subtask have to wait for all of its predecessors to complete their execution before it can start its own. Sibling subtasks refer to subtasks that have the same predecessor subtask and they can execute independently in parallel. Figure 1 shows an example of a DAG task τ1 which consists of 7 subtasks. Precedence constraints are represented by directed arrows between subtasks. A source subtask is a subtask with no predecessors, e.g., subtasks τ1,1 and τ1,2. Respectively, a sink subtask is the one without any successors such as τ1,7.

Based on the structure of DAG tasks, the critical path of DAG τi is defined as the longest sequential execution path in the DAG when it executes on a virtual platform com- posed of unlimited number of processors. Its length Li is the minimum response time of the DAG. A subtask that is part of the critical path is referred to as a critical subtask, while non-critical subtasks are the remaining subtasks which execute in parallel with the critical ones. A slack time of a DAG τi is defined as the time difference between its relative deadline Di and its critical path length Li.

A DAG task is said to be feasible if subtasks of each job respect its absolute deadline. A taskset τ is deemed unfeasible when scheduled using any scheduling algorithm on m unit-speed processors if, at least, one of the following conditions is false:

∀τi ∈τ, Li ≤ Di U (τ ) = n i=1
Ui ≤ m

DAG SCHEDULING APPROACHES: PARALLEL VS. STRETCHING

A real-time scheduler is responsible for choosing which job to execute on which processor at all times. The priorities of executed jobs are determined by using a scheduling algorithm. A scheduling algorithm is referred to as global if it allows job migrations between processors of the system, and an algorithm is referred to as preemptive if it allows higher priority jobs to interrupt the execution of lower priority ones. A taskset is said to be schedulable w.r.t. a specific scheduling algorithm if all jobs in the set complete their execution before their absolute deadlines when this scheduling algorithm is used. Definition 1. A scheduling algorithm is said to be optimal if it is able to schedule all possible feasible task sets.

Despite that many optimal uniprocessor scheduling algorithms lose their optimality when applied on multiprocessor systems, these algorithms are widely used in many researches regarding the scheduling of parallel DAG tasks. In this paper, we consider two global preemptive scheduling algorithms, EDF from the fixed job priority assignment family and DM from fixed task family. Regarding EDF, it assigns priorities to jobs based on their absolute deadlines, i.e., the job with the earliest absolute deadline is assigned the highest priority. While DM assigns priorities to tasks based on their relative deadlines, in which the jobs with the earliest relative deadline, are assigned the highest priority. Hence, jobs of the same task are assigned the same priority.

In the case of independent sequential tasks, a scheduling algorithm assigns priorities to jobs based on the timing parameters of tasks, such as their deadline, period and slack time. However, the priority assignment of DAGs is more challenging. When a DAG job is assigned a priority by a scheduling algorithm, all of its subtasks inherit the same priority. Therefore, the scheduling algorithm has to determine the execution order of sibling subtasks of a DAG task, which are assigned the same priority and they execute independently. Hence, it is important to specify the default execution order of subtasks of DAGs before applying any scheduling algorithm by using the DAG scheduling approaches. In this section, we describe in details the Direct Scheduling approach (parallel execution form) and the DAG-Str algorithm (sequential execution form). Then we prove that both approaches are not comparable by providing scheduling examples.

Direct Scheduling Approach (Parallel

Structure)

The Direct Scheduling approach defines the default parallel structure of DAG tasks. It supports the inter-subtask parallelism of DAGs in which subtasks are assumed to execute as soon as possible when they are activated. According to this approach, a scheduling algorithm does not permit there to be any time at which a processor is idle and there is a subtask ready to execute. Hence, if there are idle processors in the system, all ready sibling subtasks of a DAG task are allowed to execute in parallel.

According to the Direct Scheduling approach, each subtask τi,j ∈ τi is characterized by an earliest offset Oi,j and a relative deadline Di,j. Both timing parameters determine maximum execution interval of the subtask and are calculated based on the precedence constraints of their DAG. The offset Oi,j refers to the earliest activation time of any job of subtask τi,j when its DAG τi executes on unlimited number of processors. Hence, predecessor subtasks of τi,j execute without any delay or interruption. If a DAG task is activated at time t, then subtask τi,j cannot be activated before time instant t + Oi,j.

Similarly, a relative deadline Di,j refers to the latest finish time of subtask τi,j that guarantees no deadline miss of the DAG. If DAG task τi is released at time t and subtask τi,j fails in finishing its execution at most at t + Di,j, then the remaining time before the deadline of the DAG at t + Di is not enough for the successors of τi,j to execute, even if unlimited number of processors is considered in the system2 . Figure 2 shows an example of the parallel structure of DAG task τ1 from Figure 1. We assume that DAG task τ1 has a deadline equal to 10 and it consists of 7 subtasks. As shown in Figure 2, source subtasks {τ1,1, τ1,2, τ1,3, τ1,5} are activated at time t = 0 and they are assumed to execute in parallel. Subtask τ1,4 is a successor of subtasks τ1,1 and τ1,2 and it has to wait for them both to finish execution before it starts its own, hence, its offset O1,4 is equal to 3. Its successor subtasks τ1,6 and τ1,7 have offset equal to 4. When we consider that DAG task τ1 has a deadline at t = 10, then sink subtasks τ1,6 and τ1,7 have to finish their execution at this time instant, and D1,6 = D1,7 = 10. However, subtask τ1,4 has to finish its execution no later than t = 8, so as to leave enough time for its successors to execute. Hence, the local deadline D1,4 of subtask τ1,4 is equal to 5, and its maximum execution interval is equal to [t + O1,4, t + D1,4).

In general, Direct Scheduling approach maintains the general characteristics of DAG tasks. Real-time algorithms take scheduling decisions that are compatible with the parallel structure of DAGs and their internal dependencies. However, the main disadvantage of this approach is that higher priority DAGs can be greedy by occupying multiple processors of the system for the execution of their parallel subtasks, while delaying the execution of lower priority subtasks. This scenario may cause deadline miss in the set.

DAG Stretching Approach (Sequential Structure)

By using the Model Transformation approach, the scheduling problem of DAG tasks is simplified by avoiding their parallel structure. For example, the DAG Stretching (DAG-Str) algorithm converts each DAG task into a sequence of segments, each consists of independent sequential threads. Briefly, the concept of the DAG-Str algorithm is that the slack time of stretched DAG is filled by non-critical subtasks, and the critical path of the DAG is stretched up to its deadline. The algorithm forces certain subtasks of the DAG to execute sequentially to form a master thread whose utilization is equal to 1. The remaining threads are assigned intermediate offsets and deadlines so as to execute independently. In order to maintain the precedence constraints of stretched DAGs and to avoid that threads of the same subtasks execute in parallel, the generated threads are assigned intermediate offsets and deadlines. In the scheduling process after applying the stretching algorithm, the fully stretched master threads can be assigned dedicated processors since their utilization is equal to 1, and the independent threads can be scheduled using any multiprocessor scheduling algorithm. Figure 3 shows an example of the DAG-Str algorithm when applied on DAG task τ1 from Figure 1. The critical path of the DAG consists of subtasks τ1,1, τ1,4 and τ1,6. In order to fill the slack time of the DAG, whose length is equal to 4, parts of subtask τ1,2 and subtask τ1,7 are forced to execute sequentially within the critical path. After stretching, DAG task τ1 is transformed into 5 sequential segments, where segment S1,1 contains two independent threads, and each one of segments S1,2 and S1,4 contains one independent thread. Intermediate offsets (respectively intermediate deadlines) of threads are represented by upward pointing ar- rows (respectively downward pointing arrows) on Figure 3. Further details about the DAG-Str algorithm can be found in [START_REF] Qamhieh | A Stretching Algorithm for Parallel Real-time DAG Tasks on Multiprocessor Systems[END_REF].

The Model Transformation approach simplifies the scheduling of DAG tasks by assigning intermediate offsets and deadlines to resulting threads, which are used by the scheduling algorithm. The internal dependencies of DAG tasks are eliminated at the expense of generality loss of model characteristics. In other words, the form of DAG tasks is altered because of the stretching algorithm, e.g., subtask τ1,2 from Figure 3 has to execute within the master thread and not in parallel even if there are available processors in the system.

Incomparability of Scheduling Approaches

In this section, we analyze the schedulability of parallel and stretching approaches of DAGs. We discuss the case of global preemptive scheduling when EDF and DM algorithms are used. In related researches, schedulability analyses of scheduling approaches were provided separately, and the results were never compared with each other. In this paper, we aim at analyzing the performance of these approaches w.r.t. schedulability of DAG sets.

In comparing DAG sets that are scheduled by two different approaches A and B, there are three possibilities: (i) A dominates B if all schedulable DAG sets according to B belong to the set of schedulable DAG sets according to A, (ii) A is equivalent to B if they schedule the exact same DAG sets and (iii) A and B are incomparable if there exist DAG sets that are schedulable according to A that are unschedulable according to B and vice versa.

By using two scheduling examples, we show that both DAG approaches are not comparable when associated with global preemptive EDF and DM algorithms. Then we evaluate their schedulability performance by extensive simulations. The incomparability of these scheduling approaches means that both approaches are acceptable for DAG scheduling and no one dominates the other w.r.t. DAG schedulability. To this end, we provide two examples to show the scheduling of a given DAG set on multiprocessor system using a global preemptive scheduling algorithm. In Example 1, we show that the DAG set is schedulable when the DAG-Str algorithm is used, while Direct Scheduling approach leads to a deadline miss. Then we show in Example 2 that Direct approach successfully schedules a DAG set which is unschedulable when DAG-Str algorithm is used. In both examples, we consider that EDF and DM algorithms are associated with the DAG scheduling approaches to assign priorities to

τ 1,1 τ 1,2 τ 1,5 L1 = 4 D1 -L1 = 2 τ 1,3 τ 1,4 0 6
(a) DAG task τ1 (parallel execution form). DAG task τ2 is shown in Inset 4(c). It consists of a single subtask τ2,1 which has a WCET equal to 6 and a deadline equal to 7. Since DAG τ2 is a sequential task, there is no difference between its parallel and sequential execution forms. The utilization of the DAG set U (τ ) is equal to 8 6 + 6 7 = 2.19 which means that it needs to execute on a platform of at least 3 unit-speed processors. In this example, we consider a platform of 3 processors.

τ 1,1 τ 1,2 τ 1,5 τ 1,1 τ 1,3 τ 2,1 τ 2,1 x τ 1,4 0
Priority Assignment:

If DM scheduling algorithm is considered, then jobs of DAG τ1 are assigned a higher priority than jobs of DAG τ2 because τ1 has a shorter relative deadline. In the case of EDF, if we consider a synchronous scenario in which both DAGs are released at time t = 0, then the first job of task τ1 has an absolute deadline at t = 6 while the first job of τ2 has an absolute deadline at t = 7. Hence, EDF assigns the first job of τ1 a higher priority than the job of τ2. According to this priority assignment, active jobs in the time interval [0, 7) have the same priorities according to EDF and DM algorithms.

Direct Scheduling Approach: The considered scheduling is done based on the parallel execution form of DAGs while considering the priority assignment of EDF and DM. As shown in Inset 4(d), the first job of τ1 executes without being interrupted since it has the highest priority. Its parallel subtasks {τ1,2, τ1,3, τ1,4} occupy the 3 processors of the system for 2 time units in time interval [START_REF]OpenMP Application Program Interface version 3.1[END_REF][START_REF] Baruah | A Generalized Parallel Task Model for Recurrent Real-time Processes[END_REF]. As a result, the execution of the first job of τ2 is interrupted and it is delayed for 2 time units. Since its slack is equal to 1 time unit, a deadline miss occurs.

Model Transformation Approach: Inset 4(e) shows the scheduling of the same DAG set when the DAG-Str gorithm is used. Based on the structure of stretched DAG τ1 from Inset 4(b), each job needs 2 processors so as to execute successfully at all times, because the stretching algorithm forces subtask τ1,4 to execute sequentially within the critical path. For any given scheduling algorithm, the DAG set is schedulable on 3 processors, because DAG task τ1 occupies 2 processors and the remaining processor is dedicated to the sequential DAG task τ2.

Conclusion: In the case of preemptive EDF and DM scheduling algorithms, there exists a DAG set that is schedulable on a multiprocessor system when the DAG-Str algorithm from the Model Transformation approach is used, while Direct Scheduling approach fails to schedule the same set.

Example 2: Direct Scheduling can outperform DAG-Str algorithm (Figure 5) Task Set: In this ex-

τ 1,1 τ 1,2 τ 1,5 τ 1,6 L1 = 6 τ 1,3 τ 1,7 τ 1,4 τ 1,8 (a)
τ 1,1 τ 1,2 τ 1,5 τ 1,6 τ 2,1 τ 2,2 τ 1,3 τ 2,1 τ 2,2 τ 1,7 τ 2,3 τ 1,4 τ 2,3 τ 1,8 0 2 4
(d) A successful EDF and DM scheduling of task set in case of Direct Scheduling.

τ 1,1 τ 1,2 τ 1,3 τ 1,5 τ 1,6 x τ 2,1 τ 2,2 τ 2,3 τ 2,1 τ 2,2 τ 2,3 τ 1,7 τ 1,4 τ 1,8 0 2 4
(e) EDF and DM scheduling with a deadline miss when DAG-Str is used. ample, we consider a DAG set τ that consists of two periodic implicit-deadline DAG tasks {τ1, τ2}. DAG task τ1 has a deadline equal to 6, and it consists of 8 subtasks and a total WCET equal to 10. The WCET of subtasks and the internal structure of the DAG are shown in Inset 5(a). The critical path length of DAG τ1 is equal to 6 which is the same as its relative deadline. Thus, the DAG has no slack time and it cannot be stretched. In order to avoid a deadline miss, its subtasks have to execute without any delay or interruption. DAG task τ2 consists of 3 subtasks, in which subtask τ2,1 is the source subtask of the DAG and subtasks {τ2,2, τ2,3} are its successors, as shown in Inset 5(b). The default execution behavior of these subtasks is that both subtasks τ2,2 and τ2,3 execute in parallel. However, since DAG task τ2 has a slack time equal to 1 time unit and its utilization is less than 1, then DAG-Str algorithm transforms DAG τ2 into a sequential task in which all of its subtasks execute sequentially. The stretched form of DAG τ2 is shown in Inset 5(c). The total utilization U (τ ) of the DAG set is equal to ( 106 + 1) = 2.66. Hence, the task set requires an execution platform of at least 3 processors to be feasible.

Priority Assignment: If DM scheduling algorithm is used, then jobs of DAG τ2 are assigned a higher priority than jobs of DAG τ1 because τ2 has a shorter relative deadline. In the case of EDF, if we consider a synchronous scenario in which DAGs are released at time t = 0, then the first job of task τ2 has an absolute deadline at t = 3 while the first job of τ1 has an absolute deadline at t = 6. As a result, EDF assigns the job from DAG τ2 a higher priority. Regarding the second job of DAG τ2, its absolute deadline is equal to the deadline of the first job of DAG τ1, hence, priorities are assigned arbitrarily. In this example, we consider that the DAG with the shortest relative deadline is assigned higher priority as a tie breaking rule. According to this priority assignment, DAG jobs have the same priorities according to EDF and DM scheduling algorithms.

Direct Scheduling Approach: In Inset 5(d), we show the global preemptive scheduling of the DAG set on a system of 3 identical processors using the Direct Scheduling approach. First DAG jobs are activated at time t = 0 and the job of DAG τ2 has the highest priority. Subtask τ2,1 executes in interval [0, 1) and its successors τ2,2 and τ2,3 execute in parallel and occupy two processors of the system in [START_REF]OpenMP Application Program Interface version 3.1[END_REF][START_REF]POSIX threads programming[END_REF]. Similarly, the second job of DAG τ2 executes in parallel with τ1 in time interval [START_REF] Baruah | A Generalized Parallel Task Model for Recurrent Real-time Processes[END_REF][START_REF] Bonifaci | Feasibility Analysis in the Sporadic DAG Task Model[END_REF]. According to this scheduling, the first job of DAG task τ1 executes without interruption and all of its subtasks execute without any delay. As Figure 5(d), the synchronous DAG set is schedulable using DM and EDF scheduling algorithms.

Model Transformation Approach: When DAG-Str algorithm is used, subtasks of DAG τ2 are forced to execute sequentially as a sequential thread even if there are available processors in the system for subtasks to execute in parallel. The first job of τ2 has a higher priority according to DM and EDF, then it occupies a single processor by itself in time interval [0, 3), as shown in Inset 5(e). As a result, subtasks of the first job of DAG τ1 are blocked during this time interval and one of them (subtask τ1,3 in the example) is delayed for 1 time unit and is forced to execute in time interval [START_REF] Baruah | A Generalized Parallel Task Model for Recurrent Real-time Processes[END_REF][START_REF] Bini | Measuring the Performance of Schedulability Tests[END_REF] instead of [START_REF]POSIX threads programming[END_REF][START_REF] Baruah | A Generalized Parallel Task Model for Recurrent Real-time Processes[END_REF]. DAG task τ1 has no slack time, then a deadline miss happens as shown in the figure .  Conclusion: In the case of preemptive EDF and DM scheduling algorithms, there exists a DAG set that is schedulable on a multiprocessor system when Direct Scheduling approach is used, while it is unschedulable when the DAG stretching algorithm is used. Based on Examples 1 and 2, both scheduling approaches are not comparable and no one dominates the other.

SIMULATION ANALYSIS

Based on the scheduling examples, we conclude that the DAG scheduling approaches are not comparable, and it is not clear which approach outperforms the other. In order to evaluate their schedulability performance, we evaluate them through extensive simulations of randomly-generated DAG tasks on multiple processors. The use of simulation-based evaluations is common in real-time analysis to give an indication regarding the performance of proposed algorithms. Simulation is used to check whether a set of tasks respects its temporal constraints when a specific algorithm is used, or to evaluate the efficiency of a new approach when compared with other algorithms from the state-of-the-art.

In real-time systems, there are many simulation tools that vary in their characteristics and features, e.g., MAST, Cheddar and FORTAS. However, many factors force researchers to implement their own simulation tools without depending on the existing ones, such as the lack of a standard simulator, the difficulty of extending an existing tool to include new features and models and the lack of documentation. In our case, we implemented a new simulation tool which contains the parallel dependent DAG model.

In this section, we present our simulation tool YARTISS [START_REF] Chandarli | YARTISS: A Tool to Visualize, Test, Compare and Evaluate Real-Time Scheduling Algorithms[END_REF], which is a free open-source simulation tool written in Java for real-time multiprocessor scheduling. We focused during its design on providing a generic simulation tool and an easyto-use modular design in which new modules can be added easily without the need to decompress, edit nor recompile existing parts. We briefly describe the main features of the simulator w.r.t. random generation of the DAG model. Then we present the simulation results of DAG scheduling approaches and we evaluate their performance when global preemptive EDF and DM algorithms are used.

Task Model Generator

YARTISS offers an open architecture to facilitate the integration of different task models. Its current version contains two models, the first one is the independent sequential task model with energy parameters, in which a task is characterized by its WCET, its period and its relative deadline, in addition to its worst case energy consumption. The second model is the DAG model which belongs to the dependent parallel category.

Performing large-scale scheduling simulations requires a large data set of tasks. In order to avoid biased results and to ensure credibility, the used task sets should be randomly generated and their timing parameters should be varied sufficiently. YARTISS provides the ability to choose a task set generator which defines the various timing parameters of tasks and whether they are periodic/sporadic and implicit/constrained/arbitrary deadline tasks. The default generator in YARTISS is based on the UUniFast-Discard algorithm [START_REF] Bini | Measuring the Performance of Schedulability Tests[END_REF] adapted to energy constraints and parallel tasks (utilization is greater than 1) coupled with a hyper-period limitation technique [START_REF] Goossens | Limitation of the Hyper-Period in Real-Time Periodic Task Set Generation[END_REF].

The UUnifast-Discard algorithm is used to uniformly distribute the system utilization on all tasks of the set with a complexity of O(n), where n is the number of tasks in Algorithm 1 The UUniFast-Discard Algorithm (from [START_REF] Bini | Measuring the Performance of Schedulability Tests[END_REF]) Require: U (τ ), n Ensure: vectU An array of utilization of each task τi in the set τ . sumU = U (τ )

for i = 1 : n -1 do nextSumU = sumU × rand (1/(n-i)) vectU (i) = sumU -nextSumU sumU = nextSumU end for vectU (n) = SumU
the set. As shown in Algorithm 1, the UUniFast-Discard algorithm generates an array of n random task utilization, in which each element represents a task utilization Ui of τi ∈ τ , where 0 < Ui < U (τ ) for parallel tasks (Ui ≤ 1 for sequential tasks) and n i=1 Ui ≤ U (τ ). For each task τi, its utilization, which is equal to Ui = C i T i , is used to compute the remaining timing parameters. We generate WCET and period values for each task based on its utilization. It is known that a periodic task set repeats its task arrival pattern after an interval called the hyper period. In order to verify the schedulability of a task set, it is necessary to determine the response time of each job on a period of length that may be slightly greater than the hyper period [START_REF] Leung | A Note on Preemptive Scheduling of Periodic, Real-time Tasks[END_REF][START_REF] Goossens | The Non-Optimality of the Monotonic Priority Assignmentsfor Hard Real-Time Offset Free Systems[END_REF]. The hyper period of a task set is calculated as the Least Common Multiple (LCM) of periods of tasks in the set. Hence, the value of LCM is affected by the increase of task periods in the set. In order to limit the length of the hyper period during task generation in YARTISS, we use the hyper-period limitation technique from [START_REF] Goossens | Limitation of the Hyper-Period in Real-Time Periodic Task Set Generation[END_REF]. The idea of the technique is to generate n periods {T1, T2, ..., Tn} for each task in the set in a way to bound their resulting LCM. The algorithm uses a matrix M representing primes and their probabilistic distribution. A period is calculated as the multiple of random number from each line in the matrix. For example, if we consider a matrix M which consists of 5 primes [START_REF]POSIX threads programming[END_REF][START_REF] Baruah | A Generalized Parallel Task Model for Recurrent Real-time Processes[END_REF][START_REF] Bonifaci | Feasibility Analysis in the Sporadic DAG Task Model[END_REF][START_REF] Chetto | Dynamic Scheduling of Real-time Tasks Under Precedence Constraints[END_REF][START_REF] Goossens | Gang FTP Scheduling of Periodic and Parallel Rigid Real-time Tasks[END_REF], its structure and probabilistic distribution are provided as follows: The largest period, that can be possibly generated from M, is equal to (16 × 27 × 25 × 49 × 11 = 5821200), which represents the largest hyper period of the task set. Hence, by choosing the prime values of the matrix, we can limit the maximum hyper period of the generated task set, and respectively, the simulation interval.

M =      1 2 2 4
Based on the UUniFast-Discard and the hyper-period limitation algorithms, the utilization and period of each task are derived. The deadline Di is derived based on the type of generated task sets. In the case of implicit-deadlines, we consider that Di = Ti. While the deadline of constraineddeadline tasks is less than or equal to the period, where Di ≤ Ti. Finally, there is no relation between the deadline and the period in the case of arbitrary-deadline tasks.

For a DAG task τi, the total WCET Ci can be calculated based on the utilization and period and it is strictly less than the deadline (1 ≤ Ci ≤ Di). The inter-subtask parallelism and the dependencies between the subtasks should be taken into consideration in the generation process. The DAG generator uses the UUniFast-Discard algorithm to determine the WCET of each subtask based on the total WCET of the DAG. The following parameters are necessary for the generation of subtasks and their precedence constraints:

• Maximum number of subtasks (MAX_SUBTASKS): it is defined for each DAG set as an upper bound on the number of subtasks in the DAG. This value is important to determine the size of DAGs which affects the probability of its inter-subtask parallelism. Generally, DAG tasks, whose number of subtasks is large, tend to have more internal parallelism and more precedence constraints between their subtasks than smaller DAGs.

Additionally, the minimum number of subtasks (MIN_ SUBTASKS) is calculated so as to ensure a feasible generation of DAGs. Its value is calculated when we consider that each subtask τi,j in DAG τi has a WCET Ci,j equal to its relative deadline Di, which is the maximum execution time that can be assigned to any subtask so as to be feasible. Then, the MIN_SUBTASKS is equal to Ci Di . For each DAG task τi in the set, its number of subtasks ni is equal to rand(MIN_SUBTASKS, MAX_SUBTASKS). If random generation of subtask timing parameters leads to MIN_SUBTASKS greater than MAX_SUBTASKS, then the generation process is repeated until this relation becomes true.

• The WCET Ci,j of each subtask τi,j is calculated using the UUniFast-Discard algorithm, where the total WCET Ci of the DAG and the number of subtasks ni are its inputs. We bound the value of Ci,j of each subtask to ensure system feasibility by using the following

C max i,j
and C min i,j bounds:

-Any sequential subtask of DAG τi cannot exceed the deadline of the DAG. Hence, C max i,j = Di.

-The minimum WCET C min i,j is calculated when each subtask τ i,k in the DAG, which is not assigned a WCET yet, is considered to have a WCET C i,k equal to C max i,k . This bound is necessary to ensure the feasibility of generated subtasks. For example, let us consider a DAG task τi with the following timing parameters: a total WCET Ci = 6, a relative deadline Di = 4 and two subtasks {τi,1, τi,2}. If subtask τi,1 is assigned a WCET equal to Ci,1 = 1, then the remaining WCET available for subtask τi,2 is equal to 5 which is greater than the deadline of the DAG and the subtask is not feasible on a unit-speed processor. Hence, C min i,1

has to be at least (6 -4) = 2 time units to ensure feasibility.

• The probability factor of directed relations ρ between subtasks, where 0 < ρ < 1. If ρ is close to 0, then the probability of creating a directed relation between any two subtasks in the DAG is large. This probability is reduced when ρ moves closer to 1. In order to get rid of cyclic dependencies between subtasks, we use a triangular matrix R whose entries of ones and zeros are generated randomly based on the Listing 1. An example of an XML file describing the DAG Tasks <?xml version="1.0 " e n c o d i n g="UTF -8"?> . . . <tasks nbTasks="1" t y p e="Fixed Priority "> <task d e a d l i n e="10" f i r s t R e l e a s e="0" nbSubtasks="2" p e r i o d="10" p r i o r i t y="1 " t y p e="graph" wcee="0" wcet="5"> <subtask c h i l d r e n="1" d e a d l i n e="10" f i r s t R e l e a s e="0" i n d e x="0" l o c a l D e a d l i n e="7" nbProc="1" p a r e n t s ="" p e r i o d="10" p r i o r i t y="1" t y p e=" subtask " wcet="2"/> <subtask c h i l d r e n="-1" d e a d l i n e="10" f i r s t R e l e a s e="2" i n d e x="1" l o c a l D e a d l i n e="10" nbProc="1" p a r e n t s="0" p e r i o d="10" p r i o r i t y="1" t y p e="subtask " wcet="3"/> </ task> </ tasks> probability factor ρ. For each DAG task τi, R is a square matrix of size ni and all of its entries under the main diagonal are zeros. Also, we consider that the main diagonal entries are zeros so that a subtask does not have a precedence relation with itself. The remaining entries represent the precedence relations between subtasks and they are either zeros or ones. For DAG τi, if entry R j,k = 1, then we create a precedence relation from subtask τi,j to τ i,k . If it is zero, then there is no relation between these two subtasks. An example of the triangular matrix R of a DAG τi of 4 subtasks is considered as follows:

R =     τi,1 τi,2 τi,3 τi,4 τi,1 0 1 1 0 τi,2 0 0 0 1 τi,3 0 0 0 1 τi,4 0 0 0 0    
In this example, subtask τi,1 has two successors τi,2 and τi,3 since R1,2 = R1,3 = 1, while there is no directed relations between subtask τi,1 and subtask τi,4.

Similarly, subtask τi,4 is the successor of subtasks τi,2 and τi,3.

Using these parameters, DAG sets are generated randomly and each DAG task is assigned a WCET, a period, a relative deadline and a set of random subtasks with precedence constraints. In YARTISS, each DAG set is encoded in an XML file so as to be used repeatedly in the simulation of different scheduling algorithms. An example of a DAG XML file is shown in Listing 1, which represents a data set of a single task set (tag <tasks>) which contains a single DAG task (tag <task>). This DAG consists of two subtasks (tag <subtask>), in which the first subtask is a parent of the second one (represented by attributes parents and children). The subtask tag has other attributes such the WCET, deadline, first release time so as to represent their timing parameters. In this subsection, we present simulation results of DAG scheduling approaches when associated with EDF algorithm. These results are analyzed w.r.t. the number of processors in the system, the variation of the size of DAGs and the probability of internal dependencies.

Simulation Results for EDF Scheduling Algorithm

The effect of the number of processors on DAG schedulability

We simulate the DAG scheduling by using the two scheduling approaches with EDF scheduling algorithm. We analyze their schedulability performance w.r.t. the number of processors in the system, and the other simulation parameters (DAG size and parallelism probability) are fixed for each simulation sets.

Figure 6 shows the simulation results of Direct Scheduling and DAG-Str algorithm with EDF. The x-axis of each inset in the Figure denotes the percentage of task set utilization w.r.t. the number of processors in the system, while the yaxis denotes the percentage of schedulable task sets. In the simulations of Insets 6(a), 6(b) and 6(c), we consider that the probability factor ρ is equal to 0.1 (high probability of internal parallelism) and MAX_SUBTASKS is equal to 5.

In general, we notice that the performance of all DAG scheduling approaches decreases when the number of processors of the system is increased. However, the performance of the DAG-Str algorithm is more affected by the variation of number of processors than the Direct Scheduling approache. Inset 6(a) shows the simulation results when DAG-Str algorithm is used. For m = 2, we notice that the schedulability percentage of stretched DAG sets is almost 100% for all sets whose utilization less than or equal to 80%. Then the schedulability percentage drops to around 50% for utilization equal to 100%. However, the schedulability performance degrades when the number of processors is increased. When m = 16, less than 50% of task sets are schedulable when their utilization is greater than 40% of number of processors.

Direct Scheduling approach of DAGs behaves in the same manner but with better schedulability, as shown in Inset 6(b). The simulation results show that this approach schedules successfully more than 60% of DAG sets whose utilization is no more than 80% of any number of processors. As shown in Inset 6(c), the performance of all scheduling approaches is relatively similar when the number of processors is small (although the DAG-Str algorithm has the best performance). However, when we consider m = 16, there is a big difference in performance between the DAG-Str algorithm and the Direct Scheduling in favor of the latter.

In conclusion, when EDF is used to schedule DAG tasks on execution platforms of large number of processors, it is better to consider Direct Scheduling approaches rather than DAG-Str algorithm. In other words, the parallel structure of DAG tasks is more compatible with EDF scheduling algorithm.

The effect of the size of DAGs on schedulability Inset 6(d) (respectively Inset 6(e)) shows the simulation results of DAG-Str algorithm (respectively Direct Scheduling approach) when the size of DAGs is varied. We consider that MAX_SUBTASKS is equal to 5 (small DAGs) and 12 (large DAGs) while the number of processors is equal to 8. In these experiments, we analyze the simulation results w.r.t. the maximum and minimum probability of internal parallelism of DAG tasks (ρ = 0.9 and ρ = 0.1).

We notice that the effect of DAG size depends on the considered scheduling approach. In the case of DAG-Str algorithm, its schedulability performance decreases when the size of DAGs is increased. As shown in Inset 6(d), the DAG-Str algorithm schedules more DAG sets when their size is small. When MAX_SUBTASKS is equal to 5, more than 30% of DAG sets, whose utilization is not greater than 80%, are schedulable (when ρ is either 0.1 or 0.9). The schedulabil-ity percentage drops to around 10% of the same DAG sets when MAX_SUBTASKS is equal to 12. Moreover, we notice that the performance of DAG-Str algorithm is not affected much by the level of internal parallelism of DAG tasks which is represented by the probability factor ρ.

Similarly, Inset 6(e) shows the schedulability of Direct Scheduling approach when the size of DAGs is varied. We notice that its performance is affected by the probability of internal parallelism. When ρ is equal to 0.9, the schedulability performance remained the same even when the size of DAGs is changed. However when ρ is equal to 0.1, Direct approach schedules more DAG sets when MAX_SUBTASKS is equal to 12. As a general remark, Direct Scheduling approach successfully schedules more than 40% of DAG sets whose utilization is less than or equal to 80% of the number of processors.

The effect of internal parallelism of DAGs on schedulability

In this subsection, we analyze the effect of parallelism probability on the schedulability of DAGs using the different scheduling approaches. We present simulation results after considering probability factor ρ equal to 0.1 (solid lines) and 0.9 (dashed lines) in Insets 6(d) and 6(e). As explained earlier, when ρ is close to zero, DAG tasks are more probable to have many dependencies between their subtasks, while a factor close to 1 means that subtasks tend to execute independently within their DAGs. In this experiment set, we choose execution platforms of number processors equal to 8 and MAX_SUBTASKS equal to 5 and 12.

Starting by the DAG-Str algorithm from Inset 6(d), we notice that its performance is not affected by varying the probability factor ρ. This can be explained by mentioning that the DAG-Str algorithm avoids the internal structure of DAG tasks and execute them as sequentially as possible. Inset 6(e) shows the schedulability performance of Direct Scheduling approach improves when the probability of internal dependencies increases. Around 40% of DAG tasks with utilization less than 80% are schedulable when parallelism parameter ρ is equal to 0.9. The percentage of schedulable DAG sets raises up to more than 60% of schedulable DAG tasks with the same utilization when ρ is equal to 0.1.

Conclusion:

Based on the provided simulation results, we conclude that Direct Scheduling approach performs better than DAG-Str algorithm when preemptive EDF algorithm is used.

Simulation Results for DM Scheduling Algorithm

After analyzing the DAG schedulability performance of EDF algorithm, which is from fixed job priority assignment family, we consider another scheduling algorithm which is from fixed task priority family. DM algorithm assigns priorities to DAGs based on their relative deadlines. Similarly to previous simulations, we present in this subsection performance evaluations of scheduling approaches with DM. We compare the performance of DAG-Str algorithm to the Direct Scheduling approach while varying the number of processors in the system, the size of DAG tasks and the probability of inter-subtask parallelism. The simulation results are shown in Figure 7.

The effect of the number of processors on DAG schedulability Insets 7(a) and 7(b) show the simulation results which compare the DAG-Str algorithm (solid lines) and Direct Scheduling (dashes lines) w.r.t. the number of processors in the systems. In these experiments, the size of DAGs is fixed to MAX_SUBTASKS equal to 9, and the probability factor ρ is equal to 0.1 (respectively 0.9) in Inset 7(a) (respectively 7(b)). In general, the schedulability performance of both approaches decreases by the increase of number of processors in the system. We notice also that the schedulability of both algorithms is almost identical when m = 2. However, DAG-Str algorithm performs better than the Direct Scheduling when the execution platform consists of number of processors m greater than 2. This indicates that DM is more compatible with DAG-Str algorithm and it performs better than EDF scheduling algorithm.

However, when ρ factor is equal to 0.1, the scheduling approaches have better schedulability on large number of processors when compared to the case where ρ is equal to 0.9.

Simulation analysis for Direct Scheduling

In the case of Direct Scheduling approach, the schedulability performance is better for high probability of parallelism (ρ = 0.1) rather than low probability, as shown in Inset 7(c). In these simulations, we consider that DAGs consist MAX_SUBTASKS is equal to 12. When ρ is equal to 0.1, around 60% of DAG sets are schedulable with system utilization equal to 80%. When ρ is equal to 0.9, the schedulability percentage drops to less than 20% for the same DAG sets.

Simulation analysis for DAG-Str algorithm

As shown in Inset 7(d) and when the DAG-Str algorithm is applied on DAGs of large sizes (where MAX_SUBTASKS is equal to 12), the schedulability performance decreases by the decrease of parallelism probability but in a rate less than the Direct Scheduling approach.

When ρ is equal to 0.1, the schedulability performance is more than 50% for system utilization equal to 80%. The percentage drops to more than 20% when ρ is equal to 0.9 for the same DAG sets. From these results, we can notice that the schedulability of DAG-Str algorithm is better than Direct Scheduling in the case of low probability of internal parallelism.

As a result and based on the provided simulation results, we conclude that DAG-Str algorithm performs better than Direct Scheduling approach when associated with global preemptive DM algorithm.

CONCLUSION

In this paper, we described two main scheduling approaches for global preemptive parallel real-time DAG tasks on multiprocessor systems. The Direct Scheduling approach, which represents the parallel structure of DAGs, maintains the inter-subtask parallelism of DAGs. While DAG-Str algorithm from the Model Transformation approach transforms DAG tasks into sequential independent model which is easier to schedule. This approach represents the sequential structure of DAGs because it aims at eliminating their internal dependencies. We proved using scheduling examples, that these DAG scheduling approaches are not comparable and no one of them dominates the other. The comparability analysis was done while considering two global preemptive scheduling algorithms, the Deadline Monotonic (DM) from the fixed task priority assignment family and the Earliest Deadline First (EDF) from the fixed job priority assignment family.

Finally, we performed experimental analyses so as to evaluate the schedulability performance of DAGs. The simulation results showed that DM algorithm is more adapted to the DAG-Str algorithm and EDF scheduling algorithm performs better when DAG tasks are scheduled using the Direct approach.

In the future, we aim at providing more analysis regarding the behavior of such algorithms on the scheduling approaches of DAG scheduling by providing theoretical analysis such as resource augmentation bounds. Moreover, we aim at extending the analysis to consider other scheduling algorithms that can be associated to DAG scheduling approaches, such as Least Laxity First.

Figure 1 .

 1 Figure 1. An example of a DAG task τ1 which consists of 7 subtasks.

Figure 2 .

 2 Figure 2. An example of parallel scheduling method of DAG task from Figure 1

Figure 3 .

 3 Figure 3. Example of stretching scheduling method for DAGs.

  DAG task τ1 (stretched execution form).

  DAG task τ2 (parallel and stretched execution forms).

Figure 4 .

 4 Figure 4. An example of scheduling incomparability in favor of DAG-Str when compared to Direct Scheduling.

  DAG task τ1 (parallel and stretched forms).

  DAG task τ2 (parallel execution form).

  DAG task τ2 (stretched execution form).

Figure 5 .

 5 Figure 5. An example of DAG scheduling incomparability in favor of Direct Scheduling when compared to DAG-Str algorithm.

  (a) DAG-Str algorithm, ρ = 0.1, MAX_SUBTASKS = 5. (b) Direct Sched. ρ = 0.1, MAX_SUBTASKS = 5. (c) All algorithms, ρ = 0.1, MAX_SUBTASKS = 5. (d) DAG-Str algorithm. m = 8. (e) Direct Sched. m = 8.

Figure 6 .

 6 Figure 6. Simulation results of DAG scheduling approaches when EDF is used.

  (a) ρ = 0.1, MAX_SUBTASKS = 9. (b) ρ = 0.9, MAX_SUBTASKS = 9. (c) Direct Sched. m = 16, MAX_SUBTASKS = 12. (d) DAG-Str. m = 16, MAX_SUBTASKS = 12.

Figure 7 .

 7 Figure 7. Simulation results of DAG scheduling approaches when DM is used.

In both computations, we consider that subtask jobs execute up to their worst-case execution time.


Cody James Christopher

Marie-Odile Cordier

Alban Grastien

Critical Observations in a Diagnostic Problem

We claim that presenting a human operator in charge of repairing a faulty system with a small subset of observations relevant to the failure improves awareness and confidence of the operator. Consequently, we introduce the problem of finding a set of relevant observations (called the critical observations) that can be used to derive the same diagnosis as the full problem. We show how this problem can be solved and illustrate its benefits on a real diagnostic problem.

I. INTRODUCTION

In the context of diagnosis, more observations of the system under consideration generally improves the quality and precision of the diagnosis. A greater number of observations means a reduction in the number of unknown variables, and consequently a reduction in the complexity of the problem.

However, there are disadvantages that arise with an increase in observations. Pertinent to this paper is the particular context where a human operator is involved in the monitoring loop. We seek to present the operator with not only the diagnosis, but also a justification or rational explanation as to how the diagnosis was arrived at. The full set of observations in many cases is too large and varied to serve as an effective solution to this requirement, so the question becomes one of determing the most relevant observations. The seminal work in cognitive psychology makes the argument that the average working memory capacity in humans is only 7 ± 2 distinct items [START_REF] Miller | The magical number seven, plus or minus two: some limits on our capacity for processing information[END_REF]. Thus, the smaller this set of observations is, the better it serves in convincing an operator of the rationality of the presented diagnosis.

As further motivation, consider the following examples. In the state of Victoria, Australia, the government has mandated interval smart meters for 2.6 million electricity customers. Each of these meters provides information on electricity consumption every thirty minutes, for an average of 1.4 thousand per second. NASA provide a diagnostic benchmark system called ADAPT [START_REF] Kurtoglu | First international diagnosis competition -DXC'09[END_REF], used for the Diagnosis Competition, that involves 87 sensors operating at reporting frequencies of 1 or 2 Hz, and occasionally 10 Hz. In either scenario the raw number of observations is much too great for a human operator to process, In both, however, we posit that a small subset of observations is generally enough to convince an operator of the validity of the diagnosis.

For this work we use a consistency-and model-based approach, where a diagnosis is a set of faults that does not contradict the observations as applied to the model. We assume that operators are only concerned with minimal diagnoses (as detailed in §III), which implies that observations that do not deviate from the norm can generally be ignored. We also take that the minimal diagnoses for a problem have already been computed. We show that under these assumptions, a subset of observations can be used to prove two related results on the problem: [START_REF] Miller | The magical number seven, plus or minus two: some limits on our capacity for processing information[END_REF] the minimality of a presented diagnosis, and (2) the completeness of the presented set of minimal diagnoses. We then present a procedure to compute the critical subset of observationsthe minimal set of observations that allows us to prove either of the aforementioned results.

The method presented is developed in the context of steady state systems, but can be extended to dynamic statedriven systems. The method can also be extended to eventbased observations; this is more complicated however, and is discussed in the conclusion.

This paper is structured as follows: We initially give a simple worked example before providing the basic definitions of diagnosis. We then present the necessary theory to establish formally the problem of finding what we all the critical observations, and provide a procedure for this problem. We illustrate the results on the ADAPT-lite benchmark and conclude with a discussion on related works and possible extensions.

II. WORKED EXAMPLE

We provide a simple example that illustrates the problem, and will refer back to this example multiple times throughout. Figure 1 shows a simplified version of a power network. Electricity flows from the root through each of the buses (b 0 , b 1 , . . .) through to components (x 0 , x 1 , . . .) at the bottom of the tree. Each component has an associated sensor (s 0 , s 1 , . . .) which, for simplicity, cannot itself be faulty and only indicate whether the flow of power to the component is nominal or not.

The outputs of any given node in the network are normal provided that the input on that node is normal and the node itself is not faulty. We assume that the input to root is normal. The diagnoses for this network will be then therefore be the set of buses that precisely cover the set of abnormal sensors. It is important to note that no sensor is redundant, as a fault on x i will only be detectable by s i .

We assume that the two sensors s 2 and s 3 return abnormal observations whilst all other observations are nominal. Under this assumption it is obvious that the fault(s) originate either from b 3 or from both x 2 and x 3 . Bus b 0 and root can be exonerated as only sensors s 2 and s 3 are affected,

root b 0 b 2 x 0 s 0 x 1 s 1 b 3 x 2 s 2 x 3 s 3 b 1 b 4 x 4 s 4 x 5 s 5 b 5 x 6 s 6 x 7 s 7
Fig. 1. A Simple Power Network and we would expect other descendents would also report abnormality if either were the cause.

In this instance, it is clear that not every observation (the readings on all sensors) is needed to produce a useful diagnosis. The problem here is in computationally isolating the relevant observations that could be used to produce an identical diagnosis.

III. DIAGNOSIS FRAMEWORK

We make use of the standard general framework for model-based diagnosis [START_REF] Reiter | A theory of diagnosis from first principles[END_REF], [START_REF] De Kleer | Diagnosing multiple faults[END_REF].

Definition 1: The system model, Mod, is a tuple Comps, SD where Comps is a set of components and SD is a statement in first order logic encoding the system behaviour. We use Ab(c) to specify that component c ∈ Comps is behaving abnormally.

Definition 2: The observations, Obs, are a set of logical statements.

Definition 3: A diagnostic problem, P, is a tuple Mod, Obs .

Definition 4: A diagnostic hypothesis, δ, is a subset of Comps that implicitly defines the following conjunction:

δ ≡ c∈δ Ab(c) ∧   c∈Comps\δ ¬Ab(c)   . (1)
That is, the components c ∈ δ are those believed to be behaving abnormally (thus Ab(c)), and all c / ∈ δ are those believed to be behaving normally (thus ¬Ab(c)).

Definition 5: The diagnoses of a problem P are the hypotheses, δ, that are logically consistent with the system and the observations. We define a function, ∆, over problems that returns the set of the diagnoses for P:

∆(P) = δ ∈ 2 Comps | SD ∧ Obs ∧ δ ⊥ (2)
A diagnosis (δ ∈ ∆) is minimal if no proper subset of δ is also a diagnosis. We define another function, ∆ min , over problems that returns the set of minimal diagnoses for P.

∆ min (P) = {δ ∈ ∆(P) | δ ∈ ∆(P) : (δ ⊂ δ)} . (3)
We use D to represent a set of minimal diagnoses and D C to represent a complete set of minimal diagnoses.

The goal of diagnosis is to determine which components in a given system are faulty. We consider consistencybased diagnosis, where a diagnosis is any hypothesis that is consistent with the observations; that is, it is possible to assign the system variables in a way that agrees with the model and the observations.

A. Running Example

To model our example network (presented in §II), we define three binary predicates, i, o 1 , o 2 , representing input and (multiple) outputs of each component respectively, with two symbols N, A representing normal and abnormal. Under such definitions the fact that the input on α is normal would be modelled by i(α, N ). The buses are then modelled by:

o j (α, N ) ←→ (¬Ab(α) ∧ i(α, N )). (4)
The connections between buses are then modelled by:

o j (α 1 , N ) ←→ i(α 2 , N ) (5)
such that the connection between b 0 and b 2 is represented by

o 1 (b 0 , N ) ←→ i(b 2 , N ).
Consider the hypothesis δ 0 = ∅ which posits that no component is faulty. We say that δ 0 is not consistent with the observations i(s 2 , A) and i(s 3 , A), as our model predicts nominal observations. The possible diagnoses are then:

∆(P) = {{b 3 }, {b 3 ,x 2 }, {b 3 ,x 3 }, {x 2 ,x 3 }, {b 3 ,x 2 ,x 3 }} . (6)
Taking δ 1 = {b 3 } and δ 2 = {x 2 , x 3 }, we then have ∆ min (P) = {δ 1 , δ 2 }. This should be interpreted as follows: either b 3 is faulty or both x 2 and x 3 are. In the event that b 3 is faulty, it is possible that there are other faulty components (x 2 , x 3 ), but there is no a priori reason to assume this, thus supersets of δ 1 are not members of ∆ min .

IV. CRITICAL OBSERVATIONS

We now present key results that allow us to formalize the problem of finding a subset of observations that are sufficient to infer the same diagnoses as those of a given diagnosis problem.

A. Motivation

Understanding the implications of a given diagnoses is important in determining the appropriate reparation or workaround actions. One way to improve awareness of, as well as trust in, a given diagnoses is for the human operator in charge to be able to relate it to the observations that produced it. In a real system with thousands of observation inputs however, this is not a trivial task. Providing the operator the relevant observations therefore becomes a very useful tool for decision support.

1) Running Example: Returning to our running example, we previously computed the minimal diagnoses as δ 1 = {b 3 } and δ 2 = {x 2 , x 3 }. In this scenario, it is obvious that the observations provided by s 2 and s 3 are crucial to explaning hypothesis δ 2 . Furthermore, the observations provided by s 0 or s 1 allow us to disregard b 0 and root as potential candidates, so keeping one of the nominal observations is considered useful. The other nominal observations, however, are not similarly useful except to say that no other incident is taking place in the rest of the network, and the assumption of which was already used in the computation of the minimal diagnoses.

B. Subproblems

We now present the notion of diagnostic subproblems and the properties that link the diagnoses of problems to their subproblems. We assume at this stage that (some or all of) the minimal diagnoses of the problem, P, have been computed.

Definition 6: Take diagnosis problem P = Mod, Obs . A subproblem of P is a problem P = Mod , Obs such that Mod = Mod and Obs ⊆ Obs. That is, some observations are no longer considered.

We now establish three lemmas that are crucial to this work. For the remainder of this section we take P to be a diagnosis problem, and P to be a subproblem of P as given by Definition 6. Thus: Lemma 4.1: ∆(P) ⊆ ∆(P ) Proof: By contradiction. Take some δ ∈ ∆(P) and assume that δ / ∈ ∆(P ). Set ϕ = Obs \ Obs .

From assumption, δ / ∈ ∆(P ) implies (Mod, Obs , δ) ⊥. But, by monotonicity of entailment: (Mod, Obs , δ, ϕ) ⊥, This implies δ / ∈ ∆(P), contradicting the initial premise.

This first lemma establishes that any diagnosis of a problem, P, must also be a diagnosis for the subproblem, P . It is an important formal statement that we cannot lose diagnoses by reducing the set of observations, and is needed for Lemma 4.2.

Lemma 4.2: ∆ min (P ) ∩ ∆(P) ⊆ ∆ min (P) Proof: By contradiction. Take some δ ∈ ∆ min (P )∩∆(P), and assume δ / ∈ ∆ min (P). From assumption, ∃δ o δ, with δ o ∈ ∆(P). From Lemma 4.1, δ o ∈ ∆(P) implies that δ o ∈ ∆(P ). However since δ o δ, we have δ / ∈ ∆ min (P ) (definition 5), which contradicts the initial premise. Lemma 4.2 shows that any diagnosis for the original instance, P, that is minimal for P must then also be minimal for P. Keeping in mind that the minimality of a diagnosis provides a way of distinguishing whether one solution is better than another, this lemma provides an important consequence -if a subset of observations allows the claim that that no strictly better solutions than δ exists, then the claim is also allowed with the original set of observations. In other words, we have shown that using a subset of the original observations is a legitimate way of proving the minimality of a diagnosis.

The next lemma improves this result by showing that there are no other minimal diagnoses other than those implied by the subproblem.

Lemma 4.3: ∆ min (P ) ⊆ ∆(P) ⇒ ∆ min (P) ⊆ ∆ min (P ) Proof: By contradiction. Take ∆ min (P ) ⊆ ∆(P), and assume ∆ min (P) ⊆ ∆ min (P ).

From assumption, there exists δ ∈ ∆ min (P) \ ∆ min (P ). By definition δ ∈ ∆(P), and from Lemma 4.1, δ ∈ ∆(P ). As δ / ∈ ∆ min (P ), there exists δ o ∈ ∆ min (P ) such that δ o δ. From the premise, δ o ∈ ∆ min (P ) ⇒ δ o ∈ ∆(P). However this contradicts the consequence of the assumption, δ ∈ ∆ min (P).

The final lemma establishes that if all minimal diagnoses of P are also diagnoses of P, then all minimal diagnoses of P are minimal diagnoses of P . We can combine Lemma 4.2 with Lemma 4.3 to prove that if all minimal diagnoses of P are diagnoses of P, then ∆ min (P) = ∆ min (P ).

Consequently, if a subset of observations projects that a system is experiencing all the faults from at least one of the set of hypotheses {δ 1 , . . . , δ k }, then this claim is true with the original set of observations. In other words, we are proving that there is no alternative explanation to the observations than ∆ min (P ) (though the reality could indeed be worse than a minimal diagnosis).

There are some caveats, however. Whilst a subset of observations is sufficient to disprove the validity of a diagnosis (Lemma 4.1), it is not sufficient in general to prove its validity. Indeed, notice that both Lemma 4.2 and Lemma 4.3 apply only to the minimal diagnoses of P that are also diagnoses of P.

Futhermore, these results hold in a consistency-based diagnostic framework, but not in a probabilistic one. Logical consistency-based diagnosis ( ⊥) enjoys the monotonicity of entailment -whereby adding logical statements (statebased observations) cannot make an already invalid explanation valid -that probabilistic frameworks unfortunately do not, as an explanation which was unlikely (compared to others explanations) can suddenly become highly probable if added observations support this explanation and contradict others.

C. Critical Sets

We now present the concept of sufficient observations and formalise the problem of finding a minimal sufficient subproblem.

Take a set D of diagnoses for the problem P (i.e., D ⊆ ∆(P)). We are interested in proving two properties about D:

• Minimality: D ⊆ ∆ min (P), i.e., there are no strictly better explanations than those of D; • Completeness: D = ∆ min (P), i.e., there are no alternative explanations than those of D. Definition 7: Take diagnosis problem P and its subproblem P . Take a set D of diagnoses of P and a property of D with respect to P. Subproblem P is sufficient for this property if the property of D can be proved using only P .

From Lemma 4.2, a subproblem is sufficient for minimality if and only if the following holds: D ⊆ ∆ min (P ). Similarly from Lemma 4.3, a subproblem is sufficient for completeness if and only if the following holds: D = ∆ min (P ).

As mentioned, we assume that a more concise set of observations better serves the purpose of providing a rational explanation to a human operator in a diagnosis loop. A critical subproblem is therefore a sufficient problem from which no observation can be removed:

Definition 8: Take a diagnosis problem P and its subproblem P . Take a set D of diagnoses of P and a property of D with respect to P. Subproblem P is critical for this property if it is sufficient and no strict subproblem of P is sufficient (minimal).

V. FINDING CRITICAL OBSERVATIONS

Having defined critical subproblems -a minimal subproblem that remains sufficient -we wish to now find one.

It is easily shown that sufficiency as defined is a monotonic property; if a subproblem is not sufficient then neither are its subproblems. Therefore, an approach to finding a critical subproblem consists of iteratively testing whether removing a specific observation maintains the required properties or not.

As explained in § IV, we can determine the sufficiency of a subproblem by computing the set of minimal diagnoses of this subproblem. This operation, however, is potentially expensive and we seek a more efficient approach.

We instead present an alternative approach for testing for sufficiency with respect to either property that is based on a single consistency check. One of the consequence of Lemma 4.1, is that removing observations can only increase the total number of diagnoses; therefore, we need to make sure that these added diagnoses do not affect the relation between D and ∆ min (P ).

It is possible to identify which hypotheses, ∇, should not ever be added to the set of diagnoses. The consistency check verifies whether any of these hypotheses are consistent with the model and the observations. The set ∇ can be quite large and it should not be enumerated; we present at the end of this section a method of representing this set in a logical and compact formulation.

A. Excluded Hypotheses

With respect to minimality, we need to prevent diagnoses that would invalidate the minimality property of those already in D, so we define:

∇(D) = δ o ∈ 2 Comps | ∃δ ∈ D . δ o ⊂ δ (7)
and present a companion lemma (proof omitted): Lemma 5.1: D ⊆ ∆(P) ∧ (∇(D) ∩ ∆(P ) = ∅) ⇐⇒ D ⊆ ∆ min (P ). This lemma demonstrates that we can show D is a set of minimal diagnoses for P if ∇ does not contain any diagnoses for P . Combined with Lemma 4.2, this implies that D is a set of mninimal diagnoses for the parent problem, P, as well.

However, this still does not prevent the adding of new minimal diagnoses that are disjoint to the existing members of D (with respect to the components). To preserve the completeness of the original set, we need to exclude all remaining hypotheses:

∇ C (D) = δ o ∈ 2 Comps | δ ∈ D . δ ⊆ δ o (8)
and present a companion lemma (proof omitted): Lemma 5.2:

D ⊆ ∆(P) ∧ (∇ C (D) ∩ ∆(P ) = ∅) ⇐⇒ D = ∆ min (P ).
Again, this lemma demonstrates that completeness of D can be proved by showing that none of the excluded hypotheses in ∇ C contradict the subset of observations in P .

The key characteristic of the solution, Obs , is that it defines a diagnostic problem to which the set of diagnoses does not intersect either ∇ or ∇ C . We can interpret ∇ as a disjunction and evaluate the consistency of:

SD ∧ Obs ∧ ∇ ? ⊥. ( 9
)
If a contradiction is derived, then Obs is sufficient to prove the required property on D. Notice that sufficiency is proved when an inconsistency is found, while the validity of a hypothesis is proved when there is no inconsistency.

1) Running Example: Referring back to our example in §II, we can compute a sufficient (and indeed, critical) set of observations.

Taking

δ 1 = {b 3 }, δ 2 = {x 2 , x 3 }, with D = {δ 1 , δ 2 }, we can compute ∇(D): ∇(D) = {∅, {x 2 } , {x 3 }} (10)
This result show that a subset of observations is sufficient to prove minimality of D if it excludes the three hypotheses that would be considered strictly better than those in D: ∅ (no component is faulty), {x 2 } (only x 2 is faulty) and {x 3 }.

There is only one critical subset of observations that achieves this: {o(s 2 , A), o(s 3 , A)} -both s 2 and s 3 are abnormal.

If we only consider D 1 = {δ 1 }, we obtain ∇(D 1 ) = {∅}, indicating that a subset of observations is sufficient to prove minimality of D 1 if it excludes only the hypothesis that no component is faulty, and thus only a single observation (e.g., o(s 2 , A)) is necessary to achieve this.

Consider now the completeness of D:

∇ C (D) = {{b 0 } , {x 0 } , . . . , {b 0 , x 0 } , {b 0 , x 2 } , . . .} (11)
This is all hypotheses that do not include x 2 and x 3 together and/or b 3 -more than 10, 000 elements. As ∇ C (D) will always be a superset of ∇(D), a critical subset for completeness is always a superset of a critical subset for minimality. Thus we must include the previously indicated observations o(s 2 , A) and o(s 3 , A), which has the effect of excluding all hypotheses that do not suspect root, b 0 , b 3 , x 2 or x 3 . To demonstrate completeness, hypotheses that suspect root or b 0 must also be excluded -adding o(s 0 , N ) has this effect, leaving only hypotheses that are consistent with the model (those suspecting b 3 or both x 2 and x 3 ), none of which belongs to ∇ C (D).

If we tried to prove completeness of (the incomplete) D 1 , we would end up with a set ∇ C (D 1 ) containing δ 2 . As δ 2 is a diagnosis, it is also a diagnosis of all subproblems and there is no critical set of observations. Notice that all the critical sets presented above consider the observation o(s 4 , N ) as irrelevant, among other things it indicates that component x 4 is nominal. Keep in mind, however, that we are only interested in the minimal diagnoses. The established minimal diagnoses for the problem do not say anything about the state of component x 4 except that there is no reason to suspect x 4 of being faulty.

B. Symbolic Representation of ∇

In the small running example with less than twenty components, the set ∇ C already contains over 10, 000 elements. Since the size of this set increases exponentially with the number of components, it is impractical to enumerate it. Fortunately the consistency checker does not need an explicit enumeration, but can use the symbolic representation that we now present.

Assume that D is a singleton hypothesis, {δ}, where δ may contain several components. The set ∇(D) can be represented symbolically as follows:

∇(D) ≡   c∈Comps\δ ¬Ab(c)   ∧ c∈δ ¬Ab(c) . (12)
The symbolic representation for a non-singleton is simply the disjunction of the singleton representations for each of hypotheses in D.

In our running example, D 2 = {δ 2 }, the minimality of δ 2 is ensured by proving that the joint assumptions: (1) no component outside δ 2 is faulty, and (2) not both of components x 2 and x 3 are faulty, contradict the model and the observations. This representation is linear in the size of Comps.

We now turn to ∇ C . The symbolical representation of ∇ C (D) is:

∇ C (D) ≡ δ∈D c∈δ ¬Ab(c) . (13)
Back to the example, D 1,2 = {δ 1 , δ 2 }. Completeness of D 1,2 is ensured by proving that the joint assumptions: (1) component b 3 is not faulty, and (2) not both of components x 2 and x 3 are faulty, contradict the model and the observations.

While the size of ∇ C (D) is exponential in the size of Comps, this representation is only linear in the size of D and does not directly depend on the size of Comps (bearing in mind that D may be exponential in the size of Comps). [START_REF] Kurtoglu | First international diagnosis competition -DXC'09[END_REF]. The hardware system for the DXC-09 Industrial Track is the Electrical Power System testbed in the ADAPT lab at NASA Ames Research Center.

VI. ILLUSTRATION ON ADAPT-LITE We now present an example taken from the ADAPT-lite track used as part of the 2009 International Workshop on Principles of Diagnosis (DX) Competition

The ADAPT EPS testbed provides a means for evaluating diagnostic algorithms through the controlled insertion of faults in repeatable failure scenarios. The lite version of ADAPT is depicted in Figure 2. The sensors on the ADAPT system return observations at a rate of 1, 2, or 10Hz, which, on the full system, produces nearly one thousand, often ten digit, information inputs per second. We used a model that combines first order logic with linear arithmetics, and we use an SMT solver for the consistency checks [START_REF] Grastien | Diagnosis of hybrid systems by consistency testing[END_REF].

The specific approach used for this problem differs from the one presented in that it does not consider minimality with respect to set inclusion but with respect to cardinalitydiagnoses that minimize the number of faulty components. This change is made as the ADAPT sensors themselves may be faulty, whereas we had previously assumed otherwise. This can lead to unrealistic minimal diagnoses that involve most sensors being faulty, and the minimality of these diagnoses requires at least one observation from each sensor. The extension of our work to minimal cardinality, and in particular the representation of the ∇ sets, is very similar in construction.

Figure 3 shows a reduced example of observation trace on the ADAPT-lite system. The single minimal-cardinality diagnosis in this problem posits that Sensor IT240 (current flow in amperes) suddenly suffers from an offset fault. The critical observations are identified by our algorithm are indicated in bold in Figure 3, and we can indeed demonstrate that they suffice to prove the diagnosis.

Firstly, notice that IT240 reads a current of 16.3A at time 1500ms, after having read 6.3A prior. This value, according to the system specification and model, is clearly abnormal. Secondly, as the value of IT240 at time 2000ms is different from the former one, we deduce that the problem cannot be that IT240 is stuck at 16.3A. Finally, the only reason (at least, according to our model) for a larger than expected current is that the battery is compensating for a lower than expected voltage; however voltage sensor E235 claims that the voltage is normal (24V is expected upstream of the inverter).

Obviously E235 could be faulty, but that would imply at least one other fault, as a fault from E235 does not explain the abnormal observation from IT240. Such a diagnosis would have a cardinality of two or more, making it less preferred to the cardinality one diagnosis.

VII. RELATED WORK

The notion of reducing the number of observations in diagnosis problems has been widely studied but with different motivations from this work. Previous work in general aims at reducing the overall cost of observations, which is incurred in multiple different ways: (1) the system must be designed to allow for appropriate and useful observations, (2) sensors must be integrated and additionally powered, (3) observations must be collected, etc.

Optimal diagnosability is concerned with minimizing the number of sensors (or their total cost) while ensuring diagnosability [START_REF] Briones | Optimal observability for diagnosability[END_REF] before any observations are considered. The solution to an optimal diagnosability problem works for every possible evolution of the system, as opposed to our approach, which is specific to the current evolution and only seeks to provide an explanation for the current circumstances.

Sequential diagnosis [START_REF] De Kleer | Using crude probability estimates to guide diagnosis[END_REF], and its event-based variant [START_REF] Cassez | Fault diagnosis with dynamic observers[END_REF], focuses on the problem of deciding which observation should be collected next in order to improve the precision of diagnosis. Similarly to the work presented, sequential diagnosis is an online problem -deciding which observation to collect is not made a priori but with respect to the observations already collected. The difference to this work, however, is that all observations are kept, even when they provide no information or when they are redundant.

VIII. CONCLUSION

In this paper we presented an approach to provide an operator involved in a diagnosis loop with a manageable subset of observations with the intent of providing a better understanding and appreciation of the results returned by the diagnosis procedure. The intended application of this work is in contexts where the sheer volume of observations is overwhelming, making it difficult for a human operator to verify the validity of the given diagnosis. We made the assumption that the optimality of the solution is tied to the conciseness of the explataion. It is clear then, that the most concise explanation is strictly preferred, which we formalised with respect to the notion of minimality.

This definition of optimality could be further refined. For instance, one might consider that a better solution would be one that involves reasoning about the smallest number of variables (or components) or that involves the simplest rules (for instance, avoiding complex numerical operations). In the ADAPT-lite example from the previous section, it seems more natural to include the observation of IT261 rather than that of E235 because the disagreement between the two observations of the current flow is more obvious than the inconsistency between the current flow and the voltage.

Additionally, it might be interesting to optimize the criterion of confidentiality by abstracting away details: in a power network context, one could report that a specified household has been consuming electricity during the day rather than reporting the precise time and consumption amount.

Another direction of research is the more practical question of computing the critical set of observations fast. One possibility is to analyze the solving of M od ∧ Obs ∧ ∇ in order to extract the observations used to prove inconsistency; although this set of observations may not be minimal, it would provide a good first estimate.

A last interesting extension is to consider event-based observations -extracting the critical information from a large flow of alarms. Event-based observations bring an additional subtlety that is not a factor in state-based observations. Specifically, there is a difference between not observing an event and ignoring an event that has been observed; for instance, the repeated observations that a window is being closed without an observation of it ever being opening is symptomatic of a problem. The critical information may therefore include that certain observations were not made.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Schematic for ADAPT-lite

Artificial Intelligence Group, The Australian National University.

Optimisation Research Group, NICTA * .

Dream, Université Rennes 1. * NICTA is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program.