Guillaume Aupy

Anne Benoit

Loïc Pottier

Padma Raghavan

Yves Robert

Manu Shantharam

Co-scheduling algorithms for cache-partitioned systems

Keywords: Co-scheduling, cache partitioning, complexity results Ordonnancement concurrent, partitionnement de cache, résultats de complexité

Cache-partitioned architectures allow subsections of the shared last-level cache (LLC) to be exclusively reserved for some applications. This technique dramatically limits interactions between applications that are concurrently executing on a multi-core machine. Consider n applications that execute concurrently, with the objective to minimize the makespan, defined as the maximum completion time of the n applications. Key scheduling questions are: (i) which proportion of cache and (ii) how many processors should be given to each application? Here, we assign rational numbers of processors to each application, since they can be shared across applications through multi-threading. In this paper, we provide answers to (i) and (ii) for perfectly parallel applications. Even though the problem is shown to be NP-complete, we give key elements to determine the subset of applications that should share the LLC (while remaining ones only use their smaller private cache). Building upon these results, we design efficient heuristics for general applications. Extensive simulations demonstrate the usefulness of co-scheduling when our efficient cache partitioning strategies are deployed.

Introduction

At scale, the I/O movements of HPC applications are expected to be one of the most critical problems [START_REF]Ten technical approaches to address the challenges of Exascale computing[END_REF]. Observations on the Intrepid machine at Argonne National Laboratory (ANL) show that I/O transfers can be slowed down up to 70% due to congestion [START_REF] Gainaru | Scheduling the I/O of HPC applications under congestion[END_REF]. When ANL upgraded its house supercomputer from Intrepid (Peak perf: 0.56 PFlops; peak I/O throughput: 88 GB/s) to Mira (Peak perf: 10 PFlops; peak I/O throughput: 240 GB/s), the net result for an application whose I/O throughput scales linearly (or worse) with performance was a downgrade from 160 GB/PFlop to 24 GB/PFlop! To cope with such an imbalance (which is not expected to reduce on future platforms), a possible approach is to develop in situ co-scheduling analysis and data preprocessing on dedicated nodes [START_REF]Ten technical approaches to address the challenges of Exascale computing[END_REF]. This scheme applies to data-intensive periodic workflows where data is generated by the main simulation, and parallel processes are run to process this data with the constraints that output results should be sent to disk storage before newly generated data arrives for processing. These solutions are starting to be implemented for HPC applications. Sewell et al. [START_REF] Sewell | Large-scale compute-intensive analysis via a combined in-situ and co-scheduling workflow approach[END_REF] explain that in the case of the HACC application (a cosmological code), petabytes of data are created to be analyzed later. The analysis is done by multiple independent processes. The idea of their work is to minimize the amount of data copied to I/O filesystem, by performing the analysis at the same time as HACC is running (what they call in situ). The main constraint is that these processes are data-intensive and are handled by a dedicated machine. Also, the execution of these processes should be done efficiently enough so that they finish before the next batch of data arrives, hence resulting in a pipelined approach. All these frameworks motivate the design of efficient co-scheduling strategies.

One main issue of co-scheduling is to evaluate co-run degradations due to cache sharing [START_REF] Zhuravlev | Addressing shared resource contention in multicore processors via scheduling[END_REF]. Many studies have shown that interferences on the shared last-level cache (LLC) can be detrimental to co-scheduled applications [START_REF] Leverich | Reconciling high server utilization and sub-millisecond quality-of-service[END_REF]. Previous solutions consisted in preventing co-schedule of possibly interfering workloads, or terminating low importance applications [START_REF] Zhang | Smite: Precise QOSprediction on realsystem SMT processors to improve utilization in warehouse scale computers[END_REF]. Lo et al. [START_REF] Lo | Improving resource efficiency at scale with Heracles[END_REF] recently showed experimentally that important gains could be reached by co-scheduling applications with strict cache partitioning enabled. Cache partitioning, the technique at the core of this work, consists in reserving exclusivity of subsections of the LLC of a chip multi-processor (CMP), to some of the applications running on this CMP. This functionality was recently introduced by Intel under the name Cache Allocation Technology [START_REF]Intel 64 and IA-32 architectures software developer's manual[END_REF]. With the advent of large shared memory multi-core machines (e.g., Sunway TaihuLight, the current #1 supercomputer uses 256-cores processor chips with a shared memory of 32GB [START_REF] Dongarra | Report on the sunway taihulight system[END_REF]), the design of algorithms that co-schedule applications efficiently and decide how to partition the shared memory (seen as the cache here), is becoming critical.

In this work, we study the following problem: given a set of parallel applications, a multi-core processor with a shared last-level cache LLC, how can we best partition the LLC to minimize the total execution time (or makespan), i.e., the moment when the last application finishes its computation. For each application, we assume that we know the number of compute operations to perform, and the miss rate on a fixed size cache. For the multi-core processor, we know its LLC size, the cost for a cache miss, the cost for a cache hit, the size of the cache and total number of processors. We assume that these processors can be shared by two applications through multi-threading [START_REF] Krishna | Data sharing in multi-threaded applications and its impact on chip design[END_REF], hence we assign fractional number of processors to each application. In addition to being very natural in practice, this relaxation of the problem avoids artefacts due to rounding when assigning only integer numbers of processors, and allows us to study the intrinsic complexity of co-scheduling with cache partitioning. Equipped with all these applications and platform parameters, recent work [START_REF] Hartstein | On the nature of Is it √ 2[END_REF][START_REF] Rogers | Scaling the bandwidth wall: challenges in and avenues for CMP scaling[END_REF][START_REF] Krishna | Data sharing in multi-threaded applications and its impact on chip design[END_REF] shows how to model the impact of cache misses and to accurately predict the execution time of an application. In this context, we make the following main contributions: • We show that the co-scheduling problem is NP-complete, even when applications are perfectly parallel, i.e., their speed-up scales up linearly with the number of processors. • In the case of perfectly parallel applications, we show several results that characterize optimal solutions. We show that the co-scheduling cache-partitioning problem reduces to deciding which subset of applications will share the LLC; when this subset is known, we show how to determine the optimal cache fractions and number of processors.

• While these results only hold for perfectly parallel applications, they guide the design of heuristics for general applications. We show through extensive simulations that our heuristics greatly improve the performance of cache-partitioning algorithms, even for parallel applications obeying Amdahl's law with a large sequential fraction, hence with a limited speedup profile.

The rest of the paper is organized as follows. Section 2 provides an overview of related work. Section 3 is devoted to formally defining the framework and all model parameters. Section 4 gives our main theoretical contributions. The heuristics are defined in Section 5, and evaluated through simulations in Section 6. Finally, Section 7 outlines our main findings and discusses directions for future work.

Related work

Since the advent of systems with tens of cores, co-scheduling has received considerable attention. Due to lack of space, we refer to [START_REF] Muralidhara | Reducing memory interference in multicore systems via application-aware memory channel partitioning[END_REF][START_REF] Dauwe | A methodology for co-location aware application performance modeling in multicore computing[END_REF][START_REF] Lo | Improving resource efficiency at scale with Heracles[END_REF] for a survey of many approaches to co-scheduling. The main idea is to execute several applications concurrently rather than in sequence, with the objective to increase platform throughput. Indeed, some individual applications may well not need all available cores, or some others could use all resources, but at the price of a dramatic performance loss. In particular, the latter case is encountered whenever application speedup becomes too low beyond a given processor count.

The main difficulty of co-scheduling is to decide which applications to execute concurrently, and how many cores to assign to each of them. Indeed, when executing simultaneously, any two applications will compete for shared resources, which will create interferences and decrease their throughput. Modeling application interference is a challenging task. Dynamic schedulers are used when application behavior is unknown [START_REF] Qureshi | Utility-based cache partitioning: A low-overhead, highperformance, runtime mechanism to partition shared caches[END_REF][START_REF] Tian | A study on optimally co-scheduling jobs of different lengths on chip multiprocessors[END_REF]. Static schedulers aim at optimizing the sharing of the resources by relying on application knowledge such as estimated workload, speed-up profile, cache behavior, etc. One widely-used approach is to build an interference graph whose vertices are applications and whose edges represent degradation factors [START_REF] Jiang | Analysis and approximation of optimal coscheduling on chip multiprocessors[END_REF][START_REF] Zhu | Modelling and developing co-scheduling strategies on multicore processors[END_REF][START_REF] He | Developing graph-based co-scheduling algorithms on multicore computers[END_REF]. This approach is interesting but hard to implement. Indeed, the interaction of two applications depends on many factors, such as their size, their core count, the memory bandwidth, etc. Obtaining the speedup profile of a single application already is difficult and requires intensive benchmarking campaigns. Obtaining the degradation profile of two applications is even more difficult and can be achieved only for regular applications. To further darken the picture, the interference graph subsumes only pairwise interactions, while a global picture of the processor and cache requirements for all applications is needed by the scheduler.

Shared resources include cache, memory, I/O channels and network links, but among potential degradation factors, cache accesses are prominent. When several applications share the cache, they are granted a fraction of cache lines as opposed to the whole cache, and their cache miss ratio increases accordingly. Multiple cache partitioning strategies have been proposed [START_REF] Bui | Impact of cache partitioning on multitasking real time embedded systems[END_REF][START_REF] Guan | Cache-aware scheduling and analysis for multicores[END_REF][START_REF] Blagodurov | Contention-aware scheduling on multicore systems[END_REF][START_REF] Dwyer | A practical method for estimating performance degradation on multicore processors, and its application to hpc workloads[END_REF]. In this paper, we focus on a static allocation of LLC cache fractions, and processor numbers, to concurrent applications as a function of several parameters (cache-miss ratio, access frequency, operation count). To the best of our knowledge, this work is the first analytical model and Inria complexity study for this challenging problem.

Model

This section details all platform and application parameters, and formally states the optimization problem.

Architecture. We consider a parallel platform of p homogeneous computing elements, or processors, that share two storage locations:

• A small storage S s with low latency, governed by a LRU replacement policy, also called cache;

• A large storage S l with high latency, also called memory. More specifically, C s (resp. C l ) denotes the size of S s (resp. S l ), and l s (resp. l l ) the latency of S s (resp. S l ). In this work, we assume that C l = +∞. We have the relation l s l l . In this work, we consider the cache partitioning technique [START_REF]Intel 64 and IA-32 architectures software developer's manual[END_REF], where one can allocate a portion of the cache to applications so that they can execute without interference from other applications.

Applications. There are n independent parallel applications to be scheduled on the parallel platform, whose speedup profiles obey Amdahl's law [START_REF] Amdahl | The validity of the single processor approach to achieving large scale computing capabilities[END_REF]. For an application T i , we define several parameters:

• w i , the number of computing operations needed for T i ;

• s i , the sequential fraction of T i ;

• f i , the frequency of data accesses of T i : f i is the number of data accesses per computing operation; • a i , the memory footprint of T i . We use these parameters to model the execution of each application as follows.

The power law of cache misses In chip multi-processors, many authors have observed that the Power Law accurately models how the cache size affects the miss rate [START_REF] Hartstein | On the nature of Is it √ 2[END_REF][START_REF] Rogers | Scaling the bandwidth wall: challenges in and avenues for CMP scaling[END_REF][START_REF] Krishna | Data sharing in multi-threaded applications and its impact on chip design[END_REF]. Mathematically, the power law states that if m 0 is the miss rate of a workload for a baseline cache size C 0 , the miss rate m for a new cache size C can be expressed as m = m 0 C0 C α where α is the sensitivity factor from the Power Law of Cache Misses [START_REF] Hartstein | On the nature of Is it √ 2[END_REF][START_REF] Rogers | Scaling the bandwidth wall: challenges in and avenues for CMP scaling[END_REF][START_REF] Krishna | Data sharing in multi-threaded applications and its impact on chip design[END_REF] and typically ranges between 0.3 and 0.7 with an average at 0.5. Note that, by definition, a rate cannot be higher than 1, hence we extend this definition as:

m = min 1, m 0 C 0 C α . (1)
This formula can be read as follows: if the cache size allocated is too small, then the execution goes as if no cache was allocated, and all accesses will be misses.

Computations and data movement

We use the cost model introduced by Krishna et al. [START_REF] Krishna | Data sharing in multi-threaded applications and its impact on chip design[END_REF] to evaluate the execution cost of an application as a function of the cache fraction that it has been allocated. Specifically, for each application, we define m 0 , the miss rate of application T i with a cache of size C 0 (we can also use the miss rate of applications with a cache of another fixed size). We express the execution time of T i as a function of p i , the number of processors allocated to T i , and x i , the fraction of S s allocated to T i (recall both are rational numbers). Let F l i (p i ) be the number of operations performed by each processor for application T i , given that the application is executed on p i processors. We have F l i (p i ) = s i w i + (1 -s i ) wi pi according to Amdahl's speedup profile. Finally,

Exei(pi, xi) =                    F li(pi) 1 + fi ls + l l • min 1, m 0 x i Cs C 0 α if xiCs ≤ ai; F li(pi) 1 + fi ls + l l • min 1, m 0 a i C 0 α otherwise. (2)
Indeed, for each operation, we pay the cost of the computing operation, plus the cost of data accesses, and by definition we have f i accesses per operation. At each access, we pay a latency l s , and an additional latency l l in case of cache miss (see Equation ( 1)). The second case states that we cannot use a portion of cache greater than the memory footprint a i of application T i . This model is somewhat pessimistic: cache accesses to the same variable by two different processors are counted twice. We show in Section 6 that despite this conservative assumption (no sharing), co-scheduling can outperform classical approaches that sequentially deploy each application on the whole set of available resources.

Equation ( 2) calls for a few observations. For notational convenience, let

d i = m 0 C0 Cs α :
• It is useless to give a fraction of cache larger than ai Cs to application

T i ; • Because of the minimum min 1, di (xi) α , either x i > d 1 α
i , or x i = 0: indeed, if we give application T i a fraction of cache smaller than d

1 α
i , the minimum is equal to 1, and this fraction is wasted. Hence, we have for all i:

x i = 0 or d 1 α i < x i ≤ a i C s . (3)
Of course, if d

1 α
i ≥ ai Cs for some application T i , then x i = 0.

Scheduling problem.

Given n applications T 1 , . . . , T n , we aim at partitioning the shared cache and assign processors so that the concurrent execution of these applications takes minimal time. In other words, we aim at minimizing the execution time of the longest application, when all applications start their execution at the same time. Formally: Definition 1 (CoSchedCache). Given n applications T 1 , . . . , T n and a platform with p identical processors sharing a cache of size C s , find a schedule {(p 1 , x 1 ), . . . , (p n , x n )} with n i=1 p i ≤ p, and

n i=1 x i ≤ 1, that minimizes max 1≤i≤n Exe i (p i , x i ).

Complexity Results for Perfectly Parallel Applications

In this section, we consider CoSchedCache with perfectly parallel applications. A perfectly parallel application T i is an application with s i = 0, so that Exe i (p i , x i ) = Exei (1,xi) pi . Let Exe seq i (x i ) = Exe i (1, x i ) be the sequential execution time of application T i with a fraction of cache x i . The main results are the NP-completeness of CoSchedCache, and several dominance results on the optimal solution. While these results only hold for perfectly parallel applications, they will guide the design of heuristics for general applications in Section 5.

Inria

Intractability

We formally state the decision problem associated to CoSchedCache: Definition 2 (CoSchedCache-Dec). Given n perfectly parallel applications T 1 , . . . , T n and a platform with p identical processors sharing a cache of size C s , and given a bound K on the makespan, does there exist a schedule {(p 1 , x 1 ), . . . , (p n , x n )}, where p i and x i are nonnegative rational numbers with

n i=1 p i ≤ p and n i=1 x i ≤ 1, such that max 1≤i≤n Exe i (p i , x i ) ≤ K? Theorem 1. CoSchedCache-Dec is NP-complete.
Proof. For perfectly parallel applications, we can transform CoSchedCache into an equivalent problem that does not depend on the number of processors but that relies simply on the cache partitioning strategy (Lemma 3 below). This result will guide processor assignment for general applications in Section 5. We start with a few lemmas. The first lemma shows that all applications complete at the same time in an optimal execution: Lemma 1. To minimize the makespan, all applications must finish at the same time.

Proof. Consider the n perfectly parallel applications T 1 , . . . , T n and a solution S = {(p i , x i )} 1≤i≤n to CoSchedCache. Let D S = max i Exe i (p i , x i ) be the makespan of this solution. We denote by I S the set of applications whose execution time is exactly D S .

We show the result by contradiction. We consider an optimal solution S whose subset I S has minimal size (i.e., for any other optimal solution S o , |I S | ≤ |I So |). Then we show that if |I S | = n, we can construct a solution S with either (i) a smaller makespan if |I S | = 1 (contradicting the optimality hypothesis), or (ii) one less application whose execution time is exactly D S (contradicting the minimality hypothesis). Assume |I S | = n, let T i0 / ∈ I S and T i1 ∈ I S . We have Exe i0 (p i0 , x i0 ) < Exe i1 (p i1 , x i1 ) = D S . We define

ε = p i0 p i1 Exe i1 (p i1 , x i1 ) -Exe i0 (p i0 , x i0 ) Exe seq i0 (x i0 ) + Exe seq i1 (x i1 ) = p i0 Exe seq i1 (x i1 ) -p i1 Exe seq i0 (x i0 ) Exe seq i0 (x i0 ) + Exe seq i1 (x i1 ) > 0. Then clearly, S = {(p i , x i )} i where p i is (i) p i if i / ∈ {i 0 , i 1 }, (ii) p i0 -ε if i = i 0 , (iii) p i1 +ε if i = i 1 , is a valid solution: we have the property i p i = i p i ≤ p, and i x i = i x i ≤ 1. Furthermore, one can verify that Exe i1 (p i1 , x i1 ) = Exe i0 (p i0 , x i0 ) = Exe seq i 0 (xi 0 )+Exe seq i 1 (xi 1 ) pi 0 +pi 1 . Be- cause p i1 > p i1 , Exe i1 (p i1 , x i1 ) < Exe i1 (p i1 , x i1 ) = D S . Hence: • If |I S | = 1, then for all i, Exe i (p i , x i ) < D S , hence showing that S is not optimal. • Else, I S = I S \ {i 1 }, and D S = D S , hence showing that S is not minimal. This shows that necessarily, |I S | = n.
The second lemma shows the optimal processor assignment: Lemma 2. Given n applications T 1 , . . . , T n and a partitioning of the cache {x 1 , . . . , x n }, then the optimal number of processors for application T i (i ∈ {1, . . . , n}) is:

p i = p Exe seq i (x i ) n j=1 Exe seq j (x j )
.

RR n°8965

Proof. According to Lemma 1, all applications finish at the same time. Given i 0 ∈ {1, . . . , n}, we have

Exe seq i 0 (xi 0 ) pi 0 = Exe seq i (xi) pi
for all 1 ≤ i ≤ n. In addition, we have n i=1 p i = p: the fact that this bound is tight in an optimal solution is due to the fact that we have perfectly parallel applications. We express p in terms of the others variables, and we do the summation:

p = n i=1 p i = pi 0 Exe seq i 0 (xi 0 ) n i=1 Exe seq i (x i
) . This directly leads to the result.

Lemmas 1 and 2 lead to the following reformulation of CoSchedCache:

Lemma 3. CoSchedCache can be rewritten as finding the optimal cache partitioning strategy X = {x 1 , . . . , x n } that minimizes the completion time of an optimal solution:

1 p n i=1 Exe i (1, x i ). ( 4
)
Proof. Lemma 2 gives us that in an optimal solution the processor distribution is uniquely determined by the cache partitioning strategy. Furthermore, given a cache partitioning strategy, we know that all applications finish at the same time (Lemma 1) and that the completion time is equal to

Exe seq 1 (x 1 ) p 1 = n i=1 Exe seq i (x i ) p .
We are now ready for the proof of Theorem 1. CoSchedCache-Dec is obviously in NP: given the x i 's, it is easy to verify all constraints in linear time. We prove the completeness by a reduction from Knapsack, which is NP-complete [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]. Consider an arbitrary instance I 1 of Knapsack: given n objects, each with positive integer size u i and positive integer value v i for 1 ≤ i ≤ n, and two positive integer bounds U and V , does there exist a subset I ⊂ {1, . . . , n} such that i∈I u i ≤ U and i∈I v i ≥ V ? Given I 1 , we construct the following instance I 2 of CoSchedCache-Dec:

• We define two constants ε = 1 N (N +1) and η = 1 -1 N , where N = max(n, 2U + 1). • We let d i = uiη U α , e i = d 1 α i + ε α , a i = e 1 α i C s , and w i f i l l = vi 1- d i e i
for 1 ≤ i ≤ n. Note that we only need the value of the product w i f i , and we can set one of them arbitrarily.

• The bound K is defined as:

pK = n i=1 w i (1 + f i l s ) + n i=1 w i f i l l -V.
To simplify notations, let

z i = w i f i l l . Letting A = n i=1 w i (1 + f i l s ) and Z = n i=1 z i , we get pK = A + Z -V . Also, we have n i=1 w i 1 + f i l s + l l • min 1, di x α i = A + B, where B = n i=1 z i min(1, di x α i
). Recall from Lemma 3 that I 2 has a solution if and only if 1 p (A+B) ≤ K. Let I C ⊆ {1, . . . , n} denote the subset of applications that are given some cache (x i = 0 if and only if i ∈ I C ). We also call I C the nonzero subset of I 2 . We have

d 1 α i ≤ x i ≤ a i C s = e 1 α i , so that we can rewrite B = Z -i∈I C z i 1 -di x α i
. Given the value of the bound K, we have

A + B ≤ pK if and only if i∈I C z i (1 - d i x α i ) ≥ V.

Inria

We show that I 1 has a solution if and only if I 2 does. Suppose first that I 1 has a solution subset I ⊂ {1, . . . , n}. Then we let x i = e 1 α i if i ∈ I and x i = 0 otherwise. This is a valid solution to I 2 with nonzero subset I C = I. Indeed:

• If i ∈ I, then d 1 α i ≤ x i = e 1 α i = ai Cs . • We have i∈I x i = i∈I (d 1 α i + ε) = i∈I u i η U + |I|ε.
But i∈I uiη U ≤ η (since we have a solution for I 1 ), and

|I|ε ≤ nε ≤ 1 N +1 , hence i∈I x i ≤ η + 1 N +1 ≤ 1. • Finally, i∈I z i (1 -di x α i ) = i∈I z i (1 -di ei ) = i∈I v i ≥ V (since we have a solution for I 1 ), hence A + B ≤ pK.
Suppose now that I 2 has a solution, and let I C be its nonzero subset. We claim that I = I C is a solution to I 1 . Indeed, for i ∈ I C we have

d i ≤ x α i ≤ e i and i∈I C z i (1 -di x α i ) ≥ V . First, we have i∈I C z i (1 -di x α i ) ≥ i∈I C z i (1 -di ei ) = i∈I C v i , hence i∈I C v i ≥ V . Then i∈I C d 1 α i ≤ i∈I C x i ≤ 1, and i∈I C d 1 α i = i∈I C uiη U , hence i∈I C u i ≤ U η . But U η ≤ U + 1 2 by the choice of η, thus i∈I C u i ≤ U + 1 2 .
Because the sizes are integers, i∈I C u i ≤ U . Altogether, I C is indeed a solution to I 1 . This concludes the proof.

Dominance results

In this section, we provide dominance results that will guide the design of heuristics. In addition to restricting to perfectly parallel applications (s i = 0), we assume that application memory footprints are larger than the cache size (a i = +∞). The core of the previous intractability result relies on the hardness to determine the set of applications that receive a cache fraction (denoted by I C ) and those that do not (denoted by I C ). In this section, we show (i) how to determine the optimal solution when these sets I C and I C are known, and (ii) whether one can disqualify some partitions as being sub-optimal.

In particular, we define a set of partitions of applications that we call dominant (Definition 4). We show that (i) if a partition of applications I C , I C is dominant, then we can compute the minimum execution time for this partition, and (ii) if a partition is not dominant, then we can find a better dominant partition. We start by rewriting the problem when the partitioning I C , I C of applications is known:

Definition 3 (CoSchedCache-Part I C , I C ).
Given a set of applications T 1 , . . . , T n and a partition I C , I C , CoSchedCache-Part I C , I C is the problem to find a set X = {x 1 , . . . , x n } that minimizes the execution time:

1 p   i∈I C w i (1 + f i (l s + l l )) + i∈I C w i (1 + f i l s + f i l l d i x α i )   under the constraints x i = 0 if i ∈ I C , x i > d 1/α i if i ∈ I C , and 1≤i≤n x i ≤ 1.
We now relax some bounds in CoSchedCache-Part I C , I C and define CoSchedCache-Ext I C , I C , which is the same problem except that the constraints on the x i 's when i ∈ I C is relaxed: we have instead

x i ≥ 0 if i ∈ I C .
x i = (w i f i d i ) 1/(α+1) j∈I C (w j f j d j ) 1/(α+1) if i ∈ I C , x i = 0 otherwise.
Proof. We want to compute X = {x 1 , . . . , x n } that minimizes the execution time. Discarding constant factors, this reduces to minimizing

K(X ) = i∈I C w i f i d i x α i under the constraints: x i = 0 if i ∈ I C , x i ≥ 0 otherwise, and i x i ≤ 1.
Clearly, one can see that this last inequality is an equality when

I C = ∅ (otherwise K is not minimum).
To minimize the function, we compute the partial derivatives of K:

∀i ∈ I C , ∂K(X ) ∂x i = -α w i f i d i x α+1 i .
By setting them all to 0, we obtain the following equality for 1 ≤ i ≤ n:

-α w i f i d i x α+1 i = -α w n f n d n x α+1 n .
Hence,

∀i ∈ I C , x i = x n (w i f i d i ) 1 α+1 (w n f n d n ) 1 α+1 ; n i=1 x i = x n (w n f n d n ) 1 α+1 i∈I C (w i f i d i ) 1 α+1 = 1.
Hence, the desired result.

Definition 4 (Dominant partition). Given a set of applications T 1 , . . . , T n , we say that a partition of these applications

I C , I C is dominant, if for all i ∈ I C , (w i f i d i ) 1/(α+1) j∈I C (w j f j d j ) 1/(α+1) > d 1/α i .
We can now state the following result:

Theorem 2. If a partition I C , I C is not dominant, then we can compute in polynomial time a better solution.

Inria

Proof. Let I C , I C be a non-dominant partition.

Let i 0 ∈ I C such that (wi 0 fi 0 di 0 ) 1/(α+1) j∈I C (wj fj dj ) 1/(α+1) ≤ d 1/α i0 .
First we can show that there is i 1 ∈ I C \{i 0 }. Indeed, otherwise we would have (wi 0 fi 0 di 0 )

1/(α+1) j∈I C
(wj fj dj ) 1/(α+1) = 1 ≤ d Then clearly X is a solution, and we have:

Exe seq i0 (x i0 ) ≤ w i0 1 + f i0 l s + f i0 l l d i0 x α i0 ; Exe seq i1 (x i1 ) < w i1 1 + f i1 l s + f i1 l l d i0 x α i1 ; ( 5
)
Exe seq i (x i ) ≤ w i 1 + f i l s + f i l l d i x α i if i ∈ I C ; Exe seq i (x i ) = w i (1 + f i (l s + l l )) if i ∈ I C .
Indeed, these results are direct consequences of the definition of Exe seq , except Equation ( 5), which we establish as follows:

• If x i1 ≥ d 1/α i1 , then xi1 > d 1/α i1 Exe seq i1 (x i1 ) = w i1 1 + f i1 l s + f i1 l l d i0 xα i1 < w i1 1 + f i1 l s + f i1 l l d i0 x α i1 . • If x i1 < d 1/α i1 , then for all x ∈ [0, 1], Exe seq i1 (x) < w i1 1 + f i1 l s + f i1 l l di 0 x α i 1
.

Hence:

1 p n i=1 Exe seq i (x i ) < 1 p i∈I C w i (1 + f i (l s + l l )) + i∈I C w i (1 + f i l s + f i l l d i x α i ) = T e ≤ T p ,
which shows that X is a better solution computed in polynomial time from X . Furthermore, by construction of X , we have strictly decreased the size of the new set I C .

Finally, we can show a second dominance result:

Theorem 3. If a partition I C , I C is dominant, then the optimal solution to CoSchedCache-Part I C , I C is:

x i = (w i f i d i ) 1/(α+1) j∈I C (w j f j d j ) 1/(α+1) if i ∈ I C ; x i = 0 otherwise.
Proof. This is a corollary of Lemma 4, this solution is the optimal solution to CoSchedCache-Ext I C , I C and it is a valid solution to CoSchedCache-Part I C , I C , hence it is the optimal solution to CoSchedCache-Part I C , I C .

Heuristics

In this section, we aim at designing efficient heuristics for general applications that obey Amdahl's law, and whose memory footprints are larger than the cache size (a i = +∞). However, the CoSchedCache problem seems to be very difficult for such applications. In particular, Lemma 2 does not hold, and we have no guideline to decide how many processors to assign. We simplify the design of the heuristics by temporarily allocating processors as if the applications were perfectly parallel, and then concentrating on strategies that partition the cache efficiently among some applications (and give no cache fraction to remaining ones). In accordance with Theorem 2, our goal is to compute dominant partitions. Recall that I C represents the subset of applications that receive a fraction fo the cache. Once a dominant partition is given, we obtain the schedule S = {(x i , p i )} i as follows: first we determine the x i 's with Theorem 3, and then we recompute the p i 's so that all applications complete simultaneously at time K. However, there is no longer a nice analytical characterization of the makespan K, hence we use a binary search to compute K as follows: for each application T i , the execution time writes (s i + 1-si pi )c i = K, where s i is the sequential fraction, and

c i = w i (1 + f i (l s + l l di x α i )) if T i ∈ I C , or c i = w i (1 + f i (l s + l l )) otherwise. From n i=1 p i = p, we derive the equation n i=1 1 -s i K ci -s i = p
and we compute K through a binary search. A lower (resp. upper) bound for K is to assign p (resp. 1) processor(s) to each application.

To compute dominant partitions, we use two greedy strategies: • Dominant: we start with I C = I and greedily remove some applications from I C until we have a dominant partition (see Algorithm 1); • DominantRev: initially I C is empty, and we greedily add applications while I C remains dominant (see Algorithm 2).

In both strategies, the greedy criterion to select the next application is the choice function taken from the following three alternatives: • Random: choice(I) picks up randomly one application among all applications; Algorithm 1: Dominant partition, starting with all applications • MinRatio considers the ratio that appears in Definition 4 (dominant partitions), and chooses an application with a small ratio:

1 procedure Dominant (I, choice) begin 2 IC ← I; 3 while ∃i ∈ IC s.t. (w i f i d i ) 1/(α+1) d 1/α i ≥ j∈I C (wjfjdj) 1/(α+1) do 4 k ← choice(IC );
(w i f i d i ) 1/(α+1) d 1/α i < j∈I C (wjfjdj)
choice(I) = arg min i∈I (w i f i d i ) 1/(α+1) d 1/α i ;
• MaxRatio proceeds the other way round, by choosing an application with a large ratio:

choice(I) = arg max i∈I (w i f i d i ) 1/(α+1) d 1/α i .
The intuition behind these heuristics is the following: applications that render a solution non dominant are such that (see Definition 4):

(w i f i d i ) 1/(α+1) d 1/α i ≤ j∈I C (w j f j d j )
1/(α+1) .

Hence, we expect to reach dominance faster by removing from a non-dominant solution applications with low (wifidi) 1/(α+1) d 1/α i (left term of the equation). Intuitively, Dominant should work well with the MinRatio criterion. For symmetric reasons, we expect DominantRev to work well with the MaxRatio criterion. These intuitions will be experimentally confirmed in Section 6. Altogether, by combining two strategies and three different choice functions, we obtain six heuristics to build dominant partitions.

Simulations

To assess the efficiency of the heuristics defined in Section 5, we have performed extensive simulations. The simulation settings are discussed in Section 6.1, and results are presented in Sections 6.2 and 6.3. The code is publicly available at http://perso.ens-lyon.fr/loic.pottier/ archives/simu-cache.zip.

Simulation settings

We use data from applicative benchmarks to run the experiments. Table 1 provides a brief description of the NAS Parallel Benchmark (NPB) suite [START_REF] Bailey | The NAS Parallel Benchmarks&Mdash;Summary and Preliminary Results[END_REF], and for these six HPC applications. We obtain the values shown in Table 2 by instrumenting and simulating the benchmarks (CLASS=A) on 16 cores using PEBIL [START_REF] Laurenzano | PEBIL: Efficient static binary instrumentation for Linux[END_REF]. For the simulations, we use a cache configuration representing an Intel Xeon CPU E5-2690, with a 20MB last level cache per processor of 8 cores. Since the cache miss ratio is defined for a 40MB cache, we have

d i = m i 40MBSs 40×10 6 Cs α .
We build synthetic applications from Table 2 by varying the work w i randomly between 1E+8 and 1E+12. Other data sets building upon these applications have been used (see the Appendix A), and the results are very similar. The sequential fraction of work s i is taken randomly between 1% and 15%.

For the execution platform, we consider one manycore Sunway TaihuLight [START_REF] Dongarra | Report on the sunway taihulight system[END_REF] with 256 processors and a shared memory of 32GB. We chose this platform because of its high core count. Strictly speaking, this platform does not have a last level cache (LLC), but the shared memory can be seen as the LLC, using the disk as the large memory. We have C s = 32000 × 10 6 . The large storage latency l l is set to 1. The small storage latency l s is set to 0.17. According to the literature [START_REF] Kultursay | Evaluating STT-RAM as an energy-efficient main memory alternative[END_REF][START_REF] Molka | Cache coherence protocol and memory performance of the intel haswell-ep architecture[END_REF][START_REF] Pena | Toward the efficient use of multiple explicitly managed memory subsystems[END_REF], the last level cache (LLC) latency is on average four to ten times better than the DDR latency, and we enforce a ratio of 5.88 in the simulations. We have used different ratios in Appendix A, and they lead to similar results. Finally, the Power Law parameter is fixed to α = 0.5. We execute each heuristic 50 times and we compute the average makespan, i.e., the longest execution time among all co-scheduled applications.

In Section 6.2, we provide a comparison of the six heuristics of Section 5, before assessing the gain due to co-scheduling in Section 6.3.

Comparison of the six heuristics

Figure 1 shows the normalized makespan obtained by the six variants of heuristics building dominant partitions. Results are normalized with the makespan of AllProcCache, which is the execution without any co-scheduling: in the AllProcCache heuristic, applications are executed sequentially, each using all processors and all the cache. We vary the number of applications from 1 to 256 on 256 processors. The six heuristics obtain similarly good results, with a gain of 85% over AllProcCache as soon as there are at least 50 applications.

Since all six variants show the same performance on the previous data sets, we investigate the impact of the cache miss rate by varying it between 0 and 1 with a LLC of C s = 1GB in Figure 2. Results are now normalized with DominantMinRatio, which enables to zoom out the differences. Actually, DominantMinRatio and DominantRevMaxRatio are always the best (their plots overlap), while DominantMaxRatio and DominantRevMinRatio are almost always the worst (again, their plots overlap), hence confirming the intuition in Section 5. The random variants lay in between. We use a 1GB LLC to show the impact of cache miss rate on heuristic behaviors. We observe that there are some differences between heuristics only when the cache miss ratio becomes greater than 0.1. According to current data, m 40MBSs range from 1E-02 to 1E-04. In addition, these differences are visible only with a small shared memory (1GB in the example) while our execution platform has a 32GB shared memory. Overall, for the system used in these simulations, all heuristics perform similarly, even though DominantMinRatio and DominantRevMaxRatio seem to perform best in all other settings that we tried (see Appendix A). Therefore, for clarity, we plot only one heuristic based on dominant partitions in the remaining simulations, namely DominantMinRatio.

Gain with co-scheduling

In this section, we assess the gain due to co-scheduling by comparing DominantMinRatio with AllProcCache and with three other heuristics:

• Fair gives p i = p n processors, and a fraction of cache x i = fi n j=1 fj to each application; • 0cache gives no cache to any application, i.e., x i = 0 for 1 ≤ i ≤ n, and then it computes the p i 's so that all applications finish at the same time;

• RandomPart randomly partitions applications with and without cache. For those in cache, the x i 's are computed with the method used for dominant partitions. Then, the p i 's are computed so that all applications finish at the same time.

Impact of the number of applications. Figure 3 (normalized with AllProcCache) shows the impact of the number of applications when the number of processors is fixed to 256. We see that DominantMinRatio outperforms the other heuristics, hence showing the efficiency of our approach based on dominant partitions. Results are also normalized with DominantMinRatio, so that we can better observe the differences between co-scheduling heuristics. Fair exhibits good results only for a small number of applications, when all applications can fit into cache. Otherwise, the use of dominant partitions is much more efficient, as seen with RandomPart, or even 0cache that does not use cache but ensures that all applications finish at the same time.

Figure 4 shows the impact of the average number of processors per application. Here, results are normalized with DominantMinRatio again, and they are similar. In particular, we see that 0cache is better than Fair when there are many processors to share between applications, even though it is not using the cache at all. These results show the accuracy of the model and the benefits of using dominant partitions. Finally, we note the importance of cache partitioning, since the difference between 0cache and DominantMinRatio relies on cache allocation.

Inria

Impact of the number of processors. Figure 5 (normalized with AllProcCache) shows the impact of the number of processors when the number of applications is fixed to 16. When the number of processors increases, the gain of co-scheduling increases. DominantMinRatio is clearly the best heuristic. RandomPart, which builds a random partition instead of a dominant one, is outperformed by DominantMinRatio, and the latter is the only heuristic that surpasses AllProcCache when the number of processors is low. So, building a dominant partition seems a good strategy to optimize the makespan.

The normalization with DominantMinRatio shows that when the number of processors increases, Fair becomes better, while RandomPart and 0cache are quite stable since they are based on the same model as DominantMinRatio. The only difference between 0cache and DominantMinRatio is the cache allocation strategy, and the gain from cleverly distributing cache fractions across applications exceeds 20%. With more applications, we obtain the same ranking of heuristics, except that Fair is always the worst heuristic: since there are less processors on average per application, a good co-scheduling policy is necessary (see Appendix A for detailed results).

Impact of the sequential fraction of work. Figure 6 (normalized with AllProcCache) shows the impact of the sequential part s i when the number of processors is fixed to 256. The number of applications is fixed to 16. As expected, when the sequential fraction of work increases, all co-scheduling heuristics perform better than AllProcCache, and DominantMinRatio is always the best heuristic. It leads to a gain of more than 50% when s i = 0.01.

The normalization with DominantMinRatio better shows the impact of the sequential part: we observe that when the sequential fraction of work increases, Fair obtains results closer to DominantMinRatio.

Processor and cache repartition.

Figure 7 shows the processor repartition and cache repartition when we vary the number of applications from 1 to 256 with 256 processors. We use an error bar plot where the error interval represents here the maximum and minimum number of processors (or cache fraction) allocated to an application. As expected, we observe that the range between minimum and maximum decreases when the number of applications increases. For Fair, the maximum is always equal to the minimum because we allocate the same number of processors to each application. Since all dominant partition heuristics give the same results, we only use DominantMinRatio. The repartition of processors for 0cache is interesting: it turns out to be very close to the repartition obtained with DominantMinRatio, even though it is not using cache.

Summary.

To summarize, all heuristics based on dominant partitions are very efficient, especially when compared to the classical heuristics Fair (which share the cache fairly between applications) and AllProcCache (which does no co-scheduling). The unexpected result that can be observed is that the gain brought by our heuristics comes even with very low sequential time (below 0.01)! This is unexpected since the natural intuition would be a behavior such as

Inria

the one observed on Fair: a makespan up to 1.9 times longer than AllProcCache with low sequential time.

We show that the ratio processors/applications has a significant impact on performance: when many processors are available for a few applications, it is less crucial to use efficient cachepartitioning and all applications can share the cache, hence Fair obtains good results, close to DominantMinRatio. Otherwise, RandomPart is the second best heuristic, followed by 0cache that does not use the cache, then Fair and AllProcCache.

All heuristics run within a very small time (less than ten seconds in the worst of the settings used, to be compared with a typical application execution time in hours or days), hence they can be used in practice with a very light overhead.

Conclusion

In this paper, we have provided a preliminary study on co-scheduling algorithms for cachepartitioned systems, building upon a theoretical study for perfectly parallel applications. The two key scheduling questions are (i) which proportion of cache and (ii) how many processors should be given to each application. We proved that the problem is NP-complete, but we have been able to characterize optimal solutions for perfectly parallel applications by introducing the concept of dominant partitions: for such applications, we have computed the optimal proportion of cache to give to each application in the partition. Furthermore, we have provided explicit formulas to express the number of processors to assign to each application.

Several polynomial-time heuristics have been built upon these results, and extensive simulation results demonstrated that the use of dominant partitions always leads to better results than more naive approaches, as soon as there is a small sequential fraction of work in application speedup profiles. The concept of sharing the cache only between a subset of applications seems highly relevant, since even an approach with a random selection of applications that share the cache leads to good results. Also, a clever partitioning of the cache pays off quite well, since our heuristics lead to a significant gain compared to an approach where no cache is given to applications. Overall, the heuristics appear to be very useful for general applications, even though their cache allocation strategy relies on simulating a perfectly parallel profile.

Future work will be devoted to extending the heuristics that account for the speedup profile for both processor and cache allocation. Also, we would like to gain access to, and conduct real experiments on, a cache-partitioned system with a high core count: this would allow us to further validate the accuracy of the model and to confirm the impact of our promising results.

A Additional simulation results

We consider three sets of data for simulations:

• NPB-6: Limited to the six applications defined in Table 2;

• NPB-SYNTH: We build synthetic applications from Table 2 with only varying randomly the work w i between 1E+8 and 1E+12 (used in the core of the paper); • RANDOM: We build synthetic applications from Table 2 with varying all values randomly.

The work w i is taken between 1E+8 and 1E+12, f i between 1E-01 and 9E-01, and m i 40MBSs between 1E-02 and 9E-04.

A.1 Impact of the number of applications

Figure 8 (normalized with AllProcCache and DominantMinRatio) shows the impact of the number of applications when the number of processors is fixed to 256. We observe similar results with RANDOM and NPB-SYNTH. Dominant partition heuristics still outperform other heuristics. As in Section 6, results are also normalized with DominantMinRatio, so that we can better observe the differences between co-scheduling heuristics. Results are quite similar to the results obtained with NPB-SYNTH.

RR n°8965

A.2 Impact of the number of processors Figure 9 (normalized with DominantMinRatio) shows the impact of the number of processors with 64 applications. Compared to Figure 5, the main difference is that Fair now obtains the worst performance, even 0cache is better. This difference in performance for Fair is due to a higher number of applications. As each application receive a fraction of cache and a fraction of processors, each of them obtains less resources when the number of applications increases. Figure 10 (normalized with AllProcCache and DominantMinRatio) shows the impact of the number of processors with NPB-6. The number of applications is fixed to 6. We observe with less applications that Fair obtains better results than 0cache when the number of processors is bigger than 50. Figure 11 (normalized with AllProcCache and DominantMinRatio) shows the impact of the number of processors with RANDOM. The number of applications is fixed to 16. We obtain similar results with RANDOM and NPB-SYNTH.

Figure 12 (normalized with AllProcCache and DominantMinRatio) shows the impact of the number of processors with RANDOM and 64 applications. As expected, we obtain similar A.3 Impact of the sequential fraction of work shows the impact of the cache latency l s with NPB-SYNTH and 16 applications on 256 processors. The sequential fraction of work is fixed to s i = 0.0001 for all i. We observe that the l s cost does not have an impact on relative performance. Figure 16 (normalized with AllProcCache) shows the impact of the cache latency l s with NPB-SYNTH and 64 applications on 256 processors. The sequential fraction of work is fixed to s i = 0.0001 for all i. As on the previous figure, we see that the l s cost does not have an impact of relative performance, even with 64 applications.

RR n°8965

A.5 Processor and cache repartition

Figure 17 shows the processor repartition and cache repartition when we vary the number of applications from 1 to 256 with 256 processors. The results with RANDOM are very similar to the results obtained with NPB-SYNTH. However, note that cache allocation with Fair is more heterogeneous when we have random application profiles. A.6 Impact of the cache miss rate

Figure 18 (normalized with DominantMinRatio) shows the impact of the cache miss rate with NPB-SYNTH and 16 applications. We vary the cache miss rate m i 40MBSs between 0 and 1. When the cache miss rate increases, the performance of RandomPart and 0cache increases. Indeed, when the rate of miss increases, using the cache is less important, so 0cache becomes competitive. But, we have to keep in mind that, with real applications, the cache miss rate rarely exceeds 20%.

A

  solution of CoSchedCache-Part I C , I C is a solution of CoSchedCache-Ext I C , I C , because we simply removed the constraints x i > d 1/α i in the latter problem. Hence the execution time of the optimal solution of CoSchedCache-Ext I C , I C is lower than that of CoSchedCache-Part I C , I C . Furthermore, given a solution of CoSchedCache-Ext I C , I C , one can easily see that its execution time in CoSchedCache will be lower (the objective function is lower since it involves a minimum for all applications in I C ).

Lemma 4 .

 4 Given a set of applications T 1 , . . . , T n and a partition I C , I C , the optimal solution to CoSchedCache-Ext I C , I C is

  I C , I C is not a valid partition: then CoSchedCache-Part I C , I C does not admit any solution.Let T e (resp. T p ) be the optimal execution time of CoSchedCache-Ext I C , I C (resp.CoSchedCache-Part I C , I C ). We know that T e ≤ T p . Let us further denote by X = {x 1 , . . . , x n } the optimal solution to CoSchedCache-Ext I C , I C . Let X = {x 1 , . . . , xn } be such that (i) xi0 = 0, (ii) xi1 = x i0 + x i1 , and (iii) xi = x i for all other i's.

5 IC ← IC \ {k}; 6 ifAlgorithm 2 :

 562 IC = ∅ then break; Dominant partition, starting from empty set 1 procedure DominantRev (I, choice) begin 2 IC ← I; IC ← ∅;

3 k 4 I C ← {k}; 5 while

 345 ← choice(IC ); ∀i ∈ I C

Inria

Figure 1 :

 1 Figure 1: Comparison of the six dominant partition heuristics.

Figure 2 :

 2 Figure 2: Impact of cache miss rate using a 1GB LLC.

Figure 3 :

 3 Figure 3: Impact of the number of applications.

Figure 4 :

 4 Figure 4: Impact of the average number of processors per applications.

Figure 5 :Figure 6 :

 56 Figure 5: Impact of the number of processors.

Figure 7 :

 7 Figure 7: Processor and cache repartition with 256 processors with NPB-SYNTH.

Figure 8 :

 8 Figure 8: Impact of the number of applications with RANDOM.

Figure 9 :

 9 Figure 9: Impact of the number of processors with NPB-SYNTH and 64 applications.

Figure 10 :

 10 Figure 10: Impact of the number of processors with NPB-6.

Inria

Figure 11 :Figure 12 :

 1112 Figure 11: Impact of the number of processors with RANDOM and 16 applications.

Figure 13 (Figure 13 :

 1313 Figure[START_REF] He | Developing graph-based co-scheduling algorithms on multicore computers[END_REF] (normalized with AllProcCache and DominantMinRatio) shows the impact of the sequential fraction of work with NPB-6 and 6 applications. As in Section 6, results are also normalized with DominantMinRatio, in order to show the differences between heuristics. We observe that the performance of Fair increases when the sequential fraction of work increases. Indeed, more the sequential fraction of work is important, more the cache allocation becomes crucial.

Figure 14 (Figure 14 :Figure 15 (

 141415 Figure14(normalized with AllProcCache and DominantMinRatio) shows the impact of the sequential fraction of work with RANDOM and 16 applications. We observe similar results to the previous one obtained with NPB-SYNTH.

Figure 15 :

 15 Figure 15: Impact of latency l s with NPB-SYNTH and s i = 0.0001 for all i.

Figure 16 :

 16 Figure 16: Impact of latency l s with NPB-SYNTH and 64 applications.

Figure 17 :

 17 Figure 17: Processor and cache repartition with 256 processors with RANDOM.

Figure 18 :

 18 Figure 18: Impact of cache miss rate using a 1GB LLC.

Table 2

 2

	shows the parameters

Table 1 :

 1 Description of the NPB benchmarks.

	App	w i	f i	m i 40MBSs
	CG 5.70E+10 5.35E-01 6.59E-04
	BT 2.10E+11 8.29E-01 7.31E-03
	LU 1.52E+11 7.50E-01 1.51E-03
	SP 1.38E+11 7.62E-01 1.51E-02
	MG 1.23E+10 5.40E-01 2.62E-02
	FT 1.65E+10 5.82E-01 1.78E-02

Table 2 :

 2 Experimental values from NPB benchmarks.

RR n°8965


Olivier L Georgeon
email: olivier.georgeon@liris.cnrs.fr

Alain Mille

Thierry Bellet

Benoit Mathern

Frank E Ritter

Supporting Activity Modeling from Activity Traces

Keywords: Sequence-mining, Timeline-analysis, Activity-trace, Knowledge-Based-System, Activitymodeling

We present a new method and tool for activity modeling through qualitative sequential data analysis. In particular, we address the question of constructing a symbolic abstract representation of an activity from an activity trace. We use knowledge engineering techniques to help the analyst build an ontology of the activity, i.e., a set of symbols and hierarchical semantics that supports the construction of activity models. The ontology construction is pragmatic, evolutionist and driven by the analyst in accordance with their modeling goals and their research questions. Our tool helps the analyst define transformation rules to process the raw trace into abstract traces based on the ontology.

The analyst visualizes the abstract traces and iteratively tests the ontology, the transformation rules, and the visualization format to confirm the models of activity. With this tool and this method, we found innovative ways to represent a car driving activity at different levels of abstraction from activity traces collected from an instrumented vehicle.

As examples, we report two new strategies of lane changing on motorways that we have found and modeled with this approach.

INTRODUCTION

We introduce here new principles based on knowledge engineering techniques for designing systems to help analysts create models of activity from activity traces. We illustrate these principles with a software tool that we have implemented, and with an example modeling analysis that we have performed using this tool.

By activity trace we mean a set of multiple streams of quantitative or symbolic data that record (at least partially) an activity performed by a subject. The analysts may be psychologists seeking to build theories of the subject's cognition, ergonomists seeking to design better user interfaces, analysts seeking to predict the subject's behavior in specific conditions, trainers seeking to improve training techniques, or even the subjects themselves seeking to improve their understanding of their actions. In each case, the created models of activity constitute micro-theories proposed by the analysts to describe, explain, and try to predict how the subject performs the activity.

The principles and the tool that we introduce here address three needs for helping analysts construct models of activity from activity traces. The first need is for helping the analyst learn previously unknown aspects or details of the subject's activity from the activity traces. The second need is for helping the analyst construct meaningful symbolic representations of interesting aspects of the activity. These representations, associated with the explanations proposed by the analyst, constitute the models of activity. The third need is for helping the analyst test and support the created models of activity with regard to the activity trace.

Activity traces have also been called protocols [START_REF] Ericsson | Protocol analysis: Verbal reports as data[END_REF] or simply sequential data [START_REF] Sanderson | Exploratory sequential data analysis: Foundations[END_REF]. We prefer the term activity trace because this term conveys the idea that the trace is intended to be interpreted by somebody (designated here as the analyst). We think of a trace as a footprint that helps who sees it understand what happened. Our activity traces yet differ from mere footprints in that they are not accidentally produced or unprocessed but they rather result from the analyst's choices and setup.

Many software tools have been implemented for activity trace analysis. A recent review [START_REF] Hilbert | Extracting Usability Information from User Interface Events[END_REF] notes forty of them. These tools cannot autonomously generate a comprehensive explanation of human behavior but they interactively support analysis. This analysis consists of identifying, categorising, labelling, and transforming pieces of data and information in the activity trace. We summarise this process by the notion of abstraction. The analysts use their expertise and knowledge to formulate a whole set of tiny hypotheses and choices concerning how to collect the data, how to filter it, how to cluster and label it, and how to display and to report it so that it responds to the analysis purpose.

Although most of the existing tools acknowledge the central role of the analysts and the importance of their knowledge and expertise in the analysing process, these tools still lack knowledge representation mechanisms to support the management of the analysts' knowledge. For instance, MacShapa (Sanderson et al., 1994), does help analysts label and cluster the behavioural data. It also acknowledges the usage of these labels as symbols to describe the activity. It, however, does not help the analyst formulate and manage the symbolic inferences she can make from these symbols.

We made the hypothesis that aspects of knowledge engineering can help design software systems that address the three needs identified above. We use ontology management facilities and rule engines to capture the hypotheses and choices made by the analyst. When interactively used by the analyst or a group of analysts, these facilities help formalize the way analysts find interesting symbolic patterns and infer models from them. Once this knowledge is formalized, the system uses it to automatically compute new representations of the activity from the activity traces. The system also helps analysts organize and store the different concepts and rules that summarize different studies and help capitalize on these studies.

To explain our principles and demonstrate the system and its design, we have organized this paper as follows: section 2 presents the principles of activity trace modelling, based on a pragmatic and evolutionist approach. Section 3 presents the prototype software tool that we have implemented from these principles, its technical features, its architecture, and its user interface. Section 4 presents an example study in which we have used this tool to create models of lane change on motorways from activity traces generated with an instrumented car. The method is then summarized in the conclusion.

MODELING ACTIVITY TRACES

The notion of activity traces is widely used in the human behavior literature, and we cannot attribute its origin to a specific author. Only more specific related notions can be identified, such as pattern languages, as reviewed by [START_REF] Dearden | Pattern Languages in HCI: A Critical Review[END_REF], or grammar representations [START_REF] Olson | Characterizing the sequential structure of interactive behaviors through statistical and grammatical techniques[END_REF]. Despite the wide usage of the term activity trace, we could not find a definition of it, which led us to propose the following definition:

An activity trace is a meaningful inscription, from the viewpoint of an analyst, of the flow of what has happened, from the viewpoint of a subject.

With this definition, we want to highlight that an activity trace always implies two viewpoints, situated in two different moments. It implies the subject's viewpoint, when he or she was performing the activity, and the analyst's viewpoint, when he or she is analyzing the activity trace. Indeed, an activity trace cannot be an inscription of all that happened (if that had any sense), because an activity only concerns what relates to the subject's perspective, goals, and intentions. Thus, inevitably, the analyst has to make assumptions about what is meaningful to the subject when the analyst sets up the tracing mechanism. In addition, the activity trace depends on what activity aspects interest the analyst and what makes sense to her according to her previous knowledge and to her analysis goals.

Because an activity trace depends on the analyst's knowledge and assumptions, it can only be modeled in an iterative way, each iteration producing new knowledge leading to new hypotheses for the next iteration. [START_REF] Ericsson | Protocol analysis: Verbal reports as data[END_REF] described this iterative nature of analyzing human behavior: "In designing our data-gathering schemes, we make minimal essential theoretical commitments, then try to use the data to test stronger theories" (p. 274). Moreover, none of the iterations can produce knowledge that could be proven to be true in an absolute sense, but only knowledge that is more efficient and useful with regard to the analyst's goals, and which is more convincing to the analyst's community than the knowledge from the previous iteration. More broadly, this conception of knowledge relates to a pragmatic epistemology [START_REF] James | Pragmatism[END_REF] and an evolutionist epistemology [START_REF] Popper | Objective knowledge[END_REF].

These pragmatic and evolutionist aspects are crucial when defining a methodology and a tool for activity trace modeling. By fully acknowledging these aspects, we have designed a tool that facilitates and accelerates the evolutionist modeling process. The tool helps formulating a series of micro-hypotheses of possibly-useful symbols, possiblyuseful transformation rules to transform the low-level data into higher-level data, and possibly-useful representations of the activity trace based on the micro-hypotheses. If the obtained representation does not help the analyst understand the activity better, then she rejects these micro-hypotheses; if it helps, then she keeps them.

The tool is designed to shorten this formulation / usage / validation-or-rejection loop. This process leads to the construction of a set of micro-hypotheses that are validated by the analyst. This set constitutes a formalization of the analyst's knowledge about how to understand the activity. The tool stores this knowledge, helps the analyst keep track of it, and helps the analysts' community discuss and question it.

The next section details how the tool reaches this goal by helping the analyst define sequences at the right level of abstraction, and simultaneously identify interesting subsequences, define them precisely, and query the whole trace in search for their occurrences.

Collecting a symbolic trace

A raw activity trace can be made of any kind of data describing a subject's activity flow and intended for an analyst's usage. In a broad sense, it can range from video or audio recording to computer logs. The only common point is that the data are temporally organized, meaning that each data piece is associated with a timestamp referring to a common time base. The first abstraction step consists of converting these raw traces into sequences of symbols. We refer to this step as the discretization of the raw trace into a symbolic trace. The symbols in the symbolic trace have to be meaningful to the analyst, and they are chosen on a pragmatic and evolutionist basis, in compliance with a pragmatic and evolutionist epistemology introduced above (introduction of section 2).

The discretization process can be manual, semi-automatic, or automatic. The definition of the symbols may evolve in parallel with the implementation of the discretization process. This is because the later interpretation of the symbols may differ from the meaning initially intended by the analyst when she specifies the discretization algorithm.

For example, in a study of car driving, we have used classical mathematical curve analysis method to generate symbols of interest from numerical values of the vehicle speed, the steering wheel angle, and the pedal positions. In this case, the symbols correspond to threshold crossing, local extremum, and inflexion points. Figure 1 illustrates this discretization process. In Figure 1, the curves represent the vehicle speed in km/h, and the brake pedal position in percentage of range. Symbols of interest are shown on these curves as circles (threshold crossings, inflexion points, local extremums). The symbols are merged into the symbolic trace that is represented at the bottom of Figure 1. The figure also shows a derivative value as an example property of interest associated with a symbol generated by a brake pedal threshold crossing. The analyst specifies the way to generate these symbols so that they correspond to meaningful events that describe the activity. In this example, the threshold crossing indicates the extent of the braking action and the derivative value indicates the abruptness of this action. Notably, while creating these symbols, the analyst claims the existence of the events that these symbols represent. So doing, the analyst defines an ontology of the activity.

Our experience has taught us that the system must keep a connection between the raw trace and the symbolic trace, and provide parallel displays of both of them. The analyst needs to tune many parameters of the discretization algorithms, like the threshold values or noise filters. The analyst validates the chosen symbols and algorithms by comparing the symbolic trace to the raw trace and ensuring that the symbolic trace represents what is happening. While she defines and validates these symbols, the analyst also supports her claim that the events represented by these symbols "exist". This support arises because the method to generate these symbols from the recorded data is formally specified and explained by the analyst. In this example, after we fully specified the discretization algorithm in accordance to our specific modeling goals, the discretization algorithm could then compute the symbols fully automatically.

Modeling the symbolic trace

At the symbolic level, analysts most often want to focus on relations between events. Indeed, events are not meaningful by themselves, but they become meaningful in the context where they relate to each other [START_REF] Sanderson | Exploratory sequential data analysis: Foundations[END_REF]. Examples of such relations include a "sequence following within a certain period of time", "co-occurrence within a certain period of time", and "causality with regard to a certain explanative theory". Building and understanding these relations between events is a part of the analyzing process. By definition, a set of elements connected through relations is a graph. Therefore, we model the symbolic traces with a graph structure.

More precisely, our trace graph structure has two parts: a sequence and an ontology.

The sequence is a part of the graph that is made of event instances and of relation instances between event instances. The ontology is a part of the graph that is made of event classes and of relations between event classes. Figure 2 illustrates this graph structure with a simplified example taken from the car driving study. Our tool displays the sequence in a similar form as shown in Figure 2; the exact form is shown in Figure 4. This display uses two axes: the time axis and the "abstraction" axis.

That is, the events' time-code attributes determine their "x" coordinates, and the analyst specifies their "y" coordinates when she configures these event's class in the ontology.

The analyst can use the "y" coordinate to express different meanings; our recommendation is to use it to express an idea of abstraction level related to a specific analysis. In this example, the lowest level (circles) represents the events obtained from the discretization process; the intermediary level represents events that describe the activity in usual driving terms: accelerate, glance, turn signal on/off (blinker); and the higher level represents events describing lane change behavior: indicator of intention to change lane, and index of lane change. This example expresses the analyst's assumption that the conjunction of an acceleration and a glance to the left rear mirror can generate an indicator of the driver's intention to change lane (L.C. Indicator).

In the ontology graph, the nodes represent event classes, and the edges represent the relation "subclass of" (dashed black arrows). The analyst defines the ontology during the modeling process. For example, the "Collected events" class includes all the event classes that come from the discretization process. The "Driving descriptors" class gathers the intermediary event classes that describe the activity in usual driving terms. The "Lane Change descriptors" class gathers the most abstract event classes describing lane changes.

The dotted gray arrows in the figure represent the relation "type of" going from event classes defined in the ontology to event instances in the sequence.

Again, like most ontologies, this ontology is made by the analyst on a pragmatic basis. It is likely that two analysts will create two different ontologies. While the software cannot demonstrate that one is better than the other, it does help the analysts formalize and discuss them. This discussion leads to the construction of a language for describing the activity that represents an agreement about the terms that can be used to describe the activity. In addition, the ontology also supports the analysts' agreement about how the trace should be visualized, because the visualization properties of the symbols are stored in the ontology. This trace formalism enables the analyst to conduct a hierarchical analysis of the activity. Event instances form a hierarchy where higher-level events are temporal patterns of lower-level events. The ontology also defines a hierarchy because some event classes are sub-classes of others. Notably, these two hierarchies are different because lower-level event instances do not necessarily belong to a sub-class of the class of higher-level event instances.

SYSTEM IMPLEMENTATION

We have implemented a prototype system based on an assemblage of open source knowledge-engineering tools: an ontology editor, an inference engine, visualization facilities, and documentation facilities. This system is named ABSTRACT (Analysis of Behavior and Situation for menTal Representation Assessment and Cognitive acTivity modeling). Figure 3 illustrates this assemblage.

The collection system

The collection system integrates tools to help the analyst prepare the symbolic trace.

We call these tools collection agents. Collection agents may be automatic when specified once by the analyst, or may require the analyst's intervention. Automatic collection agents can be tools for preprocessing sensor data or computer logs, as in the example of section 2.1. Semi-automatic collection agents can be tools for helping the analyst take notes, record interviews, or transcript video data. As noted, this discretization cannot be done blindly, but must be driven by the analyst. Hence, this level requires visualization facilities. We use Microsoft Excel with specific Visual Basic Application (VBA) macros as a visualization tool for the collection system. In this visualization, each event of the symbolic trace is displayed as a line in the spreadsheet. The lines are colored according to the event's type, and the event's properties are organized in different columns. We have implemented a specific video player and analogical data player that triggers VBA macros that automatically scrolls down the spreadsheet in synchronization. Some of these facilities are also available in commercial quantitative data analysis tools such as MacShapa (Sanderson et al., 1994) and NVivo. These facilities allow the analyst to check and validate or reject the symbolic trace, that is, refine the discretization algorithm and its diverse parameters until she gets a satisfying and meaningful symbolic trace including appropriate properties of interest.

The symbolic trace system

The symbolic trace system is the knowledge-engineering system itself. At this level, the traces are modeled as described in section 2.2. In addition, they are associated with a set of inference rules and a set of style-sheets. A style-sheet is a specification for displaying the trace on the screen. It specifies how semantic properties of the events that are defined in the ontology should be converted into visualization properties, such as shape and position. Style-sheets also implement particular time scales, and particular filters to display only the interesting aspect of the trace for a particular analysis. They correspond to different ways of looking at the trace according to different modeling goals.

The inference rules produce inferred symbols from patterns of previously existing symbols. The principle is to query the graph in the search for subgraphs that match certain patterns, and to attach new nodes and arcs to the matching subgraphs. These new nodes represent the inferred symbols and the new arcs represent the inference relations.

The usage of this inference mechanism is further described in Section 3.5.

Technically, the sequence part of the activity traces is encoded as Resource Description Framework (RDF) graphs. We choose RDF because it is the most widely used specification for graph encoding. We use XML as a serialization of RDF to store sequences, because XML makes RDF graphs easy to share with other applications. The ontology is encoded as RDF-Schema (RDFS), because RDFS is the simplest ontology language based on RDF. We use Protégé as a graphical ontology editor. That is, an installation of Protégé is embedded in our tool, and the analyst uses it to define the ontology of his traces. The graphical displays of our traces are encoded under the Scalable Vector Graphic (SVG) specification. Because Firefox natively supports SVG, we use it as a visualization tool, and we have implemented most of the tool as a web application in PHP. We use Extensible Stylesheet Language (XSL) as a transformation language for transforming RDF traces into their SVG graphical representation. We use SPARQL as a query language for graphs, as we will explain in section 3.5.

The documentation system

Analysts using our symbolic trace system expressed the need for a higher system layer providing a way to both index and attach documentation to episodes of interest. We implemented this by associating the symbolic trace system with a wiki. As we have made the choice of implementing ABSTRACT as a web application, analysts can reference each episode of interest by their URL, and easily paste this URL into a wiki page.

Moreover, some new wiki implementations, like Semantic Mediawiki1 , include semantic facilities. We are still investigating how these semantic facilities can be used to merge the ontology editor with the documentation system into a single semantic documentation system.

System usage

The user interface is accessible as a web-page in any browser that supports SVG, such as Firefox. This interface is illustrated in Figure 4. It has four tabs: the Open tab that allows the analyst to select a trace in a list; the Info tab that displays general information about the selected trace, such as its creation date and its version, and the management of stylesheets; the View tab that displays graphical visualizations of the trace; and the Edit tab that allows the analyst to write queries to transform the trace. The interface also provides a link to the ontology editor, Protégé. The View tab shown in Figure 4 provides the following functionalities (noted with numbered boxes):

1. Unique ID of the analysis, including aspects of the trace file and analyses done. 6. The analyst can show the symbols' properties by clicking on the symbols. 7. The system can synchronize with a video player. When this box is checked, the system gives the timecode control to the video player and automatically follows it.

The transformation mechanism

The analyst uses the Edit tab to write queries that infer higher-level symbols from patterns of lower-level symbols. For instance, Table 1 illustrates a query to infer the Lane Change indicator symbol shown in Figure 2, which indicates that a lane change is about to happen. In this example, the analyst wants to test the hypothesis that this indicator can be inferred from a conjunction of an accelerate event with an acceleration value greater or equal than 1 m/s 2 , followed by a glance event pointing to the left mirror (generated by an eye-tracker), both within 1 second of each other.

The graph elements, either from the sequence or the ontology, are handled as triples [node, edge, node]. A query consists of a selection clause (WHERE) and a CONSTRUCT clause. The selection clause specifies a pattern of triples that should match the graph, and the CONSTRUCT clause specifies a pattern of triples that should be added to the graph wherever a pattern matches the selection clause. In addition, matching patterns can be restricted by a FILTER clause. The syntax shown in Table 1 has been simplified for clarity2 . CONSTRUCT (?r1, infer , Indicator_Symbol) (?r2, infer , Indicator_Symbol) (Indicator_Symbol, type , Lane_Change_Indicator) WHERE (?r1, type , Accelerate) (?r2, type , Left_Mirror_Glance) (?r1, time-code , ?d1) (?r2, tine-code , ?d2) (?r2, Acceleration_Value , ?v1) FILTER ( ?v1 > 1) (sequence(?d1,?d2,1)) # in order, within 1 second In this query, ?r1, ?r2, ?d1, ?d2, and ?v1 represent variables. Each of them must match the same graph element each time they appear in the query. The sequence function tests that the time codes ?d1 and ?d2 occur in order and within the parameter of 1 second of each other.

In our implementation, the analyst has to know SPARQL to specify queries on the trace. To make it simpler, however, we have implemented a template mechanism that prepares skeletons of queries. We have also added some customized functions in our implementation of SPARQL, such as the sequence function presented above. These functions facilitate the specification of queries that compare time codes of events, and make it easier to specify temporal constraints. In so doing, we are implementing a semantics of time, for example, the semantics of the relation of co-occurrence and of sequential ordering. In the future, we plan to add options to let the analyst specify these queries from a graphical interface based on the visualization of the trace.

The Edit tab allows the analyst to visualize the resulting trace in a similar way as the View tab, but it also allows her to reject the trace if she is not satisfied by the result. This feature helps the analyst refine the query in search for the best symbols and inferences rules she can get to describe the activity from the actual data. Our system returns the number of times the pattern has matched in the trace. This number indicates the number of new symbols added. The system also provides an export function to a text file that can be imported into other tools like Microsoft Excel for further statistical computations.

Queries are saved as independent files and the tool helps the user reference them. The database of queries associated to the ontology constitutes a representation of the analyst's understanding about how to make sense of the activity trace.

EXAMPLE ACTIVITY MODEL

We report here an example activity modeling analysis taken from a car driving study [START_REF] Henning | The quality of behavioral and environmental indicators used to infer the intention to change lanes[END_REF]. Another example analysis-in a study of non-state political violence-is reported by [START_REF] Georgeon | Process Modeling for the Study of Non-State Political Violence[END_REF]. Figure 5 shows a 10 second section of a car-driving activity trace focusing on a lane change on a motorway. The legend is presented in Figure 6. In Figure 5, the "Button" is an index signal from the experimenter recorded during the experiment, the start thinking event comes from a verbal signal given by the driver in a video-based post-experiment interview, and the lane crossing event is the moment when the left front wheel crosses the lane, manually encoded from the video. The representation of the driving episode given in Figure 5 is then automatically generated with the inference rules defined by the analyst.

Using the trace querying facilities of ABSTRACT on this driving data set, we could identify two categories of lane changes that we explain by the performance of two strategies (Figure 7 and Figure 8). In these descriptions, the lower part is a representative trace episode from our database while the upper part is drawn by hand as an abstract description of the strategies. This upper part also shows the car trajectory in the lanes, respecting the scale ratio length/width: about 300 m of 4 m wide lanes. The strategy displayed in Figure 7 is characterized by beginning in a situation where the subject is impeded by a slow vehicle. In this case, the subject starts accelerating

[1] almost at the same time as he looks at his left mirror [2]. Then, if there is no vehicle coming from behind, he starts looking at the left lane [3], he switches his blinker on [4], and he performs the lane change [5]. In this situation, the acceleration associated with a glance to the left mirror appears as a good predictor of the lane change. It occurs more than one second before the subject switches the blinker on.

In the situation of Figure 8, no slow vehicle impedes the subject, and he performs the lane change "on the fly". In this case, we can find no behavioral sign of his intention to change lane before the blinker is switched on [1]. Nevertheless, the blinker appears to be a sufficient predictor in that case, because it is switched in anticipation of the lane change, several seconds before the maneuver: looking to the left lane In parallel of searching and identifying these categories of situations and strategies, we define symbols to represent them and inference rules to generate these symbols.

Finally, we have named the first strategy Lane_change_delayed and represented it with white triangles, and the second strategy Lane_change_anticipated represented with white squares. Figure 9 shows that these two types of event occur four times in a representative 20-minute motorway ride of a subject. Despite the extensive existing studies of car driving (e.g., [START_REF] Groeger | Understanding driving[END_REF] and on lane change maneuvers (e.g., [START_REF] Salvucci | The time course of a lane change: Driver control and eye-movement behavior[END_REF], we could find no representation of the driving activity that could compare to ours in terms of comprehensiveness of the data and capacity to support higher-level understanding. In the case of lane changes, this innovative description helped us discover different strategies that have not been reported in the literature before. So doing, this study shows how our principles and tool have addressed the needs enounced in the introduction: our prototype tool helped us generate comprehensive symbolic representations of the activity at an appropriate abstraction level to discover previously unknown knowledge about the activity. It also helped us explain, report, and back up our models with the collected traces.

RELATED WORK

In this section, we situate our work in relation to two research areas, the area of qualitative data analysis and the area of trace-based reasoning.

In the area of qualitative data analysis, many of software tools address the need for supporting the transcription of raw data into sequences of encoded events, for example, Dismal (Ritter and[START_REF] Ritter | Developing process models as summaries of HCI action sequences[END_REF][START_REF] Ritter | Dismal: A spreadsheet for sequential data analysis and HCI experimentation[END_REF], NVivo, INTERACT, InfoScope, MORAE, MarShapa (Sanderson et al., 1994), and MacVisSTA. As such, these tools relate to our collection system as described in Section 3.1. Among these tools, MacVisSTA [START_REF] Rose | MacVisSTA: a system for multimodal analysis[END_REF] particularly relates to this aspect of our work in that it supports merging multimodal data into a common timeline.

At the symbolic level-also called transcript level in some studies-tools like Theme [START_REF] Magnusson | Discovering hidden time patterns in behavior: T-Patterns and their detection[END_REF] support the automatic discovery of temporal patterns based on statistical properties. We consider our tool complementary to these tools because our tool helps find symbolic pattern based on the meaning they have to the analyst rather than on their statistical properties. In the car-driving example, our symbols of interest are not particularly frequent or infrequent nor do they obey pre-assumed statistical laws.

HyperRESEARCH appears to be the only qualitative data analysis tool that supports the validation of hypothetic theories through rule-based expert system techniques [START_REF] Hesse-Biber | Testing hypotheses on qualitative data: the use of HyperRESEARCH computer-assisted software[END_REF]. We find HyperRESEARCH's underlying principles for theory building very similar to ours. It, however, does not focus on temporal semantics and does not offer symbolic timeline visualization facilities to support activity modeling. Its rule engine also does not exploit elaborated hierarchical semantics defined in an ontology, as apposed to our solution based on SPARQL and RDF Schemas.

The other related research area, Trace-Based Reasoning (TBR) [START_REF] Cordier | Extending Case-Based Reasoning with Traces. Grand Challenges for reasoning from experiences[END_REF] comes from the domain of knowledge representation, and more precisely from Case-Based Reasoning (CBR) [START_REF] Aamodt | Case-based reasoning: Foundational issues, methodological variations, and system approaches[END_REF]. CBR consists of helping users solve new problems by adapting solutions that have helped them solve previous problems. TBR extends CBR to retrieve useful cases as episodes from the stream of an activity trace [START_REF] Mille | From case-based reasoning to traces-based reasoning[END_REF]. Our work relates to TBR because both address the question of modeling and representing a stream of activity for future usage. In particular, we pull lessons from the work of [START_REF] Settouti | A Trace-Based System for Technology-Enhanced Learning Systems Personalisation The[END_REF] that implemented a trace-based system to support the management and the transformation of traces. TBR has been used to implement companions that provide assistance to the user based upon previous usage (e.g., [START_REF] Cram | An approach to User-Centric Context-Aware Assistance based on Interaction Traces[END_REF], or to support reflexive learning by providing the users with a dynamic display of his passed activity [START_REF] Ollagnier-Beldame | Traces d'interactions et processus cognitifs en activité conjointe :Le cas d'une co-rédaction médiée par un artefact numérique[END_REF]. As opposed to these works, our work helps a user (the analyst) understand the activity of another user (the subject). So doing, our work brings principles of qualitative data analysis to TBR and brings TBR techniques to address problems of quantitative data analysis.

CONCLUSION

We have defined the principles of a methodology and a software tool to help an analyst create models of activity from activity traces in an iterative and interactive fashion. These principles relate to the notion of abductive reasoning in that they consist of helping analysts form, organize, and test micro-hypotheses to explain and represent the activity. Specifically, they help investigate what concepts and semantics describe the activity the best and represent these concepts in an ontology and apply this semantics through a rule engine. These principles are summarized in Figure 10. In Figure 10, the collected raw data is represented as curves along the activity axis.

The first analysis step consists of collecting this raw trace. The second step consists of producing a symbolic trace (symbols represented by circles) through the discretization of the raw trace. The third step consists of modeling the symbolic trace by inferring more abstract symbols (represented as squares and triangles) and organizing these symbols in an ontology (hierarchy of white rectangles). The fourth step consists of producing explained models of activity (round-angled rectangles) that are backed up by the abstract trace. During the modeling process, the analyst formalizes her understanding of the activity in the form of transformation rules, ontology, and documentations that are stored in the system, which allows capitalizing on the analyst's knowledge across studies.

To illustrate these principles, we have implemented a prototype software tool through an assemblage of open source knowledge engineering software modules. With this tool, we have modeled car-driving activity traces collected with an instrumented vehicle. This analysis allowed us to identify and describe two strategies of lane change on motorways.

This example shows that our knowledge engineering approach of activity modeling from activity traces offers answers to the needs for tools to help analysts understand better an observed activity, create models of this activity, report, and back up these models with the observational data.

The abstract activity traces that we have constructed constitute a model of the car driver in their own, in that the analysts can use our tool to query these traces to answer new questions they may have about the driving activity. Our future developments will consist of simulating the activity, for instance, in the field of car driving, generating realistic driving behavior in a driving simulator, based on our abstract activity traces.

Figure 1 .

 1 Figure 1. Discretization of analogical traces.

Figure 2 :

 2 Figure 2: Activity trace modeled in a knowledge engineering system.

Figure 3 :

 3 Figure 3: The architecture of the ABSTRACT activity analysis system.

Figure 4 :

 4 Figure 4: ABSTRACT User interface.

2.

  Selection of different visualization style sheets in drop-down lists. Different visualizations can be displayed simultaneously on the screen, and their time-code is synchronized. 3. Time code: this value corresponds to the cursor position in the visualization modules (vertical red line). The analyst can enter a time code and click Go to to focus on it. 4. Visualization sample with a time span of 10 seconds. The analyst can scroll the trace left and right with the mouse. This visualization example corresponds to the simplified description given in Figure 2. 5. Visualization sample of an entire trace (20 minutes), with only the high-level symbols displayed. These trace examples come from our car driving study and are further explained in section 4.

Figure 5 :

 5 Figure 5: Example of lane change on a motorway (screenshot with text labels added at the top).

Figure 6 :

 6 Figure 6: Legend of car driving symbolic trace.

Figure 7 :

 7 Figure 7: Lane change with acceleration (Lane_Change_Delayed).

  [2], looking to the left mirror [3], and starting steering [4].

Figure 8 :

 8 Figure 8: Lane change anticipated without acceleration (Lane_change_anticipated).

Figure 9 :

 9 Figure 9: Categorization of lane changes between Lyon and airport (20 minutes long).

Figure 9

 9 Figure 9 displays only the symbols that are useful to see the lane changes: the index

Figure 10 :

 10 Figure 10: Activity modeling from activity traces

  9th IEEE International Conference on Advanced Learning Technologies. Riga, 93-97. OLIVIER GEORGEON is a research associate in the LIRIS department at the Claude Bernard University (Lyon, France). He previously had a 12-year industrial experience as a software engineer, developer, and project manager in the domain of automatization of industrial processes. He received a PhD in cognitive psychology from the Université Lumière (Lyon, France) in 2008. His research interests are in learning through activity. His work both produces practical applications and addresses epistemological questions concerning learning from and about an activity. ALAIN MILLE has been a professor at the Claude Bernard University (Lyon, France) since 2000. He is a scientific director in the LIRIS department (UMR 5205 CNRS), and leads the research group Supporting Interactions and Learning through Experience. After a first career as a computer engineer and a project manager (Hospices Civils de Lyon), Alain Mille was asked to build a Computer Science Department in a college of engineering (CPE-Lyon). In this latter position, he created a research team on Case Based Reasoning. The main topics were decision helping and complex tasks assistance. Alain Mille is in several national and international conference program committees, and on the editorial board of Intellectica (a cognitive sciences journal). He is specifically interested in dynamic modeling of knowledge during computer-mediated activities. THIERRY BELLET has been a researcher at the Ergonomics and Cognitive Sciences Laboratory of IFSTTAR (Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux) since 1999. His main areas of research concern human activity analysis and cognitive processes modeling (e.g., Situational Awareness, decision making, cognitive schemas). His research has produced computational simulations of mental activities of the car driver (e.g., COSMODRIVE: COgnitive Simulation MOdel of the DRIVEr). BENOIT MATHERN is a PhD student in computer science. He first worked as a computer engineer at the Ergonomics and Cognitive Sciences Laboratory of IFSTTAR (Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux), then he started his PhD work in collaboration with the LIRIS department of the Claude Bernard University (Lyon, France). His main research interests focus on knowledge engineering, knowledge discovery and human-machine interaction. His work is applied to cognitive science in the field of transportation. FRANK RITTER is one of the founding faculty of the College of IST, an interdisciplinary academic unit at Penn State to study how people process information using technology. Frank Ritter's current research is in the development, application, and methodology of cognitive models, particularly as applied to interface design, predicting the effect of behavioral moderators, and understanding learning. He edits the Oxford Series on Cognitive Models and Architectures, is associate editor of Cognitive Systems Research, editorial board member of Human Factors, and the Journal of Educational Psychology, and technical program co-chair for the BRIMS 2009, 2010, and 2011 conferences and the associated special issues in Computational and Mathematical Organizational Theory.

Table 1 : Simplified inference query to infer a lane change.

 1

Semantic Mediawiki (http://semantic-mediawiki.org)

The complete SPARQL syntax can be found in the SPARQL documentation, http://www.w3.org/TR/rdf-sparql-query/

ACKNOWLEDGMENTS

We would like to acknowledge support for this project from the European Commission through the HumanIST Network of Excellence. Partial support for this report was provided by ONR (contracts N00014-06-1-0164 and N00014-08-1-0481). We also gratefully thank Jean-Marc Trémeaux for his participation in the software implementation, and Matthias Henning for his contribution to the car-driving experiment. We appreciate the comments on this report from Jonathan Morgan and Ryan Kaulakis.