Paula Perez-Lopez

Isabelle Blanc

Benoît Gschwind

Philippe Blanc

Lionel Menard

Rolf Frischknecht

Philippe Stolz

Yvonnick Durand

Garvin Heath

INTERACTIVE WEB-SERVICE FOR ENVIRONMENTAL MULTI-CRITERIA LIFE CYCLE ASSESSMENT OF PHOTOVOLTAIC SYSTEMS WORLDWIDE

Keywords: Photovoltaic, Web-Service, environmental performance, solar irradiation data, IEA PVPS Task 12, OGC standards

Photovoltaic (PV) technologies constitute a leading renewable energy source with a worldwide installed capacity of 135 GW in 2013 that may increase to nearly 4700 GW in 2050. To achieve this production level while minimizing environmental impacts, decision makers must rely at national level on relevant technological, economic and planning aspects which are highly geographically dependent. The access to performance data is a critical issue in the decision-making process and determines the successful development of efficient PV systems. For this reason, a new interactive tool is proposed here to provide the users with easy-to-use data and maps for the solar irradiation and screening level environmental results of representative PV technologies. The calculation procedures account for the geographic location and the PV system layout (installation, orientation and inclination angles). The tool has a worldwide coverage with a multi-criteria scope, both in terms of the numerous technological scenarios and of the wide range of environmental indicators. Moreover, the user is given the possibility to compare the PV environmental performance to the corresponding country electricity mix environmental footprint.

INTRODUCTION

Photovoltaic (PV) technologies constitute a leading renewable energy source in the context of energy transition [START_REF] Hong | Scenario analysis for estimating the learning rate of photovoltaic power generation based on learning curve theory in South Korea[END_REF][START_REF]Technology roadmap: Solar photovoltaic energy[END_REF]. The worldwide installed capacity is expected to increase from 135 GW in 2013 to nearly 4700 GW in 2050 [START_REF]Technology roadmap: Solar photovoltaic energy[END_REF]. Although PV systems rely on sunlight, which is an extensive renewable source, and cause nearly no emissions during the use (power generation) phase, other processes over the production chain corresponding to materials extraction, components' manufacturing, transport and end-of-life management should be computed to quantify the environmental costs over the whole life cycle of the panels [START_REF] Raugei | Life cycle impacts and costs of photovoltaic systems: Current state of the art and future outlooks[END_REF][START_REF] Beylot | Environmental impacts of large-scale grid-connected ground-mounted PV installations[END_REF]. To achieve the worldwide production target while maintaining a low level of environmental impacts in the upstream and downstream stages, techno-economic and planning criteria affecting the theoretical generation potential of PV systems need to be included. Geographicallydependent factors that may alter the PV power production and, thus, the environmental performance should also be taken into account [START_REF] Fthenakis | The technical, geographical and economic feasibility for solar energy to supply the energy needs of the US[END_REF][START_REF] Ménard | Benefit of GEOSS interoperability in assessment of environmental impacts illustrated by the case of photovoltaic systems[END_REF].

The access to detailed data that support the decisionmaking process is essential to enhance the development of more efficient PV systems [START_REF] Ménard | Benefit of GEOSS interoperability in assessment of environmental impacts illustrated by the case of photovoltaic systems[END_REF]. With the aim of contributing to the supply of accessible information, we propose an interactive online tool to provide the users with easy-to-use data and maps for the solar irradiation and environmental performance results at screening level of representative PV technologies, according to a Life Cycle Assessment (LCA) approach. This tool was developed in the framework of Task 12 of the Photovoltaic Power Systems Program (PVPS) established by the International Energy Agency (IEA). The calculation procedures account for the geographic location and the PV system layout, namely installation, orientation and inclination angles. The tool has a worldwide coverage with a muti-criteria scope, both in terms of the numerous technological scenarios [START_REF] Frischknecht | Life cycle assessment of future photovoltaic electricity production from residential-scale systems operated in Europe[END_REF][START_REF] Frischknecht | Life cycle inventories and life cycle assessment of photovoltaic systems[END_REF] and the wide range of environmental indicators [START_REF] Frischknecht | Methodology guidelines on Life Cycle Assessment of photovoltaic electricity, 3rd edition[END_REF][START_REF] Frischknecht | Implementation of life cycle impact assessment methods[END_REF][START_REF]Climate Change 2013: The physical science basis[END_REF]. Moreover, the user is given the possibility to compare the PV environmental performance to the corresponding country electricity mix, inventoried according to treeze Ltd. [START_REF] Itten | Life cycle inventories of electricity mixes and grid[END_REF].

PURPOSE OF THE WORK

The aim of this work is to propose an easy-to-use interactive tool to assess the environmental footprint of current and prospective representative PV systems at screening level accounting for its geographic location. To enlarge the audience and to ease their access, the tool is available online [http://viewer.webservice-energy.org /project_iea/]. The geo-localized environmental performances provided by our tool are compared with the environmental footprint of the national electricity mix on the same methodological background to allow decision makers to position the environmental interest of PV systems.

APPROACH

Although renewable sources, and particularly PV systems, exhibit remarkably lower emissions and better environmental performances than fossil sources during their utilization, their impact during manufacturing and installation as well as end-of life management phases should be quantified to assess their sustainability [START_REF] Hong | Scenario analysis for estimating the learning rate of photovoltaic power generation based on learning curve theory in South Korea[END_REF][START_REF]Technology roadmap: Solar photovoltaic energy[END_REF][START_REF] Raugei | Life cycle impacts and costs of photovoltaic systems: Current state of the art and future outlooks[END_REF][START_REF] Beylot | Environmental impacts of large-scale grid-connected ground-mounted PV installations[END_REF].

Life cycle assessment (LCA) is one of the main tools recommended for the environmental evaluation of emerging technologies such as PV systems [START_REF] Raugei | Life cycle impacts and costs of photovoltaic systems: Current state of the art and future outlooks[END_REF][START_REF] Beylot | Environmental impacts of large-scale grid-connected ground-mounted PV installations[END_REF][START_REF] Wender | Illustrating anticipatory Life Cycle Assessment for emerging photovoltaic technologies[END_REF]. LCA is a standardized methodology that aims at assessing the potential environmental impacts of processes over their whole life cycle from the extraction and processing of raw materials to the use and end-of life stages. The environmental impacts are quantified by classifying the emitted substances into specific impact categories and converting their values into reference units through sets of characterization factors [START_REF]Environmental management -Life cycle assessment -Principles and framework[END_REF].

Environmental performances for energy systems are expressed as the ratio of their environmental impacts issued from LCA, over the produced energy along their life time (Eq. 1). For PV systems, the environmental impacts are calculated according to the methodological guidelines, published in the framework of the IEA PVPS Task 12 [START_REF] Frischknecht | Methodology guidelines on Life Cycle Assessment of photovoltaic electricity, 3rd edition[END_REF]. The quantification of multi-annual mean of surface solar global irradiations enables determining the total energy production at a specific location over a given life time. The developed tool allows obtaining the environmental performances of PV systems in the form of a Web-client invoking a Web-Service that combines algorithms for the calculation of PV life cycle impacts and annual solar irradiation [START_REF] Ménard | Benefit of GEOSS interoperability in assessment of environmental impacts illustrated by the case of photovoltaic systems[END_REF]. The Web-Service is based on representative life cycle inventories developed within IEA PVPS program [START_REF] Frischknecht | Life cycle assessment of future photovoltaic electricity production from residential-scale systems operated in Europe[END_REF][START_REF] Frischknecht | Life cycle inventories and life cycle assessment of photovoltaic systems[END_REF]. The expected electric yearly production of the PV systems has been computed from the freely available solar irradiation NASA SSE database (https://eosweb.larc.nasa.gov/sse). More precisely, the 1°x1° worldwide maps of multiannual (22 years) average of monthly global and diffuse irradiations have been used to compute the expected yearly global irradiations on the tilted plane corresponding to the PV systems applying the same algorithm used for the NASA SSE database itself which corresponds to the RETScreen method [START_REF]Surface meteorology and Solar Energy (SSE) Release 6.0 Methodology, version 3.1.2, NASA[END_REF].

After obtaining the annual irradiation for a given location, our tool computes the total electricity generated over the whole life cycle of the PV system, as well as the environmental performance, and provides the results to the user.

Regarding the range of results provided by the tool, the Web-client has been developed to propose an interactive user interface matching the foreseen request from the users. The tool offers the user the possibility to obtain multi-criteria LCA results including diverse impact categories of widespread impact assessment methodologies such as ILCD 2011 Midpoint+, Cumulative Energy Demand, IMPACT 2002+, IPCC 2013 and USETox among others [START_REF] Frischknecht | Methodology guidelines on Life Cycle Assessment of photovoltaic electricity, 3rd edition[END_REF][START_REF] Frischknecht | Implementation of life cycle impact assessment methods[END_REF][START_REF]Climate Change 2013: The physical science basis[END_REF].

SCIENTIFIC INNOVATION AND RELEVANCE

This Web-Service is the first tool to propose a worldwide coverage of environmental performance of PV systems. It is developed using a state of the art interoperable and open standards Web-Service framework from the Open Geospatial Consortium (OGC), namely Web Processing Service (WPS). It combines the latest updated life cycle inventories, published in 2015 by the IEA Task 12, and the solar irradiation database compiled from the worldwide NASA SSE database for a wide range of inclinations and orientations. A new Web-client based on a previously developed version [START_REF] Ménard | Benefit of GEOSS interoperability in assessment of environmental impacts illustrated by the case of photovoltaic systems[END_REF] is proposed for the user to compare the PV performance to the national LCA electricity mix from the WPS. The implemented LCA categories cover a wide range of environmental issues.

RESULTS

To obtain the environmental performance for a specific impact category, the user needs to make a choice for the following parameters:

(1) the PV technology, (2) the type of system (power output and mounting), (3) the techno-economic context, (4) the performance ratio, (5) the orientation and inclination, (6) the PV lifetime and (7) the environmental impact assessment method and impact category.

Figure 1 shows the cascading menu developed to facilitate the selection of the parameters. The interactive Web-client allows the user to investigate many different technological scenarios for representative 3kWp or 570kWp systems (Figure 2) combined with different options of installations, orientation and inclination. The techno-economic context is taken into account by selecting either "current" or "prospective" scenarios, following the scenarios defined by IEA PVPS Task 12 [START_REF] Frischknecht | Life cycle assessment of future photovoltaic electricity production from residential-scale systems operated in Europe[END_REF][START_REF] Frischknecht | Life cycle inventories and life cycle assessment of photovoltaic systems[END_REF]. After the user's selection of the requested parameters, the Web-Service provides worldwide maps of LCA results at screening level for the selected impact category. By clicking on a specific location on the map the user get for this location: the latitude, the longitude, the mean annual solar irradiation, the environmental impact over the whole life cycle, the performance as impact per kWh, the environmental footprint of the corresponding country electricity mix for an equivalent level of energy production and the relative difference between the local PV environmental performance minus the performance of the country electricity mix. The user can export those data for further processing with the "export" button.

An illustration of the environmental performance for a specific representative PV is given in Figure 3, obtained by operating the Web-Service http://viewer.webserviceenergy.org/project_iea/. The environmental benefits of mono-Si prospective scenarios in the three selected categories are depicted in Figure 5. According this figure, the business-as-usual scenario may lead to limited impact reductions ranging between 10% and 20%, whereas the realistic scenario involves significant improvements from 35% to nearly 50% and the optimistic scenario may allow higher reductions, between 40% and 60%.

A given technology vs the current country electricity mix:

In Figure 6, we propose the comparison of PV and country mix environmental performances in different countries and geographic locations. The locations were selected to represent the extreme environmental performances within each country. As shown in Figure 6, the comparative results of the climate change for the mono-Si laminates and the corresponding country electricity mix are highly dependent on the geographical location and the specific characteristics of each national grid. Thus, the differences are rather limited in the case of France due to the low carbon emissions associated with the high percentage of nuclear energy and low production from fossil fuels. On the contrary, countries with a high percentage of electricity coming from fossil sources, such as Germany or US, exhibit a remarkably lower impact on climate change of the PV systems than that of the country mix.

CONCLUSIONS

We developed an easy-to-use interactive Web-Service based on current OGC standards to provide environmental data on existing PV technologies. The tool offers accessible and adapted information to support decision-making processes.

Analyzing the differences of the PV performance of the available technologies and providing comparisons with respect to the performance of the corresponding national electricity mix open the way to understand the positioning of PV mix relying on a multi-criteria assessment. Easy and open access to this key information is essential to feed the debate on energy transition.

Figure 1 :

 1 Figure 1: Web-Service cascade menu for the selection of: a) PV technology, mounting and techno-economic context and b) impact assessment method, category, and energy production conditions including the performance ratio, the lifetime, the inclination and the orientation.

Figure 2 :

 2 Figure 2: Available production scenarios provided by the Web-Service represented by links between boxes.

Figure 3 :

 3 Figure 3: Worldwide map of climate change (ILCD 2011 Midpoint + method) obtained from the Web-Service for 3 kWp slanted-roof laminates of current CdTe technology with a 30-year lifetime at 45° inclination and south orientation. LCA practitioners can process the environmental results provided by the Web-Service to carry out three types of comparative environmental analyses:

Figure 4 : 2 .

 42 Figure 4: Comparative environmental performance of 3 kWp laminates of current PV technologies available in the Web-Service, operating at 45° inclination and south orientation 2. The current vs prospective techno-economic context for a given technology: Three prospective techno-economic contexts are provided for mono-Si and CdTe laminates. The business-as-usual scenario estimates the future context by considering the continuation with current policies and no additional goals. The realistic scenario corresponds to a situation in which energy policies would give a relatively high priority to the empowering of renewable energy policies. The optimistic scenario considers the implementation of ambitious energy policies and high development of efficient renewable energy technologies.The environmental benefits of mono-Si prospective scenarios in the three selected categories are depicted in Figure5. According this figure, the business-as-usual scenario may lead to limited impact reductions ranging between 10% and 20%, whereas the realistic scenario involves significant improvements from 35% to nearly 50% and the optimistic scenario may allow higher reductions, between 40% and 60%.

Figure 5 :

 5 Figure 5: Comparative environmental performance of current and prospective 3 kWp mono-Si laminates operating at 45° inclination and south orientation.

Figure 6 :

 6 Figure 6: Comparative environmental performance of current 3 kWp mono-Si laminates operating at 45° inclination and south orientation with respect to country electricity mix.

ACKNOWLEDGMENTS

This research has been undertaken with the framework and financial support of the International Energy Agency in the framework of Task 12 of the Photovoltaic Power Systems Program (PVPS), as well as with the financial support of ADEME (France).


Jiankun Ding

Deqiang Han
email: deqhan@gmail.com

Jean Dezert
email: jean.dezert@onera.fr

Yi Yang

A New Hierarchical Ranking Aggregation Method

Keywords: Ranking fusion, hierarchical, pairwise comparison, multiple attribute decision making (MADM)

The ranking fusion (or aggregation), which is an important branch in multiple attribute decision making, combines multiple rankings to a single one for decision making. Many traditional ranking fusion methods are implemented through heuristic ways to reduce the computational cost. They all have their own pros and cons. In this paper, a new hierarchical ranking aggregation method is proposed. All the items are first divided into multiple ranking levels (i.e., ordered items subsets) based on the information provided by different rankings to be fused. The items in high ranking levels are ranked higher than all the items in low ranking levels in the fused ranking, therefore those items in different levels never interact each other's ranking. Then, the items in the same ranking level are further divided into multiple sub-levels if possible. In the final, the items in a sub-level which cannot be further divided are further compared and ranked in particular. Simulation results show that our new hierarchical method performs well in ranking fusion for decision making.

I. INTRODUCTION

Different attributes or information sources reflect different aspects of the items concerned in decision making. Information fusion based decision making approaches such as multiple attribute decision making (MADM) [START_REF] Figueira | Multiple Criteria Decision Analysis: State of The Art Surveys[END_REF], which comprehensively uses multiple attributes, are expected to obtain better results than those using only single attribute. The ranking fusion (or ranking aggregation) is an important branch in MADM where each information source provides a order list (ranking) of the corresponding items and these input rankings are fused to generate a consensus ranking. The ranking fusion has been a research topic for more than two centuries and has been increasingly used in a wide range of successful applications such as the information retrieval [START_REF] Dwork | Rank aggregation methods for the web[END_REF], bio-informatics [START_REF] Lin | Integration of ranked lists via cross entropy Monte Carlo with applications to mRNA and microRNA studies[END_REF], estimator ranking [START_REF] Yin | Measures for ranking estimation performance based on single or multiple performance metrics[END_REF] and enterprise management [START_REF] Chen | A novel collaborative filtering approach for recommending ranked items[END_REF], [START_REF] Mitra | Mathematical Models for Decision Support[END_REF].

In the traditional MADM framework, the goal of ranking fusion is to find a ranking that can best represent all the input rankings, i.e., to find a ranking which has the smallest average distance to all the available rankings to be fused [START_REF] Dwork | Rank aggregation methods for the web[END_REF], [START_REF] Argentini | Ranking Aggregation Based on Belief Function Theory[END_REF]. Finding this fused ranking can be formulated as an optimization problem, which is usually NP-hard [START_REF] Dwork | Rank aggregation methods for the web[END_REF]. To reduce the computational cost, a series of heuristic ranking fusion methods have been proposed. According to their implementation processes, these methods can be divided into two branches, i.e., batch mode [START_REF] De Borda | Mémoire sur les élections au scrutin[END_REF]- [START_REF] Negahban | Iterative ranking from pair-wise comparisons[END_REF] (or global mode) methods and instant-runoff mode [START_REF] Burnett | Ballot (and voter) "exhaustion" under instant runoff voting: An examination of four ranked-choice elections[END_REF] (or Luce mode [START_REF] Luce | Individual Choice Behavior: A Theoretical Analysis[END_REF], [START_REF] Tao | A new probabilistic model for rank aggregation[END_REF]) methods.

Batch mode methods generate the ranking positions of all the items simultaneously, where the Borda count [START_REF] Argentini | Ranking Aggregation Based on Belief Function Theory[END_REF], [START_REF] De Borda | Mémoire sur les élections au scrutin[END_REF] is perhaps the most representative one. It works based on the items' positions in input rankings directly. Condorcet vote [START_REF] De Condorcet | Essai sur l ′ application de l ′ analyse à la probabilité des décisions rendues à la pluralité des voix[END_REF] is another popular traditional method, which works based on the pairwise comparisons of items. Dwork [START_REF] Dwork | Rank Aggregation Revisited[END_REF] used the Locally Kemeny optimal ranking as the fused ranking. It is implemented by finding Hamiltonian path. In 2002, Mark [START_REF] Montague | Condorcet fusion for improved retrieval[END_REF] designed a Condorcet-fuse method and it is also implemented by finding the Hamiltonian path. In 2012, Negahban [START_REF] Negahban | Iterative ranking from pair-wise comparisons[END_REF] introduced a kind of iterative ranking from pairwise comparisons, and later Yin [START_REF] Yin | Measures for ranking estimation performance based on single or multiple performance metrics[END_REF] proposed the Ranking Eigenvector (REV) method. Although these two methods analyze the ranking problem in different ways, they both use the eigenvector of the pairwise comparison matrix for ranking. Yin also introduced a Self-weighted Score Addition (SSA 2 ) method. Moreover, some other methods apply stochastic optimization algorithms [START_REF] Pihur | Weighted rank aggregation of cluster validation measures: a Monte Carlo cross-entropy approach[END_REF], [START_REF] Pihur | RankAggreg, an R package for weighted rank aggregation[END_REF] such as the genetic algorithm and cross-entropy Monte Carlo algorithm for searching the optimal ranking.

The instant-runoff mode methods decompose the process of generating a fused ranking of items into sequential rounds. In each round, only the one item is assigned a fused ranking position and eliminated immediately from the set of unranked items. The following rounds only concern about the unranked items. The most representative method is Instant-Runoff Voting (IRV) [START_REF] Burnett | Ballot (and voter) "exhaustion" under instant runoff voting: An examination of four ranked-choice elections[END_REF]. However, in each round of IRV, the eliminated items is selected just according to the first place votes, which can not represent the input rankings' opinions comprehensively. In 2010, Qin [START_REF] Tao | A new probabilistic model for rank aggregation[END_REF] proposed a probabilistic model, i.e., coset-permutation distance based stagewise (CPS) model, for the ranking aggregation. CPS works better than IRV, however, it has large computational cost for selecting the best item in each round. In 2015, we [START_REF] Ding | Novel instant-runoff ranking fusion approaches[END_REF] proposed an instant-runoff ranking fusion method (IRRF) using the result of traditional batch mode ranking fusion methods and a top-2 comparison based instant-runoff ranking fusion method (T2-IRRF), which is an improved IRRF by introducing more local comparison information into the selection of the best item in each round.

Traditional ranking fusion methods all have their pros and cons (e.g., the problem of rank reversal [START_REF] Shin | A critical review of popular multi-criteria decision making methodologies[END_REF]), and there is no widely accepted one. In this paper, a hierarchical ranking aggregation (HRA) method is proposed to obtain better performances of ranking fusion. HRA divides the items into different ranking levels, i.e., multiple ordered items subsets, according to their comparisons with all the other items based on all the rankings to be fused. Then the items in the same ranking level are further divided into different sub-levels according to the comparisons among themselves if they could be further divided. The ranking fusion is implemented hierarchically. In the final, the items in a sub-level, which cannot be further divided, are compared and ranked in particular to complete the fused ranking. According to HRA, the items in high ranking levels are ranked higher than all the items in low ranking levels in the fused ranking, therefore, those items in different levels never interact each other's ranking. Simulation results show that the new ranking fusion method can effectively improve the performance of ranking fusion, which is desired for decision making.

II. RANKING AGGREGATION IN MULTIPLE ATTRIBUTE DECISION MAKING

A. Conceptions and formulations in ranking aggregation

Given a set of items = { 1 , 2 , ..., }, a ranking is the order list of these items according to a certain criterion (or attribute). The ranking in general can be categorized into three types [START_REF] Argentini | Ranking Aggregation Based on Belief Function Theory[END_REF], [START_REF] González-Pachón | Aggregation of partial ordinal rankings: an interval goal programming approach[END_REF], [START_REF] Fagin | Comparing top k lists[END_REF]: the total ranking, the partial ranking, and the top-ranking. Here, we only focus on the total ranking, where all the items are assigned ranking positions. When there are more than one available rankings originated from different information sources (or attributes), the ranking fusion (or aggregation) can output a consensus ranking of these available rankings. Suppose there are available rankings with respect to items as shown in (1).

= 1 2 ⋅ ⋅ ⋅ 1 2 . . . ⎡ ⎢ ⎢ ⎢ ⎣ 11 12 ⋅ ⋅ ⋅ 1 21 22 ⋅ ⋅ ⋅ 2 . . . . . . . . . . . . 1 2 ⋅ ⋅ ⋅ ⎤ ⎥ ⎥ ⎥ ⎦ (1)
The th row of represents the ranking = { 1 , 2 , ..., } given by attribute ( = 1, 2, ..., ) and denotes the ranking position of in . In general, we assume that if the value of is smaller, the corresponding item is more preferred according to .

Each ranking in can also be described using pairwise representation [START_REF] Cook | Distance-based and ad hoc consensus models in ordinal preference ranking[END_REF], i.e., the preference between each pair of items is represented using a matrix = ( ) × , where

= ⎧ ⎨ ⎩ 1 ≻ , 0 ≺ , 0.5 = (2)
Here, ≻ denotes that is better than , and ≺ denotes the opposite situation. The ranking, e.g., 4 ≻ 1 ≻ 2 ≻ 3 can be represented with :

= 1 2 3 4 1 2 3 4 ⎡ ⎢ ⎢ ⎣ 0 1 1 0 0 0 1 0 0 0 0 0 1 1 1 0 ⎤ ⎥ ⎥ ⎦
To make a decision, the multiple rankings should be fused or aggregated to generate a consensus ranking that best represents all the rankings: * = ( 1 , 2 , ..., )

where * is the fused ranking, (⋅) denotes a kind of ranking fusion method, and 1 , 2 , ..., are the rankings provided by different attributes or information sources, e.g., the rankings in . Traditional ranking fusion methods can mainly be divided into two branches, the batch mode method and the instantrunoff mode method. Batch mode (i.e. global mode) methods obtain the fused ranking in one run, e.g., Borda Count and the Ranking Eigenvector method (REV). The instant-runoff mode methods obtain the fused ranking using a series of sequential rounds, e.g., Instant-Runoff Voting (IRV). (

) = 1 - -1 (4)
According to the scores of generated from all the available rankings ( = 1, 2, ..., ), Borda Count generates a final score for using a certain aggregate function = ( 1 ( ) , 2 ( ) , ..., ( )

)
. For example, the mean aggregate function is

( 1 ( ) , 2 ( ) , ..., ( ) ) = 1 ∑ =1 ( ) (5)
There are also many other ways to construct aggregate function , such as the -norm mapping, median mapping and geometric mean mapping, etc. [START_REF] Argentini | Ranking Aggregation Based on Belief Function Theory[END_REF]. The fused ranking is obtained by sorting the aggregated scores of items.

2) Ranking Eigenvector (REV): It works based on the pairwise comparison matrix (PCM). PCM's elements express the average preference between each items pair according to their comparisons in all the available rankings. In REV, all the available rankings ( = 1, 2, ..., ) are reformulated using pairwise representation = ( ) × . The PCM matrix is generated as:

ℳ Δ = ⎡ ⎢ ⎢ ⎢ ⎣ (1, 1) (1, 2) ⋅ ⋅ ⋅ (1, ) (2, 1) (2, 2) ⋅ ⋅ ⋅ (2, ) . . . . . . . . . . . . ( , 1) ( , 2) ⋅ ⋅ ⋅ ( , ) ⎤ ⎥ ⎥ ⎥ ⎦ (6)
where

( , ) = 1 ∑ =1 (7)
( , ) denotes the average preference of over . If ( , ) > ( , ), then ≻ . There exists

{ ( , ) + ( , ) = 1 ∀ ∕ = ( , ) = 0 ∀ = (8)
Based on the PCM matrix, REV method generates scores for different items using an certain mapping (⋅). For example, the simple linear mapping is as follows.

max = ( ) = ℳ ( 9
)
where ℳ is the PCM matrix, max is the largest eigenvalue of ℳ, and is the ranking eigenvector (REV), which is the positive eigenvector 1 corresponding to the largest eigenvalue max . is defined as

= [ 1 2 ⋅ ⋅ ⋅ ] ′ (10)
where ( = 1, 2, ..., ) is positive and stands for the fusion score of item . The fused ranking is generated by sorting the scores in .

C. Instant-runoff mode methods

Both two methods introduced above determine the positions of all items in the fused ranking simultaneously, while instantrunoff mode methods determine the items' ranking positions one by one. Instant-Runoff Voting is the most representative instant-runoff mode method. In each round, IRV only determines the ranking position of the item with the fewest (or the most) votes. The item whose ranking is determined in current round will be eliminated. The following rounds are only for determining the rankings of remaining items. The process of IRV is as follows: i) By counting first place votes according to the rankings with respect to the remaining items we get

( ) = ∑ =1 ( ) (11)
where

( ) = { 1 ≻ , ∀ ∕ = 0 ℎ (12)
( ) indicates the first place vote according to . ( ) is the count of votes for item . The item with the fewest (or the most) votes will be assigned the lowest (or the highest) ranking position.

ii) The item who has been ranked in step i) is put into the fused ranking and eliminated from all the input rankings. These updated input rankings will be used as input rankings in the next round.

iii) Repeat the above two steps until we have obtain the whole fused ranking. 1 The way of taking this eigenvector as ranking vector is also adopted in many other ranking fusion methods, i.e., AHP [START_REF] Mitra | Mathematical Models for Decision Support[END_REF].

D. Average ranking distance criterion

As aforementioned, the purpose of the ranking aggregation is to find a ranking that can most represent all of the rankings available for fusion. Kemeny optimal aggregation (KOA) [START_REF] Dwork | Rank aggregation methods for the web[END_REF] aims to find a ranking with the smallest average distance between the input rankings and the fused one, which is defined as

* = arg min 1 ∑ =1 ( , ) (13)
where (⋅, ⋅) is the Kendall distance [START_REF] Kendall | Rank Correlation Methods[END_REF], which is a measurement for describing the consensus degree between rankings. The Kendall distance compares rankings by counting the pairwise disagreements between two rankings, which is defined as follows:

(

1 , 2 ) = 1 2 ∑ ( , ), ∕ = * ( 1 , 2 ) (14)
where

* ( 1 , 2 ) = ⎧   ⎨   ⎩ 0 , ℎ 1 , 2 1 , ℎ 1 , 2 (15)
Kendall distance is calculated in time ( 2 ) . Finding the Kemeny optimal aggregation is usually NPhard, which is very difficult especially when the number of items is very large. The most direct way to find this optimal fused ranking is traversing all of the possible rankings. If the number of the items to be ranked is , there will be ! (the factorial of ) rankings to be traversed. Traditional ranking fusion methods find the feasible fused rankings, among which the one with a smaller average ranking distance is preferred. Therefore, the average ranking distance criterion (ARDC) is often used to evaluate the fused ranking, which is defined as

( ) = 1 2 ∑ =1 ( , ) (16)
If the average ranking distance is small, the corresponding fused ranking is good, i.e., the fused ranking has a higher consensus degree to the input rankings. In this paper, ARDC is adopted to evaluate the fused ranking.

Traditional ranking fusion methods introduced above have their own pros and cons. There is no well accepted ranking fusion approach till now.

III. NOVEL HIERARCHICAL RANKING AGGREGATION

Here, a novel hierarchical ranking aggregation (HRA) approach is proposed. The hierarchical fusion process of HRA is illustrated using a simple example in Figure 1. HRA first divides the items into multiple ranking levels, e.g., Level 2 , Level 1 and Level 02 , according to the comparisons between each item with all the other items. All the items in high ranking levels are ranked higher than the items in low ranking levels. The items in the same ranking level are further compared and divided into multiple ranking sub-levels, e.g., 2 , 3 in Level 2 are further compared and divided into Level 21 and Level 20 . HRA refines the fused ranking hierarchically. In the following, we introduce the way for dividing the items into different ranking levels in detail.

Assume that 1 , 2 , ⋅ ⋅ ⋅ , are the items to be ranked and there are rankings with respect to these items available for fusion. HRA assigns each item a certain ranking level according to its comparisons with all the other items. All the comparisons of each item with all the other items can construct a matrix, i.e., the pairwise comparison matrix ℳ which has already been introduced in (6) as.

ℳ Δ = ⎡ ⎢ ⎢ ⎢ ⎣ (1, 1) (1, 2) ⋅ ⋅ ⋅ (1, ) (2, 1) (2, 2) ⋅ ⋅ ⋅ (2, ) . . . . . . . . . . . . ( , 1) ( , 2) ⋅ ⋅ ⋅ ( , ) ⎤ ⎥ ⎥ ⎥ ⎦
As aforementioned, ( , ) denotes the average preference of over on the opinions of all input rankings (attributes). is preferred than if and only if ( , ) > ( , ). Then HRA generates the preference order between each items pair according to the PCM matrix and obtains the pairwise comparison decision (PCD) matrix, as

Δ = ⎡ ⎢ ⎢ ⎢ ⎣ (1, 1) (1, 2) ⋅ ⋅ ⋅ (1, ) (2, 1) (2, 2) ⋅ ⋅ ⋅ (2, ) . . . . . . . . . . . . ( , 1) ( , 2) ⋅ ⋅ ⋅ ( , ) ⎤ ⎥ ⎥ ⎥ ⎦ (17)
where

( , ) = ⎧ ⎨ ⎩ 1 ( , ) > ( , ) 0.5 ( , ) = ( , ), ∕ = 0 ( , ) < ( , ), = (18)
The th row of denotes the comparisons results between and all the other items.

According to th row of , is assigned the ranking level by counting the times of winning the pairwise comparisons.

( ) = ∑ =1 ( , ) (19)
where ( ) is defined as the ranking level of . and are in the same ranking level if ( ) = ( ), and locates in a higher ranking level than if ( ) > ( ). In the fused ranking, all the high ranking level items are ranked higher than the low ranking level items.

For the items in the same ranking level, HRA further compares their preference order and divides them into multiple ranking sub-levels. The ranking level (or sub-level), which contains more than one items but can not be divided any more, is defined as stationary level. The same ranking level items will stop being divided when this level only contains one item or it is an stationary level. For the items in a stationary level, HRA uses some traditional ranking fusion method, e.g., Borda count as an auxiliary method to generate the fused ranking of those items. The pseudo code of HRA is as Algorithm 1.

Algorithm 1: Hierarchical Ranking Aggregation

Input: Rankings to be fused,

{ } =1 ; fusedRanking = HierarchicalRank ( { } =1 ) { = number of items in { } =1 if n=1 return endif ℳ = calcuate PCM matrix { } =1 = calcuate PCD matrix (ℳ) ( ) , ( = 1, 2, ⋅ ⋅ ⋅ , ) = calcute each item's ranking level ( ) if (1) = (2) = ⋅ ⋅ ⋅ = ( ) fusedRanking = traditional ranking fused method ( { } =1 )
return fusedRanking endif for = 1: number of different levels ranking of th level = HierarchicalRank ( input rankings with respect to the items in th level ) endfor fusedRanking = Rank the items according to their levels return fusedRanking } The computational cost of HRA mainly relates to the comparison times between the same level items. The best case is that all the items are divided to different ranking levels in one time, where HRA will compute in time

( 2 ) comparing each pair of the items. The worst case is that, in each ranking level (or sub-level) division, the items in the same ranking level (or sub-level) are divided into two sub-levels, one of which only contains one item. In this case, HRA will perform -1 times ranking sub-level divisions for generating the complete fused ranking. Therefore, HRA will compute in time

( 3 ) in the worst case.

Here, we give an example to illustrate our new ranking aggregation approach.

Example 1: Assume that 1 , 2 , 3 , 4 , 5 are five rankings originated from five attributes 1 , 2 , 3 , 4 , 5 with respect to nine items 1 , 2 , . . . HRA first generates the pairwise comparison matrix ℳ 1 , according to . For example, considering the comparison between 1 and 2 , 1 loses the comparison according to 1 , 2 , 3 , 4 and wins the comparison according to5 . According to ( 2) and ( 7), we have

(1, 2) = 0.2.

ℳ 1 = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 0.0 0.
⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦
Then HRA generates the preference order between each pair of items according to ℳ 1 and obtians the pairwise comparison decision matrix 1 .

1 = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 0 0 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 1 1 1 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦
Then different items are assigned ranking levels by counting their winning times according to 1 . where 1 ( ) denotes the ranking level of . Since 1 (2) = 8 is the biggest, then 2 is in the highest ranking level. Similarly, where the preference order among 1 , 6 , 9 and the preference order among 4 , 7 , 8 has not been determined, as they are in the same ranking level, i.e., they are close to each other. They will be further compared and divided into multiple ranking levels. For 1 , 6 , 9 , the pairwise comparison matrix with respect to these three items is ℳ 2 . According to 2 we have

1 ≻ 9 ≻ 6
Then this branch will stop and return the ranking with respect to 1 , 6 , 9 , as each ranking level only has one item according to 2 . For 4 , 7 , 8 , the pairwise comparison matrix with respect to these three items is ℳ 3 .

3 = ⎡ ⎣ 0 0 1 1 0 0 0 1 0 ⎤ ⎦ So we have 3 = [ 1 1 1 ]
According to 3 , 4 , 7 , 8 can not be divided into different ranking levels any more, i.e., they are in an stationary level.

Their preference order will be determined according to some traditional ranking fusion method. In this example, we use Borda count method. According to Borda count we have

7 ≻ 4 ≻ 8
Then this branch will stop and return the ranking with respect to 4 , 7 , 8 , as these three items are in an stationary level according to 3 . Till now we have obtain the order list with respect to all the items, i.e.,

2 ≻ 1 ≻ 9 ≻ 6 ≻ 3 ≻ 7 ≻ 4 ≻ 8 ≻ 5 thus the final fused ranking is = [ 2 1 5 7 9 4 6 8 3 ]
The average ranking distance of together with the results of traditional ranking fusion methods are listed in TABLE I, where HRA is our new method and KOA is the Kemeny optimal aggregation found by traversing all of the possible rankings. According to TABLE I, in this example, the result of HRA is better than traditional ranking fusion methods based on ARDC, and the fused ranking of HRA is the same with Kemeny optimal aggregation.

Note that the stationary level appears only when all the items can not be divided into multiple levels (or sub-levels) any more, i.e., all the items still locate in the same ranking level according to the comparisons among themselves, such as 4 , 7 , 8 . In this case, every item wins half of the other items in this stationary level, i.e., these items are really close to each other. Although HRA uses Borda count to deal with the stationary level items as a auxiliary method, using HRA is better than only using Borda count to determine the whole fused ranking.

IV. SIMULATIONS

To verify the validity of the novel hierarchical ranking aggregation method, in this section, we use Monte-Carlo simulations with different settings. The rankings to be fused are randomly generated with different parameter settings in different simulations. Then different ranking fusion methods are used to fuse these rankings generated. The performance of the ranking fusion methods used are compared.

The parameters involved in the generations of simulation settings are given in TABLE II. In each run, a seed ranking

Parameters

Meanings number of rankings to be fused number of items swapping times with respect to items is randomly generated. Then, randomly select two items in and swap their positions. Such a random selection and swapping will be repeat times to generate a ranking to be fused. The swapping times can be different for different single rankings. The rankings generated with small are similar to each other, as they are all similar to the seed ranking. The ranking generated with large are quite different from all the other rankings generated. In each run, rankings are generated. In the simulations, Borda Count, REV, SSA 2 , IRV, CPS and HRA are used to fuse the input rankings. The fused rankings generated by different methods are evaluated according to average ranking distance criterion (ARDC). Totally 100 runs are executed, where in each run a seed ranking is randomly regenerated. The performance of different methods used are evaluated using the average of the 100 runs. When the number of items is small, the Kemeny optimal aggregation is found by traversing all of the possible rankings.

Simulation 1: This simulation compares the performance of different methods in the cases with small number of items and input rankings. We design three simulation settings with different similarity degrees. The simulation settings are shown in TABLE III. Note that there are in total three rankings to Because in this simulation the number of items is small, so we find the Kemeny optimal aggregation (KOA) by traversing all of the possible rankings. According to TABLE IV, the performance of HRA is better than traditional ranking fusion methods, i.e., Borda count, REV, SSA 2 , IRV and CPS, and its results are very close to the results of KOA. Furthermore, TABLE IV only lists the average ranking distance of different methods in different simulation settings. It should be better to provide further detailed comparisons among the different ranking fusion methods by considering KOA as the optimal one. Here we define the difference rate , which is calculated according to [START_REF] González-Pachón | Aggregation of partial ordinal rankings: an interval goal programming approach[END_REF].

= * - (20)
where is calculated using [START_REF] Luce | Individual Choice Behavior: A Theoretical Analysis[END_REF] with respect to the result of KOA and * is calculated with respect to the results of different ranking fusion methods. As aforementioned, if is small, the corresponding fused ranking is good and KOA finds the optimal fused ranking by traversing all of the possible rankings. Thus * ≥ , i.e., ≥ 0, and a smaller is better, i.e., the corresponding fused ranking is closer to the optimal fused ranking. The mean, maximum and minimum of with respect to different ranking fusion methods are calculated in 100 runs and shown in Figures 2∼4.

In these three figures, the histogram indicates the mean of , and the top and the bottom of the error bar (blue vertical line segment) denote the maximum and minimum of in 100 runs, respectively. According to Figures 2∼4, the performance of HRA is better than the other traditional ranking fusion methods. The mean of HRA is the smallest. Especially in setting 1, the mean of HRA nearly equals to 0, i.e., in each run, the result of HRA is very close to the optimal fused ranking. Furthermore, the top of HRA's error bar is the lowest one and the length of its error bar is the shortest one, i.e., the fused ranking obtained using HRA is more reliable than the results of the other traditional ranking fusion methods. Simulation 2: This simulation compares the performance of different methods in the cases with large number of items and more input rankings. We also design three simulation settings with different similarity degrees. The simulation settings are shown in TABLE V. Note that both setting 4 and setting 5 totally contain ten rankings to be fused. Most of the rankings in setting 4 are similar to each other and most of the rankings in setting 5 are quite different from the others. All the rankings in setting 6 are quite different from the others. The average ranking distance of different methods are listed in TABLE VI. According to TABLE VI, the performance of HRA is better than traditional ranking fusion methods, as the average ranking distance of HRA is smaller than traditional ranking fusion methods in all these three settings. Because in this simulation the number of items is too large to find the KOA by traversing all of the possible rankings. Here, we do not provide the result of KOA and the difference rates of different ranking fusion methods compared with KOA.

V. CONCLUSION

A novel Hierarchical Ranking Aggregation approach is proposed in this paper. According to HRA, the ranking fusion is implemented by dividing all the items into multiple ranking levels hierarchically. The items in the same ranking level are further divided according to the pairwise comparisons between the items in this ranking level, where the preference order among the close items are further compared. In simulations no matter when the number of items and the number of input rankings are small or big, HRA performs better than traditional ranking fusion methods as its results have smaller average ranking distances. Moreover, the fused ranking of HRA has Furthermore, evaluation criteria are crucial for ranking fusion. In future work, we will try to design better evaluation criteria for analysing the performance of HRA and the robustness of HRA to the rank reversal.

B. Batch mode methods 1 )

 1 Borda Count: It works based on the ranking positions of items directly. It assigns each item ( = 1, 2, ..., ) a score ( ) based on the position provided by ( = 1, 2, ..., ).

Fig. 1 .

 1 Fig. 1. Hierarchical fusion process of HRA.

  represents the ranking position of corresponding item in each ranking. Here we show the fusion process of HRA.

⎦

  According to ℳ 2 the preference order between each pair of items is generated and the pairwise comparison decision matrix 2 is as

⎦

  According to ℳ 3 , the pairwise comparison decision matrix 3 is generated, as

Fig. 2 .Fig. 3 .

 23 Fig. 2. Results in Setting 1.

Fig. 4 .

 4 Fig. 4. Results in Setting 3.

TABLE I RESULTS

 I OF DIFFERENT RANKING FUSION METHODS.

	Method	Ranking	Average ranking distance
	Borda	4, 1, 5, 7, 8, 3, 6, 9, 2	0.3500
	REV	4, 1, 5, 7, 8, 3, 6, 9, 2	0.3500
	SSA 2	4, 1, 5, 7, 8, 3, 6, 9, 2	0.3500
	IRV	3, 1, 2, 8, 5, 7, 6, 9, 4	0.3667
	CPS	3, 2, 5, 8, 7, 1, 6, 9, 4	0.3500
	HRA	2, 1, 5, 7, 9, 4, 6, 8, 3	0.3333
	KOA	2, 1, 5, 7, 9, 4, 6, 8, 3	0.3333

TABLE IV SIMULATION

 IV RESULTS IN SETTINGS 1 ∼ 3.

	Methods	1	settings 2	3
	Borda	0.2314	0.2456	0.2916
	REV	0.2165	0.2479	0.2828
	SSA 2	0.2137	0.2469	0.2828
	IRV	0.2356	0.2636	0.3045
	CPS	0.2085	0.2397	0.2722
	HRA	0.1966	0.2257	0.2622
	KOA	0.1950	0.2233	0.2581

TABLE VI SIMULATION

 VI RESULTS IN SETTING 4 ∼ 6. smaller difference rate , i.e., it is more reliable than the results of other methods.

	Methods	4	settings 5	6
	Borda	0.2151	0.2927	0.3390
	REV	0.2183	0.2933	0.3393
	SSA 2	0.2174	0.2933	0.3393
	IRV	0.2461	0.3448	0.4016
	CPS	0.2154	0.2923	0.3385
	HRA	0.1932	0.2837	0.3358

a

The ranking level with larger subscript number is a higher ranking level.

is in the lowest ranking level. 1 ,

, 9 are in the same ranking level, and 4 ,

,

are also in the same ranking level. Then we have2 ≻ 1 , 6 ,

≻ 3 ≻ 4 , 7 , 8 ≻ 5

ACKNOWLEDGMENT This work was supported by the Grant for State Key Program for Basic Research of China (973) (No. 2013CB329405), National Natural Science Foundation (No. 61573275), Science and technology project of Shaanxi Province (No. 2013KJXX-46), Specialized Research Fund for the Doctoral Program of Higher Education (20120201120036), and Fundamental Research Funds for the Central Universities (No. xjj2014122, xjj2016066).


Minh-Quan Quan Ho
email: minh-quan.ho@imag.fr

Bernard Tourancheau
email: bernard.tourancheau@imag.fr

Christian Obrecht
email: christian.obrecht@insa-lyon.fr

Benoît Dupont

Benoît Dupont De Dinechin

Jérôme Reybert
email: jerome.reybert@kalray.eu

MPI communication on MPPA Many-core NoC: design, modeling and performance issues

Keywords: Many-core, NUMA, Distributed memory, Networkon-Chip, MPI, Performance modeling, Linpack, HPL, MPPA

come

INTRODUCTION

In this paper, we propose the design of an MPI Message-Passing library [START_REF] William D Gropp | Using MPI: portable parallel programming with the message-passing interface[END_REF] for the intra communication on many-core processors, using the vendor support library (MPPAIPC [START_REF] Dupont De Dinechin | A Distributed Run-Time Environment for the Kalray MPPA R -256 Integrated Manycore Processor[END_REF]) as the transfer-fabric to build MPI protocols from scratch, while porting any of existing MPI implementations such as MPICH or OpenMPI would not be possible due to limited on-chip memory of most recent many-core processors.

Based on studied MPPA hardware specifications presented in [START_REF] Dupont De Dinechin | A clustered manycore processor architecture for embedded and accelerated applications[END_REF], [START_REF] Dupont De Dinechin | A Distributed Run-Time Environment for the Kalray MPPA R -256 Integrated Manycore Processor[END_REF], this paper does a brief hardware summary and focuses on an MPI design over (but not limited to) the MPPA architecture, with detailed implementation algorithms and formulated models following vendor-hardware characteristics (K, h) and different optimizing approaches (Lazy, Eager). These studies is generic enough to be compared/ported to other very-similar architectures, such as Tilera [START_REF]Tile processor architecture overview for the Tilepro series[END_REF], STHORM [START_REF] Mottin | The STHORM Platform[END_REF] or Neo chip [START_REF] Hemsoth | The Tiny Chip That Could Disrupt Exascale Computing[END_REF], on which doing/optimizing MPI communication over Network-on-chip is still a challenging or never-posed question.

The remainder of this paper is organized as follows: Section I briefly introduces the MPPA architecture and the MPPAIPC components used in our implementation. Section II describes our MPI architecture design. Section III resumes our MPI implementation in pseudo-codes of blocking and non-blocking communication (MPI_Send and MPI_Isend). Some optimization ideas are then proposed and developed in this section such as (1) synchronization-free "eager send" and (2) implicit local-buffered "lazy send" for short and medium sized messages respectively. A throughput estimation model based on the data transmission time is also introduced in section IV to evaluate the communication performance. Section V presents our results for the ping-pong test following two scenarios, either symmetric ranks (MPI compute node -MPI compute node) or asymmetric ranks (MPI compute node -MPI I/O), corresponding on MPPA to CC-CC and CC-I/O subsystem respectively. Different optimization approaches are also tested and compared.

Using the MPPA-MPI library, the HPL benchmark [START_REF] Petitet | HPL -A Portable Implementation of the High-Performance Linpack Benchmark for Distributed-Memory Computers[END_REF] [START_REF] Jack J Dongarra | The LINPACK benchmark: past, present and future[END_REF] was ported on MPPA with the support of the standard BLAS-Netlib [START_REF] Chuck L Lawson | Basic linear algebra subprograms for Fortran usage[END_REF] [10] (mono-threaded) and OpenBLAS [START_REF] Xianyi | OpenBLAS, version 0.2. 8[END_REF], an OpenMP optimized implementation. These benchmark results are summarized in section VI. Related MPI-oriented works on other many-core platforms will also be compared in section VII and conclusions are given in section VIII.

I. MPPA-256 ANDEY HARDWARE AND SOFTWARE

A. Architecture overview

The MPPA-256 Andey [START_REF] Dupont De Dinechin | A clustered manycore processor architecture for embedded and accelerated applications[END_REF] embeds 256 VLIW compute cores grouped into 16 compute clusters (CC) and four I/O subsystems (IOS), with theoretical performance of 230 GFlops (in single-precision) and 70 GFlops (in double-precision) and an energy consumption of 10 W.

1) Compute Clusters (CC): Each compute cluster operates 2MB of banked parallel memory shared by 17 VLIW cores running at 400 MHz. These cores are divided into 16 user cores referred to as Processing Elements (PEs) and one systemreserved core known as Resource Manager (RM). Each PE and RM are fitted with private 2-way associative 8KB instruction cache and 8KB data cache. The shared memory owns one Rx and one Tx NoC interface, paired with a 8-channel DMA engine and a Debug Support Unit (DSU). An MPPA-256 processor amounts to a total 32MB of memory distributed over the 16 CCs.

2) I/O Subsystems (IOS):

The four I/O subsystems (North, South, East, West), each containing four cores, integrate DRAM controllers managing the off-chip DDR memory, a 8-lane Gen3 PCI-Express and Ethernet links, as well as an Interlaken link intended to extend the NoC across multiple MPPA-256 chips, and other I/O devices.

3) Network-on-Chip: CCs and IOS are connected by two network-on-chip. The both Data NoC (D-NoC) and Control NoC (C-NoC) [START_REF] Dupont De Dinechin | A Distributed Run-Time Environment for the Kalray MPPA R -256 Integrated Manycore Processor[END_REF] ensure reliable delivery (lossless) thanks to the credit-based flow control mechanism [START_REF] Khorsandi | Robust non-probabilistic bounds for delay and throughput in credit-based flow control[END_REF] and FIFO packet arrival using static NoC routing [START_REF] Bertozzi | NoC synthesis flow for customized domain specific multiprocessor systems-on-chip. Parallel and Distributed Systems[END_REF]. No acknowledgment is needed at the packet reception. As a result, there is no need to consider a TCP layer implementation when building any communication library above these NoCs (e.g MPI).

B. MPPA Inter-Process-Communication (MPPAIPC)

One of several programming models currently available on the MPPA platform that matches our working scope in this paper is MPPAIPC -an MPPA-specific POSIX-compliant library [START_REF] Dupont De Dinechin | A Distributed Run-Time Environment for the Kalray MPPA R -256 Integrated Manycore Processor[END_REF] following the distributed memory model, where communication and synchronization between CCs and IOS are explicitly done by developer. These actions are achieved using IPC primitives through connecting objects listed in Tab. I.

Sync object provides light-weight and low-latency synchronization barriers by exchanging 64-bits messages on CNoC. This connector can be used to implement two types of barriers:

• Master-Slaves (1 : M) between an I/O subsystem and several (or all) compute clusters in case of sequential process splitting

• All-to-all (M : M) barrier between compute clusters, similar to MPI_Barrier()

Portal object supports data transfer on DNoC using onesided communication with zero-copy transfer. The sender (Tx) can write to the receiver's buffer (Rx) via a known dnoc_tag number, with an optional offset. This can be used to implement N-to-1-data-collection by many distinct writes from one (or several) Tx process(es) to the same Rx buffer, and at different offsets (see Fig. 2). RQueue object implements FIFO 120-byte-message queues with user-defined receive buffer length (120×nb slot). The inbound flow is controlled by a credit mechanism that ensures available buffer space to store incoming messages before being handled by the Rx rank. Callback function on message arrival can be defined to implement an Active Message Server [START_REF] Von Eicken | Active messages: a mechanism for integrated communication and computation[END_REF].

Channel object proposes point-to-point communication link with rendez-vous behavior. The Rx rank sends its buffer size to the Tx rank in a CNoC packet. The Tx rank then reads the buffer size and sends data through DNoc on a known dnoc_tag.

Both Portal and Channel objects contain primitives for data transfer. Otherwise, the current implementation of Portal provides higher performance and is more feature-rich than the Channel one. Portal integrates one-sided communication in either unicast or multicast, supports both blocking and nonblocking data sending (Tab. II). Meanwhile, Channel, at the time of this writing, provides only rendez-vous blocking sends. Indeed, the Portal object was used to implement the transfer layer of our MPPA-MPI model. An RQueue-message active server is also an important module as well. • exchanging information about MPI transaction type (send/receive, communicator split, etc.).

Mode

• synchronization point in case of rendez-vous protocol.

We implemented an RQueue-based active message server [START_REF] Von Eicken | Active messages: a mechanism for integrated communication and computation[END_REF] on each MPI rank (CC and IOS) to handle incoming control messages from all other ranks (including itself on loopback). Upon control message arrival, a callback function is executed on the RM, consisting typically on saving it into an internal buffer which later will be read by MPI calls from the main function (PE0).

Control messages exchanged in the MPIC layer contain either one of the structures defined in Fig. 3. In an MPI send/receive, The Tx rank posts a Request-To-Send (send_post_t) to the Rx rank; idem, the Rx rank sends back a Clear-To-Send (recv_post_t) containing its allocated dnoc_tag, to which the Tx rank will send data. Beforehand, this dnoc_tag needs to be configured and linked to the receive buffer to enable remote writing.

2) MPI-inter-process Data-Transfer (MPIDT): is a lightweight wrapper of MPPAIPC Portal primitives. Once the Tx rank has got a matching control message, it configures a data transfer using received information (e.g. dnoc_tag). Data can then be sent in either blocking or non-blocking mode dependent on the calling MPI function, using appropriate Portal primitives (see Tab. III for detailed function mapping). Fig. 4 illustrates the structure of our MPPA-MPI implementation. Each rank emits control-message(s) to its involved partner(s) at each MPI call. The active server runs on the RM core and processes incoming control-messages. Furthermore, depending on MPI transactions and their status at runtime, the server can decide whether to perform a data send if this has not been or could not be done by the main thread, especially in case of a pending MPI_Isend request or a matching registered "lazy" message.

MPPA-MPI MPPAIPC Portal

III. MPPA-MPI IMPLEMENTATION

As mentioned above, on-flight control messages carry essential information depending on their purpose. We present now their usage as well as algorithms of the two communication scenarios in our work:

(1) synchronous blocking send (MPI_Send) and (2) asynchronous non-blocking send (MPI_Isend)

A. MPI Send -MPI Recv

Most well-known and optimized MPI libraries contain many (combined) techniques to perform the MPI_Send call. In the first time, we chose to implement this function with rendez-vous blocking behavior, in order to avoid extra buffer space and minimize memory usage. This choice certainly adds more synchronization cost but does not change the functionality of the send/receive transaction. Some optimization approaches will be presented in the coming sections. Algorithms 1 and 2 summarize the implementation of MPI_Send and MPI_Recv.

Algorithm 1 MPI Recv(buf, count, datatype, source, tag, comm, status) recv post ← find recv post(count, datatype, tag, ...); 7: until recv post = NULL 8: /* send data (MPIDT layer), using mppa pwrite(s) */ 9: send data(buf, count, datatype, recv post.dnoc tag); 10: return MPI SUCCESS;

The implementation of MPI_Irecv is the same as the one of MPI_Recv, except that the function returns right after having posted the receive to the sender, and the completion of reading (mppa_aio_wait) is done in MPI_Wait.

B. MPI Isend -MPI Recv

The implementation of MPI_Isend uses non-blocking Portal primitives on both PE and RM on the Tx side. When the Tx rank (PE0) reaches MPI_Isend in its execution without having received any matching recv_post, it creates a "non-started" pending_isend request containing related information (buffer pointer, dest, count, tag etc.) and returns. On arrival of the matching recv_post, the RM core (callback handler) reads the previous pending_isend request and triggers a non-blocking data send (to the recv_post.dnoc_tag of the Rx rank). The request is then set to "started" state to be distinguished from other "nonstarted" requests.

On the other hand, when the recv_post arrives before MPI_Isend, the RM core saves it into the internal buffer. The PE core executing MPI_Isend later reads this recv_post, performs a non-blocking send and marks the pending_isend request as "started". This propriety ensures that the transfer is performed only once for each transaction, either by the PE core (in MPI_Isend) or by the RM core (in callback handler). At the end, "started" requests will be finished and cleaned by MPI_Wait. Algorithms 3 and 4 present in more details the implementation of MPI_Isend and of the callback handler. save recv post(recv post); 10: end if 11: return ; C. Optimization 1) Eager send optimization: Our idea is to pack any MPI message which can fit into a 120-byte space, as a controlmessage and send it directly to the Rx's active server. In reality, the maximum data payload is about 96 bytes (24 bytes is used for control header). An eager_buffer needs to be allocated on each MPI rank and can be defined by the EAGER_BUFFER_LENGTH macro in main.c. This approach is synchronization-free when the MPI_Send call can return before a matching receive is posted (non-local). It also leads to an improvement of about 6 to 10% in performance for the HPL benchmark on MPPA (see Section VI).

For longer messages, using several "eager sends" introduces segmentation and reassembly costs. We implemented a test case where messages are splitted into "eager" pieces in order to determine the best communication trade-off in Fig. 6. Such segmentation however consumes memory for buffers and therefore puts more pressure on RM's resources and limits its usage in practice.

2) Lazy send optimization: Lazy send consists in copying medium-size message into a local buffer and returns. The RM is then responsible for sending it to the destination. Unlike eager_buffer on the Rx side, lazy_buffer is allocated on the Tx side and can be tuned via some macros (LAZY_THRESHOLD, LAZY_BUFFER_LENGTH).

This approach must be used with care because bad communication scheduling may lead to wasting and lazy messages remaining for too long. Inversely, a dense communication scheme should neither be set to "lazy" mode in order to be able to send data directly rather than spending time doing memcpy in local memory.

3) DMA thread usage: MPI_Isend uses Portal nonblocking primitive to configure a Tx DMA thread for data sending. The DMA engine implements a fetch instruction that loads the next cache line while pushing the current line into the NoC. This fetch is nowadays not available on PE cores, meaning that outbound throughput using PE is 4 times lower than using DMA engine (1 B/cycle vs. 4 B/cycle). Thus, tuning to use non-blocking DMA on MPI_Send for messages of size greater or equal to DMA_THRESHOLD will maximize the transfer performance.

IV. MPPA-MPI THROUGHPUT MODELING

The MPPA-256 Network-on-chip [START_REF] Inc | MPPA-256 Cluster and I/O Subsystem Architecture[END_REF] is designed so that any path linking two CCs always contains less than eight hops (including two local hops -one at sender and one at receiver). The average switching time on a NoC router is 7 cycles, then it takes the packet at most 8 cycles to reach the next hop. In the worst case, the link distance (time a packet spends on NoC to reach its destination) is 112 cycles (7 × 8 + 8 × (8 -1)). However, the necessary time to send a buffer (transmission time -t) is about O(N ) cycles [START_REF]MPPAIPC Performance[END_REF] (where N the buffer size in bytes), which is much longer than the link distance [START_REF] Kumar | A network on chip architecture and design methodology[END_REF].

As a result, we describe the transmission time t as a function of the buffer size N , a constant transfer ratio K and a default overhead h (aka. the cost of sending an empty buffer). This default overhead presents the initial cost of MPI implementation management (ID mapping, metadata setup, synchronization, error checking ...) and/or configuring the peripherals (cache, DMA) to prepare for data sending. This cost is paid on each MPI call and is independant to the subsequent data-sending process (which is presented by a datatransfer factor K). The ping-pong round-trip time (RTT) is approximately the sum of the transmission time on both sides, as the propagation time is negligible.

T ransmissionT ime : t = K × N + h (cycles) (1) RT T 2 × t = 2 × (K × N + h) (cycles) (2)
T hroughput :

T = 2 × N RT T N K × N + h = 1 K + h N (bytes/cycle) (3) lim N →∞ T lim N →∞ 1 K + h N = 1 K (bytes/cycle) = 400 × K -1 (M B/s) (at f requency 400 M Hz) (4)
The constant K is a value specific to each send function with its own underlying transport primitive. For example, the MPI_Isend which uses the DMA engine with peak throughput of 4 B/cycle, would have its transfer ratio K of about 0.25. The MPI_Send, with default peak throughput of 1 B/cycle (no DMA engine), should obtain a transfer ratio K around 1.

V. RESULTS AND DISCUSSION

Using the MPPA Developer platform [START_REF] Inc | Kalray platforms and boards[END_REF] with AB01 board and MPPA-256 Andey processor integrated, we set up pingpong tests between: In each case, the same MPI send function is used on both sides (MPI_Send or MPI_Isend). At the first time, all tests are run without any optimization in order to calibrate the proper throughput of each context (Fig. 5). At the second time, we enable all optimization on the MPI_Send test and compare our optimization approaches in term of latency, throughput and messages sent per second (Fig. 6).

Each ping-pong is repeated 50 times. We assume that there is no waiting time inside the MPI send function, since all ranks start at the same time and run at the same clock speed. Hence, the duration of the MPI send function can be considered as the transmission time. Depending on the send context, the measured transmission time is fitted into a linear correlation K × N + h presented in Tab. IV. The standard deviation from all obtained results is always less than 0.2%.

A. Compute cluster ↔ Compute cluster

Communication links between CCs are bi-directionally symmetric. According to our model and the K values from Tab. IV, the estimated maximum throughput (given by 400 × MPI_Send and MPI_Isend respectively. The ratio h N can be ignored in this case. Fig. 5a shows obtained results that match with our estimation model.

K -1 M B/s) should

B. Compute cluster ↔ I/O subsystem

Contrary to the symmetric communication performance between CCs, the transmission rate on I/O subsystem relies on the DDR bandwidth, which is much lower than the on-chip memory on CCs. We observed higher K values and much more considerable overhead h on the IOS 128, showing that the communication link from IOS to CCs might be the bottleneck on the MPPA. It is then difficult ignoring h N in this case. Keeping on our throughput estimation by 400 × (K + h N ) -1 now matches with experiment results on Fig. 5b, where the performance gap between the CC 15 and the IOS 128 is also illustrated.

C. Optimization comparison

We focus now on finding, on a given message size, the best send method among the four (Normal, Eager, Lazy and DMA) to use on MPI_Send, in order to obtain lowest latency (roundtrip-time) and/or highest ping-pong throughput, by enabling all optimizations and re-running our experiments between CCs. We also evaluate the number of messages sent per second in each approach by dividing the clock frequency (400 MHz) by the duration of the MPI_Send call (in cycles). As the message will now be "eagerly" sent or "lazily" buffered and MPI_Send returns right afterward, this duration on Eager(-splitting) or Lazy could no longer be evaluated as the transmission time in the Tab. IV, but respectively by :

E × (f loor( N 96 ) + 1) (cycles, E ≈ 3800) (5)
O memcpy (N ) = 1.28 × N + 5300 (cycles)

where E is the constant necessary cost to send 1 eager-split and O memcpy is a linear function of memcpy cost. Note that in the Lazy approach, the message is sent in background by the RM.

Hence, Eager and Lazy methods provide lower latency and higher message rate on short buffers, since they were designed to get rid of two-sided synchronization and the buffer size is still small enough not to be outperformed by the DMA's highthroughput capacity. Fig. 6a shows that the ping-pong latency for [1 .. 256 B] using eager-splitting is reduced by half compared to DMA or Normal. Otherwise, this latency increases radically as soon as its transmission time, despite being smaller at the beginning, getting repeated as many times as split segmentation (f loor( N 96 ) + 1). On the other hand, using DMA on large buffers optimizes bandwidth utilization compared to Normal (using PE) or Lazy (using RM) methods. (Fig. 6b).

Fig. 6c illustrates the message-rate of the four send methods. Not only this kind of measure gives user a high-level point of view about the implementation's capacity to support communication load, but it shows interesting advantages of Eager and Lazy methods in tuning MPI applications, thanks to their fast sending time for short messages and synchronizationfree algorithm.

VI. HIGH PERFORMANCE LINPACK (HPL) ON MPPA-256 HPL benchmark was ported on MPPA-256 using our MPI implementation and cross-compiling of BLAS-Netlib and OpenBLAS. Each MPI compute rank, assigned to a compute cluster, only disposes 2 MB of memory, that make a total onchip memory of 32 MB, enable to store up to 4 million double precision floating point numbers or a 2000 × 2000 matrix. Operating system space and user code (BLAS, MPI, HPL) must be taken into account as well. In practice, the HPL can run on the MPPA-256 with 1250 × 1250 matrix, which is a very small problem size for this kind of benchmark. As a result, communication, local indexing etc. has a significant cost with respect to the number of floating point operations (O(N 3 )). Fig. 7b. does an estimation on further problem sizes if MPPA disposes more on-chip memory than its current capacity. Fig. 7a shows the HPL result on MPPA-256 using BLAS and OpenBLAS. Note that 70 GFLOPS of annouced theoretical performance is for all the 256 cores, while the best benchmark score (R max = 1.2 GFLOPS) was achieved using only 1 core per CC (i.e 16 cores in total) and MPI "eager" send. Also, we have seen no performance change by enabling MPI "lazy" optimization. This can be explained by well-scheduled HPL overlapping [START_REF] Jack J Dongarra | The LINPACK benchmark: past, present and future[END_REF] in which, either MPI processes arrive to the communication step at the same time, or all heavy sends are done asynchronously by MPI_Isend, while lazy sending only shows its advantage in bad-scheduled MPI_Send. Furthermore, multi-threading on MPI compute ranks (OpenMP on CCs) did never give better HPL result, because of the small working set and the OpenMP overhead.

VII. RELATED WORKS

A. MPI libraries design

Our design is similar to the co-processor-only MPI model on the Intel Xeon-Phi TM platform [START_REF] Jeffers | Intel Xeon Phi Coprocessor High Performance Programming[END_REF], with support of OpenMP for hybrid multi-threaded programming. Besides MPI ranks running on CC, we introduce an MPI I/O rank running on an I/O subsystem of the chip as bridge to communicate with the host through the PCI-e interface, while there are no direct communication link between the host and the compute clusters on MPPA. Along the way, some collective MPI functions were also implemented (MPI_Comm_split, MPI_Bcast, MPI_Reduce, MPI_Allreduce and MPI_Barrier).

Our message-trigger handling mechanism using the RM core was inspired by the similar work of Prylli and Tourancheau [START_REF] Prylli | BIP: a new protocol designed for high performance networking on myrinet[END_REF] [START_REF] Prylli | Modeling of a high speed network to maximize throughput performance: the experience of BIP over Myrinet[END_REF] implementing the BIP protocol for an optimized MPI implementation over the Myrinet network, taking advantage of its dedicated hardware, an extra core like the MPPA RM core.

B. Similar architectures

Today, there exist other multi/many-core processors similar to the MPPA. Some of them has an MPI implementation, others do not. This section reviews these achitectures and, if existing, summarizes any MPI-oriented libraries and their performance related to our work.

Freescale P4080 multi-core processor [START_REF]QorIQ P4080 Communcations Processor Product Brief[END_REF], based on the PowerPC architecture and resources virtualization technology from IBM, is mostly used in avionic industries and critical real-time systems. The P4080 processor has eights cores connected through CoreNet -the proprietary NoC of Freescale. Cache-coherence is guaranteed by a hardware mechanism. Our research for MPI implementation and topic on this platform did not encounter any relevant reference.

Raw processor [START_REF] Bedford | The Raw microprocessor: A computational fabric for software circuits and general-purpose programs[END_REF], designed by the Computer Science Laboratory at MIT, combines 16 identical compute units, called tile. The 16 tiles are connected by one static NoC and two dynamic NoC. The static network is used for predefined memory access pattern at compile time, the dynamic ones are used for communication scheme at runtime. Psota and James [START_REF] Ryan | rMPI: An MPI-compliant message passing library for tiled architectures[END_REF] propose rMPI, the first MPI library over the Raw achitecture by inheriting some design aspects from MPICH and LAM/MPI also other specific implementation belonging to the Raw hardware. The highest throughput obtained on the ping-pong test of the Raw processor is about 150 MB/s with buffer size of 3.2 MB (100K words) [START_REF] Psota | rMPI: message passing on multicore processors with on-chip interconnect[END_REF].

STHORM processor [START_REF] Mottin | The STHORM Platform[END_REF] is a four-cluster-based Networkon-chip many-core from ST Microelectronics. Each cluster (named ENCore) hosts 16 STxP70-V4 processors (PE). Moreover, a special cluster unit, named fabric controller (FC) is responsible for interaction with the host memory and coordination of clusters. Coupled with an ARM processor as host, STHORM architecture mostly supports offloading model using either OpenCL [START_REF] Pierre G Paulin | OpenCL Programming Tools for the STHORM Multi-Processor Platform: Application to Computer Vision[END_REF] or through OpenMP [START_REF] Spiros N Agathos | Deploying OpenMP on an embedded multicore accelerator[END_REF] with extension primitives similar to #pragma omp target in OpenMP 4.0. Otherwise, no MPI library supporting the STHORM architecture was found as of this writing.

Neo chip [START_REF] Hemsoth | The Tiny Chip That Could Disrupt Exascale Computing[END_REF], announced on March 2015 by Rex Computing, is a 256 VLIW core MIMD, organized on a 2D Mesh NoC. It is designed to aim the HPC market with disruptive exascale power ratio. The cache and memory system on Neo is rethough to reduce energy consumption by cutting off the virtual memory translation and other unecessary components. This choice would further produce more complexity and security issues when implementing operating system and software stack over Neo chip.

Tilera processors [START_REF]Tile processor architecture overview for the Tilepro series[END_REF] are mainly used in high performance embedded systems such as networking and multimedia. The TilePro64 processor defines a flat 2D-mesh with 64 identical VLIW cores connected through the Tilera iMeshTM networkon-chip. Cache coherence on TilePro64 is guaranteed by a hardware mechanism called Dynamic Distributed Cache (DDC) [START_REF]Tile processor architecture overview for the Tilepro series[END_REF]. Kang et al. [START_REF] Kang | MPI performance analysis and optimization on tile64/maestro[END_REF] propose an MPI implementation on Tile64 processor which delivers up to 250 MB/s on MPI_Send/MPI_Recv communication, with the largest message size of 256 KB due to the limited memory per core. At this buffer size, our MPI implementation on MPPA delivers 400 MB/s on MPI_Send or up to 1 GB/s using DMA. Intel Single-Chip Cloud (SCC) is a prototype aimed to promote many-core processor. Its 48 cores are organized in 24 dual-core clusters with access to off-chip DRAM shared/private region for all/each core through a look-up table (LUT), also a dedicated shared on-chip Message Passing Buffer (MPB). This memory architecture gives extra advantage for implementing quick message sending based on shared buffers. However, the use of the dynamic NoC routing on Intel SCC (instead of static NoC in MPPA) makes it difficult to evaluate the maximum communication latency [START_REF] Bruno Dausbourg | Deterministic Execution on Many-Core Platforms: application to the SCC[END_REF] also incurs unordered packets, hence inappropriate for hard realtime applications.

The SCC-specific MPI-like native communication library (RCCE) delivers peak throughput of 55 MB/s on the ping-pong test [START_REF] Timothy G Mattson | The 48-core SCC processor: the programmer's view[END_REF]. By the same test, Clauss et al. [START_REF] Clauss | Evaluation and improvements of programming models for the Intel SCC many-core processor[END_REF] presented iRCCE (an improved RCCE version) and SCC-MPICH (an MPICHbased implementation over iRCCE) that reach respectively 150 MB/s and 120 MB/s of throughput. RCKMPI, an Intel MPI implementation for SCC is also bounded by the performance of the iRCCE layer. Our MPI library on MPPA was built from scratch over the MPPAIPC library, without any TCP/UDP layer, while an MPICH-based solution would not fit the cluster private memory space (2 MB). A such MPICH implementation on MPPA can be extrapolated to 1.0 GB/s by adding the same overhead of 20% of SCC-MPICH over to iRCCE.

Intel Many Integrated Core (MIC), known as Intel Xeon Phi co-processor family, is a many-core computer architecture with autonomous on-chip Linux operating system and x86 compatibility. Intel MIC proposes three MPI programming models [START_REF] Jeffers | Intel Xeon Phi Coprocessor High Performance Programming[END_REF] which are (1) offload (host-only), (2) coprocessor-only and (3) symmetric (both host and co-processor). The MPI communication in the intra-MPPA context corresponds to the co-processor-only intra-MIC case. Potluri et al. [START_REF] Potluri | MVAPICH2-MIC: A High Performance MPI Library for Xeon Phi Clusters with InfiniBand[END_REF] studied the communication throughput of the MVAPICH2 library on Xeon Phi and their results show that a MICoptimized MVAPICH2 library can delivers more than 9 GB/s of uni-direction throughput for messages up to 1 MB.

VIII. CONCLUSIONS

In this paper, we have introduced the design and performance issues of an MPI implementation on the Kalray MPPA-256. The MPPA-MPI library provides 1.2 GB/s of throughput for any inter compute-cluster point-to-point communication and this performance depends on the underlaying MPPAIPC library. Optimization ideas such as eager send and lazy message are proposed, implemented and compared to determine the best approach based on threshold. A synthetic model is also presented for each approach to evaluate their communication latency and throughput. We also learn that supporting MPI programming model is not an easy task on recent many-core processors, including MPPA, since MPI has become a large API with high-level abstractions and many-core hardware is taking more diversity and complexity. Thus, optimizing an MPI implementation on each of these platforms is even more not trivial.

On the other hand, the HPL benchmark is also successfully ported on MPPA as a validation test of our MPI library. The best performance of 1.2 GFLOPS is achieved by using only 16 cores instead of 256 available core due to limited on-chip memory makes us believe that traditional benchmark methods for supercomputers could hardly run effectively on many-core systems nowadays, given limited on-chip memory and the offchip bandwidth, as well as the cache coherence challenge. Some dedicated benchmark suites for embedded systems such as Core Mark [START_REF]The Embedded Microprocessor Benchmark Consortium[END_REF] and software APIs (like MCAPI [34]) may be a good match.

The next-generation MPPA processor aims at supporting global addressable DDR off-chip memory (Distributed Shared Memory) on clusters and will be more energy efficient. In a future work, we will study the performance gain and detailed power consumption of this new MPPA processor.

Fig. 1 :

 1 Fig. 1: MPPA-256 processor overview.

Fig. 2 :

 2 Fig. 2: Data collection on portal

Fig. 3 :

 3 Fig. 3: Control message structures

Fig. 4 :

 4 Fig. 4: MPPA-MPI components and interaction withNetwork-on-chip through MPPAIPC.

( 1 )

 1 MPI rank 0 (CC 0) -MPI rank 15 (CC 15) and (2) MPI I/O 128 (IOS 128) -MPI rank 15 (CC 15). All MPI cluster ranks run at the same clock frequency of 400 MHz. The North IOS running the MPI I/O rank is configured to use the DDR controller at the default frequency of 600 MHz.

15 Fig. 5 :

 155 Fig. 5: Ping-pong throughput MPI_Send (PE core) vs. MPI_Isend (DMA).

Fig. 6 :

 6 Fig. 6: Optimization approaches comparison.

Fig. 7 :

 7 Fig. 7: HPL current performance (a) and extrapolation (b)

TABLE II

 II

	Type	Pathname	Tx:Rx aio_sigevent.sigev_notify
	Sync	/mppa/sync/rx nodes:cnoc tag	N : M
	Portal	/mppa/portal/rx nodes:dnoc tag	N : M SIGEV_NONE, SIGEV_CALLBACK
	RQueue /mppa/rqueue/rx node:dnoc tag/tx nodes:cnoc tag/credits.msize N : 1	SIGEV_NONE, SIGEV_CALLBACK
	Channel /mppa/channel/rx node:dnoc tag/tx node:cnoc tag	1 : 1	SIGEV_NONE
		TABLE I: NoC connector pathnames, signature, and asynchronous I/O sigevent notify actions
	compute ranks on CCs subsequently. To keep the portability
	of any MPI legacy code, this extra MPI I/O rank is not
	listed in the MPI_COMM_WORLD. Any communication with
	this rank can be achieved through a "local communicator"
	(MPI_COMM_LOCAL ) that groups all MPI ranks within an
	MPPA processor (i.e 17 ranks). The MPPA-MPI architecture
	on each rank is then divided in two layers:
	1) MPI-inter-process Control (MPIC): Each MPI transac-
	tion begins by exchanging control messages at the MPIC layer
	between MPI ranks. Control messages are used for:
		: Portal connector primitives associating to send/re-
		ceive modes
			II. MPPA-MPI DESIGN
		In the MPPA context, each CC is referred to as an
		MPI rank. Thus, the MPPA-256 processor supports up to 16
		MPI ranks. Each MPI rank owns a private memory space
		of 2MB. Moreover, a hybrid MPI I/O rank is introduced
		running on the North IOS and manages the off-chip DDR
		memory. This MPI I/O rank is started from the host via the
		k1-mpirun command and is responsible for spawning MPI

TABLE III

 III

	MPI_Send, MPI_Ssend	mppa_pwrite,
		mppa_pwrites
	MPI_Isend, MPI_Issend mppa_aio_write
	MPI_Recv, MPI_Irecv	mppa_aio_read
	MPI_Wait	mppa_aio_wait

: MPI send/receive implementation in MPIDT level

  Algorithm 3 MPI Isend(buf, count, datatype, dest, tag, comm, request) 1: my rank ← get rank(comm); 2: /* send send post to dest */ 3: send send post(my rank, dest, tag, comm, ...); 4: req ← new request(buf, count, ..., PENDING ISEND); 5: /* look for a matching recv post (MPIC layer) */ 6: recv post ← find recv post(count, datatype, tag, ...); 7: if recv post = NULL then

	8:	/* configure/start a non-blocking write (MPIDT layer)
		*/
	9:	aio request	←	configure aio write	(buf,
		recv post.dnoc tag, ...);
	10:	req→status := STARTED;
	11:	req→aio request := aio request;
	12: else
	13:	/* Do nothing (request initialized NON STARTED) */
	14: end if
	15: request ← req;
	16: return MPI SUCCESS;
	Algorithm 4 callback recv post(recv post)
	1: /* look for a matching pending isend */
	2: req ← find pending isend(recv post);
	3: if req = NULL then
	4:	/* configure/start a non-blocking write (MPIDT layer)
		*/
	5:	aio request	←	configure aio write	(req→buf,
		recv post.dnoc tag, ...);
	6:	req→status := STARTED;
	7:	req→aio request := aio request;
	8: else

9:

  be around 408 MB/s and 1481 MB/s for

	From	To	MPI Send	MPI Isend
	CC 0	CC 15	t = 0.98 × N + 31430	t = 0.27 × N + 33690
	CC 15	CC 0	t = 0.98 × N + 30240	t = 0.27 × N + 32850
	IOS 128 CC 15	t = 13.52 × N + 159544 t = 0.84 × N + 181300
	CC 15	IOS 128 t = 0.98 × N + 129200	t = 0.26 × N + 144500

TABLE IV :

 IV Transmission time (cycles).