Francisco Chicano

Fabio Daolio

Gabriela Ochoa

Sébastien Vérel

Marco Tomassini

Enrique Alba

Local Optima Networks, Landscape Autocorrelation and Heuristic Search Performance

Recent developments in fitness landscape analysis include the study of Local Optima Networks (LON) and applications of the Elementary Landscapes theory. This paper represents a first step at combining these two tools to explore their ability to forecast the performance of search algorithms. We base our analysis on the Quadratic Assignment Problem (QAP) and conduct a large statistical study over 600 generated instances of different types. Our results reveal interesting links between the network measures, the autocorrelation measures and the performance of heuristic search algorithms.

Introduction

An improved understanding of the structure of combinatorial fitness landscapes can facilitate the design and further successful application of heuristic search methods to solve hard computational problems. This article brings together two recent developments in fitness landscape analysis for combinatorial optimisation, namely, local optima networks (LONs) and elementary landscape decomposition. LONs represent a new model of combinatorial landscapes based on the idea of compressing the information given by the whole problem configuration space into a smaller mathematical object that is the graph having as vertices the local optima and as edges the possible transitions between them [START_REF] Tomassini | Complex-network analysis of combinatorial spaces: The NK landscape case[END_REF][START_REF] Verel | Local optima networks of NK landscapes with neutrality[END_REF]. This characterization of landscapes as complex networks enables the use of tools and metrics of the complex networks domain [START_REF] Barrat | Dynamical processes on complex networks[END_REF] and has brought new insights into the global structure of the landscapes studied in the past [START_REF] Daolio | Local optima networks of the quadratic assignment problem[END_REF].

The QAP has been recently analysed using this model [START_REF] Daolio | Local optima networks of the quadratic assignment problem[END_REF] and the clustering structure of the local optima networks of two classes of QAP instances was studied in [START_REF] Daolio | Communities of minima in local optima networks of combinatorial spaces[END_REF]. The study revealed that the so called "real-like" instances have significantly more optima cluster (or modular) structure than the class of random uniform instances of the QAP problem. Using the theory of elementary landscapes [START_REF] Barnes | A note on distance matrices yielding elementary landscapes for the TSP[END_REF] the QAP has been analysed in [START_REF] Chicano | Elementary landscape decomposition of the quadratic assignment problem[END_REF] and the methodology presented in [START_REF] Francisco Chicano | A methodology to find the elementary landscape decomposition of combinatorial optimization problems[END_REF] has been used to decompose the landscape and provide expressions for each elementary component. This decomposition can then be used to exactly compute the autocorrelation coefficient and the autocorrelation length of any arbitrary QAP instance [START_REF] Chicano | Autocorrelation measures for the quadratic assignment problem[END_REF].

In this article, the expression in [START_REF] Chicano | Autocorrelation measures for the quadratic assignment problem[END_REF] is used to calculate the autocorrelation length of the two classes of QAP instances studied in [START_REF] Daolio | Communities of minima in local optima networks of combinatorial spaces[END_REF]. Since for those instances the LONs were exhaustively computed, the exact number of local optima are known in all cases. This will allow us to support the autocorrelation length conjecture [START_REF] Peter | Biological Evolution and Statistical Physics, chapter Fitness Landscapes[END_REF], which links the autocorrelation length to the number of local optima of a landscape. We also conduct a correlation study among several network metrics calculated on the extracted LONs and the success rate of two heuristic search algorithms: simulated annealing and genetic algorithm. Our goal is to discover relationships between fitness landscape features and the performance of heuristic search methods.

The article is structured as follows. Section 2 includes the relevant definitions, methodologies and metrics used in this article. Section 3 presents the correlation study and Section 4 discusses our main findings and suggests directions for future work.

Background

In this section we introduce all the background concepts required in the rest of the paper. We define the QAP, describe the LONs, introduce the network metrics, the autocorrelation length and describe the heuristic search algorithms used in the experimental section.

The Quadratic Assignment Problem

The QAP is a combinatorial problem in which a set of facilities with given flows have to be assigned to a set of locations with given distances in such a way that the sum of the product of flows and distances is minimized. A solution to the QAP is generally written as a permutation π of the set {1, 2, ..., n}. The cost associated with a permutation π is: C(π) = n i=1 n j=1 a ij b πiπj , where n denotes the number of facilities/locations and A = (a ij ) and B = (b ij ) are referred to as the distance and flow matrices, respectively. The contents of these two matrices characterize the class of instances of the QAP problem.

For the statistical analysis conducted here, the two instance generators proposed in [START_REF] Knowles | Instance generators and test suites for the multiobjective quadratic assignment problem[END_REF] for the multi-objective QAP were adapted for the single-objective QAP. The first generator produces uniformly random instances where all flows and distances are integers sampled from uniform distributions. The second generator produces flow entries that are non-uniform random values. The instances produced have the so called "real-like" structure since they resemble the structure of QAP problems found in practical applications. We consider here these two types of instances and tree problem dimensions: 9, 10 and 11. Therefore, we have six different instance groups. For each group, 100 instances were generated for a total of 600 QAP instances that will be used in our study.

Local Optima Networks

In order to define the local optima network of the QAP instances, we need to provide the definitions for the nodes and edges of the network. The vertices of the graph can be straightforwardly defined as the local minima of the landscape. In this work, we select small QAP instances such that it is feasible to obtain the nodes exhaustively by running a best-improvement local search algorithm from every configuration (permutation) of the search space. The neighborhood of a configuration is defined by the pairwise exchange or swap operation, which is the most basic operation used by many metaheuristics for QAP. This operator simply exchanges any two positions in a permutation, thus transforming it into another permutation. The neighborhood size is thus |V (s)| = n(n -1)/2. Given a local optima s, its basin of attraction is defined as the set of solutions s from which s can be reached using a hill-climbing algorithm [START_REF] Daolio | Local optima networks of the quadratic assignment problem[END_REF].

The edges account for the transition probability between basins of attraction of the local optima. More formally, the edges reflect the total probability of going from basin b i to basin b j , which is the average over all s ∈ b i of the transition probabilities to solutions s ∈ b j . The reader is referred to [START_REF] Daolio | Local optima networks of the quadratic assignment problem[END_REF] for a more detailed exposition.

We define a Local Optima Network (LON) as being the graph G = (S * , E) where the set of vertices S * contains all the local optima, and there is an edge e ij ∈ E with weight w ij = p(b i → b j ) between two nodes i and j if and only if p(b i → b j ) > 0, where p(b i → b j ) is the probability of moving from basin b i to basin b j in one step. Notice that since each optimum has its associated basin, G also describes the interconnection of basins.

Network metrics

We describe below the six network metrics considered in our analysis.

Number of vertices, N v :

The number of nodes of a LON is simply the number of local optima in the fitness landscape. It is exhaustively computed running a best-improvement hill-climbing algorithm from each solution of the search space. Clustering coefficient, Cc : Measures the probability that two neighbors of a given node are also neighbors of each other [START_REF] Barrat | Dynamical processes on complex networks[END_REF]. In other words, it accounts for the ratio of connected triples in the graph. In the language of social networks, it measures how likely it is that the friend of your friend is also your friend. Shortest path length to the optimum, L opt : A standard metric to characterize the structure of networks is the shortest path length (number of link hobs) between two nodes in the network. In order to compute this measure on the LONs, we considered the expected number of moves (in the case of QAP swap moves) to pass from one basin to the other. This expected number can be computed by considering the inverse of the transition probabilities between basins: 1/w ij . We use this to calculate the average shortest paths leading to the global optimum.

Disparity, Y 2 : Measures the local heterogeneity introduced by edge weights [START_REF] Barrat | Dynamical processes on complex networks[END_REF]. It indicates whether the outgoing links from a given node have mostly the same weights (transition probabilities) or there is one outweighing the others. Disparity for a vertex i is computed as

Y 2 (i) = j =i (w ij /s i ) 2
, where s i = j =i w ij is the so-called strength of vertex i. Fitness-fitness correlation, F nn : Measures the correlation between the fitness values of adjacent local optima. More precisely, we estimate with the Spearman rank correlation coefficient the correlation between the fitness value f i of vertex i and its weighted-average nearest-neighbors fitness, defined as F w nn (i) = 1/s i j =i w ij f j . Modularity, Q: Clusters or communities in networks can be loosely defined as groups of nodes that are strongly connected between them and poorly connected with the rest of the graph. To calculate the level of community structure, also known as modularity, we consider a graph clustering algorithm that is based on the simulation of network flow [START_REF] Enright | An efficient algorithm for largescale detection of protein families[END_REF], as in [START_REF] Daolio | Communities of minima in local optima networks of combinatorial spaces[END_REF].

Calculation of the autocorrelation length

Let us consider an infinite random walk {x 0 , x 1 , . . .} on the solution space such that x i+1 ∈ N (x i ). The random walk autocorrelation function r : N → R is defined as [START_REF] Weinberger | Correlated and uncorrelated fitness landscapes and how to tell the difference[END_REF]:

r(s) = f (x t )f (x t+s ) x0,t -f (x t ) 2 x0,t f (x t ) 2 x0,t -f (x t ) 2 x0,t (1)
where the subindices x 0 and t indicate that the averages are computed over all the starting solutions x 0 and along the complete random walk. The autocorrelation length [START_REF] García | Correlation length, isotropy and metastable states[END_REF] is defined as = ∞ s=0 r(s). Using the landscape decomposition of the QAP in [START_REF] Chicano | Autocorrelation measures for the quadratic assignment problem[END_REF] the authors provide a closed-form formula for based on the matrices (a ij ) and (b ij ) of the QAP instance. We will use in the present article this formula to efficiently compute the autocorrelation length of all the instances in our experimental study.

Heuristic search algorithms and the performance metric

We considered two well-known heuristic search algorithms: simulated annealing (SA) and genetic algorithm (GA). The SA uses a cooling factor of 0.9983 and an initial temperature of 10 7 . The neighborhood move is the same used for generating the LONs, namely, the pairwise exchange or swap operation in permutation space. The GA is a steady-state GA with a population size of 100, where one solution is computed at a time and inserted in the population using elitist replacement. The individuals are selected using a binary tournament. The genetic operators are the partially mapped crossover (PMX) [START_REF] Bäck | Evolutionary Computation 1. Basic Algorithms and Operators[END_REF] and the pairwise exchange mutation operation applied with probability 0.3. We perform 100 independent runs for each algorithm and instance.

In order to measure the performance of a search algorithm solving the QAP instances we use the success (hit) rate, defined as the fraction of the 100 independent runs that found the global optimum. Both algorithms stop when they reach 10 000 function evaluations.

Our statistical analysis considers the pair-wise correlation among the six network metrics, the autocorrelation length, and the SA and GA success rates. As mentioned above, six classes of instances are considered, including two types ('uniform' and 'real-like') of instances as described in Section 2.1, and 3 problem sizes 9, 10 and 11. Each of the 6 instance classes is considered separately, and 100 instances conform the sample for the statistical analysis in each class.

The main goal of our study is to discover whether some of the studied metrics can predict the performance of a heuristic search algorithm on a given instance class. We start, then, by showing the performance of the two selected search algorithms: SA and GA. Figure 1 illustrate the range and distribution of the hit rates for each algorithm and instance class, while Table 1 contains hit rate values, number of local optima and the average shortest path length for the instance classes. We show the values of these two network metrics because they seem to have an impact on the hit rate, as we will see later. The results suggest that, for each instance type (uniform or real-like), the hit rates for both algorithms decrease as the instance size increases, with the only exception of GA in the real-like 11 class. This is expected as the size of the search space increases, and so locating the global optimum is harder. However, the hit rates for real-like instances are much higher in all cases, which confirms that these instances are easier to solve for both algorithms [START_REF] Daolio | Local optima networks of the quadratic assignment problem[END_REF]. In Table 1 we can see that real-like instances have a lower number of local optima compared to uniform instances, which explains why real-like instances are easier to solve than the uniform ones. A second observation is that the hit rate of the GA, for a given instance type, does not change much when the size of the instances is increased. However, in SA the hit rate is clearly reduced when the size increases. That is, SA seems to be quite sensitive to the size of the instance (in addition to the type) while GA is clearly sensitive to the type of the instance (uniform or real-like) but little sensitive to the size. Let us consider the correlations between the network metrics, the autocorrelation length and the algorithms' performance. These are shown qualitatively in Figure 2 for the instance sizes 9 and 11. The figure shows that the GA is not correlated to any measure in the real-like instances of large size. Only for the uniform instances and the ones of size 9 there are some significant correlations. We can thus, conjecture that the measures used in this study are not useful to predict the performance of the GA. A possible explanation is the presence of the crossover operator, which introduces an additional neighborhood not used for generating the LONs. On the contrary, the SA algorithm only uses a single move operator (pairwise exchange or swap) which is the same used to generate the LONs. In this case, the Figure reveals correlation with some metrics. In particular, the correlation between the performance of SA and L opt is the highest, which suggests that L opt is the measure that better predicts the behavior of SA.

In Figure 3 we plot the hit rate against some selected measures for SA and GA in the real-like instances of size 11. The plots of the SA and GA are interleaved in order to compare the results of the regression analysis (the regression line is superimposed on the plot). We can observe how the line has a smaller slope in the case of the GA for all the plots, what explains the low correlation for the GA hit rate and the measures. But we can also observe how L opt is a good predictor of the SA performance.

An interesting observation that contributes to explain the robustness of the GA over the problem size is that while hit rate for the SA is correlated with the number of local optima, this is not the case for the GA. This suggests that the global search characteristic of a population in GA makes it more robust to the presence of larger number of local optima.

On the uniform instances, we can observe a positive correlation between the performances of GA and SA, which suggests that the search difficulty is similar for both algorithms in this case. This is observed for all instance sizes although the correlation decreases as the size increases. On the real-like instances, the observation is different. In particular, for the real-like instance of size 11, there is no correlation whatsoever between the performance of both algorithms, which suggests that the search difficulty depends on the algorithm for these instances.

In other words, the hard instances for the GA are not the same as the hard instances for the SA and vice versa. We may also speculate that the GA is more efficient at exploiting the more modular structure of the real-like instance, which makes its search dynamic different than that of the SA on these instances.

Regarding the rest of the measures, in general, the correlations are higher in the uniform instances than in the real-like instances. F nn and Q seem to be the less correlated LON measures (this is particularly true for the real-like instances). (l) GA and Fig. 3. Regression analysis for the hit rate of SA and GA against some selected measures for the real-like 11 instances.

The higher correlation coefficients appear between the clustering coefficient, the disparity, the number of nodes and the path to the global optimum. The autocorrelation length seems to be correlated with these measures and with the performance of SA. This is specially interesting, since the autocorrelation length can be computed from the instance data, without the need to exhaustively generate the complete search space (like it happens with the LON measures). The correlation between and the performance of SA suggests that we can use as a measure of problem difficulty, when a trajectory-based search algorithm is used. This idea is also supported by the results of Angel and Zissimopoulos [START_REF] Angel | On the landscape ruggedness of the quadratic assignment problem[END_REF], which provided a positive correlation between an autocorrelation measure and the performance of a SA. The correlation between and the performance of the GA is much smaller, which again indicates that it is harder to predict the performance of the GA using landscape metrics. Finally, the correlation analysis also provides evidence of the autocorrelation length conjecture. This conjecture claims that the number of local optima is inversely correlated to the autocorrelation length [START_REF] Peter | Biological Evolution and Statistical Physics, chapter Fitness Landscapes[END_REF]. In [START_REF] Chicano | Autocorrelation measures for the quadratic assignment problem[END_REF] some results were presented that supported the autocorrelation length conjecture. In that work, the correlation between the number of local optima and was between -0.1640 and -0.3256. In our case the correlation is higher (in absolute value), in the range from -0.3729 to -0.7187. This support of the conjecture is higher in the uniform instances than in the real-like instances of the same size.

Discussion

We conducted a large statistical correlation study considering QAP instances of different types and sizes, a number of landscape metrics and the performance of two widely known search heuristics. Our study also brings together two recent developments in combinatorial landscape analysis, with the aim of shedding new light on the relationships between the landscape structure and the performance of heuristic search algorithms. Our study confirms that the real-like instances are easier to solve by heuristic search algorithms. Clearly, in these problems, the number of local optima in the landscape is a much better predictor of search difficulty than the size of the search space. As we already knew from the study in [START_REF] Daolio | Local optima networks of the quadratic assignment problem[END_REF], for a fixed problem dimension, real-like instances result in much smaller networks (small number of vertices); the size difference between the two types of QAP instances grows almost exponentially with the problem dimension.

Overall, the GA was a stronger algorithm to solve all the studied classes of QAP instances. Moreover, the GA is more robust to the increase in problem size. Interestingly, the performance of SA and GA is correlated for the uniform instances, but this is not the case for the real-like instances. Which suggests that the GA is better at exploiting the more clustered structure of the reallike instances. However, predicting the performance of the GA seems to be a harder task than predicting the performance of SA. GAs are more complex algorithms as they incorporate a population and a recombination operator. In particular, we found some network metrics such as the average distance to the global optima and the number of local optima, which are good predictors of the SA performance, but less so for the GA. The question is still open for a better understanding and prediction of the GA performance.

Finally, our study provides supporting evidence of the correlation length conjecture indicating that the number of local optima is inversely correlated to the correlation length. This is an interesting contribution, as using elementary landscape decomposition the autocorrelation length for QAP instances can be exactly calculated from the instance data [START_REF] Chicano | Autocorrelation measures for the quadratic assignment problem[END_REF].

More detailed studies, additional metrics, sampling approaches to extract the LONs and larger landscapes are required to better understand and predict search difficulty in combinatorial optimization. Our study, however, is a first step that incorporates new landscape metrics coming from the field of complex networks, and try to correlate them with both previously studied landscape metrics and the performance of heuristic search methods.

Fig. 1 .

 1 Fig. 1. Hit rate of the GA and SA for the 6 classes of instances considered. The boxplots are computed on the results of the algorithms over the 100 random instances per class.

-like instances of size 11 Fig. 2 .

 112 Fig.2. Correlations between the measures. An arrow pointing up means positive correlation whereas an arrow pointing down means negative correlation. The absolute value of the correlation is shown in grey scale (the darker the higher).

Table 1 .

 1 Number of local optima (Nv), shortest path to the optimum (Lopt) and hit rate of the GA and SA for the 6 instance classes. We show the average and the standard deviation.

			Nv	Lopt	GA	SA
	Class	Avg. Std. dev. Avg. Std. dev. Avg. Std. dev. Avg. Std. dev.
		n = 9 131.220 51.268 25.761 11.231 0.220	0.170 0.320	0.200
	uni	n = 10 399.840 153.097 45.217 17.120 0.185	0.190 0.155	0.105
		n = 11 1337.300 453.520 76.815 26.698 0.210	0.175 0.090	0.070
		n = 9	14.300	7.473 8.564	4.343 0.675	0.265 0.585	0.350
	rl	n = 10 26.720 17.775 13.588	7.228 0.610	0.465 0.420	0.240
		n = 11 64.420 47.410 22.508 11.563 0.585	0.370 0.295	0.235

Acknowledgements

This work was partially funded by the Spanish Ministry of Science and Innovation and FEDER under contract TIN2011-28194 (the roadME project) and the Andalusian Government under contract P07-TIC-03044 (DIRICOM project).


Jussara Marandola

Stephane Louise
email: stephane.louise@cea.fr

Loïc Cudennec
email: loic.cudennec@cea.fr

Jean-Thomas Acquaviva
email: jean-thomas.acquaviva@cea.fr

David Bader
email: bader@cc.gatech.edu

Enhancing Cache Coherent Architectures with access patterns for embedded manycore systems

One of the key challenges in advanced microarchitecture is to provide high performance hardwarecomponents that work as application accelerators. In this paper, we present a Cache Coherent Architecture that optimizes memory accesses to patterns using both a hardware component and specialized instructions. The high performance hardwarecomponent in our context is aimed at CMP (Chip Multi-Processing) and MPSoC (Multiprocessor System-on-Chip).

A large number of applications targeted at embedded systems are known to read and write data in memory following regular memory access patterns. In our approach, memory access patterns are fed to a specific hardware accelerator that can be used to optimize cache consistency mechanisms by prefetching data and reducing the number of transactions. In this paper, we propose to analyze this component and its associated protocol that enhance a cache coherent system to perform speculative requests when access patterns are detected. The main contributions are the description of the system architecture providing the highlevel overview of a specialized hardware component and the associated transaction message model. We also provided a first evaluation of our proposal, using code instrumentation of a parallel application.

I. INTRODUCTION

Chip multi-processing (CMP) has become very popular lately, providing the power of massively parallel architectures on a single chip. One of the key challenges arising from these systems consists in designing the right programming model which would be as independent as possible of the underlying hardware. This is particularly critical in the field of data management between cache memories of many-core systems. In such architectures, each core may store a copy of a data element in its cache. Cache coherence is either directly managed by the programmer or falls under the control of a cache coherence unit (usually hardware based). This second solution makes all updates and data transfers transparent and also simplifies the development of applications. Unfortunately, it is known to have a cost in term of hardware design, refraining it from being massively adopted in embedded computing.

To make data coherence more attractive for massivelyparallel embedded architectures, we think that cache coherency models and protocols should be tightly adapted to the needs of targeted applications. A large number of applications deployed on embedded devices focus on image, video, data stream and workflow processings. This class of applications tends to This work was done in part as the first author was in CEA, LIST access data in a regular fashion, using a given set of memory access patterns. These patterns can be used to optimize the cache coherency protocol, by prefetching data and reducing the number of memory transactions.

Using memory access patterns has already been studied in the literature but, as far as we know, our way of mixing a software and a hardware approach is unique. In this paper we describe the system architecture of a hardware component proposed to store and manage patterns, and the associated protocol which takes advantage of them for optimizing memory consistency and access time. Our main contributions provide the state of the art of directory-based cache protocols, adding an optimization for regular memory access patterns. These contributions are part of the CoCCA project standing for Codesigned Coherent Cache Architecture. We also provide in this paper a first evaluation by code instrumentation of a typical parallel program.

The remainder of this paper is organized as follows: section II presents a brief state of the art and related works; section III explains our architecture and how we optimized it to take the best advantage of regular memory access patterns that occurs in applications, the principles, and the associated protocol; section IV relates an analysis of a first parallel benchmark by tracking memory traces. Finally, section V concludes and gives some perspectives about this work.

II. MEMORY CONSISTENCY AND STATE OF THE ART

A. Context: Cache Coherence for CMP Architectures

Shared Memory Chip Multi-Processor Architectures are expected to host up to hundreds of cores. These cores are connected through a scalable network (Network on Chip, NoC) usually based on a mesh topology. In this context, coherence issues occur when data are replicated on different cache memories of cores, due to concurrent read and write operations. Versions of data may differ between cores and with main memory. In order to maintain consistency, one popular approach is to use of a four-state, directory-based cache coherence protocol. This protocol, called baseline protocol, is a derivative of the Lazy Release Consistency [START_REF] Li | Memory Coherence in Shared Virtual Memory Systems[END_REF] protocol.

B. Baseline Protocol: a Directory-based Cache Protocol

In order to illustrate the behavior of the baseline protocol, we consider a CMP machine. Each core of the machine hosts a Fig. 1. Baseline Protocol: an example of a simple Write Request L1 instructions and data caches, a L2 cache, a directory-based cache, a memory interface and a network (NoC) interface. The directory-based cache hosts coherency information of a given set of data stored in the cache (see also Figure 2 since the CoCCA approach only modifies the CMP architecture by adding the Pattern Table and and modifying the protocol). The coherency information is a set of (N +2) long bit-fields, sorted by memory addresses, where N is the number of cores in the system. Traditionally, the coherency information is composed by 2 bits representing the coherence state, plus a N bitslong presence vector. The coherence state field represents four states, as defined by the MESI protocol:

• M (modified): a single valid copy exists across the whole system; the core owning this copy is called Owner of the data and has the right to write. The value of this copy has changed since the data was cached by the owning core.

• E (exclusive): a single valid copy exists across the whole system, the core owning this copy is named the Owner of the data and has the right to write. The data was not modified since it was cached by the owning core.

• S (shared): multiple copies of the data exist, all copy are in read-only mode. Any associated core is named Sharer.

• I (invalid): the copy is currently invalid, should not be used and so will be discarded. The length of the presence vector is equal to the number of cores in the system: 0 at the i th bit means the data is not cached in core i, and 1 at the j th bit means it is cached in core j. For each data element managed by the coherency protocol, a dedicated node, named Home-Node (HN), is in charge of managing coherency information for this particular element. In the literature, many cache coherence protocols, such as proximity-aware [START_REF] Jeffery | Proximity-aware Directory-based Coherence for Multicore Processor Archectures[END_REF], alternative home-node [START_REF] Zhuo | Alternative Home Node: Balacing Distributed CMP Coherence Directory CMP-MSI: 2nd Workshop on Chip Multiprocessor Memory Systems and Interconnects[END_REF], MESI [START_REF] Chung | ProtoFlex: Co-simulation for Componentwise FPGA Emulator Development[END_REF] and MESIF [START_REF] Hum | Forward State for Use in Cache Coherency in a Multiprocessor System[END_REF] derivate from the baseline protocol.

We can illustrate the baseline protocol on a write request transaction, as shown in Figure 1: it triggers a sequence of messages transmitted between different cores. 1) The requester sends a message to the home node in charge of keeping track of the coherency information. 2) The home node checks the vector of presence and sends an exclusive access request to all the cores owning a copy of the data. 3) Then, all these cores invalidate their own copy and send an acknowledgment back to the home node. 4) Finally, the home-node grants the write permission to the requester and possibly transfers an up-todate version of the data.

C. Optimizing the Cache Coherence Protocol

The number of messages generated by the coherency protocol is one of the most important criterion used to evaluate the overall performance. In section II-B, we have seen that a simple write request generates a four-step transaction with up to 10 messages sent over the network.

In a more sophisticated case, we can imagine an application accessing a picture column by column. This type of access cannot be handled by the baseline protocol in only one transaction. This simple example shows a case where the baseline approach falls into a worst-case scenario.

Working on columns in a picture can be achieved with the help of data access patterns. Patterns can be used to speculate on the next accesses, prefetching data where they will be most likely used in a near future. Patterns can also be used to save bandwidth, by reducing the number of protocol messages: one transaction can provide access to a whole set of data.

D. Related works 1) Exploiting Data Access Patterns:

In the literature, several projects propose to optimize data consistency protocols by supporting data access patterns. This has been explored in the fields of database systems, distributed shared memories or processor cache management.

In [START_REF] Debes | Apparatus and Method for Performing Data Access in Accordance with Memory Access Patterns[END_REF], Intel uses patterns as a sequence of addresses stored in physical memory. A dedicated instruction set is provided to apply patterns, given a base memory address and an offset. A single call to these instructions can perform accesses to noncontiguous addresses in the cache. However this mechanism is limited to data stored in one cache.

In [START_REF] Shen | Mechanisms and Methods for Using Data Access Patterns[END_REF], IBM proposes to sort patterns by type: read-only, read-once, workflow and producer-consumer. Corresponding patterns are stored in a hardware component. Dedicated processor instructions are provided to detect and apply patterns. Here again, this mechanism is not fitted to the context of manycore computing, as it only applies patterns on a local cache.

2) MPSoC and other platforms: Our Cache Coherence Architecture was developed with MPSoC (Multiprocessor System-on-chip) in mind. This architecture is based on a multicore system with state of the art shared memory and paradigm of parallel computing. Platforms such as hybrid or heterogeneous systems (e.g. composed with CPU+GPU) could adopt our model of architecture.

For high performance computing, we aim at the kind of following hybrid systems: multicore processor with GPU (Graphics Processing Unit), NVIDIA Tesla (Cluster of GPU A related work is the TSAR project that describes a multicore architecture with a scalable shared memory that supports cache coherency. The TSAR system [START_REF]Tera-scale Multicore processor architecture (TSAR). Project Profile Medea+, European Project[END_REF] aims to achieve a shared memory architecture including thousands of RISC-32 bit processors.

III. COCCA ARCHITECTURE AND PROTOCOL DESIGN

A. Principle and motivations

The main contribution is the specification of the CoCCA protocol of transaction messages that provides support for managing regular memory access patterns. The associated messages are called speculative messages. The CoCCA protocol is a hybrid protocol designed to interleave speculative messages and baseline messages through a hardware-component that has the following purposes: store patterns and control transaction messages.

The optimization of the CoCCA protocol is based on finding memory addresses of application matching a stored pattern. The requester sends the speculative message to the CoCCA Home Node (or Hybrid Home Node, HHN) if it matches a stored pattern or otherwise, the requester sends the baseline message to the ordinary Baseline Home Node (BHN). This optimized method enhance the performance of cache coherency traffic, aiming for the following advantages:

• reduction of throughput of messages,

• lower time of memory accesses. In the next sections, we will present the design principles of our architecture, a first specification of simple patterns, the bases of our protocol and the associated data structures.

B. CoCCA Architecture principles

A typical implementation of the CoCCA Architecture would have several dozens of cores for a start. Each CPU core of the system may be involved in exchange of coherence messages, taking four different roles with regards to data, i.e. a core can play one role (or several) in transactions related to a given data, and assume different roles for different data.

• Requester, the core asking for a data.

• Home Node, the core which is in charge of tracking the coherence information of a given data in the system.

• Sharer, a core which has a copy of the data in its cache. This copy is in "shared mode", i.e. multiple copies of this data can exist at the same time for several cores.

• Owner, a core which has a copy of the data in its cache. This copy is in "Exclusive" or "Modified" mode, so one and only one instance of it can exist at this time across the whole system. Each CPU has the following components of cache hierarchy: L1 caches, a L2 cache (shared inclusive), a directory of cache coherence and the "CoCCA Pattern Table ", as seen on figure 2.

C. CoCCA Pattern Table

Patterns are used to summarize the spatial locality associated to the access of data. The pattern table lookup process uses a signature of a pattern which is either its base address, or in a more general way a "trigger", i.e. a function that provides a specific signature of a pattern1 , as seen in figure 3. One can imagine lot of different principles for patterns, but let us illustrate it with the simplest of them: the 2D strided access, since it would cover a lot of data accesses encountered in embedded applications. Where baseaddress is the address of the first cache line of the pattern, size, the size of the pattern (number of elements), and stride expresses the distance between two consecutive accesses of the pattern.

In figure 3, we present some initial concepts about the Cocca Pattern Table . The base architecture is a multi-core system, each core fitted with its memory hierarchy (L1, L2), Directory and Pattern Table, and all cores have access to a Network on Chip (NoC) that permits each core to communicate with one another and with main memory (figure 2). The CoCCA protocol optimizes the coherency protocol for the stored memory access patterns of a given application running on the system.

The pattern descriptor enables to describe the CoCCA pattern table entry: Desc = f n (B addr , s, δ), with:

• f n () the function that build the pattern of length n with the given characteristics,

• Desc the pattern descriptor that results from applying function f n () with the parameters B addr , s and δ,

• B addr represents the offset address, regarding the first address of many addresses composed by pattern access on address lookup,

• s is the size of the pattern, or number of elements,

• δ is the stride between two given accesses in the pattern We can define an example of pattern access:

{1, 4, 2} f ollowing @1 + 1 = @2 and {1, 4, 2}(@1) = (@2, @5, @8, @11) So applying address @1 to the pattern {1, 4, 2} is a series of 4 addresses starting at @2 (@1 plus 1 offset) and with an interval of 2 addresses not belonging to the pattern between two successive addresses. This defines the base addresses of our simple patterns. In general there can be more than one address for each element of the pattern: this is given by an extra n parameter, which defines the length of each access in the pattern.

In our future work we want to simulate our principles using a transaction level model (TLM) like simSoC, but a first approach of cache coherence architecture was developed through an API that describes the hardware behavior. The implementation used the C language where Typedef structure modelize hardware storage and the API describes execution of a special instruction set to manage pattern tables.

A pattern table is similar to a hash table describing pattern ids (or triggers, as seen previously) and associated patterns. Regarding the pattern table, we described it as composed by patterns. Our pattern structure is based on an associated stride; the key elements that compose the pattern are: offset, length and stride. To this, we added the capacity and a size. The capacity represents the memory space required to store each pattern and size is the space in memory.

Definition of Pattern Structure

In our first approach toward embedded systems, we thought that pattern table can be the result of the compilation process of an optimized application. Therefore, pattern tables can be fetched as part of a program, by using a specialized set of instructions. For our evaluation, a library is used to simulate the use of these special instructions:

D. Protocol and Home Node management

The pattern table permits the management of a hybrid protocol to improve the performance of transaction messages in the system memory. The hybrid protocol was specified for Cache Coherent Architecture to optimize the flow of messages, interleaving baseline messages and speculative messages. We introduce the concept of granularity of messages to avoid hotspot of messages in the systems.

The specification of this hybrid protocol presents the following characteristics:

• Difference between baseline and speculative messages,

• Speculative messages that permit to read all addresses of pattern through their base address,

• Requests of speculative messages by page granularity,

• Round-Robin method to choose the Home Node (HN). The CoCCA protocol augments the baseline protocol with a dedicated protocol for managing memory access patterns. Both protocols have an important actor in message management: the Home Node (HN). Each core of the system is the Home Node of a fraction of the cached data, and the coherence information of these data are kept within an extra storage named "Coherence Directory".

When a processor accesses a data element, it needs to check the coherence state by asking to the corresponding HN. This task is handled by the coherence engine which manages all messages related to shared memory accesses. Therefore, the Fig. 4. Model of Transaction Messages including the Home Nodes initial step is to determine which core in the system is the HN of the requested data. The basic, and classical, algorithm is an allocation of HNs in a round-robin way. Round-Robin is performed by a modulo operation on the low order bits of the address of the data element.

One key question is the granularity used for the round robin algorithm. For instance, it has be shown that memory accesses are not distributed in a homogeneous way, leading to an uneven bandwidth consumption (some cores becomes hot-spots because they are solicited often).

To reduce the hotspot issue of cache systems, the throughput of messages, and to limit the number of messages of cache coherence protocol, we chose a different granularity to determine the HN of the Baseline protocol and of the CoCCA (pattern specific) protocol: we use the line granularity and page granularity, respectively.

E. Transaction Message Model

Figure 4 shows the read transaction message model in the coherency hybrid-protocol that describes the key rules: requester, hybrid (CoCCA) HN, baseline HN. Each read access triggers the search of its address in the pattern table. If the pattern table lookup returns true, the base address is sent to the hybrid HN. Otherwise, the baseline message is sent to the baseline HN (note that table lookups can be done in parallel).

For the hybrid protocol, the rules can be divided in: core that request the data (requester), the baseline HN and the hybrid HN. The baseline HN is the core appointed by fine granularity (line) for the Round-Robin attribution, and the hybrid HN uses the coarse granularity (page) for the Round-Robin attribution. The first model of decision tree is based on the read transaction message, where the pattern table lookup is similar to a cache lookup as seen in the top box of figure 4. This schematic decision tree for read accesses describes data lookup in cache. In the case of a pattern table hit, the speculative message is sent to the Hybrid HN (determined by page granularity). The main interest of pattern tables, is that the ranges of addresses that are defined by patterns provide a way to enhance the baseline protocol (MESI modified protocol) by authorizing a speculative coherence traffic which is lighter (i.e. with less message throughput) than the baseline protocol alone. Hence, it accelerates shared memory accesses (see figure 5).

In case of a cache miss, the flow of message transaction defined by the baseline protocol is sent by requested addresses. When the pattern table and the speculative (CoCCA) protocol is added and a pattern is triggered, the flow of message transaction can be optimized in term of messages, because the pattern provides a means to use speculative messages which are in fewer number than in the baseline protocol. As a conclusion, when a pattern is discovered in our approach, the number of transaction messages is reduced by using speculation, leading to a better memory access time, less power consumption and an optimized cache coherency protocol.

In figure 5, we compared two approaches of cache coherency protocols for a cache miss case. We present two scenarios: the baseline only approach, where the node requested sends the sequential addresses x, y, z, totalizing 9 messages; and the pattern approach where the node send speculatively the pattern with xyz, totalizing only 7 messages, and a early (speculative) prefetching of data in the cache.

IV. CODE INSTRUMENTATION AND FIRST EVALUATION

A. Choice of a first benchmark program

Our goal is to provide a first evaluation of the performance of our hybrid coherence protocol over the baseline protocol alone (but it is worth noting that the CoCCA hybrid protocol relies on the baseline protocol for the messages outside of the prefetch mechanisms).

Therefore we need a benchmark program that would be representative of algorithms found in the embedded world, easy to parallelize, and that shows an interesting variety of behaviors with regards to cache coherence and prefetch. We decided to use a cascading convolution filter: it is very typical of image processing or preprocessing, make a good reuse of data, and is easy to parallelize. The cascading part of the convolution filter use the destination image of one filter as the source of the new filtering, the old source image becoming Fig. 6. Scheme of affectation of source image parts to each core in our benchmark program the new destination image, triggering a lot of invalidation messages in the baseline protocol.

The choice done was to process the algorithm by dividing the source and images in nearly equal rectangles (little variations in rectangle sizes are due to the uneven division in integers) as seen in Figure 6. Source and destination images have a resolution of 640 × 480 and the underlying CMP architecture is chosen as a 7 × 7 processor matrix, each with 256KB of L2 cache (64B by line of L2 cache). Images are defined as a set of pixel and each pixel is composed of 3 floating point values (32 bits). Both the source and the destination parts of the image managed by a given core can fit in its L2 cache. This is not the best possible implementation of a cascading filter, but this application can show lots of different behaviors regarding caches and consistency.

B. Instrumentation

In order to make a first evaluation of the hybrid protocol, we need to extract shared data read and write for each core, for this program. We decided to use to use the Pin/Pintools [START_REF] Bach | Analyzing Parallel Programs with Pin[END_REF] software suite to that end. Pin is a framework that performs runtime binary instrumentation of programs and provides a wide variety of program analysis tools, called pintools. It uses JIT techniques to speed up instrumentation of the analyzed program. A lot of different pintools exists from the simplest (like "inscount") to very elaborate ones. Let us give an example of the use of Pin, using the Simple Instruction Count (instruction instrumentation); this inscount pintools instruments a program to count the number of instructions executed. Here is how to run a program and display its output: The indications of this file are, in order: the Load/Store instruction address, the Read (R) or Write (W) status, the memory access address, the size of the access in bytes, and the core Id number of the CMP architecture (the execution cores are numbered from 1 to 49 in the output). With this modification of the pinatrace pintool, we filtered the accesses to the shared memory accesses. The trace file has nearly 48 millions accesses for a single execution.

C. Approach to patterns

We can define three kinds of patterns on this benchmark:

• Source image prefetch and setting of old Shared values (S) to Exclusive values (E) when the source image becomes the destination (2 patterns per core),

• False concurrency of write accesses between two rectangles of the destination image. This happens because the frontiers is not alined with L2 cache lines. The associated patterns is 6 vertical lines with 0 bytes in common2 ,

• Shared read data (because convolution kernels read pixels in conterminous rectangles, see figure 7). There are 6 vertical lines and 3 sets of two horizontal lines for these patterns. As can be seen a few set of simple patterns are enough to cover all the coherence data for our benchmark program. Number of patterns is limited to 6 patterns for each core to handle all the coherency issues. This is a tiny number, showing that our approach is sustainable without having too much of impact on chip size (we can imagine to keep the pattern tables and associated components for managing pattern table lookup and the enhanced protocol at half the size of the coherence directory, by storing only the most relevant patterns).

D. First evaluation of the protocol

The hypotheses we rely on at this point, is that the pattern tables are a given result of the compilation process, either by code instrumentation, as above, or by static analysis. They are statistically attributed for a given part of an application, and reloaded as required. This is a valid hypothesis in the embedded world where static generation is often standard because the system is tuned to a limited set of applications that are highly optimized. For pure HPC systems, an automatic dynamic generation of patterns would be preferable, but this is still future work.

In the periodic execution of our program, once initialization is passed, we have the following trend of message for the pure MESI versus the hybrid protocols: Hence, there is a reduction of over 37% of message throughput. This does not includes the advantages of data prefetch which reduce in a large way the memory access latency. On this example, prefetch stands for about 10% of the on-chip cache sharing and nearly all main memory accesses, minus the first ones corresponding to the first access of a given pattern.

On an Intel Xeon Nehalem a single task run in a bit less than 4490.10 3 cycles on a core, with preloaded caches (no misses, 37128 write accesses and 928200 read accesses in shared memory). This is the expected speed when the CoCCA protocol is used, since, in this case, caches are efficiently prefetched. With the baseline protocol alone, all the write accesses trigger a memory access, 17283 read misses with memory also appear and about 13000 cache sharing requests. When using 80 cycles to access main memory and a mean of 20 cycles to access on chip L2 shared data, this gives a total overhead of 3.10 6 cycles or 67% slower. For this application, using a speculative protocol like CoCCA is a huge performance boost.

V. CONCLUSION

With the growing scale of chip multi-processors, data cache consistency becomes one of the key challenge to efficiently support parallel applications. This is also true for embedded systems: a large number of embedded applications read and write data, according to regular memory access patterns. These patterns can be used to optimize cache coherence protocols and therefore, to improve application performances when sharing data among cores.

In this paper, we proposed a system architecture of Cache Coherency Architecture that make such use of memory access patterns. A regular consistency protocol has been enhanced to handle speculative requests and a new hardware component has been designed to store and retrieve patterns. We described a new hardware-component with an auxiliary memory unit that composes the cache hierarchy to implement that.

We provided a first evaluation of the benefits of our enhanced Cache Coherency Architecture. Basically, we generated the memory access traces for a benchmark program and showed the easiness of handling patterns: only a few patterns per core are sufficient to handle all the coherency traffic with the speculative protocol. On our benchmark, the evaluation shows a performance boost of over 60% thank to the reduced access time to data (prefetched L2 caches). We showed also an optimized throughput of messages by over 35%.

As future work, we want to use an analytical model of cache coherency protocol that would permit to evaluate the effective cost of our protocol performance with regards to the standalone baseline protocol with more accuracy, and use a real simulator platform like SoClib for that. We want also to extend our protocol toward HPC friendly systems, with a dynamic (online, or at runtime) generation of pattern tables.

Fig. 2 .

 2 Fig. 2. CoCCA Architecture showing the addition of the PatternTable to the cache hierarchy

Fig. 3 .

 3 Fig. 3. Cocca Pattern Table lookup principle: in a first implementation, triggers are the base addresses of patterns

  t y p e d e f s t r u c t P a t t e r n { u n s i g n e d l o n g c a p a c i t y ; / * s i z e o f ( a d d r e s s ) * / u n s i g n e d l o n g s i z e ; / * a d d r e s s number * / u n s i g n e d l o n g * o f f s e t ; / * p a t t e r n o f f s e t * / u n s i g n e d l o n g * l e n g t h ; / * p a t t e r n l e n g t h * / u n s i g n e d l o n g * s t r i d e ; / * p a t t e r n s t r i d e * / } P a t t e r n t ;

•

  PatternNew(): function to create a pattern, • PatternAddOffset(): function to add an offset entry, • PatternAddLength(): function to add a length entry, • PatternAddStride(): function to add a stride entry, • PatternFree(): function to release the pattern after use.

Fig. 5 .

 5 Fig. 5. Baseline and Pattern Approach comparison for a sequence of read requests

  This is the number of sequential instructions executed when running a mono threaded version of our program. There exists a multi-thread version of this pintool. When the multi-threaded convolution is used, we can obtain a number of instructions executed per core: An interesting pintool is pinatrace which is a memory reference trace (instruction instrumentation): this tool generates a trace of all memory addresses referenced by a program. We modified it to provide also the core Id on which a given memory access is done. It generates the pinatrace.out file:

				Exclusive data (1 core only)
	Rect. i		Rect. i+1	Data shared by 2 cores
				Data shared by 4 cores
	Rect. i+7	Rect. i+8
	Fig. 7. Read data sharing in conterminous rectangles
	Number o f t h r e a d s e v e r e x i s t = 50
	Count [ 0 ] = 238062
	Count [ 1 ] = 9064522
	Count [ 2 ] = 9087339
	. . .
	0x401c5e: R	0xa0aecc 4	12
	0x401d5d: W	0x6832b4 4	12
	0x40119c: R	0xa02c20 4	9
	0x4011c8: R	0xa02c2c 4	9
	...
	˜/ p i n -2.10> . / p i n -t $ ( PIN OBJ PATH ) / i n s c o u n t . s o --
	. / c a s c a d i n g -convo-s i n g l e -p r o c
	˜/ p i n -2 . 1 0 / t e s t > c a t i n s c o u n t . o u t
	Count 450874769

Of course the simplest trigger, and the one we implemented in our evaluation in this paper, is the use of the base address.

hence, the CoCCA pattern has the information that this is a false concurrency, and that the synchronization can be serialized.