Philippe Virouleau

Pierrick Brunet

François Broquedis

Nathalie Furmento

Samuel Thibault

Olivier Aumage

Thierry Gautier
email: thierry.gautier@inrialpes.fr

Evaluation of OpenMP dependent tasks with the KASTORS benchmark suite

Keywords: OpenMP, task dependencies, benchmarks, runtime systems, KAS-TORS

The recent introduction of task dependencies in the OpenMP specification provides new ways of synchronizing tasks. Application programmers can now describe the data a task will read as input and write as output, letting the runtime system resolve fine-grain dependencies between tasks to decide which task should execute next. Such an approach should scale better than the excessive global synchronization found in most OpenMP 3.0 applications. As promising as it looks however, any new feature needs proper evaluation to encourage application programmers to embrace it. This paper introduces the KASTORS benchmark suite designed to evaluate OpenMP tasks dependencies. We modified state-of-theart OpenMP 3.0 benchmarks and data-flow parallel linear algebra kernels to make use of tasks dependencies. Learning from this experience, we propose extensions to the current OpenMP specification to improve the expressiveness of dependencies. We eventually evaluate both the GCC/libGOMP and the CLANG/libIOMP implementations of OpenMP 4.0 on our KASTORS suite, demonstrating the interest of task dependencies compared to taskwait-based approaches.

Introduction

HPC architectures evolved so rapidly that it is now common to build shared-memory configurations with several dozens of cores. The recent appearance of technologies such as the Intel Xeon Phi co-processor makes affordable configurations with thousands of cores a not-so-far reality. Efficiently programming such large-scale platforms requires to express more and more fine-grain parallelism.

Standard parallel programming environments such as OpenMP have evolved to address this requirement, introducing new ways of designing highly parallel programs. Extending OpenMP to support task parallelism stands as a first step to improve the scalability of OpenMP applications on large-scale platforms. Indeed, task parallelism usually comes with lower runtime-related overhead than thread-based approaches, allowing OpenMP programmers to create a large amount of tasks at low cost. Task parallelism also promotes the runtime system to a central role, as having more units of work to execute requires smarter scheduling decisions and load balancing capabilities.

OpenMP was recently extended to support task dependencies. Instead of explicitly synchronizing all the tasks of a parallel region at once, the application programmer can now specify a list of variables a task will read as input or write as output instead. This information is transmitted to the task scheduling runtime system. The runtime then marks a task as ready for execution only once all its dependencies have been resolved. Dependencies therefore provide a way to define finer synchronizations between tasks, able to scale better than global synchronizations on large-scale platforms. Dependencies also give the runtime system more options to efficiently schedule tasks, as these become ready for execution as soon as the data they access has been updated.

As promising as it looks however, any new feature needs proper evaluation to encourage application programmers to embrace it. While several compilers and runtime systems are now beginning to support OpenMP 4.0 task dependencies, no benchmark suite currently exists to evaluate their respective benefits and compare them to traditional task parallelism.

This paper highlights two major contributions. We first introduce a new benchmark suite to experiment with OpenMP 4.0 task dependencies. We present performance results for both the GCC/libGOMP and the CLANG 1 /libIOMP compilers and their runtime systems, comparing kernels involving either dependent or independent tasks. Secondly, we comment on the issues we met while implementing these benchmarks along the lines of current 4.0 revision of the OpenMP specification. Building on this experience, we contribute some extension proposals to the existing OpenMP specification, to improve the expressiveness of the task dependency support.

The remainder of this paper is organized as follows. Section 2 describes the task dependency programming model in OpenMP 4.0. It then analyzes the strategies adopted by GCC/libGOMP and CLANG/libIOMP to implement this model. Section 3 introduces the KASTORS benchmark suite we have designed to evaluate OpenMP 4.0's task model implementations. Section 4 presents the performance results of KASTORS using two different hardware configurations. We identify and discuss practical issues with the current OpenMP specification, and we propose extensions in section 5 to address these issues. We finally present some related works in section 6 before concluding.

The way OpenMP specifies dependencies between tasks

The OpenMP Architecture Review Board recently introduced a new way of expressing task parallelism using OpenMP, through the task dependencies extension that comes with revision 4.0 of the specification. This section gives some insight into how programmers can use task dependencies to advantageously replace the often excessive global task synchronizations found in many OpenMP 3.0 applications. We also study the way the development teams of GCC/libGOMP and CLANG/libIOMP choose to implement this new OpenMP task model within their compilers and associated runtime systems. either in, out or inout whether the corresponding variable is respectively read as input, written as output or both read and written by the considered task. This information is then processed by the underlying runtime system to decide whether a task is ready for execution or should first wait for the completion of other ones.

Task dependencies by the example

Listing 1.1 shows the implementation of a LU factorization. It is inspired by the SparseLU kernel from the BOTS [START_REF] Duran | Barcelona openmp tasks suite: A set of benchmarks targeting the exploitation of task parallelism in openmp[END_REF] benchmark suite, which generates OpenMP independent tasks. The matrix being factorized is divided into a set of smaller sub-matrices on which are applied three computation kernels, called fwd, bdiv and bmod. At iteration k, the update of sub-matrix (i,j) by the bmod function requires an update of both sub-matrices (k,j) and (i,k) from the fwd and bdiv functions respectively. For each iteration, we make sure no bmod task starts executing before tasks fwd and bdiv have completed using the broad range, explicit taskwait synchronization keyword on line 11. This keyword indiscriminately waits for the completion of every task created by the parallel section so far.

While respecting the algorithm semantics, this solution limits the potential parallelism that can be generated out of such an application. Listing 1.2 shows the same algorithm implemented with OpenMP task dependencies. Instead of waiting for the termination of all previous tasks before executing bmod tasks, we specify dependencies to make sure bmod tasks can execute as soon as the data they access has been updated by the corresponding fwd and bdiv tasks. Running this depend version of the program leads to the creation of a dependency graph. When an OpenMP thread turns idle, the runtime system browses this graph to decide which task should be executed next, according to tasks' current state and resolved dependencies.

Task dependency support comes with several benefits. First, task dependencies involve decentralized, selective synchronization operations that should scale better than the broad-range taskwait-based approaches. In some situations, this way of program-ming unlocks more valid execution scenarios than explicitly synchronized tasks, which provides the runtime system with many more valid task schedules to choose from. For example, many instances of the fwd, bdiv and bmod computations can legally run concurrently with the version of the LU factorization expressing task dependencies. On the contrary, this level of concurrence is not possible with the taskwait version because the lack of accurate dependency information leads to an over-conservative synchronization scheme. As an added benefit, information about task dependencies also enables the runtime system to optimize further, such as improving task and data placement on NUMA systems.

In expressing dependencies, the programmer needs to strike the right balance however. Indeed, dependencies expressed too coarsely might limit the amount of available parallelism. On the other hand, defining fine-grain dependencies may increase runtimerelated overheads, depending on the way the underlying runtime system keeps track of the variables set inside a depend clause and the method it uses to enforce dependencies.

Maturity of compiler support

Both the GCC (4.9) and CLANG2 compilers now support most of the functionalities of OpenMP 4.0. The GNU libGOMP runtime system is responsible for executing OpenMP applications compiled with GCC, while the CLANG compiler generates calls to the Intel libIOMP library. Please note that support for OpenMP 4.0 dependent tasks is still very recent in these compilers at the time of this writing. GCC 4.9 was released on April 22, 2014. The CLANG branch with Intel OpenMP support is under active development. However, even though both compilers are still maturing their support for OpenMP dependent tasks, the tests that we conducted and that we present in Section 4 show that the OpenMP dependent task support in these compilers already favorably compares to the legacy independent task support.

Compiler support for the "depend" clause The GCC 4.9 compiler stores the entire list of dependencies into a void ** array. This array is passed as argument to the GOMP_task function call generated out of a #pragma omp task directive. It contains the addresses of all the variables referenced in the depend clause.

The Clang 3.4 compiler also generates a list out of the depend clause, and passes it to the __kmpc_omp_task_with_deps runtime function. This structure stores the addresses of all the variables described inside the depend clause, as well the length and flags of associated dependencies.

Runtime support for task dependencies The libGOMP library that comes with GCC 4.9 uses two data structures to manage task dependencies. The first data structure is the depend variable list generated by the compiler for the newly created task, as mentioned above. The second data structure is a hashtable located in the parent of the created task, which keeps track of all the pending dependencies between all the already created child tasks of the parent task. Upon creating the new child task, the runtime walks the list of depend variables and looks every variable up in the pending dependency table. If any unresolved dependency is found, the task creation enter the deferred path. Otherwise, the task is fully instantiated immediately.

The libIOMP used with Clang 3.4 has a very similar approach. Each parent task maintains a hashtable containing the pending dependencies for its children tasks. If a newly created task is found clear of any pending dependency, the __kmpc_omp_task_with_deps runtime function immediately instantiates it by calling the __kmpc_omp_task function. Otherwise, the new task is added as a successor to all tasks from which it expects some data, and the __kmpc_omp_task_with_deps function returns a code indicating that the new task has not yet been queued. The waiting new task will subsequently be woken up upon completion of its last predecessor.

The KASTORS suite overview

We designed the KASTORS benchmark suite to evaluate implementations of the OpenMP dependent task paradigm, introduced as part of the OpenMP 4.0 specification [START_REF]OpenMP application program interface version 4[END_REF]. This section introduces the different benchmarks and describes how we extended them to express task dependencies.

Cholesky and QR decompositions from PLASMA The PLASMA [START_REF] Kurzak | Multithreading in the PLASMA Library[END_REF] library developed at ICL/UTK provides a large number of key linear algebra algorithms optimized for multi-core architectures. Several implementations of each algorithm are available, using either static or dynamic scheduling. Dynamic scheduled algorithms are built on top of the QUARK [START_REF] Yarkhan | Quark users' guide: Queueing and runtime for kernels[END_REF] runtime system, which uses a data-flow dependency model to schedule tasks. The two algorithms we selected are a Cholesky decomposition and a QR decomposition, respectively known as DPOTRF and DGEQRF in PLASMA, which all operate on double precision floating point matrices (double type). The initial implementation uses multiple levels of wrappers, packing and unpacking parameters at each level, which affects the readability of algorithms and can be error prone. Listings 1.3 and 1.4 show the initial dynamic version and the transformations we made for the OpenMP 4.0 port respectively. On the original version the wrapper_blas_function performs parameters unpacking before calling the actual BLAS/LAPACK routines it is built on. The OpenMP 4.0 modification led to the removal of multiple wrapper levels, thus improving code readability and maintainability, and removing the need for such parameter management.

Poisson2D This algorithm solves the Poisson equation on the unit square [0,1]x[0,1], which is divided into a grid of NxN evenly-spaced points. This benchmark relies on a 5-point 2D stencil computational kernel that is repeatedly applied until convergence is detected. We implemented two main blocked versions of this kernel, using either independent tasks and tasks with dependencies.

SparseLU This benchmark computes the LU decomposition of a sparse matrix. We modified the original BOTS implementation to express task dependencies like described on listings 1.1 and 1.2, except only non-NULL blocks are updated to adapt the traditional LU decomposition to sparse matrices.

Strassen The Strassen algorithm uses matrix decompositions to compute the multiplication of large dense matrices. Similarly to SparseLU, we modified the BOTS implementation to add parallelism to the addition part of the algorithm and express task dependencies instead of using taskwait-based synchronizations.

Performance Evaluation

All experiments were performed with the libGOMP library distributed with GCC 4.9 (git-mirror commit 6ed3847ffd0), and the libIOMP library distributed with clang-omp 3.4 (llvm commit 233b1e3f034, clang-omp commit 7580e521e51f).We conducted our experiments on two different NUMA configurations.

The first one holds 8 AMD Magny Cours processors for a total of 48 cores. Each core has access to 64 KB of L1 cache, 512 KB of L2 cache. Both L1 and L2 caches are private, while L3 cache is shared between the 6 cores of a processor. This configuration provides a total of 256 GB (32 GB per NUMA node) of main memory. We will refer to this configuration as AMD48.

The second one holds 4 Intel Xeon E5-4620 processors for a total of 32 cores. Each core has access to 64 KB of L1 cache, 256 KB of L2 cache. Both L1 and L2 caches are private, while L3 cache is shared between the 8 cores of a processor. This configuration provides a total of 380 GB (95 GB per NUMA node) of main memory. We will refer to this configuration as INTEL32.

Plasma The DPOTRF and DGEQRF algorithms from Plasma rely on the BLAS library. We used different versions of optimized BLAS depending on the machine: ATLAS 3.10.1 was used on INTEL32, and ATLAS 3. were conducted using the maximum number of CPUs for each machine. The performance results are expressed in gigaflops (the higher the better), from an average of 10 runs, with an average standard deviation of 2 Gflops.

We compared four versions of these algorithms: The original PLASMA implementation with static scheduling (Plasma), the dynamic scheduling implementation on top of Quark runtime (Plasma-Quark) and two KASTORS OpenMP versions compiled with GCC/libGOMP (GCC-OMP) and CLANG/libIOMP (Clang-OMP), respectively. Each version was run on the following matrix size (M) / block size (B) couples: (2048 / 128), (4096 / 128), (8192 / 224).

Fig. 3: Poisson 2D

For both algorithms the results are positive: On both machines the OpenMP versions compete with the original versions. In several cases, the Clang-OMP version even leads by a slight margin. The overall good results of the original static version can be explained by the fact that it does not have to pay the overhead of task creation. One can also notice that QUARK-based versions always are slightly slower than both CLANG and GCC implementations for small matrix sizes, which leads to the conclusion that the libGOMP and libIOMP runtimes induce less overhead and provide a better handling of fine-grain tasks than QUARK. The conclusion is encouraging, as we were able to get similar or better performance results using a portable OpenMP-based approach than with a specifically designed runtime.

Poisson2D

The results are shown in figure 3 and the corresponding sequential times are reported in table 1. The speedup of both independent tasks and dependent tasks versions are low: Less than 14 on AMD48 and 6 on INTEL32. The application is memory bound with about the same number of arithmetic operations per load and store. The Poisson2D code is an iterative computation in which tasks are created at each time-step to update the sub domain of the initial grid. One of the important problem is that tasks are not bound to resources in order to take data locality into account. Typical scenario is that tasks between successive iterations may be performed by different threads of the same Fig. 5: Strassen parallel region. Neither the CLANG or the GCC runtime tries to schedule tasks in order to maximize data reuse. Moreover, tasks that access to same data (due to sharing of frontiers between two sub-domains) may be better scheduled if they are mapped to cores on the same NUMA node. It is challenging for OpenMP runtime developers to take data dependencies into account in order to better schedule tasks to improve data locality.

SparseLU For this benchmark we used two matrices and sub-matrices sizes : 128x64 and 64x128. Speed up were measured from an average of 10 runs, with an average standard deviation of 0.5. Results are shown on Figure 4 and reference sequential times are listed in Table 1.

For every tested configuration, the dependent task version outperforms the independent task version for both compilers. The best speed up is achieved using the 64x128 configuration. The OpenMP 4.0 version using dependencies performs slightly better in most cases because it is able to exploit inter-iteration parallelism. The version using independent tasks cannot exploit it, because of the global synchronization steps (see listings 1.1 and 1.2). It is therefore unable to provide enough parallelism to fully benefit from the available number of cores. This confirms that using data-flow dependencies can lead to a better use of CPUs.

Strassen The Strassen matrix multiplication is typically performed in 3 steps: a matrix add, a matrix multiply and a matrix add again. The most expensive part is the multiply, but the first adds are not negligible. Thus we define dependences between these two parts. We apply a recurse cutoff of 5, and for matrix smaller than 128x128, multiplies are computed with the usual algorithm instead of Strassen. Experiments were made using two matrix/blocksize combinations: 8192/128, 16384/128. Speed up were measured from an average of 10 runs. Results are shown on Figure 5 and reference sequential times are listed on Table 1. The dependent task version very slightly outperforms the independent task version for both compilers on most test cases. We can also notice that these fine-grain dependency expressions are at the bleeding-edge of the OpenMP 4.0 implementation for both GCC and Clang, as some finer dependencies are not yet supported by these compilers.

The general conclusion of these experiments with early implementations of the new OpenMP 4.0's data-flow paradigm is that there is little reason not to make use of it for the benchmarked codes. Under the large majority of the cases tested, the new paradigm incurs no performance regression. Moreover, the finer-grain synchronization scheme it provides is able to deliver more parallelism to feed large multicore configurations, usually leading to better performance results.

5 Extending OpenMP dependency expressiveness 5.1 Enabling reductions for OpenMP tasking: the cumulative-write mode OpenMP supports reduction for several directives such as section, parallel and for. Since the introduction of task-based programming within OpenMP 3.0, programs increasingly use loops to generate tasks, instead of performing computations directly within an omp for loop. OpenMP 4.0's task dependencies should strengthen this tendency even further, to enable more load-balancing flexibility. Unfortunately, the reduction clause is not available for the omp task directive, nor any alternative mechanism, leaving programmers to build it by themselves.

The approach we propose is to extend the set of in,out and inout data access modes with a new cumulative-write mode cw. This new mode indicates that several tasks may contribute to a piece of data in any order (but not simultaneously). It is inspired by the reduction support implemented in runtime system Kaapi [START_REF] Gautier | Kaapi: a thread scheduling runtime system for data flow computations on cluster of multi-processors[END_REF]. One might suggest to use the existing inout mode instead. However, the inout mode imposes a strong ordering between tasks, that proves to be unnecessary in that case. The following example illustrates this idea with a modified version of the LU decomposition code from Fig. 1.2. Using a cumulative write mode cw for the bmod computation (line 23) breaks the strong inter-iteration dependency that was caused by the inout mode, thus enabling more parallelism. On the next input or inout dependency, or at the next synchronization point (taskwait, explicit or implicit barrier), the runtime ensures that variables previously accessed using the cw mode may then be read. The reduction operator can be a pre-defined operators or a user defined reduction operator such as introduced with OpenMP-4.0. We plan to extend reduction operators to enable non-commutative operators as well (such as appends on a string or matrix multiplication) such as in [START_REF] Gautier | Kaapi: a thread scheduling runtime system for data flow computations on cluster of multi-processors[END_REF] or [START_REF] Augonnet | StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures[END_REF].

Expressing dependencies on non-contiguous memory areas

OpenMP 4.0 makes it possible to express task dependencies on the slice of an array, by specifying the offset and the length of the dependent slice. These slices specifications can be chained to express dependencies on 2D-subarrays. Chained array slices are available only for constant arrays and variable length arrays, however. The lack of leading dimension information makes them impractical for pointers, which strongly limits their interest. Temporarily copying data to constant arrays is tedious and time consuming. Variable length arrays on the other hand, are passed by value (copy) from a function to another, and only integrated the C language standard since C99. However, VLA is an optional feature in C11. A possible workaround could be to cast the pointer to a variable length array or constant array, such as this: This solution is not very much elegant, however. Our proposal is thus to extend the slice syntax to enable the specification of the missing leading dimension information. Following this extension, 2D sub-arrays may be specified such as this: OpenMP benchmarks To the best of our knowledge, KASTORS is the only benchmark suite focusing on OpenMP task dependencies. This section describes existing benchmarks evaluating other aspects of the OpenMP specification.

The Barcelona OpenMP Tasks Suite [START_REF] Duran | Barcelona openmp tasks suite: A set of benchmarks targeting the exploitation of task parallelism in openmp[END_REF] evaluates the addition of tasking to the OpenMP 3.0 specification, comparing several ways of generating tasks out of small computing kernels. We adapted two of these kernels, SparseLU and Strassen, to express task dependencies, and we added the modified versions to our KASTORS suite.

Older OpenMP benchmark suites such as PARSEC [START_REF] Bienia | Benchmarking Modern Multiprocessors[END_REF], SPECOMP [START_REF] Müller | Spec omp2012 -an application benchmark suite for parallel systems using openmp[END_REF] and Rodinia [START_REF] Che | A characterization of the rodinia benchmark suite with comparison to contemporary cmp workloads[END_REF] could be extended to benefit from task parallelism, as well as the NAS Parallel Benchmark suite [START_REF] Bailey | The NAS Parallel Benchmarks[END_REF] (NPB). NPB was originally introduced to evaluate the performance of parallel supercomputers. It was later extended to provide OpenMP 2.5 compatible versions of most kernels. We consider modifying some of them to exploit task parallelism, especially the "multi-zone" ones [START_REF] Jin | Performance characteristics of the multi-zone nas parallel benchmarks[END_REF] involving nested parallelism.

Compilers and runtime systems supporting task dependencies KAAPI [START_REF] Gautier | Kaapi: a thread scheduling runtime system for data flow computations on cluster of multi-processors[END_REF] 3 , StarPU [1]4 , Quark [START_REF] Yarkhan | Quark users' guide: Queueing and runtime for kernels[END_REF] and OMPSs [START_REF] Duran | Ompss: a proposal for programming heterogeneous multi-core architectures[END_REF] are libraries that support task dependencies in a different context than OpenMP. We present them here focusing on the different access modes they propose, and the way application programmers can provide task dependencies using these libraries.

The KAAPI and StarPU runtime systems were designed to improve the performance of task-based parallel applications on large-scale heterogeneous platforms. Unlike the current OpenMP specification, KAAPI and StarPU support the expression of dependencies on multi-dimensional arrays. StarPU provides ways of splitting a data with user-defined filters that can help to express dependencies on sub-matrices, for example. The Quark runtime system that comes with the PLASMA library is responsible for executing tasks created out of BLAS operators in a dynamic way. Unlike KAAPI and StarPU, Quark only considers unidimensional arrays, but comes with an original scratch access mode to reuse thread-specific temporary data.

OMPSs [START_REF] Duran | Ompss: a proposal for programming heterogeneous multi-core architectures[END_REF] is a programming model inspired by OpenMP with specific directives to support task dependencies and heterogeneity. The OMPSs programming model includes the concurrent clause to express that tasks will perform reductions on the listed variables. Similar access-modes also exist in KAAPI and StarPU.

Conclusion

The introduction of task dependencies in the revision 4.0 of the OpenMP specification provides application programmers with a new, powerful way of describing synchronizations in task-based parallel applications. OpenMP compilers and runtime systems will play a key role in the adoption of such a new feature by the community, as they are responsible for tracking and resolving variable dependencies before executing tasks.

The performance of OpenMP applications expressing task dependencies will be closely related to how efficiently compilers and runtime systems implement this new feature.

We introduced a new benchmark suite, called KASTORS, composed with small kernels ported on the OpenMP dependent task model. We then compared their performance with taskwait-based versions of the same kernels for both the GCC/libGOMP and the CLANG/libIOMP compilers and runtime systems. While the support for task dependencies in these compilers is still very recent, experiments run on two different hardware configurations show that the versions with task dependencies offer performances comparable and sometimes better to taskwait-based versions on most kernels. The results obtained by rewriting some PLASMA kernels to use OpenMP task dependencies also demonstrated that this model even outperforms dedicated data-flow solutions in some situations, while improving portability.

In the near future, we plan to extend the KASTORS suite with new benchmarks coming from either modified versions of existing benchmarks or small kernels inspired from real-life scientific applications. Based on CLANG, we are also developing a source-to-source compiler that generates direct calls to the KAAPI or StarPU runtime systems out of C/C++ OpenMP programs. We are currently working on releasing this compiler with a full support of the extensions proposed in section 5.

OpenMP 4 . 11 for

 411 0 introduces the depend keyword to specify the access mode of each shared variable a task will access during its execution. Access modes can be set to Listing 1.1: LU with independent tasks for (k=0; k<NB; k++) { lu0(M[k * NB+k]); for (j=k+1; j<NB; j++) #pragma omp task untied shared(M) fwd(M[k * NB+k], M[k * NB+j]); for (i=k+1; i<NB; i++) #pragma omp task untied shared(M) bdiv(M[k * NB+k], M[i * NB+k]); #pragma omp taskwait for (i=k+1; i<NB; i++) for (j=k+1; j<NB; j++) #pragma omp task untied shared(M) bmod(M[i * NB+k], M[k * NB+j], M[i * NB+j]); #pragma omp taskwait } Listing 1.2: LU with task dependencies 1 for (k=0; k<NB; k++) { 2 #pragma omp task untied shared(M)\ 3 depend(inout: M[k * NB+k:BS * BS]) 4 lu0(M[k * NB+k]); 5 for (j=k+1; j<NB; j++) 6 #pragma omp task untied shared(M)\ 7 depend(in: M[k * NB+k:BS * BS])\ 8 depend(inout: M[k * NB+j:BS * BS]) 9 fwd(M[k * NB+k], M[k * NB+j]); 10 (i=k+1; i<NB; i++) 12 #pragma omp task untied shared(M)\ 13 depend(in: M[k * NB+k:BS * BS])\ 14 depend(inout: M[i * NB+k:BS * BS]) 15 bdiv(M[k * NB+k], M[i * NB+k]); 16 17 for (i=k+1; i<NB; i++) 18 for (j=k+1; j<NB; j++) 19 #pragma omp task untied shared(M)\ 20 depend(in: M[i * NB+k:BS * BS])\ 21 depend(in: M[k * NB+j:BS * BS])\ 22 depend(inout: M[i * NB+j:BS * BS]) 23 bmod(M[i * NB+k],M[k * NB+j],M[i * NB+j]); 24 }

Fig. 2 :

 2 Fig. 1: Plasma on AMD48

  Fig. 4: SparseLU

#

  pragma omp task untied shared(M) \ depend(in: M[i * NB+k:BS * BS]) \ depend(in: M[k * MSIZE+j:BS * BS]) \ depend(cw: M[i * NB+j:BS * BS]) bmod(M[i * NB+k], M[k * NB+j], M[i * NB+j]);

#

  pragma omp task depend(inout:array[offset1:length1][offset2:length2]) blas_function(...);

  double * f_ = malloc(NX * NY * sizeof(double)); double ( * f)[NX][NY] = (double ( * )[NX][NY])f_; #pragma omp task depend(inout:f[offset1:length1][offset2:length2]) blas_function(...); free(f_);

  double * f = malloc(NX * NY * sizeof(double)); #pragma omp task depend(inout:f[offset1:length1:NX][offset2:length2]) blas_function(...); free(f);

Table 1 :

 1 Sequential Poisson2D, Strassen and SparseLU execution time (s).

			Platform Compiler Poisson2D	SparseLU	Strassen
				8192 16384 128x64 64x128 4096 8192
			AMD48 GCC 5.28 21.34 97.74 94.36 38.35 269.93
			AMD48 CLANG 5.42 21.66 99.34 95.08 32.92 234.16
			INTEL32 GCC 1.64 6.53 77.88 71.97 25.32 180.11
			INTEL32 CLANG 1.77 6.79 76.74 71.58 20.12 142.54
				Poisson2D
		35 40 45		GCC task GCC task-dep Clang task Clang task-dep
	Speed up	20 25 30
		15
		10
		5
		0	8192 AMD48	16384	8192 INTEL32 16384

Intel branch with support for OpenMP: http://clang-omp.github.io/

In this article, we designate as "CLANG" the branch developed and maintained by Intel to integrate OpenMP support into the CLANG compiler. This branch is available there: http: //clang-omp.github.io/.

http://kaapi.gforge.inria.fr

http://starpu.gforge.inria.fr

Acknowledgments

This work has been partially supported by the INRIA ADT K'STAR Project, the ANR-11-BS02-013 HPAC Project and the IRSES2011-295217 HPC-GA Project.


Ahmad Assaf

Ghislain A Atemezing

Raphaël Troncy

Elena Cabrio
email: <elena.cabrio@inria.fr>

What are the Important Properties of an Entity? Comparing Users and Knowledge Graph Point of View

Keywords: Entities, Google Knowledge Graph, visualization, knowledge extraction

Entities play a key role in knowledge bases in general and in the Web of Data in particular. Entities are generally described with a lot of properties, this is the case for DBpedia. It is, however, difficult to assess which ones are more "important" than others for particular tasks such as visualizing the key facts of an entity or filtering out the ones which will yield better instance matching. In this paper, we perform a reverse engineering of the Google Knowledge graph panel to find out what are the most "important" properties for an entity according to Google. We compare these results with a survey we conducted on 152 users. We finally show how we can represent and explicit this knowledge using the Fresnel vocabulary.

Introduction

In many knowledge bases, entities are described with numerous properties. However, not all properties have the same importance. Some properties are considered as keys for performing instance matching tasks while other properties are generally chosen for quickly providing a summary of the key facts attached to an entity. Our motivation is to provide a method enabling to select what properties should be used when depicting the summary of an entity, for example in a multimedia question answering system such as QakisMedia3 or in a second screen application providing more information about a particular TV program 4 .

Our approach consists in: (i) reverse engineering the Google Knowledge Panel by extracting the properties that Google considers as sufficiently important to show (Section 2), and (ii) analyzing users' preferences by conducting a user survey and comparing the results (Section 3). We finally show how we can explicitly represent this knowledge of preferred properties to attach to an entity using the Fresnel vocabulary before concluding (Section 4).

Reverse Engineering the Google KG Panel

Web scraping is a technique for extracting data from Web pages. We aim at capturing the properties depicted in the Google Knowledge Panel (GKP) that are injected in search result pages [START_REF] Bergman | Deconstructing the Google Knowledge Graph[END_REF]. We have developed a Node.js application that queries all DBpedia concepts that have at least one instance which is owl:sameAs with a Freebase resource in order to increase the probability that the search engine result page (SERP) for this resource will contain a GKP. We assume in our experiment that the properties displayed for an entity are "entity type dependent" and that context (country, query, time, etc) can affect the results. Moreover, we filter out generic concepts by excluding those who are direct subclasses of owl:Thing since they will trigger ambiguous queries. We obtained a list of 352 concepts 5 .

For each of these concepts, we retrieve n instances 6 . For each of these instances, we issue a search query to Google containing the instance label. Google does not serve the GKP for all user agents and we had to mimic a browser behavior by setting the U ser -Agent to a particular browser. We use CSS selectors to extract data from a GKP. An example of a query selector is . om (all elements with class name om) which returns the property DOM element(s) for the concept described in the GKP. From our experiments, we found out that we do not always get a GKP in a SERP. If this happens, we disambiguate the instance by issuing a new query with the concept type attached. However, if no GKP was found again, we capture that for manual inspection later on. Listing 1 gives the high level algorithm for extracting the GKP. The full implementation can be found at https://github.com/ahmadassaf/KBE.

Algorithm 1 Google Knowledge Panel reverse engineering Algorithm

Evaluation

We conducted a user survey in order to compare what users think should be the important properties to display for a particular entity and what the GKP shows.

User survey. We set up a survey7 on February 25th, 2014 and for three weeks in order to collect the preferences of users in term of the properties they would like to be shown for a particular entity. We select one representative entity for nine classes: TennisPlayer, Museum, Politician, Company, Country, City, Film, SoccerClub and Book. 152 participants have provided answers, 72% from academia, 20% coming from the industry and 8% having not declared their affiliation. 94% of the respondents have heard about the Semantic Web while 35% were not familiar with specific visualization tools. The detailed results8 show the ranking of the top properties for each entity. We only keep the properties having received at least 10% votes for comparing with the properties depicted in a KGP. Hence, users do not seem to be interested in the INSEE code identifying a French city while they expect to see the population or the points of interest of this city.

Comparison with the Knowledge Graphs. The results of the Google Knowledge Panel (GKP) extraction9 clearly show a long tail distribution of the properties depicted by Google, with a top N properties (N being 4, 5 or 6 depending on the entity) counting for 98% of the properties shown for this type. We compare those properties with the ones revealed by the user study. Table 1 shows the agreement between the users and the choices made by Google in the GKP for the 9 classes. The highest agreement concerns the type Museum (66.97%) while the lowest one is for the TennisPlayer (20%) concept. We think properties for museums or Books are more stable (no many variety) while for entities categories of Person/Agent, they change a lot according to the status, the function, etc. And so more subjective. With this set of 9 concepts, we are covering 301, 189 DBpedia entities that have an existence in Freebase, and for each of them, we can now empirically define the most important properties when there is an agreement between one of the biggest knowledge base (Google) and users preferences.

Modeling the preferred properties with

Conclusion and Future Work

We have shown that it is possible to reveal what are the "important" properties of entities in a large knowledge base by reverse engineering the choices made by Google when creating knowledge graph panels and by comparing with users preferences obtained from a user survey. Our motivation is to represent this choice explicitly, using the Fresnel vocabulary, so that any application could just read this configuration file for deciding which properties of an entity is worth to visualize. This is fundamentally different from the work in [START_REF] Steiner | SEKI@home or Crowdsourcing an Open Knowledge Graph[END_REF] where the authors created a generalizable approach to open up closed knowledge bases like Google's by means of crowd-sourcing the knowledge extraction task. We are aware that this knowledge is highly dynamic, the Google Knowledge Graph panel differing from countries and varying along the time. We have provided the code that enables to perform new calculation at run time and we aim to study the temporal evolution of what are important properties on a longer period. This knowledge which has been captured will be made available shortly in a SPARQL endpoint. We are also investigating the use of Mechanical Turk to perform a larger survey for the complete set of DBpedia classes.

1 :

 1 INITIALIZE equivalentClasses(DBpedia, F reebase) AS vectorClasses 2: Upload vectorClasses for querying processing 3: Set n AS number-of-instances-to-query 4: for each conceptT ype ∈ vectorClasses do 5:

		SELECT n instances
	6:	listInstances ← SELECT-SPARQL(conceptT ype, n)
	7:	for each instance ∈ listInstances do
	8:	CALL http://www.google.com/search?q=instance
	9:	if knowledgeP anel exists then
	10:	SCRAP GOOGLE KNOWLEDGE PANEL
	11:	else
	12:	CALL http://www.google.com/search?q=instance + conceptT ype
	13:	SCRAP GOOGLE KNOWLEDGE PANEL
	14:	end if
	15:	gkpP roperties ← GetData(DOM, EXIST(GKP))
	16:	end for
	17:	COMPUTE ocurrences for each prop ∈ gkpP roperties
	18: end for
	19: return gkpP roperties
	5 SPARQL query: http://goo.gl/EYuGm1
	6 In our experiment, n was equal to 100 random instances

Table 1 .

 1 Agreement on properties between the users and the Knowledge Graph Panel

	Classes TennisPlayer Museum Politician Company Country City Film SoccerClub Book
	Agr.	20%	66.97%	50%	40%	60% 60% 60%	50%	60%

  Fresnel. Fresnel 10 is a presentation vocabulary for displaying RDF data. It specifies what information contained in an RDF graph should be presented with the core concept fresnel:Lens[START_REF] Pietriga | Fresnel: A Browser-Independent Presentation Vocabulary for RDF[END_REF]. We use the Fresnel and PROV-O ontologies 11 to explicitly represent what properties should be depicted when displaying an entity.

	:tennisPlayerGKPDefaultLens rdf:type fresnel:Lens ;
	fresnel:purpose fresnel:defaultLens ;
	fresnel:classLensDomain dbpedia-owl:TennisPlayer ;
	fresnel:group :tennisPlayerGroup ;
	fresnel:showProperties (dbpedia-owl:abstract dbpedia-owl:birthDate
	dbpedia-owl:birthPlace dbpprop:height dbpprop:weight
	dbpprop:turnedpro dbpprop:siblings) ;
	prov:wasDerivedFrom
	<http://www.google.com/insidesearch/features/search/knowledge.html> .

http://qakis.org/

http://www.linkedtv.eu/demos/linkednews/

The survey is at http://eSurv.org?u=entityviz

https://github.com/ahmadassaf/KBE/blob/master/results/ agreement-gkp-users.xls

https://github.com/ahmadassaf/KBE/blob/master/results/survey.json

Acknowledgments. This work has been partially supported by the ANR Datalift (ANR-10-CORD-009) and UCN (ANR-11-LABX-0031-01) projects.


Alain Angora
email: ette-alain.angora@unilim.fr

Isabelle Distinguin
email: isabelle.distinguin@unilim.fr

Clovis Rugemintwari
email: clovis.rugemintwari@unilim.fr

A Note on Bank Capital Buffer: Does Bank Heterogeneity matter?

Keywords: bank capital buffer, prudential regulation, Basel accords JEL Classification Numbers: G21, G28, G32

The objective of this paper is to extend the literature on bank capital buffer by considering the role of bank heterogeneity. Using a sample of European commercial banks over 1992-2006, we show that four key determinantsrisk, business cycle, market and peer disciplinehave different impact on capital buffer depending on banks' financing mode, activity or size. Our results offer a framework for discussing the appropriateness of the still on-going suggestions on bank capital regulation. Whereas they support the differentiating measures undertaken in Basel 3 such as specific capital surcharges for SIFIs, they disagree with the adoption of uniform countercyclical buffers.

Introduction

Different studies deal with the determinants of bank capital buffer. They mainly focus on the relationship between a given factor and the buffer by controlling for its other potential determinants (Lindquist (2004), [START_REF] Jokipii | The cyclical behaviour of European bank capital buffers[END_REF], Fonseca and Gonzalez (2010)). For example, [START_REF] Jokipii | The cyclical behaviour of European bank capital buffers[END_REF] and [START_REF] Ayuso | Are capital buffers pro-cyclical? Evidence from Spanish panel data[END_REF] 2 focus on the cyclical behavior of capital buffer. They show that the economic cycle (captured through the GDP) and capital buffer are negatively related. Nier and Baumann [2006] 3 examine the link between market discipline and banks' capital ratios. They mainly show that, ceteris paribus, stronger market discipline, taken into account via the portion of uninsured liabilities, leads to a higher capital ratio. [START_REF] Alfon | What determines how much capital is held by UK banks and building societies?[END_REF] 4 argue that regulatory environment, market discipline and risk management are the main determinants of the amount of capital held by banks.

However, all these studies consider all banks equally, or focus only on banking specialisation whereas banks have evolved towards the universal banking model, inducing a substantial heterogeneity in banks' activities even in the same banking specialisation. Banks mainly focused on traditional activities (loans supply and deposits collection) coexist with banks more involved in market activities. Similarly, large conglomerates coexist with small entities. We suspect that this heterogeneity may affect the determinants of capital buffer. Thus, we consider a set of European commercial banks over 1992-2006 and consider several sub-samples depending on three factors: bank activity type, financing mode and size. Indeed, European commercial banks are heterogeneous both in terms of size and balance sheet structure. However, the Basel capital constraint does not differentiate banks and seems almost set to fit banks turned towards traditional activities.

The main novelty of this paper lies in the fact that we consider the impact of the heterogeneity of banks' characteristics on the determinants of capital buffer. We assume that these determinants might differ depending on banks' size, activity and financing mode. Our hope is that our results might offer a framework for discussing the appropriateness of the still on-going suggestions on bank capital regulation. Concretely, according to our results, we might be able to judge whether the new Basel 3 measures such as the capital surcharge for Systemically Important Financial Institutions (SIFIs) or the prescription of a uniform countercyclical buffer for all banks are appropriate or not.

The rest of the paper is structured as follows. In section 2, we describe the method, the set of variables and the sample of banks. We present our results in section 3. Section 4 concludes the paper. 2 Jokipii and Milne [2008] use a sample of European banks from 1997 to 2004 and [START_REF] Ayuso | Are capital buffers pro-cyclical? Evidence from Spanish panel data[END_REF] consider Spanish banks from 1986 to 2000. 3 They use a substantial cross-country panel data of 32 countries from 1993 to 2000. 4 They consider British banks from 1997 Q2 to 2002 Q2.

Sample, method and variables

The sample consists of 742 commercial banks from 16 European countries5 over the period 1992-20066 . Accounting data for individual banks are obtained from Bankscope Fitch IBCA and we retain banks for which information about the total capital ratio7 is available.

Before taking into account bank heterogeneity, we derive the determinants of European banks' capital buffer by estimating the model defined below on the whole sample of banks. Subscripts i and t denote bank and period respectively.

                     (1)
The regression includes time (τ t ) and individual (η i ) fixed effects and standard errors are robust to heteroscedasticity. Following Lindquist ( 2004), we introduce one year lag in explanatory variables which are susceptible to be endogenous in order to avoid simultaneity problems.

Table 1 presents the definition of the variables, the expected sign and shows some descriptive statistics for our sample of banks. We can notice that it exhibits a relatively high level of heterogeneity. The capital buffer is on average 6.10 and we denote a high volatility of this buffer as the standard deviation is 6.29. Besides, we can see that the sample of banks presents high differences in terms of size, activity type, and financing mode. After studying the determinants of European banks' capital buffer in a general framework, we investigate whether they differ depending on banks' size and balance sheet structure. In this aim, we estimate our equation separately on different sub-samples constructed on the basis of the size of banks, the proportion of loans in total assets and that of customer deposits in total liabilities. We define six sub-samples on the basis of three criteria:

-Financing mode: banks heavily (slightly) relying on customer deposits are defined as those with a ratio customer deposits/total liabilities greater (lower) than its median value (55.01%)

-Credit activity: banks with a high (low) credit activity are defined as those with a ratio of net loans/total assets greater (lower) than its median value 11 (56.23%);

-Size: banks with total assets greater (lower) than one billion 12 Euros are considered as large (small) banks;

Results

First, we study the determinants of capital buffer on the whole sample of banks. The results are presented in column (1) of table 2. We can see that seven out of the ten independent variables are significant at the one percent level with associated coefficients presenting the expected sign. Like [START_REF] Jokipii | The cyclical behaviour of European bank capital buffers[END_REF], we find that the profit variable significantly and positively affects capital buffer. It appears that retained earnings are used by banks to increase their capital buffer. Our risk variable llpa which corresponds to the ratio of loan loss provisions to total assets is also highly significantly and positively related with capital buffer. This suggests that banks with greater expected losses raise capital buffer in order to reduce insolvency risk. Our indicators comp and uninsliab are highly significant and their coefficients are positive suggesting that European commercial banks are both disciplined by their peers and uninsured debtholders. This result is in line with those of Nier andBaumann (2006), Lindquist (2004) and [START_REF] Alfon | What determines how much capital is held by UK banks and building societies?[END_REF]. The loan demand variable loang is, as expected, negatively and significantly related to capital buffer indicating that high annual loan growth rate increases the capital requirement ratio and therefore reduces the bank capital buffer. This confirms the results of [START_REF] Ayuso | Are capital buffers pro-cyclical? Evidence from Spanish panel data[END_REF] and [START_REF] Jokipii | The cyclical behaviour of European bank capital buffers[END_REF]. Similarly, the ratio net loans/total assets (nla) is negatively related to capital buffer, like in Fonseca and Gonzalez (2010) and [START_REF] Jokipii | The cyclical behaviour of European bank capital buffers[END_REF], implying that banks more involved in credit activity have lower capital buffer. The size coefficient is significantly negative which gives support to the notion that large banks have lower capital buffer than small banks. This different behaviour may be explained by, among other things, the portfolio diversification and the economies of scale in screening and monitoring enjoyed by large banks which can allow them to operate with lower capital buffer. Thus, our general findings are in line with those obtained in the previous literature. However, we suspect that the high heterogeneity of European banks in terms of size, activities and financing mode might have an impact on the relationship between these traditional determinants and capital buffer that is why we estimate this relationship on different subsamples (columns 2-7 of Table 2).

11 For both financing mode and credit activity, we considered other criteria to separate banks. Banks with a low value of the considered ratio are defined as those with a ratio lower than the first quartile and banks with a high value of the considered ratio are defined as those with a ratio greater than the third quartile. The first quartile is 44.72% for net loans/ total assets and 39.52% for customer deposits/ total liabilities. The third quartile is 70.59% for net loans/ total assets and 73.01% for customer deposits/ total liabilities. Considering these criteria leads to the same conclusions. 12 This common criterion corresponds to the definition of large banks by Bankscope Fitch IBCA. This table shows estimation results obtained using the panel fixed effects method. The regression includes both time and individual fixed effects. Net loans/total assets is considered as high (low) if it is greater (lower) than the median value on the whole sample (56.23%). Customer deposits/total liabilities is considered as high (low) if it is greater (lower) than the median value on the whole sample (55.01%). Large (small) banks are those with total assets greater (lower) than one billion euros (Bankscope criterion).

Standard errors are adjusted robust to heteroscedasticity. ***, ** and * pertain to 1, 5 and 10% level of significance, respectively. T-stats are between parentheses.

Considering the results obtained on the different sub-samples, we can notice that the profitability (profit), the size of the bank (size), the importance of loans in total assets (nla) and loan demand (loang) are always significant determinants of capital buffer. Thus, the heterogeneity of banks does not affect the relevance of these variables.

However, we can notice several different behaviors for the other variables depending on banks' credit activity, financing mode 13 and size 14 .

More precisely, the variable reflecting credit risk (llpa) appears significant only for large banks and banks more involved in non traditional activities that is banks with low ratios of net loans/total assets and customer deposits/total liabilities. The significance of this variable implies that credit risk is not properly taken into account in the capital constraint and that these banks have a better assessment of this risk which leads to the building of capital buffers. This result suggests that the refinements of the capital constraint to better capture risk might have an impact on bank actual capital essentially for small banks and banks involved in traditional activities.

The market discipline variable, uninsliab, is significant at least at the five percent level with the expected positive coefficient only for banks more turned towards non traditional activities and small banks. This may reflect the fact that the Basel capital constraint does not correctly take into account risks related to non traditional activities and that uninsured debtholders, aware of these risks, exert a pressure on banks to hold capital buffer. Besides, the significance of this variable only for small banks may be interpreted as a Too Big To Fail effect: large banks are considered as Too Big To Fail by uninsured debtholders which have no incentive to discipline them. Thus, if market discipline is to be considered in complement to capital regulation, it might be effective only for banks not perceived as Too Big To Fail and those more involved in non traditional activities.

We also find a significant positive relationship between the buffer and the annual growth rate of the real gross domestic product (gdpg) only for small banks. This result shows that capital buffers co-move positively with the business cycle highlighting a forward-looking behaviour i.e. small banks tend to increase capital buffer during good times that should be drawn upon during bad times. Thus, prescribing a uniform countercyclical buffer for all banks does not appear appropriate.

Finally, the effectiveness of peer discipline (comp) varies with banks' financing mode. It is only significant for banks highly funded by deposits. Thus, it seems that the competition between banks to attract deposit funding is fierce and capital buffer may act as a signaling tool for these banks. 13 We ensure that the distinction between banks according to the importance of the ratio Net loans/ Total assets is not equivalent to the distinction according to the importance of the ratio Customer deposits/ Total Liabilities. Only 54.3% of banks with low Customer deposits/ Total Liabilities ratio are also banks with low Net loans/ Total assets ratio and 58,6% of banks with high Customer deposits/ Total Liabilities ratio are also banks with high Net loans/ Total assets ratio.

14 Similarly, we ensure that the distinction between banks according to the size is not equivalent to the distinctions made according to the importance of loans or customer deposits. 53.7% of large banks have a high Net loans/ Total assets ratio and 41.6% a high (Customer deposits/ Total Liabilities) ratio. 40.8% of small banks have a low Net loans/ Total assets ratio and 40.4% a low (Customer deposits/ Total Liabilities) ratio. Thus, our criteria to separate banks are not equivalent and do not lead to identical sub-samples.

Conclusion

In this paper, we study the determinants of bank capital buffer considering bank heterogeneity. We find that the impact on capital buffer of factors such as risk, market discipline and economic cycle, which have been the main focus of the previous literature, differs depending on banks' financing mode, activity or size. These results might offer a framework to appreciate the appropriateness of the still on-going suggestions on bank capital regulation. More precisely, to tackle the procyclical behaviour of the regulatory capital in banking, it has been decided -in what is now known as Basel 3-to require banks to hold a countercyclical buffer of a magnitude between 0 and 2.5 % of risk weighted assets whatever the size and the type of the bank (BCBS, 2010). However, as our results indicate, the capital buffer is already countercyclical for small banks. Consistent with our findings, we therefore argue that this new burden might be nuanced as small and large banks seem to build differently their capital buffer. In the same way, our results suggest that reliance on market discipline for large banks might be a bad option. Hence, we welcome the underway Basel 3 measures, such as the capital surcharge, directed specifically towards Systemically Important Financial Institutions (SIFIs).

,

Table 1 :

 1 Definition of the variables and summary descriptive statistics on 1992-2006.

	Variable	Mnemonic Definition	Mean	Standard deviation	Min	Max	Expected Sign
			((Tier 1+Tier 2	6.10	6.29	-7.90	33.70
	Capital buffer	buffer	capital)/Risk-weighted assets)-regulatory
			minimum requirements
	Profitability profit	Post tax profit/Total assets	0.66	1.09	-12.37	10.60	+
	Equity cost	roe	Net income/Equity 8	9.39	12.54	-99.81	98.45	-
	risk	llpa	Loan loss provisions/Total assets	0.54	0.67	0.00	6.58	-/+
	Off-balance sheet	obsa	Off-balance sheet/Total assets	23.75	28.70	0.00	236.44	+
	Market discipline	uninsliab	Total uninsured funding/Total liabilities	47.16	27.04	1.03	100.00	+
	Peer discipline	comp	Annual mean of the in the same country capital buffer of banks	6.10	1.97	0.10	14.15	+
	Size	size	Total assets (€ mil.) 9	36558.00 1.14*10 5	9.54	1.57*10 6 -
	Credit demand	loang	Annual net loan growth rate	13.56	28.94	-100.00	272.87	-
	Asset structure	nla	Net loans 10 /Total assets	54.66	22.33	0.00	98.86	-
	Economic cycle	gdpg	Annual growth rate of (deseasonalized) the real GDP	2.29	1.67	-3.97	15.43	-

Table 2 : Determinants of capital buffer taking into account bank heterogeneity

 2

	, i t buffer	0   	1 	, 1 i t profit			2	, 1 i t roe		3 llpa i t , 1   4 , 1 i t obsa 		5	, 1 i t comp 
		6	, 1 i t uninsliab  7 , 8 , 1 i t i t loang nla  		9	, i t size		10	gdpg	, i t	i    t	, i t u
						(1)			(2)			(3)	(4)	(5)	(6)	(7)
							(Net loans/	(Net loans/	(Customer	(Customer
						Whole	Total assets)	Total assets)	deposits/ Total	deposits/ Total
			Variables	sample			low			high	Liabilities) low	Liabilities) high	Large	Small
			C			50.424		62.036		33.325	64.153	21.458	41.289	44.592
					(15.746)*** (12.578)***		(7.434)***	(13.262)***	(3.886)***	(10.391)*** (5.646)***
			Profit		0.481			0.595			0.426	0.549	0.478	0.590	0.518
					(4.713)***		(3.267)***		(3.674)***	(3.715)***	(3.456)***	(4.097)***	(3.202)***
			Roe		-0.010		-0.0008		-0.024	-0.021	-0.034	-0.015	-0.044
					(-0.945)		(-0.045)		(-1.751)*	(-1.439)	(-1.819)*	(-1.276)	(-1.605)
			Llpa		0.389			0.675			0.221	0.435	-0.193	0.534	-0.187
					(2.752)***		(2.497)**		(1.487)	(2.125)**	(-0.936)	(2.870)***	(-0.768)
			Obsa		-0.002		0.00003		-0.006	0.0006	-0.007	0.003	-0.012
					(-0.807)		(0.009)		(-1.759)*	(0.178)	(-1.792)*	(1.332)	(-1.384)
			Comp		0.155			0.135			0.102	0.050	0.176	0.103	0.374
					(3.461)***		(1.848)*		(1.943)*	(0.844)	(2.585)***	(2.336)**	(2.672)***
			Uninsliab		0.024			0.062		-0.015	0.028	0.013	-0.0002	0.031
					(3.610)***		(5.331)***		(-1.931)*	(2.624)***	(1.196)	(-0.031)	(2.028)**
			Loang		-0.019		-0.017		-0.015	-0.016	-0.025	-0.014	-0.044
					(-7.314)*** (-4.846)***		(-4.484)***	(-5.588)***	(-5.4480)***	(-5.435)*** (-6.798)***
			Nla		-0.092		-0.093		-0.076	-0.079	-0.089	-0.082	-0.141
					(-12.246)*** (-6.419)***		(-7.567)***	(-7.931)***	(-7.620)***	(-10.313)*** (-8.321)***
			Size		-2.790		-3.593		-1.604	-3.588	-0.838	-2.061	-2.545
					(-13.444)*** (-11.644)***		(-5.331)***	(-12.333)***	(-2.182)**	(-8.434)*** (-4.013)***
			Gdpg		0.052			0.051		-0.014	0.022	0.101	-0.067	0.339
						(0.987)		(0.739)		(-0.178)	(0.309)	(1.316)	(-1.316)	(2.230)**
		Observations:		2874			1380			1493	1404	1462	1985	889
			R-squared:		0.824			0.867			0.818	0.870	0.839	0.782	0.858

Austria (19), Belgium (18), Denmark (65) Finland (11), France (147), Germany (28), Greece (18), Ireland (14),Italy (198), Netherlands (50), Norway (21), Portugal (20), Spain (31), Sweden (31), Switzerland (20), and United Kingdom (51). We notice that French and Italian banks are comparatively well represented in our sample. To make sure that our results do not depend on this unbalanced sample representation we ran, as a robustness check, all our regressions by excluding the banks from these two countries. Our conclusions remain unchanged.

Note that on the whole time period, banks are under the Basel I framework.

Total capital ratio is (Tier 1 + Tier 2)/ Risk weighted assets and is used to construct our dependent variable.

Notice that in our regressions, due to colinearity issues, the variable roe corresponds to the residuals of the regression of the Return on Equity on our profit variable.

In our regressions, we consider the natural logarithm of total assets.

Net loans are: gross loansloan loss reserves.


Philippe Marmottant
email: philippe.marmottant@ujf-grenoble.fr

Alexandre Ponomarenko

Diane Bienaimé

The walk and jump of Equisetum spores

Keywords: Equisetum, spores, locomotion, hygroscopic, elastic energy

Equisetum plants (horsetails) reproduce by producing tiny spherical spores that are typically 50 micrometers in diameter. The spores have four elaters, which are flexible ribbonlike appendages that are initially wrapped around the main spore body, and that deploy upon drying or fold back in humid air. If elaters are believed to help dispersal, the exact mechanism for spore motion remains unclear in the literature. In this manuscript we present observations of the 'walks' and 'jumps' of Equisetum spores, which are novel types of spore locomotion mechanisms compared to the ones of other spores. Walks are driven by humidity cycles, each cycle inducing a small step in a random direction. The dispersal range from the walk is limited, but the walk provides key steps to either exit the sporangium or to reorient and refold. Jumps occur when the spores suddenly thrust themselves after being tightly folded. They result in a very efficient dispersal: even spores jumping from the ground can catch again the wind, while non-jumping spores stay on ground. The understanding of these movements, which are solely driven by humidity variations, conveys biomimetic inspiration for a new class of self-propelled objects.

Plants show a broad spectrum of movements with a wide variety of underlying mechanisms. Spore dispersion mechanisms are widely varied in plants and fungi. However, one common physical process is rapid ejection achieved by the sudden rupture of material. For example, spore dispersal in fungus relies the sudden rupture of the junction between the spore and its stalk after condensation of a water droplet [START_REF] Noblin | Surface tension propulsion of fungal spores[END_REF][START_REF] Dumais | Vegetable dynamicks: The role of water in plant movements[END_REF], or after the rupture of the fluidfilled stalk under osmotic stress [START_REF] Yafetto | The fastest flights in nature: High-speed spore discharge mechanisms among fungi[END_REF]. In Sphagnum mosses, the spore-containing capsules break when the drying stress is excessively large, which expels a jet of spores [START_REF] Whitaker | Sphagnum moss disperses spores with vortex rings[END_REF]. These motions can also be compared with the explosive dispersal of seeds [START_REF] Evangelista | The mechanics of explosive dispersal and self-burial in the seeds of the filaree, Erodium cicutarium (Geraniaceae)[END_REF][START_REF] Armon | Geometry and Mechanics in the Opening of Chiral Seed Pods[END_REF]. In ferns, the sudden collapse of water (cavitation) in the flexible arm of the sporangium catapults the spores [START_REF] Noblin | The fern sporangium: A unique catapult[END_REF].

Like ferns, Equisetum is a very ancient plant with robust adaptations [START_REF] Pryer | Horsetails and ferns are a monophyletic group and the closest living relatives to seed plants[END_REF]. Their spores present four elaters that respond to humidity variations [START_REF] Beer | The development of the spores of equisetum[END_REF][START_REF] Duckett | Spore size in the genus equisetum[END_REF]. The elaters function is to increase dispersal because they push the spores out of the plant and increase the aerodynamic drag in the wind [START_REF] Newcombe | Spore-dissemination of Equisetum[END_REF]. Contrary to other types of spores mentioned earlier, the dispersal does not involve any rupture of material.

Hygroscopic response. To understand the locomotion and dispersion mechanisms of Equisetum spores, we performed a detailed microscopic study of the shape of the spores under various humidity conditions. We observed that the elaters clearly change their shape (Fig. 1). At high humidity levels, the elaters spiral around the spherical body. At less than 75% humidity, the elaters begin to unfurl and become straight at approximately 50% of relative humidity (RH), at which point they are fully extended. At less than 50% RH, the elaters curl up, and the maximum span of the spores is slightly reduced. These changes are fully reversible, and only slight hysteresis was observed when increasing the humidity, suggesting that the spore shape reflects the current humidity. Humidity variations that induce changes in the elater shape are typical in the Equisetum habitat where humidity is high but can decrease periodically, e.g., due to wind or sun exposure.

The change in the curvature of the elaters can be understood from a structural perspective, as the elaters have a bilayer structure [START_REF] Uehara | An ultrastructural study of spore wall morphogenesis in equisetum arvense[END_REF]. The inner layer consists of dense longitudinal cellulose microfibrils (similar to that of higher plant cell walls), whereas the outer layer is less dense. We can infer from this structure that the outer layer is highly porous to water and changes in volume with variations in humidity. The differential volume change of one layer with respect to the other is responsible for the marked curvature changes. Thus, elaters are an example of natural "hygromorphs" [START_REF] Reyssat | Hygromorphs: from pine cones to biomimetic bilayers[END_REF]. Such hygromorphs include certain types of seeds [START_REF] Elbaum | The role of wheat awns in the seed dispersal unit[END_REF].

Random walks.

The elaters can open periodically in response to repeated humidity cycles. The position of the center of mass oscillates but does not return to the same position at the end of a cycle (Fig 2a-b). As a result, the spore "walks" in random directions. The amplitude of the steps of these walks is variable (see also Fig. 2c), as a spore can stay in the same position for multiple cycles before experiencing a large step, but with a well-defined average. We interpret these random steps to be a consequence of friction with the ground. More precisely, kinetic friction (as opposed to static friction) occurs during the opening/closing cycles when the elaters slide on the ground. Kinetic friction creates irreversible changes because the position of static contact is displaced. These repeated displacements induce steps. The variability in the orientation of the steps is attributed to the changes in the points of contact of this complex "tetrapod" during the opening/closing cycles. The tracking of many spores using image analysis showed that the spores diffuse in space (see Fig. 3a-b). The average squared distance travelled by each spore follows a diffusion law r 2 = 4Dt , where t is the time elapsed from a starting position, and D is the two-dimensional diffusion coefficient. The average is taken over several trajectories, and over different starting points. The value of the diffusion coefficient corresponds to an effective step of amplitude l=28 µm repeated with a period τ given by the cycle duration T cycle (using D=l 2 /2τ). The average distance travelled was calculated for many spores and for various starting positions, which is typical when tracking mobile agents such as swimming microorganisms [START_REF] Garcia | Random walk of a swimmer in a lowreynolds-number medium[END_REF].

At dense concentrations, spores can temporarily aggregate in mobile clusters. Surprisingly, these larger clusters diffuse at a higher speed, which we may call anti-Brownian behavior. Indeed, standard Brownian motion of inert particles in a liquid is slower for larger objects. We attribute this effect to the larger number of elaters per cluster, which leads to a greater frequency of random steps at each cycle. Therefore, we assume that the time interval τ between steps is divided by the number of spores, so that the diffusion coefficient (of the order of l 2 /τ) is proportional to the number of spores. Measurements of the diffusion coefficient of clusters of different sizes (see Fig. 3b) indeed shows a diffusion that increases proportionally to the number of spores (up to 6 spores), which is consistent with the assumption. This proportional trend should be less pronounced for very large heaps, since elaters on top of the heap do not touch the ground.

Jumps.

During drying from a fully hydrated state, spores can suddenly leave the ground at speeds of approximately 1 m/s and reach elevations of up to one centimeter (Fig. 4a-b). This height is very large compared to the spore size. These jumps were rarely observed in the walking experiment described above with a maximum of 90% RH. We noticed that a high humidity is necessary, here obtained in a saturated atmosphere at 100% RH or by immersion in a tiny droplet, most likely to sufficiently entangle the elaters prior to drying. Spores could jump several times, after a humidification/drying cycle. The probability of the spores to jump depends on the nature of the ground surface. On a hydrophobic surface the proportion of spores jumping (34%) is much larger than on a hydrophilic glass (12%), see Methods. We interpret this result as a consequence of a larger adhesion energy of wet spores with glass. However the height of jumps did not change much from surface to surface. Careful observations led us to hypothesize that pairs of elaters can be temporarily held motionless by friction during opening and store an elastic energy that is released when the forces are sufficiently large. The friction is localized between the elaters (see Fig. 4c). The upward thrust is obtained when the body is pushed upwards by the elater that is still in contact with the ground, this elater acting like a compressed spring releasing its energy.

Subsequently, we evaluated the energies at play during this motion to assess this hypothesis. The elastic energy is stored when the elaters are fixed with a given curvature c = 1/R (radius of curvature R = 60 µm in the sequence of Fig. 4a). The drying process changes the spontaneous curvature of the elaters, and observations of other loose elaters allow us to monitor the evolution of the spontaneous curvature. The curvature changes to c 0 = 1/R 0 immediately prior to ejection (R 0 is approximately 83 µm). The elastic energy, mainly caused by bending, can be modeled by assuming that the elater is a thin strip plate of length L el (approximately 160 µm) according to the following equation:

E b = 1 2 E I h L el (c-c 0 ) 2
where E is the Young's modulus, I h = h 3 w/12 is the bending moment, h (approximately 3 µm) is the thickness, and w (approximately 7 µm) is the width.

The kinetic energy after ejection at velocity v e is

E c = 1 2 m v e 2 ,
where the mass of the spore is the central body m = ρ body 4/3 πR body 3 , using R body = 20 µm, and a density, ρ body , similar to that of water. Here we neglect any rotational kinetic energy: the majority of jumps showed little rotation during ejection.

By assuming that all of the bending energy is released as kinetic energy, the jump velocity can be predicted and is directly given by the unknown Young's modulus of the elater. To match the measured jumping velocity, v e = 0.4 m/s (see Fig. 4), we determine that the Young's modulus should have a value of 100 MPa, as a lower bound. This value seems reasonable because it is much less than that of wood (approximately 10 GPa [START_REF] Ponomarenko | Ecoulements critiques et plantes[END_REF]), as it contains soft hygroscopic tissue, but is much larger than that of parenchymatous tissue (approximately 10 MPa [17]). Independent measurements of the bending modulus (see Methods) for dry elaters yielded a modulus that was of the same order of magnitude.

In conclusion, the elastic energy stored in the bending of the very thin elaters is sufficient to propel the spores. In the absence of air friction, all of the initial kinetic energy could be converted to gravitational potential energy, and a jump would reach a height H, such that mgH = E c , which implies that H = v e 2 2g = 8 mm. However, this height cannot be attained due to air drag. Therefore, we have included air drag in the model (see Materials and methods). The experimental trajectory, with a maximum height of 1.5 mm, closely fits the model (see Fig. 4d).

Discussion and perspectives Jumps enhance the dispersion of spores and provide a way to overcome adhesion to the plant or to neighboring spores. They are a natural occurrence of the phenomenon of Levy flights [18] in statistical physics that increase greatly the diffusion compared to a random walk with limited step amplitude. Fig. 5a illustrates how a small jump is enough for the spore to be entrained by wind. The jump allows to exit the ground where the air velocity is reduced, and to enter the higher velocity wind current. These spores are then more likely to travel than are immobile spores. Indeed, non-jumping spores stayed on the ground of a wind tunnel for velocities less than 5 m/s, and were just gliding on the flat ground for higher velocities. The Equisetum habitat is usually wet, which provides opportunities for the spores to contract into the entangled state quite frequently, and therefore also jump frequently. The jump mechanism can be repeated many times because it does not involve any irreversible fracture, in contrast to the movement of other species. Note that since the jumps occur upon drying, they provide an escape from dry locations and thus increase the chances of finding a more humid environment.

Even if the walk participates only to small distances locomotion, it enables the spores to make key steps. First, with humidity variations or rain, groups of spores make large steps, which helps to fall from the sporangium. It is an additional contribution to the spilling out of spores due to the volume increase of clusters when spores unfold. Second, the random steps reorient the spores and changes its contact points with the ground, which results in different entanglements at each humidity cycle, and increase the probability to block the elaters and store elastic energy. Third, the reorientation also helps to obtain jumps in random directions, maximizing the explored area.

As a perspective, we believe that this study will inspire new biomimetic classes of self-propelled objects, based on many appendices that open/close and that undergo friction with the ground. The comprehension of the velocity of walk and directionality of motion as a function of their geometry suggests a whole scope of investigation. Concerning their energy source, these hygroscopic objects have the interesting property to be able to move in response to humidity changes only, a free resource that occurs naturally.

[17] Niklas, K. J. 1988 Amer. J. Bot. 75, 1286-1292.

Appendices

Materials and Methods

Materials

The experiments where performed using fresh spores obtained by collecting sporangium shoots of Equisetum arvense at Saint Martin d'Hères in the early spring. The spores where placed in a Petri dish and imaged from the bottom or from the side using a binocular microscope. Image acquisition was performed either with a slow-motion CCD camera (Marlin, Allied Vision Technology) or with a high-speed camera (Miro 4, Vision Research) at 7,000 images per second for full images and up to 120,000 images per second for reduced regions of interest. The humidity was controlled by a programmable humidity generator (Wetsys, Setaram Instrumentation) with air blowing at a low speed above the Petri dish. To obtain rapid changes in humidity, the spores were covered for several minutes by a cap containing wet paper to obtain vapor saturation, and the cap was then quickly removed by the operator.

Measurement of the bending modulus of an elater

Recordings of the vibrations of an elater in a dry atmosphere (see Fig. 5b-c) yielded vibration frequencies in the ultrasonic range, f = 41+/-4 kHz, for an elater of length L el = 159 +/-10 µm.

According to Rocard [19], the vibration frequency of a cantilever having a round cross section is f = (3.515/4)(E/ρ) 1/2 r/L el 2 . By assuming that the density of the elater is similar to that of water, and because the elater is twisted into an effective round cross section of r = 5.7 µm, which is the cubic mean of h and w, we predict that Young's modulus is 400 MPa. This value is on the order of magnitude estimated based on the jump ejection velocity. The factor of four difference may be observed because here the elater is more dry, which tends to increase the elastic modulus. In addition, there may be a certain amount of energy lost by friction during the jump, leading to smaller jumps than expected based on the stored energy.

Jump trajectory with air drag, in still air

The equation of motion for the spore having a vertical position z and vertical velocity v z =dz/dt is as follows:

m dv z dt =-mg-6π η air R drag v z ,
where the last term is the Stokes drag force due to the dynamic viscosity of the air, η air (≈1.95x10 -6 Pa.s), and R drag is the effective radius of a sphere given the same amount of drag.

Stokes drag formula holds because the Reynolds number, ρ air v e R drag / η air , is low (approximately 1) at the maximum velocity. This equation can be integrated twice to give the evolution of the altitude:

z(t)=τ (v 0 +τ g)(1-exp(-t/τ ))-τ gt,
where τ = m/6πη air R drag is the deceleration time due to the viscosity. Fitting of the trajectory shown in Fig. 4 d) yielded a deceleration time of 5 ms.

Jumping statistics

The spores were spread on two kinds of surfaces: clean glass (hydrophilic, contact angle around 17°) or polystyrene Petri dishes (much less hydrophilic, contact angle around 88°). The contact angle of the water interface with respect to the ground was measured on photographs of tiny droplets of deionized water gently deposited on these surfaces. Three behaviors were observed using an inverted microscope with a 4x objective and classified in three categories: (i) clear jumps, (ii) start of jumps, exhibiting a sudden motion without takeoff, and (iii) continuous unfolding. The percentages given in the main text consider the first two classes. See figure S2 for detailed statistics.

Wind tunnel experiments

The spores were deposited on the lower flat surface of a wind tunnel (cross-section of air stream: 250x250 mm), the spores being initially wetted within a water droplet. The spores were seen to jump after complete evaporation of the droplets.

Electronic supplementary material is available :

Movie S1 Available at http://www.youtube.com/watch?v=ZALgWLpanE0 Legend: This movie illustrates for a general audience the walk and jump of Equisetum spores.

Figure S2

Legend: This figure shows the proportion of spores that were jumping.

Figure 1 :

 1 Figure 1: (a) The four elaters of a spore unfurling in a dry atmosphere. Scale bar is 50 µm. (b) Elater extent as a function of the relative humidity. Curves obtained by varying the humidity at a rate of 1% RH per minute. Points 1 to 5 correspond to the 5 pictures.

Figure 2 :

 2 Figure 2: Walks under repeated humidity oscillations. (a) The trajectory of the center of mass of the spore (see also Supplementary Movie S1), and (b) measurement of the extent, L, and the total distance, r, travelled. (c) Distribution of step sizes during a trajectory. The step size is defined as the distance between positions at the beginning of each humidity cycle. The average step size is here 31 µm.

Figure 3

 3 Figure 3 (a) Motion of spores under a succession of five humidity cycles (10% RH for 15 min and 90% RH for 15 min, T cycle =30 min). Scale bar is 500 µm. (b) Travelled distance as a function of time for several trajectories. The thick red line is the average of all trajectories (around a hundred) and over time, and the dashed line shows diffusion with r 2 =4Dt. The thick orange line shows the diffusion of a cluster (comprising of 5 spores on average). (c) Diffusion coefficient as a function of the n number of spores in a cluster.

Figure 4 :

 4 Figure 4: Side view of jumps. (a) Superposition of images immediately after the jump with an interval of 0.57 ms. The take-off velocity is 0.35 m/s. (b) Larger view with images taken every 1 ms. The take-off velocity is 0.4 m/s for the jump in the middle and 0.8 m/s for the jump starting on the right. On both images the scale bar is 500 µm and the ground position is indicated by the gray line. (c) Jumping mechanism of a spore (only two elaters are drawn). The elaters released when stresses overcome static friction are drawn in pale color with dashes. (d) The altitude of the spore (middle trajectory of Fig. 4b showing a dark spore). Circles represent measurements, and the line represents the model prediction with an initial velocity of 0.41 m/s and a drag radius of 21.2 µm.

Figure 5 :

 5 Figure 5: (a) Spore jump in a wind tunnel (superposition of images at 0.4 ms intervals). The wind speed far away from the ground is 4.85 m/s, corresponding to a "gentle breeze" of Beaufort number 3. The scale bar is 500 µm. (b) An elater was set into vibration using a tungsten tip mounted on a micrometric translation stage. Highspeed recordings of the vibration at 121,000 images/s were performed. The camera was recording a line of pixels (dotted line). The scale bar is 50 µm. (c) A spatio-temporal diagram showing 6 periods of oscillations is plotted.

[ 18 ]

 18 Mandelbrot, B. 1982 The Fractal Geometry of Nature, W.H. Freeman. [19] Rocard, Y. 1949 Dynamique générale des vibrations. Masson & Cie.

Acknowledgements

We thank Salima Rafaï for her insight on the tracking of spores and the computation of the diffusion coefficients, and Nicolas Mordant for his help in operating the wind tunnel. Automated tracking was performed using the routines of Erik Weeks. We also thank Tobias Haushan for suggesting literature on spore anatomy and Zi Chen and Catherine Quilliet for helpful discussions on elaters.