I Masliah

A Abdelfattah

A Haidar

S Tomov

M Baboulin

J Falcou

J Dongarra

High-performance matrix-matrix multiplications of very small matrices

The use of the general dense matrix-matrix multiplication (GEMM) is fundamental for obtaining high performance in many scientific computing applications. GEMMs for small matrices (of sizes less than 32) however, are not sufficiently optimized in existing libraries. In this paper we consider the case of many small GEMMs for a wide range of computer architectures, including multicore CPUs, ARM, Intel Xeon Phi, and GPUs. This is a case that often occurs in applications like big data analytics, machine learning, high-order FEM, and others. The GEMMs are grouped together in a single batched routine. We present specialized for these cases algorithms and optimization techniques to obtain performance that is within 90% of the optimal. For example, on a P100 GPU for square matrices of size 32, we achieve an execution rate of about 1, 030 Gflop/s in double precision arithmetic, which is 90% of the theoretically derived peak for this computation on a P100 GPU. We show that our results outperform currently available state-of-the-art implementations and vendor-tuned math libraries, including Intel MKL, Nvidia CUBLAS, and OpenBLAS.

Introduction

Parallelism in todays computer architectures is pervasive not only in systems from large supercomputers to laptops, but also in small portable devices like smartphones and watches. Along with parallelism, the level of heterogeneity in modern computing systems is also gradually increasing. Multicore CPUs are combined with discrete high-performance GPUs, or even become integrated parts with them as a system-on-chip (SoC) like in the NVIDIA Tegra mobile family of devices. To extract full performance from systems like these, the heterogeneity makes the parallel programming for technical computing problems extremely challenging, especially in modern applications that require fast linear algebra on many independent problems that are of size O(100) and smaller. According to a recent survey among the Sca/LAPACK and MAGMA [START_REF] Tomov | Towards dense linear algebra for hybrid GPU accelerated manycore systems[END_REF] users, 40% of the responders needed this functionality for applications in machine learning, big data analytics, signal processing, batched operations for sparse preconditioners, algebraic multigrid, sparse direct multifrontal solvers, QR types of factorizations on small problems, astrophysics, and high-order FEM. At some point in their execution, applications like these must perform a computation that is cumulatively very large, but whose individual parts are very small; when such operations are implemented naively using the typical approaches, they perform poorly. To address the challenges, we designed a standard for Hybrid Batched BLAS [START_REF] Dongarra | A proposed API for Batched Basic Linear Algebra Subprograms[END_REF], and developed innovative algorithms [START_REF] Haidar | A Framework for Batched and GPU-Resident Factorization Algorithms Applied to Block Householder Transformations[END_REF], data and task abstractions [START_REF] Abdelfattah | High-Performance Tensor Contractions for GPUs[END_REF], as well as high-performance implementations based on the standard that are now released through MAGMA 2.0 [START_REF] Dong | LU Factorization of Small Matrices: Accelerating Batched DGETRF on the GPU[END_REF][START_REF] Haidar | Batched matrix computations on hardware accelerators based on gpus[END_REF]. Figure 1 illustrates how the need for batched operations and new data types arises in areas like linear algebra (Left) and machine learning (Right). The computational characteristics in these cases are common to many applications, as already noted: the overall computation is very large but is made of operations of interest that are in general small, must be batched for efficiency, and various transformations must be explored to cast the batched small computations to regular and therefore efficient to implement operations, e.g., GEMMs. We note that applications in big data analytics and machine learning target higher dimension and accuracy computational approaches (e.g., ab initio-type) that model mutilinear relations, thus, new data abstractions, e.g., tensors, may be better suited vs. the traditional approach of flattening the computations to linear algebra on two-dimensional data (matrices). Indeed, we developed these tensor data abstractions and accelerated the applications using them significantly [START_REF] Abdelfattah | High-Performance Tensor Contractions for GPUs[END_REF] compared to other approaches. There is a lack of sufficient optimizations on the batched GEMMs needed and targeted in this paper. We show this in comparison to vendor libraries like CUBLAS for NVIDIA GPUs and MKL for Intel multicore CPUs. Related work on GEMM and its use for tensor contractions [START_REF] Abdelfattah | High-Performance Tensor Contractions for GPUs[END_REF] target only GPUs and for very small sizes (16 and below). Batched GEMM for fixed and variable sizes in the range of O(100) and smaller were developed in [START_REF] Abdelfattah | Performance, Design, and Autotuning of Batched GEMM for GPUs[END_REF]. The main target here are batched GEMMs for multicore CPUs, ARM, Intel Xeon Phi, and GPU architectures on matrices of sizes up to 32.

Contributions to the Field

The evolution of semiconductor technology is dramatically transforming the balance of future computer systems, producing unprecedented changes at every level of the platform pyramid. From the point of view of numerical libraries, and the myriad of applications that depend on them, three challenges stand out: 1) the need to exploit unprecedented amounts of parallelism; 2) the need to maximize the use of data locality and vectorized operations; and 3) the need to cope with component heterogeneity. Below, we highlight our main contributions related to the algorithm's design and optimization strategies aimed at addressing these challenges on multicore CPU, ARM, Xeon Phi, and GPU architectures.

Exploit Parallelism and Vector Instructions:

Clock frequencies are expected to stay near their current levels, or even decrease to conserve power; consequently, as we already see, the primary method of increasing computational capability of a chip will be to dramatically increase the number of processing units (cores), which in turn will require an increase of orders of magnitude in the amount of concurrency that routines must be able to utilize as well as increasing the computational capabilities of the floating point units by extending it to the classical Streaming SIMD Extensions set (SSE-1, to SSE-4) in the earlier 2000, and recently to Advanced Vector Extensions (AVX, AVX-2, AVX-512). We developed specific optimization techniques that demonstrate how to use the many cores (currently multisocket 10 -20 cores for the Haswell CPU, 4 cores for a Cortex A57 processor, 68 cores for an Intel Knights Landing 7250 (KNL) and 56 × 64 CUDA cores for the Tesla P100 GPU) to get optimal performance. The techniques and kernels developed are fundamental and can be used elsewhere.

Hierarchical Communication Techniques that Maximizes the use of Data Locality:

Recent reports (e.g., [START_REF] Fuller | The Future of Computing Performance: Game Over or Next Level?[END_REF]) have made it clear that time per flop, memory bandwidth, and communication latency are all improving, but at exponentially different rates. So computation on very small matrices, that can be considered as computation-bound on old processors, is, -today and in the futurecommunication-bound and depends on the communication between levels of the memory hierarchy. We demonstrate that performance is indeed harder to get on new manycore architectures unless hierarchical communications and optimized memory management are considered in the design. We show that, only after we developed algorithmic designs that feature multilevel blocking of the computations and use multilevel memory communications, our implementations reach optimal performance.

Performance Analysis and Autotuning:

We demonstrate the theoretical maximal performance bounds that could be reached for computation on very small matrices. We studied various instructions and performance counters, as well as proposed a template design with different tunable parameters in order to evaluate the effectiveness of our implementation and optimize it to reach the theoretical limit.

All experiments are done on an Intel multicore system with two 10-cores Intel Xeon E5-2650 v3 (Haswell) CPUs, a 4-cores Cortex A57 ARM CPU, a 68-cores Intel Knights Landaing CPU 7250 and a Pascal Generation Tesla P100 GPU. Details about the hardware are illustrated in Figure 2. We used gcc compiler 5.3.0 for our CPU code (with options -std=c++14 -O3 -avx -fma), as well as the icc compiler from the Intel suite 2016.0.109, and the BLAS implementation from MKL (Math Kernel Library) 16.0.0 [14]. We used CUDA Toolkit 8.0 for the GPU. For the CPU comparison with the MKL library we used two implementations: 1) An OpenMP loop statically or dynamically unrolled among the cores (we choose the best results), where each core computes one matrix-matrix product at a time using the optimized sequential MKL dgemm routine, and 2) The batched dgemm routine that has been recently added to the MKL library. To evaluate the efficiency of our algorithms we derive theoretical bounds for the maximum achievable performance P max = F/T min , where F is the number of operations needed by the computation and T min is the fastest time to solution. For simplicity, consider C = αAB + βC on square matrices of size n. We have F ≈ 2n 3 and T min = min T (T Read(A,B,C) + T Compute(C) + T W rite(C) ). Note that we have to read/write 4n 2 elements, or 32n 2 Bytes for double precision (DP) calculations. Thus, if the maximum achievable bandwidth is B (in Bytes/second), and we assume T Compute(C) → 0 for very small computation, then T min = T Read(A,B,C) + T W rite(C) = 4n 2 /B in DP. Note that this time is theoretically achievable if the computation totally overlaps the data transfer and does not disrupt the maximum rate B of read/write to the GPU memory. Thus,

P max = 2n 3 B 32n 2 = nB 16 in DP.
The achievable bandwidth can be obtained by benchmarks. For our measures, we used the STREAM benchmark [START_REF] Mccalpin | Memory bandwidth and machine balance in current high performance computers[END_REF] and the Intel memory latency checker 3.0 tool for CPU. We also used NVIDIA's bandwidthTest and a set of microbenchmarks that we developed for GPU. Our tests show that the practical CPU bandwidth we are able to achieve using different benchmarks is about 44 GB/s per socket.

On the Tesla P100 GPU, the peak is 580 GB/s, so in that case P max is 2.75 n GFlop/s per socket for the CPU and 36.25 n GFlop/s for the Tesla P100 GPU. The curve representing this theoritical maximal limit is denoted by the "upper bound" line on Figures 6 and14a. Thus, when n = 16 for example, we expect a theoretical maximum performance of 580 GFlop/s in DP on the P100 GPU.

5 Programming Model, Performance Analysis, and Optimization for CPUs

Our overall designs and software construction include the use of new features of C++ for better re-usability and adaptability of the code. By using advanced template techniques we can create high-level interfaces [START_REF] Masliah | Metaprogramming dense linear algebra solvers applications to multi and many-core architectures[END_REF] without adding any cost even for small matrix-matrix products. To do so, we designed a batch structure which contains a C++ vector for the data and static dimensions. By using the C++ constexpr keyword and integral constants we developed a generic batched code that dispatches at compile time the correct version depending on the size of matrices. We use this environment for each code sequence that we generate.

The implementation of a matrix-matrix products kernel for very small matrices for CPUs requires specific design and optimizations. As we can store three double precision matrices of size up to 32 × 32 in the L1 cache of an Intel Xeon E5-2650 v3 processor (or any modern processor), one can expect that any implementation will not suffer from data cache misses. This can be seen on Figure 9b where the performance of an ijk implementation, which is not cache-aware and cannot be vectorized, is pretty close to the ikj one. The ijk and ikj implementation correspond to the simple matrix product implementation using for loops. The ikj version is cache-friendly as data accessed in a continuous fashion which also gives the possibility to the compiler for vectorization. In ijk version, data is not accessed contiguously but we can minimize the number of store operations by computing one value of C for each iterations of the innermost loop. For smaller sizes, the ijk implementation is more efficient than the ikj one, as it optimizes the number of stores (Figure 4a). To obtain a near optimal performance, we conduct an extensive study over the performance counters using the PAPI [START_REF] Weaver | Measuring energy and power with PAPI[END_REF] tools. Our analysis concludes that in order to achieve an efficient execution for such computation, we need to maximize the CPU occupancy and minimize the data traffic while respecting the underlying hierarchical memory design. Unfortunately, today's compilers cannot introduce highly sophisticated cache/register based loop transformations and, consequently, this kind of optimization should be studied and implemented by the software developer [START_REF] Loshin | Efficient Memory Programming[END_REF]. This includes techniques like reordering the data so that it can be easily vectorized, reducing the number of instructions so that the processor spends less time in decoding them, prefetching the data that will be reused in registers, and using an optimal blocking strategy. In this CPU section, we use a batch count of 10000 which is enough to get the best performance for small size matrix-matrix products.

Programming techniques using C++14

The development of programming languages and their use has dramatically changed in recent years leading to continuous evolution. C++ is an example of such a programming language. The standardization committee has decided to make a new standard every 3 years, with the next release being the C++17 standard. The cause of these changes is the need for higher level language that provides better idioms for generic and generative programming and support for parallel computing. Here we discuss the new features of the C++14 standard that we use to develop our matrix-matrix product.

The first feature of the C+14 language that we discuss is auto [START_REF] Järvi | Decltype and auto (revision 3)[END_REF]. Consider the following declaration in Listing 1.1:

// x i s t h e t y p e o f 7 : i n t a u t o x = 7 ;

Listing 1.1. C++ auto Here x will have the type int because it is the type of its initializer. In general, we can write the code in Listing 1.2

// x i s o f t h e t y p e o f e x p r e s s i o n a u t o x = e x p r e s s i o n ;

Listing 1.2. C++ generic auto and x will be of the type from the value expression in Listing 1.2. For any variable, auto specifies that the type of the variable that is being declared will be automatically deduced from its initializer. This allows to write high level complex code without having the burden of complex types that can appear. We can apply the auto keyword on several features of the C++ language.

Another important feature of the C++14 standard is the constexpr keyword [START_REF] Reis | General constant expressions for system programming languages[END_REF]. The constexpr keyword provides a mechanism that can guarantee that an initialization is done at compile time. It also allows constant expressions involving user-defined types.

In Listing 1.3, the fibonnaci function is guaranteed to be executed at compile time if the value passed x is available at compile time.

c o n s t e x p r l o n g l o n g f i b o n a c c i ( c o n s t i n t x ) { r e t u r n x <= 1 ? 1 : f i b o n a c c i ( x -1 ) + f i b o n a c c i ( x -2 ) ; } Listing 1.3. C++ constexpr
Using constexpr and the features described previously also allow for integral constants. Integral constants are part of the C++ standard and wrap a static constant of a specific type in a class. This allows us to easily support different SIMD extensions (Intel SSE,AVX2,AVX512 and ARM AArch64) while using a generic function for each call (see Listing 1.4).

// T h i s i s t r u e i f t h e CPU i s an I n t e l P r o c e s s o r # i f If we then want to do a multiplication using SIMD instructions, we can simply use the standard operator with our overloaded functions (see Listing 1.5). These programming techniques allow us to have a single source file of around 400 lines that support Intel and ARM processors for very efficient small size matrix products. It is also very simple to extend. For example, adding support for IBM processors with Altivec SIMD instructions only requires us to add an overload for each SIMD functions we need.

Data Access Optimizations and Loop Transformation Techniques

In our design, we propose to order the iterations of the nested loops in such a way that we increase locality and expose more parallelism for vectorization. The matrix-matrix product is an example of perfectly nested loops which means that all the assignment statements are in the innermost loop. Hence, loop unrolling, loop peeling, and loop interchange can be useful techniques for such algorithm [START_REF] Ahmed | Tiling imperfectly-nested loop nests[END_REF][START_REF] Bacon | Compiler transformations for highperformance computing[END_REF]. These transformations improve the locality and help to reduce the stride of an array based computation. In our approach, we propose to unroll the two inner-most loops so that the accesses to matrix B are independent from the loop order, which also allows us to reorder the computations for continuous access and improved vectorization. This technique enables us to prefetch and hold some of the data of B into the SIMD registers. Here, we manage to take advantage from the knowledge of the algorithm (see Figure 3), and based on the principle of locality of references [START_REF] Hennessy | Computer Architecture, Fifth Edition: A Quantitative Approach[END_REF], to optimize both the temporal and spatial data locality.

(a) Compute first row of matrix C 1.

2.

4.

(b) Compute all of matrix C Fig. 3. Example of a 4-by-4 matrix product using SIMD

Register Data Reuse and Locality

Similarly to the blocking strategies for better cache reuse in numerically intensive operations (e.g., large matrix-matrix products), we focus on register blocking to increase the performance. Our study concludes that the register reuse ends up being the key factor for performance. The idea is that when data is loaded into SIMD register, it will be reused as much as possible before its replacement by new data. The amount of data that can be kept into registers becomes an important tuning parameter. For example, an 8 × 8 matrix requires 16 256-bit AVX-2 registers to be completely loaded. As the targeted hardware consists of only 16 256-bit AVX-2 registers, one can expect that loading the whole B will not be optimal as we will have to reload the vectors for A and C. However, if we load only 8 registers for B, which is equal to 4 rows, we can compute a row of C at each iteration and reuse these 8 registers for each iteration. We propose an auto-tuning process to check all the possible scenarios and provide the best option. This reduces the number of load, store, and total instructions from O(n 2 ) to O(n), compared to a classical ijk or ikj implementation as depicted in Figures 4a,4b, and 6a, respectively.

Algorithmic Advancements

Algorithm 1 is an example of our methodology for a matrix-matrix product of 16 × 16 matrices. In this pseudo-code, we start by loading four 256-bit AVX-2 registers with values of B which correspond to the first row. These registers are reused throughout the algorithm. In the main loop (Lines 4-14), we start by computing the first values of every multiplication (stored into a register named M=A×B) based on the prefetched register in line 1. Then, we iterate on the remaining rows (Lines 7-11) loading B, multiplying each B by a value of A, and adding the result into M. Once the iteration over a row is accomplished, the value of M is the final result of A×B and thus, we can load the initial values of C, multiply by α and β, and store it back before moving toward the next iteration such a way to minimize the load/store as shown in Figure 4. Each C ends up being loaded/stored once. We apply this strategy to matrix sizes ranging from 8 to 32 as for smaller sizes the whole matrix can fit in registers. Different blocking strategies (square versus rectangular) have been studied through our auto-tuning process in order to achieve the best performance. We generate each matrixmatrix product function at compile time with C++ templates. The matrix size is passed as a function parameter using C++ integral constants.

Effect of the Multi-threading

As described above, operating on matrices of very small sizes is memorybound computation and thus, increasing the number of CPU cores may not always increase the performance since the performance will be limited by the bandwidth which can be saturated by a few cores. We performed a set of experiments towards clarifying this behavior and illustrate our findings in Figure 5b. As shown, the notion of perfect speed-up does not exist for a memory-bound algorithm, and adding more cores increases the performance slightly. We performed a bandwidth evaluation when varying the number of cores to find that a single core can achieve about 18 GB/s while 6 and 8 cores (over the available 10 cores) can reach about 88% and 93% of the practical peak bandwidth, which is about 44 GB/s.

Effect of the NUMA-socket and Memory Location

We also studied NUMA-socket (non-uniform memory access) [START_REF] Hager | Introduction to High Performance Computing for Scientists and Engineers[END_REF] when using two Xeon sockets as seen in Figure 5a. A standard memory allocation puts all of the data in the memory slot associated to the first socket until it gets filled, then starts filling the second socket. Since the problem size we are targeting is very small, most of the data is allocated on one socket, and thus using extra 10 cores of the second socket will not increase the performance. This is due to the fact that the data required by the cores of the second socket goes through the memory bus of the first socket, and thus is limited by the bandwidth of one socket (44 GB/s). There are ways to overcome this issue. By using NUMA with the interleave=all option, which spreads the allocation over the two sockets by memory pages, we can improve the overall performance. However, for very small sizes, we observe that such solution remains far from the optimal bound since data is spread out over the memory of the two sockets without any rules that cores from socket 0 should only access data on socket 0, and vice versa. To further improve performance, we use a specific NUMA memory allocation, which allows us to allocate half of the matrices on each socket. As shown in Figure 5a, this allows our implementation to scale over the two sockets and to reach close to the peak bound.

Application to the Intel KNL

The Intel KNL is a new architecture that provides improved hardware features such as 512-bit vector units, up to 288 hardware threads and a high bandwidth memory called MCDRAM. The KNL can be configured in different ways using the MCDRAM and sub-numa nodes which have been detailed in Sodani's Hot Chips presentations [START_REF] Sodani | Knights landing (knl): 2nd generation intel R xeon phi processor[END_REF]. An extensive study to apply the Roofline Performance Model [START_REF] Williams | Roofline: an insightful visual performance model for multicore architectures[END_REF] on the KNL [START_REF] Doerfler | Applying the roofline performance model to the intel xeon phi knights landing processor[END_REF] has shown the differences between the MCDRAM configurations and its impact on performance. Our study has ended up with the same conclusion and all application results we present use the Quad-Flat representation as all of the data fits in the MCDRAM. We use the Linux utility numactl to target the MCDRAM ( flag -m 1). To compile with gcc on the KNL, we add the -march = knl flag for AVX512F instructions support.

We can see in Figure 7 that the number of load 7a and store 7b instructions are following the same pattern as with the Haswell processor. The important drops we see on each graph for the KNL are a bit different than on the Haswell processor. This is due to the size of the vector unit going from 256-bit to 512-bit. For double precision operations, we see on every multiple of 8 a large drop in the number of load/store due to the matrix size being a multiple of the SIMD size.

We generally reach the same number of load instructions as the MKL since we cannot really optimize this parameter as seen with the Haswell CPU. However, by not using a standard blocking strategy, we are able to optimize even more the number of stores operations compared to the Haswell CPU due to the larger SIMD vector size. We can see on Figure 8a that we always have a lower total instruction count. On the KNL, it is possible to have up to 4 threads per core. Using the maximum number of threads is never efficient as see on Figure 8. Using 2 threads per core can sometime yields better performance but the delta is quite negligible. Except for matrix sizes smaller than 12, it is always better to utilize every CPU core available on the KNL.

Similarly to what we saw with the Haswell processor, our analysis and design directly translates on the performance obtained (see Figure 9). The performance with our generated code in MAGMA is always better than that of the MKL. We can see that the use of the MCDRAM as the main memory instead of the DDR4 heavily impacts the performance. We observe an overall performance increase of two when using the MCDRAM. We end up far from the upper bound due to data in the MCDRAM not being read multiple times which limits the bandwidth usage. Using the MCDRAM also leads to more stable performance. Memory bound problems tend to be less stable in terms of performance when using SIMD instructions and multi-threading due to limited resources. This is even more prevalent with the KNL as its very large SIMD instructions (512-bit) corresponds to the size of an L1 cache line (64 Bytes).

Application to ARM processor

The ARM processor that we use for this benchmark is the CPU of the Tegra X1, a 4-core Cortex A57. The problems we detailed earlier still apply to the Tegra but on a different scale. Indeed, the ARM intrinsics only support 128-bit vectors which severely limit the SIMD use for double precision computations. In Figure 10, we compare the performance between our MAGMA code, an ijk code, an ikj code and OpenBLAS [START_REF] Xianyi | Openblas[END_REF] using the latest version available from the develop branch on Github. Results follow the same trend we saw on the Intel processors. On very small sizes, ijk and ikj versions are quite efficient as the arithmetic intensity is very low, limiting the usefulness of parallelism. With increased sizes, we start to see these version stale and reach a limit set around 3.5 Gflops. The OpenBLAS version provides good performance but is limited by its blocking model which is not adapted for very small sizes.

Programming Model, Performance Analysis, and Optimization for GPUs

Considering the development for GPUs, we set a goal to have a unified code base that can achieve high performance for very small sizes. The design strategy is different from the MAGMA batched GEMM kernel for medium and large sizes [START_REF] Abdelfattah | Performance, Design, and Autotuning of Batched GEMM for GPUs[END_REF]. The latter uses a hierarchical blocking technique where different thread blocks (TBs) compute different blocks of the output matrix C. With such a design, a TB reads an entire block row of A and an entire block column of B to compute its share of C. Obviously, there will be redundant reads of both A and B among TBs. Considering extremely small sizes (e.g. up to 32), redundant reads cannot be afforded, since the memory bandwidth becomes the main bottleneck for such computational workload.

Instead, we adopt a strategy where a single TB performs the entire multiplication of at least one problem, computing all of C with no subdivision involved. We start by an initial design that represents a special case of a 1×1 blocking technique, in order to avoid redundant reads from global memory. Since the sizes considered are very small, there is enough resources on the SM to store all of A, B, and C in shared memory and/or registers. Similar to the design proposed in [START_REF] Abdelfattah | Performance, Design, and Autotuning of Batched GEMM for GPUs[END_REF], we use CUDA C++ templates to have an abstract design that is oblivious to tuning parameters and precision. In this paper, we discuss the main design aspects of the proposed kernel, and how we managed, through an extensive auto-tuning and performance counter analysis, to improve its performance on the Tesla P100 GPU over the original design proposed in [START_REF] Masliah | High-Performance Matrix-Matrix Multiplications of Very Small Matrices[END_REF].

A Shared Memory Approach

Our previous work [START_REF] Masliah | High-Performance Matrix-Matrix Multiplications of Very Small Matrices[END_REF] showed that using shared memory to exploit data reuse is superior to using the read-only data cache. We start by a simple design where A and B are stored in shared memory for data reuse, and C is stored in registers. Each TB performs exactly one GEMM operation. Eventually, the kernel launches as many TBs as the number of multiplications to be performed. Using a 2D thread configuration, each thread computes one element in the output matrix C. The matrices A, B, and C are read only once from the global memory. Data reuse of A and B occurs only in shared memory, where each thread reads a row of A and a column of B to compute its respective output.

Data prefetching

Our first try to improve the performance adds data prefetching to the initial design. By assigning more multiplications per TB, we can prefetch the next triple A, B, and C, while another multiplication is taking place. We choose to prefetch data in registers in order to reduce synchronization and avoid overloading the shared memory. Recall that the register file per SM is about 256KB, while the shared memory is 64KB at maximum. Surprisingly, Figure 11a shows that data prefetching does not result in performance gains except for slight improvements for few certain sizes. We list two major reasons for this behavior. The first is that the prefetching technique uses 4× the register resources of the original design, which might limit the number of TBs per SM as the sizes get larger. The second is that there is a costly branch statement inside the kernel that checks whether there is more data to prefetch. Eventually, we decided to drop data prefetching from the final design. 11. Impact of data prefetching and aggregation on performance. The experiment is performing 100,000 GEMM operations in double precision on a Tesla P100 GPU.

Thread block-level Aggregation

We adopt a different approach to assign multiple multiplications per TB. Considering the original design, we aggregate a number of TBs together into one bigger TB. Internally, the new TB is divided into smaller working groups, each taking care of one multiplication. Such a design significantly improves the performance for tiny sizes. The main reason is that the original design suffers from a bad TB configuration, which assigs very few warps or even less than a warp to a TB. The aggregation technique improves this configuration for tiny sizes. As an example, the original design launches 4 threads per TB for a multiplication of 2 × 2 matrices, which is one eighth of a warp. The aggregation technique groups 16 multiplications per TB, thus launching 2 warps per TB. The level of aggregation is controlled through a tuning parameter (tba). Figure 11b shows the impact of aggregation (after tuning tba for every size) on performance, where we observe performance improvements on sizes less than 8. For example, aggregation achieves a speedups of 4.1×, 2.5×, 1.7×, 1.25×, and 1.20× for sizes 2, 3, 4, 5, and 6, respectively. For larger sizes, we observe that it is always better to set tba=1, since there are enough warps per TB.

Recursive Blocking

We propose a new optimization technique that helps improve the performance as the sizes get larger. For a multiplication of size N , the original design uses N×N threads and 2N ×N of shared memory per TB. This configuration can limit the number of TBs that can execute concurrently per SM. In order to mitigate this effect, we recursively block the computation in shared memory. The new design uses N × N threads and 2 N × N , where N is a tuning parameter that is typically less than N , such that:

1 < N N ≤ 2 . ( 1
)
The kernel reads A, B, and C once into registers. Since the shared memory resources can only accomodate two N × N blocks, the computation is performed on several stages. Equation 1 ensures a 2×2 blocking of the form:

C 00 C 01 C 10 C 11 = α A 00 A 01 A 10 A 11 × B 00 B 01 B 10 B 11 + β C 00 C 01 C 10 C 11 (2)
We point out that the sizes of C 00 , C 01 , C 10 , and C 11 are N × N , N × (N -N ), (N -N ) × N , and (N -N ) × (N -N ), respectively, which is exactly the same for A and B. The scaling with β is done upon reading C. In order to compute C 00 , the kernel loads A 00 and B 00 into shared memory to compute αA 00 × B 00 , and then similarly αA 01 × B 10 . The accumulation occurs in the registers holding β × C 00 . The computation of other blocks of C is performed similarly to C 00 . Eventually, the kernel is performing one GEMM operation using much less resources in terms of shared memory and threads. While this comes at the cost of using more registers, the register file per SM is big enough to accomodate such increase. The overall result is an improved performance for relatively larger sizes as shown in Figure 12. In the range of sizes [20:32], we observe speedups ranging from 3% up to 31%. The non-blocking kernel loses performance as we increase the sizes, unlike the blocking kernel which maintains a steady performance. Eventually, our solution combines all of the aforementioned techniques, with the exception of data prefetching. We can subdivide the range [1:32] into three segments. The first represents the tiny sizes in the range [1:10], where we use a non-blocking kernel with tba> 1. The second is the midrange [11:19], where we still use the non-blocking kernel, but setting tba = 1. The third is the relatively larger sizes in [20:32], where we call the blocking kernel.

Instruction Mix

A common optimization in all of our designs is the instruction mix of the GPU kernel, which is crucial to performance when operating on matrices of such very small sizes. Integer instructions, which are used for loop counters and memory address calculations, can be quite an overhead in such computations. Moreover, our study showed that a loop with predefined boundary can be easily unrolled and optimized by the Nvidia compiler. Using CUDA C++ templates that are instantiated with compile-time tuning parameter, we are able to produce fully unrolled code for every size of interest. By profiling the kernel execution, we collected the number of integer instructions as well the number of the FP64 instructions. Figure 13 shows the total number of integer instructions as well as the ratio of integer instructions to the total number integer and FP64 instructions. We observe that the MAGMA kernel always executes less integer instructions than CUBLAS. It also has the smallest ratio for most sizes. An interesting observation of the CUBLAS implementation, for this range of matrices, is that it uses a fixed blocking size of 16×16. This explains the drops at sizes 16 and 32, where the problem size matches the internal blocking size.

Performance and Profiling Results

Figure 14a shows the final performance of the proposed kernel against the batched GEMM kernel from CUBLAS, as well as against a CPU reference implementation that combines MKL with OpenMP. We also show the upper bound of the performance, as estimated in Section 4. The results show that MAGMA is significantly faster than CUBLAS, scoring speedups that range from 1.13× (at size 32) up to 18.2× (at size 2). We observe that the smaller the size, the larger the speedup. Similarly, MAGMA speedups against the CPU implementation range from 11.4× up to 164.4×. On another hand, the MAGMA kernel is up to 88% close to the performance upper bound.

An interesting observation is shown in Figure 14b, which shows that the the CUBLAS kernel achieves higher occupancy than the MAGMA kernel, starting from size 10. We point out that the achieved occupancy metric does not necessarily give good insight to performance, and it has to be combined with other metrics. In fact, the achieved occupancy is defined as the ratio of the average active warps per active cycle to the maximum number of warps supported on the SM. However, the measurement of busy warps does not mean that they are doing useful work. In fact, Figure 13 shows that the CUBLAS kernels executes a lot more integer instructions than the MAGMA kernel. Moreover, since the computation is memory bound, we show a more representative metric. Figure 15 shows the read and write throughputs of the GPU memory, during execution. The proposed MAGMA kernel achieves significantly higher throughput than CUBLAS in both reads and writes, with an up to 22× higher throughput in reads and up to 15× higher throughput in writes.

Conclusions and future directions

We presented work motivated by a large number of applications, ranging from machine learning to big data analytics, that require fast linear algebra on many independent problems that are of size 32 and smaller. The use of batched GEMM for small matrices is fundamental for obtaining high performance in applications like these. We presented specialized algorithms for these cases -where the overall computation is memory bound but still must be blocked -to obtain performance that is within 90% of the optimal, significantly outperforming currently available state-of-the-art implementations and vendor-tuned math libraries. Here, the optimal is the time to just read the data once and write the result, disregarding the time to compute. The algorithms were designed for modern multi-core CPU, ARM, Xeon Phi, and GPU architectures. The optimization techniques and algorithms can be used to develop other batched Level 3 BLAS and to accelerate numerous applications that need linear algebra on many independent problems.

Future work includes further optimizations and analyses, e.g., on how high performance can go using CUDA. It is known that compilers have their limitations in producing top performance codes for computations like these, thus, requiring the use of lower level programming languages. Current results used intrinsics for multi-core CPUs and CUDA for GPUs, combined with auto-tuning in either case, to quickly explore the large algorithmic variations developed in finding the fastest one. Future work includes also use in applications, development of application-specific optimizations, data abstractions, e.g., tensors, and algorithms that use them efficiently.

∑Fig. 1 .

 1 Fig. 1. Left: Example of a 4 th -order tensor contractions design using Einstein summation notation and a Domain Specific Embedded Language (or DSEL ). Right: Illustration of batched computations needed in machine learning.

Fig. 2 .

 2 Fig. 2. Memory hierarchies of the experimental CPU and GPU hardware

  u s i n g s i m d s i z e = s t d : : i n t e g r a l c o n s t a n t <u n s i g n e d l o n g ,512 > // P r o p a g a t e t h e v a l u e a t A [ iA * N ] i n t h e 512 SIMD r e g i s t e r tmp a u t o tmp = s e t ( A [ iA * N ] , s i m d s i z e {} ) ; // Load B [ i ] . . B [ i+s i m d s i z e ] and m u l t i p l y a u t o C = tmp * l o a d (&B [ i ] , s i m d s i z e { } ) ; Listing 1.5. C++ multiply operation

1 :Fig. 4 .

 14 Load B0, B1, B2, B3 2: Load α, β 3: S = 16 4: for i = 0, 1, ... , S-1 do 5[i*S+u] * Bu0; ... Mi3 += A[i*S+u] *Bui3 11: end for 12: Mi0 = α Mi0 + β (Load Ci0); ... Mi3 = α Mi3 + β (Load Ci3) 13: Store Mi0, Mi1, Mi2, Mi3 14: end for Algorithm 1: Generic matrix-matrix product applied to matrices of size 16 × 16 CPU Performance counters measurement of the memory accesses on Haswell

Fig. 5 . 6 .

 56 Fig. 5. CPU Performance analysis on Haswell

8 .

 8 # of store instructions Fig. 7. CPU Performance counters measurement of the memory accesses on KNL Effect of the number of CPU Fig. CPU performance counters and scaling analysis on KNL

9 .

 9 CPU Performance comparison with MC-DRAM Fig. Experimental results of the matrix-matrix multiplication on KNL -68 threads

Fig. 10 .

 10 Fig. 10. Experimental results of the matrix-matrix multiplication on the Tegra X1

Fig. 12 .

 12 Fig.[START_REF] Haidar | A Framework for Batched and GPU-Resident Factorization Algorithms Applied to Block Householder Transformations[END_REF]. Impact of recursive blocking on performance. The experiment is performing 100,000 GEMM operations in double precision on a Tesla P100 GPU.

Fig. 13 .

 13 Profiling the instruction mix of MAGMA versus CUBLAS. The experiment is performing 100,000 GEMM operations in double precision on a Tesla P100 GPU.

  Final performance and achieved occupancy. The experiment is performing 100,000 GEMM operations in double precision on a Tesla P100 GPU.

Fig. 15 .

 15 DRAM read and write throughputs. The experiment is performing 100,000 GEMM operations in double precision on a Tesla P100 GPU.

REGISTERS MAIN MEMORY BANDWIDTH PCI EXPRESS GEN3 X16 INTERCONNECT CRAY GEMINI L3 CACHE L2 CACHE L1 CACHE & GPU SHARED MEMORY MAIN MEMORY Haswell E5-2650 v3 KNL 7250 DDR5|MCDRAM ARM K40c P100 10 cores 68 cores 4 cores 15 SM x 192 cores 56 SM x 64 cores 16/core AVX2 32/core AVX-512 32/core 256 KB/SM 256 KB/SM 32 KB/core 32 KB/core 32 KB/core 64 KB/SM 64 KB/SM 256 KB/core 1024 KB/2cores 2 MB 1.5 MB 4 MB 25 MB 0...16 GB N/A N/A N/A 64 GB 384 |16 GB 4 GB 12 GB 16 GB 68 GB/s 115 | 421 GB/s 26 GB/s 288 GB/s 720 GB/s 16 GB/s 16 GB/s 16 GB/s 16 GB/s 16 GB/s 6 GB/s 6 GB/s 6 GB/s 6 GB/s 6 GB/s Memory hierarchies for different type of architectures Memory hierarchies

Acknowledgments

This material is based in part upon work supported by the US NSF under Grants No. CSR 1514286 and ACI-1339822, NVIDIA, the Department of Energy, and in part by the Russian Scientific Foundation, Agreement N14-11-00190.


Sonia Lehman-Frisch

Le goût des autres. Gentrification told by children

If the gentrification literature has considerably expanded in the last decades, few works have attempted to understand the relationship between the "gentrifying" households of the middle classes and the "gentrified" households of the working classes, as seen through the eyes of the children. However, in many cases, gentrification involves families, and children are then actively involved in the local cohabitation relationship. This is the issue at the heart of this article: to examine the experiences of social diversity of children from different social backgrounds aged 9 to 11, living in a gentrified neighbourhood in Paris. We will do so by investigating successively their representations of and activities within the neighbourhood, their usage of a public space which occupies a key position (the local park), and their sociability. On the basis of these analyses, we will show how, within this gentrified neighbourhood, the children "play" with social diversity.

Le goût des autres. Gentrification told by children i

Since the pioneering work of Ruth Glass in the 1960's on the social revitalisation of an old working class neighbourhood in the centre of London "invaded" by housing belonging to the middle and upper middle classes *Glass, 1964+, "gentrification" has been the subject of numerous works [Atkinson and Bridge (dir.), 2005;[START_REF] Lees | Gentrification[END_REF]Authier and Bidou-Zachariasen (dir.), 2008]. Within this group, many authors have been interested in the residential co-existence in these areas, which, considering the more and more prominent social divisions in the urban spaces of the inner city, constitute relatively rare -and lasting -examples of social diversity ii . Yet in these gentrified (or gentrifying) neighbourhoods few works have attempted to understand the relationship between the "gentrifying" households of the middle and upper-middle classes and the "gentrified" households of the working classes, as seen through the eyes of the children. Gentrification is certainly not always a tale of families and children. In some contexts, it concerns mainly single people or young childless couples [START_REF] Dansereau | La réanimation urbaine et la reconquête des quartiers anciens par les couches moyennes : tour d'horizon de la littérature nord-américaine[END_REF][START_REF] Van Criekingen | Réurbanisation ou gentrification ? Parcours d'entrée dans la vie adulte et changements urbains à Bruxelles[END_REF]. But many circumstances of gentrification involve family households from diverse social backgrounds.

In these cases, children are actively involved in the relationships of residential coexistence. Like their parents, they are residents of these neighbourhoods, examples of the ways and means of co-existence. Moreover, as these ways and means are more or less defined by the parents [START_REF] Valentine | Public Space and the Culture of Childhood[END_REF] they are clear indicators of the relationship that the parents maintain with the social diversity of their neighbourhood. Conversely, through their particular uses of the neighbourhood and their social interaction, children can also influence their parents' co-existence relationships. Analysing the place and role of children in co-existence relationships in gentrified neighbourhoods can, therefore, allow us to develop our knowledge of residential co-existence in circumstances of gentrification, and, in turn, of gentrification. This is both the object and the issue at the heart of this article: to examine the experiences of social diversity of children from different social backgrounds aged 9 to 11, living in a gentrified neighbourhood in Paris, the Batignolles. iii What connection do these children have with their socially diverse neighbourhood? How do they perceive the other children and residents that make up their neighbourhood? What uses do they make of their neighbourhood? What is the relationship between children of middle (or upper-middle) class families and those of the working class? In this neighbourhood, do we notice a "nice mix of children" * Vincent, Ball, 2006: 59] or, on the contrary, a reluctance to mix? How do the parents involve themselves in their children's practices and in their sociability?

To clarify our approach, we will firstly cover the literature relating to gentrification and children. We will then introduce the Batignolles neighbourhood, the school and the class which these particular children attend, explaining our methodology. Finally, we will analyse the social diversity experiences of these children, by examining successively their representations of and activities within the neighbourhood, their usage of a public space which occupies a key local position (Cardinet Park), and their sociability. On the basis of these analyses, we will demonstrate how, within this gentrified neighbourhood, the children "play" with social diversity.

The children: poor parents from works on gentrification

As a study entitled La gentrification à Paris intra-muros recently noted, "the place of families and children in gentrification has (...) scarcely been touched on until now" [Clerval, 2008, p.43]. Gentrification processes were first related to artists, students, etc., who were non family households most of the time, which explains why studies

have not yet turned to families and their children. When they have, authors have tended, in different types of gentrified neighbourhoods, to analyse the schooling strategies of middle class families, either within work focused on gentrification [START_REF] Butler | London calling: the middle classes and the remaking of inner London[END_REF][START_REF] Clerval | La gentrification à Paris intra-muros : dynamiques spatiales, rapports sociaux et politiques publiques[END_REF][START_REF] Collet | Générations de classes moyennes et travail de gentrification. Changement social et changement urbain dans le Bas-Montreuil et à la Croix-Rousse[END_REF], or within a wider range of works on the educational choices of the middle classes [START_REF] Oberti | L'école dans la ville: Ségrégation, mixité, carte scolaire[END_REF][START_REF] Van Zanten | Choisir son école : Stratégies familiales et médiations locales[END_REF]. In a convergent way, these studies show that these families who often vaunt social diversity and for whom the school constitutes an important factor in social reproduction and an accurate gauge of their relationship to social diversity, have tended to favour a "rationale of protection", demonstrated alternatively by a "strategy of avoidance" or by a "strategy of colonisation" of the neighbourhood's state schools. Simultaneously, behind these general trends the research reveals varied schooling strategies closely tied to the families' links to their neighbourhood, alternating between closed and open social attitudes towards those "different from themselves", according to the context, to the gentrifiers and, also, to the age of the children. These works therefore demonstrate that the new generation of gentrifiers are more likely to send their children to school outside the neighbourhood and are less open to social diversity than the "pioneers", that middle class households working in the public sector make use of public establishments more than private sector families, and that the "school avoidance" tendency (of the neighbourhood's public establishments) is more common amongst secondary school children than those in primary education.

In a similar perspective, other researchers have explored the early childcare support choices made by middle class parents in gentrified neighbourhoods. One such study was made by Carol Vincent and Stephen J. Ball [2006] in two gentrified areas of London: Stoke Newington and Battersea. Here, the authors questioned middle class men and women with children aged 0 to 5 on their choices of babysitter or nanny, of childcare, of playgroup and of primary school. As in the aforementioned research, their analysis highlights the differences between members of the middle classes and between the neighbourhoods, with regards to the local and interpersonal dimensions of the middle class. In Stoke Newington, where social diversity is extensive, middle class families, often working in public services, in the media or in associations, find types of childcare relatively open to social diversity. In contrast, in the more gentrified Battersea area, where social diversity is more relative and where the gentrifying population comprises mainly professionals from the City, choices of childcare amongst the middle classes point to, and reveal, an "ethnic and class-based insularity". Some authors have studied the residential choices of middle class families who, rather than settling in the suburbs as is usually the case, prefer to live in the gentrified neighbourhoods in the central city [START_REF] Karsten | Family Gentrifyers : Challenging the City as a Place Simultaneously to Build a Career and to Raise Children[END_REF][START_REF] Karsten | Housing as a Way of Life : Towards an Understanding of Middle-Class Families' Preferences for an Urban Residential Location[END_REF]. In the different contexts observed (Rotterdam, Amsterdam), the motivation for couples to raise their children in these neighbourhoods is very close to that of other, childless gentrifiers: to reduce the time and the cost of transport, to enjoy the social and cultural aspects of the city, and to live in an area with a diverse population of varying lifestyles. But here again, as vaunted as this "diversity" may be, the "social anchorage" of these families appears limited: their social networks are in fact composed of individuals and families of similar class, ethnicity, family situation and values in urban life. And in the make-up of these networks, children play an important role: they link these families who live in close proximity, those links becoming opportunities for mutual help and for the exchange of services and advice. Equally, as in previously mentioned studies, the analyses reveal variations between the different contexts. In Rotterdam, for example, the social networks of middle class families are less mono-ethnic than in Amsterdam. Within this literature, researchers have therefore focused their attention on middle class families more than working class families, no doubt in part because the latter are harder to investigate [START_REF] Clerval | La gentrification à Paris intra-muros : dynamiques spatiales, rapports sociaux et politiques publiques[END_REF][START_REF] Oberti | L'école dans la ville: Ségrégation, mixité, carte scolaire[END_REF]. This lack of studies is problematic because working-class families are also residents of these gentrified neighbourhoods in their own right. Furthermore, these authors have studied coexistence relationships more between parents than between children, arising from surveys conducted amongst those parents, and not the children themselves, who are themselves a legitimate category of residents of these neighbourhoods. The authors have also favoured the question of schooling (and educational choices), at the expense of a wider and more systematic analysis of co-existence relationships in the various public areas of gentrified neighbourhoods (shops, parks, after school clubs, etc.). Similarly, these works do not add a great deal to our knowledge of the ways and means of living together of middle class and working class children in gentrified neighbourhoods, outside of the school walls. iv However, within Children's Studies, many researchers have focused on children's daily lives in non-gentrified urban areas: they have shown the changing nature of children's urban practices, their decreasing presence in public spaces, their loss of spatial freedom and the institutionalization and the insularization of their uses [START_REF] Holloway | Children's Geographies: Playing, Living, Learning[END_REF][START_REF] Chawla | Growing Up in an Urbanizing World[END_REF]Christensen, O'Brien, 2003;[START_REF] Valentine | Public Space and the Culture of Childhood[END_REF]. These studies recognize the importance of place in shaping children's urban practices, and a few studies have concentrated on children's daily lives in segregated contexts by highlighting the multiple spatial practices of children of different social and ethnic backgrounds depending on the neighbourhood in which they live [START_REF] Karsten | Growing Up in Amsterdam: Differentiation and Segregation in Children's Daily Lives[END_REF]O'Brien, 2003+. In addition, a few researchers while lamenting the scarcity of studies on children's social networks, have recently focused on the implications of children's decreasing spatial autonomy on their social network: they have showed how it resulted in a decline of social cohesion or in other terms in a sharpening of segregation patterns [Weller and Brugel, 2010;[START_REF] Karsten | Children's Social Capital in the Segregated Context of Amsterdam: An Historical-Geographical Approach[END_REF].

By building on these studies and by focusing on the case of a gentrified neighbourhood in Paris, this paper proposes to examine the children's practices and ways of living together, through the example of 9-11 year old schoolchildren v in a state school in the Batignolles .

The Batignolles neighbourhood, the school and the class

The Batignolles, in the 17 th arrondissement of Paris, is widely considered as an "intermediary" neighbourhood *Bernard, 2004+, both geographically and socially, compared to the working class Epinettes to the north of the Avenue de Clichy and to the bourgeois Monceau area to the south of the rail tracks (Fig. 1).

(Insert Fig. 1)

A strong working class neighbourhood in the 1950's, the Batignolles subsequently suffered several decades of demographic and socio-economic decline, before a revival, starting in the 1990's, with growth led by a back to the city movement of the middle classes. Today, with 25,500 residents, it is a socially heterogeneous area: executives and superior intellectual professions make up 52% of the employed population, side by side notably with workers (6%), employees (14.8%), and the retired (18.7% of the total households) vi . This social diversity should be considered in light of the structure of the habitat: in this neighbourhood of modest five or six storey buildings, small apartments are still predominant; furnished rentals and social housing also allow accommodation for the less wealthy households. The structure of incomes highlights the social disparity of the neighbourhood's inhabitants, the incomes of the households in the first decile approximately being ten times greater than those of the last decile.

In addition, contrary to more central and trendier gentrified areas of Paris inhabited by young couples with no children or by single people [START_REF] Clerval | La gentrification à Paris intra-muros : dynamiques spatiales, rapports sociaux et politiques publiques[END_REF], it is a family The class we chose consists of 27 children, 14 girls and 13 boys. These children live in different family setups: 14 children live with both their parents and 13 are from single parent or "reconstituted" families. As is the case for the whole school, the parents of this class have very diverse professions from lawyers, biologists, journalists, to caretakers, cleaners, taxi drivers, etc. All in all, working class children account for the majority (16 children out of 27) and the socio-professional composition of the class is the opposite of that of the neighbourhood. Added to this social diversity is a great cultural diversity, as 17 of the children have at least one foreign parent (Portuguese, Tunisian, Moroccan, Algerian, Turkish, Polish, etc.) and two of them are of Caribbean origin. More often than not these two dimensions (social background and cultural origins) overlap, but not always.

Geographically, 17 of the children live in the Batignolles and 10 of them live nearby, in the working class Epinettes area. These differences in location are very much linked socially: all but two of the upper middle class children live in the Batignolles. On the contrary, there are as many working class children living in the Batignolles as there are in the Epinettes (Fig. 1). For two of the children the family setup is more complex; the parents are separated, with one parent living in the Batignolles and the other in the Epinettes. In both cases the children spend more time at their mother's household, which for one is in the Batignolles, for the other in the Epinettes. viii Within the class, we can distinguish three distinct groups: upper-middle class children who live in the Batignolles (9 children), working class children who live in the Batignolles (8 children), and working class children who live in the Epinettes (8 children) ix . In most cases, these children have lived in their households since birth and have attended the same school since the age of 7. But a few of them moved to the area more recently and have attended the school for a shorter period.

To understand the ways of living of these children, we have proceeded through two stages. Firstly, we asked them to draw their neighbourhood x . Then, we interviewed them all individually, for approximately fifteen minutes, based on a set of 7 photos of the Batignolles, among which were the local library, Cardinet Park, a shopping street, the market, the entrance to the metro, the neighbouring private school and a square situated towards the edge of the neighbourhood. These photos, which the children were invited to comment on, allowed us to appreciate their knowledge and representations of the neighbourhood, but also, through a series of questions linked to each photo, to collect broader information on their usage of the neighbourhood, their movements within and outside the area, and on their sociability. To complete the data, we also had a discussion with the children's teacher, as well as with a few parents.

"The neighbourhood of happiness"?

In general, the children know the Batignolles neighbourhood well. Most of them had no trouble in identifying the various photos. That was the case for all of the uppermiddle class children living in the Batignolles (of the two upper-middle class children living in Epinettes, just one of them recognised all the photos). It was also widely the case for the working class children of the area. Only half of the working class children living in Epinettes, though, were able to clearly identify all the places. The photos which proved the most problematic were those of the neighbouring private school, of the shopping street and of the square situated on the edge of the neighbourhood (which some children -including those living in the Batignolles -do not consider as part of their neighbourhood).

As well as being well-known, the Batignolles neighbourhood is also greatly appreciated, by both the upper-middle and working class children who live there. Within this positive feedback, which one of the (working class) children summarized by labelling his drawing "the neighbourhood of happiness", the children give particular weight to the presence of the parks, friends, sometimes family, and also, the proximity of shops: *Do you like your neighbourhood?+ "Well, yeah, we can do lots of things, there's a new park, there's a second park not far away, we don't go that often, we've got shops, it's good". (Paul, UMC) "I like it, it's nice. I like to wander around, because sometimes I see people I know, so it's nice. I've got lots of friends who live next to me, I've got family, so it's nice. We see each other often, we have fun, there we go". (Antonia, WCF).

For some of the children, this positive feedback is often tempered with the appearance of some disadvantages. : "Sometimes the people aren't very nice" (Martin, UMC) "There are loads of bottles on the ground" and "sometimes, there are too many fights in the street". (Jessica, WCF)

The analysis of the usage of the gentrified Batignolles by the children reveals other differences. Some children clearly make great use of this socially diverse space: they often go to shops and markets, they regularly visit the library, they practise sporting and artistic activities locally, etc. Conversely, other children, who do not have these habits, make very little use of the neighbourhood. In addition to this quantitative criterion, a qualitative analysis allows to distinguish the nature of the children's practices: some children regularly visit the public areas of the Batignolles (the shops, the market or the parks), whereas others are more likely to be found in the library, the local cinema, or taking part in one of the extra-curricular activities organised by the school on Wednesday afternoons. Furthermore, according to the children, the usage made of this neighbourhood is more or less strongly defined by the parents, who may or may not accompany them in their movements around the area. Finally the children also partake in a range of activities outside of the Batignolles, which gives a purpose to what they do -or cannot do -within the Batignolles. For example, some children are involved in other clubs (sporting, musical, etc.) xi ; other children, or even the same children, visit Paris' museums; others, still, will be regular visitors to nearby shopping centres, etc.

More precisely, the upper-middle class children living in the Batignolles tend to have an intense and multiple usage of the neighbourhood. This is the case for 5 out of the 9 children who belong to this type of family. For all the children, this usage is supervised by their parents and is accompanied by activities and "specific" outings outside the neighbourhood: learning music at the Conservatoire; visiting museums in Paris; going to Monceau Park situated in the adjacent "bourgeois" neighbourhood... Three other children from this type of family also go to the shops, the library or the cinema, often frequently, but do not partake in any activities near their homes. These children, less "anchored" in their area, are characterised by a significant social life -made up of outings and activities -outside the neighbourhood. The final child in this category has a far more limited usage of the neighbourhood, and in particular of the public spaces, and his local activities (Wednesday activities, catechism) are strongly supervised. This is undoubtedly in no small part due to his living in the area with his mother while he spends every other weekend at his father's house (with a garden) in the suburbs with his half-siblings. xii Within the population of working class children living in the Batignolles, two subgroups become apparent. Half of them has an under-developed usage of the neighbourhood, essentially limited to going to the shops. These children do not visit the library, barely go to the cinema and do not partake in activities (sporting or cultural) in the neighbourhood (considered too expensive by one of them), or outside it. The other half, on the contrary, is characterised by a considerable usage of the neighbourhood: the children regularly go to the shops, the market and the cinema, less often to the library, and some of them partake in the organised Wednesday activities and the catechism classes given in the neighbouring private school. In this second group, some of the children also have activities going on outside the Batignolles.

Finally, the working class children living in the Epinettes very rarely make use of the Batignolles. They never (or rarely) go to the area's shops (because their parents do their shopping elsewhere), they do not visit the cinema or the library and they do not partake in other activities, in that area or anywhere else. In other words, they live very much "at a distance" from the gentrified neighbourhood, not only geographically but also socially. In this group, two girls, who both indulge in relatively distinctive activities outside the Batignolles neighbourhood (dancing, tennis, chess), and one boy, who attends catechism classes, do, however, have a more extensive usage of the Very often referred to as the favourite place in the neighbourhood, for both Batignolles and Epinettes children, or as the place which they would choose if they were to take one photograph of their neighbourhood, this park is greatly appreciated by the children in the class, "because it's big, there are lots of people, there are lots of friends" (Jessica, WCF), "because there's noise, there are games, there's lots of things" (Samantha, WCF), even if some often point to there being "too many people" or "too many older kids". It is also an area visited by all the children interviewed, whether it is mainly at weekends, sometimes on Wednesdays, rarely during the rest of the week, after school, or even during the holidays. But this border space is not used with the same regularity by everyone. Where some children are there "every Saturday and Sunday" (Paul, UMC) or "more than once a week" (Jessica, WCF), others conversely go "not very often" or "not much", like Olivier (UMC) who prefers to spend his weekends playing with his "little brother" in his father's garden in the suburbs. This varied usage is first and foremost related to the children's gender. Accordingly, all of the boys in the class use the park very regularly, with the exception of Olivier. This intense usage is not shared by the girls, as 6 (out of 14) of them cannot be found there regularly. Cardinet Park appears in fact to be a more regular haunt of working class children than of upper-middle class children (13 out of 16 claim to go there "very often", compared to 7 out of 11 in the other category). Unlike the gentrified neighbourhood of the Batignolles, it also comes across as a more working class space, where working class children and adolescents, more often present and in greater numbers, "set the tone locally" *Chamboredon, Lemaire, 1970+. This is revealed in the discussions held with some of the upper-middle class children's parents:

"Batignolles Park, it seems to have a lot of people in it, and as a result, it's not great" (Mother of Lou) "It's great to have a park, a green space. (...) And it's wrecked by people who are so out of control that they vandalise public property. They've just broken a building which was for toilets. They broke everything in the building. There was lots of violence, and damage to material in the park. It's terrible". (Mother of Olivia, who also refers to the "bad company" in the park).

Added to the differences in regularity are other distinctions which relate to the how the children get to the park. Most of the time the children go to Cardinet Park accompanied by one or both of their parents, usually the mother. But nearly half of the children often go to the park without parents. Some go with friends, others (or the same children on different occasions) with an older brother, an older sister or a cousin, and some even go alone. These different configurations are far from random, as the following table shows:

(insert Fig. 2) Amongst the upper-middle class children, visits to the park are always supervised, by parents or by friends, except in one case (a boy). And for some of them, the use of this space is only allowed under parental supervision. This strong regulation appears closely tied to the impressions that some parents have of this place: *Do you ever go to Cardinet Park alone?+ "No, never, because my mother says it's not great there; sometimes they say it's full of scum". (Paul, UMC) On the contrary, working class children will more readily visit Cardinet Park without their parents. If some of these children will alternatively go with parents or friends, in two cases this is the only way they get to the park. In addition, within this group, two children -again, two boys -sometimes go to the park alone.

Within the park, the children do numerous activities: soccer, basketball, tennis (Paul, UMC), scooter, roller-skating, rollerblading (Constantin, UMC), badminton and scooter (Jessica, WCF), jogging (Cindy, WCF), etc. But more than just a playing field, Cardinet Park is a place where the children meet their friends. More often than not, these are classmates or school friends. But they can also be close neighbours, or friends from primary school (who subsequently went to another school in the area), or even, more exceptionally, friends they have met in the park. In some cases, cousins -who also live in the neighbourhood or elsewhere in Paris -replace or complement the friends.

Like the school, and more than the gentrified neighbourhood, this haven of child sociability is a space where children from different social backgrounds rub shoulders with each other. But in order to understand more precisely how this mix works between upper-middle and working class children, we must first examine their sociability networks and habits.

From places to connections: the children's sociability

The information gathered from the discussions with the children and their teacher The boys tend to meet their classmates in the park. Girls are partial to this meeting place too, but are more likely to invite their friends round to their homes than the boys, for a snack, a birthday or a pyjama party. Equally, upper-middle class children are more likely to invite their school friends to their home than working class children, in part because the former category have homes more suited to receiving guests than the latter. But this propensity to invite is also undoubtedly a result of some of the parents' desire to bring the social relationships of their children into the home, and therefore control them. For example, Olivier (UMC) frequently invites round -a little too frequently for his mother's liking -his working class friends, who mostly live in the Epinettes, yet he never goes to their homes. Similarly, Lou (UMC) invites Cindy (WCF) (who also lives in the Epinettes) to her home, but does not pay her any visits in return. xiii For most of the children, these school friends, whom they meet just as often outside of school, form their principle network of relationships. But in the Batignolles or sometimes outside, the children often have other relationships: primary school friends attending another state school in the neighbourhood, friends met through various activities, neighbours they bump into, or even -although very rarely -friends from the neighbouring private school (out of the 27 children in the class, only 3 have friends from this private school). In addition, several children have cousins -in their neighbourhood or elsewhere in Paris -with whom they play regularly, in their homes or in Cardinet Park, or whom they visit (this is the case for 8 out of the 16 children from working class families, and only 3 out of the 11 children from upper-middle class families).

Following the trends of their parents [START_REF] Héran | Comment les Français voisinent[END_REF], upper-middle class children are more likely to accumulate friendships through their multiple activities [START_REF] Karsten | Growing Up in Amsterdam: Differentiation and Segregation in Children's Daily Lives[END_REF]].

And very often the relationships forged by these children outside their network of school friends, in the neighbourhood and beyond, involve children from the same social background, guaranteeing the return to a certain social equilibrium when compared to the school friendships, which are often with children from working class families. Such is the case for Jeanne, who has friendships at school with girls from working class families whom she meets at Cardinet Park or whom she invites to her home, and also has friendships with girls from the same social background as herself, who live in her building, and/or who attend the neighbouring private school, or who live outside the Batignolles but with whom she shares the same leisure activities. But this double trend for accumulation and social re-equilibrium is not followed by all the children of this category; in Paul we have an example of a child who has few relationships, at school or elsewhere.

In comparison, working class children have less varied interpersonal networks. What is more, they tend to mix with children from the same social background as themselves outside of school, and in particular with members of their extended families (cousins, etc.). Antonia is one such child; she is friends with Alissa (WCF) and Jeanne (UMC) at school, but only ever invites Alissa to her home ("We're always together, always inviting each other round"). As a further illustration, Sophie has two friends from working class families at school, Samantha and Cindy, and two friends from upper-middle class families, Lou and Olivia. But outside of school, Sophie only mixes with Samantha, in Cardinet Park (Cindy and Lou rarely go to the park and Olivia never does), and two other girls from working class families who are her neighbours.

For some of these children this trend towards social introversion outside of school, encouraged by the small numbers of children from upper-middle class families in the park, by the greater proximity of the family, by the disinclination to invite home children from other social backgrounds, only serves to double the social segregation observable at school. Lilian (a boy's name in France) is a prime example of this phenomenon: at school his only friend is Thomas, a child from a working class family of Portuguese origin, like him. Outside of school he mixes with Thomas in Cardinet Park, and spends a great deal of time -in the park and at home -with his cousins, also of Portuguese descent. But once again these trends do not apply to all the children of this category, as is shown by Jessica's friend network and sociability. She, like Lilian, lives in the Batignolles. At school Jessica is friends not with girls from working class families but with those from upper-middle class backgrounds. And outside of school, Jessica regularly visits their homes, she equally invites them to hers, and they also meet up in Cardinet Park.

The networks and sociability of the children, at school or outside, are therefore differentiated, between children of working class families and children of uppermiddle class families, but also within these categories. Far from being a simple reflection of geographical distance and proximity (between the children's homes), the varied combinations observed here point to more global trends of social diversity, or, conversely, social introversion.

Openness to social diversity and introversion

The joint acknowledgement of the children's connection to places, in Cardinet Park, but also beyond (through their activities and outings) and the links between themselves, in school and outside, highlights different ways of "playing" with the social diversity of the neighbourhood.

On the whole upper-middle children in the Batignolles are typified by a real social openness to working class children. In line with the school choices of their parents, who opted for the neighbourhood's state school, these children have diverse social relationships and make real use of the different spaces in their neighbourhood. But this social openness, which is equally common amongst girls and boys, is strongly supervised by the parents. This parental supervision takes many forms: in accompanying the children in their usage of the neighbourhood and in particular of Cardinet Park, in the fact that the children are more likely to receive other children in their homes than they are to meet them in the park, and in the fact that the children are often signed up to "distinctive" activities outside of the neighbourhood. In other words, everything is in place to facilitate and encourage social diversity for these children, but these mechanisms simultaneously ensure it is controlled and nonexclusive. Behind these general trends, differences are to be found within this category of children. Certain boys, for example, with absent fathers and working mothers, are less regulated in their usage of the neighbourhood and Cardinet Park, as well as in their relationships. Another example, from the other side, is Olivia; she rarely meets children from working class families outside of school and has a very limited and supervised use of the neighbourhood. She does not take part in the activities organised at the school on Wednesdays, she does not go to Cardinet Park, and her nanny systematically accompanies her in all her movements within the area.

Her mother expresses a critical and disenchanted view of the neighbourhood, and her social life is organised for her very much outside of the area.

Amongst working class children, two distinct categories become apparent. On one side are children who, through their usage of the Batignolles and Cardinet Park, and through their relationships, show a certain openness to social diversity, which appears less structured for them than it is for upper-middle class children. On the other side are children for whom social diversity is very limited, and who, in some cases, are characterized by a strong social introversion towards children of other backgrounds. The latter category, who have little or no contact with their classmates from upper-middle class families, who make almost no use of the gentrified Batignolles, are those who come from the most underprivileged households (their parents are unemployed, clothes-makers, cleaners...) and who, for this reason, live more often than children from the first category, but not always, in the Epinettes.

Within the first sub-category, is a unique group of children, who all live in the Batignolles, and who combine an openness to social diversity with a strong cultural introversion. Antonia is one such child, as she mixes with upper-middle class children, makes extensive use of the gentrified neighbourhood and Cardinet Park, and yet she also attends catechism classes in Portuguese, spends a great deal of time with her Portuguese cousins who live nearby and speaks Portuguese with her parents at home.

Conclusion

In the gentrified Batignolles neighbourhood there is a real mix between the working class children and the upper-middle class children (or, more accurately, between the working class children and the upper-middle class children whose parents have chosen to send to the local state school). In other terms, the children display a strong "goût des autres" compared to the limited interactions between adults from workingclass and from upper-middle class backgrounds, which several studies on gentrified neighbourhoods have highlighted [START_REF] Simon | La société partagée. Relations interethniques et interclasses dans un quartier en rénovation[END_REF][START_REF] Butler | London calling: the middle classes and the remaking of inner London[END_REF][START_REF] Lehman-Frisch | Gentrifieurs, gentrifiés : co-habiter dans le quartier de la Mission (San Francisco)[END_REF].

Thus, the observation of the children's practices and of their ways of living together in gentrified neighbourhoods allows to highlight other ways of living together in these neighbourhoods and to reveal understudied aspects of the gentrification processes.

On the whole, contrary to the results brought forward by most studies on social mix (from [START_REF] Chamboredon | Proximité spatiale et distance sociale. Les grands ensembles et leur peuplement[END_REF] to [START_REF] Launay | Les politiques de mixité par l'habitat à l'épreuve des rapports résidentiels[END_REF]), this paper highlights that social mix is not exclusive of social relationships between individuals of different social backgrounds xiv .

But this social mixing comes in many different forms in the school, in Cardinet Park, and in other areas of the neighbourhood. In other words, there is no obvious continuity in the cohabiting relationships between the children from different social backgrounds, at school or in the wider area. For example, some children from uppermiddle families cohabit in a privileged way at school with children from working class families, but blend more willingly with children from the same social background as their own at home, in the neighbourhood or beyond. The same is true for working class children. These results show that it is necessary not to confine the analysis of children's co-existence to the school environment, as is usually the case of the studies of sociology of education [START_REF] Van Zanten | Choisir son école : Stratégies familiales et médiations locales[END_REF]) and of gentrification. At the same time, they prove the importance for studies on children of analysing "the relationship between children's social networks at school and in the neighbourhood" *Karsten, 2010: 4]; like Lia Karsten has underscored recently, this is still a largely underresearched focus in Children's Studies, which should obviously be developed.

What is more, our study shows that this social mix does not affect all the neighbourhood's children equally, and can take a different form from one child to the next (including through parental supervision). More precisely, it appears that these children's rapport with social diversity varies according to their place of residence, between boys and girls, between working class families and upper-middle class families, and, also, within these two categories xv . To better understand these differences, but equally to see how the co-existence relationships of the children of this gentrified neighbourhood structure the co-existence relationships of their parents, it would be useful to compare these children's experiences of social diversity with the co-existence relationships of their parents and with their views on social diversity. This is one of the aims of the next stages of this research. i Le goût des autres (The Taste of Others in English) is a French film directed by Agnes Jaoui [1999] which deals with the relationships between individuals of different social backgrounds with different "cultural" tastes.

Illustrations:

ii In this article, the notion of social diversity refers to the presence of socially differentiable peoples within a certain space. It does not prejudge the nature of the relationships between these peoples.

iii This neighbourhood constitutes one of the fields of study of ongoing research, financed by the Caisse Nationale des Allocations Familiales, on cohabitation relationships in gentrified "family" neighbourhoods, in Paris, London and San Francisco. iv In France, and more widely in francophone social sciences , this meagre interest in children is not exclusive to works on gentrification: there are relatively few works associated with children [START_REF] Sirota | Eléments pour une sociologie de l'enfance[END_REF] and in particular very few studies on their urban habits [Danic, Delande, Rayou, 2006]. v We have chosen to focus on this age range because studies showed that children start to be more independent in their mobility in the neighbourhood when they reach the age of 8 years old [START_REF] Danic | Enquêtes auprès d'enfants et de jeunes : Objets, méthodes et terrains de recherche en sciences sociales[END_REF]. In addition, we wanted to investigate their practices before they enter Middle School (11-12 years old) because middle schools are less often located in the neighbourhood of their homes. vi The data mentioned in this section are extracted from the 2007 INSEE Census. They refer to the "Batignolles" IRIS (census tracts) number 1 to 6, 12 and 13 and the two "Epinettes" IRIS number 2 and 6, which as a whole correspond to our study area. The perimeter of the latter is smaller than the "Batignolles" district defined by INSEE, which is composed of 16 IRIS. avoidance of the state school system by certain families, and the variations this may lead to in their practices and representations of the neighbourhood, we have also investigated, within the bounds of our research, children from a private school in the same neighbourhood. In this article, these children are not taken into account.

viii Equally, two other children live in the Batignolles neighbourhood with their mothers and regularly spend the weekends with their fathers in the Parisian suburbs.

ix Two more children are from middle-upper middle class families and live in the Epinettes.

x See [START_REF] Lehman-Frisch | Draw me your neighbourhood': A gentrified Paris neighbourhood through its children's eyes[END_REF].

xi As Lia Karsten has shown in another context [START_REF] Karsten | Growing Up in Amsterdam: Differentiation and Segregation in Children's Daily Lives[END_REF], the activities undertaken outside of the neighbourhood are socially differentiated: 6 of the 9 middle class children living in the Batignolles are involved, compared to only 3 of the 8 of the two working class categories of children (Batignolles and Epinettes). There is also a clear sex divide within these activities: 5 of the 6 working class children in question are girls.

xii The two other children (two girls) from upper-middle class families who live in the Epinettes also have a limited usage of the Batignolles.

xiii According to the teacher, Lou's mother would prefer her daughter to invite another girl in the class (Olivia (UMC)) home, rather than Cindy.

xiv This study does not aim to analyze the impact of these interactions on the social construction of children.

xv This rapport varies also according to the cultural origin of the children, as shown by the case of Antonia. But as regards the Parisian neighbourhood of the Batignolles, this is not a determining factor. The "cultural" (or "ethnic") aspect certainly plays a more important role in the other gentrified neighbourhoods which we have chosen for our study (in London and San Francisco) in the structuring of cohabitation relationships between children.

  neighborhood and more precisely a neighborhood of young children. Admittedly the households with children do not represent a greater share of the population in the Batignolles than in Paris or in the 17th arrondissement. But the children below 15 years old are overrepresented (15.3% vs. 14.4% in Paris) and 69% of the children (aged 18 or younger) are between 0 and 10 years old. These young children are very obvious in the daily life of the neighbourhood. On Saturday or Sunday mornings, the narrow pavements of the rue des Moines or the alleys of the covered Market can be extremely busy, quickly congested with prams and the patter of tiny feet. In fine weather the density of families and children in "Cardinet Park" (officially named Martin L. King Park and devoted to children of all ages) or in Batignolles Square (for younger children only) is extraordinary.In this neighbourhood the children interviewed in this study all belong to a CM1 class (aged 9 to 11) in a state school (211 children in total, spread out over 10 classes from CP (age 6-7) to CM2 (age 10-11)). vii Like the neighbourhood, this school is socially diverse. In attendance are children from very modest and from wealthier backgrounds. Coupled with this social diversity is a certain variety in the origins of the families, the school being made up of 21 different nationalities, where some children of French nationality also have foreign roots.

  Batignolles.The socially diverse Batignolles neighbourhood is therefore occupied in a very unequal way by the children of the class. Comparatively, Cardinet Park appears more of a shared space."Cardinet Park": a shared space "Cardinet Park", a 4 hectares park opened in 2007, consists of play areas for small children, medium-aged children and adolescents, a basketball court, a clay football pitch, a skate park, a wall for ball games and various green spaces. It acts as a linking area between the Batignolles (to the south-east) and the working class areas of the north of Paris, and in particular the Epinettes.

  allows us to gauge both the interpersonal affinities of the children in the class as well as their sociability outside school, in their homes, in Cardinet Park, in the Batignolles neighbourhood and beyond. In the class we observe "a nice mix of children" *Ball, Vincent, Kemp, 2004+. Of the 27 children, 22 of them have affinities with at least one child from a different social background to their own. Only 3 (working class) children have affinities uniquely with one or more child from the same background as their own, and two other (uppermiddle class) children do not have very developed social relations with the other children of the class. This social mix does, however, appear better established amongst upper-middle class children than their working class peers. In the first category, 4 children have "mixed" relationships, shared between upper-middle and working class children, and 5 children have relationships exclusively or predominantly with working class children. In the second category, 9 children have relationships predominantly or exclusively with working class children, 3 children have mixed relationships and 4 children have relationships mainly with upper-middle class children. In this domain, residential location is not a discriminating factor. Working class children whose "school friends" are mainly working class are certainly more often those who live in the Epinettes. But it is not the case of all the Epinettes children, and two of the three working class children who have affinities solely with other working class children live in the Batignolles. Similarly, being a girl or being a boy is not a determining factor in the social layout of the school friend network, neither in the first category nor in the second. Unsurprisingly, however, the children's affinities are very gender orientated: inside or out of the classroom, boys are friends with boys, and girls are friends with girls. These relationships based at school are often continued beyond the school walls, in the children's homes or in Cardinet Park, to different extents depending on the child.

Fig. 1 :Fig. 2 :

 12 Fig. 1: The Batignolles, a gentrified neighbourhood of Paris Fig. 2: Whom do the children go to the park with?

vii In France, state primary school admissions are based around local catchment areas, meaning they are, by definition, neighbourhood schools. In order to gauge the extent of possible

Translated from French by George McGairl.