Cyrille Bertelle

Antoine Dutot
email: antoine.dutot@univ-lehavre.fr

Frédéric Guinand

Damien Olivier

Organization Detection for Dynamic Load Balancing in Individual-Based Simulations

Keywords: Complex Systems, Self-Organization, Artificial Ants, Dynamic Graph, Community Structures, Dynamic Load Balancing, Individual-Based Model, Ecological Simulations

Large-scale individual-based simulations can benefit a lot from high performance computing environments. The benefit that can be hopped depends greatly on a good load distribution among the processing ressources together with the minimization of the communication overhead. However, minimizing both idle time and communication overhead requires the search for a trade-off.

Inspired by complex systems, the approach described in this paper aims at minimizing the volume of data exchanged over the network between tasks of a distributed application, while balancing the load between available computing 1 ressources. The method lies on the trail-laying trail-following paradigm used in algorithms based on artificial ants.

Introduction

There exist many application classes whose structural as well as numerical characteristics may change during their execution. Simulations are one of these classes, they cover a wide range of domains: from life and Earth sciences to social sciences. Many applications rest on a mathematical analysis and formulation of the global process to be simulated with systems of differential equations. An alternative or a complementary way of modeling problems for simulation purposes consists in modeling the environment, each entity moving and evolving within this environment, and the mechanisms needed for computing entities evolution, their activities and their interactions. Entities may be living beings, particles, or may represent non-material elements (vortices, winds, streams...). Individualbased models (IBM) belong to this category. Within such models, interactions between the environment and the individuals are explicit as well as interactions among individuals themselves. During the simulation, some individuals may appear and/or disappear without prior notice, and interactions may change, leading to the emergence of unpredictable organizations at different description levels.

Many recent studies have adopted this approach. The motivation is that "simulating the actions of single organisms allows to study how the properties of higher level ecological entities like swarms, populations, trophic networks and regional distribution patterns emerge" [START_REF] Breckling | Individual-based models as tools for ecological theory and application: Understanding the emergence of organisational properties in ecological systems[END_REF]. Instead of using systems of differential equations, an individual based model provides a representation of each entity, interactions between the environment and the individuals and among individuals themselves. From the computer science point of view, multi-agent systems coupled with discrete-time simulation constitutes an obvious way of implementing IBMs. Several tools and frameworks have already been proposed for that purpose as reported in [START_REF] Ginot | A multi-agents architecture to enhance end-user individual-based modelling[END_REF]. What motivates our work comes from a series of observations. In order to observe emergent properties in IBMs, many individuals have to be considered, the use of discrete classes instead of individuals may lead to wrong results [START_REF] Cope | Individuality in modelling: a simplifying assumption too far ? Nonlinear Analysis[END_REF]: "If IBMs treat individuals as members of classes, rather than as unique organisms, predictions of population size and variability may be wrong". In addition, "a successful application of the approach requires detailed biological information about the represented species." [START_REF] Breckling | Individual-based models as tools for ecological theory and application: Understanding the emergence of organisational properties in ecological systems[END_REF]. As a consequence, since the number of entities may reach thousands to millions, distributed simulations running on high performance computing environments is unavoidable in order to obtain results in a reasonable time. However, the benefit that can be hopped depends greatly on a good load distribution among the processing ressources together with the minimization of the communication overhead. In order to limit/avoid performance degradations due to the dynamics of such applications, the possible re-allocation of existing entities and the allocation of new ones have to be continuously managed. But that's not enough, for observing emergent organizations and structures in the system, the scientists need another software for detecting such properties. The tool presented in this paper, AntCO 2 , advises for both: dynamic allocation and re-allocation of individuals and detection of application-level organizations. AntCO 2 is a bio-inspired algorithm based on numerical ants. It gives global information in a decentralized way that indicate a possible better location of some existing entities or a good location for new ones, according to processors load, inter-entities communications and existing application-level organizations. But it also gives global information for detecting new application-level organizations.

The next section presents the general context of ecological simulations and specifies the problem of dynamic load balancing, in particular for individualbased ecological models. In section 3, the problem is formalized and the method is presented. Some experiments are reported in Section 4 and the last Section discusses open perspectives for this work.

General Context

The problem we are interested in is the distribution of entities composing a system conceived for simulating ecosystems using individual-based models. Before entering in the details of the distribution strategy, the following section presents the target applications.

Individual-Based Ecological Simulation

Mechanisms leading to the global behavior of ecological systems often remain unclear, due to the large number of interactions and feedbacks processes. Differential equation-based models may be sometimes unsuited since the system is often characterized by different organization levels and by changing structures.

For many years, it has been accepted that some high level properties of ecological systems emerge from interactions among lower level components, but it has recently gain an important effort in the community [START_REF]Handbook of ecosystems theories and management[END_REF][START_REF] Reuter | The concept of emergent and collective properties in individual-based models -summary and outlook of the Bornhöved case studies[END_REF][START_REF] Jopp | Dispersal of carabid beetles -emergence of distribution patterns[END_REF][START_REF] Hölker | A spatiotemporal individual-based fish model to investigate emergent properties at the organismal and the population level[END_REF][START_REF] Johnson | Predicting global dynamics from local interactions: individual-based models predict complex features of marine epibenthic communities[END_REF][START_REF] Breckling | Individual-based models as tools for ecological theory and application: Understanding the emergence of organisational properties in ecological systems[END_REF]. In order to better understand the mechanisms at the origin of the emergence of these properties and to capture ecological dynamics over several levels of organization, ecologists use individual-based models [START_REF] Gross | Individual-based models and approaches in ecology: populations, communities and ecosystems[END_REF][START_REF] Grimm | Ten years of individual-based modelling in ecology: what have we learned and what could we lear in the future ?[END_REF]. These models allow the examination of explicit spatial and temporal variation on the scale of the individual. This approach allows scientists to build virtual laboratories to test different scenarii of the population evolution, and help them to understand the variations of some specific parameters of individuals (length, weight...) depending or not on environmental characteristics.

For example, in [START_REF] Hölker | A spatiotemporal individual-based fish model to investigate emergent properties at the organismal and the population level[END_REF], the authors present a spatiotemporal IBM of roach to study emergent properties at the individual and the population level. The fish model includes swimming mode that may lead to shoal formation, habitat selection according to food availability, temperature, light and age, bioenergetics, responsible for growth and that specifies energy storage, food consumption, and extra metabolic functions (respiration...). They also provide a model of the environment (Lake Belau). Their study shows that some interesting emergent properties can be obtained from the simulation. At the individual level, they notice that spatial behavior, as well as growth and food consumption fit with empirical studies. At the population level, among other properties, they show that the fishes self-sort themselves in shoals according to their length, they also remark a length variability into the population, and they show that this variability depends on the lake morphology.

Our motivation for that work comes from a series of remarks. At first, a noticeable point is that some processes occurring in IBMs are non linear and very sensitive to initial conditions. As a consequence, two runs of the same simulation, with similar initial conditions, may lead to different global situations. Secondly, some parts of the simulation depend on random choices, and this leads ecologists to perform many runs starting from the same parameters set but with different values of the random seed. Thirdly, running individual-based simulations may require a lot of time with respect to the temporal as well as the space scales considered.

Finally, as said by Dunstan and Johnson in [START_REF] Johnson | Predicting global dynamics from local interactions: individual-based models predict complex features of marine epibenthic communities[END_REF]: "in real ecologies, space does matter: real assemblages typically manifest non-random spatial pattern at a range of scales, which underpins patterns of spatial variability, and individual organisms are more likely to interact with neighbouring than with distant indi-viduals".

We can summarize all these remarks saying that individual-based ecological applications are time-consuming, characterized by dynamically changing structures, and made of sets of locally interacting entities. So, in the context of a distributed/parallel implementation of such applications, a desirable feature of a dynamic load-balancing method should be the detection of emerging structures based on interactions in order to map these structures on different computing resources with the aim of balancing the load. The remaining part of this paper is dedicated to the description and analysis of such a method.

Dynamic Load Balancing

The execution of an application in a parallel environment is efficient if the inactivity periods of the different computing resources are small with respect to the total execution duration. The two main sources of overhead for a given processor are idleness due to a lack of work, and time spent waiting for data from another processor (a.k.a. communication overhead). When the application is fully defined before the execution (precedence task graph, tasks durations and communication delays), an a priori computation of a schedule is possible. But, when the application is partially known or undefined before the execution, an on-line strategy with the aim of reducing both idleness and communication overhead has to be considered. This is dynamic load balancing (DLB). The problem may be described as the on-line allocation or migration of tasks to computing resources. It is usually assumed that communications between tasks located on the same processor may be neglected. The communications that may entail overhead occur between tasks located on distinct computing resources. Thus, the quality of a dynamic load balancing strategy rests on its capacity of combining local decisions (communicating tasks gathered into clusters) with global ones (load balancing). Partitioning of the application graph seems to be a suitable starting point for that purpose, since clustering may be driven by the objective of minimizing the communications, and the load balancing may be achieved by fixing the number of clusters.

There are two main approaches to the problem. In the first one, relevant information is gathered and the load balancing is computed by only one processor: this is the centralized scheme. Advantadges: the decision is taken according to the full knowledge of the system and classical quality-proven algorithms can be used. But, keeping and/or gathering updated information generates an important network traffic and the decision process (collect of information and decision making) has to be faster than changes in the application. The decentralized scheme is the second approach. Most of distributed DLB strategies rely on load exchanges between neighbor computing resources. For instance, in the method proposed by Heiss and Schmitz [START_REF] Heiss | Decentralized dynamic load balancing: The particles approach[END_REF], each computing resource possesses a load balancing procedure which is activated when a change of the load occurs in the neighborhood. They address the problem of dynamically load balancing several applications, and their approach is based on an analogy with physics. Each application is considered as a fluid characterized by a viscosity factor modelling communication density between tasks forming the application. Fluids are added to a flat container (corresponding to the computing resources). Two kinds of forces are considered: gravitational forces that entails a spreading of the fluid, and frictional resistance and cohesion forces (related to the viscosity) that keep the fluid dense.

The former force leads to more parallelism while the latter aim at minimizing inter-processors communications. However, in their work, the behavior of each application is supposed fixed during the application execution, so for them, "load balancing should take place when the load situation has changed. The load situation changes when tasks are generated or finished", while for us, load balancing should take place when either the load situation changes or when the communi-cation characteristics (numerical as well as structural) change.

Another interesting method was proposed by Fenet and Hassas [START_REF] Hassas | Ant based system for dynamic multiple criteria balancing[END_REF] who use numerical ants. Ants are used for process migration, according to pheromones concentration on the arcs of the computing environment topology. Pheromones code for the load of the processors and different kinds of pheromones are attributed to different groups of processes, given that processes inside a group aim at communicate with each other.

Our goal is to implement such a DLB method that is additionally able to detect interacting groups instead of identifying them a priori.

Organization Detection and Load Balancing

Large-scale ecological simulations are natural candidates for distributed discrete event simulation [START_REF] Glass | Distributed simulation of spatially explicit ecological models[END_REF]. However, such simulations may also be performed through a series of discrete time steps [START_REF] Scahill | Distributed individual-based environmental simulation[END_REF]. In both cases, the same graph model can be considered: a dynamic interaction graph, that is a graph varying along time.

Individual-based ecological models are made of an environment and many entities interacting with the environment and each other. We are in front of complex systems in which there are numerous interactions. As the system evolves, communications between entities change. Entities and their interactions appear and disappear creating stable or unstable organizations. Each entity, in IBMs, is simulated at the level of the individual organism rather than the population level, and the model allows individual variation to be simulated [START_REF] Barnes | The impact of programming paradigms on the efficiency of an individual-based simulation model[END_REF]. Thus, during the simulation process some entities may appear or disappear without prior notice, groups of entities with weak interactions may meet, leading to an important increase of the number of communications between them.

Problem formulation

While highly dynamic, the whole system may be modeled using a classical undirected graph whose structural and numerical characteristics may change during the simulation.

Within such a graph, each vertex is associated to an element of the simulation that may be a biological entity or any environmental element, and an edge materializes an interaction between two elements of the simulation, mapped to a communication in lower levels of the implementation.

More formally, the considered simulations are composed of a number n at time t of interacting entities, which we wish to distribute over a number of p processing resources. Entities do not necessarily communicate with all the others and their numbers and the communications may vary during the application execution. The pattern of communications can be represented by a dynamic graph (network) in which entities are mapped one-to-one with vertices and communications with edges.

We distinguish communications occuring inside a single computing resource, that is between entities in executing on the same computer, from communications that must cross the network between distinct computing resources. We call the later actual communications.

Dynamic graph: A dynamic graph G(t) = (V(t), E(t)) is a weighted undi- rected graph such that: • V(t) is the set of vertices at time t. • E(t) is the set of edges at time t. Each edge (u, v) is characterized by: -a weight w(t, u, v) ∈ N -{0}.
The problem is to distribute entities of the application at anytime in such a way to balance the load on each processing resources and at the same time to minimize the actual communications. To solve this problem, we search a partition of the graph G(t) defined as follows:

Let G(t) = (V(t), E(t)) a dynamic graph, a partition D(t) of G is composed by k disjointed subsets D i (t) of V(t) called domains with : k > 0, i=1..k D i (t) = V(t)
Where the set of edges connecting the domains of a partition (i.e. edges cut by the partition) D(t) is called an edge-cut denoted by B(t).

The objective is therefore to find a k-partition, at anytime, which evenly balances the vertex weight among the processing resources while minimizing the total weight of B(t). The number of domains k must be greater or equal than p the number of processing resources. For example, in figure 1, we have 4-partitions and three domains identied by three colors.

AntCO 2 , an ant algorithm

Ant algorithms are a class of meta-heuristics based on a population of agents exhibiting a cooperative behaviour [START_REF] Langton | Artificial Life[END_REF]. Ants are social insects which manifest a collective problem-solving ability [START_REF] Deneubourg | Collective patterns and decision making[END_REF]. They continuously forage their territories to find food [START_REF] Gordon | The expandable network of ant exploration[END_REF] visiting paths, creating bridges, constructing nests, etc. This form of self-organization appears from interactions that can be either direct (e.g. mandibular, visual) or indirect. Indirect communications arise from individuals changing the environment and other responding to these changes: this is called stigmergy 1 . There are two forms of stigmergy, sematectonic stigmergy produces changes in the physical environment -building the nest for exampleand stigmergy based on signal which uses environment as support. Thus, for example, ants perform such indirect communications using chemical signals called pheromones. The larger the quantity of pheromones on a path, the larger the number of ants visit this path. As pheromone evaporates, long paths tend to have less pheromone than short ones, and therefore are less used than others (binary bridge experiment [START_REF] Goss | Self-organized shortcuts in the argentine ant[END_REF])). Such an approach is robust and well supports parameter changes in the problem. Besides, it is intrinsically distributed and scalable. It uses only local information (required for a continuously changing environment), and find near-optimal solutions. Ant algorithms have been applied successfully to various combinatorial optimization problems like the Travelling Salesman Problem [START_REF] Dorigo | Ant colony system: A cooperative learning approach to the traveling salesman problem[END_REF], routing in networks [START_REF] Caro | Antnet: A mobile agents approach to adaptive routing[END_REF][START_REF] White | Routing with swarm intelligence[END_REF], clustering [START_REF] Faieta | Diversity and adaptation in populations of clustering ants[END_REF], graph coloring [START_REF] Costa | Ant can colour graphs[END_REF], graph partitioning [START_REF] Kuntz | A colony of ant-like agents for partitioning in VLSI technology[END_REF], and more recently DNA sequencing [START_REF] Bertelle | DIMANTS: a distributed multi-castes ant system for DNA sequencing by hybridization[END_REF], dynamic load balancing falls into the category of optimization problems. Dorigo et al. [START_REF] Bonabeau | Swarm Intelligence: from natural to artificial systems[END_REF], define an approach named Ant Colony Optimization (ACO) that may be applied to a given problem if it is possible to define: the problem representation as a graph, the heuristic desirability of edges, a constraint satisfaction, a pheromone updating rule and a probabilistic transition rule.

Our approach, AntCO 2 , is an ant algorithm that exhibits great similarities with ACO, excepted that it has no satisfaction constraint, and detects organizations with several colonies in competition, each of a distinct color.

Organizations are seen as a sub-graph, set of vertices that are more densely connected each other, both in number of links, and eventually in the importance of the links, while being slightly connected with the other vertices that do not belong to the considered sub-graph.

We search such organizations since they concentrate communications inside themselves. As we want to reduce communication costs, identifying high communication areas allows to better distribute them. Furthermore the graph being dynamic, such organizations will present a more stable form than edges and vertices taken alone.

Indeed, communications on a single host are often considered negligible, whereas communications between hosts are more costly. Therefore placing organizations on hosts may provide a good communication cost reduction. We must also take into account the possible overhead of the different computing resources.

To reach this objective we have to determine a good load balancing between computing resources. Unfortunately, this objective is in conflict with the other which is to minimize the communication costs. A good trade-off must be find. Thus if to find organizations with collaborative ants offer a good solution to reduce the communication costs, competition with colored ants is introduced to obtain a good load balancing.

Colored ants

The method proposed by Kuntz et al. [START_REF] Kuntz | A colony of ant-like agents for partitioning in VLSI technology[END_REF] for graph partitioning is able to detect clusters within a graph and it also has the ability of gathering vertices such that:

1. if they belong to the same cluster they are gathered in the same place, 2. the number of intercluster edges is minimized and, 3. distinct clusters are located in different places in the space.

Points 1. and 2. are relevant for our application, however, additional issues have to be considered:

1. the number of clusters may be different of the number of processing resources, 2. the sum of the sizes of the clusters allocated to each processing resource has to be similar (considering the resource computing capacity), 3. and their number as well as the graph structure may change.

For the first issue, in [START_REF] Bonabeau | Swarm Intelligence: from natural to artificial systems[END_REF], the authors mentioned the possibility to parametrize their algorithm in order to choose the number of clusters to build. Unfortunately, for our application, we do not know in advance what should be the best number of clusters for achieving the best load balancing, as shown in Figure 1, where elements of the two opposite and not directly linked clusters should be allocated to the same processing resource. As the number of processing resources available at a given moment is known, this problem may be identified as a competition between processing resources for computing as many elements as possible. This may be directly included in the ant approach by considering competing ant colonies. In our approach, a distinct color is associated to each computing resource, and an ant colony is attached to each resource. Each ant is also colored, and drops pheromones of its color.

✁ ✁ ✁ ✁ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✄ ✁✄ ✄ ✁✄ ✄ ✁✄ ✄ ✁✄ ☎ ✁☎ ☎ ✁☎ ☎ ✁☎ ☎ ✁☎ ✆ ✁✆ ✆ ✁✆ ✆ ✁✆ ✆ ✁✆ ✝ ✁✝ ✝ ✁✝ ✝ ✁✝ ✝ ✁✝ ✞ ✁✞ ✞ ✁✞ ✞ ✁✞ ✞ ✁✞ ✟ ✁✟ ✟ ✁✟ ✟ ✁✟ ✟ ✁✟ ✠ ✁✠ ✠ ✁✠ ✠ ✁✠ ✠ ✁✠ ✡ ✁✡ ✡ ✁✡ ✡ ✁✡ ✡ ✁✡ ☛ ✁☛ ✁☛ ☛ ✁☛ ✁☛ ☛ ✁☛ ✁☛ ☛ ✁☛ ✁☛ ☞ ✁☞ ✁☞ ☞ ✁☞ ✁☞ ☞ ✁☞ ✁☞ ☞ ✁☞ ✁☞ ✌ ✁✌ ✌ ✁✌ ✌ ✁✌ ✌ ✁✌ ✍ ✁✍ ✍ ✁✍ ✍ ✁✍ ✍ ✁✍ ✎ ✏✎ ✏✎ ✏✎ ✎ ✏✎ ✏✎ ✏✎ ✑ ✏✑ ✏✑ ✏✑ ✑ ✏✑ ✏✑ ✏✑ ✒ ✏✒ ✏✒ ✏✒ ✏✒ ✒ ✏✒ ✏✒ ✏✒ ✏✒ ✓ ✏✓ ✏✓ ✏✓ ✓ ✏✓ ✏✓ ✏✓ ✔ ✏✔ ✏✔ ✏✔ ✔ ✏✔ ✏✔ ✏✔ ✕ ✏✕ ✏✕ ✏✕ ✕ ✏✕ ✏✕ ✏✕ ✖ ✁✖ ✁✖ ✖ ✁✖ ✁✖ ✖ ✁✖ ✁✖ ✖ ✁✖ ✁✖ ✗ ✁✗ ✁✗ ✗ ✁✗ ✁✗ ✗ ✁✗ ✁✗ ✗ ✁✗ ✁✗ ✘ ✁✘ ✘ ✁✘ ✘ ✁✘ ✘ ✁✘ ✙ ✁✙ ✙ ✁✙ ✙ ✁✙ ✙ ✁✙ ✚ ✁✚ ✁✚ ✚ ✁✚ ✁✚ ✚ ✁✚ ✁✚ ✚ ✁✚ ✁✚ ✛ ✁✛ ✛ ✁✛ ✛ ✁✛ ✛ ✁✛ ✜ ✏✜ ✏✜ ✏✜ ✜ ✏✜ ✏✜ ✏✜ ✢ ✏✢ ✏✢ ✏✢ ✢ ✏✢ ✏✢ ✏✢ ✣ ✏✣ ✏✣ ✏✣ ✣ ✏✣ ✏✣ ✏✣ ✤ ✏✤ ✏✤ ✏✤ ✤ ✏✤ ✏✤ ✏✤ ✥ ✁✥ ✥ ✁✥ ✥ ✁✥ ✥ ✁✥ ✦ ✁✦ ✦ ✁✦ ✦ ✁✦ ✦ ✁✦ ✧ ✁✧ ✁✧ ✧ ✁✧ ✁✧ ✧ ✁✧ ✁✧ ✧ ✁✧ ✁✧ ★ ✁★ ★ ✁★ ★ ✁★ ★ ✁★ ✩ ✁✩ ✩ ✁✩ ✩ ✁✩ ✩ ✁✩ ✪ ✁✪ ✪ ✁✪ ✪ ✁✪ ✪ ✁✪ ✫ ✁✫ ✫ ✁✫ ✫ ✁✫ ✫ ✁✫ ✬ ✁✬ ✬ ✁✬ ✬ ✁✬ ✬ ✁✬ ✭ ✁✭ ✭ ✁✭ ✭ ✁✭ ✭ ✁✭ ✮ ✁✮ ✮ ✁✮ ✮ ✁✮ ✮ ✁✮ ✯ ✏✯ ✏✯ ✏✯ ✯ ✏✯ ✏✯ ✏✯ ✰ ✏✰ ✏✰ ✏✰ ✰ ✏✰ ✏✰ ✏✰ ✱ ✏✱ ✏✱ ✏✱ ✱ ✏✱ ✏✱ ✏✱ ✲ ✏✲ ✏✲ ✏✲ ✲ ✏✲ ✏✲ ✏✲ ✳ ✏✳ ✏✳ ✏✳ ✏✳ ✳ ✏✳ ✏✳ ✏✳ ✏✳ ✴ ✏✴ ✏✴ ✏✴ ✏✴ ✴ ✏✴ ✏✴ ✏✴ ✏✴ ✵ ✁✵ ✵ ✁✵ ✵ ✁✵ ✵ ✁✵ ✶ ✁✶ ✶ ✁✶ ✶ ✁✶ ✶ ✁✶ ✷ ✁✷ ✷ ✁✷ ✷ ✁✷ ✷ ✁✷ ✸ ✁✸ ✸ ✁✸ ✸ ✁✸ ✸ ✁✸ ✹ ✁✹ ✹ ✁✹ ✹ ✁✹ ✹ ✁✹ ✺ ✁✺ ✺ ✁✺ ✺ ✁✺ ✺ ✁✺ ✻ ✁✻ ✻ ✁✻ ✻ ✁✻ ✻ ✁✻ ✼ ✁✼ ✼ ✁✼ ✼ ✁✼ ✼ ✁✼ ✽ ✁✽ ✽ ✁✽ ✽ ✁✽ ✽ ✁✽ ✾ ✁✾ ✾ ✁✾ ✾ ✁✾ ✾ ✁✾ ✿ ✁✿ ✿ ✁✿ ✿ ✁✿ ✿ ✁✿ ❀ ✁❀ ❀ ✁❀ ❀ ✁❀ ❀ ✁❀ ❁ ✁❁ ❁ ✁❁ ❁ ✁❁ ❁ ✁❁ ❂ ✁❂ ❂ ✁❂ ❂ ✁❂ ❂ ✁❂ ❃ ✁❃ ❃ ✁❃ ❃ ✁❃ ❃ ✁❃ ❄ ✁❄ ❄ ✁❄ ❄ ✁❄ ❄ ✁❄ ❅ ✁❅ ❅ ✁❅ ❅ ✁❅ ❅ ✁❅ ❆ ✁❆ ❆ ✁❆ ❆ ✁❆ ❆ ✁❆ ❇ ✏❇ ✏❇ ✏❇ ✏❇ ❇ ✏❇ ✏❇ ✏❇ ✏❇ ❈ ✏❈ ✏❈ ✏❈ ✏❈ ❈ ✏❈ ✏❈ ✏❈ ✏❈ ❉ ✏❉ ✏❉ ✏❉ ❉ ✏❉ ✏❉ ✏❉ ❊ ✏❊ ✏❊ ✏❊ ❊ ✏❊ ✏❊ ✏❊ ❋ ✏❋ ✏❋ ✏❋ ❋ ✏❋ ✏❋ ✏❋ • ✏• ✏• ✏• • ✏• ✏• ✏• ❍ ✁❍ ❍ ✁❍ ❍ ✁❍ ❍ ✁❍ ■ ✁■ ■ ✁■ ■ ✁■ ■ ✁■ ❏ ✏❏ ✏❏ ✏❏ ❏ ✏❏ ✏❏ ✏❏ ❑ ✏❑ ✏❑ ✏❑ ❑ ✏❑ ✏❑ ✏❑ ▲ ✁▲ ▲ ✁▲ ▲ ✁▲ ▲ ✁▲ ▼ ✁▼ ▼ ✁▼ ▼ ✁▼ ▼ ✁▼ ◆ ✁◆ ✁◆ ◆ ✁◆ ✁◆ ◆ ✁◆ ✁◆ ◆ ✁◆ ✁◆ ❖ ✁❖ ❖ ✁❖ ❖ ✁❖ ❖ ✁❖ ✁ ✁ ✁ ✁ ◗ ✁◗ ◗ ✁◗ ◗ ✁◗ ◗ ✁◗ | ✏| ✏| ✏| | ✏| ✏| ✏| ❙ ✏❙ ✏❙ ✏❙ ❙ ✏❙ ✏❙ ✏❙ ❚ ✁❚ ❚ ✁❚ ❚ ✁❚ ❚ ✁❚ ❯ ✁❯ ❯ ✁❯ ❯ ✁❯ ❯ ✁❯ ❱ ✁❱ ✁❱ ❱ ✁❱ ✁❱ ❱ ✁❱ ✁❱ ❱ ✁❱ ✁❱ ❲ ✁❲ ✁❲ ❲ ✁❲ ✁❲ ❲ ✁❲ ✁❲ ❲ ✁❲ ✁❲ ❳ ✏❳ ✏❳ ✏❳ ❳ ✏❳ ✏❳ ✏❳ ( ✏( ✏( ✏( ( ✏( ✏( ✏( ) ✁) ) ✁) ) ✁) ) ✁) ❬ ✁❬ ❬ ✁❬ ❬ ✁❬ ❬ ✁❬ ❭ ✏❭ ✏❭ ✏❭ ✏❭ ❭ ✏❭ ✏❭ ✏❭ ✏❭ ( ✏( ✏( ✏( ( ✏( ✏( ✏( ) ✁) ) ✁) ) ✁) ) ✁) ❴ ✁❴ ❴ ✁❴ ❴ ✁❴ ❴ ✁❴ ❵ ✏❵ ✏❵ ✏❵ ❵ ✏❵ ✏❵ ✏❵ ❛ ✏❛ ✏❛ ✏❛ ❛ ✏❛ ✏❛ ✏❛
So, in addition to the classical collaborative nature of ant colonies we have added the competition aspect to the method. In fact, this reflects exactly the trade-off previously discussed about dynamic load-balancing. On one hand, the collaborative aspect of ants allows the minimization of communications by gathering into clusters elements that communicate a lot, while, on the other hand, the competition aspect of colored ants allows the balancing of the load between computing resources.

The technical issues about the management of ants, colors and pheromones are described in detail in the next sections.

Graph description and notations

As previously mentioned, we consider an undirected graph which structural as well as numerical characteristics may be subject to changes during the execution. Colored ants walk within this graph, crossing edges and dropping colored pheromones on them.

Dynamic Communication Colored Graph:

A dynamic communication colored graph is a dynamic graph G(t) = (V(t), E(t), C(t)) such that:

• C(t) is a set of p colors where p is the number of available processing resources of the distributed system at time t.

• V(t) is the set of vertices at time t. Each vertex v is characterized by:

a color c ∈ C(t),

• E(t) is the set of edges at time t. Each edge (u, v) is characterized by:

a weight w (t) (u, v) ∈ N -{0} that corresponds to the volume and/or the frequency and/or the delay of communications between the elements associated to vertices u and v, a quantity of pheromones of each color.

The figure 1 shows an example of a dynamic communication colored graph where the proposed method described in the following, changes the color of vertices if this improve communications or processing resource load. The algorithm tries to color vertices of highly communicating clusters with the same colors.

Therefore a vertex may change color several times, depending on the variations of data exchange between entities. On the figure we can see three colors only, one for each computing resource, and four clusters. Indeed it can be necessary, in order to maintain a good load balancing to have several distinct clusters of the same color.

Pheromones management

We denote by F(t) the population of ants at time t, and F c (t) the set of ants of color c at time t. Pheromones are dropped on edges by ants crossing them.

Pheromones are colored. An ant x of color c crossing an edge (u, v) between steps t -1 and t will drop a given quantity of pheromone of color c. This quantity is denoted by

∆ (t)
x (u, v, c), and the quantity of pheromones of color c dropped by ants when they crossed edge (u, v) during time interval ]t -1, t] is equal to:

∆ (t) (u, v, c) = x∈Fc(t) ∆ (t) x (u, v, c) (1)
The total quantity of pheromones of all colors dropped by ants on edge (u, v) during ]t -1, t] is equal to

∆ (t) (u, v) = c∈C(t) ∆ (t) (u, v, c) (2)
If ∆ (t) (u, v) = 0, the rate of dropped pheromones of color c on (u, v) during ]t -1, t] is equal to:

K (t) c (u, v) = ∆ (t) (u, v, c) ∆ (t) (u, v) with K (t) c (u, v) ∈ [0, 1] (3)
The quantity of pheromone of color c present on the edge (u, v) at time t is denoted by τ (t) (u, v, c). At the beginning τ (0) (u, v) = 0 and this value changes according to the following recurrent equation:

τ (t) (u, v, c) = ρτ (t-1) (u, v, c) + ∆ (t) (u, v, c) (4)
Where ρ ∈ ]0, 1] denotes the persistence of the pheromones on the edges, that is the proportion of pheromones which has not been removed by the evaporation phenomenon.

τ (t) (u, v, c
) may be considered as a reinforcement factor for clustering vertices based on colored paths. However, due to the presence of several colors, this reinforcement factor is corrected according to

K (t)
c (u, v) that represents the relative importance of the considered color with respect to all colors. This corrected reinforcement factor is noted:

Ω (t) (u, v, c) = K (t) c (u, v)τ (t) (u, v, c)
Then, if we denote by V u the set of vertices adjacent to u at t, the color ξ (t) (u) of this vertex is obtained from the main color of its incident edges:

ξ (t) (u) = arg max c∈C(t) v∈Vu τ (t) (u, v, c) (5)

Ants moving and population management

Ants move according to local information present in the graph. Each processing resource is assigned to a color. Each vertex gets its initial color from the processing resource it was allocated to. Initially the number of ants of a given color is proportional to the processing resource power that they represent.

Population management

The process is iterative, between two steps, each ant crosses one edge and reaches a vertex. When there are too few ants, evaporation makes pheromones disappear and the method behaves as a greedy algorithm. If there are too many ants, pheromones play a predominant role and the system efficiency may decreases.

Furthermore, the population is regulated with respect to the number of processing resources and to the number of entities.

Initially, our algorithm creates a fixed number of ants per vertex, which depends on processing ressources power. Vertices are, in the same way, proportionally associated to processing resources. Then, during the execution, our method tries to keep the population density constant in the graph. When some new vertices are created, new ants are created in order to maintain the population density, and some ants are removed from the population when some vertices disappear.

When one new processing resource becomes available, the number of colors increases by one. However, the population has to be modified in order to take into account this new color. This is done by changing the color of an equal number of ants of each current color into the new color. Symmetrically, when a processing resource, associated to color c, disappears from the environment, either because of a failure or because this resource is out of reach in case of wireless environments, all ants of color c change their color into the remaining ones. The creation and the removing of edges have no effect on the population.

Ants moves

The moving decision of one ant located on vertex v k is taken according to its color and to the concentration of the corresponding colored pheromones on adjacent edges of u. Let us define p (t) (u, v k , c) the probability for one arbitrary ant of color c, located on the vertex u, to cross edge v k during the next time interval [t, t + 1[. If we denote w (t) (u, v k ) the weight associated to this edge at time t, then:

               p (t) (u, v k , c) = w (0) (u, v k ) v∈Vu w (0) (u, v) if t = 0 p (t) (u, v k , c) = (Ω (t) (u, v k , c)) α (w (t) (u, v k )) β v∈Vu (Ω (t) (u, v, c)) α (w (t) (u, v)) β if t = 0 (6)
The parameters α and β (both > 0) allow the weighting of the relative importance of pheromones and respectively weights. However, if ants choices were only driven by this probability formula, there would be no way for avoiding oscillatory moves. So, we introduce a penalisation factor in equation ( 6) η ∈ ]0, 1] aiming at preventing ants from using previously crossed edges. The idea is very similar to the tabu list used in tabu search heuristic, but we add this constraint directly into the probability formula. Each ant has the ability to remember the k last vertices it has crossed. These vertices are stored into a list: W x with card(W x ) < M (M constant). Then, the value of η for an ant x considering an edge (u, v) is equal to:

η x (v) =      1 if v / ∈ W x η if v ∈ W x (7)
Then, for the ant x, the probability of choosing edge (u, v) during time interval

[t, t + 1[ is equal to: p (t) x (u, v k , c) = (Ω (t) (u, v k , c)) α (w (t) (u, v k )) β η x (v k ) vq∈Vu (Ω (t) (u, v q , c)) α (w (t) (u, v q )) β η x (v q ) (8)
To complete this, we introduce a demographic pressure to avoid vertices that already contain too many ants of another color. This better spread ants in the graph to balance the load. It is modeled by an another penalisation factor γ(v)

on vertices that have a population greater than a given threshold. This factor is introduced in the formula [START_REF] Gross | Individual-based models and approaches in ecology: populations, communities and ecosystems[END_REF]. Given N (v) the ant count on the vertex v and N * the threshold.

γ(v) =      1 if N (v) ≤ N * γ ∈]0, 1] else (9)
The formula (8) becomes :

p (t) x (u, v k , c) = (Ω (t) (u, v k , c)) α (w (t) (u, v k )) β η x (v k )γ(v k ) vq∈Vu (Ω (t) (u, v q , c)) α (w (t) (u, v q )) β η x (v q )γ(v q ) (10)

Ants way of life

The algorithm is based on an iterative process. During the time interval [t, t + 1[, each ant may either, hatch, move, or die.

An ant of color c, located on a vertex u dies if the proportion of color c on adjacent edges is under a threshold. If φ ∈ [0, 1] is the threshold, then, the ant of color c located on u dies if:

v∈Vu τ (t) (u, v, c) c∈C(t) v∈Vu τ (t) (u, v, c) < φ (11)
A new ant is then created in another location. This "jumping" mechanism improves the global algorithm behavior. For instance, when the graph becomes unconnected, some ants may be prisoners of isolated clusters, and the die-andhatch sequence allow them to escape.

The mechanism, while keeping population constant, also avoids locked situations : grabs, overpopulation, starvation as shown on figure 2. These problems occur when the system meets local minima. For example, when a set of red ants are circled by a set of blue ants inside the same organization, or when too many ants of the same color are captured in an area because of a too large volume pheromones at this place. This phenomenon is amplified by retroactions with ants attracted by pheromone, depositing more pheromones, that attracts more ants etc.

It also allows to avoid areas without any ants, that are the counterparts of overpopulated areas. Moreover, this improves the reactivity of our algorithm that runs continuously, not to find the best solution for a static graph but, for providing anytime solutions to a continuously changing environment.

Figure 2: Problems solved by jumping mechanism. As the application is distributed, AntCO 2 is also distributed, possibly with an instance on each computing resource used by the application. Each instance of AntCO 2 has a set of ants and a sub-graph representing the part of the application it is serving. Across iterations ants are exchanged between AntCO 2 instances, information events are received from the application (node or edge creation/deletion, edge valuations, etc.). Events are also received from the computing environment (computing resources added or removed for example).

AntCO 2 architecture an implementation

At regular intervals, or when queryed by the application, AntCO 2 instances send migration advices to the application. A migration is advised, when an vertex color changes, therefore indicating that the corresponding entity in the application should be on another computing resource. The application is free to follow or ignore this advice according to specific information or constraint it has.

Several methods can be used to distribute AntCO for each edge do

Apply persistence factor ρ on pheromones τ (t-1) (eq. 4)

for each node do Search dominant pheromone color on all incident edges (eq. 5)

and color the node with it; Look at application and computing environment events arrived and modify the sub-graph and the ant population accordingly Send migration suggestions to the application end Algorithm 2: Application instance forever ...

Look at suggestions from AntCO 2 and migrate entities accordingly

Send measures, events and eventual migration decisions to AntCO 2 end

Here is an example of an usage scenario. We take a distribution architecture as depicted in figure 6, where each computing resource holds both a part of the application and an instance of AntCO 2 . To simplify explanations we will use only two computing resources, R 1 and R 2 .

The application starts its two instances on App 1 and App 2 (Figure 7). Two corresponding instances of AntCO 2 are created accordingly Ant 1 and Ant 2 . En- tities of the application start to appear on instance App 1 and notifies Ant 1 of this.

The color theses entities is therefore known directly. Identically, entities appear on App 2 .

Each time entities of App 1 interact one whith another, Ant 1 is notified and an edge is created between this entities. Several organizations may appear in the application, with entities more closely interacting with other entities of the organization than with other entities.

If an entity of App 1 in an organization interact with an entity of App 2 in an other organization, both Ant 1 and Ant 2 are notifyed. If this interaction becomes more an more important, the edge on both Ant 1 and Ant 2 will be notified and its importance will be updated. More an more ants will cross it. It is possible thant other links appear between these two organizations, leading to a colonization by ants of one color/computing resource of the two organizations. At this point a set of entities on one computing resource will be colored by the color identifying the other resource. This color change will indicate that these entities should be migrated. Indeed, they are in high interaction, they should then probably run on the same computing resource.

Identically an organization, running for example on R 1 , may be split in two since the the application notifies AntCO 2 that the importance of set of edge (in-teractions) inside the organization decrease, or disapear. If one part of this split organization has some weak relations with another organization on R 2 , it may be colonized by ants of R 2 and again, AntCO 2 will detect a color change and advice the application App 1 to migrate the entities on R 2 .

Experiments and results

Dynamic load balancing falls into the category of distributed time-varying problems. It seems difficult, unless impossible, to perform a comparison to optimal solutions on dynamic graphs, because of our incapacity to compute such optimal solutions. Indeed, suppose that we were able to divide the dynamic problem into a series of static statements. Finding an optimal solution for each static statement is by itself a difficult problem, but let us assume that it would be possible. It may happen that applying the optimal solutions for two consecutive steps is not optimal because of the amount of migrations entailed by the static choices. Moreover, the structures should be kept from one step to the next one.

A dynamic graph should take into account at once also inter-steps This is why the first part of the performance analysis is dedicated to the comparison of allocations computed by our method for some classes of static graphs with optimal allocations. The second part of the analysis focuses on the reactivity and on the adaptability of our algorithm for some relevant dynamic graphs.

Before entering into details, some performance measures are defined in the next section.

Quality analysis

As previously said, two measures are relevant for qualifying the quality of a dynamic load balancing:

• The global costs of communications;

• The load-balancing of the application.

They are antagonist. So, in order to evaluate our solution we first define two quality criteria r 1 and r 2 .

The first criterion r 1 ≥ 0 corresponds to the ratio of actual communications (see section 3.1) over the total number of communications occurring in the graph.

Solutions are better when r 1 is smaller.

r 1 = B(t)
w(u, v, t)

E(t) w(u, v, t)
The second criterion r 2 measures how the load is balanced among the available processing ressources, independently of the communications. For each color c, we have V c (t) the set of vertices having color c at time t. Then we have:

r 2 = min K max K where K = card(V c (t))
The load-balancing is better when r 2 is close to 1.

In case of static graphs, these criteria, enable us to store the best solutions obtained so far, that makes the method anytime.

Since we seek to find organizations, r 1 is considered to be a more important criterion. Indeed, it is explicitly defined in ant behavior, unlike r 2 that is implicitly optimized by competition mechanisms.

Dynamic Graphs

Here are two experiments we made with dynamic graphs. For these tests, we used program that simulate the application by creating a graph and then applying events to it. Events are the appearance or disappearance of an edge, a vertex or a processing resource, but also functions that change weights on edges.

The first dynamic graph represents a static grid above which another smaller grid moves. The smaller grid continuously connects and disconnects to the lower one as it moves. Typically this represents a small organization exploring a larger set of interacting entities (see figure 8) 2 .

The small graph keeps the same color along the experiment while it crosses different domains of the grid having a distinct color because communications in the small graph are stronger and communication with the larger graph are less durable. Therefore, the organization formed by the small graph is not perturbed by its interactions with the grid. This graph could represent an aquatic simulation application where a fish school passes in an environment. Interactions in the fish school are based on the fish vision area and are more important, and durable, inside the school than with the environment.

It must be noted that the dynamics of the graph helps creating correct clusters, indeed this is the dynamics, and the short durability of interactions between the he second graph is not dynamic in its topology, however, the application it represents is executed on a set of processors whose number varies. As said previously, there are several forms of dynamics and the dynamic of the computational environment must also be taken into account. The application entities are mapped as a grid (for example, many numerical physics simulations that use a mesh).

In figure 9, a 30 × 30 static grid is used, introducing new colonies, that is computing resources, at regular intervals every 1000 steps. We can compare this approach to a recursive bisection, but using a non power of two number of partitions. This test simulates a computing environment inside which more and more computing resources become available. The figure also shows the evolution of the two quality criteria r 1 and r 2 during this test. We can see that besides the small size of the grid that brings solutions at a lower rate at each new computing resource added, the algorithm stabilizes on good quality solutions.

It is interesting to notice that no global reorganization of the graph : organization are globally maintained in place when a new computing resource is added.

Indeed some areas are cut whereas the other parts stay in position therefore limiting the number of migrations.

The same test has been made on a quite larger graph containing 2851 vertices and 15093 edges (figure 10 that only shows the evolution of criteria r 1 and r 2 ).

The parameters used where : We compared the distribution found by AntCO 2 with the two other methods:

1. random, 2. and using a grid-like environment.

In random mode, as soon as a boid appear, a processor is assigned to it and it will never change afterward. In the simulations we used, the boid count is fixed once and for all, therefore this load balancing mode is at any time optimal.

Each processor is charged the same (depending on respective powers), however communication costs are not taken into account. Inside an organization there are chances that two communicating boids are on two distinct processors. This distribution mode is therefore the worst concerning the network load.

The grid-like environment cuts the space in rectangular cells, and each cell is assigned to a computing resource. Boids execute on the resource of the cell they cross. This mode improve communication minimization but degrades load balancing compared to the random mode. Indeed, with this mode, as boids travel without constraints, it is possible that all individuals migrate to the same grid cell, hence on the same processor. Moreover, concerning communications, it is possible that an organization stay on the frontier of two cells handled by two distinct processors hence forcing high communications to use the network.

These two methods have been compared to the results produced by AntCO 2 .

We see that this last one gives a good trade-off between load balancing and communication minimization. Concerning quality criterion r 1 , communications, results are better than the two other approaches. For r 2 , load balancing, AntCO 2 is better than the grid-like distribution mode. It cannot be better than the random distribution mode that is optimal when considering only load balancing.

Conclusion

In this paper we presented an colored ant algorithm allowing to detect and distribute dynamic organizations. The algorithm offers advices for entity migration in a distributed system taking care of the load and communication balancing.

We described a base colored algorithm, observed its behaviour with static and dynamic graphs and provided methods to handle them. Organizations emerge from the ant behavior. Such an emergence is not explicitly implemented. These organizations make up solutions, which is the reason why we don't need an objective function at the contrary of traditional ant systems [START_REF] Dorigo | The ant system: optimization by a colony of cooperating agents[END_REF].

We favor the r 1 criterion, communication minimisation, above the r 2 criterion, load balancing, since the algorithm searches for organizations. The r 1 criterion is explicitly defined in ant behavior whereas r 2 is only implicitly expressed Total pheromone quantity on edge e at time t.

Figure 1 :

 1 Figure 1: Example for which the best number of clusters is different of the number of processing resources.

Figure 3

 3 Figure3shows the AntCO 2 architecture. In this diagram AntCO 2 is seen both as a service inside a middleware and as a user of this middleware. The middleware allows communications between AntCO 2 and the distributed application, providing entity migration and communication measurement. It also serves as an interface to the computing environment providing event notification like the apparition or disappearance of resources. For the application, AntCO 2 is a service of the middleware that offers entity migration suggestions.

Figure 3 :

 3 Figure 3: AntCO 2 architecture.

2 as shown on figures 4, 5 and 6 .Algorithm 1 :

 561 The first figure depicts an environment where the application uses the whole cluster of computers for its own use, excepted on computer dedicated to AntCO 2 . The second figure shows the same architecture but with several computers for AntCO 2 . Finally, the last figure, shows a possible better distribution architecture, where each AntCO 2 instance would be located on the same computer as each application part it serves. Algorithm 1 show the ant behavior and ant environment evolution. Algorithm 2 shows the application interactions through the middleware with AntCO 2 . AntCO 2 instance forever for all ants do if the ant does not die (eq. 11) thenChoose the next vertex to visit according to pheromone level and edge weight (eq. 10)

Figure 4 :

 4 Figure 4: Distribution model, one computer dedicated to AntCO 2 .

Figure 5 :

 5 Figure 5: Distribution model, a set of computers dedicated to AntCO 2 .

Figure 6 :

 6 Figure 6: Distribution model, an AntCO 2 instance runs on all computers.

Figure 7 :

 7 Figure 7: Sequence diagram of AntCO 2 and an application running in parallel.

Figure 8 :

 8 Figure 8: A small organization browsing a larger set of interacting entities.

Figure 9 :Figure 10 :

 910 Figure 9: Adding a colony every 1000 steps in a 30 × 30 grid.

  Colored relation graph between entities of the simulation

Figure 11 :

 11 Figure 11: At the beginning of the simulation.

Figure 12 :

 12 Figure 12: Later on in the simulation.

Figure 13 :

 13 Figure 13: Comparison on criterion r 1 between distribution modes "random", "gridlike" and AntCO 2 with 200 boids.

Figures 13 and 14

 14 Figures 13 and 14 show the evolution of criteria r 1 and r 2 respectively on a test with 200 boids spread in 4 species during 5000 time steps. These figures compare the three distribution modes described above. For r 2 the random model, always optimal, is not shown.The parameters that where used for AntCO 2 are:

Figure 14 :

 14 Figure 14: Comparison on criterion r 2 between distribution modes "grid-like" and AntCO 2 with 200 boids.

  Ant count for vertex v. w (t) (e) ∈ N + Weight of edge e at time t. V(t) Set of vertex at time t. V c (t) Set of vertices having color c at time t. E(t) Set of edges at time t. E u (t) Set of edges adjacent to vertex u at time t. A(t) Set of actual communication edges at time t. Pheromone quantity of color c dropped by ant x on edge e during time interval ]t -1, t]. ∆ (t) (e, c) Pheromone quantity of color c dropped by all (c colored) ants on edge e during time interval ]t -1, t]. ∆ (t) (e) Pheromone quantity dropped by all ants on edge e during time interval ]t -1, t]. K Pheromone of color c rate on edge e at time t. τ (t) (e, c) Total pheromone quantity of color c on edge e at time t. τ (t) (e)

	6 Notations
	Notation	Signification
	G(t) = (V(t), E(t))	Dynamic communication graph at time t.
	G(t) = (V(t), E(t), C(t))	Dynamic colored communication graph at time t.
	u, v ∈ V(t)	Vertices.
	e = (u, v) ∈ E(t)	An undirected edge.
	c ∈ C(t)	A color.
	n ∈ N +	Vertex count.
	p ∈ N +	Colors / computing resource count.
	t ∈ N +	Time.
	x		Usually an ant.
	N (v) ∈ N
	C(t)	Set of colors at time t.
	B(t)	Edge-cut at time t.
	D(t)	Partition of G(t) at time t.
	D i (t)	Domain making up partition D(t).
	F(t)	Ant population at time t.
	F c (t)	Ant population having color c at time t.
	∆	(t)
		(t) c (e)

x (e, c)

PP. Grassé, in Insectes Sociaux, 6, (1959), p. 41-80, introduced this notion to describe termite building activity.

You can see a video of this experiment at the following URL http://litis. univ-lehavre.fr/~dutot/videos/MovingStruct2.avi.

by colored ant competition.

We develop actually an heuristic layer allowing to handle some constraints tied to the application, like entities that cannot migrate (e.g. bound to a database), but also information peculiar to the application. This work takes place within the context of aquatic ecosystem models [3],

where we are faced to a very large number of heterogeneous auto-organizing entities, from fluids representatives to living creatures presenting a peculiar behaviour.

Distributed simulations

Our algorithm is particularly suited for dynamic graphs. The relevance of our method lies in the incremental computation of the solution. A change in the input (the dynamic graph, the number of computing resources) can interrupt the computation at any time, it will continue from here to compute a new solution (as seen in the previous section).

Indeed, at the base component level, the dynamic graph is constantly being reconfigured. At the contrary, taken as a whole, long lasting organizations appear. They are the image of organizations appearing in the distributed application whose the graph is a representation. Such organizations often have a larger time to live than the average duration of edges or vertices of the graph. Inside these organizations, communication is higher both in terms of volume and connectivity.

And these two last points are criteria used by ants to form clusters.

We tested our algorithm on graphs deduced from an ecosystem simulation where entities have a boid-like behavior, made of three rules:

• avoidance: they try to stay at a small distance of perceived boids,

• cohesion: they try to fly toward the position of all perceived boids,

• alignment: they try to match velocity with perceived boids.

These rules create one or several groups of boids. Furthermore, boids try to avoid predators introduced in the simulation. Predators destroy some boids, and cut boids groups in sub-groups.

Each boid is modeled by a vertex in the dynamic graph. When a boids comes into the field of view of another this create an interaction (boids reacting to others in their field of view) and therefore an edge in the graph. Figures


Sofya Dymchenko
email: sofya.dymchenko@inria.fr

Bruno Raffin
email: bruno.raffin@inria.fr

Loss-driven sampling within hard-to-learn areas for simulation-based neural network training

This paper focuses on active learning methods for training neural networks from synthetic input samples that can be generated on-demand. This includes Physics Informed Neural Networks (PINNs), simulation-based inference, deep surrogates and deep reinforcement learning. An adaptive process observes the training progress and steers the data generation with the goal of speeding up and increasing the quality of training. We propose a novel adaptive sampling method that concentrates samples close to the areas showing high loss values. Compared to the state-ofthe-art R3 sampling our algorithm converges to a validation loss of 0.5 in 6000 iterations, while it takes 25000 iterations to reach a loss of 0.7 for the R3 algorithm when training a PINN with the Allen Cahn equation.

Introduction

The machine learning community has recently shown a growing interest in applying deep neural networks (DNN) to physical science [START_REF] Lavin | Simulation intelligence: Towards a new generation of scientific methods[END_REF]. The novel approaches take different perspectives on the subject [START_REF] Das | State-of-the-art review of design of experiments for physics-informed deep learning[END_REF]. Some design specific types of neural models and loss functions, such as graph-based networks [START_REF] Meyer | Deep surrogate for direct time fluid dynamics[END_REF], physics-informed neural networks (PINNs) [START_REF] Raissi | Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations[END_REF]. Others use DNNs to learn probability distributions for experimental design [START_REF] Foster | Deep adaptive design: Amortizing sequential bayesian experimental design[END_REF], probabilistic programming [START_REF] Baydin | Etalumis: Bringing probabilistic programming to scientific simulators at scale[END_REF], and simulation-based inference [START_REF] Cranmer | The frontier of simulation-based inference[END_REF]. Deep surrogates are combined with traditional numerical solvers and trained through different modalities on supercomputers as in [START_REF] Meyer | Simulation-based parallel training[END_REF], [START_REF] Brace | Coupling streaming AI and HPC ensembles to achieve 100-1000x faster biomolecular simulations[END_REF] and [START_REF] Ward | Colmena: Scalable machinelearning-based steering of ensemble simulations for high performance computing[END_REF]. In this paper we focus on adaptive sampling methods to optimize DNN training in the case where samples can be generated on-demand, usually through a solver code.

Classical DNN training methods work with fixed datasets that are repeatedly presented during training across multiple epochs. The ability to perform training using synthetic data, which can be generated on-demand, opens the way to different strategies to improve the training process. Synthetic data is generated from a set of input parameters sampled within a given bounded domain. The inputs can be directly used for DNN training without transformation as in data-free PINNs training, or be the initial conditions for autoregressive solvers, which produce data series. Adaptive sampling monitors training progress to guide the sampling process towards selecting the inputs that provide the most effective data. The associated computing cost should also be reduced so as not to slow down training.

The question of data selection and sample similarity originated in the context of training DNN with a finite dataset. It is tackled in various ways: measuring samples uncertainty by approximating training dynamics [START_REF] Kye | TiDAL: Learning training dynamics for active learning[END_REF], Wang et al., 2022], calculating samples influence [K and Søgaard, 2021], selecting representative subset with use of gradients [START_REF] Killamsetty | AUTOMATA : Gradient based data subset selection for compute-efficient hyper-parameter tuning[END_REF], Fayyaz et al., 2022, Katharopoulos and Fleuret, 2019].

Machine Learning and the Physical Sciences Workshop, NeurIPS 2023. For PINN's collocation set [START_REF] Yang | DMIS: Dynamic mesh-based importance sampling for training physics-informed neural networks[END_REF], Nabian et al., 2021] proposes re-weighting samples importance, [START_REF] Wu | A comprehensive study of nonadaptive and residual-based adaptive sampling for physics-informed neural networks[END_REF] creates a training subset based on a distribution calculated as a normalized loss. However, these methods usually require additional computations or are not applicable to non-finite data. The recently published R3 sampling [START_REF] Daw | Mitigating propagation failures in physics-informed neural networks using retain-resample-release (r3) sampling[END_REF] advances the baseline by retaining points whose loss is higher than average and resampling the remaining ones uniformly for each iteration. This way the DNN is able to learn better the points with high loss while exploring new ones. Relying on the per-sample loss to quantify the data training effectiveness has the benefit of being a lightweight single value, which requires no extra computation or excessive memory.

In this paper, we propose a method where the main objective is to increase the sampling density in areas with high loss over the lifetime of the training process. Instead of retaining high-loss points, we sample new points in their Gaussian neighbourhoods according to loss. To avoid overfitting in these areas, we introduce a balance control value that evolves across iterations. It defines a ratio between the proposed loss-driven sampling and uniform sampling, which enables the exploration of new high-informative areas and the repetition of already learned examples. The main contributions of the paper are:

• a loss-driven sampling method called Breed (Balance Ratio and EnhancE Density); • a concept of exploration-concentration balance control with ratio value; • a novel benchmark designed for evaluating sampling strategies for simulation-based training; • a comparison with the state-of-the-art R3 sampling on two tasks, which shows a significant performance improvement on both, the convergence speed and validation loss.

Proposed method

Let's first introduce notations. The sampling selects input points x ∈ X ⊆ R d . x can be used directly as a collocation point as for PINNs training, or go through a function f (x) = y, where y ∈ Y ⊆ R d is the output, the tuple (x, y) being used for training. The trained neural network is denoted f θ (x), where θ are neural network parameters. In the case of surrogate training, the goal is to have f θ approximate f .

The exploration-concentration balance control value

To balance a training set, we introduce a concentrate-explore value r (i) ∈ [0, 1] as a ratio of points to sample non-uniformly by concentrating in areas of high loss. The remaining points are sampled uniformly in the domain for (1) having examples for the network to remember what was learned and

(2) exploring areas with samples that might show high losses. The value r (i) changes over iterations i of the neural network, growing linearly from the starting value s r to the ending value e r for c r iterations and then is constant at value e r . The configuration of r value is called scenario and denoted as a triplet (s r , e r , c r ).

Gaussian neighbourhood sampling method

The sampling strategy is based on loss statistics from the neural network similar to [START_REF] Wu | A comprehensive study of nonadaptive and residual-based adaptive sampling for physics-informed neural networks[END_REF].

The loss is normalized to construct a distribution that will provide a number of points to sample within sample neighbourhoods.

The algorithm is repeated for N iterations. At each iteration i, the neural network f θ (i) (x) provides a loss value L(x

(i) j ; θ (i) ) = l (i) j ≥ 0 per sam- ple x (i) j ∈ S (i) for j = [N s ].
The values of vector l (i) then are sum normalized to have distribution properties. The categorical distribution over the samples of S (i) is constructed proportionally to the loss, i.e. P (x

(i) j ) = l ′(i)
j . This distribution trialed n times is a multinomial distribution P (n, l ′(i) ) . It models the number of points, called children, in the next training set to be sampled around each point, called parent, of the current training set. The sampling is run with replacements, so a parent with high loss will have several children while a parent with low loss might not have any. It allows us to adaptively refine sampling density in areas with high loss. The name of the algorithm, Breed, self-explains this mechanic of breeding the most interesting points from the point of view of the training process.

The next training set S (i+1) consists of two sets. The concentration set S (i+1) c is a set of points sampled in a loss-driven manner. Its size depends on r (i) value, i.e.

|S (i+1) c | = N (i) c = ⌊N s × r (i) ⌋.
To construct it, the number of children for each parent is sampled as {m j } j=[Ns] ∼ P (N

(i) c , l ′(i) ). Note that j=[Ns] m j = N (i)
c . A parent point acts as the centre of a Gaussian with Σ width, which we call a neighbourhood. We sample the children set from each neighbourhood, i.e.:

S (i+1) c = j=[Ns] C Σ (x (i) j ) = j=[Ns] x (i+1) k ∼ N (x (i) j , Σ), k = [m j ] .
(1)

The uniform set S (i+1) u is a remaining portion of points, i.e.

|S (i+1) u | = N (i) u = N s -N (i)
c , sampled uniformly to explore new data and to keep the presence of points with low loss as well, i.e.:

S (i+1) u = x (i+1) k ∼ U(X ), k = [N (i) u ] . (2)
Finally, the composed training set is

S (i+1) := S (i+1) c ∪ S (i+1) u
.

Experiments

We compare1 Breed sampling to the baseline uniform dynamic sampling, which creates a training set for each iteration by selecting N s uniformly distributed points in X , and the R3 sampling [START_REF] Daw | Mitigating propagation failures in physics-informed neural networks using retain-resample-release (r3) sampling[END_REF] on two benchmark problems. The simulation is a gradient descent on a surface made of "bell pits" configured by the number, centres, weights, and widths of the bells (negative Gaussians curves). The input is a point x 0 ∈ X ⊂ R 2 and the output is the local minimum x f ∈ Y = X ⊂ R 2 corresponding to the starting point of the gradient descent. The task can be extended to a time-dependent variant and/or 3-dimensional variant with boundary conditions being a surface equation.

The motivation to create this benchmark was to have flexibility in configuring different cases and an obvious visual clue about hard-to-learn areas, which are those with near-zero gradients.

The case we consider in experiments is a surface with two pits located at points (-0.5, -0.5) and

(1.5, 1.5) in the domain X × Y = [-2, 2] 2 , with corresponding weights (0.895, 0.005), and widths (0.4, 0.008). Because the widths and weights are extremely different, this configuration is referred to as two imbalanced pits (IPGD), see Figure 1. The validation is done on two sets: the first one consists of 10k points uniformly sampled in the domain, and the second, hard validation set, consists of 10k points whose gradients are less than 4 • 10 -3 . For a fair comparison, we designed a neural network with hyperparameters optimized for the best results with uniform sampling. The model is a 4-layered perceptron, Adam optimizer with a learning rate 10 -3 scheduled by plateau scheduler with patience 5, weight decay 5 • 10 -5 , and a Huber loss function. The maximum number of iterations is N = 100 and the number of samples is N s = 1000. The r scenario is (0.15, 0.7, 25), the width of neighborhoods is σ = 0.005.

The second benchmark is a PINN trained to solve the classical Allen Cahn partial differential equation. This benchmark is used in [START_REF] Daw | Mitigating propagation failures in physics-informed neural networks using retain-resample-release (r3) sampling[END_REF]. The model we use here has the exact same architecture and hyperparameters, and others are as follows: N = 60k, N s = 1000, r scenario is (0.15, 0.7, 5000), σ = 0.001. Results analysis. Results are presented in Figure 2 as errors over training iterations. For all experiments, Breed shows both faster convergence and lower errors compared to Uniform and R3 sampling. Notice that for Breed the error decrease happens near the c r iteration, showing the importance of the exploration-concentration r scheme. In Figure 2a, R3 sampling performs worse than the baseline for both validation sets, while Breed reaches twice lower error than the baseline even for the hard validation set. In Figure 2b, the variation of error for R3 is explained by the instability of the method visible in Figure 2c. R3 converged for 3 out of the 5 trainings to the same error value. In opposite, Breed shows a stable convergence for all runs, while the uniform sampling converges only for 1 run.

Conclusion

We presented Breed, a novel adaptive sampling algorithm for training DNNs with synthetic data. Breed relies on the per-sample loss value to identify hard-to-train areas and combines a dual exploration-concentration scheme with Uniform sampling to discover potential hard areas and to remember trivial ones and Gaussian multinomial sampling to focus on hard areas. The experiments demonstrate overall better performance in quality, convergence speed, and stability compared to the baseline uniform and the state-of-the-art R3 sampling. Future work will focus on validating Breed with more benchmarks, including higher dimension problems and simulation-based scenarios with functions generating time series.

  i.e. i = [N ], where we denote [N ] = 0, . . . , N -1. The covariance Σ = I d • σ defines the radius of the spherical neighbourhood (fixed). The values r (i) ∈ [0, 1] to control concentrate-explore trade-off ratio are predefined (subsection 2.1). The initial training set S (0) is sampled uniformly and the number of samples |S (i) | = N s is fixed.

Figure 1 :

 1 Figure 1: IPGD surface Benchmarks. The first problem is a new simulation-based benchmark called pits gradient descent (PGD).The simulation is a gradient descent on a surface made of "bell pits" configured by the number, centres, weights, and widths of the bells (negative Gaussians curves). The input is a point x 0 ∈ X ⊂ R 2 and the output is the local minimum x f ∈ Y = X ⊂ R 2 corresponding to the starting point of the gradient descent. The task can be extended to a time-dependent variant and/or 3-dimensional variant with boundary conditions being a surface equation. The motivation to create this benchmark was to have flexibility in configuring different cases and an obvious visual clue about hard-to-learn areas, which are those with near-zero gradients.

Figure 2 :

 2 Figure 2: Comparison of validation errors over training iterations for Breed, R3 and uniform sampling for (a) Imbalanced Pits Gradient Descent and (b-c) Allen Cahn PINN. The plots (a-b) are presented as mean and standard deviation computed over 5 random seeds, whereas in the plot (c) each line represents one run.

https://gitlab.inria.fr/breed/breed/

Acknowledgements

This work has been supported by the ENGAGE Inria-DFKI project.


Ada Czesnakowska

Gerald Ledru

Benoit Glorieux

Georges Zissis

Thermal Analysis of Blue Laser Diode for Solid State Lighting Application

Keywords: Laser Diode, Solid State Lighting, YAG, FEM, Thermal Analysis

Solid-state light sources based on laser diode are becoming great alternative for LEDs. Improvement of the thermal characteristics of InGaN LD is very important for realizing reliable devices. In this investigation the influence of the temperature of diode on light parameters was studied. White light was obtained by coupling blue light of diode with yellow phosphors: YAG:Ce 3+ and GYAG:Ce 3+ with nitride. For three values of the temperature of LD's stem, regulated by Peltier module, CCT, CRI and chromaticity coordinates were measured by spectroradiometer. The importance of emission characteristics of materials was shown. Subsequently, the influence of temperature on laser diode intensity was investigated for 120 hours. This experiment was repeated for different levels of current and temperature. Finally, the steady state of thermal finite element analysis was performed to reveal the distribution of the temperature. The analysis showed the importance of heat sink and also temperature control.

Introduction

In past few years InGaN-based semiconductors have attracted much attention for application in solid-state light sources. Recently, their usage is constantly increasing in worldwide market. High-brightness white LEDs have been used due to their size, long life and energy saving. Also, white light can be generated from LEDs in three major ways: mixing blue, red and green diode [START_REF] Muthu | Red, Green and Blue Leds for White Light Illumination[END_REF] [START_REF] Sato | Full-Color Fluorescent Display Devices Using a Near-uv Light-Emitting Diode[END_REF], coupling UV diode with RGB phosphor [START_REF] Nakamura | The Blue Laser Diode: The Complete Story[END_REF] or coupling blue diode with yellow phosphor [START_REF] Yang | Essential Factor for Determining Optical Output of Phosphor-Converted LEDs[END_REF]. The last method is the most convenient and efficient to generate white light A. Czesnakowska and it has been commonly adapted in white LEDs.

Unfortunately, LEDs used in these devices suffer a loss in external quantum efficiency as operating current increases, known as a droop. This may lead to shift in a peak emission wavelength and broadening of the emission spectrum.

Variations of spectrum of LED and phosphor change the ratio of the light emitted by each component, resulting in shift in the color coordinates of the emitted light and decrease in overall device efficiency [START_REF] Czesnakowska | Effect of Different Phosphor Properties for White Light Generation Using a Blue Laser Diode[END_REF].

An alternative to light-emitting diodes for obtaining white light can be blue laser diode (LD). In contrast to LEDs, they do not exhibit efficiency loss. The output power and external quantum efficiency of laser diode increase linearly with current and maintains color stability of laser emission. Additionally, laser-based devices can be operated in reflection mode, allowing for the phosphor to be placed on a reflection substrate that may also act as a heat sink to effectively dissipate heat away from the phosphor.

Common problem of SSL based on semiconductors is their heating [START_REF] Wen | Identification of Degradation Mechanisms Based on Thermal Characteristic of InGaN/GaN Laser Diode[END_REF] [7] [START_REF] Uddin | Study of Degradation Mechanism of Blue Light Emitting Diodes[END_REF],

when the current increases. It doesn't concern only lighting domain, but also data storage or communication, when coupling of laser and phosphor is used [START_REF] Retamal | 4-Gbit/s Visible Light Communication Link Based on 16-QAM OFDM Transmission over Remote Phosphor-Film Converted White Light by Using a Blue Laser Diode[END_REF] [10]. To avoid the diode degradation caused by heat and to assure long-life, the cooling module is required. In our investigation we verified the influence of the temperature augmentation of the laser diode on parameters of the light generated by coupling the laser diode and phosphor. We also studied the distribution of the temperature in the laser diode by using FEM (Finite Element Method) analysis.

Temperature Augmentation

Experimental Setup

The white light was generated by coupling blue laser diode and two different types of materials. For the production of the materials a two-part high optical transparency silicon was used as a matrix. Silicon was filled in with different powders to obtain two types of material: YAG:Ce 3+ (NYAG4354 Intematix) powder and mixture of green GYAG:Ce 3+ (GYAG3856-01-13 Intematix) and nitride in ratio 4.5:1. Phosphors were incorporated into silicon plate of diameter 10 mm and thickness of 1mm. The materials were prepared in ICMCB laboratory in Bordeaux, France. As an excitation source the InGaN blue laser diode OSRAM TB450B 450 nm was used. Laser was thermally coupled with a Peltier module, which was connected to PID temperature controller TEC 2000 from Thor Labs. A sensor AD590 was placed under a stem of the laser to measure the temperature. The measurements were performed in an optical sphere (Figure 1), where as an output the spectroradiometer SpecBos 1201 was put. In front of spectrometer we placed a phosphor plate. This let us to keep a phosphor in a distance from a diode, to avoid heating of material. The diode with its module was put as an input of the sphere. and chromaticity coordinates. The temperature of LD was fixed at three different levels: first at 25˚C, then at 45˚C and finally 55˚C. For each, we measured firstly the spectrum of the LD itself, and then the spectrum of laser's light converted by the phosphor and its parameters.

Results

Below, on Figure 2, the spectrum of blue LD for different diode's temperatures was presented. When the temperature increases, the shift into higher wavelengths can be observed. Moreover, when reaching the 55˚C, the intensity of the light decreases about 30%. This shift obviously has influence on the emission of the material (Figure 3 and Figure 4). The graphs were normalized to peak of laser emission in order to present the amount of converted light by the phosphor. On Figure 3 the intensity of converted light increase proportionally to the temperature, but this augmentation is not significant. In contrary, on Figure 4, it can be found that converted light decreased by 50%, only after changing the temperature by 15˚. This variation is connected to the characteristics of light emission by materials. The optimal emission for YAG can be found at level of 442 nm (Figure 5) and for GYAG: 437 nm (Figure 6). GYAG was mixed with nitride, so its emission needs also be taken into consideration (Figure 7).

If the emission of converted light drops, at the output of our light source we find more blue light. It is caused by the drop of the efficiency of the phosphor emission. In emission characteristics we are not anymore at the maximum, which means that more blue light passes through plate. Rise of blue color can cause perturbation of human circadian rhythm [START_REF] Vitaterna | Overview of Circadian Rhythms[END_REF], which can be dangerous to health.

The color rendering index (CRI) of light source defines the ability of the source to render the true colors of an object [START_REF] Chhajed | Influence of Junction Temperature on Chromaticity and Color-Rendering Properties of Trichromatic White-Light Source Based on Light-Emitting Diodes[END_REF]. The maximum value is 100, which implies the best possible color rendition. The down-conversion method of obtaining white light has an advantage of a high CRI due to the broad emission spectrum of a phosphor [START_REF] Uddin | Study of Degradation Mechanism of Blue Light Emitting Diodes[END_REF]. Based on the results presented in Since the efficiency of converted material changed, CCT and chromaticity coordinates should be affected. In Table 2 we present CCT values obtained and measured by SpecBos spectrometer. On Figure 8 the chromaticity coordinates were presented.

Emission by YAG:Ce 3+ does not change radically. The small shift into green can be noticed. In contrary, the shift into blue is clearly seen on the figure above for GYAG:Ce 3+ , which is caused by drop of the emission efficiency.

Variation of the diode temperature not only has an influence on light parameters. Operating on high value of temperature can lead to reduction of life duration of semiconductor. To obtain a long lifetime of a laser, appropriate cooling is required. The important factor to prolong diode operation is junction temperature not exceeding 100˚C. In our study, we investigated the temperature distribution of the operating diode by performing Finite Element Method Analysis.

FEM Analysis

The Laplace heat equation was numerically solved for this thermal analysis [START_REF] Feng | Thermal Analysis of GaN Laser Diodes in a Package Structure[END_REF].

For steady state approach the solution is independent from density and specific heat. All the external surfaces were in heat convection with the air. The ambient temperature was fixed at 25˚C. In semiconductor the heat generation is located in active layer and p-cladding layer. In our simulation we defined active layer and p-cladding layer as "heat generators". The value of heat generation was calculated based on lumped element model:

c Q IV = ( 2
)
I WLJ = (3) l h J V σ = ( 4
)
where Q c is the heat generation, V the voltage drop, J the density of current, W the stripe width, L the cavity length, h the high of the layer, σ the electrical conductivity.

Below, the model designed in FEM software is presented (Figure 9). Chip is mounted on AlNsubmount in a TO 56 package. Submount is attached to heat sink.

Based on thermal conductivity of each material [START_REF] Wen | Identification of Degradation Mechanisms Based on Thermal Characteristic of InGaN/GaN Laser Diode[END_REF], the distribution of the temperature was simulated. The conditions of simulation on Figure 10 represent case without any radiator or cooling module of a laser diode.

The maximum temperature reached on the chip and substrate was 190.15˚C, which exceed the recommended operating junction temperature almost twice.

A. The heat dissipation for a packaged semiconductor is mainly by conduction. From the heat source, through the substrate, finally to heat sink. Heat can be also removed by convection via a gas, as in surrounding air. Although effective heat transfers from source to ambient is an aim, it is more usual to define heat dissipation by considering inverse of the heat flow-thermal resistance between these two points. It is calculated by equation:

th total T R Q ∆ = ( 5
)
where ΔT is a difference of the temperature between junction and ambient, Q total is a total heat generation. Calculated R th was 46 K/W. However, the thermal resistance value calculated by this equation is a lumped value and will differ from depending on the special distribution of the heat source. Subsequently, we simulated the conditions, where we fixed our temperature of stem on 25˚C, and then 55˚C respectively, which represents thermal coupling with Peltier module.

Figure 11 and Figure 12 show, that fixing proper temperature on stem, by using cooling module and temperature controller let us not exceed the maximum of junction temperature equal to 100˚C. Comparing results of simulation without temperature control, to the one, where the control was used, it is noticed that stem reaches almost 140˚C. Considering, that heat flow is directed toward the heat sink, the temperature of the stem should be lower. The result suggests that the parameters of stem material need to be optimized.

The thermal resistance, while connected thermally to the copper plate, results in the lower value of 15.5 K/W (Equation ( 5)).Studies show [START_REF]Thermal Analysis of GaN Laser Diodes[END_REF] [15], that decreasing the connected area at the bottom of the stem will increase in thermal resistance. Also, connecting a diode from lateral surface is enough to keep thermal resistance low. No connection, or connections only to pins lead to even three times increase of this value (46 K/W).

Conclusions

The dependency of the temperature on the emission of a laser, which results in variation of light parameters, when used as excitation source in down converted phosphor method was investigated.

To study the influence of this changing on white light parameters, the phosphors absorption and emission characteristics were performed. Investigation shows that shift of wavelength, which is a result of temperature rise has an influence on light parameter. In case of our blue laser diode coupled with YAG:Ce 3+ , it came out that more optimal results, closer to "daylight" parameters, are achieved when the shift to higher wavelengths appeared. On the other hand-when the laser was coupled with GYAG:Ce 3+ , we observed deterioration of the results. This part of studies showed the importance of keeping the temperature of diode on a constant level and finding an optimum of light conversion by phosphor.

From thermal analysis in FEM software we found out, that operating without cooling system leads to exceeding the junction temperature almost two times.

Also, the studies show, that the material of stem in used laser diode could be optimized. We calculated the value of thermal resistance between heat generator and air for conditions with and without cooling module. Investigation proves, that without appropriate cooling module, the value of thermal resistance can increase even three times, which leads to fast diode degradation.

Figure 1 .

 1 Figure1. Measurement Setup. Blue laser diode in Peltier module as an input, produces the light that passes by phosphor. The plate of phoshor is placed as an output of sphere, just in front of spectro-radiometer, to avoid heating from the laser itself.

Figure 2 .

 2 Figure 2. Spectrum of blue laser diode for different temperature.

Figure 3 .

 3 Figure 3. Spectrum of converted light by YAG for different temperature.

Figure 4 .

 4 Figure 4. Spectrum of converted light by GYAG for different temperature.

  ] radiant flux [W/sr*m -2

Figure 8 .

 8 Figure 8. Chromaticity coordinates changing for YAG:Ce 3+ and GYAG:Ce 3+ with nitride.

Figure 9 .

 9 Figure 9. Model of a laser diode for simulation purposes.

Figure 10 .

 10 Figure 10. Distribution of temperature without external cooling module.

Figure 11 .

 11 Figure 11. Distribution of temperature for fixed 25˚C on stem.

Figure 12 .

 12 Figure 12. Distribution of temperature for fixed 55˚C on stem.

  et al.

DOI: 10.4236/opj.2018.83005 41 Optics and Photonics Journal

Table 1

 1

	Phosphor
	Optical Sphere	SpecBos 1201
	LD coupled
	with Peltier

we can say that changings in emission spectrum do not influence on CRI parameter. DOI: 10.4236/opj.2018.83005 43 Optics and Photonics Journal

Table 1 .

 1 Color rendering index.

	25°C
	40°C
	55°C

DOI: 10.4236/opj.2018.83005 45 Optics and Photonics Journal

Table 2 .

 2 Correlated color temperature.

	Temperature	YAG:Ce 3+	GYAG:Ce 3+ with nitride
	25˚C	6653	3927
	40˚C	6354	4974
	55˚C	6254	4974

Czesnakowska et al. DOI: 10.4236/opj.2018.83005 46 Optics and Photonics Journal