Salah Eddine Saidi
email: salah-eddine.saidi@ifpen.fr

Nicolas Pernet
email: nicolas.pernet@ifpen.fr

Yves Sorel
email: yves.sorel@inria.fr

Scheduling Real-time HiL Co-simulation of Cyber-Physical Systems on Multi-core Architectures

Keywords: simulation, HiL, scheduling, real-time, multicore

When designing complex cyber-physical systems, engineers have to integrate numerical models from different modeling environments in order to simulate the whole system and estimate its global performances. Co-simulation refers to such joint simulation of heterogeneous models. If some parts of the system are physically available, it is possible to connect these parts to the co-simulation in a Hardware-in-the-Loop (HiL) approach. In this case, the simulation has to be performed in realtime where models execution consists in periodically reacting to the real (physically available) components and providing periodic output updates. This paper deals with the parallelization and scheduling of real-time Hardware-in-the-Loop co-simulation of numerical models on multi-core architectures. A method for defining real-time constraints that have to be met is proposed. Also, an ILP formulation as well as a heuristic are proposed to solve the problem of scheduling the co-simulation on a multicore architecture while satisfying the previously defined real-time constraints. The proposed approach is evaluated for different sizes of co-simulations and multi-core processors.

I. INTRODUCTION

Systems that combine computational elements and physical processes are referred to as Cyber-Physical Systems (CPS) [START_REF] Lee | Introduction to embedded systems: a cyberphysical systems approach[END_REF]. The different elements are more or less tightly coupled and interact with each other using different communication media. The diversity of the involved disciplines makes the process of building CPS challenging, costly and time consuming. Enabling the prediction of the system's behavior before its deployment has the potential to reduce the risks, the cost and the needed effort. Simulation is an efficient way to achieve these requirements as it allows imitating the functioning of the system on a computer and assessing its design.

In co-simulation, the different subsystems are modeled in a segregated manner and then connected together to simulate the whole system on a computer. Integrating heterogeneous models usually results in computationally expensive co-simulation. Increasing CPU frequency by means of silicon integration has reached its possible limits and semiconductor manufacturers switched to building multi-core processors, allowing parallel processing on a single computer.

In Hardware-in-the-Loop (HiL) co-simulation, real components, that are physically available, are connected to simulated models. The goal here is to emulate the behavior of a part of the system using the simulated models in order to run the real component under realistic conditions. In HiL, two concepts of time have to be correctly meshed: the simulated time and the real time. Achieving a correct meshing of the simulated time and the real time defines a set of timing constraints imposed on the simulated models. Performing HiL co-simulations on multi-core processors can enhance the opportunities of satisfying these timing constraints which may be infeasible on single-core processors.

In the present paper, we focus on the execution of HiL co-simulation under real-time constraints on multi-core processors. We are interested in co-simulations of CPS that are compliant with the Functional Mock-up Interface (FMI) standard [START_REF]Functional mock-up interface for model exchange and co-simulation[END_REF] that is widely adopted in industry. The Refined CO-SIMulation (RCOSIM) [START_REF] Ben Khaled | Fast multicore co-simulation of cyber-physical systems: application to internal combustion engines[END_REF] is a co-simulation parallelization approach which takes advantage of the information given by FMI about input-output relationships inside a model that is exported as a Functional Mock-up Unit (FMU). In our recent work [START_REF] Saidi | Automatic parallelization of multi-rate fmi-based co-simulation on multi-core[END_REF], we extended the use of RCOSIM to multi-rate cosimulation. In this paper, we extend the use of RCOSIM to HiL co-simulation under real-time constraints. First, we propose rules to propagate real-time constraints to FMI compliant models in a HiL co-simulation. Furthermore, we propose non preemptive multi-core scheduling algorithms to satisfy the timing constraints. These algorithms consist in an exact algorithm based on an Integer Linear Programming (ILP) to find the optimal solution and a heuristic giving an approximate solution.

The rest of the paper is organized as follows. The next section is dedicated to related work. In Section III, we present basic concepts and preliminaries related to FMI HiL cosimulation under real-time constraints and give a description of the problem. In Section IV, we define the real-time constraints that are imposed in a HiL co-simulation. Then, we propose rules and algorithms to propagate these constraints in the dependence graph in Section V. Next, we present in Section VI an ILP formulation and a list heuristic to solve the problem of non preemptive multi-core scheduling of HiL co-simulation under real-time constraints. We evaluate our solution in Section VII and conclude the paper in Section VIII.

II. RELATED WORK

Some work has been carried out in academia as well as in industry in order to tackle the problem of real-time HiL co-simulation. A first aspect of our contribution is to assign HiL real-time constraints to the different operations of the simulated part. In industry, this problem is tackled at the model or submodel level. Engineers have to define the different periods of the different models or submodels. Such approach has two drawbacks. First, it often leads the user to naively translate a model-rate (stepsize) requirement into a real-time period requirement. This results in more stringent period constraints than necessary. Second, to find an execution order, it is often necessary to break some data dependencies by adding a delay or memory function. Indeed, at the model or submodel level, cycles may be present but disappear at lower levels. Figures 1 and2 give an example of such co-simulation. In [START_REF] Faure | Propagation rules of real-time constraints on physical systems simulators in a hardware-in-the loop context[END_REF], a proposed set of propagation rules allows fixing the problem of assigning an adequate period and deadline to each model. Nevertheless, Faure et al. address the problem at the model-level even if they distinguish between models where no output directly depends on the inputs and models where at least one output does. In this approach, the cycle problem is not solved. On the opposite, our approach, by exploiting FMI features, is able to use internal input-output relationships of each model to propagate constraints on a set of models without having to break any data dependency.

After propagating the real-time constraints, our approach deals with a real-time multi-core DAG scheduling problem that may look close to the multi-rate synchronous language scheduling problem which is addressed in [START_REF] Pagetti | Multitask implementation of multi-periodic synchronous programs[END_REF]. Nevertheless, such approach implies strict periodicity which is not a constraint in the co-simulations that we target. In [START_REF] Chetto | Dynamic scheduling of realtime tasks under precedence constraints[END_REF] and [START_REF] Spuri | How to integrate precedence constraints and shared resources in real-time scheduling[END_REF], online approaches are proposed for real-time DAG scheduling, but on mono-processor platforms. On the other hand, multicore real-time scheduling of independent tasks has received a lot of attention in the literature [START_REF] Davis | A survey of hard real-time scheduling for multiprocessor systems[END_REF]. In our work, operations may have deadlines greater than their respective periods and data dependencies have to be considered as constraints. In [START_REF] Palencia | Exploiting precedence relations in the schedulability analysis of distributed real-time systems[END_REF] and [START_REF] Qamhieh | Graph-to-segment transformation technique minimizing the number of processors for realtime multiprocessor systems[END_REF], multiprocessor real-time scheduling with dependencies is addressed. However, the proposed approaches are preemptive. We adopt an offline non preemptive approach since preemption seems not beneficial given that most industrial applications exhibit fine granularity with short computation times [START_REF] Jayachandran | The case for non-preemptive scheduling in distributed real-time systems[END_REF]. Also, online scheduling is likely to bring no significant advantages due to the short computation times. We are mainly lead by our experience in industrial co-simulation. Most of the FMI operations that we have to schedule have short computation times (few µs) and an industrial use case may easily lead to a number of operations between 100 and 10000.

III. FMI HIL CO-SIMULATION

In this Section, we present basic concepts related to FMI cosimulation with a focus on HiL co-simulation. First, we give an overview of the FMI standard. Then, we describe briefly our method for transforming a model graph of an FMI cosimulation into a dependence graph. The resulting graph has a finer granularity than the model graph. Finally, we give some preliminaries regarding HiL co-simulation.

A. FMI Standard

The Functional Mock-up Interface (FMI) is a toolindependent and open standard designed within the MOD-ELISAR project 1 and is currently developed and maintained by the Modelica Association 2 which promotes the Modelica language. The FMI standard was developed in order to facilitate the co-simulation of dynamical systems, such as CPS. It provides specifications in order to enable the exchange and the co-simulation of heterogeneous dynamical models that may be developed by different tools and originating from different parties. A modeling tool that supports FMI can export a model as a Functional Mock-up Unit (FMU) which can be used in co-simulation environments. An FMU is a package that encapsulates an XML file containing, among other data, the definitions of the model's variables, and a library defining the equations of the model as C functions. FMI defines interfaces for the involved models to allow their co-simulation.

B. Dependence Graph of an FMI Co-simulation

The method for automatic parallelization of FMU cosimulation that we propose in this paper is based on representing the co-simulation by a dependence graph. We present below how this graph is constructed and a set of attributes that characterize it. The graph construction and characterization method is done following the RCOSIM approach as presented in [START_REF] Ben Khaled | Fast multicore co-simulation of cyber-physical systems: application to internal combustion engines[END_REF].

The entry point for the construction of a dependence graph of an FMU co-simulation is a user-specified set of interconnected FMUs as depicted in Figure 1. In this Figure, each model has a number of inputs, outputs and, even if not displayed, one state. The execution of each FMU is seen as computing a set of inputs, a set of outputs, and the state of the FMU. A computation of an input, output, or the state is performed by FMU C function calls. Thanks to FMI, it is additionally possible to access information about the internal structure of a model encapsulated in an FMU. In particular, as shown in Figure 2, FMI allows the identification of Direct Feedthrough (e.g. Y B1 ) and Non Direct Feedthrough (e.g. Y A1 ) outputs of an FMU and other information depending on the version of the standard. The information provided by FMI on input-output dependence allows transforming the FMU graph into a graph with an increased granularity. For each FMU, the inputs, outputs, and the state are transformed into operations. An input, output, or a 1 itea3.org/project/modelisar.html 2 www.modelica.org/association/

FMU A U A1 U A2 Y A1 Y A2 Y A3 FMU B U B3 U B2 U B1 Y B2 Y B1
FMU A U A1 U A2 Y A1 Y A2 Y A3 FMU B U B3 U B2 U B1 Y B2 Y B1
Fig. 2: Intra-FMU dependence provided by FMI state operation is defined as the set of FMU function calls that are used to compute the corresponding input, output, or state respectively. The co-simulation is described by a dependence graph G(V, A), called the operation graph, where each vertex o i ∈ V : 0 ≤ i < n represents one operation, each arc (o i , o j ) ∈ A : 0 ≤ i, j < n represents a dependence between operations o i and o j which means that o i must be executed before o j and, possibly, produces data to be consumed by o j . n = |V | is the size of the operation graph. The operation graph is built by exploring the relations between the FMUs and between the operations of the same FMU. A vertex is created for each operation and arcs are then added between vertices if a dependence exists between the corresponding operations.

The co-simulation of a system is run over a user-specified time interval. More specifically, each model is simulated over a certain number of time steps. At each step, the corresponding FMU inputs, outputs, and state are updated. An execution of the obtained operation graph corresponds to one simulation step. Therefore, running the co-simulation consists in repeatedly executing the graph until the desired number of steps is reached. A new execution of the graph cannot be started unless the previous one was totally finished. The operation graph corresponding to the FMUs of Figure 2 is shown in Figure 3 where input and output operations are represented by circle vertices and state operations are represented by square vertices. Note that state operations do not have successors. Although they do not appear in Figures 1 and2, we recall that every FMU has one state operation.

YA1 UB3 YB1 UA2 YA3 UB1 ẊB ẊA UB2 YA2 UA1 YB2
Fig. 3: Operation graph obtained from the FMUs of Figure 2 At each repetition of the execution of the operation graph, the equations of each FMU are integrated according to an integration step assigned by the user and which, in some cases, is driven by the dynamics of the modeled system and the control objective. In addition, each FMU exchanges data with the other FMUs according to a communication step also assigned by the user and which can be equal or larger than its integration step. In a multi-rate co-simulation, multiple FMUs are assigned different communication steps [START_REF] Saidi | Automatic parallelization of multi-rate fmi-based co-simulation on multi-core[END_REF].

We use the notation f m (o i ) to refer to the FMU to which the operation o i belongs. Once the operation graph is constructed, each operation o i is characterized by a set of parameters. The first parameter consists in the Worst Case Execution Time (WCET) C(o i ) obtained through a profiling phase. Each operation o i is characterized by a communication step H(o i ) which is equal to the communication step of its FMU. In addition, the following parameters are defined for each operation o i :

• The set of successors (resp. predecessors) succ(o i ) (resp.

pred(o i )).

i ) = E(o i ) + C(o i ). • The flexibility F (o i ) = R -S(o i ) -C(o i ) -E(o i ). CP = max oi∈V I (E(o i ))
denotes the critical path of the graph.

These notations are used afterward in the proposed scheduling algorithms.

In the case of multi-rate co-simulation, a multi-rate transformation algorithm is applied on the the operation graph. Its principle consists in repeating each operation o i in the operation graph a certain number of times where each repetition is called an occurrence, assigning to it a repetition factor (number of occurrences) denoted r(o i ), and adding arcs between these occurrences. More details can be found in our previous work [START_REF] Saidi | Automatic parallelization of multi-rate fmi-based co-simulation on multi-core[END_REF].

C. Preliminaries on HiL Co-simulation

A HiL setup is composed of a simulated component and a physically available component that is interfaced with the simulated component via inputs and outputs. It should be noted that multiple parts may be physically available and involved in HiL, e.g. multiple controllers interacting with multiple parts of simulated physical processes. We regard all these physically available parts as a single real component. Figure 4 shows a basic example of a HiL co-simulation. The simulated component is represented by an operation graph. It consists of two FMUs A and B. The real component has one input (resp. output) connected to an output (resp. input) operation of the simulated component. We refer to output and input operations that are directly connected with the real component as gate operations.

The main goal of HiL co-simulation is to estimate the performance of the real component by providing a realistic environment through the simulated component. The simulated component has to interact with the real component at the same rate as its real counterpart. As such, the inputs and outputs of the real component, which we assume to be periodically sampled, define real-time constraints which involve that the simulated time has to match the real time. These constraints are imposed on the outputs and inputs of the simulated component that are connected with the inputs (resp. outputs) of the real component.

The ultimate goal of this work is to perform real-time multicore scheduling of operation graphs representing HiL cosimulations. In order to achieve this, we deal with a problem that is essentially composed of two parts. First, we need to characterize all the operations of the operation graph with realtime parameters. Starting from the constraints that are imposed on the gate operations, we seek to propagate these constraints to the rest of the operations. Second, we aim at proposing a real-time scheduling algorithm that allows the execution of the operations, characterized as described above, on a multicore processor in such a way that the propagated real-time constraints are satisfied.

IV. DEFINITION OF REAL-TIME CONSTRAINTS

The propagation of real-time constraints that we propose avoids over-constraining the co-simulation compared to classical real-time co-simulation [START_REF] Bélanger | The what, where and why of real-time simulation[END_REF] where a unique real-time constraint inherited from the real component is imposed on all the tasks of the simulated component. On the other hand, in our approach, we only impose real-time constraints on gate operations of the simulated component and we define constraints for the rest of the operations accordingly, i.e. in such a way that the constraints imposed on the gate operations can be satisfied.

We assume that the sampling period of a given input (resp. output) of the real component is a multiple of the communication step size of the operation of the simulated component that is connected with it.

Let the inputs and the outputs of the real component be sampled with sampling periods T x and T y respectively where x and y denote the indices of the corresponding input and output respectively. In other words, an input (resp. output) of the real component is periodically activated every T x (resp. T y ) units of time. The sampling periods of the different inputs and outputs of the real component can be identical or different.

The periodic activation of an output of the real component leads to the production of data that are consumed by an input gate operation o i of the simulated component. Therefore, at the z th sample z × T y , the input gate operation o i consumes new data corresponding to simulated time z × T y . This defines a periodic release for this input gate operation, i.e. time instants at which the data to be consumed by o i is periodically updated by the real component. A release constraint imposed on a gate operation is defined by its period R(o i ) = T y .

Similarly, the periodic activation of an input of the real component requires data produced by an output gate operation o j of the simulated component to be available. Therefore, before the w th sample w×T x , the output gate operation o j has to produce data corresponding to simulated time w × T x . This defines a periodic deadline for this output gate operation, i.e. it has to periodically produce the data to be consumed by the real component before specific periodic instants. A deadline constraint imposed on an output gate operation is defined by its period D(o j ) = T x .

V. PROPAGATION OF REAL-TIME CONSTRAINTS

The aforementioned definitions specify real-time constraints for gate operations. These operations being dependent on other operations and vice versa, it becomes necessary to define the impact of the real-time constraints on the rest of the operations.

A. Propagation of Release Constraints

Let's consider an operation graph representing a multi-rate co-simulation. Let a release constraint of period T y be applied on an input gate operation o i ∈ V . Given that the sampling period of this release constraint T y is greater or equal to the communication step size of o i , H(o i ), only a subset of the occurrences of o i , o p i , 0 ≤ p < r(o i ) that belong to the operation graph are subject to this release constraint. We recall that r(o i ) is the repetition factor of operation o i which is equal to the number of its occurrences. The z th occurrence of the release constraint z × T y = t k is applied on the occurrence o p,t k i , i.e. the occurrence p of operation o i executed at time step t k , where 0 ≤ p < r(o i ) and t k ∈ R + . This subset of occurrences can be determined as follows. The occurrence z × T y of the release constraint is applied on occurrence

o p i : p = z × Ty H(oi) where H(o i ) is the communication step of o i . Therefore o p i is assigned a release R(o p i ) = z × T y . Once o p
i is released and executed, the operations that depend on o p i can be released. Therefore, the release constraint R(o p i ) is propagated towards all the successors of o p i . This propagation is given by expression

∀o i ∈ succ(o i ) : R(o i ) = R(o i ).
Let's consider, for example, the HiL co-simulation shown in Figure 4. Let H A = 2 and H B = 4 be the communication step sizes of FMUs A and B respectively and let the sampling period of the output of the real component be T out = 4. Figure 5 shows the propagation of the release constraint in the operation graph. Note that the multi-rate transformation algorithm is applied before the propagation. The operations that are assigned a release are colored. The release assigned to each operation is shown below or above the corresponding operation. The dashed blue arrow indicates the direction of the propagation which is from a predecessor to a successor. The propagation of the release constraint is performed iteratively.

Starting from the input gate operation o p 4 , for each operation that is assigned a release constraint, this constraint is propagated towards all its successors as described above. The values of release that are placed below or above some operations, correspond to the first occurrence of the release constraint z × T out = 0 × 4 = 0. In order to find the occurrence of the input gate operation o 4 that is subject to this occurrence of the release constraint, we use the formula given above: p = z × Tout H(o4) = 0 × 4 4 = 0. Therefore, in Figure 5, p = 0.

B. Propagation of Deadline Constraints

Now let a deadline constraint of period T x be applied on an output gate operation o j of the operation graph. Given that the sampling period of this deadline constraint T x is greater or equal to the communication step size of o j , H(o j ), only a subset of the occurrences of o j , o q j : 0 ≤ q < r(o j ) that belong to the operation graph are subject to this deadline constraint. The w th occurrence of the deadline constraint w × T x = t k is applied on the occurrence o q,t k j , i.e. the occurrence q of operation o j executed at time step t k , where 0 ≤ q < r(o j ) and t k ∈ R + . This subset of occurrences can be determined as follows. The occurrence w × T x = t k of the deadline constraint is applied on occurrence o q j : q = w × Tx H(oj ) where H(o j ) is the communication step of o j . Therefore, o q j that is assigned a deadline D(o q j ) = w × Tx H(oj ) . This constraint is, then, propagated towards all the predecessors of o q j . The propagation of a deadline constraint is given by expression

∀o j ∈ pred(o j ) : D(o j ) = D(o j ).
Figure 6 illustrates the propagation of the deadline constraint in the operation graph. The sampling period of the input of the real component is T in = 4. We recall that the execution of the co-simulation consists in running the operation graph repeatedly. Therefore, each run corresponds to a pattern that involves specific occurrences of the operations. While in the pattern of the operation graph that is shown previously, operation o p 5 does not have a predecessor, the state operation o p-1 10 belonging to the preceding pattern is a predecessor of o p 5 . The operations that are assigned a deadline are colored.

The deadline assigned to each operation is shown above the corresponding operation. The dashed red arrow indicates the direction of the propagation which is from a successor to a predecessor. The propagation of the deadline constraint is performed iteratively. Starting from the output gate operation o q 5 , for each operation that is assigned a deadline constraint, this constraint is propagated towards all its predecessors. The values of deadline that are shown correspond to the second occurrence of the release constraint w × T in = 1 × 4 = 4. In order to find the occurrence of the output gate operation o 5 that is subject to this occurrence of the release constraint, we use the formula given previously: q = w × Tin H(o5) = 1× 4 2 = 2. Therefore, in Figure 6, q = 2.

o q 5 o q 4 o q 8 o q 1 o q 7 o q 2 o q 11 o q 10 o q 3 o q 6 o q 0 o q 9 o q+1

C. Propagation of real-time constraints towards unreached operations

It can be seen that the propagation of the real-time constraints is based on graph traversal. The Breadth First Search (BFS) [START_REF] Moore | The shortest path through a maze[END_REF] or the Depth First Search (DFS) graph traversal algorithms [START_REF] Cormen | Introduction to algorithms[END_REF] can be used to perform this propagation. On the one hand, the release constraints are propagated following the topological ordering of the graph since the constraint is always propagated from a predecessor to a successor. We refer to such propagation as forward propagation. On the other hand, the deadline constraint is propagated in reverse topological ordering of the graph because the constraint is always propagated from a successor to a predecessor. We refer to such propagation as backward propagation. This means that the release (resp. deadline) constraint cannot propagate towards the operations that come before (resp. after) the input (resp. output) gate operation that is subject to this constraint.

Below, we propose a method to assign release and deadline constraints to operations that are not reached in the forward and backward propagation phases respectively due to the nonexistence of a path starting at a gate operation (resp. these operations) and leading to these operations (resp. a gate operation). This method is based on looping the propagation. In other words, a release (resp. deadline) constraint is propagated in a reverse order of the forward (resp. backward) propagation phase. Such looping is possible because the operation graph is repeated periodically in runtime.

We define the hyperperiod as the least common multiple of the real-time sampling periods of all inputs and outputs of the real component and the communication step sizes of all operations of the simulated component: HP = lcm(H(o 1 ), H(o 2 ), . . . , H(o n ), T 1 , T 2 , . . . , T m ) where n is the number of operations in the operation graph and m is the number of inputs and outputs of the real component.

The hyperperiod notion resembles the notions of hyperperiod found in the real-time literature. More specifically, it specifies a time interval for describing a periodic pattern of the real-time constraints assigned to operations. It only differs in that it combines real-time periods and communication step sizes. In the context of co-simulation under real-time constraints, we apply the multi-rate transformation algorithm over the hyperperiod. Therefore, the repetition factor of each operation o i ∈ V is r(o i ) = HP H(oi) . In the example shown in Figure 7, we have only one real time constraint of period 4 and, therefore, the usual hyperperiod and the one proposed above are equal (4). Now, assume that FMU A has a communication step size of 3, the usual hyperperiod remains 4 whereas the proposed hyperperiod becomes 12.

Given the periodic repetition of the operation graph, a release constraint can be written as follows:

∀o p i , o p i : p = p - HP H(o i ) , R(o p i ) = R(o p i ) -HP (1)
Equation 1 expresses how a release constraint imposed on a given operation o i , is repeated periodically over the occurrences of o i . In other words, if we know the value of the release constraint imposed on occurrence o p i , we can determine the value p such as R(o p i ) = R(o p i ) -HP . Similarly, a deadline constraint can be written as follows:

∀o q j , o q j : q = q + HP H(o j ) , D(o q j ) = D(o q j ) + HP (2)
Let's consider that a release constraint is propagated in the operation graph G(V, A) starting from the gate operation o i . Also, consider that the multi-rate transformation algorithm has been applied on the operation graph over the hyperperiod HP . Then, o p i , the last occurrence of the state operation

o i : f m (o p i ) = f m (o i )
that is assigned a release constraint during the forward propagation phase corresponds to the time step that is equal to the hyperperiod, i.e. it can be written o p,HP i . Note that such operation has no successor in the initial operation graph as well as the one obtained using the multi-rate transformation. In order to propagate the release constraint to the operations that come before o i in the graph, we loop back to the occurrence o p i of the state operation o i by performing a negative shift of the release constraint whose length is equal to the hyperperiod. The occurrence o p i is a predecessor of the first occurrence of the gate operation o i that appear in the periodic pattern of the operation graph. This is done for every FMU, for which the state operation is assigned a release. An example is shown in Figure 7.

Afterward, starting from the operations that are newly assigned release constraints, a new forward propagation phase is applied. Now consider that a deadline constraint is propagated in the graph G(V, A) starting from the gate operation o j . Let o q j be the occurrence of the state operation o j : f m (o p j ) = f m (o j ) that is a predecessor of the first occurrence of the gate operation o j that appear in the periodic pattern of the operation graph. Also, let o q j be the last occurrence of the state operation o j that appear in the periodic pattern of the operation graph. Like for the release constraint, the operations that come after o j in the operation graph can be assigned deadline constraints by looping forward the deadline constraint that is assigned to o q j towards o q j . In other words, a positive shift equal to the length of the hyperperiod is applied by looping forward to the last occurrence of the state operation o q j . This is performed for every FMU whose state operation was assigned a deadline date. Figure 8 shows an example of such looping. A backward propagation phase, starting from the operations that are newly assigned deadline constraints, is then applied.

D. Propagation of Multiple Real-time Constraints

So far, we considered that the operation graph is subject to real-time constraints that are equal. In industrial applications, this is not always the case. Now, let's consider that multiple input and output gate operations are subject to different release and deadline constraints respectively. This means the sampling periods of the inputs and the outputs of the real component are different. As before, we consider that every sampling period is a multiple of the communication step size of the gate operation that is applied to.

In order to propagate multiple real-time constraints, we follow the propagation process described previously. The release constraints are propagated by iteratively running forward propagation and back loop propagation phases whereas deadline constraints are propagated by iteratively running backward propagation and forward loop propagation phases. The main difference here is that during propagation, several constraints may be applied to the same operation.

Gate operations are always subject to only one constraint because they are directly assigned the constraints imposed by the real component. Therefore, assigning constraints to gate operations remains unchanged. On the other hand, the rest of the operations of the operation graph may have several predecessors and successors. In fact, if an operation o i ∈ V has no more than one predecessor, i.e. |pred(o i )| ≤ 1, the propagation of a release constraint towards this operation remains unchanged. Similarly, if an operation o j ∈ V has no more than one successor, i.e. |succ(o j )| ≤ 1, the propagation of a deadline constraint towards this operation remains unchanged. Hence, we are interested here in propagating release (resp. deadline) constraints towards operations which have more than one predecessor (resp. successor), i.e.

|pred(o i )| > 1 (resp. |succ(o j )| > 1).
We denote by R(o i ) the set of release constraints propagated towards the operation o i and by D(o j ) the set of deadline constraints propagated towards the operation o j . The set R(o i ) is built as the union of all the release constraints propagated towards o i from its predecessors, i.e. R(o i ) = {R(o i ) :

o i ∈ pred(o i )}.
Each operation o i must be assigned only one release constraint which is chosen from the set R(o i ). A release constraint specifies the earliest date the associated operation can start its execution. As such, the most constraining release constraint has to be chosen from the set R(o i ):

∀o i ∈ V, R(o i ) = max R(o i )∈R(oi) (R(o i )).
In the same way, the set D(o j ) is built as the union of all the deadline constraints propagated towards o j from its successors, i.e. D(o j ) : o j ∈ succ(o j ). Each operation must be assigned only one deadline constraint which is chosen from the set D(o j ). A deadline constraint specifies the latest date by which the associated operation must finish its execution. Therefore, the most constraining deadline constraint is selected from the set D(o j ):

∀o j ∈ V, D(o j ) = min D(o j )∈D(oj ) (D(o j ))

VI. MULTI-CORE SCHEDULING OF REAL-TIME CO-SIMULATION

In this section, we are interested in multi-core scheduling of FMU co-simulation under real-time constraints. We consider that the real-time constraints that are imposed by the real component have been propagated through the operation graph as described in Section V. Therefore, the aim here consists in scheduling the operations of the operations graph on a multi-core processor, such that these constraints are satisfied. Rather than an online scheduling algorithm, we use an offline scheduling approache which we consider to be more suitable given the fine granularity of the operations, and since information about the execution times of the operations and the dependence between them is available before runtime. In addition, we adopt a non preemptive scheduling approach. In fact, most of the operations have short execution times which limits the benefits of allowing preemption. Hereafter, we detail two important points necessary for performing real-time multicore scheduling. Afterward, we propose an ILP formulation and a heuristic for offline scheduling of operation graphs under real-time constraints.

A. Accounting for Dependence in Real-time Scheduling

The model of computation for (co-)simulation is close to the synchronous paradigm [START_REF] Benveniste | The synchronous approach to reactive and real-time systems[END_REF], [START_REF] Benveniste | The synchronous languages 12 years later[END_REF]. In this paradigm, a program evolves according to a sequence of ticks of logical time at which computations are considered to produce their results instantaneously. In co-simulation, the repetitions of the operation graph correspond to the ticks of the logical time. It means that the processor on which the graph will be executed is not taken into consideration. The propagation of the release and deadline constraints presented in Section V follows this model of computation. However, when real-time constraints are involved, they have to be taken into account since the processor and communication channels are known. In fact, each operation takes a certain execution time to run and, therefore, cannot produce the result instantaneously. In order to proceed to scheduling the operation graph, it is necessary to account for the dependence between operations.

We adopt an approach similar to the one proposed in [START_REF] Chetto | Dynamic scheduling of realtime tasks under precedence constraints[END_REF] to modify the release and deadline dates assigned to each operation in order to account for execution times.

Let o i and o j be two operations such that o j ∈ pred(o i ). For a given schedule of the operation graph to be valid, the relations S(o i ) ≥ R(o i ) and S(o i ) ≥ E(o j ) must be satisfied. Therefore, a new release date for o i can be computed as follows: R(o i ) = max(R(o i ), max oj ∈pred(oi) (E(o j ))).

Consider now two operations o i and o j such that o j ∈ succ(o i ). For the operation graph to be schedulable, the relations E(o i ) ≤ D(o i ) and E(o i ) ≤ D(o j ) -C(o j ) must be satisfied. In fact, D(o j ) -C(o j ) represents the latest time to start the execution of the successor o j such that its deadline can be met. Therefore, a new deadline date of o i can be computed as follows:

D(o i ) = min(D(o i ), min oj ∈succ(oi) (D(o j ) - C(o j ))).

B. Scheduling Interval

In offline scheduling, the schedule is computed over an interval of time. This schedule is then executed repetitively. For co-simulation under real-time constraints, a natural approach is to apply techniques that are used for classical real-time systems (such co-simulation is considered a real-time system after all). For this, we need first to represent the operation graph with a model that involves the parameters that are usually used for classical real-time systems. In particular, we need to define a relative deadline and a period for each operation. Note that so far, we have only spoken about sampling periods of data exchange between the real and the simulated component. Although related to the sampling periods, the periods that we seek to define here for each operation are different and correspond to task periods that are found in classical real-time systems. We propose to handle this requirement as follows. We consider that every operation that appears in the hyperperiod pattern of the operation graph is a distinct operation. In other words, occurrences of one operation are not regarded as repetitions of a single operation. Therefore, we consider that the operation graph is mono-period, i.e. all the operations have the same period. The value of this period is equal to the hyperperiod (see Section V-C). The relative deadline of each operation can then be defined as the duration between its release and deadline.

In the real-time literature, we find contributions regarding the schedule interval targeting different kinds of real-time tasks, schedulers, and processors [START_REF] Grolleau | On the periodic behavior of real-time schedulers on identical multiprocessor platforms[END_REF]. To the best of our knowledge, the existing results are either not applicable (e.g. constrained deadlines) to our problem or propose bounds that are intractable, i.e. as the size of the operation graph grows and depending on the parameters of the operations, they result in very large schedule intervals and we cannot guarantee to compute the schedule within an acceptable time. The length of the schedule interval for co-simulation under real-time constraints cannot be chosen in a straightforward manner to be equal to the hyperperiod. This is because the operation graph features arbitrary deadlines, i.e. relative deadlines that are greater than the periods. Indeed, some operations may have relative deadlines that exceed the hyperperiod which we consider to be the period of every operation. For instance, in Figure 8, operation o p+1 10 has a relative deadline of 8 while the hyperperiod is equal to 4. Arbitrary deadlines may lead to hyperperiod spill [START_REF] Dave | Cosyn: hardwaresoftware co-synthesis of heterogeneous distributed embedded systems[END_REF]. The latter refers to operations that are not scheduled in their hyperperiod and spill over the next one.

We propose to handle this situation as follows. We start with a schedule interval whose length is equal to the hyperperiod and iteratively increase it. If no hypeperiod occurs we consider that the operation graph is schedulable. If an operation misses its deadline, the operation graph is not schedulable and we stop the process. Otherwise, this process is stopped after being repeated for a certain number of times set by the user. In this case, we consider that the scheduling algorithm failed to find a schedule. Note that determining a non pessimistic schedulability interval length remains an open problem.

As shown in Section V, the propagation of the real-time constraints in an operation graph may lead to assigning negative release dates to some operations. This means that such operations can be considered to belong to the previous iteration of the operation graph.

C. ILP Formulation

In order to find the optimal solution of the real-time multicore scheduling problem, we need to use an exact algorithm. We have chosen to use the ILP approach. Our ILP formulation for multi-core scheduling of co-simulation under real-time constraints is given below.

We define the decision binary variables x ik which indicates whether the operation o i is allocated to core p k or not. Expression 3 states the constraint that each operation has to be allocated to one and only one core. The end time of each operation o i is computed using the expression 4. The start date of every operation must be at the earliest equal to its release date. Expression 5 captures this constraint. The deadline date of every operation is the latest time before which the operation has to finish its execution. Expression 6 specifies this constraint.

For operations that are allocated to the same core and that are completely independent, i.e. no path exists between them, we have to ensure that they are executed in non overlapping time intervals. Expressions 7 and 8 capture this constraint where b ij is a binary variable that is set to one if o i is executed before o j and M is a large positive constant. Therefore, expression 7 ensures the case where o i is executed before o j and expression 8 ensures the case where where o j is executed before o i

For dependent operations that are allocated to different cores, synchronization mechanism is necessary to ensure the order of their execution. While the computed schedule defines an order of execution for dependent operations, variations of execution times may occur in runtime leading to changing the start and end times of the operations. Therefore, we use synchronization to ensure the order of execution. The cost of synchronization is taken into account as follows. A synchronization cost is introduced in the computation of the start time of an operation o j , if it has a predecessor o i that is allocated to a different core and if its start time is the earliest among the successors of o i that are allocated to the same core as the operation o j . Since these successors are executed on the same core, and thus sequentially after o j , it is not necessary to add synchronizations between them and o i . sync ijk is a binary variable which indicates whether synchronization is needed between o i and o j if o j is allocated to p k . Therefore, sync ijk = 1 iff α(o j ) = p k and α(o i ) = p k and S(o j ) = max o j ∈succ(oi): α(o j )=p k (S(o j )) where α is the allocation function. Expressions 9 and 10 capture this constraint. V ik is a binary variable that is set to one only if α(o i ) = p k . It is used to define for which cores a synchronization is needed between o i and its successors and therfore needed to compute the value of variable sync ijk . In other words, if a successor is allocated to the same core as o i , no synchronization is needed. Expressions 11 and 12 capture this constraint. Variable Q ik denotes the earliest start time among the start times of all the successors of o i that are allocated to processor p k . It is computed using expressions 13 and 14.

The start time of each operation o j is computed using expression 15. The synchronization cost is introduced taking into account the synchronizations with all the predecessors of o j that are allocated to different cores.

∀ o i ∈ V, p k ∈P x ik = 1 (3) ∀o i ∈ V, E(o i ) = S(o i ) + C(o i ) (4)
∀ o i ∈ V, S(o i ) ≥ R(o i ) (5)
∀ o i ∈ V, E(o i ) ≤ D(o i ) (6)
∀p k ∈ P, ∀ o i , o j ∈ V, (o i , o j ), (o j , o i ) / ∈ A, E(o i ) ≤ S(o j ) + M × (3 -x ik -x jk -b ij ) (7) ∀p k ∈ P, ∀ o i , o j ∈ V, (o i , o j ), (o j , o i ) / ∈ A, E(o j ) ≤ S(o i ) + M × (2 -x ik -x jk + b ij ) (8)
∀o i ∈ V, ∀p∈P,∀oj ∈pred(oi) sync ijk = Q ik (9) ∀o i ∈ V, ∀o j ∈ succ(o i ), sync ijk ≤ x jk : ∀o i ∈ V ( 10
)
∀o i ∈ V, ∀o j ∈ succ(o i ), V ik ≥ x jk -x ik : ∀o i ∈ V (11) ∀o i ∈ V, V ik ≤ ∀oj ∈succ(oi) x jk -x ik ( 12
)
∀o i ∈ V, ∀o j ∈ succ(o i ), Q ik ≤ S(o j ) + M × (1 -x jk ) (13) ∀o i ∈ V, ∀o j ∈ succ(o i ), Q ik ≥ S(o j ) -M × (1 -sync ijk ) (14)
∀o j ∈ V, ∀o i ∈ pred(o j ), S(o j ) ≥ E(o i ) + ∀p k ∈P,∀o i ∈pred(oj ) sync i jk × synCost (15)

D. Multi-core Scheduling Heuristic

Multi-core scheduling problems are known to be NP-hard resulting in exponential resolution times when exact algorithms are used. Heuristics have been extensively used in order to solve multi-core scheduling problems [START_REF] Kwok | Static scheduling algorithms for allocating directed task graphs to multiprocessors[END_REF]. In most situations they lead to results of good quality in practicle resolution times. Greedy list heuristics are used in the context of offline multi-core scheduling since they are very fast. In the following, we propose a greedy list heuristic inspired by [START_REF] Grandpierre | Optimized rapid prototyping for real-time embedded heterogeneous multiprocessors[END_REF] for scheduling operation graphs representing FMU cosimulations under real-time constraints. The proposed heuristic is priority based. The scheduling priority expresses the criticality of a given operation which is measured by how close it is to miss its deadline if scheduled on a specific core: ρ i,k = D(o i )-E(o i ) where ρ i,k and E j (o i ) are the scheduling priority and the end date of operation o i respectively, computed when the latter is scheduled on core p k .

The proposed heuristic builds the multi-core schedule iteratively. At each iteration, a list of candidate operations is constructed. An operation is added to the list of candidate operation if all its predecessors have been scheduled. The heuristic computes the priority for each candidate operation on every core and selects the core for the which the priority is maximized. After that, a list of operation-best core pairs is obtained. The heuristic selects from this list the operation whose priority is the smallest among all the operations in the list. Synchronization operations are added between the scheduled operation and all its predecessors that were allocated to different cores. The heuristic repeats this procedure and finally stops when all the operations have been scheduled. This heuristic is called repeatedly as long as the scheduling interval is increased according to the proposed method given in Section VI-B. Algorithm 1 lists the proposed real-time multicore scheduling heuristic. The scheduling heuristic contains three nested loops. The outermost loop is executed until all the operations are scheduled. At each iteration, one operation is scheduled. Therefore, the outermost loop is executed n times where n is the number of operation in the operation graph. In the inner loops, the heuristic attempts to schedule all the ready operations on all the available cores. As such, the inner loops execute in O(nm), where m is the number of cores. From the foregoing, the complexity of the heuristic is evaluated to O(mn 2 ).

k ; foreach p k ∈ P do L k ← 0; while O = ∅ do foreach o i ∈ O do ρ ← ∞; // Initialize the priority of o i S(o i ) ← max(R(o i ), max oj ∈pred(oi) (E(o j ))); foreach p k ∈ P do syncCost ← 0; S(o i ) ← max(S(o i ), L k ); // Start time of o i if executed on p k foreach o j ∈ pred(o i ) do if o j is scheduled on a core p k = p k then syncCost ← syncCost + sync; S(o i ) ← S(o i ) + syncCost; E(o i ) ← S(o i ) + C(o i ); ρ ← D(o i ) -E(o i ); //

VII. EVALUATION

In this Section, we evaluate our proposed approach. We implemented a random generator of operation graphs to run tests. The random generation is not presented in this paper. We present the evaluation of the performances of the scheduling ILP and heuristic for different sizes of operation graphs and multi-core processors. We consider the proposed ILP as a reference and compare it with our heuristic performances.

A. Comparison of Resolution Times

We compared the resolution times of the real-time scheduling ILP and heuristic. We tested the real-time scheduling heuristic on operation graphs with a maximum number of operations of 1000. Tests were performed by fixing the number of cores and varying the number of operations. The obtained results are shown in Figure 9a, Figure 9b, and Figure 9c for 2, 4, and 8 cores respectively. The real-time scheduling ILP is able to solve smaller graphs than the heuristic ILP within acceptable times, and the resolution time increases exponentially as the graph size increases. On the other hand, the real-time scheduling heuristic produces results in short times keeping the resolution times within practical bounds even for large operation graphs. It is very important to produce the schedule within short times even if the latter is computed offline. In fact, in the context of co-simulation, the time needed to compute the schedule is suffered by the user. Therefore, a fast heuristic is needed to allow launching the co-simulation within acceptable times even for large industrial applications.

B. Schedulability

We run tests in order to measure the quality of our proposed heuristic. Because the execution of the ILP takes long times, we limited these tests to operation graphs of small sizes. We generated five sets of operation graphs containing each 10 graphs of sizes between five and 50. We ensured that all the generated operation graphs are schedulable by applying the ILP. Then, we apply our heuristic and save the number of schedulable operation graphs for which the heuristic is able to find a solution. The application of the heuristic resulted in an interesting quality, especially when considering its very fast resolution time compared to the ILP algorithm. The heuristic succeeded in scheduling 54%, 80%, and 94% of the operation graphs for 2, 4, and 8 cores respectively.

VIII. CONCLUSION

In this paper, we dealt with the problem of real-time scheduling of operation graphs representing FMI HiL cosimulations on multi-core processors. First, we extended the operation graph of a co-simulation under real-time constraints by assigning real-time parameters to the operations. We proposed a method for propagating real-time constraints imposed by inputs and outputs of the real component on gate operations of the simulated component. Second, we proposed an ILP and an offline heuristic to perform the real-time multi-core scheduling. We evaluated these algorithms for different sizes of co-simulations and operation graphs. We present below some possible research directions for future work.

In our approach, we used a schedulability analysis based on simulation. In future work, we aim at deriving an analytic schedulability condition or finding a non pessimistic schedulability interval. Our approach relies on propagating the realtime constraints to all the operations. An interesting alternative to our method consists in defining latency constraints on gate operations only. Then, scheduling algorithms suitable for latency constraints can be applied. Finally, it is worth investigating the use of preemptive scheduling algorithms, for instance by only allowing the preemption of operations which have long execution times.

Fig. 1 :

 1 Fig. 1: Inter-FMU dependence specified by the user

Fig. 4 :

 4 Fig. 4: Example of co-simulation under real-time constraints.

Fig. 5 :

 5 Fig. 5: Example of release propagation.

Fig. 6 :

 6 Fig. 6: Example of deadline propagation.

Fig. 7 :

 7 Fig. 7: Release back loop propagation phase.

4 +HPFig. 8 :

 48 Fig. 8: Deadline forward loop propagation phase.

Algorithm 1 :

 1 Multi-core scheduling heuristic Input : Operation graph G(V, A), set of cores P ; Output: Schedule of operations o i ∈ V on cores p k ∈ P ; Set O the set of operations without predecessors; Set sync the cost of one synchronization operation; Set L k : p k ∈ P the length of schedule of core p

(a) 2

 2 cores.

Fig. 9 :

 9 Fig. 9: Comparison of the real-time scheduling resolution time.

  Add to the set O all successors of o i for which all predecessors are already scheduled;

priority of o i if executed on p k if ρ > ρ then Set ρ ← ρ ; Set BestCore(o i ) ← p k ; Find o i with the smallest priority ρ in O; Schedule o i on its core BestCore(o i ); p best ← BestCore(o i ); L best ← E(o i ); Remove o i from the set O;


James A Thom
email: james.thom@rmit.edu.au

Jovan Pehcevski
email: jovan.pehcevski@inria.fr

Anne-Marie Vercoustre
email: anne-marie.vercoustre@inria.fr

Use of Wikipedia Categories in Entity Ranking

Wikipedia is a useful source of knowledge that has many applications in language processing and knowledge representation. The Wikipedia category graph can be compared with the class hierarchy in an ontology; it has some characteristics in common as well as some differences. In this paper, we present our approach for answering entity ranking queries from the Wikipedia. In particular, we explore how to make use of Wikipedia categories to improve entity ranking effectiveness. Our experiments show that using categories of example entities works significantly better than using loosely defined target categories.

Introduction

Semi-structured text documents contain references to many named entities but, unlike fields in a wellstructured database system, it is hard to identify the named entities within text. An entity could be, for example, an organisation, a person, a location, or a date. Because of the importance of named entities, several very active and related research areas have emerged in recent years, including: entity extraction/tagging from texts, entity reference solving (e.g. "The president of the Republic"), entity disambiguation (e.g. which Michael Jackson), question-answering, expert search, and entity ranking (also known as entity retrieval).

Entity ranking is very different from the related problem of entity extraction. The objective of entity extraction is to identify named entities from plain text and tag each and every occurrence; whereas the objective of entity ranking is to search for entities in a semi-structured collection and to get back a list of the relevant entity names as answers to a query (with possibly a page or some description associated with each entity).

The Initiative for the Evaluation of XML retrieval (INEX) is running a new track on entity ranking in 2007 [START_REF] Arjen | INEX 2007 Entity ranking track guidelines[END_REF], using Wikipedia as its document collection. In Wikipedia, pages correspond to entities which are organised into (or attached to) categories. References to entities and their categories occur frequently in natural language. For example, "France" is an named entity that corresponds to the Wikipedia page about France, belonging to categories such as "European Countries" and "Republics".

There are two tasks in the INEX 2007 entity ranking track: a task where the category of the expected entity answers is provided; and a task where a few (two or three) of the expected entity answers are provided. The inclusion of target categories (in the first task) and example entities (in the second task) makes these quite different tasks from the task of full-text retrieval, and the combination of the query and example entities (in the second task) makes it a task quite different from the task addressed by an application such as Google Sets 1where only entity examples are provided.

In this paper, we present our approach to entity ranking that augments the initial full-text information retrieval approach with information based on hypertext links and Wikipedia categories. In our previous work we have shown the benefits of using categories in entity ranking compared to full-text retrieval [START_REF] Vercoustre | Entity ranking in Wikipedia[END_REF]. Here we particularly focus on how best to use the Wikipedia category information to improve entity ranking.

Related Work

The traditional entity extraction problem lies in the ability to extract named entities from plain text using natural language processing techniques or statistical methods and intensive training from large collections. Benchmarks for evaluation of entity extraction have been performed for the Message Understanding Conference (MUC) [START_REF]Proceedings of the Third Message Understanding Conference (MUC)[END_REF] and for the Automatic Content Extraction (ACE) program [START_REF]The ACE 2006 evaluation plan: Evaluation of the detection and recognition of ACE entities, values, temporal expressions, relations, and events[END_REF].

Entity extraction

McNamee and Mayfield [START_REF] Mcnamee | Entity extraction without language-specific resources[END_REF] developed a system for entity extraction based on training on a large set of very low level textual patterns found in tokens. Their main objective was to identify entities in multilingual texts and classify them into one of four classes (location, person, organisation, or "others"). Cucerzan and Yarowsky [START_REF] Cucerzan | Language independent named entity recognition combining morphological and contextual evidence[END_REF] describe and evaluate a language-independent bootstrapping algorithm based on iterative learning and re-estimation of contextual and morphological patterns. It achieves competitive performance when trained on a very short labelled name list.

Other approaches for entity extraction are based on the use of external resources, such as an ontology or a dictionary. Popov et al. [START_REF] Popov | Towards semantic web information extraction[END_REF] use a populated ontology for entity extraction, while Cohen and Sarawagi [START_REF] Cohen | Exploiting dictionaries in named entity extraction: combining semi-Markov extraction processes and data integration methods[END_REF] exploit a dictionary for named entity extraction. Tenier et al. [START_REF] Tenier | Annotation semantique de pages web[END_REF] use an ontology for automatic semantic annotation of web pages. Their system first identifies the syntactic structure that characterises an entity in a page. It then uses subsumption to identify the more specific concept for this entity, combined with reasoning exploiting the formal structure of the ontology.

Using ontology for entity disambiguation

Hassell et al. [START_REF] Hassell | Ontology-driven automatic entity disambiguation in unstructured text[END_REF] use a "populated ontology" to assist in disambiguation of entities, for example names of authors using their published papers or domain of interest. They use text proximity between entities to disambiguate names (e.g. organisation name would be close to author's name). They also use text co-occurrence, for example for topics relevant to an author. So their algorithm is tuned for their actual ontology, while our algorithm is more based on the structural properties of the Wikipedia.

Cucerzan [START_REF] Cucerzan | Large-scale named entity disambiguation based on Wikipedia data[END_REF] uses Wikipedia data for named entity disambiguation. He first pre-processed a version of the Wikipedia collection (September 2006), and extracted more than 1.4 millions entities with an average of 2.4 surface forms by entities. He also extracted more than one million (entities, category) pairs that were further filtered out to 540 thousand pairs. Lexico-syntactic patterns, such as titles, links, paragraphs and lists, are used to build co-references of entities in limited contexts. The knowledge extracted from Wikipedia is then used for improving entity disambiguation in the context of web and news search.

Ontology similarity

Since Wikipedia has some but not all characteristics associated with an ontology, one could think of adapting some of the similarity measures proposed for comparing concepts in an ontology and use those for comparing categories in Wikipedia. Ehrig et al. [START_REF] Ehrig | Similarity for ontologies -a comprehensive framework[END_REF] and Blanchard et al. [START_REF] Blanchard | A typology of ontologybased semantic measures[END_REF] have surveyed various such similarity measures. These measures are mostly reflexive and symmetric [START_REF] Ehrig | Similarity for ontologies -a comprehensive framework[END_REF] and take into account the distance (in the path) between the concepts, the depth from the root of the ontology and the common ancestor of the concepts, and the density of concepts on the paths between the concepts and from the root of the ontology [START_REF] Blanchard | A typology of ontologybased semantic measures[END_REF].

All these measures rely on a strong hierarchy of the ontology concepts and a subsumption hypothesis in the parent-child relationship. Since those hypothesis are nor verified in Wikipedia (see Section 4), we could not use those similarity functions. Instead we experimented with similarities between sets of categories and lexical similarities between category names.

Entity ranking

Fissaha Adafre et al. [START_REF] Sisay Fissaha Adafre | Entity retrieval[END_REF] form entity neighbourhoods for every entity, which are based on clustering of similar Wikipedia pages using a combination of extracts from text content and following both incoming and outgoing page links. These entity neighbourhoods are then used as the basis for retrieval for the two entity ranking tasks.

Our approach is similar in that it uses XML structural patterns (links) rather than textual ones to identify potential entities. It also relies on the co-location of entity names with some of the entity examples (when provided). However, we also make use of the category hierarchy to better match the result entities with the expected class of the entities to retrieve.

INEX 2007 XML entity ranking track

The INEX XML entity ranking track is a new track that is being proposed in 2007. The track will use the Wikipedia XML document collection as its test collection.

Two tasks are planned for the INEX Entity ranking track in 2007 [START_REF] Arjen | INEX 2007 Entity ranking track guidelines[END_REF]: task 1: entity ranking, which aims to retrieve entities of a given category that satisfy a topic described in natural language text; and task 2: list completion, where given a topic text and a number of examples, the aim is to complete this partial list of answers.

An example of an INEX entity ranking topic is shown in Figure 1. In this example, the title field contains the plain content only query, the "The euro . . . is the official currency of the Eurozone (also known as the Euro Area), which consists of the European states of Austria, Belgium, Finland, France, Germany, Greece, Ireland, Italy, Luxembourg, the Netherlands, Portugal, Slovenia and Spain, and will extend to include Cyprus and Malta from 1 January 2008." description provides a natural language description of the information need, and the narrative provides a detailed explanation of what makes an entity answer relevant. In addition to these fields, the entities field provides a few of the expected entity answers for the topic (task 2), while the categories field provides the category of the expected entity answers (task 1).

Wikipedia XML document collection

As Wikipedia is fast growing and evolving it is not possible to use the actual online Wikipedia for experiments, and so there is a need to use a stable collection to do evaluation experiments that can be compared over time. Denoyer and Gallinari [START_REF] Denoyer | The Wikipedia XML corpus[END_REF] have developed an XMLbased corpus based on a of the Wikipedia, which has been used by various INEX tracks in 2006 and 2007. It differs from the real Wikipedia in some respects (size, document format, category tables), but it is a very realistic approximation.

Entities in Wikipedia

In Wikipedia, an entity is generally associated with an article (a Wikipedia page) describing this entity. For example, there is a page for every country, most famous people or organisations, places to visit, and so forth. In Wikipedia nearly everything can be seen as an entity with an associated page. The Wikipedia is also a rich source of links, though some are to pages that do not exist yet! When mentioning entities in a new Wikipedia article, authors are encouraged to link at least the first occurrence of the entity name to the page describing this entity. This is an important feature as it allows to easily locate potential entities, which is a major issue in entity extraction from plain text.

For example, in the small extract from Euro page shown in Figure 2, there are 18 links (shown as underlined) to other pages in the Wikipedia, of which 15 are links to countries.

Categories in Wikipedia

Wikipedia also offers categories that authors can associate with Wikipedia pages. There are 113,483 categories in the INEX Wikipedia XML collection, which are organised in a graph of categories. Each page can be associated with many categories (2.28 as an average).

Wikipedia categories have unique names (e.g. "France", "European Countries"). New categories can also be created by authors, although they have to follow Wikipedia recommendations in both creating new categories and associating them with pages. For example, the Spain page is associated with the following categories: "Spain", "European Union member states", "Spanish-speaking countries", "Constitutional monarchies" (and some other Wikipedia administrative categories). Some properties of Wikipedia categories include:

• a category may have many subcategories and parent categories;

• some categories have many associated pages (i.e. large extension), while others have smaller extension;

• a page that belongs to a given category extension generally does not belong to its ancestors' extension; for example, the page Spain does not belong to the category "European countries";

• the sub-category relation is not always a subsumption relationship; for example, "Maps of Europe" is a sub-category of "Europe", but the two categories are not in an is-a relationship; and

• there are cycles in the category graph.

Yu et al. [START_REF] Yu | Ontology evaluation using Wikipedia categories for browsing[END_REF] explore these properties in more detail.

Category similarity approaches

To make use of the Wikipedia categories in entity ranking, we define similarity functions between:

• categories of answer entities and target categories (for task 1), and

• categories of answer entities and a set of categories attached to the entity examples (for task 2).

Task 1

We first define a very basic similarity function that computes the ratio of common categories between the set of categories cat(t) associated to an answer entity page t and the set cat(C) which is the union of the provided target categories C:

S C (t) = |cat(t) ∩ cat(C)| |cat(C)| (1)
The target categories will be generally very broad, so it is to be expected that the answer entities would not generally belong to these broad categories. Accordingly, we defined several extensions of the set of categories, both for the target categories and the categories attached to answer entities.

The extensions are based on using sub-categories and parent categories in the graph of Wikipedia categories. We define cat d (C) as the set containing the target category and its sub-categories (one level down) and cat u (t) as the set containing the categories attached to an answer entity t and their parent categories (one level up). Similarity function can then be defined using the same ratio as above except that cat(t) is replaced with cat u (t) and cat(C) with cat d (C).

Another approach is to use lexical similarity between categories. For example, "european countries" is lexically similar to "countries" since they both contain the word "countries" in their names. We use an information retrieval approach to retrieve similar categories: we have indexed all the categories using their names as corresponding documents. By sending the category names C as a query to the search engine, we then retrieve all the categories that are lexically similar to C.

We keep the top M ranked categories and add them to C to form the set Ccat(C). We then use the same similarity function as before, where cat(C) is replaced with Ccat(C). We also experiment with two alternative approaches: by sending the title of the topic T as a query to the search engine (denoted as Tcat(C)); and by sending both the title of the topic T and the category names C as a query to the search engine (denoted as TCcat(C)).

An alternative approach of using lexical similarity between categories is to index the categories using their names and the names of all their attached entities as corresponding documents. For example, if C="countries", the retrieved set of categories Ccat(C) may contain not only the categories that contain "countries" in their names, but also categories attached to entities with names lexically similar to "countries".

Task 2

In task 2, the categories attached to entity examples are likely to correspond to very specific categories, just like those attached to the answer entities. We define a similarity function that computes the ratio of common categories between the set of categories attached to an answer entity page cat(t) and the set of the union of the categories attached to entity examples cat(E):

S C (t) = |cat(t) ∩ cat(E)| |cat(E)| (2)
We also expand the two sets of categories by adding the parent categories to calculate cat u (t) and cat u (E) and apply the same similarity function as above.

Our approach to entity ranking

Our approach to identifying and ranking entities combines: (1) the full-text similarity of the entity page with the query; (2) the similarity of the page's categories with the target categories or the categories of the entity examples; and (3) the links to a page from the top ranked pages returned by a search engine for the query.

Architecture

The approach involves several modules and functions that are used for processing a query, submitting it to the search engine, applying our entity ranking algorithms, and finally returning a ranked list of entities. We use Zettair2 as our choice for a full-text search engine. Zettair is a full-text information retrieval system developed by RMIT, which returns pages ranked by their similarity score to the query. We used the Okapi BM25 similarity measure that has proved to work well on the INEX 2006 Wikipedia test collection [START_REF] Iskandar | Social media retrieval using image features and structured text[END_REF].

Our approach involves the following modules:

• The search module sends the query to Zettair and returns a list of scored Wikipedia pages. The assumption is that a good entity page is a page that answers the query.

• The link extraction module extracts the links from a selected number of highly ranked pages, 3together with the information about the paths of the links (XML paths). The assumption is that a good entity page is a page that is referred to by a page answering the query; this is an adaptation of the Google PageRank [START_REF] Brin | The anatomy of a large-scale hypertextual Web search engine[END_REF] and HITS [START_REF] Kleinberg | Authoritative sources in hyperlinked environment[END_REF] algorithms to the problem of entity ranking.

• The linkrank module calculates a weight for a page based (among other things) on the number of links to this page (see 6.2). The assumption is that a good entity page is a page that is referred to from contexts with many occurrences of the entity examples. A coarse context would be the full page that contains the entity examples. Smaller and better contexts may be elements such as paragraphs, lists, or tables [START_REF] Pehcevski | Exploiting locality of Wikipedia links in entity ranking[END_REF].

• The category similarity module calculates a weight for a page based on the similarity of the page categories with that of the target categories or the categories attached to the entity examples (see 6.3). The assumption is that a good entity page is a page associated with a category close to the target categories or categories of the entity examples.

• The full-text retrieval module calculates a weight for a page based on its initial Zettair score (see 6.4).

The global score for a page is calculated as a linear combination of three normalised scores coming out of the last three modules (see 6.5).

The above architecture provides a general framework for evaluating entity ranking.

LinkRank score

The linkrank function calculates a score for a page, based on the number of links to this page, from the first N pages returned by the search engine in response to the query. We carried out some experiments with different values of N and found that N=20 was an acceptable compromise between performance and discovering more potentially good entities.

We use a very basic linkrank function that, for an answer entity page t that is pointed to by a page p, takes into account the Zettair score of the referring page z(p), and the number of reference links to the answer entity page #links(p, t):

S L (t) = N r=1 z(p r ) * f (#links(p r , t)) (3)
where f (x) = x (when there is no reference link to the answer entity page, f (x) = 0).

The linkrank function can be implemented in a variety of ways; for task 2 where entity examples are provided, we have also experimented by weighting pages containing a number of entity examples, or by exploiting the locality of links around the entity examples [START_REF] Pehcevski | Exploiting locality of Wikipedia links in entity ranking[END_REF]. This more complex implementation of the linkrank function is outside the scope of this paper.

Category score

The basic category score S C (t) is calculated for the two tasks as follows: task 1

S C (t) = |cat(t) ∩ cat(C)| |cat(C)| (4) task 2 S C (t) = |cat(t) ∩ cat(E)| |cat(E)| (5)
We then consider variations on the category score S C (t) given the considerations in Section 5, using various combinations of replacing cat(t) with cat u (t), replacing cat(C) with cat d (C), Ccat(C), Tcat(C) or TCcat(C), and replacing cat(E) with cat u (E).

Z score

The Z score assigns the initial Zettair score to an answer entity page. If the answer page does not appear in the final list of ranked pages returned by Zettair, then its Z score is zero:

S Z (t) =    z(t)

Global score

The global score S(t) for an answer entity page is calculated as a linear combination of three normalised scores, the linkrank score S L (t), the category similarity score S C (t), and the Z score S Z (t):

S(t) = αS L (t) + βS C (t) + (1 -α -β)S Z (t) (7)
where α and β are parameters that can be tuned.

A special case of interest here is when only the category score is used (α = 0.0, β = 1.0). It allows us to evaluate the effectiveness of various category similarity functions and the overall benefit of using categories.

Experimental results

We now present results that investigate the effectiveness of our entity ranking approach for the two entity ranking tasks. We start by describing the test collection we developed for entity ranking.

Test collection

There is no existing set of topics with relevance assessments for entity ranking, although such a set will be developed for the INEX XML entity ranking track in 2007. So for these experiments we developed our own test collection based on a selection of topics from the INEX 2006 ad hoc track. We chose 27 topics that we considered were of an "entity ranking" nature, where for each page that had been assessed as containing relevant information, we reassessed whether or not it was an entity answer, and whether it loosely belonged to a category of entities we had loosely identified as being the target of the topic. If there were entity examples mentioned in the original topic these were usually used as entity examples in the entity topic. Otherwise, a selected number (typically 2 or 3) of entity examples were chosen somewhat arbitrarily from the relevance assessments. To this set of 27 topics we also added the Euro topic example (shown in Figure 1) that we had created by hand from the original INEX description of the entity ranking track [START_REF] Arjen | INEX 2007 Entity ranking track guidelines[END_REF], resulting in total of 28 entity ranking topics.

We use mean average precision (MAP) as our primary method of evaluation, but also report results using several alternative information retrieval measures: mean of P [START_REF] Cucerzan | Large-scale named entity disambiguation based on Wikipedia data[END_REF] and P [START_REF] Sisay Fissaha Adafre | Entity retrieval[END_REF] (mean precision at top 5 or 10 entities returned), and mean R-precision (R-precision for a topic is the P[R], where R is the number of entities that have been judged relevant for the topic). When dealing with entity ranking, the ultimate goal is to retrieve all the answer entities at the top of the ranking. Although we believe that MAP may be more suitable than the other measures in capturing these aspects, part of the track at INEX 2007 will involve determining what is the most suitable measure.

Task 1

For this task we carried out three separate investigations. First, we wanted to investigate the effectiveness of our category similarity module when varying the extensions of the set of categories attached to both the target categories and the answer entities. We also investigated the impact that this variation had on the effectiveness when the two different category indexes are Table 1: Performance scores for runs using different retrieval strategies in our category similarity module (α0.0-β1.0), obtained for task 1 by different evaluation measures. For the three runs using lexical similarity, the Zettair index comprises documents containing category names (C), or documents containing category names and names of entities associated with the category (CE). The number of category answers retrieved by Zettair is M=10. For each measure, the best performing score is shown in bold. used by Zettair. Second, for the best category similarity approach we investigated the optimal value for the parameter M (the number of category answers retrieved by Zettair). Last, for the best category similarity approach using the optimal M value, we investigated the optimal values for the α and β parameters. The aim of this investigation is to find the best score that could be achieved by our entity ranking approach for task 1.

Investigating category similarity approaches

The results of these investigations are shown in Tables 1(C) and 1(CE). 4 Several observations can be drawn from these results. First, the choice of using the Zettair category index can dramatically influence the entity ranking performance. When cross-comparing the results in the two tables, we observe that the three lexical similarity runs using the Zettair index of category names substantially outperform the corresponding runs using the Zettair index of category and entity names. The differences in performance are all statistically significant (p < 0.05). Second, the run that uses the query that combines the terms from the title and the category fields of an INEX topic (TCcat(C)-cat(t)) performs the best among the three runs using lexical similarity, and overall it also performs the best among the five runs when using the Zettair index of category names. However, the differences in performance between this and the other four runs are not statistically significant. Third, extending the set of categories attached to both the target categories and the answer entities overall does not result in an improved performance, although there are some (non-significant) early precision improvements.

Investigating the parameter M

The above results show that the best effectiveness for our category similarity module (α0.0-β1.0) is achieved when using the Zettair index of category names, together with the query strategy that combines the terms from the title and the category fields of an INEX topic. 4 The first two runs do not use any of Zettair's category indexes and are included for comparison. For these experiments we used a fixed value M=10 for the parameter M that represents the number of category answers retrieved by Zettair. However, since this was an arbitrary choice we also investigated whether a different value of M could also have a positive impact on the retrieval effectiveness. We therefore varied M from 1 to 20 in steps of 1, and measured the MAP scores achieved by our best performing TCcat(C)-cat(t) run using the Zettair index of category names. Figure 3 shows the results of this investigation. We observe that a value of 5 for the parameter M yields the highest MAP score (0.242) for our category similarity module, which is a 7% relative performance improvement over the MAP score obtained with M=10. This performance improvement is statistically significant (p < 0.05).

Investigating the combining parameters α and β

To find the best score that could be achieved by our entity ranking approach for task 1, we used the run TCcat(C)-cat(t) with the optimal value M=5 and investigated various combinations of scores obtained from the three modules. We calculated MAP over the 28 topics in our test collection, as we varied α from 0 to 1 in steps of 0.1. For each value of α, we also varied β from 0 to (1α) in steps of 0.1. We found that the highest MAP score (0.287) is achieved for α = 0.1 and β = 0.8. This is a 19% relative performance improvement over the best score achieved by using only the category module (α0.0-β1.0). This performance improvement is statistically significant (p < 0.05). We also calculated the scores using mean R-precision instead of MAP as our evaluation measure, and we again observed the same performance behaviour and optimal values for the two parameters.

Task 2

For this task we carried out two separate investigations. First, as with task 1 we wanted to investigate the effectiveness of our category similarity module when varying the extensions of the set of categories attached to both the example and the answer entities. Second, for the best category similarity approach we investigated the optimal values for the α and β parameters, with the aim of finding the best score that could be achieved by our entity ranking approach for task 2.

Investigating category similarity approaches

The results of these investigations are shown in Table 2. We observe that, as with task 1, extending the set of categories attached to either (or both) of the example and answer entities does not result in an improved performance. The differences in performance between the best performing run that does not use the extended category sets and the other three runs that use any (or both) of these sets are all statistically significant (p < 0.05).

Investigating the combining parameters α and β

To find the best score that could be achieved by our entity ranking approach for task 2, we used the run cat(E)-cat(t) and investigated various combinations of scores obtained from the three modules. We calculated MAP over the 28 topics in our test collection, as we used the 66 combined values for parameters α and β. We found that the highest MAP score (0.396) was again achieved for α = 0.1 and β = 0.8. This score is a 17% relative performance improvement over the best score achieved by using only the category module (α0.0-β1.0). The performance improvement is statistically significant (p < 0.05).

Comparing Task 1 and Task 2

To investigate which of the two query strategies (target categories or example entities) is more effective for entity ranking, we compared the scores of the best performing runs across the two tasks. Table 3 shows the results of this comparison, when separately taking into account two distinct cases: a case when using scores coming out of the category module only (α0.0-β1.0); and a case when using optimal global scores coming out of the three modules (α0.1-β0.8). We observe that, irrespective of whether category or global scores are used by our entity ranking approach, the run that uses the set of categories attached to example entities (task 2) substantially outperforms the run that uses the set of categories identified by Zettair using the topic title and the target categories (task 1). The differences in performance between the two runs are statistically significant (p < 0.05). This finding shows that using example entities is much more effective query strategy than using the loosely defined target categories, which allows for the answer entities to be identified and ranked more accurately.

Conclusions and future work

In this paper, we have presented our entity ranking approach for the INEX Wikipedia XML document collection. We focused on different entity ranking strategies that can be used by our category similarity module, and evaluated these strategies on the two entity ranking tasks. For task 1, we demonstrated that using lexical similarity between category names results in an effective entity ranking approach, so long as the category index comprises documents containing only category names. For task 2, we demonstrated that the best approach is the one that uses the sets of categories directly attached to both the example and the answer entities, and that using various extensions of these two sets significantly decreases the entity ranking performance. For the two tasks, combining scores coming out of the three modules significantly improves the performance compared to that achieved when using scores only from the category module. Importantly, when comparing the scores of the best performing runs across the two tasks, we found that the query strategy that uses example entities to identify the set of target categories is significantly more effective than the strategy that uses the set of loosely defined target categories.

In the future, we plan to further improve the global score of our entity ranking approach by using a better linkrank function that exploits different (static and dynamic) contexts identified around the entity examples. Preliminary results demonstrate that the locality of links around entity examples can indeed be exploited to significantly improve the entity ranking performance compared to the performance achieved when using the full page context [START_REF] Pehcevski | Exploiting locality of Wikipedia links in entity ranking[END_REF]. To improve the category similarity function, we plan to introduce different category weighting rules that we hope would better distinguish the answer entities that are more similar to the entity examples. We will also be participating in the INEX 2007 entity ranking track, which we expect would enable us to test our approach using a larger set of topics.

  Proceedings of the 12thAustralasian Document Computing Symposium, Melbourne, Australia, December 10, 2007. Copyright of this article remains with the authors.

Figure 1 :

 1 Figure 1: Example INEX 2007 XML entity ranking topic

Figure 2 :

 2 Figure 2: Extract from the Euro Wikipedia page

Figure 3 :

 3 Figure 3: Investigating the optimal value for the number of category answers retrieved by Zettair, when using the run TCcat(C)-cat(t).

  if page t was returned by Zettair

	0	otherwise
		(6)

Table 2 :

 2 Performance scores for runs using different retrieval strategies in our category similarity module (α0.0-β1.0), obtained for task 2 by different evaluation measures. For each measure, the best performing score is shown in bold.

		P[r]
	Run	5	10	R-prec MAP
	cat(E)-cat(t)	0.536 0.393 0.332 0.338
	cat(E)-cat u (t)	0.493 0.361 0.294 0.313
	cat u (E)-cat(t)	0.407 0.336 0.275 0.255
	cat u (E)-cat u (t) 0.357 0.332 0.269 0.261

Table 3 :

 3 Comparing best performing runs for task 1 and task 2 for two distinct cases (using either category or global scores). The number of category answers retrieved by Zettair for run TCcat(C)-cat(t) is M=5. For each case, the best results are shown in bold.

		P[r]
	Run	5	10	R-prec MAP
	Category score: α0.0-β1.0
	TCcat(C)-cat(t) 0.307 0.318 0.263 0.242
	cat(E)-cat(t)	0.536 0.393 0.332 0.338
	Global score: α0.1-β0.8
	TCcat(C)-cat(t) 0.379 0.361 0.338 0.287
	cat(E)-cat(t)	0.607 0.457 0.412 0.396

http://labs.google.com/sets

http://www.seg.rmit.edu.au/zettair/

We discarded external links and some internal collection links that do not refer to existing pages in the INEX Wikipedia collection.

Acknowledgements Part of this work was completed while James Thom was visiting INRIA in 2007.