Elizangela M Menegassi Lima

Jorge A Pona

João Jose B Sacomano
email: jbsacomano@gmail.com

Dos Reis

Debora S Lobo

Elizangela M Menegassi Lima

Jorge G A Pona

João Gil- Berto Mendes

Relationships and Centrality in a Cluster of the Milk Production Network in the State of Parana/Brazil

Keywords: Clusters, Networks, Simultaneous Networks, Relationship, Milk

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

Introduction

The advent of globalization and the internationalization of the economy made the competitive advantages be seen as essential to the business management [START_REF] Tilahun | Transit and Job Accessibility: an Empirical Study of Access to Competitive Clusters and Regional Growth Strategies for Enhancing Transit Accessibility[END_REF][START_REF] Porter | Location, Competition, and Economic Development: Local Clusters in a Global Economy[END_REF][START_REF] Huggins | Competition, Competitive Advantage and Clusters: The Ideas of Michael Porter[END_REF]. Therefore, studies are needed to clarify new forms of regional operations in niche markets, due to their increasingly competitiveness, creating sustainable competitive advantages in that niche. This process requires the actors to implement a development policy and seek new concepts of organization of products and services in micro and macroeconomic terms, to favors a more flexible structure supported by new technologies [START_REF] Porter | Location, Competition, and Economic Development: Local Clusters in a Global Economy[END_REF], [START_REF] Söylemezoglu | Are Clusters Efficiente for the Relation Betweem Milk Production and Value Added per Capita in Regional Level? An Empirical Assessment[END_REF].

One of these new technologies used to increase the competitiveness of organizations is the approach by the concepts of Business Networks, mainly regarding the relationships between the actors and the centrality of the network [START_REF] Söylemezoglu | Are Clusters Efficiente for the Relation Betweem Milk Production and Value Added per Capita in Regional Level? An Empirical Assessment[END_REF].

However, the large number of actors involved makes it difficult to conduct a study of the agents' role in the structure of these networks. Thus, some studies have been developed by analyzing the company networks from the perspective of social networks using softwares such as UCINET and NetDraw [START_REF] Borgatti | Ucinet for Windows: Software for Social Network Analysis[END_REF].

The studies of Roy and Sarkar [START_REF] Roy | Identifying Influential Stock Indices from Global Stock Markets: A Social Network Analysis Approach[END_REF] proposed a method to rank the stock indices from across the globe using social network analysis approach; Söylemezoglu and Doruk [START_REF] Söylemezoglu | Are Clusters Efficiente for the Relation Betweem Milk Production and Value Added per Capita in Regional Level? An Empirical Assessment[END_REF] clearly confirm that the clustering approach has positive results in regional development and also values the cluster.

The aim of this study is to evaluate the network relationships of the milk production network, using Social Network Analysis (SNA) in the city of Umuarama-PR/BRAZIL, focusing on the collective gains and competitive advantages for the cluster of milk producers in the city For this, a survey was applied to agents of the milk production network through an analysis of the simultaneous networks (physical, value and business) [START_REF] Ferdows | Making the Most of Foreign Factories[END_REF], in three dimensions: relationship, governance and distribution of power and cost transaction. It is inferred that, when the relationships between the actors of a network are dense, the cluster becomes more competitive, allowing a local and regional growth.

2

Theoretical Background

Networks Analysis

In the relationships that occur within the organization between their individuals, it can be argued that the interactions between the various types of actors are understood and studied by the analysis of the theory of companies networks. [START_REF] Hahn | Network Structure, Organizational Learning Culture, and Employee Creativity in System Integration Companies: The Mediating Effects of Exploitation and Exploration[END_REF][START_REF] Spear | Reducing Radmissions to Detoxification: An Interorganizational Network Perspective[END_REF][START_REF] Grandori | Inter-Firm Networks: Antecedents. Mechanisms and Forms[END_REF][START_REF] Granovetter | Economic Action and Social Structure: the problem of Embeddedness[END_REF][START_REF] Williamson | The Nature of the Firm: Origins, Evolution, and Development[END_REF] The concept of business network is shown as a collection of individuals or organizations connected through relationships of various kinds, and that a network consists of nodes and links (lines or edges) that connect the nodes based on bilateral relations between two actors. [START_REF] Mohammadi | Women's Position in Intra Organizational Informal Relationship Networks: An Application of Network Analysis Approach[END_REF] In a network there is a central actor joining many other actors not connected to each other that helps to lead the actions of the group. This centrality describes the degree of the position where the individual can be found in this network. It is noteworthy that many are the quantitative indicators that measure and reflect the power of the actors. [START_REF] Söylemezoglu | Are Clusters Efficiente for the Relation Betweem Milk Production and Value Added per Capita in Regional Level? An Empirical Assessment[END_REF]. [START_REF] Mohammadi | Women's Position in Intra Organizational Informal Relationship Networks: An Application of Network Analysis Approach[END_REF] [START_REF] Shao | Research on the Influencing Factors of Customer Referral Behavior Based on Social Network -Application in the Catering Industry[END_REF].

The centrality emphasizes the positive effects of dense and consistent ties in a regulatory environment. Such ties facilitate trust and cooperation between individuals, and in return, provide benefits, such as information and knowledge sharing.

The existence of structural holes in a network represents business opportunities, in which an actor can join to complete the network [START_REF] Granovetter | Economic Action and Social Structure: the problem of Embeddedness[END_REF], [START_REF] Williams | Cooperation by Design: Structure and Cooperation in Interorganizational Networks[END_REF], [START_REF] Wäsche | Interorganizational Cooperation in Sport Tourism: A Social Network Analysis[END_REF]. A network can be characterized for its general structure and by the way it establishes the links between the actors. A business network is dense when the maximum of information takes place between the actors. On the contrary, the business network is considered diffuse when the relations between the actors are weak. [START_REF] Lazzarini | Empresas em rede[END_REF]

Networks Companies

In the study of the key attributes of companies networks it can be considered the existence of three sub networks that interact with each other, called Simultaneous Networks. These networks are divided into (a) physical network, (b) value network and (c) business network, as can be seen in Figure 1 [7]: The physical network is responsible for the activities or delivery functions of raw material supplies; from suppliers to the places of their effective use, it is there that the physical production of goods and/or services can be checked.

The value network is the place where occurs the alternative development activities to obtain the conditions for meeting the needs that customers consider important.

The actors of value networks are companies with areas of projects connected with the achievement of a particular item of value, such as universities, research centers, among others.

The business network is composed of agents that assess or measure the needs dictated by a given market; it is meant to discover them and pass on to their business partners; it should develop commercial activities, and is responsible for implementing activities that facilitate customer access to products and services [START_REF] Ferdows | Making the Most of Foreign Factories[END_REF], [START_REF] Hahn | Network Structure, Organizational Learning Culture, and Employee Creativity in System Integration Companies: The Mediating Effects of Exploitation and Exploration[END_REF], [START_REF] Fusco | Alianças em redes de empresas[END_REF].

In this study it was proposed a conceptual model of simultaneous networks, whose dimensions are shown in Figure 2.

Dimensions of the Milk Production Network

Relationship

Governance and Power Distribution Transaction Costs

The simultaneous networks Physical Enable the free flow of products, services and information.

Enable the reduction in operating costs by creating a more favorable working environment.

Are reduced in a cooperation environment due to the confidence of the members.

Value

Enable greater access to information and innovations to support the activities of the agent.

Enable efficiencies gains and make clear the network value creation processes.

More efficient operations and more credibility between the partners; generate lower transaction costs.

Business

Enables a better understanding between the agents and joint works for the network performance.

Enables more partnerships and more agility in decision making, identifying new opportunities, generating business. While all domestic production grew 5,1436 billion liters, the production in Parana grew more than 1 billion liters, which means that 19.60% of the national production growth between the years 2009 and 2013 were from Parana.

The milk production network in the state of Parana presents distinct aspects from the producing regions. For example, in the southern state, in the cities of Carambei, Castro, Palm and Arapoti (Ponta Grossa's region), some dairy cattle are among the best in the country, with the average yield in the region of about 4,000 liters/cow/year; however, in these regions it is not uncommon to come across properties that hit the mark 8,000-10,000 liters/cow/year.

Methodology

The study was conducted in the city of Umuarama, located in southern Brazil, in northwestern Parana region.

It was chosen a case study with descriptive approach with quantitative and qualitative methodology [START_REF] Wäsche | Interorganizational Cooperation in Sport Tourism: A Social Network Analysis[END_REF], using a survey research that is more appropriate for this type of approach [08], [START_REF] Mohammadi | Women's Position in Intra Organizational Informal Relationship Networks: An Application of Network Analysis Approach[END_REF] [START_REF] Shao | Research on the Influencing Factors of Customer Referral Behavior Based on Social Network -Application in the Catering Industry[END_REF].

The agents considered active participants in the milk production network are called:

 producer associations -milk producers associations operating in the city of the study. To collect data, questionnaires and interviews with participants in the milk network agents in the city of Umuarama -PR were made. The data were tabulated and it was attributed a value of 1 (one) when a particular agent relationship was appointed by the respondent, and attributed 0 (zero) when a particular agent relationship was not appointed by the respondent, forming with this an analysis matrix

The tabulated data were processed using the software UCINET to compute various metrics of interest for network analysis patterns and relationships [START_REF] Borgatti | Ucinet for Windows: Software for Social Network Analysis[END_REF], [START_REF] Spear | Reducing Radmissions to Detoxification: An Interorganizational Network Perspective[END_REF], [START_REF] Mohammadi | Women's Position in Intra Organizational Informal Relationship Networks: An Application of Network Analysis Approach[END_REF].

Fig. 3. Relationship Dimension Network

In Figure 3 the data analysis showed that the physical network is represented by the agents AG1, AG2, AG4 and AG8. The nodes AG3, AG5, AG7 and AG10 represent the value network, but may also belong to the physical network. The nodes AG6, AG9 and AG11 indicate the business network and may also be a participant of the physical network and of the value network.

The analysis showed that only AG4, AG6 and AG9 had significant factors in the relationship dimension, so the others are not the focus of consistent relationships.

This configuration shows that the network focuses its relationships at key points, but they fail to prioritize agents that could help in the development of the sector in the region, such as universities, dairy and producer association and industries.

The calculated density of this network was approximately 0,26; so, the physical network in the relationship dimension is considered diffuse [START_REF] Mohammadi | Women's Position in Intra Organizational Informal Relationship Networks: An Application of Network Analysis Approach[END_REF], [START_REF] Lazzarini | Empresas em rede[END_REF], what indicates that they are unprepared to reach the goal of a free flow of goods, services and information.

Governance and Distribution of Power Dimension

To demonstrate the adequacy of factor analysis [START_REF] Gujarati | Econometria Básica[END_REF] it was used the MOK (Meyer-Olkin Kaiser) test and the Bartlett's test of sphericity to study the governance and distribution of power dimension [GDPD].

The results showed that the relationship matrix performed wholly void, composed only of zeros, that is, without relationships, suggesting that the network is not being managed, and none of the concurrent networks is being governed in order to develop the sector as a whole.

As the relationship dimension has performed diffuse, the governance and distribution of power dimension performed similarly diffuse, as one is linked to the other.

Transaction Costs Dimension

The transaction costs dimension [TCD] has an important analysis parameter in relationships related to agribusiness. Figure 4 shows this dimension in the milk production network. The agent [AG3] with four significant ties of relationships shows that this agent is of greater impact in the transaction costs. This indication may be due to the purchase and handling of veterinary products

The agent [AG6] is related to this dimension due to regulatory issues and supervision exerted by the SEAB. The dairy market is a regulated market by the Brazilian Federal laws.

The questionnaires applied to the financial institutions that represent the agent [AG9] indicate a significant relationship of transaction costs with the agent [AG11]. Another important result showed that the farmers also point the agent [AG11] as focus of the relationship in this dimension.

Conclusions and Outlook

The analysis carried out in the simultaneous networks (physical, value and business) have shown unexpectedly that the current configuration of the existing relationship network in this production network is inadequate to promote collective gains and competitive advantages to its agents. Even making the analysis for three different dimensions they confirmed the lack of solid relationships to promote coordination of significant collective actions that could lead to a reduction of transaction costs and to collective gains for the participants in the milk production network, showing a diffuse network.

However, the research, and in particular the analysis of the relationship dimension, indicated significant ties -centrality indicators -in three agents, namely: milk producers, EMATER/SEAB, and financial institutions, representing respectively the production, the regulation and propagation of knowledge, and the finance and credit in the production network.

The connection between the three agents shows that they may be responsible for the beginning of a strategic policy of sectorial development, if encouraged to fulfill this function. The research reaffirms also the importance of integration among the supply network agents, in an organized way for better competitive benefits.

For future studies it is suggest the study of other networks, focused on their density and determination of continuous improvement factors using this same procedure.

Fig. 1 .

 1 Fig. 1. Simultaneous networks (Source: Adapted [7])

Fig. 4 .

 4 Fig. 4. Networks in Transaction Costs Dimension Through the network graph analysis in the transaction costs dimension, the agents[AG3], [AG11] are part of the physical network and of the value network, simultaneously, and the agents [AG6], [AG9] are simultaneously part of the value network and of the business networkThe agent [AG3] with four significant ties of relationships shows that this agent is of greater impact in the transaction costs. This indication may be due to the purchase and handling of veterinary productsThe agent [AG6] is related to this dimension due to regulatory issues and supervision exerted by the SEAB. The dairy market is a regulated market by the Brazilian Federal laws.The questionnaires applied to the financial institutions that represent the agent [AG9] indicate a significant relationship of transaction costs with the agent [AG11]. Another important result showed that the farmers also point the agent [AG11] as focus of the relationship in this dimension.

Network in Brazil and in the State of Parana The

  milk production network is one of the most important agro-industrial activities, and in the economic and social development process in Brazil it has an important role, given that milk production in Brazil, from 2009 to 2013 obtained a percentage growth of 17.67%, starting in 2009 from 29 billion liters to 34 billion liters in 2013.The milk production in the state of Parana/Brazil has increased year after year; for example, in 2009 the production came from 3,3 billion liters, reaching 4,3 billion liters in 2013, a percentage growth of 30.19%. Compared with the national growth, the state of Parana stood out greatly, as shown in

	Fig. 2. Conceptual research model (Source: adapted [7])
	2.3	The Milk Production
		Physical
		Network
		Value	Business
		Network	Network
			Transparency, credibility
			and trust generate ad-
			vantages in the search for
			new partnerships.

Table 2 .

 2 Table1. Evolution of milk production. (Source: adapted [19])

		Brazil	Parana State
	Year	Quantity	Quantity	%
		(1 000 liters)	(1 000 liters)
	2013	34,255,236	4,347,493	12.69%
	2012	32,304,421	3,968,506	12.28%
	2011	32,091,012	3,819,187	11.90%
	2010	30,715,460	3,595,775	11.71%
	2009	29,112,024	3,339,306	11.47%


Lúcio T Costabile¹
email: luciotadeucostabile@terra.com.br

Oduvaldo Vendrametto¹

Geraldo Cardoso De Oliveira Neto²

Mario Mollo Neto³

Marcelo K Shibuya¹

Social network analysis on grain production in the Brazilian scenario

Keywords: Network Analysis, Centrality, Grains, Geographic Regions. 1

This article provides study of the 2012/2013 grain harvest of federal units of Brazil in relation to the following factors: planted areas, productivity, and production, which assist producers in agricultural planning. The research method used for data collection was the documentary and exploratory data analysis using the software Ucinet® for social networks. The findings indicate that the Midwest has the largest area planted in soybean per thousand / ha, demonstrating the opportunity for producers to develop new crops. In production in thousand / ton, the Midwest region also excelled in soybeans, showing the possibility for producers to seek new techniques for planting. The southern has the highest productivity of the rice grain per kg / ha, contributing to the producer having the best land use and resource optimization.

Introduction

Brazil is one of the largest economies in the world and in this context contributes significantly to agribusiness, standing as one of the largest producers and exporters of grain. With the advance of incentives, the country's agriculture has been increasing in the production and export of grains, mainly soybeans, corn, rice [START_REF] Wto | Trade policy review[END_REF][START_REF] Usda | [END_REF] and wheat [START_REF] Conab | Companhia Nacional de Abastecimento. Situação da Armazenagem no Brasil[END_REF]. The country's federal units have undergone changes in recent years. Factors such as the emergence of new technologies, research development, and new planting techniques have emerged [START_REF] Conab | Companhia Nacional de Abastecimento. Situação da Armazenagem no Brasil[END_REF]. In this context, it is necessary to plan agricultural production, considering the use of machinery and equipment and manpower for operation [START_REF] Osaki | Optimization model of agricultural production system in grain farms under risk, in Sorriso, Brazil[END_REF]. The soybean is one of the agricultural products with highest production and participation in Brazilian agriculture [START_REF] Pontes | Problemas Logísticos na Exportação Brasileira da soja em grão[END_REF]. Rice production provides satisfactory results in the Brazilian agribusiness, due to the cultivation of rice [START_REF] Nitzke | Terra de Arroz[END_REF] and adoption of new techniques and specialized machinery [START_REF] Vieira | A influência das inovações no campo: as cultivares produzidas na Região Sul Catarinense no Brasil[END_REF]. On the production of corn, Brazil ranked third, as a major exporter [START_REF] Ferraz | Production Systems -An example from Brazil[END_REF]. Regarding the wheat crop, production exceeded expectations for planted area, resulting in a reduction in imports [START_REF] Conab | Companhia Nacional de Abastecimento. Situação da Armazenagem no Brasil[END_REF].

A literature search on grain production in Brazil found the need of agricultural production planning to minimize risk and achieve better financial return [START_REF] Osaki | Optimization model of agricultural production system in grain farms under risk, in Sorriso, Brazil[END_REF]. In this context, it is necessary to invest in new technologies to provide the development of new techniques in the Brazilian agricultural sector. These new technologies include, for example, the study of geographic variables (soil, atmosphere, and temperature) of each region to improve handling and increase productivity [START_REF] Pontes | Problemas Logísticos na Exportação Brasileira da soja em grão[END_REF], intensification of technologies for a grain storage process to reduce loss [START_REF] Tefera | The metal silo: An effective grain storage technology for reducing postharvest insect and pathogen losses in maize while improving smallholder farmers' food security in developing countries[END_REF], introduction of incremental changes in rice planting to contribute to increased productivity [START_REF] Nitzke | Terra de Arroz[END_REF], and the analysis of the influence of rice as the ability to influence [START_REF] Vieira | A influência das inovações no campo: as cultivares produzidas na Região Sul Catarinense no Brasil[END_REF] the economy of a region. There was a lack of research related to social network analysis at a national level to measure the relationship between the network actors (regions and types of grains) to assist the producer in the planning of agricultural production. The analysis included data extracted from the following variables: areas planted per hectare, yield, and production [START_REF] Conab | Companhia Nacional de Abastecimento[END_REF]. In this context, for effectiveness in grain production, new forms of agricultural planning can be performed based on the centrality of the network, i.e., other technological applications in terms of resources and enhancement techniques can be employed in regions with the highest centrality. The degree of centrality measures the number of links between actors in the network, allowing inclusion of the strategic position of each actor [START_REF] Scott | Social network analysis[END_REF]. From this emerged the following research question, which grain has the greatest impact on Brazilian Agriculture in relation to the planted area, yield per hectare, and production per ton? To answer this question, we chose to analyze Social Networks. These structures can be defined by the reciprocal relationship between independent, but economically interdependent, agents, aimed at cooperation to achieve common or complementary goals [START_REF] Powwel | Neither market not hierarchy: network forms of organization[END_REF][START_REF] Williams | Cooperation by design: structure and cooperation in inter organizational networks[END_REF][START_REF] Borgatti | A Social Network View of Organizational Learning[END_REF]. The structure of the network and the position of the actors can affect the functions of the organization and their skills in generating value [START_REF] Lazzarini | Empresas em rede[END_REF]. Connectivity, which is the ability to link each individual network, can be represented by the intensity and frequency of communication between the actors [START_REF] Borgatti | On social network analysis in a supply chain context[END_REF]. The most common representations of networks are those in which the nodes represent actors and ties, allowing transfer of information [START_REF] Krackhardt | Informal networks: the company behind the chart[END_REF]. We can classify the links / bonds by their intensity, denoting absent, weak, and strong ties [START_REF] Granovetter | Getting a Job: a study of contacts and careers[END_REF].

Thinking of the research question, this study aims to assess which of the grains and regions of the 2012/2013 harvest had greater impact on the Brazilian agribusiness in relation to the acreage productivity per hectare and production per ton. This can help producers with agricultural planning and will present the factors that influence the culture of grains. Our assessment was done using Ucinet®. By applying network analysis with relational matrices, and the visual analysis of graphs of these same networks, it allowed the finding of new indicators, other than those offered by traditional statistical analysis with specific focus on the degree of centrality.

Methodology

This article presents an exploratory research study through a literature review using the keywords: grain production and agribusiness, in databases: Science Direct, Proquest, Ebsco, Capes, and Scielo. Data collection was conducted through research in a regulatory government agency of the Brazilian agricultural sector called the National Supply Company (Companhia Nacional de Abastecimento -Conab). Using these sources, we mapped the crops of grains under study for a period related to the cultivated area, including yield per hectare and production in thousand tons, for the harvest of 2012/2013 in the federal units of Brazil, as shown in Table 1.

Table 1. Mapping of cropplanted area, production and productivity Source: CONAB, (2012/2013) For the creation of the crop mapping, we used matrix and graphical analysis of the data provided to look at the relationship between the individuals in the network. For this, we used social network analysis software (Ucinet®), developed in the laboratories Analytic Technologies at the University of Greenwich. This methodology allows the mapping of networks of federal units with the respective values of area, yield, and production per hectare.

The values obtained from literature surveys are included in generated files in the Windows operating system notepad, thus building the files of type ".vna" (visual network analysis) required for implementation and enforcement in Ucinet® software. The processes result in the values of the degree of centrality of interaction of the actors within the network [START_REF] Borgatti | Ucinet for Windows: software for social network analysis[END_REF].

The general degree of centrality is composed of the input degree of centrality and by the output degree of centrality, and these depend on the relative direction of flow. The sum of relations that an actor has with other actors is the output degree centrality, and the sum of relations that the other actors have with a particular actor is the input degree of centrality [START_REF] Velazquez | Manual Introdutório à Análise de Redes Sociais -Medidas de Centralidade: Exemplos práticos com UCINET 6[END_REF]. An actor is locally central, if it has a large number of connections to other points. It is globally central, if it has a significant strategic position in the network as a whole [START_REF] Scott | Social network analysis[END_REF]. The centrality of degree is measured by the number of ties that an actor has with other actors in a network [START_REF] Wasserman | Social network analysis: methods and applications[END_REF].

Generally, for software available for network analysis, as used in this research with the Ucinet® and Netdraw® module, the data is provided by relational matrices (socio-matrices in the language of sociologists), which can be viewed through graphs. The graphic display alone can offer new information and insights for researchers [START_REF] Iacobucci | Graphs and matrices[END_REF][START_REF] Wasserman | Social network analysis: methods and applications[END_REF]. This function was used via the Netdraw® module accompanying Ucinet® to enable the visualization of networks based on the ".vna" files generated.

The corresponding graphs of Planted area networks, Productivity, and Production, are generated with Netdraw®, and the images obtained are marked by relationships of higher intensities and their respective directions. Likewise the actors are indicated (highlighted with discs in red) with its expanded size (larger diameter) Social network analysis on grain production in the Brazilian scenario 4 based on their relative centrality, in order to visually indicate the actors with greater power or influence, and participation in the network by means of larger diameter.

The design of centralities in accordance with the indications [START_REF] Emirbayer | Network analysis, culture and the problem of agency[END_REF], obeyed the software, application of the following equation 1:

𝐶 𝐺 (𝑣 𝑘 ) = ∑ 𝑤 𝑘𝑗 𝑛 𝑗=1
Eq. 1 Where: 𝐶 𝐺 = Degree of centrality; 𝑣 𝑘 = Node of the net to be considered; 𝑗 = Number of nodes;

𝑤 𝑘𝑗 = Number of adjacent nodes; and, 𝑤 𝑘𝑗 = 1 if there is a link between the nodes vk e vj.

After visualizing the data for analysis and the corresponding graphical behavior in the networks under study, it is possible to obtain the patterns of the actor's behavior and to transcribe this data to relational matrices (also known as sociometric matrices), which are necessary for the data analysis by the chosen analysis program, Ucinet®.

Results and Discussion

After data entry, the actors were processed using UCINET® software. The data represents areas planted in million hectares, productivity in kilograms per hectare, and production in thousands of tons of soybeans, corn, rice and wheat, in the Brazilian states of the Midwest, South, Northeast, Southeast, and North, and their relationships, represented by the values of participation of each grain which resulted in the interaction of the actors within the network.

Planted area

The graph of the corresponding network acreage was developed in Netdraw® (Figure 1) and it shows the centrality of the network and the positional indicators and intermediary actors. The results indicate that the Midwest and South regions have the highest densities (or most significant trade links) between the actors in the network, i.e., greater participation among the federal units in areas planted on millions of acres, confirming what was collected in the literature review, with 12,738 million/ha of soybeans planted in these areas, 5,133 million / ha of maize, 201,000/ha of rice, and 24,000/ha of wheat. Soy has the highest centrality in the relationship, due to new technologies, research development, and economic changes in the [START_REF] Osaki | Optimization model of agricultural production system in grain farms under risk, in Sorriso, Brazil[END_REF] region. On the international scene, Brazil appears as the largest soybean supplier to China and the United States.

The results obtained by Ucinet® found that the OutDegree is the level of output, representing the share of each federal unit. The Midwest revealed 18,096 million hectares of planted areas; followed by the southern region, with 17,097; the Northeast, 5,383; Southeast: 4,011; and North, 1,713. The InDegree represents the degree of entry, or the quantities of areas planted with beans with their respective values in million hectares, considering all regions, resulting in soybeans for 27,239; corn, 14,759; rice, 2,408; and wheat, 1,894. The actor "soy" has the highest degree of entry, with the Midwest region 12,738,000 / ha, Southeast 1,735 million / ha, South 9,604,000 / ha, Northeast 2,329 million / ha, and North 833,000 / ha, totaling 27,239 million hectares. The highlight is the Midwest region, which has the highest level of output, i.e., is the main actor who has the highest participation of areas planted in million hectares in the country. This share is characterized due to research for adaptation of new crops for fertile soils, such as cotton, soybean, wheat, corn, etc. [START_REF] Pontes | Problemas Logísticos na Exportação Brasileira da soja em grão[END_REF]. It is noteworthy that the increase of planted areas is due to the new planting techniques, improved communications, and the significant consumer market in the Southeast region, which has contributed to the increase in commercial agriculture development [START_REF] Pontes | Problemas Logísticos na Exportação Brasileira da soja em grão[END_REF]. We found that the average degree of centrality of the relationship between the actors of the network was measured at 14,298% for output values, and 24,392% for the input values, which indicates that power is distributed over the network heterogeneously both for input relationships and output relationships.

The values obtained also show that the Midwest has the largest area of planted areas in million hectares, and the prospect is that the Midwest will continue to invest in increasing planted areas, mainly in soybean cultivation, which showed growth during the last three decades.

Production

The results obtained by Ucinet® (Figure 2) in OutDegree, found that the Midwest was the most substantial at 68,077,000 / t, followed by the southern region, with 66,774,000 / t, Northeast: 13,333,000 / t; Southeast: 17,651,000 / t, and North: 5.126 million / t. The results show that the Midwest and South, have the highest levels of output and are the main actors who have higher productions thousand / t and have more developed techniques for planting, which can be studied by the regions with the lowest rate of production. These techniques were presented [START_REF] Vieira | A influência das inovações no campo: as cultivares produzidas na Região Sul Catarinense no Brasil[END_REF] regarding the different soil types, climate, availability of water for agriculture, land use, and technological resources that contribute to increase production. The research [START_REF] Osaki | Optimization model of agricultural production system in grain farms under risk, in Sorriso, Brazil[END_REF] also mentions that the South has great genetic potential of new forms of cultivation, producing satisfactory levels of commercialization, directly impacting the profitability of agribusiness. The actors' (representing the grain) InDegree accounted for soybeans: 82,626, corn: 71,934, rice: 11,926, and wheat: 4,475. Soy has the highest degree of entry, most notably in the Midwest: 39,389,000/t; South: 28,705,000/t; Northeast: 6,915 million/t; Southeast: 5,080.000/t; and North: 2,537,000/t, for a total production of 82,626 million/t. General indicators of the network and their descriptive statistics related to the production per thousand / t denoted the state of network centrality output was measured as 17,523%, and the degree of input centrality was 22,717%.

These figures show that power is distributed over the network heterogeneously both for input relationships and output relationships. However, with regard to the levels of output, it is observed that there is a higher concentration to the power of the regions center -west and south, which are, as highlighted earlier, the largest producers. But, one should also highlight, the areas are very disparate from each other as well as the productivity of the regions focused on in the study.

Productivity

In Figure 3, using calculations applying the processing with the software, the results indicate via the analysis of OutDegree, that the southern region has the highest level of output (18,259 kg/ha), followed by the Southeast (14,599 kg/ha), Midwest (14,558 kg/ha), North (8954 kg/ha) and Northeast (6617 kg/ha). It is noteworthy that in the South, the rice grain represents the largest production (7,369,000/t), followed by maize (5565 kg/ha), soybean (2989 kg/ha) and wheat (2336 kg/ha). In relation to InDegree analysis, we found that corn grain is the most representative (21,737 kg/ha), followed by rice (18,378 kg/ha), soybean (14,750 kg/ha) and wheat (8122 kg/ha). This finding is corroborated by [START_REF] Osaki | Optimization model of agricultural production system in grain farms under risk, in Sorriso, Brazil[END_REF] due to favorable conditions for growing. The southern region has attracted several companies in the agribusiness sector for research, use of new technologies, and new inputs correcting soil deficiencies for planting.

The degree of overall centrality of network output was measured in 21,489% and the degree of input centrality was 28,126%. The figures show that the network has low power relations between the actors in the case of the degrees of output, which indicates that there is no balanced participation of regions for the production as a whole. This can be seen in the lower contribution of North and Northeast. However, the product that stood out in this case was the highest input degree of centrality, the corn, and its production was strongly influenced by good production in all federal units participating in the study. The largest production in thousands of ton was presented in the South concerning the growth of planted areas, alternative crops, adoption of new management systems appropriate to the soil, use of technology, tax breaks, and donations of new land for planting. This stands out because the participating regions provide areas with large differences in their size and production per ton varies greatly between states.

Conclusions

With the use of the social network analysis technique, we found that the Midwest region showed the highest share of areas planted in million hectares in the country, followed by the South region, with the soybean receiving the largest investment, and presenting the largest participation in the growth of cultivated areas. This analysis can help producers based on cultivating the soil with the help of research and new techniques of planting, as well as new forms of financing. For example, the producers of the region with the lowest degree of centrality (North) could develop new crops in the region.

The Midwest region was found to have the highest production in thousand / t, followed by the South, with the largest share of soybeans, corn, and rice, because of the resources used in cultivation. In pursuit of increased production, this result will allow direct producers to better understand the planting techniques. For example, regions with lower production volume can intensify these factors to increase their crops.

The southern region aims to be the leading region with higher grain yield kg / ha, with the emphasis on the grains of rice and corn, taking advantage of climate conditions, and human and technological resources of the region. The results indicate to producers the need for better use of soil, seed selection, and the best use of natural resources in the region, because with this, other regions could contribute to the grain productivity at a national level. For example, the Midwest, the leader in planted areas WHEAT and production, is not the most important in productivity per hectare, indicating that the increase in productivity is related to better land use and resource optimization, leading to better crop yield. A limitation of this research is the use of a documentary exploratory research approach. For future research regions with less centrality could be explored to propose new incentives and agricultural practices to increase productivity.

Figure 1 .

 1 Figure 1. Representation of the corresponding network acreage, crops, and regions represented by Ucinet® software and its Netdraw® module.

  on grain production in the Brazilian scenario 6

Figure 2 .

 2 Figure 2. Representation of the corresponding network production, cultures and regions represented by Ucinet® software.

Figure 3 .

 3 Figure 3. Representation of the corresponding network productivity, cultures and regions represented by Ucinet® software.


Issue on Software Verification and Testing (Selected Papers from

Preface: Special Issue on Software Verification and Testing (Selected Papers from SAC-SVT'15)

Software drives today's world. Daily needs like electricity supply, transportation, groceries, are all empowered by software, and not to mention communication and emails. This dependency will only increase, given innovations like the Internet-of-things, 3D printing, self-driving cars and drones. Therefore, software correctness is more important than ever: nobody wants drones to drop on our heads, autonomous cars to crash, or intrudes to enter our house via Internet-ofthings devices. Hence, rigorous verification and testing is of paramount importance, as a technique to assess and improve the quality of software systems. This is exactly the topic of the Software Verification and Testing (SVT) track of the ACM Symposium on Applied Computing. This special issue of the Journal on Science of Computer Programming arose from the SVT track at the 30 th ACM Symposium on Applied Computing, held in Salamanca, Spain on April 13-17, 2015. The track received 60 full paper submissions. After a careful reviewing process, the international Program Committee decided to select 14 papers for presentation during the symposium and inclusion in the SAC'15 proceedings. From these 14 papers, the six best papers were selected and invited for an extended version to this special issue. These extended papers went again through a rigorous peer review process; five papers were finally accepted and are included in this special issue. The papers included here provide key insights on different formal verification and testing approaches.

This special issue includes three papers on testing. The paper Model-Based Testing for Building Reliable Realtime Interactive Music Systems by Poncelet and Jacquemard concerns an unusual, and innovative case study in model based testing, namely an interactive music system. Such a system allows musical performers and composers to create an interactive piece of music where the system reacts in realtime to audio signals from musicians. The paper describes how such complex realtime behaviour can be tested automatically by using timed automata and the testing tool UPPAAL TRON.

The paper CenUMS -Concurrency Enhanced Usage Models for Statistical Testing of Complex Systems with Concurrent Streams of Use by Homm, Eckert, and German represents a natural extension of Markov Chain Usage Models by composite states with regions, which are used to formalize concurrent streams of use. This allows a simplified and reasonable specification as it hides the state space explosion. This paper provides configurable algorithms for test case generation that take composite states into account. A new analysis method also leads to a significant improvement of the calculation time for parameters.

The last paper on testing is Tri-Modal Under-Approximation for Test Generation by Bride, Julliand, and Masson. This paper presents a method for underapproximating behavioural models with the guarantee that the abstract paths can be instantiated as executions of models. This allows a model-based testing approach to operate on an abstraction of infinite or very large behavioural model, by characterizing the abstract transitions as either may, must+ or must-.

Initial experimental results show that, despite the complexity of symbolic exploration, the method is able to reach significant configurations within a small number of exploration steps.

Two papers in the area of verification were accepted. The paper Symmetry Reduction for Time Petri Net State Classes by Bourdil, Berthomieu, Dal Zilio, and Vernadat proposes a method to exploit the symmetries of a realtime system represented by Time Petri nets. The method handles both markings and timing constraints and it can be used in conjunction with the widely used state classes abstraction, with initial experiments showing its effectiveness.

The other paper is Fast as a Shadow, Expressive as a Tree: Optimized Memory Monitoring for C by Jakobsson, Kosmatov, and Signoles. This paper addresses memory monitoring in the context of runtime assertion checking of C programs, annotated in E-ACSL, an expressive specification language offered by the FRAMA-C framework for analysis of C code. The paper proposes an effective combination of tree-based and shadow-memory-based techniques that reconciles the efficiency of shadow memory with the high expressiveness of runtime annotations. Experiments confirm that this hybrid approach leads to a significant speedup.

Many people have contributed to this special issue. Besides the authors of the papers, we would like to thank both the members of the Program Committee of the symposium and the additional reviewers who kindly agreed to help us with the reviewing of the papers in this special issue. All carried out an excellent job during this demanding process: Stefan Blom (University of Twente, The Netherlands), Laura Brandán Briones (National University of Cordoba, Argentina), Maximiliano Cristiá (Universidad Nacional de Rosario, Argentina), Marco Faella (University of Naples, Italy), Ylies Falcone (University of Grenoble Alpes, France), Tingting Han (University of London, UK), Fabrice Kordon (University Pierre et Marie Curie, France), Stefan Leue (University of Konstanz, Germany), Malte Lochau (Darmstadt University, Germany), Annabelle McIver (Macquarie University, Australia), Stephan Mennicke (TU Braunschweig, Germany), Mercedes Merayo (Universidad Complutense de Madrid, Spain), Dominique Mery (University of Lorraine, France), Mohammad Mousavi (Halmstad University, Sweden), Brian Nielsen (Aalborg University, Denmark), Jun Pang (University of Luxembourg, Luxembourg), Corina Pasareanu (NASA Ames, USA), Wishnu Prasetya (Utrecht University, The Netherlands), Marjan Sirjani (Reykjavik University, Iceland), Hasan Sözer ( Özyegin University, Turkey), Tanja Vos (Valencia University, Spain), Anton Wijs (Eindhoven University of Technology, The Netherlands), Karsten Wolf (Universität Rostock, Germany), Liu Yang (Nanyang Technological University, Singapore), Gianluigi Zavattaro (University of Bologna, Italy), Lijun Zhang (Chinese Academy of Sciences, China).

We hope that these articles will bring the reader novel insights and ideas.

Gwen Salaün Université Grenoble Alpes, France


I Alfaro

L Fratini
email: fratini@dtpm.unipa.it

E Cueto
email: ecueto@unizar.es

F Chinesta

Numerical Simulation of Friction Stir Welding by Natural Element Methods

Keywords: Friction Stir welding, meshless methods, NEM

In this work we address the problem of numerically simulating the Friction Stir Welding process. Due to the special characteristics of this welding method (i.e., high speed of the rotating pin, very large deformations, etc.) finite element methods encounter several difficulties. Meshless methods somewhat alleviate this problems, allowing for an updated Lagrangian framework in the simulation. Accuracy is not affected by mesh distortion (and hence the name meshless), but the price to pay is the computational cost, higher than in the FEM. In this paper we will show some examples on the performance of the method.

INTRODUCTION

Friction stir welding (FSW) is a solid state welding process used to join two pieces of sheet or plate material as aluminium, copper, lead and even some plastics. It achieves the welding of the pieces by employing a rotating pin and shoulder that provoke both extremely high plastic deformation and also a high heat generation. It is schematically represented in figure 1. At first, the sheets or plates are abutted along edge to be welded and the rotating pin is sunken into the sheets/plates until the tool shoulder is in full contact with the sheets or plates surface. Once the pin is completely inserted, it is moved with a small nutting angle in the welding direction. Due to the advancing and rotating effect of the pin and shoulder of the tool along the seam, an advancing side and a retreating side are formed and the softened and heated material flows around the pin to its backside where the material is consolidated to create a high-quality, solid-state weld.

In this paper we focus on the numerical simulation of the process, rather than the experimental characterization. From the numerical point of view, such a process presents several challenging difficulties. First of all, the extremely large deformations present dur-ing the process, although very localized in a region around the pin, always introduce numerical problems. Second, there is a strong coupling between these large deformations and heat generation, that in turn affects the behavior of the material. Last, it is important to notice the difficulty of simulating the FSW of two plates of different material. Up to our knowledge, few numerical attempts have been made in order to simulate this process. In [START_REF] Chenot | Finite element modelling and control of new metal forming processes[END_REF] a FE based Lagrangian approach with intensive remeshing is employed. Similar approaches have been employed in [START_REF] Buffa | A continuum based fem model for friction stir welding-model development[END_REF]. Remeshing, however, is wellknown as a potential source of numerical diffusion in the results. In this paper we employ a somewhat different approach based on the use of meshless meth-ods. Meshless methods allow for a Lagrangian description of the motion, while avoiding the need for remeshing. Thus, the nodes, that in our implementation transport all the variables linked to material's history, remain the same throughout the simulation. Mappings between old and new meshes are not necessary and hence the avoidance of numerical diffusion.

Among the many meshless methods available nowadays, we have chosen the Natural Element Method [6] [4]. It possesses some noteworthy advantages over other meshless methods that will be described shortly.

THE NATURAL ELEMENT METHOD Consider a model composed by a cloud of points

, for which there is a unique decomposition of the space into regions such that each point within these regions is closer to the node to which the region is associated than to any other in the cloud. This kind of space decomposition is called a Voronoi diagram of the cloud of points and each Voronoi cell is formally defined as (see figure 2):

(1) where is the Euclidean distance function. The dual structure of the Voronoi diagram is the Delaunay triangulation, obtained by connecting nodes that share a common -dimensional facet. While the Voronoi structure is unique, the Delaunay triangulation is not, there being some so-called degenerate cases in which there are two or more possible Delaunay triangulations (consider, for example, the case of triangulating a square in 2D, as depicted in figure 2 (right)). Two nodes sharing a facet of their Voronoi cell are called natural neighbours and hence the name of the technique.

The most extended natural neighbour interpolation method is the Sibson interpolant [START_REF] Sibson | A Vector Identity for the Dirichlet Tesselation[END_REF]. Consider the introduction of the point in the cloud of nodes. Due to this introduction, the Voronoi diagram will be altered, affecting the Voronoi cells of the natural neighbours of . Sibson [START_REF] Sibson | A Vector Identity for the Dirichlet Tesselation[END_REF] defined the natural neighbour coordinates of a point with respect to one of its neighbours as the ratio of the cell that is transferred to when adding to the initial cloud of points to the total volume of . In figure 3 the shape function associated to node 1 at point may be expressed as

(2)
Sibson's interpolation scheme possesses the usual reproducing properties for this class of problems, i.e., verify the partition of unity property (constant consistency), linear consistency (and therefore are suitable for the solution of second-order PDE). This kind of interpolation scheme is then used in a Galerkin framework, exactly like in the finite element method.

GOVERNING EQUATIONS

FSW processes involve large deformation and high velocities of the rotating pin that make the elastic strains to be negligible. Although an elastic recovery exists, it is obvious negligible as a first approximation. The obvious advantage of this assumption is that the material can then be modeled as a non-newtonian (visco-plastic) fluid. This assumption is known as the flow formulation in the forming processes community [START_REF] Zienkiewicz | Flow of plastic and visco-plastic solids with special reference to extrusion and forming processes[END_REF]. Thus, the essential variables of the problem will be velocities and pressures, instead of displacements and pressures. The stresses will be, under this assumption, [START_REF] Chenot | Finite element modelling and control of new metal forming processes[END_REF] where and stands for the secondorder identity tensor. The viscosity can depend on the strain, the strain rate, the temperature and other variables.

We consider, for the plates being welded, the balance of momentum equations without inertia and mass terms and the assumed incompressibility of a von Mises-like flow: [START_REF] Cueto | Overview and recent developments in Natural Neighbour Galerkin methods[END_REF] where represents the velocity field. Velocities are interpolated by means of the Sibson shape functions, while pressures are considered constant over the whole Voronoi cell associated to each node.

This rigid-plastic material is coupled with the following heat transfer equation: [START_REF] Sibson | A Vector Identity for the Dirichlet Tesselation[END_REF] where denotes the thermal conductivity, the heat generation rate, the specific density and the specific heat of the metal. The rate of heat generation in the aluminium billet due to plastic deformation is given by where represents the fraction of mechanical energy transformed to heat and is assumed to be 0.9.

The coupling has been made through a blockiterative semi-implicit method, together with a fixedpoint algorithm to treat the non-linear coupling. This strategy has also been employed successfully in previous works of the authors [START_REF] Alfaro | Three-dimensional simulation of aluminium extrusion by the -shape based natural element method[END_REF].

NUMERICAL RESULTS

We consider here a very simplified two-dimensional plane stress model of the union of two plates with a rigid pin. Despite that the usual friction coefficient between the pin and the sheet has been established to be around 0.5 we have considered here perfect adhesion between them. This will overestimate the strain produced by the pin rotation. The material chosen for both plates of this first example corresponds to aluminium AA7075, with a viscosity, taken from [START_REF] Buffa | A continuum based fem model for friction stir welding-model development[END_REF]: [START_REF] Sukumar | The Natural Element Method in Solid Mechanics[END_REF] whith , , , and the following thermal properties: and

. The pin has a diameter of 3mm, rotates at and advances at . In figure 4 the evolution of the temperature is shown, checking the good agrement with the FEM results shown in [START_REF] Buffa | A continuum based fem model for friction stir welding-model development[END_REF]. It is also checked that the properties of the material, such as the viscosity, change due to the temperature evolution (see figure 5). The most important advantage of the presented technique is the possibility of tracking the materials particles throughout the process. Now we have considered two plates of different materials, with viscosity defined by . They have equal consistency parameter and different sensitivity index:

and . Now only rotating movement is studied, thus the advancing speed is zero.

In figures 6 to 8, several steps of the simulation are shown. Nodes of each plate have been labeled, by painting them in blue and red. This tracking can be performed without remeshing despite the high level of distortion of the resulting triangulation because triangles do not constitute the support of NEM shape functions. In this way, the numerical diffusion provoked by continuous remeshing is avoided. In addition, if some kind of nodal integration is performed, all history variables can be linked to the nodes, thus avoiding any projection procedures.

CONCLUSIONS

Although the presented results can be considered as very preliminary, and further refinement of the models (especially relative to contact and friction) is needed, we can conclude that the NEM constitutes a valuable tool for the simulation of such a complex forming process. In particular, it has been shown how a large number of time steps have been accomplished maintaining the initial set of nodes. Despite the high distortion of the triangulation, good qualitative agreement with previous results has been found. Note, however, that the true interest of the proposed technique relies in its extension to three-dimensional settings, where the true complexity of the process should be analyzed. This constitutes the ongoing work of the authors.

Figure 1 :

 1 Figure 1: Schematic representation of the FSW process.

Figure 2 :

 2 Figure 2: Delaunay triangulation and Voronoi diagram of a cloud of points.

Figure 3 :

 3 Figure 3: Definition of the Natural Neighbour coordinates of a point .

Figure 4 :Figure 5 :

 45 Figure 4: Temperature. Left: 100th time step.Right: 400th time step

Figure 6 :Figure 7 :Figure 8 :

 678 Figure 6: Material distribution at 50th time step.


Pierre Huchant
email: pierre.huchant@inria.fr

Marie-Christine Counilh
email: counilh@labri.fr

Denis Barthou
email: denis.barthou@inria.fr

Automatic OpenCL Task Adaptation for Heterogeneous Architectures

OpenCL defines a common parallel programming language for all devices, although writing tasks adapted to the devices, managing communication and load-balancing issues are left to the programmer. In this work, we propose a novel automatic compiler and runtime technique to execute single OpenCL kernels on heterogeneous multi-device architectures. The technique proposed is completely transparent to the user, does not require off-line training or a performance model. It handles communications and load-balancing issues, resulting from hardware heterogeneity, load imbalance within the kernel itself and load variations between repeated executions of the kernel, in an iterative computation. We present our results on benchmarks and on an N-body application over two platforms, a 12-core CPU with two different GPUs and a 16core CPU with three homogeneous GPUs.

Introduction

Heterogeneous parallel architectures are ubiquitous, from supercomputers to cell phones. Developing an application for a heterogeneous, multi-devices system, taking advantage of all available devices is extremely challenging. OpenCL is a standard language for the development of code on heterogeneous architectures. It leverages part of this difficulty by defining one language for all platforms, and by structuring parallelism into a task graph, where tasks are parallel computations to be mapped onto one device. However, this implies that the developer has to design as many tasks as there are devices, with tasks adapted in terms of parallelism and memory granularity: There should be enough parallelism for all devices, and communications between devices have to be explicit.

OpenCL kernels describe tasks as parallel work-groups. To transform one kernel into as many kernels as devices, these work-groups have to be partitioned among devices. This raises load balancing issues, stemming from device heterogeneity and from workload variation between work-groups. As many kernels are executed in iterative computation, the workload may change from one iteration to the other, requiring a constant adaptation of the work-group partitioning. Moreover, data has to be split among partitioned work-groups in order to reduce communication time and written data has to be merged upon kernel completion. Achieving adaptive work-group partitioning, with no training, handling load balancing and data movements has never been conducted before.

We propose in this paper a static/dynamic approach for the execution of any given OpenCL kernel on a multi-device heterogeneous architecture. The method tackles, without training, load balancing issues coming from device heterogeneity and from varying computational intensity inside the kernel, when the kernel is called multiple times. The load-time analysis computes how to partition data for the execution of work-groups as a function of the work-group partitioning. The dynamic method evaluates from previous runs how to partition work-groups and splits/merges data accordingly. We show with two different runtime methods that only a few iterations are required to reach the optimal granularity. Finally, when the kernel computational intensity changes with each execution, the method dynamically adapts the load and stays close to the optimal load.

Section 2 shows causes for load balancing issues when splitting a kernel into subkernels. Section 4 presents our method, generating partition-ready kernels and instantiating with the appropriate granularity, for each device. Computation of granularities is described in Section 5. Related works and experimental results are given in Sections 6 and 7.

Motivating Example

Given an OpenCL kernel, we define a subkernel as a code executing only part of the kernel computation. As OpenCL kernel executions are characterized by the number of parallel work-groups, the ratio of work-groups of a subkernel over the total number of work-groups is called granularity, a granularity of 1 meaning the whole kernel is executed. We study the performance variation of a kernel on one device, decreasing manually its granularity. The granularity is indicated as a percentage of the total number of work-groups, and performance is indicated as the mean time per work-group (lower is better). Figure 1 shows performance of AESEncrypt and EP from SNU NPB Suite [START_REF] Seo | Performance Characterization of the NAS Parallel Benchmarks in OpenCL[END_REF] for different granularities on a 16-core Intel Xeon E5-2650 2.00GHz with 64GB (CPU) and on an Nvidia Tesla M2075 (GPU). For AESEncrypt, the average time per work-group is nearly constant for all granularities, and very different on CPU and on GPU. For EP, we observe large performance drops (higher average time/work-group) at regular intervals of granularities on both CPU and GPU. This may come from compiler optimizations (such as unrolling), cache effects, and inefficient occupancy of the parallel resources due to a low number of work-groups within subkernels.

Work-groups are indexed in OpenCL by a vector of indices among a rectangular space (from 1D to 3D) called the NDRange. Selecting a granularity boils down to defining a subvolume of indices. In this paper, the subvolumes we consider are obtained by selecting one smaller interval in one dimension of the NDRange. The offset is the first index of this interval of indices, the granularity defining the size of this interval. Figure 1c shows for a Sparse Matrix Vector Multiply (SpMV) the influence of the offset on performance when, for a kernel of 1/4 granularity, the offset is changed. In the chosen sparse matrix, rows with a high index have more non-0 elements than those with a low index. This accounts for the execu- tion time increase for large offsets, more than 7× the time of a 0-offset. When splitting a kernel into subkernels, this is a possible source of load-imbalance.

Many OpenCL kernels are executed in iterative computations. For instance, OTOO [START_REF] Nakasato | Astrophysical Particle Simulations on Heterogeneous CPU-GPU Systems[END_REF] is an astrophysics particle N-Body simulation and the same kernel is called repeatedly to compute forces and move the different particles. Figure 1d shows how the execution time changes for different iterations, for different offsets, for each iteration of the computation. The kernel is split into 4 subkernels, each one is given a granularity of 1/4 and executed on one GPU. The input set corresponds to a non-uniform distribution of the masses in space. As this space is partitioned among the work-groups, this results in a non-homogeneous load distribution among the work-groups, changing with iteration number.

These results advocate for a method able to cope with the heterogeneity of the hardware, but also with the performance variations associated to different granularities, depending on the offset and varying with each execution of the kernel. Adapting a single OpenCL kernel to an heterogeneous architecture with any number of devices, taking into account these four sources of imbalance has never been tackled before.

The method proposed is threefold. First the kernel is analyzed and a new version, partition-ready, is generated at compile time. Then each time the original kernel has to be executed, a granularity is chosen for each device, based on previous executions if any, and the partition-ready kernel is instantiated on each device with the chosen granularity. More precisely: (i) When the kernel code is first loaded, it is analyzed. This step is more thoroughly described in Section 4. The objective is the generation of a parametric and partition-ready kernel, executing only a slice of the NDRange space. The analysis is performed once on the OpenCL code (no host code analysis) but the code generated can be instantiated at runtime for many different granularities and offsets. The slicing of the rectangular volume corresponding to the NDRange is done in any of the dimensions of the volume and does not require to flatten it. The memory region accessed by each work group is computed, parametrically w.r.t. the work-group id and the scalar parameters of the kernel; (ii) Each time the original kernel is launched, a granularity for each device is determined. This granularity determines the number of work-groups to execute on a particular device. The array regions are instantiated with the granularities and the actual parameters of the kernel. Depending on the result, all arrays are communicated to the devices or only the region they require. The same occurs for bringing back data from the devices. This kernel instantiation is described in Section 4.2; (iii) The execution time of each kernel execution is collected for refining the granularity in the possible following runs. This iterative granularity optimization is described in Section 5.

Automatic Adaptation of Data and Parallelism

We describe in this section how a kernel is analyzed and transformed into a parametric partition-ready kernel, function of the granularity.

Static Analysis and Transformation

The analysis determines for each array passed to the kernel how this array can be split among the different devices. For arrays that are read-only, a safe overapproximation is to broadcast the whole array to all devices. A more precise analysis can determine a finer partition, allowing shorter communication times and for some extreme case, may be the only possible way to execute the kernel if the initial array is too large for any of the devices. Finding how to partition arrays written by the kernel is essential: When the written region is precisely known and there is no overlap with other device regions, bringing back this data to the host can be done in parallel. On the contrary, if the analysis is not able to precisely determine which region has been written, a merge operation is necessary to build the output array [START_REF] Pandit | Fluidic Kernels: Cooperative Execution of OpenCL Programs on Multiple Heterogeneous Devices[END_REF][START_REF] Lee | SKMD: Single Kernel on Multiple Devices for Transparent CPU-GPU Collaboration[END_REF]. The analysis only handles arrays (buffer objects) but could be extended to OpenCL images. We describe in this section how to determine precisely the array regions accessed by each work-item. The case where the analysis fails is discussed in the next section.

We first identify in the kernel all statements accessing arrays passed as a parameter. In OpenCL, arrays can be cast into other types (from 1D to 3D for instance), with possible offsets. All accesses through the cast arrays are also accesses to the initial array. Likewise, array accesses may occur inside functions called by the kernel. We therefore resort to an inter-procedural alias analysis, following assignments and use-def chains on arrays. In the following example, For each array that is a parameter of the kernel and for each statement, we compute the array region accessed by this statement. The idea is to consider the index expression and to replace the variables in it by their values, repeatedly. Assuming the code is in SSA-form, this repeated substitution may lead to several cases: The resulting expression only uses scalar parameters of the kernel and work-item ids (local, group or global). In such case, the substitution process stops and the exact region will be evaluated dynamically, when these ids and parameter values are known. When a variable is defined by a Φ-function, if this is an induction variable and its interval of values can be determined, then the variable is replaced by its interval, the index expression becoming an interval expression. For other cases of Φ-functions or variables that are defined by loads, the region accessed is assumed to be unknown. Therefore, the array regions computed are interval expressions of the scalar inputs of the kernel and of the work-item ids, or unknown. We compute additionally the conditions on the ids for which this region is accessed. The abstraction we use for these conditions is an interval on ids. A similar analysis is therefore conducted on the conditionals (or loop bounds) governing the execution of the statement considered. Out of simplicity, only uniform expressions on ids are kept, i.e. inequalities of the form: ±id ≤ expr where expr is an expression independent of the work-item ids. Conditionals that are not uniform expressions are assumed to be true. The conjunction of such conditionals define intervals of ids. To wrap-up, the array region accessed by a statement is either unknown, or represented by a guarded region of the form:

if id ∈ [lb(s), ub(s)] : [expr1(id, s), expr2(id, s)]
with s the scalar parameters of the kernel and id a work-item id. Note that the expressions expr 1 , expr 2 , lb and ub have no restriction and can use any operator allowed by the language. For a given array, the region accessed by the kernel is defined by the union of array regions accessed by all statements.

Kernel modification When executing a kernel with a fraction of the original NDRange, some syntactic modifications are needed in order to keep the correct All analyses and transformations are performed once at compile-time within the LLVM compiler [START_REF] Lattner | LLVM: A compilation framework for lifelong program analysis and transformation[END_REF]. The granularities are determined later at runtime.

Kernel Instantiation and Communication Generation

OpenCL function calls from the host are intercepted by our runtime library Libsplit. When the kernel is called in the OpenCL code, the values of the scalar parameters and the size of the NDRange are known. The array regions can then be evaluated and the range of work-item ids is determined according to the chosen granularity and the size of work-groups. The runtime kernel instantiation evaluates the dimension of the NDRange that allows to distribute written data among devices, with no need for a merge operation, if possible.

Array regions are defined as union of guarded intervals. In order to reduce the number of communications, we evaluate for a given interval of ids and for each array an interval including the array region.

Figure 2 shows the different steps, assuming a copy is performed with a WriteBuffer command. Calls to WriteBuffer are deferred communications: Our library registers the commands, write protects the buffers to prevent any modification until the kernel execution. If one buffer is modified before kernel execution, the modification access is trapped, so that the copies occur first and then the modification occurs. If the buffers are not modified, this additional copy is not done. When the kernel is called, the granularity for each device is computed and the devices execute a subkernel, with its associated data. The runtime analysis keeps information related to data distribution. When multiple kernel executions are performed, communications are only performed for data not already present on the device.

Limits of the analysis The previous analysis is not always able to precisely compute the regions accessed by a work-item, in particular when indirections occur or when the region accessed depends on control flow too complex for the analysis. When this happens, the array is not split between devices. If the array is written, a merge operation is required after the kernel execution in order to fuse the different contributions computed by each device. The operation we propose is based on a diff, similarly to [START_REF] Pandit | Fluidic Kernels: Cooperative Execution of OpenCL Programs on Multiple Heterogeneous Devices[END_REF]. Such operation degrades the overall performance for communication/memory bound kernels.

Adapting Granularity

This section proposes a method to dynamically adapt granularity to the devices and to the kernel, assuming the same kernel is executed multiple times.

Formalization

Given a kernel and n devices, the problem consists in determining how to split the computation among the devices so as to minimize the execution time. Each device executes the same kernel, but possibly with a different number of workgroups and different data. We formally define the granularity as a value x i in [0, 1] corresponding to the ratio between the number of work-groups allocated to the device i and the total number of work-groups (numgroups). numgroups is known when the kernel is called. We define f i (x i , offset i , t) as the mean time to execute one work-group on device i, when a subkernel of granularity x i is executed at time step t, with an offset offset i . The total execution time of this subkernel is therefore f i (x i , offset i , t) * x i * numgroups.

The solution to the problem consists in finding the time T and the granularities x i and the offsets offset i such that the system in Fig. 3a is fulfilled. The functions f i are not known precisely but they can be measured for a given x i , offset i and t. We arbitrarily order the offsets by increasing id of device.

Thus, with offsets defined by values in [0, 1], offset 1 = 0, . . . , offset n = k<n x k and f i no longer depends on offsets in Fig. 3b but on x i .

We generalize this formulation by introducing a new set of variables, y i ∈ [0, 1], as shown in Fig. 3b. Now it is possible to define a function F such that F t (x) = (y), with x = (x i ) i the vector of all x i and y = (y i ) i the vector of all y i , satisfying conditions from Fig. 3b:

Ft(x) = T fi(x1, . . . , xi, t) * numgroups i , with T = numgroups i 1/fi(x1,...,xi,t)
. The evaluation of F t (x) requires O(n) basic arithmetic operations with n the number of devices. A solution to the problem of Fig. 3a can be found by computing a fixed point of the function F: F t (x) = x or similarly, by finding the 0 of the function

G t : G t (x) = x -F t (x)

Resolution Method

First assume the function F t does not depend on t, the iteration count. Several methods have been proposed in the literature for solving such problem, when the function is not known analytically: The fixed point method consists in computing the suite of granularity vectors x k = F (x k-1 ), k ≥ 1 from some initial value x 0 . The evaluation of F (x k-1 ) requires to execute the kernel with the granularities x k-1 . When the suite converges, it converges linearly towards a vector of optimal granularities satisfying the initial problem and achieving perfect load balance. The convergence depends on F and on the initial value x 0 but is in general linear. The secant method, or its generalization for n-D space the Broyden's method, uses an approximate gradient to converge to the 0 of a function with a near quadratic convergence rate. We implemented both methods to refine the granularity assigned to each device. F is evaluated at each kernel instantiation and provides the input necessary to instantiate the partition-ready kernel.

Finally, when the functions f i also depend on the iteration count t, the fixed point equation becomes F t-1 (x k-1,t-1 ) = x k,t with F changing for each term of the suite. For real applications, a good approximation of the solution at step t remains a good approximation at step t+1. As the fixed point method converges quickly when the approximation is close to the solution, we believe this approach can be used for many real cases. We demonstrate for a N-Body application that the fixed point method is able to stay close to the optimal, even when the optimal granularity is varying with the iteration count (see Section 7).

Related Works

Several works focus on kernel splitting. Kim et al. [START_REF] Kim | Achieving a single compute device image in OpenCL for multiple GPUs[END_REF] are making one OpenCL device unifying multiple uniform GPUs. The OpenCL NDRange and array regions are split according to the values recorded by sampling. They do not handle conditionals as we do and assume that array indices are all linear in the kernel parameters. Moreover, they assume subkernels have the same load. Luk et al. [START_REF] Luk | Qilin: exploiting parallelism on heterogeneous multiprocessors with adaptive mapping[END_REF] propose an heterogeneous programming system that provides an adaptive mapping technique based on execution-time projections stored in a database during training runs. The technique we propose does not require training runs. Li et al. [START_REF] Li | Automatic OpenCL Code Generation for Multi-device Heterogeneous Architectures[END_REF] present STEPOCL, a tool which takes as input kernels along with a configuration file and generates automatically an OpenCL multi-devices application. The configuration file describes how to split data, the control flow of the program, and allow to have specialized kernels for different architectures. The work partitioning between devices is based on offline profiling. Grewe et al. [START_REF] Grewe | A Static Task Partitioning Approach for Heterogeneous Systems Using OpenCL[END_REF] propose a pure static task partitioning method, based on predictive modeling and program features. They do not collect data dynamically however and cannot adapt to differences in terms of computing efficiency, depending on granularity, as shown in the motivating example. Kim et al. [START_REF] Kim | SnuCL: an OpenCL framework for heterogeneous CPU/GPU clusters[END_REF] propose to solve the load imbalance problem on CPUs by dynamically assigning sets of work-groups with decreasing sizes to an idle compute unit thread. It manages data across different devices in a cluster, however mapping tasks and data to these devices is left to the programmer. Seo et al. [START_REF] Seo | Automatic OpenCL work-group size selection for multicore CPUs[END_REF] propose an automatic work-group size selection technique for OpenCL kernels on multicore CPUs. Their method uses a profiling-based algorithm. Heterogeneity is not handled however and kernels are assumed to be work-group size independent. Kofler et al. [START_REF] Kofler | An Automatic Input-sensitive Approach for Heterogeneous Task Partitioning[END_REF] present a method for OpenCL task partitioning relying on offline generated model. This model is based on artificial neural networks, relying on the features of the kernels, including their input sizes. In [START_REF] Boyer | Load Balancing in a Changing World: Dealing with Heterogeneity and Performance Variability[END_REF], the authors propose a dynamic method to partition OpenCL tasks and perform load balancing. Their approach generates chunks of work-groups with increasing size to execute on different devices and selects the best partition of these chunks on the devices. The chunks are manually generated and there is no automatic scheme to partition data for the OpenCL kernels.

In [START_REF] Pandit | Fluidic Kernels: Cooperative Execution of OpenCL Programs on Multiple Heterogeneous Devices[END_REF], the authors propose an OpenCL runtime that takes a single device kernel and executes it on CPU and GPU. Load balancing is managed at runtime. While their approach dynamically balance work between one CPU and one GPU, it cannot be easily generalized for any number of devices. Besides, data is not split between subkernels, all arrays are transferred to all devices. Finally, the kernel transformation is achieved by hand, and not with an automatic compiler optimization. In [START_REF] Shen | Glinda: a framework for accelerating imbalanced applications on heterogeneous platforms[END_REF], Shen et al. present a method for heterogeneous platforms and imbalanced applications. They propose a model integrating both the workload of the application, determined by sampling, and the architecture. When the workload has an irregular shape, it is reshaped by sorting to obtain a regular shape with a peak and a bottom part. Based on this model and after profiling, a predictor determines the optimal partitioning between CPUs and GPUs. The work described in [START_REF] Lee | SKMD: Single Kernel on Multiple Devices for Transparent CPU-GPU Collaboration[END_REF] relies on complex training, resorting to linear regression techniques in order to predict the correct load balance. They do not handle dynamic load changes, such as the SpMV or OTOO case shown in the motivating example. In [START_REF] Lee | Orchestrating Multiple Data-Parallel Kernels on Multiple Devices[END_REF], the authors extend the previous work to complete task graphs. It is still based on offline training and assumes performance per work-group is constant, while we have shown there can be large variations.

Experiments are conducted on two platforms: conan -16-core Intel Xeon E5-2650 2.00GHz with 64GB, 3 Nvidia Tesla M2075; happyCL -12-core Intel Xeon E5-2680 2.80GHz with 64GB, Nvidia Tesla K20c, Nvidia Quadro K5000.

Detailed Load Balancing: Figure 4 shows the speed-up obtained on conan with AESEncrypt and EP compared to the best single device performance, when these kernels are repeated 10 times. The speed-up shown here are per iteration. For the first iteration, the granularity is the same for all devices (uniform hypothesis), explaining poor performance compared to the GPU performance. For EP, Figure 4a, the fixed point method requires 6 iterations to reach a maximum speed up of 2.8, whereas the Broyden's method converges in only 4 iterations leading to a better global speedup. For AESEncrypt, Figure 4b shows there is no such difference and both methods are similar, reaching a peak speed-up of 2.15 in 3 iterations only. The variations are due to the fact that the optimal granularity does not correspond to a round number of work-groups, hence there are granularity adjustments and communications at each step.

Figure 5 shows how our method behaves when the load changes over 60 iterations. Figure 5a illustrates the time taken by each subkernel for OTOO when the granularity is the same for all devices (Uniform strategy). From one device to the other, the execution time differs by more than a factor 3 (iteration 15 for instance). Figure 5b shows how the same load is shared among the four devices when it is continuously adapted by our technique (Adaptive strategy). As the 4 plots are close to each other, this shows the execution time is nearly optimal. We observe that convergence to the optimal only requires 2 iterations.

Overall Speedups: Figure 6 presents speed-ups compared to the best single device performance on the two target architectures, for a large number of benchmarks when they are repeated 100 times. We observe the results of our method (Adaptive) are close to the optimal, obtained when launching the kernel directly with the granularity obtained after convergence (Oracle). For Jacobi1D and Jacobi2D, the gap is more important because these benchmarks consist in Figure 5a shows the execution time of each subkernel with the Uniform splitting, same granularity for all devices. Figure 5b shows the execution time of each subkernel with the Adaptive splitting.

2 kernels, one stencil and one copy. Defining the same granularity for both copy and stencil minimizes communication time. Our method handles only one kernel at a time, and does not find the same granularity for both kernels. Uniform and Adaptive are using subkernels automatically obtained by our method.

Conclusion

We proposed in this paper the design and implementation of a method that simplifies the development of OpenCL applications for heterogeneous, multi-device systems. Our technique splits computation and data automatically across the computing devices, handling all load-balancing issues, including load variations when the kernel is executed iteratively. We have shown the optimal granularity is obtained in a few iterations and the technique does not require profiling or training. The approach is completely transparent to the user, and the same code can be executed without modification on different machines.

Fig. 1 .

 1 Fig. 1. (a) and (b): Impact on performance of architectural heterogeneity and granularity on AESEncrypt and EP benchmarks. Performance is given as an average time per work-group, granularity as a percentage of the total number of work-groups. (c) Impact on performance of the offset (starting index) for SpMV kernel, with a fixed granularity of 1/4. (d) Impact of iteration count on performance for OTOO application. Granularities are set to 1/4 for all devices, and offset is fixed on all devices.

  void KERNEL(float *A) { ... S1: double(* B)[3][5][5] =(double (*) [3][5][5])&A[ offset ]; ... S2: B[1][0][0]=.. } the analysis detects that statement S1 defines the 3D array B, aliasing A. S2 accesses B[1][0][0], corresponding to A[ 25+offset ]. Only constant offsets are handled so far. It generates a list of statements accessing input arrays, with their mapping function turning the index into an index of the input array.

Fig. 2 .

 2 Fig.2. Buffer management semantics. Indeed, the global size is different from the original kernel, the number of work-groups has changed and their id has changed too. Two additional parameters are added to the partition-ready kernel: splitdim (1,2 or 3) accounts for the dimension of the NDRange that is split, and numgroups is the number of work-groups in this dimension. Then the following function calls are changed: Expression Rewritten into get global size(expr) (expr == splitdim?numgroups*get local size(expr):get global size(expr)) get num groups(expr) (expr == splitdim?numgroups:get num groups(expr)) get group id(expr) (get global id(expr)/get local size(expr))

1 (Fig. 3 .

 13 Fig. 3. Formulations of the granularity problem

Fig. 4 .Fig. 5 .

 45 Fig. 4. Speedup per iteration of EP and AESEncrypt

Fig. 6 .

 6 Fig.6. Performance of AESEncrypt, EP, MonteCarlo, OTOO, SPMV and some Polybench on happyCL (top) and conan (bottom). Original codes run only on one device. Uniform and Adaptive are using subkernels automatically obtained by our method.