Matheus A Souza

Pedro Henrique Penna

Matheus M Queiroz

Alyson Deives Pereira

Luís Fabricio

Wanderley Góes

Henrique Cota De Freitas

Márcio Castro

Philippe Olivier

Alexandre Navaux

Jean-François Méhaut

Pedro Henrique Souza

Penna

F W Luís

Góes

Henrique C Freitas

Philippe O A Navaux

Jean-Franc ¸ois Méhaut

CAP Bench: a benchmark suite for performance and energy evaluation

Keywords: benchmark, low-power, many-cores, network-on-chip

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

INTRODUCTION

Computer Architecture is a research field that is largely based on a rapid evolution of processors in order to support the high demand for performance in software development. The ever-increasing amount of data to be processed demands large scale platforms that are able to surpass the petaflop barrier and deliver exaflop performance. However, the development of large scale platforms with exponentially scaling performances also led to an exponential growth in power consumption. This problem was also pointed out by the Defense Advanced Research Projects Agency (DARPA) in their report [START_REF] Bergman | Exascale computing study: Technology challenges in achieving exascale systems[END_REF], which states that current trends are insufficient to achieve exascale systems due to power and energy consumption constraints. This concern is now enough to warrant the research on the use of low-power many-core processors [START_REF] Francesquini | On the energy efficiency and performance of irregular application executions on multicore, {NUMA} and manycore platforms[END_REF][START_REF] Padoin | Performance/energy trade-off in scientific computing: the case of arm big.little and intel sandy bridge[END_REF]. Indeed, several research efforts are looking for alternatives to place a large number of processing cores inside a single chip to increase the processor's efficiency [START_REF] Shalf | Exascale computing technology challenges[END_REF][START_REF] Simon | Barriers to exascale computing[END_REF][START_REF] Asanovic | The landscape of parallel computing research: A view from berkeley[END_REF].

In this context, the use of busses and crossbar switches as global interconnection mechanisms is no longer viable when scalability is necessary, due to physical wire-related constraints, such as low bandwidth, signal attenuation, delays due to the long wire sizes, and concurrency [START_REF] Ho | The future of wires[END_REF][START_REF] Dally | Route packets, not wires: on-chip interconnection networks[END_REF]. To address this issue, Networks-on-Chip (NoCs) have emerged as an appealing approach for interconnecting a large number of cores [START_REF] Guerre | Hierarchical network-on-chip for embedded many-core architectures[END_REF][START_REF] Bjerregaard | A survey of research and practices of network-on-chip[END_REF]. The Multi-Purpose Processor Array (MPPA-256) is a state-ofthe-art low-power many-core processor designed by Kalray that embraces such structure, featuring 16 multi-core clusters of 16 cores each, totaling 256 cores in a single chip. In this architecture, clusters are interconnected by two NoCs. It is a next-generation many-core architecture built for low energy consumption that may be potentially used to attain exaflop performance with better energy efficiency [START_REF] De Dinechin | A clustered manycore processor architecture for embedded and accelerated applications[END_REF][START_REF] Castro | Analysis of computing and energy performance of multicore, numa, and manycore platforms for an irregular application[END_REF].

To make efficient use of such many-core processors, parallel applications developed for them must efficiently exploit both shared and distributed memory programming models [START_REF] Francesquini | On the energy efficiency and performance of irregular application executions on multicore, {NUMA} and manycore platforms[END_REF]. In MPPA-256, for instance, applications must use a shared memory model inside multi-core clusters, whereas they must use a specific Application Programming Interface (API) that implements a NoC Inter-Process Communication (IPC) model to exchange data between clusters. Writing code for such hybrid models demands deep knowledge about the target architecture. Unfortunately, most programmers are used to develop code based on the shared memory paradigm, which is the usual programming model for multi-cores. These challenges increase the complexity in the effective use of NoC-based many-core processors.

Another important issue concerning these emerging architectures is performance evaluation. Even though several benchmark suites have been previously proposed to assess the performance of multicore processors, they are not suitable for conducting analyses on low-power many-core architectures [START_REF] Ramachandran | Performance evaluation of nas parallel benchmarks on intel xeon phi[END_REF][START_REF] Woo | The SPLASH-2 programs: Characterization and methodological considerations[END_REF]. There are three main reasons for that. First, they were not designed to accommodate the greatly increased number of cores. Work units are either too small or outnumbered, which leads to load imbalance and thus poor performance. Second, they do not deal effectively with low-power many-core memory constraints such as limited amounts of on-chip memory and the absence of cache coherence protocols. The use of smaller memory units might be a key aspect in many-core architectures in order to achieve low-power consumption [START_REF] Shiue | Memory exploration for low power, embedded systems[END_REF]. Third, they are not usually designed to specifically exploit platform-dependent features, such as vector processing units or NoCs, which might demand a specific understanding about how to deal with them.

New research efforts are needed to efficiently deal with NoC-based many-core architectures, since they are the state-of-the-art for future exascale computing. However, both industry and academy are now facing challenges on software development and performance evaluation of the emerging manycore processors. For instance, when new architectures based on different programming models such as MPPA-256 come up, they have no accompanying software to address these issues upon their arrival. Fortunately, this stalemate may be resolved by open benchmarks that are able to encourage programmers and demystify the architecture.

In this paper we discuss the design of an open benchmark suite (CAP Bench) to provide a solution to evaluate energy consumption and performance of low-power many-core architectures. As a case study, we used CAP Bench to evaluate an emergent state-of-the-art low-power many-core processor called MPPA-256 and to assess whether MPPA-256 can be used as an alternative for energy-efficient High Performance Computing (HPC). To the best of our knowledge no benchmark is available to be used as baseline to design, program, evaluate and learn about MPPA-256. Besides being used and validated specifically on MPPA-256, CAP Bench also features an OpenMP implementation of all applications. This implementation can be used in shared-memory many-core architectures such as the Intel Xeon Phi [START_REF] Jeffers | Intel Xeon Phi Coprocessor High Performance Programming[END_REF] and the Mellanox TILE-Gx [START_REF] Fleig | Evaluation of adaptive memory management techniques on the tilera tile-gx platform[END_REF], the PULP platform [START_REF] Rossi | Energy efficient parallel computing on the pulp platform with support for openmp[END_REF], as well as in full-system simulators such as Gem5 [START_REF] Binkert | The gem5 simulator[END_REF].

This paper is organized as follows: Section 2 presents an overview of related work. Section 3 quickly introduces the MPPA-256 architecture. Section 4 presents the design method used throughout the development of the benchmark suite. Section 5 discusses the algorithms available in CAP Bench as well as their main characteristics. An evaluation of the benchmark applications is presented in Section 6. Finally, Section 7 concludes this paper and suggests future research paths. The need for energy-efficient processors led to the development of low-power many-core architectures. Early studies such as the GigaNetIC [START_REF] Niemann | A scalable parallel soc architecture for network processors[END_REF], the CHNoC [START_REF] Leng | Implementation and simulation of a cluster-based hierarchical noc architecture for multi-processor soc[END_REF] and the MCNoC [START_REF] Freitas | Noc architecture design for multi-cluster chips[END_REF] focused on NoC aspects. Currently, cluster-based architectures are under development such as the SMYLEref many-core [START_REF] Kondo | Smyleref: A reference architecture for manycoreprocessor socs[END_REF] and a cluster-based multi-core SoC [START_REF] Tang | Design for prototyping of a parameterizable cluster-based multi-core system-on-chip on a multi-fpga board[END_REF]. The STHORM/P2012 project [START_REF] Mottin | Smart Multicore Embedded Systems, chap. The STHORM Platform[END_REF], which is developed by CEA and ST Microeletronics, and the Parallel Ultra-Low-Power Processing-Platform (PULP) [START_REF] Rossi | Energy efficient parallel computing on the pulp platform with support for openmp[END_REF], a joint project between groups at ETH Zurich and UNIBO, are also under development. Both were designed on cluster-based NoCs towards low-power many-core architectures with strong similarities to the already mentioned MPPA-256 platform.

With regard to benchmark suites, several ones have already been proposed to assess the performance of multi-core processors. In this section, we first underline the main aspects of the most popular ones, and then discuss why these benchmark suites are not suitable to evaluate emerging low-power many-core processors such as the MPPA-256.

The NAS Parallel Benchmark (NPB) [START_REF] Bailey | The NAS parallel benchmarks[END_REF] was developed at NASA Ames Research Center in 1991 with the goal of testing the performance of highly parallel supercomputers running scientific applications. NPB originally consisted of five parallel kernel benchmarks and three simulated applications that were developed to resemble Computational Fluid Dynamics (CFD) applications. The benchmark applications were implemented in C/Fortran77 and involved larger computations than other benchmarks that were available at the time, and therefore were suitable for the evaluation of parallel machines. Additionally, they were conceived to be simple enough to be implemented in new machines without much effort and time.

SPLASH-2 [START_REF] Woo | The SPLASH-2 programs: Characterization and methodological considerations[END_REF] is a parallel application suite proposed in 1995 to study shared-memory multiprocessors. It is composed of 8 complete applications and 4 kernels, representing a variety of scientific, engineering and graphic applications. The paper characterizes the applications with respect to aspects that interfere in their performance, namely: concurrency and load balance; working sets and temporal locality; communication-to-computation ratio and traffic; and spatial locality and false sharing. The authors remark that this characterization was made to help people to better understand the applications and thus to make a more efficient use of them.

In 2006, the Standard Performance Evaluation Corporation (SPEC) announced an update to its benchmark suite CPU2000, introducing CPU2006 [START_REF] Henning | SPEC CPU2006 benchmark descriptions[END_REF]. CPU2006 contains applications implemented in C, C++ and Fortran, inspired by real life applications instead of using synthetic benchmarks. It has a total of 30 benchmarks, of which 12 are integer benchmarks and the remaining 18 are floating-point benchmarks. Each of the applications has a varied set of pertinent inputs and different outputs. One of the intended uses of the CPU2006 benchmark suite is early design analysis of new architectures, hence the focus on including varied, real-world applications.

PARSEC [START_REF] Bienia | The PARSEC benchmark suite: Characterization and architectural implications[END_REF] is a parallel benchmark suite designed in 2008 with the goal of studying Chip Multiprocessor (CMP) architectures. The need for a new benchmark suite is due to old suites being biased towards HPC architectures, as well as using dated implementation techniques and not necessarily being research-friendly. PARSEC is composed of 9 applications and 3 kernels, selected to be as diverse as possible. Several different parallelism strategies are used in the applications. The paper also characterizes the applications with regard to metrics such as locality exploration, plays an important role in many-cores. Furthermore, applications with small work units and load imbalance may not be suitable to evaluate many-core architectures. For instance, the SPLASH-2 characterization reveals that some of the applications present poor performance when the number of cores were greatly increased [START_REF] Woo | The SPLASH-2 programs: Characterization and methodological considerations[END_REF]. The Rodinia benchmark concept is quite similar to ours, however, its characterization does not cover parallel patterns applied to hybrid programming models, which is an alternative in low-power many-core architectures that improves the explicit parallelism and the programming flexibility.

Strategies to address the aforementioned problems could be employed, such as load balance of loop iterations and vectorization. To accommodate these changes, however, these applications would need to be completely remodeled and redesigned to be suitable for use in the aforementioned architecture, which is an endeavor that can be time-consuming [START_REF] Francesquini | On the energy efficiency and performance of irregular application executions on multicore, {NUMA} and manycore platforms[END_REF][START_REF] Castro | Analysis of computing and energy performance of multicore, numa, and manycore platforms for an irregular application[END_REF][START_REF] Francesquini | Improving the performance of actor model runtime environments on multicore and manycore platforms[END_REF][START_REF] Kofman | Application architecture adequacy through an fft case study[END_REF].

Given the above considerations, it is important to evaluate and understand low-power many-core architectures, by setting a baseline, using proper benchmarks, in order to support innovations in the same direction. Our proposal, CAP Bench, also differs from the aforementioned benchmarks since it takes into account a design methodology, which is substantiated in parallel patterns, energy efficiency of many-core architectures and workload balance. This design method will be further detailed in Section 4.

It is worth noting that some of the reported benchmark suites have been proposed in the past decades, thus, they did not cover application design aspects that are essential to conduct evaluations and research on the state-of-the-art many-core architectures, which reinforces the need for new approaches .

THE MPPA-256 MANY-CORE PROCESSOR

MPPA-256 [START_REF] De Dinechin | A clustered manycore processor architecture for embedded and accelerated applications[END_REF] is a many-core processor developed by Kalray which features 16 compute clusters in a single chip. An overview of MPPA-256 is presented in Figure 1(a), and a more detailed view of a compute cluster is shown in Figure 1(b). Each compute cluster is composed of 16 processing cores (named C 0 -C 15 ) and a Resource Manager (RM ), thus totaling 256 processing cores. Processing cores are dedicated to run user threads (one thread per core) in non-interruptible and non-preemptive mode, whereas RM s execute kernel routines and communication services. Each compute cluster has 2 MB of memory shared by the 16 processing cores of the cluster.

MPPA-256 also has 4 quad-core clusters, named I/O subsystems, that make it possible to perform I/O operations, such as getting data from the DDR memory (2 GB) and sending it to compute clusters. A compute cluster cannot directly access the DDR or another cluster's memory. Because

DESIGN METHOD

To enable the design of a benchmark suite to evaluate low-power many-core architectures, MPPA-256 processor was chosen as target and a development method was defined and adopted. Our main goal was to keep the source code as clear as possible, while optimizing the applications to make a more efficient evaluation of the target architecture. This way, the benchmark itself can be easily extended and applications may help new programmers to learn about low-power many-core architectures, MPPA-256 and next generations.

Applications were developed using the C language with two parallel programming libraries: (i) OpenMP 3.0 and (ii) a proprietary Application Programming Interface (API) from Kalray. The former is based on a shared memory model and was used to parallelize the applications inside the clusters and the I/O subsystems. The latter, on the other hand, follows a distributed memory model and was used for inter-cluster communication and for communication between clusters and the I/O subsystem through the NoC. The API is based on the classic POSIX Inter-Process Communication (IPC) with synchronous and asynchronous operations adapted to the NoC and PCI features. It is worth noting that the proprietary API relies on explicit parallelism, in which the work units are totally independent in terms of data and computing. It means that the programmer must use functions and directives from the API in order to determine how the parallelism, with respect to inter-cluster communication, should happen. To actually build applications, the Kalray toolchain that specifically targets MPPA-256 was used.

The first step of the development cycle was the selection of the algorithms. We selected algorithms that solve general scientific problems, such as image processing and clustering. The selected algorithms (Section 5) can be used to develop relevant applications with diverse characteristics with respect to parallel patterns, job types, communication intensities and task loads. We believe that these characteristics are relevant to evaluate MPPA-256.

Once the algorithms were chosen, they were parallelized with OpenMP (shared memory model). This first parallelization allowed us to identify code snippets that would work in parallel units. Different parallel patterns were considered during this process. Several runs of the applications were conducted with the shared memory model. On that stage, after running an application, the perceived results were analyzed and code redesigns were done. This way, the parallel pattern might have been changed in this process, until we get a version that have performance improvements. Once the parallel versions of all applications using the shared memory model were finished, they were tested on MPPA-256 using a single cluster. This allowed us to evaluate the performance of our parallel solutions without any communication overhead. The next step was then to adapt these solutions to a hybrid model, which uses OpenMP inside the clusters and the Kalray API to perform cluster-to-cluster and cluster-I/O communications.

The execution flow on MPPA-256 is the following. The main process runs on an RM of the I/O subsystem and is responsible for spawning worker processes. These processes are then executed on compute clusters and may create up to 16 threads, one for each core (PE) inside them. Figure 2 shows an overview of how this process occurs in MPPA-256.

The I/O subsystem creates one process per cluster using the mppa spawn() function. Communication channels are allocated using mppa open() on the I/O subsystem and on all clusters involved in the communication. These communication channels are associated with preallocated buffers on the receiver's memory. By using these communication channels, the I/O subsystem can perform write operations (mppa write() function) on the memory allocated in each cluster (2 MB) and clusters can perform write operations on the DDR connected to the I/O subsystem (2 GB). Each mppa write() operation executed by the transmitter must be combined with an mppa read() on the receiver. The API allows both synchronous and asynchronous communication. Threads in compute clusters are then created and managed by either OpenMP 3.0 or Pthreads, allowing thread parallelism through the 2 MB shared memory. Once all computations are finished, each compute cluster should call mppa close(), which will be responsible for performing a synchronization with the I/O subsystem (mppa waitpid() function).

Each application was adapted to the hybrid model described before. After that, their performance was analyzed in order to found opportunities for possible improvements. For instance, an empirical study of the impact of the task size on the performance of each application was conducted. We concluded that the tradeoff between communication time and load imbalance is key to achieve high performance on MPPA-256. This study led us to fine-tune the task sizes and communications done through the NoC, which improved the performance of all applications due to a better use of the MPPA-256 resources.

All results presented in Section 6 represent the average values for the metrics considered in this study (i.e., time and energy). Averages were calculated based on the values obtained from at least 10 runs, presenting statistical confidence of 95% by Student's t-distribution and less than 0.7% of relative error. Confidence intervals were omitted from the results due to very low relative error. The rationale behind such a low relative error is due to the fact that there is almost no overhead from the operating system on MPPA-256. For instance, threads within the clusters run without being interrupted by the operating system that runs on the Resource Manage RM .

The MPPA-256 was evaluated with respect to performance, scalability and energy consumption. To measure performance, the applications were executed with small, default and huge input sizes, using 2, 4 and 16 compute clusters, respectively. Then, all applications were executed with all input sizes, varying the number of used compute clusters in a base-2 logarithmic scale (1, 2, 4, 8 and 16 compute clusters) to evaluate both scalability and energy consumption on MPPA-256. Additionally, all applications were executed with the default input size comprising any possible quantity of compute clusters (1 to 16). The energy consumption was collected through the use of specific tools for Kalray MPPA-256, while the executions were conducted.

THE CAP BENCH SUITE

To compose the benchmark, seven applications are proposed, covering a wide range of characteristics. Applications follow five different parallel patterns based on [START_REF] Wilkinson | Pattern programming approach for teaching parallel and distributed computing[END_REF][START_REF] Mccool | Structured parallel programming with deterministic patterns[END_REF]:

F o r P e e r R e v i e w
1. Divide and Conquer, which starts with a division of the problem into small subproblems solvable in parallel, merging partial solutions into a result; 2. Map, where operations are mostly uniform and applied individually over elements of a data structure; 3. MapReduce, which combines Map with a consolidation of results in a Reduce procedure; 4. Stencil, in which a function can access an element in a collection and its neighbors, given by relative offsets; and 5. Workpool, where the algorithm can be divided into independent tasks and distributed among the execution units.

Job types pertain to what resource is critical to the application: the CPU, memory or NoC. When using the MPPA-256, if the time to complete a specific application task is determined mainly by the compute clusters' speed, the application is said to be CPU-bound. If the application time to solution is decided primarily by the amount of memory required, it is said do be memory-bound. In the case of MPPA-256, with limited memory inside compute clusters, it was an effort to adjust the applications to be as little memory-bound as possible. Finally, the application is said to be NoC-bound if the time to solution is mainly determined by the period spent transferring data through the D-NoC. This behavior occurs, for instance, when the task sizes are small, causing high communication intensity.

Communication intensity concerns how often the applications require the use of the NoC. Three levels of communication intensity were defined: low, for applications that do not require the NoC often; average, for applications that make moderate use of the NoC; and high, for applications that rely heavily on the NoC in their operations. It is worth noting that the data sent to compute clusters must not be larger than 2 MB, since the memory space in these clusters is limited. Thus, communication intensities are mainly dependent on the number of times the NoC is required.

Finally, task loads can be regular, if they have the same size, or irregular, if they have diverse sizes due to irregularities in task generation and/or computation.

In the following sections we describe the strategies used to implement these applications for the MPPA-256 processor. These sections are meant to introduce the applications and briefly outline how they were implemented. CAP Bench is open source software and it is available online † .

Features from Accelerated Segment Test -FAST

Features from Accelerated Segment Test (FAST) [START_REF] Rosten | Fusing points and lines for high performance tracking[END_REF][START_REF] Rosten | Machine learning for high-speed corner detection[END_REF] is a corner detection method that follows the Stencil parallel pattern. It is usually used to extract feature points and to track and map objects in computer vision tasks. It uses a circle of 16 pixels to test whether a candidate point p is actually a corner. Each pixel in the circle is labeled from integer number 1 to 16 clockwise. If all N contiguous pixels in the circle are brighter than the intensity of the candidate pixel p plus a threshold value t or all darker than the intensity of p -t, then p is classified as a corner.

In the MPPA-256 implementation, we use randomly generated images as inputs and a mask containing the positions relative to p that must be analyzed. The N value is set to 12 and threshold t is set to 20. Due to very large input images and the compute cluster memory restriction, the I/O subsystem partitions the input image into 256 KB chunks and sends them to compute clusters for corner detection. Such a fine granularity causes intense communications through the NoC. After that, output chunks are sent back to the I/O subsystem, which in turn puts them together to build the output image that indicates all corners present in it. Moreover, the I/O subsystem receives the amount of corners detected by each compute cluster and summarizes them to indicate the overall number of corners detected.

Friendly Numbers -FN

In number theory, two natural numbers are friendly if they share the same abundancy. The abundancy A of a given number n is defined as

A(n) = σ(n)
n , where σ(n) denotes the sum of divisors of n, i.e., σ(n) = d|n d. FN computes and compares the abundancy of all numbers in a given interval [m, n] to determine which pairs of numbers are friendly. The parallel pattern used in FN implementation is MapReduce.

The MPPA-256 implementation uses a master/slave approach. Since every processing task for FN can be executed independently, we split the input interval into equal sized tasks in the master process and distribute them among the compute clusters to be simultaneously processed. These tasks are balanced, causing a regular task load in the slave processes. The abundancy results are sent back to the master process, which then performs abundancy comparisons using the 4 I/O clusters in parallel. This computation is not influenced by the NoC use or memory access, being exclusively CPU-bound.

Gaussian Filter -GF

The Gaussian blur (also known as Gaussian smoothing) filter is an image smoothing filter that seeks to reduce noise and achieve an overall smoothing of the image. It consists in applying a specially computed two-dimensional Gaussian mask (m) to an image (i), using a matrix convolution operation. It uses the Stencil parallel pattern.

In the MPPA-256 implementation, we use randomly generated masks and images as inputs. Since some input images are very large and the compute clusters have a 2 MB memory restriction, the I/O subsystem partitions the image into 1 MB chunks and sends them to compute clusters to be filtered. This is an average chunk size, causing a moderate use of the NoC that in general does not overwhelm the general computation. After the individual chunks are filtered, they are be sent back to the I/O subsystem, which puts them together to build the output image.

Integer Sort -IS

The integer sort problem consists in sorting a very large amount of integer numbers. We implemented a variation of the integer sort problem called bucket sort, which divides the elements to be sorted into buckets. A bucket is a structure that stores numbers in a certain range. The integer numbers used as input are randomly generated and range from 0 to 2 20 -1. IS uses the Divide and Conquer parallel pattern.

In the MPPA-256 implementation, the buckets are further subdivided into minibuckets of 1 MB. As input elements are mapped to the appropriate buckets, they are placed in a minibucket. When the minibucket becomes full, a new minibucket is allocated inside its parent bucket and starts receiving elements. This takes place in the I/O subsystem, which will also send minibuckets for compute clusters to work on. Each compute cluster receives only one minibucket at a time, due to memory restrictions. Inside a compute cluster, minibuckets are sorted using a parallel mergesort algorithm, and as the starting order are random, the task load is irregular. Sorted minibuckets are then sent back to the I/O subsystem to be merged in parallel by its 4 cores. Because of this flow of minibuckets, IS is a high-intensity algorithm in terms of communication, therefore being NoC-bound.

K-Means -KM

K-Means clustering is a data clustering solution employed in clustering analysis. We opted to use Lloyd's algorithm [START_REF] Kanungo | An efficient k-means clustering algorithm: Analysis and implementation[END_REF] in our work. Given a set of n points in a real d-dimensional space, the problem is to partition these n points into k partitions. The data points are evenly and randomly distributed among the k partitions, and the initial centroids are computed. Then, the data points are re-clustered into partitions taking into account the minimum Euclidean distance between them and the centroids. Next, the centroid of each partition is recalculated taking the mean of all points in the partition. The whole procedure is repeated until no centroid is changed and every point is farther than the minimum accepted distance. During the execution, the number of points within The MPPA-256 version of the K-Means algorithm (KM) takes additional parameters p, specifying the number of compute clusters to be used, and t, which specifies the total number of execution flows. Each cluster spawns t working threads, so the total number of threads equals p × t. This strategy causes intense communication between the I/O subsystem and the compute clusters. We first distribute data points and replicate data centroids among clusters, and then loop over a twophase iteration. First, partitions are populated. Then, data centroids are recalculated, which is a memory-intensive process. For this recalculation, each cluster uses its local data points to compute partial centroids, i.e., a partial sum of data points and population within a partition. Next, clusters exchange partial centroids so each cluster ends up with the partial centroids of the same partitions. Tasks in KM are irregular, since the amount of work for each thread may vary during each iteration. Finally, clusters compute their local centroids and send them to the master process.

LU Factorization -LU

LU is a matrix decomposition algorithm which factors a matrix A as a product of two triangular matrices: lower (L) and upper (U ). We opted to implement Gaussian elimination to compute L and U , which requires n -1 iterations, where n is the order of A (always square). In each iteration, a sub-matrix of a smaller order (1 unit smaller) is analyzed, starting from order n. First, the biggest element in the submatrix (pivot) is found. Then, this element is moved to the (1, 1) position, shifting rows and columns appropriately. The line containing the pivot is subsequently divided by itself, thus the pivot element becomes 1. The last step (reduction) aims to nullify elements below the main diagonal. For every line l below the pivot, we multiply the pivot line p by the opposite of the first element e of l and replace l with l + p. We store -e in a separate matrix. After the iterations are finished, every line will have undergone reduction, and the resulting matrix is the U matrix. The L matrix is formed by the -e factors that were stored in the separate matrix. Therefore, both matrices are computed simultaneously. LU uses the Workpool parallel pattern.

Our MPPA-256 solution assigns rows to compute clusters so the largest element can be found. Each compute cluster receives no more than 1 MB of data, in this case, leading to intensive communication. On the other hand, the distributed task loads are regular. The same restriction of 1 MB applies when distributing lines among the compute clusters to apply reduction. Row swapping is done in the master process (I/O subsystem), so the pivot becomes the first element in the matrix. The I/O subsystem is also used to rebuild the L and U matrices from chunks processed in the compute clusters.

Traveling-Salesman Problem -TSP

The Traveling-Salesman Problem consists in solving the routing problem of a hypothetical traveling salesman. Such a route must pass through n towns, only once per town, return to the town of origin and have the shortest possible length. Our solution (TSP) is based on the branch-and-bound method using brute force [START_REF] Castro | Analysis of computing and energy performance of multicore, numa, and manycore platforms for an irregular application[END_REF]. It takes as input the number of towns and a cost matrix, and outputs the minimum path length. The algorithm does a depth-first search looking for the shortest path, pruning paths that have a bigger cost than the current minimum cost. This pruning introduces irregularities in the algorithm, since the depth-first search needs to discard branches depending on the order in which the branches are searched. TSP uses the Workpool parallel pattern.

The MPPA-256 implementation uses a task queue in which tasks are branches of the search tree. Compute clusters take jobs from the queue and run them. The number of clusters and the number of threads define the total number of lines of execution. For each cluster, n threads will be spawned, totaling n threads × n clusters threads. When the minimum path is updated, the new value is broadcast to every cluster so they can also use it to optimize their execution. At the end of the execution, one of the clusters (typically the 0-th) prints the solution. The final solution might be discovered by any one of the clusters, however all of them are aware of it due to the broadcasts of each path update.

Design Decisions

We had to make several decisions in order to develop suitable applications for the MPPA-256. Diverse parallel patterns were considered for each application running on the processor with regard to communication intensities and strategies, job types, and task loads. Table I summarizes the general characteristics of CAP Bench applications that allow for a better use of the MPPA-256 resources.

The applications that deal with image processing, such as FAST and GF, commonly have to take an image data array as input to operate on. The Stencil pattern, used in both FAST and GF, enables the use of low-level operations over highly parallel data that can be optimized by using the numerous MPPA-256 cores. The communication intensities when running FAST are higher than GF due to the chunk sizes, which are bigger in GF. Smaller chunks create more communication between the I/O subsystem and the compute clusters and therefore a heavier use of the NoC. There is a trade-off in FAST, which pertains to the fact that if we increase the chunk size, the compute cluster would become very overloaded by the irregular tasks.

The Divide and Conquer pattern is almost inherent to the bucket sort used in the IS application. This sort of strategy is effective when an optimal number of buckets are used, which is easy to achieve when using MPPA-256. We conclude that a big number of buckets with small sizes generates high communication intensities, by the constant use of the NoC. On the other hand, bigger buckets would not fit on the limited memory size of a compute cluster. Generally speaking, the division of numbers in many independent parallel units has no impact in the sorting algorithm's performance, even though the task load is irregular.

FN and KM use the Map parallel pattern. The former also uses the Reduce pattern. Applications using these patterns scale well in MPPA-256 due to the explicit parallelism of the architecture and patterns. As FN and KM are algorithms with highly independent tasks, the other patterns' results were worse than Map or MapReduce. FN tasks consist of operations over sets of positive integers. Each cluster receives one set of integers, regardless of the input size (i.e., there is only one send and one receive operation per cluster). Thus, FN does not use the NoC very intensely. In the case of KM, the opposite occurs. There is high-intensity communication between the I/O subsystem and the compute clusters to distribute the points.

The Workpool pattern could be easily used in any MPPA-256 application. Given a set of independent tasks, they are distributed by the master process between the slave processes. LU and TSP follow this approach, in which the tasks are coordinated by the I/O Subsystem (master process) (for instance in a task queue) and then delivered to any available compute cluster (slave process). This was the best pattern we found to develop both LU and TSP. The LU application is mainly favored by this pattern because of task regularity. The size of rows sent to compute clusters is the same, leading to balanced computations, improved by the Workpool strategy. Just like in other applications, this brings up the NoC-bound behavior. In the case of TSP application, the data set is smaller, and time to solution is mainly determined by the compute cluster speed (CPU-bound).

In order to enable testing with different workload sizes, we defined 5 input set sizes for applications in CAP Bench: • Default: medium-sized inputs, meant to resemble input sizes of typical application workloads;

• Large: larger-scale inputs, meant to be above-average in resource needs, but not much;

• Huge: very large input sizes, sometimes greater than 1 GB, meant to more thoroughly evaluate the processing and NoC performance.

Each application was designed to fully support all workload sizes. Applications related to image processing, such as FAST and GF, have different symmetric image sizes. FN and IS, which deal with integer numbers, have input parameters that are directly related to these numbers. Thus, the higher the number or the range of numbers, the higher the computation cost. LU is an application that deal with symmetric matrix operations, thus the workload is associated to the size of the matrix. KM is a clustering application that computes a number of centroids based on a set of points. If these parameters are increased, the workload increases proportionally. Finally, in the case of TSP, the number of towns is required in order to determine the computation cost. The addition of a single town in the problem set can substantially increase the computation cost. Table II summarizes the parameters for each application.

RESULTS

In this section we first present a workload analysis of all applications in CAP Bench. Hence, we show the performance scalability and energy consumption results.

Workload Analysis

To point out the main characteristics and potential bottlenecks on all applications, we measured master time, slave time and communication time. Master time corresponds to processing time in the I/O subsystem, and excludes data transfer time or blocking time. Slave time is the average processing time of all compute clusters. Communication time corresponds to the total data transfer time between master and slave processes, and excludes the time spent by the master process waiting for slaves to be ready to send or receive data. We considered a total of ten executions for each application and input size combination, and we observed a relative standard deviation below 1.00%.

The applications were executed with small, default and huge input sizes, using 2, 4 and 16 compute clusters respectively. The results are presented in Table III. Total time in the table corresponds approximately to the sum of master and communication times, since slave time happens in parallel relative to the other two. Frequently, communication time can be close to slave time, which happens because the referred applications use blocking communication in the I/O subsystem.

The results for FN show a predominance of slave and communication time over master time for small and default input sizes, but the opposite occurs for huge input size and 16 compute clusters (a master time of 69.02% of total time). This happens because, as input sizes grow, more comparisons to identify which numbers are friendly have to be made in the master process during the Reduce procedure. Communication times remained constant for the tested input sizes because the amount of numbers to be sent to each cluster during the Map procedure remained almost constant as input sizes and available resources were increased. FN also has regular task loads, which makes the slave time equal for all clusters.

For FAST and GF, results indicate that the majority of the time is spent sending data chunks to compute clusters (an average communication time of 99.54% and 99.21% of total time, respectively). It is worth noting that the communication part refers to blocking communication. These applications, characterized by high or average communication intensities, would benefit from a faster NoC with smaller delays, as well as faster and more numerous compute clusters.

FAST slightly has better communication times than GF due to its smaller chunks, which flow faster through the NoC. The I/O subsystem is not a bottleneck for these applications. A similar behavior can be observed for KM, with the difference that it spends more time in the slave processes relative to communication than FAST and GF do (KM presented a slave time average of 80.94% of total time). This occurs because slave processes in KM run more computationally expensive code than FAST and GF slave processes, therefore requiring proportionally more time to perform their tasks.

A result that immediately draws attention to IS is that the time spent in the slave processes decreases as input sizes increase, with a slave time of 29.29% of total time with 2 clusters and the small input size, 9.21% for 4 clusters with default input size and 1.13% with 16 clusters and huge input size. This means that even though there are more numbers to be sorted they are distributed among more compute clusters, improving the slave time. This behavior corroborates the use of the Divide and Conquer pattern, mainly on the divide phase. Time spent in the master process tends to increase with input, and this is due to the fact that more merge operations need to be carried out in the master process running in the I/O subsystem when inputs are larger.

Communication would be a bottleneck for IS if the minibuckets sent to the clusters were bigger, as IS is really a NoC-bound application. In other words, as the size of the data sent each time is relatively small, communication happens more often, and the NoC is required many times. But the communication time was not excessively large, as shown in Table III, due to the small data packets flowing through the NoC.

For LU, communication is the key performance-halting factor. Even though both the I/O subsystem and compute clusters are used in this application, the vast majority of the total execution time can be attributed to the use of the NoC to send matrix chunks back and forth (an average communication time of 94.95% of total time). This behavior explains the increase in communication time, since more chunks have to be sent for bigger matrices and when more compute clusters are employed.

Communication time is not a bottleneck for TSP, which does not use the NoC heavily in spite of using the same Workpool parallel pattern as LU, a NoC-bound application. Both applications have a pool of tasks to be executed, but LU generates more tasks to be sent to the compute clusters. TSP also spends most of its execution time in compute clusters. However, unlike the GF and KM, little time is spent in communication. This behavior, as mentioned before, can be explained by the fact that TSP performs few data transfers.

Another particularity that is observed in TSP is the great difference between the total and slave time -for the huge input size, for instance, the slave time corresponds to 78.02% of total time. However, this behavior is expected due to the irregularity issue discussed in Section 5.7, related to the branch-and-bound method. This also incurs in a reduction in average slave time, because some threads finish earlier than others, which brings the mean down.

Performance and Energy Consumption

To analyze the overall performance and energy consumption, we executed all the applications using every input size with 1, 2, 4, 8 and 16 compute clusters (Figure 3). We collected the average time-tosolution (TTS) and energy-to-solution (ETS) for the applications to evaluate how they scale when larger inputs and more resources are used. Additionally, a more detailed scaling test was conducted for all applications using the default input size, gradually increasing the number of compute clusters from 1 to 16 (Figure 4). The performance gains mentioned below use executions with 1 compute cluster as base for comparison. For each application and input size we ran the applications ten times, and observed a relative standard deviation below 1.00%.

Energy measurements were obtained from a proprietary tool called K1-POWER, which allows us to collect energy measurements of the whole chip, including all clusters, on-chip memory, I/O subsystems and NoCs when running the applications. According to the Kalray's reference manuals, energy measurements are accurate to within ±0.25 W of the current power draw. In order to clarify how good this accuracy is, Table IV presents a sample analysis of the power consumption perceived on all applications when executed with default input set size. The minimum, maximum and average values of power consumption are presented, with the respective accuracy taking into account the ±0.25 W margin. The worst accuracy value was 92.88% in FN, when running it with one cluster. FAST, FN, GF, KM and TSP have similar well-scaling behaviors, which means that for a determined input size, TTS tends to decrease as more compute clusters are employed. These applications, as we can see in Table I, are all CPU-bound. IS and LU have their TTS mainly determined by the data transfers through the NoC, resulting in worse scalability results than the others.

Other exceptions are KM and GF for tiny input size. The inputs are so small that synchronization operations become a bottleneck as the number of compute clusters increases. Besides that, KM is a Memory-bound application which could not be executed with large input size using 1 compute cluster and with huge input size using 1 and 2 compute clusters, due to the 2 MB memory restriction in them. Concerning the applications that follow the Stencil pattern, the chunks in GF are bigger than in FAST and therefore the compute clusters are less often used by the former.

Regarding energy consumption, the same decreasing behavior is observed in some applications: since consumed power is constant and applications take less time to finish when more resources are used, energy consumption is smaller. FAST, GF, KM and TSP do not rely heavily on the I/O subsystem for their operations, causing TTS and energy consumption to be closely related to the time spent on compute clusters.

On the other hand, the Reduce procedure in FN heavily relies on the I/O subsystem for comparing abundancies. Besides that, it is a CPU-bound algorithm composed of a high number of arithmetic operations. These characteristics led the average power consumption to increase linearly. With that in mind, when changing from 4 to 5 clusters, the average power consumed by FN was more determinant for the energy consumption than the TTS. Changing from 5 to 6 clusters, the power consumption increased slightly, thus, in this case, the TTS was more determinant. Although FN and KM have similar parallel patterns, the latter does not use the Reduce procedure on the I/O subsystem. Nevertheless, the overall time spent in compute clusters in KM substantially surpasses the time spent on the I/O subsystem, causing TTS and energy consumption to decrease as more compute clusters are used. The best execution time results for these applications were obtained with 16 clusters. In tests with 16 compute clusters, FAST obtained a decrease in execution time up to 82.24% and FN a decrease up to 92.91%. In GF, a reduction of about 89.80% was achieved. In KM and TSP, the achieved reduction in execution times was 87.84% and 93.01%, respectively.

In spite of achieving better results with 16 clusters, IS presented a decreasing scalability behavior, which means that performance gains tended to decrease as input set sizes increased. More precisely, the referred gain with 16 clusters was 58.42% with tiny input size, and 14.57% with huge input size. This happened because, as input sizes grow, IS relies more on the I/O subsystem to merge sorted minibuckets in the Conquer phase than sorting the numbers in the compute clusters. Larger input sets mean a larger number of minibuckets to be merged by the I/O subsystem, which in turn causes performance gains to diminish because the I/O subsystem has a constant number of cores and does not perform computations as well as the compute clusters. Regarding energy consumption, Figure 4 shows that IS presented the most irregularities among all the applications in CAP Bench: it decreased proportionally when up to five clusters were used and then it increased almost linearly. This is because when more clusters are used, more communication takes place, causing the average power to increase linearly. The performance behavior is reflected The performance scalability of LU was negligible. Generally, we observed a more significant reduction in execution time when varying the number of compute clusters from 1 to 2. For more than 4 clusters, however, the overall execution time of LU usually increased. This poor scalability is justified by the fact that LU is heavily NoC-bound, and communication was its main performance bottleneck. As we increase the number of compute clusters we also increase the contention on the NoC. As a result, the amount of time spent in communications becomes higher than the amount of processing time. Overall, the highest reduction in execution time observed for this application was 4.21%, which was obtained with 4 clusters and large input size.

Regarding energy consumption, we can see in Figure 4 that it increases in a quasi-linear fashion for LU, except when increasing the number of compute clusters from 1 to 2, when a slight decrease is present. As in FN, the average power consumption in LU increases linearly when more compute clusters are employed. However, LU presented worse energy consumption results due to its poor scalability. The perceptible increase in energy consumption can also be attributed to the more intense use of the NoC, since bigger inputs will require more data chunks to be sent and more compute clusters also require the NoC to work more intensely.

To summarize, CAP Bench scales well enough to study the MPPA-256 architecture and its potential bottlenecks. We believe that CAP Bench applications cover important aspects of lowpower many-core architectures, being useful to study emerging and upcoming low-power manycore architectures in terms of performance, energy consumption and communication bottlenecks. It is worth noting that MPPA-256 has all of the previously mentioned constraints, and the parallel patterns and design decisions related on Section 5.8 proved to be appropriated to address them. For instance, the tradeoffs between the NoC use and the data sizes (chunks) is something that some applications could expose, also pointing out that the NoC speed might be improved in spite of increasing the clusters' memory size. The results corroborate that CAP Bench enables a solid evaluation concerning energy efficiency of current low-power many-core architectures, such as the MPPA-256, and can be further used to evaluate and compare the upcoming ones.

CONCLUSIONS

In this paper we presented CAP Bench, an open source benchmark suite that includes parallel applications suitable to evaluate emerging low-power many-core processors such as MPPA-256. The benchmark contains a diverse set of applications that evaluated key aspects of MPPA-256, namely the use of its compute clusters, I/O subsystem, NoC and energy consumption. We expose development difficulties and potential bottlenecks that can stem from the shift in development paradigm when programming for low-power many-core architectures. The results showed us that different applications can have different performance bottlenecks, which is why a solid knowledge about the low-power many-core architecture is necessary for the development of efficient programs.

Our analysis shows that CAP Bench is prepared for the analysis of low-power many-core processors such as the MPPA-256, being scalable and concerned with new trends on this type of architectures. To achieve good performance and scalability, we developed applications considering aspects such as parallel patterns, load balance and architecture limitations. This allowed us to evaluate several aspects of the MPPA-256.

Our benchmark explores the hybrid programming model, which is a trend in low-power manycore processors, following parallel patterns. This enables us to verify that, in the case of MPPA-256, communication time may surpass computation time, which would ideally never occur. This behavior was highlighted by the LU application available in CAP Bench, which may indicate that the NoC should be improved to achieve better performance on NoC-bound applications. In this manner, CAP Bench comes up with the proposal to identify such bottlenecks, revealing potential improvements that might be done in future many-core architectures.

Application development challenges are still out there, and have to be solved to enable the evaluation of next generation many-core processors. As future work, we intend to incorporate other applications to the benchmark, to make it more diverse and allow for a better characterization of the architecture and its aspects. We also intend to extend the benchmark use to other manycore architectures, to achieve a broader understanding of them and the differences between manycore processors. Another future plan is to collect full-system simulation results to strengthen the hypothesis that CAP Bench can be used to evaluate emerging many-core architectures with specific characteristics. These characteristics could be adjusted in a simulator to reveal strengths and potential bottlenecks of the simulated architecture. Thus, the use of a simulator along with CAP Bench opens up a wide range of possible evaluations of NoC and memory characteristics of many-core processors.

Figure 1 .

 1 Figure 1. Kalray MPPA-256 overview. (a) The chip is composed of 16 compute clusters interconnected by NoCs. (b) Inside each cluster, there are 16 cores that share 2 MB of memory.

  THE CONCURRENCY COMPUTAT.: PRACT. EXPER. CLASS FILE 5 of that, the 16 compute clusters and the 4 I/O subsystems are connected by two parallel NoCs with bi-directional links, one for data (D-NoC), and the other for control (C-NoC). The D-NoC allows any of the compute clusters to write data to the internal memory of other compute clusters. Moreover, it allows the I/O subsystem to write data from the DDR to the compute clusters' internal memories and vice-versa. The way in which communication occurs is covered in Section 4.

Figure 2 .

 2 Figure 2. Kalray MPPA-256 execution flow.

  THE CONCURRENCY COMPUTAT.: PRACT. EXPER. CLASS FILE 9 each partition may differ, implying different recalculation times for each partitions centroid. The parallel pattern of KM is Map.

  THE CONCURRENCY COMPUTAT.: PRACT. EXPER. CLASS FILE 11

  THE CONCURRENCY COMPUTAT.: PRACT. EXPER. CLASS FILE 13

Figure 3 .

 3 Figure 3. Execution time and energy consumption of all applications and input sizes.

Figure 4 .

 4 Figure 4. Detailed execution time and energy consumption results of all applications with default input set size.

  results, with smaller inputs presenting energy consumption gains which dwindle as input sizes augment.

Table I .

 I Characteristics of each application available in CAP Bench.

	App. Parallel Patterns	Job Types	Communication Intensities Task Loads
	FAST Stencil	CPU-bound; NoC-bound	High	Irregular
	FN	MapReduce	CPU-bound	Low	Regular
	GF	Stencil	CPU-bound	Average	Regular
	IS	Divide and Conquer NoC-bound	High	Irregular
	KM	Map	CPU-bound; Memory-bound High	Irregular
	LU	Workpool	NoC-bound	High	Regular
	TSP	Workpool	CPU-bound	Low	Irregular

Table II .

 II Input parameters.

	App.	Tiny	Small	Default	Large	Huge
	FAST 2048 × 2048	4096 × 4096	8192 × 8192	16384 × 16384	24576 × 24576
	FN	8 × 10 6 + 1 to	8 × 10 6 + 1 to	8 × 10 6 + 1 to	8 × 10 6 + 1 to	8 × 10 6 + 1 to
		8 × 10 6 + 2 12	8 × 10 6 + 2 13	8 × 10 6 + 2 14	8 × 10 6 + 2 15	8 × 10 6 + 2 16
	GF	2048 × 2048 (i)	4096 × 4096 (i)	8192 × 8192 (i)	16384 × 16384 (i)	32768 × 32768 (i)
		7 × 7 (m)	7 × 7 (m)	11 × 11 (m)	11 × 11 (m)	15 × 15 (m)
	IS	2 23 integer	2 24 integer	2 25 integer	2 26 integer	2 27 integer
	KM	2 12 R 16 points,	2 13 R 16 points,	2 14 R 16 points,	2 15 R 16 points,	2 16 R 16 points,
		256 centroids	512 centroids	512 centroids	1024 centroids	1024 centroids
	LU	512 × 512	1024 × 1024	1536 × 1536	2048 × 2048	2560 × 2560
		matrix	matrix	matrix	matrix	matrix
	TSP	14 towns	15 towns	17 towns	19 towns	20 towns

Table III .

 III Breakdown of execution times (in seconds) with different number of clusters and input sizes: small with 2 clusters (left), default with 4 clusters (middle) and huge with 16 clusters (right).

	App.	Master	Small -2 Clusters Slave Comm.	Total Master	Default -4 Clusters Slave Comm.	Total Master	Huge -16 Clusters Slave Comm.	Total
	FAST	0.00	0.79	1.02	1.03	0.00	1.58	2.50	2.52	0.0	3.55	13.32	13.40
	FN	7.47 213.94	213.94 221.43	29.90 214.04	214.04 243.95	478.31 214.60	214.61 692.97
	GF	0.00	0.87	1.04	1.05	0.00	3.46	4.11	4.12	0.00	24.09	33.89	33.95
	IS	47.21	18.94	19.69	66.95	93.86	9.66	10.97 104.90	523.89	6.06	11.06 535.09
	KM	0.07	6.89	8.19	8.28	0.38	22.72	25.54	25.97	2.89	42.68	56.17	59.17
	LU	1.92	1.42	36.17	38.63	4.66	2.42	121.06 127.41	14.73	2.93	566.72 589.15
	TSP	0.00	1.88	0.24	2.18	0.01	35.46	0.05	38.66	0.02 254.30	0.73 325.94

Table IV .

 IV Power consumption sample analysis (in Watts) of all applications with default input set size.

	App.	Minimum Accuracy Maximum Accuracy Average Accuracy
	FAST	4.14	93.96%	4.34	94.24%	4.24	94.10%
	FN	3.51	92.88%	9.22	97.29%	6.34	96.06%
	GF	4.16	93.99%	4.35	94.25%	4.25	94.12%
	IS	4.06	93.84%	4.73	94.72%	4.37	94.28%
	KM	4.51	94.46%	7.70	96.75%	6.31	96.04%
	LU	4.31	94.20%	6.88	96.37%	5.49	95.45%
	TSP	4.34	94.24%	7.96	96.86%	6.28	96.02%

http://mc.manuscriptcentral.com/cpe Concurrency and Computation: Practice and Experience

ACKNOWLEDGMENTS CAP Bench was born from a joint initiative involving four research groups: Computer Architecture and Parallel Processing Team (CArT) at Pontifical Catholic University of Minas Gerais (PUC Minas), Compiler Optimization and Run-time Systems (CORSE) at Laboratoire d'Informatique de Grenoble (LIG), Distributed Systems Research Laboratory (LAPESD) at Federal University of Santa Catarina (UFSC) and Parallel and Distributed Processing Group (GPPD) at Federal University of Rio Grande do Sul (UFRGS). This work was supported by FAPEMIG, FAPERGS, FAPESC, CNPq, CAPES, INRIA and STIC-AmSud and was developed in the context of EnergySFE and ExaSE cooperation projects.


Tayeb Lemlouma
email: tayeb.lemlouma@irisa.fr

Sébastien Laborie
email: sebastien.laborie@univ-pau.fr

Philippe Roose
email: philippe.roose@univ-pau.fr

Toward a Context-Aware and Automatic Evaluation of Elderly Dependency in Smart Homes and Cities

Keywords: Dependency, activities of daily living, smart home, smart city, services, service composition I

In this work, we propose a framework for automatic dependency evaluation that can notify the changes of the elderly dependency, hence providing persons with required services in time. In order to validate our approach, we target the French dependent population. Especially, we focus our proposal on the AGGIR dependency model used in the French medical field. Our objective is to provide a flexible architecture and an extensible model linked to opened data that can refer to a wide variety of services (hardware sensors and software; simple or composed services).

INTRODUCTION

According to the United Nations projections [1], in 2050, the old-age dependency ratio of the population aged 65 years or over will approximate 51,70% of the population aged 20-64. For instance, this ratio will approximate 48,2% in France, 62% in Germany and 44,10% in UK (Fig. 1). In healthcare domain, the evaluation of the autonomy or dependency of a person is of high importance. Indeed, such evaluation is used by the professionals of health to identify the person's needs of assistance, services and allowance. Also, it allows taking the right decision about keeping the person in the health institution, nursing home or independently at home with or without healthcare monitoring. In a smart home environment, and more globally in a smart city environment, particular attention and care should be made for dependent people, in particular for elderly since they are left on their own at home or in the city. A continuous dependency evaluation is of high concern since it can detect the changes regarding the person's abilities to achieve elementary daily tasks. In this work, we propose a framework for automatic and flexible dependency evaluation that can notify any changes of the elderly dependency and hence allows providing him, in time, with required help, assistance and allowance. We consider the heterogeneity of elderly profiles and service sources that can come from anywhere from the home or the city. The dependency evaluation takes benefits from the description model of the elderly and the dynamic composition of services. Our approach considers the activities of daily living (ADL) as used in the French AGGIR (Autonomy Gerontology Iso-Resources Group) model [START_REF] Aggir | The national standardized instrument determining the attribution of the specific dependence allowance in France[END_REF]. The automatic way in observing the different elderly activities allows avoiding human errors and patient's ignorance that face the current use of the AGGIR tool and similar evaluation methods used in geriatrics.

II. RELATED WORK

The person's dependency can be defined as the ability of a person to achieve elementary tasks of daily living without the help or stimulation of a third party. In the geriatrics domain, different methods and tools have been defined to evaluate this dependency using different factors, such as age, medical status, mobility, fall risk, etc. The main reason of the existence of such different methods is the determination of what is a basic activity of daily living (ADL, called also BADL). Methods are mostly based on the ADL definitions of Katz [START_REF] Katz | A measure of primary sociobiological functions[END_REF], Barthel [START_REF] Mahoney | Functional evaluation: the barthel index[END_REF] and the instrumental daily activities (IADL) of Lawton [START_REF] Lawton | Assessment of older people: Selfmaintaining and instrumental activities of daily living[END_REF]. Among these very numerous scales, we cite for instance RAI [START_REF] Achterberg | Het resident assessment instrument (rai): een overzicht van internationaal onderzoek naar de psychommetrische kwaliteiten en effecten van implementatie in verpleeghuizen[END_REF], AGGIR, SMAF [START_REF] Herbert | The functional autonomy measurement system (smaf): despcription and validation of an instrument for the measurement of handicaps[END_REF] and MOS SF-36 [START_REF] Horney | Measuring and monitoring general health status in elderly persons: practical and methodological issues in using the sf-36 health survey[END_REF]. In the evaluation tools, the notion of group is used to define a set of persons with common characteristics in terms of needs to healthcare assistance and help. For instance, we find the Diagnosis Related Groups (DRG) in USA [START_REF] Fetter | Case mix definition by diagnosis related groups[END_REF] and the iso-resource group (GIR) in France [START_REF] Aggir | The national standardized instrument determining the attribution of the specific dependence allowance in France[END_REF].

We notice that most of these evaluation methods are achieved using questionnaires and manual scales, and are consequently subject of human errors or patients ignorance. Various research efforts, like [10][11][12][13] [START_REF] Rantz Marilyn | Automated technology to speed recognition of signs of illness in older adults[END_REF], investigate the automatic (or semi-automatic) context aware monitoring of elderly activities.

In [START_REF] Gu | Toward an OSGi-Based Infrastructure for Context-Aware Applications[END_REF], an OSGi-based infrastructure is proposed for smart homes in order to build context-aware services based on an ontology model. A middleware (SOCAM) was presented and includes services that perform context discovery, acquisition and interpretation. In the proposed architecture, the required intensive computation delays (due to the logic reasoning and context processing) are inconvenient in the context of providing services to dependent persons. Furthermore, it is not easy to integrate heterogeneous services provided by third party. Le et al. presented in [START_REF] Le | Health Smart Home -Towards an assistant tool for automatic assessment of the dependence of elders[END_REF] a system for activity recognition using a set of presence sensors. The considered activity is limited to the detection of mobile and immobile states of elders. Immobile states are identified from the observation of elder's daily life.

The study in [START_REF] Thomas | Improving the Validity of Activity of Daily Living Dependency Risk Assessment[END_REF] focuses on the prevention of ADL dependency through models of elderly dependency risk. The analysis of models is based on the interview of an important set of self-respondents with different interview models including cognitive measures. The work in [START_REF] Kokkinos | Local Geometrically Enriched Mixtures for Stable and Robust Human Tracking in Detecting Falls[END_REF] discussed fall detection and identification using a new algorithm based on visual cues that exploits robust and stable foreground object tracking methods. In [START_REF] Franco | Behavioral Telemonitoring of the Elderly at Home: Detection of Nycthemeral Rhythms Drifts from Location Data[END_REF], the authors propose a method using sensors for detecting abnormal changes in the resident's behavior. It focuses on the detection and quantification of a potential nycthemeral shift in activity through a statistical approach. The work is based on infrared sensors placed in each room of the resident's home. The work in [START_REF] Rantz Marilyn | Automated technology to speed recognition of signs of illness in older adults[END_REF] describes a system that monitors elderly in order to automatically detect signs of illness. The system is based on an early illness detection using a set of medical sensors that report data for visualization and interpretations by healthcare professionals, such as nurses and doctors. The considered environment by the proposed system is a clinicallike system that focuses on significant health events. These characteristics make difficult and less flexible the integration of the system in a home or a city-like environment.

Our approach aims to make the use of the dependency evaluation methods automatic and more flexible. This is done thanks to the ability of including any kind of services and observation sources. Despite the specification of services per daily activity that we will identify in order to validate our architecture, we do not make any restriction neither on the kind of the used services (hardware sensors, software or manual inputs) nor in data sources used in handling the elderly dependency. Our framework takes benefits from the collaboration of these different sources and opened technologies that facilitate the processing of heterogeneous services and sources. Our proposed approach considers the main activities of daily living as a whole and does not focus on a particular activity like some previous work. This choice is done because of the heterogeneity of the monitored elderly persons; also, we believe that when a dependency degree changes, this is the consequence of not only one activity of the person but also several of them. Consequently, such changes should be quickly notified to healthcare providers.

III. CONTEXT AWARE AND AUTOMATIC EVALUATION OF DEPENDENCY

Most of context-aware approaches refer to the Dey's context definition [START_REF] Dey | Understanding and Using Context[END_REF] as any information that can be used to characterize the situation of an entity. An entity includes a person, a place or an object. This work focuses on the evaluation of the dependency in order to help healthcare professionals to provide services and monitoring without keeping persons in the health institution. Hence, the context considered in this work is represented by a set of the different variables that influence the elderly dependency evaluation. In order to validate our approach, we target the French dependent population and in particular elderly dependent persons. In France, in order to evaluate the needs of an elderly person in terms of medical assistance and allowance, the AGGIR model is used [START_REF] Aggir | The national standardized instrument determining the attribution of the specific dependence allowance in France[END_REF].

Like other dependency evaluation scales, the AGGIR evaluation is achieved manually by a medical reviewer, such as the referring doctor or a medical assistant. Each daily activity of a dependent person is qualified by the medical reviewer using the four possible adverbs: Spontaneously (S), Completely/Totally (T), Usually (U) and Correctly (C). The S adverb means that activity can be done without any stimulation. The T adverb means that all of the actions involved in the activity can be done by the person. The U adverb means that the activity is done regularly; the frequency of the execution depends to the nature of the activity. The C adverb involves the quality of person's realization, safety and conformance with the recommended usage of the activity. According to a logical condition involving these adverbs, the activity is evaluated with the modalities: A, B or C. A given activity is evaluated with the modality A, if the person can achieve the activity with the following condition: S∧T∧C∧U; the condition of the C evaluation is: ¬S∧¬T∧¬C∧¬U; the B evaluation is given if the previous conditions are not satisfied. The A evaluation means that the person is completely autonomous in achieving the given activity, B means that the person is partially dependent and C means that the person is dependent and cannot achieve the activity alone.

The AGGIR model considers 17 variables describing the activities of daily living, such as the mental coherence, hygiene and mobility. Each variable evaluates the dependency degree of achieving a given activity. Based on a multivariate analysis involving more than 5000 persons, the model has identified 10 discriminated variables, 8 of them are used in the classification of the dependent persons into 13 profile ranks and 6 groups. The 13 profile ranks concern the losses of autonomy of dependent persons. The 6 groups, called iso-resource groups or GIR, reduce the number of profile ranks and concern the needs of assistance and allowances. The GIR algorithm computes the iso-resource group number (1 to 6) based on predefined association between profile ranks and groups. For instance, the rank 1 is associated to the GIR 1, ranks from 2 to 7 are associated to the GIR 2, etc. (Table I.). The first group (GIR 1) represents the persons that are completely dependent while the last group (GIR 6) represents autonomous persons.

To identify the profile rank of a person, the model uses 8 classification functions that compute the classification scores. The person is classified as belonging to the profile rank for which he/she has the highest classification score (Table I.). Scores conditions are tested in a sequential order of the classification functions from S 1 to S 8 . Classification functions are defined as:

S i =
, where, S i is the score of the i'th function; w ij is the weight for the j'th variable modality (i.e., A, B or C). II.). To identify the profile rank, the score conditions are tested first with the S 1 score, if there is no satisfied condition, the score is then tested with S 2 and so forth until the last condition of S 8 (S 8 < 2000). Here, the score of S 1 (3332) does not satisfy the S 1 score conditions (Table I.). However, the score of S 2 (2760) satisfies the "S 2 ≥ 2016" condition (Table I). Hence, the person's profile rank is 4 and his iso-resource group is 2. We propose to encode inside a person profile the required information that concerns the patient itself (i.e., name, address, age, etc.) and all the values (i.e., A, B and C) that correspond to the 8 evaluation variables. Of course, each time a new evaluation of a person is made, we aggregate the results in the profile and attach to it a specific date in order to confront different evaluations, thus sending notifications if needed. Figure 2 shows an example of a person profile that corresponds to a potential instance of an evaluation process. The beginning of the profile shows details about the patient. In the illustrated example, the profile is related to a person named John Doeuf, which is 55 years old. Thereafter, for a specific date, some values of the evaluation variables are detailed. As illustrated in the figure above, we have proposed an RDF/XML serialization [START_REF] Beckett | RDF/XML Syntax Specification (Revised)[END_REF] of a person profile for the following reasons: • RDF descriptions [START_REF] Manola | RDF Primer[END_REF] allow us to easily perform aggregation of descriptions, which can be useful if several applications handle and maintain profile data that concerns the same person. Since our objective in this paper is to automatically fill in the person profile (especially, for determining the output values of the 8 evaluation variables) thanks to services, we propose to enhance our profile model by referring to, for each variable, the service description and a confidence value. For instance, in Figure 2, the Coherence variable value (i.e., C) has been computed thanks to a specific service with a high confidence value, i.e., 0.9 (confidence values are set between 0 and 1, the higher the value is, the higher is the confidence). Of course, thanks to the service URI, here http://127.0.0.1/sensor01/rawdata#SensorOutput, it is possible to access to other descriptions that concern the service details, e.g., the service characteristics, the service location, the service owner, etc. Based on the person profiles, we have performed the simulations of all the possible activities evaluations within the six GIR groups. For instance, Figure 3 illustrates the ratio of each variable's modality in the iso-resources group 2 and 3. Our simulations have leaded us to identify the most characteristic daily activities of each dependency group. The objective is to identify what are the most likely activities that could be negatively affected when the dependency of a person changes. Consequently, given a dependency group of the person, some identified activities have to be given high priority in monitoring and observing them. From our simulations, we model the dependency changes with a transition graph between all of the 24 modalities (8 variables with the A, B and C modalities) from a group N to a group N-1. Only the transition from a group N to a group N-1 is considered because when a dependency change occurs, the current dependency group passes always first by the direct lower group. When a change in the dependency of a person occurs, this implies that the person is no longer able to achieve some daily activities. The new evaluation of such key activities should be negative (i.e., evaluated B or C). Given a current dependency group N, in order to identify priority services for the detection of the dependency changes:

(1) we only focus on the variables of the group N-1 with a negative modality (B or C) and a high ratio δ regarding the size of N-1 group's population, then (2) we keep only the transitions with an increased ration from a variable modality of the current group N to the new group N-1. Figure 4 shows an overview of the results regarding the dependency change from the group 3 to 2. If we fix the ration δ at 40%, identified priority services will concern the following activities (Fig. 4): Transfers (a change with the modality C from 8,58% to 60,16%), Eating (modality C from 19,04% to 52,28%), Coherence (modality C from 25% to 43,8%) and Orientation (modality C from 25,87% to 43,14%).

IV. PROPOSED ARCHITECTURE SPECIFICATION

The use of traditional sensors (temperature, video, sound, presence, etc.) helps in detecting Activities of Daily Living (ADL) [START_REF] Monaci | Neuropsychological screening performance and the association with activities of daily living and instrumental activities of daily living in dementia: baseline and 19 -to 24 -month follow-up[END_REF] (e.g., hygiene, toilet use, eating, resting, and dressing). In order to detect such ADL variables, it does not exist one unique sensor. Only a composition of several ones can provide an interesting measure. In the following part, we identify and review for each variable of the AGGIR model various configurations in order to detect and measure each variable in our architecture (Fig. 6).

A. Variables:

• Coherence: SF-36 Health Survey questionnaire [START_REF] Nygrena | Resilience, sense of coherence, purpose in life and self-transcendence in relation to perceived physical and mental health among the oldest old[END_REF] gives information and measure of current coherence. Such questionnaire can be easily designed using our already implemented platform for media services at home through the resident's TV set [START_REF] Lemlouma | Smart Media Services Through TV Sets for Elderly and Dependent Persons[END_REF]. • Orientation: Floor plan and indoor GPS give orientation information and permit dedicated human to measure and/or detect troubles.

• Hygiene: Ultrasonic water flow meter, sound detector, and flush switch. The use of ultrasonic water flow meter can measure the power and water consumption. The number of flushes may give adequate information. In [START_REF] Chen | Bathroom activity monitoring based on sound[END_REF], an automated bathroom activity monitoring system is based on the acoustics information. • Dressing: Dressing door sensor aperture and IP Cam.

Both can give an interesting measure of the quantitative use of the dressing. With human evolvement, the quantitative information can become qualitative in order to give information on the used clothes. • Eating: light switch, door fridge sensor, hob sensors, mixer tap, etc. All those sensors can give information on the use of the kitchen. • Elimination: Ultrasonic water flow meter, sound detector, flushes switch. The same sensors as the hygiene variable may also give information on elimination.

• Transfers: single inertial sensor. The use of inertial sensor-based motion analysis provides information in the longitudinal follow-up. • Internal Moving: Floor plan and indoor GPS help in giving such information. This non-exhaustive list of sensors, multi-sensors and human tasks analysis gives information of the amount of various possibilities for each variable. Moreover, some of them can be useful for several measures. Nevertheless, all those sensors and/or IS data or human activities are all heterogeneous. The heterogeneity is both on data format, contents and access mode (query, notify, regular, etc.). Moreover, according to specific situations (sensor failure, emergency, mobility, etc.), they are not always available and may not give correct information. The use of dynamic composition can complete and give qualitative additional data (Fig. 6). The following section presents a solution based on mediation in ambient environment and ADL oriented architecture with dynamic service composition.

B. General Software Architecture

The particularity of such application is its strong interaction with various heterogeneous devices and services. It raises two problems: a technological one because of communication interfaces (Bluetooth, Wi-Fi, Zigbee, proprietary, etc.) and a logical one (heterogeneity of data). Many existing frameworks have been proposed, we identify Cilia (Fig. 5), which is an open candidate to be the core of such heterogeneity management. "Cilia is a lightweight data mediation and integration service component model, built upon OSGi, the dynamic Java platform. Cilia provides a framework and toolset that simplify the development and the maintenance of large-scale, complex integration solutions that interacts with heterogeneous and complex integrated systems". Such ambient applications also need a dynamic composition of service (logical or physical).

Because of the mobility of users, the availability of devices, the energy consumption, and therefore economy, the orchestration of services aiming at providing high level tasks needs to continuously evolve in order to always being able to achieve its task. Moreover, the availability of services continuously increases and therefore, new available ones must be included in services compositions. Each GIR variable (Coherence, Dressing, Int. moving, etc.) corresponds to a configuration. A configuration is an orchestration (done with BPMN [START_REF] Hangjung | End-to-end reliability of service oriented applications[END_REF][23]) of Cilia mediators, and each mediator will serve as a proxy for services in order to hide and solve heterogeneity problems (access, synchronization, data routing, etc.). The set of services, orchestrations and mediators forms the Architecture Layer. The result of each GIR service will be sent to the GIR Algorithm (also composed of atomic services in order to be dynamically adapted to different contexts and situations). Figure 7 presents our Smart Auto-Dep interface that implements the GIR algorithm and its extension with heterogeneous sources. Variables observations can come from heterogeneous data sources provided by different services (Fig. 6). The interface allows notifying the dependency change if it occurs. Notifications are based on a threshold value after which, if a dependency change is maintained, the notification is sent. The destination of the notification could be, for instance, the person's referring doctor or its medical assistance institution (hospital, clinic, etc., see Fig. 6). The rapid notification of the dependency change allows providing the elderly quick assistance and to consider its needs and allowance as soon as possible.

V. CONCLUSION AND FUTURE WORK

The objective of this paper was to make automatic the dependency evaluation process, which is usually done manually in the medical field. We focused on the dependency change within the medical AGGIR model. Our proposition tried to move the current situation toward a flexible architecture and an extensible model linked to opened data referring to a wide variety of services. We have identified priority variables for the dependency changes according to the context of the elderly (GIR groups). We described our vision of a flexible architecture that includes our implemented Smart Auto-Dep interface, which is ready to integrate various sources (services, sensors and data) and notify the dependency changes. Next steps will be to enrich our proposed RDF model, to explore other dependency models and to experiment the dependency changes with real heterogeneous sensors and services composition.

Figure 1 .

 1 Figure 1. Old-Age Dependency Ratio in France, Germany and UK

Figure 2 .

 2 Figure 2. An Example of a Person Profile Encoded in RDF/XML

Figure 3 .

 3 Figure 3. Variables Modalities Ratios in the Iso-resource Groups 2 and 3

Figure 4 .

 4 Figure 4. Dependency Change from the Group 3 to 2.

Figure 5 .

 5 Figure 5. Cilia Mediation Architecture 1 [21]

Figure 6 .

 6 Figure 6. ADL oriented architecture

Figure 7 .

 7 Figure 7. Smart Auto-Dep Interface

  Table II presents the different weights of the different variables modalities regarding S 1 and S 2 functions. Let us consider the example of a person with the following evaluation: Coherence=C, Orientation=C, Hygiene=C, Dressing=A, Eating=C, Elimination=A, Transferts=A and Interior Moving=B. We have S 1 = =3332 and S 2 = =2760 (Table

	TABLE I.	ASSOCIATION BETWEEN PROFILE RANKS, CLASSIFICATION
			SCORES AND GIR
		Profile Ranks	Score Condition	GIR
		1	S1 ≥ 4380	1
		2	4140 ≤ S1 < 4380
		3	3390 ≤ S1 < 4140
		4 5	S2 ≥ 2016 S3 ≥ 1700	2
		6	1 432≤ S3 < 1700
		7	S4 ≥ 2400
		8 9	S5 ≥ 1200 S6 ≥ 800	3
		10 11	S7 ≥ 650 S8 ≥ 4000	4
		12	2000 ≤ S8 < 4000	5
		13	S8 < 2000	6

TABLE II .

 II WEIGHTS OF THE CLASSIFICATION FUNCTIONS S1 AND S2

	Activity		W1i	W2i			W1i	W2i
	Coherence C 2000 1500 Eating	C	60	60
		B	0	320		B	20	0
		A	0	0		A	0	0
	Orientation C 1200 1200 Elimination C	100	100
		B	0	120		B	16	16
		A	0	0		A	0	0
	Hygiene	C 40	40	Transferts	C	800	800
		B 16	16		B	120	120
		A	0	0		A	0	0
	Dressing	C 40	40	Int. Moving C	200	-80
		B 16	16		B	32	-40
		A	0	0		A	0	0

http://wikiadele.imag.fr/index.php/Cilia