Anne Benoit
email: anne.benoit@ens-lyon.fr

Swann Perarnau

Loïc Pottier
email: loic.pottier@ens-lyon.fr

Yves Robert
email: yves.robert@ens-lyon.fr

A performance model to execute workflows on high-bandwidth-memory architectures

Keywords: CCS CONCEPTS, General and reference → Performance, • Computer systems organization → Parallel architectures, • Software and its engineering → Memory management, Scheduling

This work presents a realistic performance model to execute scientific workflows on high-bandwidth-memory architectures such as the Intel Knights Landing. We provide a detailed analysis of the execution time on such platforms, taking into account transfers from both fast and slow memory and their overlap with computations. We discuss several scheduling and mapping strategies: not only tasks must be assigned to computing resources, but also one has to decide which fraction of input and output data will reside in fast memory and which will have to stay in slow memory. We use extensive simulations to assess the impact of the mapping strategies on performance. We also conduct experiments for a simple 1D Gauss-Seidel kernel, which assess the accuracy of the model and further demonstrate the importance of a tuned memory management. Our model and results lay the foundations for further studies and experiments on dual-memory systems.

INTRODUCTION

Recently, many TOP500 supercomputers [START_REF] Strohmaier | The TOP500 benchmark[END_REF], such as the Intel Knights Landing (KNL) [START_REF]Intel Xeon Phi Processor: Performance Monitoring Reference Manual[END_REF] or some custom many-core architectures [START_REF][END_REF][START_REF] Dongarra | Report on the Sunway TaihuLight system[END_REF], use many-core architectures to increase their processing capabilities. Among these many-core architectures, some systems add a new level in the memory hierarchy: a byte-addressable, highbandwidth, on-package memory. One of the first widely available systems to exhibit this kind of new memory is the KNL [START_REF] Asai | Clustering Modes in Knights Landing Processors: Developer's Guide[END_REF][START_REF]Intel Xeon Phi Processor: Performance Monitoring Reference Manual[END_REF][START_REF] Vladimirov | MCDRAM as High-Bandwith Memory (HBM) in Knights Landing Processors: Developer's Guide[END_REF]. Its on-package memory (called multi-channel dynamic random access memory, or MCDRAM) of 16 GB has a bandwidth five times larger than the classic double data rate (DDR) memory. At boot, a user can decide to use this on-package memory in three modes: Cache mode: In cache mode, MCDRAM is used by the hardware as a large last-level direct-mapped cache. In this configuration, cache misses are expensive; indeed, all data will follow the path DDR → MCDRAM → L2 caches. Flat mode: In flat mode, the MCDRAM is manually managed by programmers. It is a new fast addressable space exposed as a NUMA node to the operating system. Hybrid mode: This mode mixes both previous modes. A configurable ratio of the memory is used in cache mode; the other part is configured in flat mode.

While Intel promotes the cache mode, the flat mode may be more interesting in some cases. The goal of this work is to demonstrate, theoretically and experimentally, that the flat mode can obtain better performance with particular workloads (for instance, bandwidthbound applications). Unlike GPU and classic out-of-core models, with high-bandwidth-memory systems there is no need to transfer the whole data needed for computations into the on-package memory before execution and then to transfer back the data to the DDR after the computation. An application can start its computations using data residing in both memories at the same time.

We built a detailed performance model accounting for the new dual-memory system and the associated constraints. We focus our study on scientific workflows and provide a detailed analysis of the execution time on such platforms, taking into account transfers from both fast and slow memory and their overlap with computations. The problem can be stated as follows: given (i) an application represented as a directed acyclic graph (DAG), and (ii) a manycore platform with P identical processors sharing two memories, a large slow memory and a small fast memory, how should this DAG be scheduled (which processor should execute which task and in which order) and which memory mapping should be used (which data should reside in which memory) in order to minimize the total execution time, or makespan.

Our major contributions are the following:

• We build a detailed performance model to analyze the execution of workflows on high-bandwidth systems, and we design several scheduling and mapping strategies. • We conduct extensive simulations to assess the impact of these strategies on performance. • We conduct experiments for a simple 1D Gauss-Seidel kernel, which establish the accuracy of the model and further demonstrate the importance of a tuned memory management. The rest of the paper is organized as follows. Section 2 provides an overview of related work. Section 3 formally defines the performance model with all its parameters, as well as the target architecture. Section 4 discusses the complexity of a particular problem instance, namely, linear workflows. Mapping and scheduling heuristics are introduced in Section 5 and evaluated through simulations in Section 6. The experiments with the 1D Gauss-Seidel kernel are reported in Section 7. Section 8 summarizes our conclusions and provides ideas for future work.

Deep memory architectures have become widely available only in the last couple of years, and studies focusing on them are rare. Furthermore, since vendors recommend to make use of them as another level of hardware-managed cache, few works make the case for explicit management of these memories. Among existing works, two major trends can be identified: studies arguing for data placement or for data migration.

Data placement [START_REF] Unat | Programming Abstractions for Data Locality[END_REF] addresses the issue of distributing data among all available memories only once, usually at allocation time. Several efforts in this direction aim at simplifying the APIs available for placement, similarly to work on general NUMA architectures: memkind [START_REF]Memkind: A User Extensible Heap Manager[END_REF], the Simplified Interface for Complex Memory [START_REF]Simplified Interface to Complex Memory[END_REF] and Hexe [START_REF] Oden | Hexe: A Toolkit for Heterogeneous Memory Management[END_REF]. These libraries provide applications with intentbased allocation policies, letting users specify bandwidth-bound data or latency-sensitive data, for example. Other works [START_REF] Servat | Automating the Application Data Placement in Hybrid Memory Systems[END_REF][START_REF] Voskuilen | Analyzing Allocation Behavior for Multi-Level Memory[END_REF] focus instead on tracing the application behavior to optimize data placement on later runs.

Data migration addresses the issue of moving data dynamically across memories during the execution of the application. Preliminary work [START_REF] Perarnau | Exploring Data Migration for Future Deep-Memory Many-Core Systems[END_REF] on this approach showcased that performance of a simple stencil benchmark can be improved by migration, using a scheme similar to out-of-core algorithms, when the computedensity of the application kernel is high enough to provide compute/migration overlapping. Closer to the focus of this paper, another study [START_REF] Chandrasekar | A Memory Heterogeneity-Aware Runtime System for Bandwidth-Sensitive HPC Applications[END_REF] discussed a runtime method to schedule tasks with data dependencies on a deep memory platform. Unfortunately, the scheduling algorithm is limited to scheduling a task only after all its input data has been moved to faster memory. Also, no theoretical analysis of this scheduling heuristic was performed.

We also mention the more general field of heterogeneous computing, usually focusing on CPU-GPU architectures. Until recently, these architectures were limited to separated memories: to schedule a task on a GPU, one had to move all of its data to GPU memory. Task scheduling for such architectures is a more popular research area [START_REF] Ait Aba | Approximation Algorithm for Scheduling a Chain of Tasks on Heterogeneous Systems[END_REF][START_REF] Augonnet | Data-Aware Task Scheduling on Multi-Accelerator Based Platforms[END_REF][START_REF] Augonnet | StarPU: a Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures[END_REF][START_REF] Gautier | XKaapi: A Runtime System for Data-Flow Task Programming on Heterogeneous Architectures[END_REF]. Unfortunately, the scheduling heuristics for this framework are poorly applicable to our case because we can schedule tasks without moving data first. More recent GPU architectures support accessing main memory (DDR) from GPU code, for example by using unified memory since CUDA 6 [START_REF] Landaverde | An Investigation of Unified Memory Access Performance in CUDA[END_REF][START_REF]CUDA: Unified Memory Programming[END_REF]. To the best of our knowledge, however no comprehensive study has addressed memory movement and task scheduling for these new GPUs from a performance-model standpoint.

MODEL

This section describes the performance model: architecture in Section 3.1, the target application in Section 3.2, scheduling constraints in Section 3.3, execution time in Section 3.4, and optimization objective in Section 3.5.

Architecture

We consider a deep-memory many-core architecture with two main memories: a large slow-bandwidth memory, M s , and a small highbandwidth memory, M f . This two-unit memory system models that of the Xeon Phi (KNL) architecture [START_REF]Intel Xeon Phi Processor: Performance Monitoring Reference Manual[END_REF][START_REF] Vladimirov | MCDRAM as High-Bandwith Memory (HBM) in Knights Landing Processors: Developer's Guide[END_REF]. Let S s denote the size and β s the bandwidth of the memory M s . We express memory size in terms of the number of data blocks that can be stored. A data block is any unit convenient for describing the application (e.g. bytes or words). Accordingly, bandwidths are expressed in data blocks per second. Similarly, let S f denote the size and β f the bandwidth of the memory M f .

Both memories have access to the same P identical processing units, called processors in the following. Each processor computes at speed s. Figure 1 illustrates this architecture, where the fast MC-DRAM corresponds to M f and the slow DDR memory corresponds to M s .

Application

The target application is a scientific workflow represented by a directed acyclic graph G = (V , E). Nodes in the graph are computation tasks, and edges are dependencies among these computation tasks. Let V = {v 1 , . . . , v n } be the set of tasks. Let E ⊆ V 2 be the set of edges. If (v i , v j ) ∈ E, task v i must complete its execution before v j can start. Each task v i ∈ V is weighted with the number of computing operations needed, w i . Each edge (v i , v j ) ∈ E is weighted with the number of data blocks shared between tasks, v i and v j . Let e i, j be the number of shared (i.e., read or write) data blocks between v i and v j . We consider disjoint blocks; hence each e i, j is specific to the task pair (v i , v j ). For each task, input edges represent data blocks that are read and output edges data blocks that are written. Hence, in the example of Figure 2, task v 2 reads e 1,2 blocks and writes e 2,3 blocks. We define succ

(v i ) = {v k | (v i , v k ) ∈ E} (resp. pred(v i ) = {v k | (v k , v i ) ∈ E})
to be the successors (resp. predecessors) of task v i ∈ V . Note that if G has multiple entry nodes (i.e., nodes without any predecessor), then we add a dummy node v 0 to G. We set w 0 = 0, and v 0 has no predecessor. Finally, v 0 is connected with edges representing the initial input to each entry node of G.

Scheduling constraints

Data blocks. At schedule time, we have to choose from which memory data blocks will be read and written. We define a variable for each edge, e f i, j , which represents the number of data blocks into the fast memory M f . Symmetrically, let e s i, j be for each edge the number of data blocks into the slow memory, M s , defined as e s i, j = e i, je f i, j .

v 1 w 1 v 2 w 2 v 3 w 3 e 1,2 e 2,3
We define in

f i = v j ∈pred(v i ) e
f j,i as the total number of blocks read from M f by task v i . Similarly, we define out

f i = v j ∈succ(v i ) e f i, j
as the total number of blocks written to M f by task v i . For the slow memory, M s , we similarly define in s i and out s i .

Events. To compute the execution time and to express scheduling constraints, we define two events, {σ 1 (i), σ 2 (i)}, for each task v i . These events are time steps that define the starting time and the ending time for each task. With n tasks, there are at most 2n such time steps (this is an upper bound since some events may coincide). A chunk is a period of time between two consecutive events. We denote by chunk k the period of time between events t k and t k +1 , with 1 ≤ k ≤ 2n -1. Let t σ 1 (i ) be the beginning and t σ 2 (i ) be the end of task v i (see Figure 3). Let S and then update this value depending on the events of starting or ending a task. For task v i , we consider two events (see Figure 3):

• At time step t σ 1 (i ) : Before v i begins its execution, the schedule decides which output blocks will be written in fast memory, hence what is the value of e f i, j , for each successor v j ∈ succ(v i ). It must ensure that S

(σ 1 (i )) f + out f i ≤ S f . Thus at time step t σ 1 (i ) , out f i blocks are reserved in M f , hence S (σ 1 (i )) f ← S (σ 1 (i )) f + out f i .
• At time step t σ 2 (i ) : After computation, we want to evict useless blocks. Since we have disjoint blocks, all read blocks in fast memory are useless after computation; hence S

(σ 2 (i )) f ← S (σ 2 (i )) f -in f i .
We do not need to transfer these blocks to M s thanks to the disjoint blocks assumption. To ensure that a task v i starts only if all its predecessors have finished, we enforce the following constraint:

∀(v i , v j ) ∈ E, t σ 2 (i ) ≤ t σ 1 (j ) . (1)
Also, we have to ensure that, at any time, the number of blocks allocated in the fast memory, M f , does not exceed S f :

∀1 ≤ k ≤ 2n -1, S (k ) f ≤ S f . (2)
However, we must ensure that no more than P tasks are executing in parallel (no more than one task per processor at any time).

Accordingly, we bound the number of executing tasks at each time step t:

v i | t σ 1 (i ) ≤ t < t σ 2 (i ) ≤ P. ( 3
)
We have at most 2n events in total, and we have to define a processing order on these events in order to allocate and free memory. We sort the events by nondecreasing date. If two different types of events, σ 1 (i) and σ 2 (j), happen simultaneously (t σ 1 (i ) = t σ 2 (j ) ), then we process σ 2 (j) first.

Execution time

We aim at deriving a realistic model where communications overlap with computations, which is the case in most state-of-the-art multithreaded environments. We envision a scenario where communications from both memories are uniformly distributed across the whole execution time of each task, meaning that an amount of communication volume from either memory proportional to the execution progress will take place during each chunk, that is, in between two consecutive events, as explained below.

We aim at providing a formula for w

(k )
i , the number of operations executed by task v i during chunk k, that is, between time steps t k and t k +1 . If the task v i does not compute at chunk k, then w

(k ) i = 0.
Otherwise, we have to express three quantities: (i) computations; (ii) communications from and to fast memory, M f ; and (iii) communications from and to slow memory, M s . We assume that the available bandwidths β f and β s are equally partitioned among all tasks currently being executed by the system. Let β

(k ) f (resp. β (k )
s ) be the available bandwidth during chunk k for memory M f (resp. M s ) for each task executing during that chunk. Let

N (k ) f (resp. N (k )
s ) be the set of tasks that perform operations using the fast (resp. slow) memory bandwidth. Hence, we have β

(k ) f = β f |N (k ) f | and β (k ) s = β s |N (k ) s | .
Computations are expressed as the number of operations divided by the speed of the resource used, hence

w (k ) i s for v i . The task v i needs to read or write in f i + out f i blocks in total at speed β (k )
f . We want to express the communication time between t k and t k +1 also in terms of w (k )

i . The number of data accesses in fast memory per computing operations for task v i can be expressed as

in f i +out f i w i .
The communication time is obtained by multiplying this ratio by the number of operations done during this chunk, w (k ) i , and by dividing it by the available bandwidth.

Since each task can perform communications and compute in parallel, we are limited by one bottleneck out of three; computations, or communications from M f or communications from M s . Hence,

for each chunk k with 1 ≤ k ≤ 2n -1, we have w (k ) i s ≤ t k +1 -t k , (4) w (k )
i (in

f i + out f i ) w i β (k ) f ≤ t k +1 -t k , (5)
w (k ) i (in s i + out s i ) w i β (k ) s ≤ t k +1 -t k . (6)
Note that a more conservative (and less realistic model) would assume no overlap and replace Equations ( 4) to ( 6) by

w (k ) i s + w (k ) i (in f i + out f i ) w i β (k ) f + w (k ) i (in s i + out s i ) w i β (k ) s ≤ t k +1 -t k . (7)
An important assumption is made here: we assume that the number of flops computed with one data block remains constant. In other words, the computation time

w (k ) i
s does not depend on the data scheduling (into either fast or slow memory).

From the previous equation, we can derive the expression for w

(k ) i : w (k ) i = (t k +1 -t k ) min s, β (k ) f w i in f i + out f i , β (k )
s w i in s i + out s i . (8)
Finally, we need to compute the time step t k +1 for the beginning of the next chunk. We express the time E (k ) i for a task i to finish its execution if there are no events after t k . We call this time the estimated execution time, since we do not know whether there will be an event that could modify available bandwidths and change progress rate for the execution of the task:

E (k ) i = t k + w i - k -1 k ′ =σ 1 (i ) w (k ′ ) i min s, β (k ) f w i in f i +out f i , β (k ) s w i in s i +out s i . (9)
Hence, the time step of the next event t k +1 is

t k +1 = min v i ∈V E (k ) i , (10)
Note that the task that achieves the minimum is not impacted by any event and completes its execution at time step t k +1 . We point out that despite the simplifications we made, we still have a complicated model to compute execution time. The reason is that the partitioning of input and output data of each task into fast and slow memory has an impact on the execution of many other tasks, since it imposes constraints on available bandwidth for both memories and remaining space in the fast memory.

There remains to ensure that all tasks perform all their operations and communications. We have the following constraint:

2n-1 k=1 w (k ) i = w i . (11)
Indeed, Equation [START_REF]Memkind: A User Extensible Heap Manager[END_REF] guarantees that the communications corresponding to an amount of work w (k ) i can effectively be done during chunk k, since we assume that communications from both memories are uniformly distributed during execution time. Therefore, Equation ( 11) is enough to validate the correctness of computations.

Let in

f (k ) i = w (k ) i
w i in f i be the number of read operations performed at chunk k by v i from M f . We have the following constraint on communications:

2n-1 k =1 in f (k ) i = in f i . (12)
Thanks to Equation ( 11), we ensure that the previous constraint is respected. We have the same type of constraints on in s i , out f i , and out s i . To compute the total execution time of a schedule, we have

T = max v i ∈V t σ 2 (i ) . ( 13
)

Objective

Given a directed acyclic graph G = (V , E), our goal is to find a task memory mapping between the small high-bandwidth memory and the large slow-bandwidth memory, in order to minimize the time to execute the critical path of G. More formally, we have the following:

Definition 1 (MemDag). Given an acyclic graph G = (V , E) and a platform with P identical processors sharing a two-level memory hierarchy, a large slow-bandwidth memory M s and a small highbandwidth memory M f , find a memory mapping X = {e f i, j } (v i ,v j ) ∈E and a schedule {t σ 1 (i ) , t σ 2 (i ) } v i ∈V satisfying all the above constraints and minimizing

max v i ∈V t σ 2 (i ) .

COMPLEXITY FOR LINEAR CHAINS

MemDag is NP-complete in the strong sense. To show this, we remove the memory size constraints and assume an unlimited fast memory with infinite bandwidth. We now have the classical scheduling problem with n = 3P independent tasks to be mapped on P processors, which is equivalent to the 3-partition problem [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]. Since the problem is NP-hard for independent tasks, deriving complexity results for special classes of dependence graphs seems out of reach.

Still, we have partial results for workflows whose graph is a linear chain, as detailed hereafter. Consider a linear chain of tasks

v 1 e 1, 2 → v 2 → • • • → v i e i,i +1 → v i+1 → • • • → v n ,
and let e 0,1 denote the input size and e n,n+1 the output size. Because of the dependences, each task executes in sequence. Partitioning e i,i+1 = e s i,i+1 + e f i,i+1 into slow and fast memory, we aim at minimizing the makespan as follows:

Minimize n i=1 m i Subject to                            e i,i+1 = e s i,i+1 + e f i,i+1 for 0 ≤ i ≤ n w i s ≤ m i for 1 ≤ i ≤ n e s i -1,i +e s i,i +1 β s ≤ m i for 1 ≤ i ≤ n e f i -1,i +e f i,i +1 β f ≤ m i for 1 ≤ i ≤ n e f i-1,i + e f i,i+1 ≤ S f for 1 ≤ i ≤ n (14)
Equation ( 14) captures all the constraints for the problem. There are 3n + 2 unknowns, the n values m i and the 2n + 2 values e s i,i+1 and e f i,i+1 . Of course, we can replace one of the latter values, say e s i,i+1 , by e i,i+1e f i,i+1 , so there are only 2n + 1 unknowns, but the linear program reads better in the above form.

To solve Equation ( 14), we look for integer values, so we have an integer linear program (ILP). We attempted to design several greedy algorithms to solve Equation ( 14) but failed to come up with a polynomial-time algorithm for an exact solution. We also point out that it is not difficult to derive a pseudo-polynomial dynamic programming algorithm to solve Equation ( 14), using the size S f of the fast memory as a parameter of the algorithm. Furthermore, on the practical side, we can solve Equation ( 14) as a linear program with rational unknowns and round up the solution to derive a feasible schedule.

Still, the complexity of the problem for linear workflows remains open. At the least, this negative outcome for a simple problem instance, fully evidences the complexity of MemDag.

HEURISTICS

Since MemDag is NP-complete, we derive polynomial-time heuristics to tackle this challenging problem. We have two types of heuristics: (i) processor allocation heuristics that compute a schedule S, defined as a mapping and ordering on the tasks onto the processors and (ii) memory mapping heuristics that compute a memory mapping X = {e f i, j | (v i , v j ) ∈ E}. Recall that when a task finishes its execution, the memory used is released. Therefore, memory mapping is strongly affected by the scheduling decisions. We aim to design heuristics that consider both aspects and minimize the global makespan T .

In Section 5.1, we introduce the general algorithm that computes the makespan according to scheduling and memory-mapping policies. Then we present scheduling policies in Section 5.2 and memory-mapping policies in Section 5.3.

Makespan heuristics

We outline the algorithm to compute the makespan of a task graph according to (i) a processor-scheduling policy called φ and (ii) a memory mapping policy called τ . Let L (k ) be the list of ready tasks at time step k. A task is called ready when all its predecessors have completed their execution. The scheduling policy, φ, sorts the list of tasks L (k ) according to its priority criterion, so that the task in first position in L (k ) will be scheduled first. The memory-mapping policy, τ , returns the number of blocks in fast memory for each successor of a task, according to the size of the fast memory available for this chunk, namely, S f -S (k ) f . In other words, τ (v i ) returns all e f i, j with v j ∈ succ(v i ). Algorithm 1 computes the makespan of a task graph G, given a number of processors P, a fast memory of size S f , and two policies: φ for processors and τ for the memory. The scheduling algorithm is based on a modified version of the list scheduling algorithm [START_REF] De | Synthesis and Optimization of Digital Circuits[END_REF]. The idea of list scheduling is to build, at each time step k, an ordered list L (k ) of tasks that are ready to be executed. Then, the algorithm greedily chooses the first task in the list if one resource is available at this time step, and so on. The key of list scheduling algorithms lies in the sorting function used to keep the ordered list L (k ) . We detail several variants in Section 5.2. Since we have homogeneous computing resources, we do not need to define a function that sorts computing resources, in order to use the most appropriate one. We simply choose any computing resource available at time step k.

We now detail the core of the algorithm. At Line 7, we iterate until the list of tasks to execute is empty, in other words until the workflow G has been completely executed. At Line 12, we sort the list of ready tasks at time-step k according to the scheduling policy. At Line 9, we release processors for each task ending at chunk k. At Line 13, we try to schedule all available tasks at time step k, and at Line 16 we choose the memory allocation for each task scheduled. At Line 20, we compute the set of tasks finishing at k + 1; recall that E (k ) i computes the estimated finishing time of task v i at chunk k (see Equation 10). At Line 23, we compute the list of tasks ready to execute at time step k + 1.

Scheduling policies φ

The function φ(L (k ) ) aims at sorting the list L (k ) that contains the ready tasks at step k, in order to decide which tasks should be scheduled first. We define several scheduling policies to schedule tasks onto processors.

Critical path. The first heuristic, called critical path (CP), is derived from the well-known algorithm heterogeneous earliest finish time (HEFT) [START_REF] Topcuoglu | Performance-effective and lowcomplexity task scheduling for heterogeneous computing[END_REF]. The HEFT algorithm chooses the task with the highest critical path at each step and schedules this task to a processor that minimizes its earliest finish time. In our model, we consider homogeneous processors; hence we select the first available processor. We define the critical path CP i of task v i as the maximum time to execute, without fast memory, any chain of tasks between v i and an exit task. Formally,

CP i = max w i s , in i + out i β s + max j ∈succ(v i ) CP j . (15)
CP sorts the list of ready tasks according to their critical paths (in nonincreasing order of CP i ).

Gain graph.

With this heuristic, we avoid short-term decisions that could lead to bad scheduling choices, we take into consideration the potential gain of using fast memory. To estimate the potential gain of a node v i , we estimate the potential gain of the subgraph rooted at v i , called G i . (k ) ) ; // Sort tasks according scheduling policy 13 while p > 0 and L (k ) ∅ do 14

f ← 0 ; 4 L (k ) ← {v i s.t pred(v i ) = 0} ; // Roots of G 5 p ← P ; // Available processors 6 foreach v i ∈ V do σ 1 (i ) ← +∞ ; σ 2 (i ) ← +∞ ; 7 while L (k ) ∅ do 8 S (k ) f ← S (k -1) f ; 9 foreach v i ∈ V s.t. σ 2 (i ) = k do 10 S (k ) f ← S (k ) f -in f i ; // Release input blocks 11 p ← p + 1 ; 12 L (k ) = φ (L
v i ← head(L (k ) ) ; 15 L (k ) ← tail(L (k ) ) ; 16 {e f i, j | j ∈ succ(v i ) } ← τ (v i ) ; // Allocate each e f i, j 17 S (k ) f ← S (k ) f + out f i ; // Allocate output blocks 18 p ← p -1 ; 19 σ 1 (i ) ← k ; 20 i ← argmin σ 1 (j )≤k <σ 2 (j ) E (k ) j ; // Finishing task 21 σ 2 (i ) ← k + 1; 22 t σ 2 (i ) ← E (k ) i ; 23 L (k +1) ← {v i | ∀v j ∈ pred(v i ) s.t. σ 2 (j ) ≤ k + 1 < σ 1 (i ) } ;
// Ready tasks for next time-step

24 k ← k + 1 ; 25 return max v i ∈V t σ 2 (i ) ;
Definition 2 (Rooted subgraph). Let G x = (V x , E x ) be the subgraph rooted at v x , with v x ∈ V . The set of vertices V x ⊆ V contains all nodes in V reachable from v x . An edge is in E x ⊆ E if and only if both of its endpoints are in V x . Formally,

(v i , v j ) ∈ E x ⇔ v i ∈ V x and v j ∈ V x .
The gain of using fast memory for a graph is defined as

дain(G i ) = Bl f (G i ) Bl s (G i ) , (16)
where Bl f (G i ) is the makespan of G i with an infinite number of processors and with an infinite fast memory and Bl s (G i ) is the makespan using only slow memory. If дain(G i ) = 1, then G i is compute bound, and using fast memory might not improve efficiently its execution time. The gain graph (GG) heuristic sorts the list of tasks in nondecreasing order of potential gains using fast memory дain(G i ).

Memory mapping policies τ

In addition to scheduling policies with function φ, we need to compute a memory mapping for tasks ready to be scheduled. Recall that the function τ (v i ) aims at computing the amount of data in fast memory, e f i, j , for each successor of v i . We propose three heuristics returning a memory mapping.

MemCP and MemGG. The idea behind these two heuristics is to greedily give the maximum amount of memory to each successor of the task v i that is going to be scheduled. The difference lies in the criterion used to order the successors. The MemCP heuristic uses the critical path to choose which successors to handle first (see Algorithm 2), while MemGG sorts the list of successors in increasing order of their potential gains using fast memory.

Algorithm 2: Heuristic MemCP

1 procedure MemCP (v i ) begin 2 Let U be the set of v i 's successors ordered by C P i ; 3 X ← ∅ ; 4 foreach j ∈ U do 5 e f i, j ← min S f -S (k ) f , e i, j ; 6 X ← X ∪ {e f i, j } ; 7 S (k ) f ← S (k ) f + e f i, j ; 8 return X ;
MemFair. The previous greedy heuristics MemCP and MemGG give as much as possible to the first tasks according to their criterion. The idea of MemFair is to greedily give data blocks in fast memory to the tasks, according to their amount of computations, but accounting for other successors. Recall that S f -S (k ) f is the number of blocks available at chunk k. MemFair spreads blocks from fast memory across the successors of the scheduled tasks: each successor has at most a number of blocks equal to S f -S (k ) f divided by the number of successors. Algorithm 3 details this heuristic.

      S f -S (k ) f | succ(v i ) |       , e i, j ; 6 X ← X ∪ {e f i, j } ; 7 S (k ) f ← S (k ) f + e f i, j ; 8 return X ;
By combining two heuristics for processor scheduling and three heuristics for memory mapping, we obtain a total of six heuristics.

Baseline heuristics

For comparison and evaluation purposes, we define three different baseline heuristics for memory mapping. Because of lack of space, we combine them only with CP as a processor-scheduling heuristic. Results when combining with GG are similar and available in the extended version [START_REF] Benoit | A performance model to execute workflows on high-bandwidth memory architectures[END_REF].

CP +NoFast and CP +InfFast. NoFast considers that no fast memory is available, while InfFast uses a fast memory of infinite size (but still with a finite bandwidth, β f ).

CP +CcMode. This baseline heuristic is more complicated. Recall that our target architecture is the Xeon Phi KNL, which proposes two principal modes to manage the fast memory: the cache mode and the flat mode [START_REF] Vladimirov | MCDRAM as High-Bandwith Memory (HBM) in Knights Landing Processors: Developer's Guide[END_REF]. In the cache mode, the fast memory is managed by the system as a large cache. Our memory-mapping heuristic CcMode aims at imitating the KNL cache mode behavior. In CcMode, we divide the fast memory into P slices, where P is the total number of processors and each processor has access only to its own slice into the fast memory. When a node v i is scheduled onto a processor, all its output blocks are allocated, if possible, to fast memory. If the slice into fast memory is too small to contain the output blocks of each successor, we consider the successors in nondecreasing index order (v j-1 is handled before v j ). CcMode aims at providing a more realistic comparison baseline than does NoFast.

SIMULATIONS

To assess the efficiency of the heuristics defined in Section 5, we have conducted extensive simulations. Simulation settings are discussed in Section 6.1, and results are presented in Section 6.2. The simulator is publicly available at https://perso.ens-lyon.fr/loic. pottier/archives/simu-deepmemory.zip so that interested readers can instantiate their preferred scenarios and repeat the same simulations for reproducibility purpose.

Simulation settings

To evaluate the efficiency of the proposed heuristics, we conduct simulations using parameters corresponding to those of the Xeon Phi KNL architecture. Unless stated otherwise, the bandwidth of the slow memory, β s , is set to 90 GB/s, while the fast memory is considered to be five times faster, at 450 GB/s [START_REF] Vladimirov | MCDRAM as High-Bandwith Memory (HBM) in Knights Landing Processors: Developer's Guide[END_REF]. The processor speed, s, is set to 1.4 GHz (indeed the processor speed of KNL cores ranges from 1.3 to 1.5 with the Turbo mode activated [START_REF]Intel Xeon Phi Processor: Performance Monitoring Reference Manual[END_REF]). The size of the fast memory is set to 16 GB unless stated otherwise, and the slow memory is considered infinitely large.

To instantiate the simulations, we use random directed acyclic graphs from the Standard Tasks Graphs (STG) set [START_REF] Tobita | A Standard Task Graph Set for Fair Evaluation of Multiprocessor Scheduling Algorithms[END_REF]. The STG set provides 180 randomly generated DAGs with different sizes ranging from 50 to 5, 000 nodes. We select two sizes: 50 and 100 nodes. This leads us to two sets of 180 same-size graphs. For these two sets, we further distinguish between sparse and dense graphs. Recall that the density of a graph G = (V , E) is defined as

|E | |V |( |V |-1)
; hence the density is 0 for a graph without edges and 1 for a complete graph. We consider two different subsets of each set: (i) the 20 graphs, over the 180 available for each set, that exhibit the lower densities and (ii) the 20 graphs with the higher densities in the set. Because of lack of space, we report results only for sparse subsets and graphs with 50 nodes, but detailed results for the dense subsets and for larger graphs with 100 nodes are available in the companion research report [START_REF] Benoit | A performance model to execute workflows on high-bandwidth memory architectures[END_REF].

We need to set the number of computing operations, w i , for each node, v i , in the DAG and the number of data blocks, e i, j (i.e., number of bytes) on each edge. One of the key metrics in task graph scheduling with multiple memory levels is the computationto-communication ratio (CCR). In our framework, for a node v i and an edge e i, j , the CCR is the ratio of the time required to compute w i operations over the time required to transfer e i, j blocks to slow memory: CCR = w i s e i, j β s .

We let the CCR vary in our experiments and we instantiate the graphs as follows. For the computing part, we choose w i uniformly between w min i = 10 4 and w max i = 10 6 flops: since the processor speed s is set to 1.4 GHz, the computing part of each node is comprised between 10 -3 and 10 -5 seconds. For data transfers, we randomly and uniformly pick e i, j in the interval

w min i ×β s s×CCR , w max i ×β s s×CCR .

Results

To evaluate the heuristics, we execute each heuristic 50 times with different random weights on the 20 graphs from each STG subset; hence each point is the average of 1, 000 executions. Then, we compute the average makespan over all the runs. All makespans are normalized with the baseline without fast memory, CP +NoFast. The standard deviation is represented as error bars. We study the impact of the number of processors, the size of fast memory, and the fast memory bandwidth, by varying these parameters in the simulations.

6.2.1 Impact of the number of processors. Figure 4 presents the normalized makespan of graphs of 50 nodes, and with 1 GB fast memory, when we vary the CCR from 0.1 to 10 and the number of processors from 8 to 64 with the scheduling policy CP combined with each memory mapping. Figure 5 presents the same results but for the scheduling policy GG. All heuristics exhibit good performance in comparison to the two baselines CP +NoFast and CP +CcMode, but only GG +MemFair and CP +MemFair clearly outperform other heuristics, with an average gain around 50% over the baseline CP +NoFast. CP and GG present similar trends; the difference between heuristics performance lies in the memory mapping. With the approaches MemCP and MemGG, we give the maximum number of blocks possible to the successors (according to the heuristic rules). Several nodes might be strongly accelerated but likely at the expense of other nodes in the graph. On the contrary, MemFair aims at giving a fair amount of fast memory to each successor of the scheduled task. As a result, the usage of fast memory is more balanced across tasks in the graph than for mappings produced by MemCP and MemGG.

When the CCR decreases, the number of data blocks on the edges increases, and the graph no longer fits into fast memory. On the contrary, when the CCR increases, the number of data blocks on the edges decreases, so that the graph fits, at some point, into the fast memory; but then computations become the bottleneck, and the benefits of the high-bandwidth memory are less important. For small values of P, MemCP and MemGG show almost the same behavior with noticeable improvements over the case without fast memory NoFast, but are close to the cache mode CcMode. When the number of processors increases, the performance of CcMode decreases, mainly because when P increases, the size of each fast memory slice decreases. fast memory size and the CCR (see detailed results with more processors in the research report [START_REF] Benoit | A performance model to execute workflows on high-bandwidth memory architectures[END_REF]). As always, we vary the CCR from 0.1 to 10 and the size of fast memory from 200 MB to 16 GB. Recall that the fast memory bandwidth is set to 450 GB/s (five times faster). Clearly, when the size of the memory increases, the global performance of heuristics converges to the baseline CP +InfFast. All proposed heuristics perform better than the cache mode Cc-Mode, and MemFair outperforms other memory mappings with an average gain of around 25%, when the size of fast memory is small enough so that all data do not fit in fast memory. We observe that the CCR for which all heuristics reach the lower baseline InfFast decreases when the fast memory size increases. up to 16 times the slow memory bandwidth. We observe that for small bandwidths, the memory mapping MemFair outperforms the baseline InfFast. Recall that the fast memory bandwidth is the same for every memory heuristic, so InfFast has an infinite fast memory with a finite bandwidth. When the bandwidth is too small compared with the slow memory bandwidth, saturating the fast memory leads to decreased performance because the fast memory bandwidth is shared by the number of tasks concurrently trying to gain access to it. 6.2.4 Summary. All heuristics are efficient compared with the baseline without fast memory. But only two combinations, CP +MemFair and GG +MemFair, clearly outperform the baseline CP +CcMode. Recall that CcMode aims at imitating KNL's behavior when the system manages the fast memory as a cache. Therefore, obtaining better performance than this mode demonstrates the importance of a fine-tuned memory management when dealing with deep-memory architectures.

EXPERIMENTS

In this section, we assess the accuracy of the model by running both simulations and actual experiments for a 1D Gauss-Seidel computational kernel, using data movement between the slow and fast memories. We detail experimental settings in Section 7.1 and present results in Section 7.2. The code is available at https://gitlab. com/perarnau/knl/.

Experimental settings

Application data is partitioned into rectangular tiles and iteratively updated as shown in Algorithm 4, where Tile t i denotes tile i at iteration t.

t i ← Gauss-Seidel Tile t i -1 , Tile t -1 i , Tile t -1 i +1 ;
At each step of the procedure 1D-GS, Tile t i is computed as a combination of three tiles: (i) Tile t i-1 , its left neighbor that has just been updated at iteration t; (ii) Tile t -1 i , its current value from iteration t -1; and (iii) Tile t -1 i+1 , its right neighbor from iteration t -1. Each tile is extended with phantom borders whose size depends on the updating mask of the Gauss-Seidel kernel (usually we need one or two columns on each vertical border), so that each tile works on a single file of size m.

Our model currently does not allow for data movements between the slow and fast memories, so we decompose the update of each tile Tile t i into three sequential tasks: (i) task R t i transfers the tile from slow memory to fast memory; (ii) task C t i computes the tile in fast memory; and (iii) task W t i writes the updated tile back into slow memory. This leads to the task graph shown in Figure 8. We use this graph as input for the simulations and run the scheduling and mapping heuristics presented in Section 5. For the experiments, we extend the previous study developed for parallel stencil applications in [START_REF] Perarnau | Exploring Data Migration for Future Deep-Memory Many-Core Systems[END_REF] and provide a deep-memory implementation of the 1D Gauss-Seidel kernel for the KNL architecture. First, we copy tiles to migrate input and output data between slow and fast memory. Then, migration tasks and work tasks are pipelined, so that for a given iteration, three batches of tasks are executing concurrently: prefetching of future tiles in fast memory, computing on tiles already prefetched, and flushing of computed tiles back into slow memory. This scheme corresponds to executing tasks R t i+1 , C t i and W t i-1 in parallel, as in the classical wavefront execution of the dependence graph in Figure 8.

R t 0 C t 0 W t 0 R t i-1 C t i-1 W t i-1 R t i C t i W t i R t i+1 C t i+1 W t i+1 R t n C t n W t n . . . . . . . . . . . . . . . . . . R t+1 0 C t+1 0 W t+1 0 R t+1 i-1 C t+1 i-1 W t+1 i-1 R t+1 i C t+1 i W t+1 i R t+1 i+1 C t+1 i+1 W t+1 i+1
For the experiments, the parameters of the benchmark were the following: (i) input array of 64 GB; (ii) tiles of size 32 MB: (iii) 64 cores at 1.4 GHz; and (iv) 64 threads used. We vary the CCR by increasing the number of operations done per tile.

Results

For the benchmark runs, the platform runs CentOS 7.2, and experiments were repeated 10 times for accuracy. Figure 9 gives the performance of the benchmark against a baseline running entirely in slow memory with 64 threads. Figure 10 reports the results of the simulations for the same task graph, using the best heuristic, CP +MemFair, on 64 threads.

We observe a good concordance between the experiments and the simulations. In both cases, the performance of the application is greatly increased when using the overlapping scheme and fast memory access. For small values of the CCR, the execution time is divided by half. Then the gain starts to decrease when the CCR reaches the value 2, until reaching a threshold where there is no gain left. This is expected: the threshold is reached when the cost of computations becomes higher than the transfer time of a whole tile from slow memory. We have a discrepancy here since the threshold value is 10 for the experiments and 5 for the simulations. Still, both plots nicely demonstrate the impact of the CCR and the possibility of gaining performance when the CCR is low, hence when access to slow memory is the bottleneck.

CONCLUSION

In this paper, we address the problem of scheduling task graphs onto deep-memory architectures such as the Intel KNL. In addition to the traditional problems of ordering the tasks and mapping them onto processors, a key decision in the scheduling process is what proportion of fast memory should be assigned to each task. We provide a complete and realistic performance model for the execution of workflows on dual-memory systems, as well as several polynomialtime heuristics for both scheduling and memory mapping. These heuristics have been tested through extensive simulations and were shown to outperform the baseline strategies, thereby demonstrating the importance of a good memory-mapping policy. These results also demonstrate that the KNL cache mode can be outperformed by a customized memory mapping. We also conducted experiments on a KNL platform with a 1D Gauss-Seidel computational kernel and compared the performance of a tuned memory mapping with that of the heuristics in simulation, thereby demonstrating the accuracy of the model and bringing another practical proof of the importance of a fine-tuned memory management of the fast memory.

Future work will be devoted to extending simulations on other kinds of workflow graphs, such as fork-join graphs, and extending the model in order to allow for moving data across both memory types. This is a challenging endeavor, because it requires deciding which data blocks to move, and when to move them, while other tasks are executing. Also, we would like to conduct additional experiments with more complicated workflows, such as those arising from dense or sparse linear factorizations in numerical linear algebra. All this future work will rely on the model and results of this paper, which represent a first, yet crucial, step toward a full understanding of scheduling problems on deep-memory architectures.

Figure 1 :

 1 Figure 1: Target memory hierarchy.

Figure 2 :

 2 Figure 2: Simple DAG example.

Figure 3 :

 3 Figure 3: Events with two tasks.

f

  be the number of blocks allocated to the fast memory, M f , during chunk k. At the beginning, no blocks are allocated; hence we set S (0) f = 0. At the start of a new chunk k, we first initialize S

Algorithm 1 : 2 k ← 1 ; 3 S

 1213 Compute the makespan of G1 procedure Makespan (G, φ, τ , S f , P) begin

Algorithm 3 : 3 X

 33 Heuristic MemFair1 procedure MemFair (v i ) begin 2Let U be the set of v i 's successors ordered by w i ;

6. 2 . 2

 22 Impact of fast memory size.

Figure 4 :Figure 5 :

 45 Figure 4: Impact of the number of processors with 50 nodes and S f = 1 GB fast memory for CP scheduling heuristic.

6. 2 . 3

 23 Impact of fast memory bandwidth.

Figure 6 : 4 Figure 7 :

 647 Figure 6: Impact of fast memory size with 50 nodes and 8 processors.

Algorithm 4 :

 4 1D Gauss-Seidel algorithm 1 procedure 1D-GS(array) begin 2 for t = 1 to . . . do 3 for i = 1 to . . . do 4 Tile

Figure 8 :

 8 Figure 8: 1D stencil task graph, where t is the iteration index, i is the tile index, and m is the size of one tile.

Figure 9 :

 9 Figure 9: Performance of a 1D stencil running on a KNL with 64 threads.

Figure 10 :

 10 Figure 10: Performance of a 1D stencil according to the model, with 64 threads.

ACKNOWLEDGMENTS

Argonne National Laboratory's work was supported by the U.S. Department of Energy, Office of Science, Advanced Scientific Computer Research, under Contract DE-AC02-06CH11357. This research was supported by the Exascale Computing Project (17-SC-20-SC), a collaborative effort of the U.S. Department of Energy Office of Science and the National Nuclear Security Administration.


Rachid Dris
email: drisr@leesu.enpc.fr

Johnny Gasperi
email: gasperi@u-pec.fr

Mohamed Saad

Cécile Mirande

Bruno Tassin

Synthetic fibers in atmospheric fallout: a source of microplastics in the environment?

Keywords: Microplastics, Urban environment, Atmospheric fallout, Microplastic sources, Synthetic fibers

Sources, pathways and reservoirs of microplastics, plastic particles smaller than 5 mm, remain poorly documented in an urban context. While some studies pointed out wastewater treatment plants as a potential pathway of microplastics, none have focused on the atmospheric compartment. In this work, the atmospheric fallout of microplastics was investigated in two different urban and sub-urban sites.

Microplastics were collected continuously with a stainless steel funnel. Samples were then filtered and observed with a stereomicroscope. Fibers accounted for almost all the microplastics collected. An atmospheric fallout between 2 and 355 particles/m 2 /day was highlighted. Registered fluxes were systematically higher at the urban than at the sub-urban site. Chemical characterization allowed to estimate at 29% the proportion of these fibers being all synthetic (made with petrochemicals), or a mixture of natural and synthetic material. Extrapolation using weight and volume estimates of the collected fibers, allowed a rough estimation showing that between 3 and 10 tons of fibers are deposited by atmospheric fallout at the scale of the Parisian agglomeration every year (2500 km²).

These results could serve the scientific community working on the different sources of microplastic in both continental and marine environments.

INTRODUCTION

Microplastics are a widespread particular contaminant originating from the breakdown of larger plastic debris (secondary) or directly manufactured on a millimetric or submilletric size (primary) [START_REF] Cole | Microplastics as contaminants in the marine environment: A review[END_REF]. These plastics have been defined as particles with the largest dimension smaller than 5 mm [START_REF] Arthur | Proceedings of the International Research[END_REF]; they cover a continuous spectrum of sizes and shapes including 1D-fibers, 2Dfragments and 3D-spheres.

Given their size, these microparticles can be ingested by a wide range of species, either in marine [START_REF] Anastasopoulou | Plastic debris ingested by deepwater fish of the Ionian Sea (Eastern Mediterranean)[END_REF][START_REF] Lusher | Occurrence of microplastics in the gastrointestinal tract of pelagic and demersal fish from the English Channel[END_REF][START_REF] Thompson | Lost at sea: where is all the plastic?[END_REF] or freshwater environnements [START_REF] Sanchez | Wild gudgeons (Gobio gobio) from French rivers are contaminated by microplastics: Preliminary study and first evidence[END_REF]. These microplastics have negative effects on organisms and the possibility of their translocation, bioaccumulation and trophic accumulation is currently being debated [START_REF] Wright | The physical impacts of microplastics on marine organisms: A review[END_REF].

While marine plastic pollution has been well documented, there has been limited focus on the continental contamination (Dris et al., 2015b;[START_REF] Wagner | Microplastics in freshwater ecosystems: what we know and what we need to know[END_REF]. Moreover, its sources, pathways and reservoirs in urban environments remain largely unknown. It is crucial to gather a better knowledge about these particles in the continental environment as rivers are said to be the main source of marine microplastics [START_REF] Andrady | Microplastics in the marine environment[END_REF]. If it is very often cited that 80% of the fibers in the marine environment come from the continent, this estimation is not well documented and demonstrated.

Synthetic fibers are one of the forms in which microplastics can be found. They derive presumably from synthetic clothing or macroplastics. Different pathways are thought to be an important source of fibrous microplastics in the aquatic environment. It has been shown that laundry washing machines discharge large amounts of microplastics into wastewaters (reaching 1900 fibers in one wash [START_REF] Browne | Accumulation of Microplastic on Shorelines Woldwide: Sources and Sinks[END_REF]). During wastewater treatment, synthetic fibers are known to contaminate sewage sludge [START_REF] Habib | Synthetic fibers as indicators of municipal sewage sludge, sludge products, and sewage treatment plant effluents[END_REF][START_REF] Zubris | Synthetic fibers as an indicator of land application of sludge[END_REF]. The sources and fate of microplastics in the various compartment of the urban environment are poorly documented (Dris et al., 2015a); this paper focuses on the atmospheric compartment and investigates the contribution of the atmospheric fallout as a potential vector of plastic pollution.

MATERIALS AND METHODS

Total atmospheric fallout was collected on two sampling sites: one in a dense urban environment (48°47'17.8"N, 2°26'36.2"E -Site 1 -Figure 1) and one in a less dense sub-urban environment.

(48°50'27.8"N, 2°35'15.3"E -Site 2 -Figure 1). Site 1 was monitored over a period of one year (February 19 th 2014 to March 12 th 2015) and site 2 for a shorter period from October 3 rd to 12 th March 2015. Site 1 is localized in an area of 7900 inhabitants/km 2 while site 2 is characterized by a surrounding population of 3300 inhabitants/km 2 ("Insee -Régions, départements et villes de France," 2011).

The sampling surface was 0.325 m 2 allowing for total atmospheric fallout (dry and wet deposition) to be collected through a stainless steel funnel. A 20 L glass bottle was placed at the bottom of the funnel in an opaque box to collect the water. The samples were collected at various frequencies during the monitoring period depending on cumulative rainfall leading to 24 samples at site 1 and 9 at site 2.

When both sites were monitored, the collection of samples was carried out the same day for both sites in order to allow comparison. No interruption of the sampling occurred during the whole monitoring period in each site, providing a full view of the annual variability of the atmospheric fallout.

Each time the atmospheric fallout was collected, the funnel was rinsed with 3*1 L of reverse osmosed water in order to recover all particles adhering to the funnel. As commonly done in studies focusing on the pollutant fluxes in atmospheric fallout, preliminary tests demonstrated the efficiency of such rinses. Consecutive rinses with 1 L showed that in the fourth rinse, the number of microplastics is similar to the one in the laboratory blanks. After the rinsing step, samples were immediately covered until the processing step to avoid any contamination. Given the sampling period and the collecting surface area, the atmospheric fallout is expressed as a number of particles per square meter per day.

The rainfall was recorded for both sites.

All samples were filtered on quartz fiber GF/A Whatman filters (1.6 µm). To minimize post-sampling contamination from indoor air, samples were always covered. The filters and the vessel were heated to 500°C prior to their use. All laboratory procedures were performed wearing a cotton laboratory coat. Laboratory blanks were performed to verify that no microplastics are added to the samples during the laboratory procedures. Globally, blank results do not reveal any significant contamination in comparison to the levels found in samples (1 to 2 fibers per filter, representing between 0.5 and 5% of the fibers on the samples).

Filters were observed with a stereomicroscope (Leica MZ12). Previously used criteria were employed in order to identify synthetic fibers (Dris et al., 2015a;[START_REF] Hidalgo-Ruz | Microplastics in the Marine Environment: A Review of the Methods Used for Identification and Quantification[END_REF][START_REF] Norén | Small plastic particles in Coastal Swedish waters -Kimo reports[END_REF]. The accuracy of the method was estimated by comparing the counting of 3 different observers on the same filters. No difference > 5% in the total number of fibers was observed. In 11 of the collected samples, the length of the fibers was measured during the counting (the software "Histolab" coupled with the stereomicroscope). The observation size limit was defined to 50 µm.

Atmospheric fallout in this study is presented as a number of total fibers. Chemical characterization was also performed. A subsample of n=24 fibers was analyzed with Fourier Transform infrared (FT-IR) micro spectroscopy (Microscope LUMOS FT-IR -Brucker) coupled with an ATR (Attenuated Total Reflectance) accessory in order to characterize the proportion of synthetic and natural fibers and identify the predominant plastic polymers. The fibers were categorized according to the classification proposed by the international organization for standardization (ISO/TR 11827:2012 Textiles -Composition testing -Identification of fibers).

RESULTS AND DISCUSSION

Based on a long term monitoring (one year), our results show large amounts of fibers in the atmospheric fallout, which has not yet been reported in the literature. Throughout the year of monitoring (site 1), the atmospheric fallout ranged from 2 to 355 particles/m 2 /day (Figure 2) with an average atmospheric fallout of 110  96 particles/m 2 /day (mean  SD), indicating a high annual variability. On Site 2 (6-month monitoring), the atmospheric fallout was around 53  38 particles/m 2 /day (mean  SD).

Figure 3 illustrates the proportion of fibers belonging to each size range considered for 11 samples. It can be seen that the smallest fibers (in the 200 -400 µm and 400 -600 µm size ranges) are predominant while fibers in the larger size ranges are rare. Few fibers have been found in the 50 µm -200 µm size range. Fibers smaller than < 50 µm are also observed with the stereomicroscope, but since their nature can be hardly identified, they were not taken into account. The length of the fibers was measured during counting. The diameter of the fibers varies mainly between 7 and 15 µm. Rainfall seems to be an important factor influencing the fallout flux. In fact, particularly low numbers of fibers were found during dry weather or low cumulated rainfall periods. For rainfall between 0 and 0.2 mm/day, an atmospheric fallout between 2 and 34 particles/m 2 /day was recorded. During rainy periods (from 2 to 5 mm/day), highly variable levels of atmospheric fallout were encountered ranging from 11 to 355 particles/m 2 /day. No significant correlation between the levels of fibers in atmospheric fallout and the mean daily rainfall was highlighted. The same conclusion is obtained by considering the cumulative rainfall and the total amount of fibers collected. This indicates that if the absence of rain limits the microplastics atmospheric fallout, rainfall height is a significant factor, though not the only one, contributing to fallout variability; other mechanisms and temporal conditions also contribute to the fallout flux, but remain to be identified.

When the levels on both sites are compared side by side, it can be seen that through all the monitoring periods, the sub-urban site systematically showed fewer fibers then the urban one (Figure 4). Statistical tests showed a significant difference between the atmospheric fallout on the urban and the sub-urban site (Wilcoxon matched pairs test, confidence level of 5%, pvalue = 0.007). One of the reasons that could explain this difference is the density of the surrounding population, which is considered as a proxy of the local activity. This is a pilot study as it contains only two sampling locations leading to a limited statistical power.

Fourier Transform infrared (FT-IR) spectroscopy showed that half of the analyzed fibers are natural fibers (50%) being mainly cotton or wool. The remaining fibers are man-made. For 21% of the total fibers, they are manufactured by transformation of natural polymers (rayon or acetate from cellulose).

In an other hand, 17% of the fibers corresponds to purely synthetic fibers, mainly polyethyleneterephthalate and only one fiber of polyamide. The other 12% fibers are made with a mixture of different materials including purely synthetic materials fibers (mixture of polyethylene-terephthalate and polyurethane) and fibers being a mixture of natural and synthetic materials (cotton and polyamide). Therefore, petrochemicals are found in 29% of the analyzed fibers in atmospheric fallout.

Given the lack of studies and data addressing the issue of plastic sources and fluxes in an urban area, it is hard to evaluate the importance of the atmospheric fallout as a source of microplastics. According to the average atmospheric flux of total fibers on each site (110 and 53 particles/m 2 /day), the length of the fibers (Figure 3), their approximated section (80 µm 2 ), the mass of fibers in the atmospheric fallout per year may be assessed. Two densities were considered : 1 for the polyamide and 1.45 g/cm 3 for the polyethylene-terephthalate, corresponding to two low and heavy plastic polymers widely used in the textile industry [START_REF] Hidalgo-Ruz | Microplastics in the Marine Environment: A Review of the Methods Used for Identification and Quantification[END_REF]. At the scale of the Parisian agglomeration (area around 2500 km 2 ), it was estimated that between 3 and 10 tons of synthetic fibers, including microplastics, could originate annually from the atmosphere.

CONCLUSIONS

These results show a significant amount of fibers in atmospheric fallout, which leads to the hypothesis that the atmospheric compartment should not be neglected as a potential source of microplastics, specially knowing that we estimated at 29%, the amount of these fibers containing at least partially plastic polymers. These microplastics have different possible sources: synthetic fibers from clothes and houses, degradation of macroplastics, landfills or waste incineration. The characterization indicates that the hypothesis of the clothing being the main source of these fibers is the more plausible. These fibers in the atmosphere, including microplastics, could be transported by wind to the aquatic environment [START_REF] Free | High-levels of microplastic pollution in a large, remote, mountain lake[END_REF] or deposited on surfaces of cities or agrosystems. After deposition, they could impact terrestrial organisms or be transported into the aquatic systems through the runoff.

More work is needed in order to investigate these atmospheric fibers and understand where they come from, where they end up and which mechanisms and factors lead to their transport and their fallout.

The micro IR-TF spectroscopy analysis shows the presence of microplastic fibers in the atmospheric fallout. Nevertheless, some questions arise regarding the definition of microplastics in relation with their nature and the ISO classification. Only fibers made of petrochemicals are generally considered in the literature as microplastics [START_REF] Song | A comparison of microscopic and spectroscopic identification methods for analysis of microplastics in environmental samples[END_REF]. Authors think that fibers made of a mixture of natural and synthetic materials should be also included in the identification of microplastics. Further discussions are also needed to identify if artificial fibers, which are manufactured by transformation of natural polymers, could be included in microplastics. In fact, these fibers might also be prevalent in marine and continental environments and could cause physical impacts on organisms. Moreover, harmful additives and dyes can be used when manufacturing these fibers.

Furthermore, this study could serve the implementation of the marine strategy framework directive (MSFD) [START_REF] Galgani | Marine litter within the European Marine Strategy Framework Directive[END_REF] aiming to achieve by 2020 the good environmental status for European marine waters. The indicator 10 of the MSFD related to marine liter with a focus on microplastics indicates that the solution for marine plastic pollution is to tackle the problem at its source. This work does not aim to provide accurate atmospheric fluxes for microplastics as a lot of uncertainties remain and more studies are needed, but serves to highlight the important role that this source could play in continental and marine environments and encourages scientists to take it into consideration in future works.

ACKNOWLEDGMENTS

We address sincere thanks to the members of the LISA (Laboratoire Interuniversitaire des Systèmes Atmosphériques), especially Anne Chabas. The PhD of Rachid Dris is funded by the region Île-de-France Research Network on Sustainable Development (R2DS Ile-de-France). We thank Kelsey Flanagan for lingual improvements on the manuscript. We thank the members of the ICMPE (Institut de Chimie et des Materiaux Paris-Est) especially Mohamed Guerrouache and Valérie Langlois. We also thank Ludovic Lemee and Gregory Candor from Brucker Optics.

FIGURES CAPTIONS

Figure 1 :

 1 Figure 1: Localization, sampling device and synthetic fibers for each site Figure 2: Atmospheric fallout of microplastics on the site 1 in parallel with daily rainfall Figure 3: Size distribution of synthetic fibers in 11 atmospheric fallout samples (site 1). Boxplots are plotted from bottom to top with: [ Lower quartile -1.5*Interquartile range ], [ Lower quartile ], [ Median ], [ Upper quartile ], [ Upper quartile + 1.5*Interquartile range ]. Outliers are displayed as isolated points.Figure 4: Atmospheric fallout of microplastics on an urban site (site 1) and a sub-urban site (site 2)

Figure 4 :

 4 Figure 1: Localization, sampling device and synthetic fibers for each site Figure 2: Atmospheric fallout of microplastics on the site 1 in parallel with daily rainfall Figure 3: Size distribution of synthetic fibers in 11 atmospheric fallout samples (site 1). Boxplots are plotted from bottom to top with: [ Lower quartile -1.5*Interquartile range ], [ Lower quartile ], [ Median ], [ Upper quartile ], [ Upper quartile + 1.5*Interquartile range ]. Outliers are displayed as isolated points.Figure 4: Atmospheric fallout of microplastics on an urban site (site 1) and a sub-urban site (site 2)


Anne Tchounikine

Maryvonne Miquel

Thierry Pécout

Jean-Luc Bonnaud

Prosopographical data analysis. Application to the Angevin officers (XIII-XV centuries)

The EUROPANGE project, involving both medievalists and computer scientists, aims to study the emergence of a corps of administrators in the Angevin controlled territories in the XIII-XV centuries. Our project attempts to analyze the officers' careers, shared relation networks and strategies based on the study of individual biographies. In this paper, we describe methods and tools designed to analyze these prosopographical data. These include OLAP analyzes and network analyzes associated with cartographic and chronological visualization tools.

I CONTEXT

This research work was conducted within the framework of the EUROPANGE project funded by the ANR (French National Research Agency) and the Ecole Franc ¸aise de Rome's five-year program. It emanates from a team that links computer scientists and medievalists studying the rhythms and elaboration methods of political communities. The thirteenth to fifteenth century constitute an ideal period to observe the development of organisms, speech methods and corps of administrators, within the context of the birth of national and princely states. For this project, we examine the emergence of a particular political and societal environment through the constitution of a corps of administrators (the officers), with their relation networks, with jurisdiction within the political space of the Angevins' possession: Anjou, Maine, Provence, Lorraine, Southern Italy and Sicily, Piedmont, Lombardy and Tuscany, Hungary, Poland, Morea, and the Balkans. This spatially disjoined and temporally variable nature of the area administered by the officers, required new capabilities within the political bodies to rally and administer, creating a common political discourse, which is of special interest today in the context of current reflections on the construction of Europe. During the last two decades, historians have rethought the role of the individual as an actor ([2, 10, 5, 9]). According to Pierre-Marie Delpu ([3]), a prosopography could be minimally defined as a collective study which extracts the common characteristics of a group of historical actors based on the systematic observation of their lives and individual careers. This approach, coupled with quantitative and statistical methods and advanced display methods has shown that prosopography is the most accurate way to determine the sociological aspects of a particular group of people through its members' individual careers ([14, 8, 1]).Our project attempts to reconstitute the officers' careers, shared relation networks and strategies.

II CONTRIBUTIONS

The data to be gathered and analyzed include all the biographical details of the officers and their acquaintances, extracted from the inventory of archival and iconographical sources (Angevin chancery records, deeds, epigraphic sources). Our contribution hinges on 3 elements:

• a collaborative application for the capture and rendering of the data in the form of prosopographical pages made up of the consolidated, enhanced, structured and formatted data ( [START_REF] Tchounikine | Modélisation de données pour une base de données prosopographique[END_REF]), • an analytics application to build and survey multi-criteria populations,

• a prosopographical database used by the above applications. All these elements make up the software suite Prosopange which is presently deployed on the French CNRS TGIR Huma-Num site. This software suite (see Figure 1) is a 3-tier client-server application. The data tier is made up of a database that allows structuring the set of data that characterizes an officer. The users who extract from and analyze the bibliographical sources usually enter this data directly, but data can be also found that are automatically computerized from the entered data. The processing tier includes algorithms for data creation and searching within the database, various controls and computation and analysis algorithms. Finally, the client tier is made up of the user Web interface equipped with data acquisition processing, and requesting and displaying tools. In this paper, we will mainly focus on the prosopographical data analytics application. This application involves multidimensional analyzes and relation network analyzes connected to temporal and cartographical representations of data. These analyzes are carried out on selected officers' populations by means of a multi-criteria filter relying upon the historical period, the concerned territories and/or individual traits (religion, gender, locations . . . ).

III OLAP CUBE AND ANALYSIS

Leonardus Afflicto de Scallis, native of del Giustizierato di Terra di Lavoro Citra (Kingdom of Sicily), professor juris civilis holder since September 24th 1372 appointed in 1373 by Johanna I as judex major et secundarum appelationum in the Counties of Provence et Forcalquier. He is referred to as nobilis and vir in the documents after 1378.; these are the kinds of data that are available in the database.

It soon became apparent that the historians involved in the project as research partners had multiple expectations in terms of data analysis. This was especially true for the number of themes interesting them: some are interested in the movement of the officers, their impact and influence areas; others focus on the territory political organization, appointment games and duty stations; or the sociology of the constituted corps, officers' places of origin, their acquaintances and their honorific or their qualifying academic degrees. The methods and the choice of analyzed populations are themselves also diverse: quantitative mass analyzes, temporal or spatial transversal analyzes, and analyzes of an identified group of officers, faction, trade and even a single individual. In order to satisfy all these requirements and be open to future requirements, we propose a flexible user interface that offers the researcher the opportunity to build his/her specific analysis dynamically.

Data warehousing and OLAP (On Line Analytical Processing) are database technologies specially designed for data analysis and decision making ([6, 7, 13]). They allow interactive multidimensional data analysis and are proving to provide interesting solutions. OLAP data modeling is guided by analysis needs. It relies on multidimensionnal models that are built around the major analysis subject (called facts) and the various axes which might be used to elaborate an analysis (called dimensions). The OLAP engine stores detailled data and can materialize all or selected aggregates so as to allow fast access to summarized data. At the front-end user interface level, OLAP technologies provide operators and tools to interactively explore the multidimensional data, supporting in the meantime the iterative nature of the analysis process, and allowing the analysts to navigate across data at different levels of detail without the use of query languages.

OLAP presupposes that the various axes which might be used to elaborate an analysis be defined in advance. As far as historians are concerned, the challenge was to identify, define and create these various analysis axes. For the computer scientist, the problem has been to adapt the OLAP concepts and operators to the specificities of prosopographical data and historians needs. The OLAP analyses focus on a unique fact: the officers. Officers have to be enumerated and identified (i.e. listed) according to various analysis axes. These axes allow us to describe the officer, his/her office or offices, his/her title or titles, (academic degrees, honorific). Within the multidimensional model, 3 dimension categories are defined:

• dimensions related to individuals: place of origin, gender, place of residence, religion, various dates (birth, residence...). . . • dimensions related to the public offices hold by individuals: office type, place of work, place of duty, appointment, exercise dates. . . • dimensions related to the individual titles: honorific, academic degrees, dates of granted titles. . . Concerning the OLAP analysis, the user dynamically chooses among these 3 categories, the dimensions he is willing to include in his multidimensional table, with the option for combining categories: for example, ("place of origin" x "religion") or ("place of origin" x "religion" x "types of offices"). Aggregate measures can include a distinct count of officers or offices and the calculation of the duration of offices and of associations.

Unfortunately all these dimensions have many irregularities: The fact-dimension associations often are multivalued, for example an officer may occupy several offices simultaneously or sequentially, a single office can have several places of duty. The database filled levels also are varying, because the collected information within the manuscript sources is very often incomplete or vague. Moreover, many dimensions are not orthogonal, for example the place of duty dimension depends on the office dimension, and many are also unbalanced (see Figure 2, a dimension extract type of office in the cross-table). In addition, it is impossible to build, a priori, a multidimensional schema and cube as should be done in a classical decision-support application because of the unpredictability of the historian requests and the evolution of dimension

E d i = E d i { j } parents(j, d i ) nr(j, d i , l) E c i = E d 1 × E d 2 × ... E of f ices = ∪E c i foreach q i in o. titles : // same as offices foreach coordinate in E individuals × E of f ices × E titles :
add or update a point p in the cube and compute associated measure : p.measure.add(o) // the measure contains the list of concerned officers members which are progressively discovered as documentary sources are analyzed . Therefore, the traditional use of an OLAP server is not possible. Our algorithm to compute the hypercube takes as an input every officer (see Algorithm 1) and is calculated on the fly at request time on the server side using the database data. Every officer's data are transformed in a point in the multidimensional target space and the set of aggregate points is updated. For example in a "place of origine" x "type of office" cube, data on Leonardus Afflicto will generate the following points in the multidimensional space : ("Terra di Lavoro", "judex"), ("Terra di Lavoro", "principal"), ("Terra di Lavoro", "justice"), ("Terra di Lavoro", "central office")...("Sicily", "judex"),("Sicily", "principal") and so on considering the dimension hierarchical instances...

Dynamic of dimensions

For each regular balanced dimension hierarchy, historians predefine the levels. For example, for the spatial dimension used in places of origin, residence, work, and duty, the predefined hierarchical schema is : location < subdivision < political space < territory < all; concerning the public office types, an unbalanced parent-child tree hierarchy is used. The members of balanced or unbalanced dimensions are built as and when database insertions are performed and gradually build up a set of nomenclature data. The choices of the dimensions and nomenclature constitutions have been performed according to both the needs expressed by the historians and the computer scientists' need to have a repository for comparative analyzes. Hence the hierarchical spatial dimension arises from a consensus on a territorial division. However, the choice related to member incorporation according to evolving needs, allows us to take into account new places during the acquisition of the officers and thus to enhanced the hierarchy.

Incomplete and imprecise data

The strategy implemented by the algorithm 1 allows us to accurately generate known or entered data at various levels. For example, an officer whose place of origin is only known at the subdivision level will be obviously booked into the subdivision aggregates and the upper ones (political spaces, territories, all). At every detailed level of this dimension, this inaccuracy will be translated by means of a dynamical inclusion of an empty child member in order to provide a correct counting. The multivalued data are also taken into account. An officer who held public offices of "judex" and "notarius" types will occur in both the "Justice" and "Writting" aggregates and in the upper level aggregates (Script, Central offices. . . ). Date entries especially are frequently imprecise or incomplete: thus, in the GUI for data entering, we allow the entry of dates with full or partial yyyy-mm-dd format but also interval, alternative or prefixed date (post, circa, ante). These dates are processed in order to be mapped into minimum and maximum timestamps that are used for chronological sorts and duration calculus.

Cube materialization and OLAP navigation

Unlike the conventional OLAP approach, multidimensional space is here dynamically built as the scan of the officers' associated data is progressing. The hypercube is thus fully materialized; the aggregate set is calculated and then sent to the client. This choice of both full materialization of the cube and officer table scan is made possible due to the small amount of data (˜7000 officers) and it allows insuring good performances during the OLAP navigation. On the client side, we implemented the set of classical OLAP operators ( [START_REF] Gray | Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-total[END_REF][START_REF] Rafanelli | Multidimensional Databases: Problems and Solutions[END_REF]):

• sort: to sort dimension members (i.e. row and column headers within the table),

• drill-down: to move to a hierarchy finer level (i.e. spread the offspring of a row or column header), • roll-up: to move to a hierarchy coarser level (i.e. aggregate the offspring of a row or column header), • slice: to remove a member of the cube (i.e. remove a header and its offspring within the rows and columns of the table), • drill-through: to make a drill-down then a slice on a row and column header). The results are provided in the form of tables, charts, choropleth maps. Figures 2 and3 show the result of the analysis of the number of officers by type of public office and persons or types of persons who performed their appointment. Here, the public office hierarchy is extended till the detailed level for the "General Command" type and the person type hierarchy is deployed for the "Sovereign" type. A click on a table cell highlights the cell in green and allows getting the list of the concerned officers and for each of them his prosopographical page can be displayed.

IV RELATION NETWORK ANALYSIS

One of the Europange project goals is to analyze interpersonal relationships such as family, profession and friendship. This information describing relationships that connect an officer to other individuals in the database are implemented by 4-tuples (source of relation officer, connected target individual, relation type, connection date), for example ("L. Afficto de Scallis", "sovereign Johanna I", "fidelis", "06/07/1371"). The connections are typed and oriented, and eventually associated to a reciprocal link during the acquisition. The connection type is selected among an unbalanced tree hierarchy (see Figure 5, left frame).

Starting from this information, 3 types of graph are built:

• an inter-personal graph in which individuals are vertices and directed edges are made up with acquired and computed relationships both labeled with the first and last relation reference dates and weighted according to the relationship's known or computed duration (first and last date mention), • an officer-public office graph in which individuals and offices are vertices and which edges represent the office holding that are both labeled by means of assignment dates and weighted by the holding computed duration (first and last date mention), • a graph for residence coincidence or assignment coincidence which vertices are officers and which edges connect the officers having resided or being assigned at the same location, same dates and weighted according to the coincidence computed duration (number of years)(see algorithm 2). These different graphs are calculated on the server side thanks to suited OLAP cubes with duration of links aggregated measure. They may be displayed on the client side under the form of relation networks or coincidence matrix. Customization tools allow the historians to undertake structural analyzes and to interpret and interrogate these graphs. Thus, the user can select the relation types to be displayed or colored in the graph; the user can also make the graph dynamically evolve on a chosen period of time or search for and highlight vertices according to a label.

V EGO-CENTERED ANALYSIS

The aim of this analysis is to enrich the traditional tools of the prosopographical method that very often provide only a descriptive vision of the careers and relationships without any true understanding of their formation. The ego-centered relation network investigation allows comparing the social capital of several people. It requires scaling-up (from the study of an entire group to the study of specific cases) and imposes a dynamic vision. A static vision of the relations between people is artificial since it does not take into account the role of time, a significant problem for historians. In an officer study, one of the main issues is to look into both the constitution of a homogenous milieu of officers and analyze how it was constructed. One possible perspective is to consider how newcomers are incorporated into their new environment. Varying forms of data can be examined and compared to understand and measure immigrant integration: migratory flows (origin of the officer, place of residence, place of duty); marriages as marker of the integration in the host society and as an influence on the conferring of noble title and position; professional networks; nomination and promotion; the individual or family policies of sale or purchase of goods, donations to local places of worship,chosen burial sites...

To complete this analysis, a graph centered on the central individual (called "ego") is built which aggregates the inter-personal graphs, the coincidence graphs of the ego and the graphs of the officers connected to him. The number of iterations and depth of the graph is set by the user.

A cartography of the officers present in the graph (origin of the officer, place of residence, duty place) and the ego's chronology made up with his various associated dates (dates of the various offices, academic degree dates of graduation, link dates, . . . ) are associated and displayed with the graph. Tools for time-based animation synchronized to the different components (network, cartography and chronology) allow highlighting the momentum of the network establishment and the career paths (see Figure 6).

VI CONCLUSIONS AND OUTLOOK

The Prosopange software suite and its database are currently deployed on the digital humanity Huma-Num site. About 60 medievalist researchers (including French, Italian, Hungarian, Pole, German . . . ) daily feed this site with data gathered thanks to the analysis of manuscript archival documents (currently more than 7000 officers covering a period from 1210 until 1539). The database is already the largest one in the field in terms of the number of officers and of data points per officer, and can be used for bibliographic reviews by every researcher who submits an account request. The definition of the different classifications composing the dimensions, the public offices, the relations and the positions, required a significant effort to pool, name, synthesize and reach a consensus encompassing the terms used, their classification and their prioritization. This work is fully unprecedented and amounts to a result in itself. The nomenclature of places, in turn, lays the groundwork for an administrative cartography. The use of the database and the analysis tools reveal the relevance of a collaborative approach: the historians enrich their knowledge of the officers' careers thanks to the pooling of data collected by the researchers who are experts in different political spaces; the analysis reveals the links between individuals that transcend the territories and allows them to contextualize and to compare the corps organization in the various spaces and over time. Prosopange allowed accumulating a huge amount of unpublished tools and materials. The processing of all these resources is just starting and it already allows supplying various research topics related to, for example, the public office typology, recruitment profiles, the analysis of periods during which parties are formed during severe political tensions, or further more to the study on the relation between administrative standards and the office practice. From a computer science point of view, the work is ongoing in two directions. A first perspective will be to extend the analysis tools particularly to the dynamics and the navigation in the networks and to the regularities and singularities in the officer career paths. A second challenge is the consideration of the highly variable quality and quantity of the data that are an ongoing problem when medieval documentary sources have to be processed. In fact, the bibliography of certain officers could be informative, very precise while the hitherto known information concerning other officers could be piecemeal or questionable. In this context, any quantitative analysis has to be treated with caution and should be coupled with metrics by measuring the accuracy and the significance.

VII ACKNOWLEDGMENT

This Europange project was made possible by the financial support from the ANR (French National Research Agency) and from the Ecole Franc ¸aise de Rome's five-year program.

Figure 1 :

 1 Figure 1: Architecture of the Prosopange software suite.

Figure 2 :

 2 Figure 2: OLAP Analysis of the cube: "type of office" x "appointment"

Figure 3 :

 3 Figure 3: Details of the cross-table shown figure 2.

Figure 4 :Algorithm 2

 42 Figure 4: Types of graphs.

Figure 5 :

 5 Figure 5: Visualization of an inter-personal network with family relation coloring and parametrization of the period, plus officer-public office and coincidence graphs

Figure 6 :

 6 Figure 6: Visualization of an ego-centered network with cartography of officers selected in the graph and chronological record of the ego.

  Algorithm 1 Construction of a cube cube(in : population of officers, list of dimensions; out : cube) foreach o in population : foreach dimension d i related to individuals : E d i = {} //coordinates on d i axis foreach j member of d i at level l i in o properties : // j can be religion of o, place of origin , gender etc . E d i = E d i { j } // add j to coordinates E d i = E d i parents(j, d i ) // add all ancestors of j in d i hierarchy E d i = E d i nr(j, d i , l) // add empty child for each incomplete lower level E individuals = E d 1 × E d 2 × ... foreach c i in o. offices : foreach dimension d i related to public offices : // public office is a multivalued dimension E d i = {} foreach data j corresponding to d i at level l

i : // j can be office type , place of work, ...

Journal of Data Mining and Digital Humanities

http://jdmdh.episciences.org


Giovanna Guidoboni

Christophe Prud'homme

Lorenzo Sala

Marcela Szopos

Unconditionally Sta-

Unconditionally stable operator splitting method for a multiscale application in ophthalmology

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.