Ben Rabie

Pierre Atitallah

Arnaud Boulet

Jean-Luc Cuccuru

Antoine Dekeyser

Ouassila Honoré

Sébastien Labbani

Philippe Le Beux

Eric Marquet

Julien Piel

Taillard

Rabie Ben

Atitallah -Pierre Boulet -Arnaud

Cuccuru -Jean-Luc Dekeyser

Antoine Honoré -Ouassila

Labbani -Sébastien Le

Beux -Philippe Marquet

Éric Piel - Julien

Taillard -Huafeng Yu

Éric Marquet

Huafeng Taillard

Yu

Gaspard2 UML profile documentation

Keywords: Gaspard, UML, profile, system-on-chip, parallelism, data-parallelism, co-modeling Documentation du profil UML Gaspard2 Gaspard, UML, profil, système-sur-puce, parallélisme, parallélisme de données, comodélisation

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

This document describes the current UML2 profile of Gaspard2 [4]. This profile extends the UML2 semantics [3] to allow the user to describe a SoC (System-on-Chip) in three steps: the application (behavior of the Soc), the hardware architecture, and the association of the application to the hardware architecture. This is a refinement of the profile presented previously in the thesis of Arnaud Cuccuru [START_REF] Cuccuru | Modélisation unifiée des aspects répétitifs dans la conception conjointe logicielle/matérielle des systèmes sur puce à hautes performances[END_REF].

Chapter by chapter, the packages of the profile are presented.

Chapter 1

Packages overview 1.1 Overview

Description

Here is a short description of the seven packages that compose the Gaspard2 profile. Each one will be explained in details in the following chapters.

multiDimMultiplicity

The multiDimMultiplicity package introduces the concept of multi-dimensional multiplicity explained in [START_REF] Cuccuru | Modélisation unifiée des aspects répétitifs dans la conception conjointe logicielle/matérielle des systèmes sur puce à hautes performances[END_REF]. This is an extension of the UML2 multiplicity attribute of the metaclass MultiplicityElement.

In place of just putting one integer, we insert a vector of integers that gives the size of each dimension. This package is not directly written in the profile because we use the multiplicity of UML2 as a string value to simplify Gaspard2 models writing.

component

The component package gives the basis of Gaspard2 component behaviour and their interconnections. This package introduces the elementary component (view as a black box), the hierarchical component and the repetitive component. UML2 metaclasses are specialized and rules are given. Most of Gaspard2 elements are based on the UML2 Component metaclass with its ports.

factorization

The factorization package represents Array-OL concepts that perform array computing and model factorization.

hardwareArchitecture

This package contains all the components that describe a hardware architecture in Gaspard2. According to the factorization package, the hardwareArchitecture package allows powerful and compact modeling of regular and repetitive architectures, such as a multiprocessor architecture. This package is still under development.

application

The application package allows the expression of intensive signal processing tasks, and powerful expressions of data dependences between tasks.

control

The control package introduces the concept of automaton in Gaspard2. For now, it is only used with application components.

association

The association package defines relations between application and hardware components. In particular, it allows to specify the way to associate data and task components with hardware components.

Chapter 2

Package Component

Overview

The Component package provides some basic extensions to the UML2 component model. It also provides strong guidelines and shortcuts in order to make it more user friendly to handle:

• Systematic identification of interaction points trough the definition of ports,

• Components internal structure descriptions through the use of composite structure diagrams,

• Systematic use of delegation connectors to relate the externally visible boundary of a component to its internal parts,

• Simplification of the ports typing mechanism, with an explicit direction information.

• A specific parameter model, more suited to our needs than the classical UML template mechanism.

The extensions are displayed on Figure 2.1. The main extension introduced is the GaspardComponent abstract stereotype. It does not carry any particular semantics, but only provides a context for the definition of common mechanisms and constraints related to the Gaspard component model. This stereotype will be refined in the application and hardwareArchitecture packages. The GaspardPort abstract stereotype (and its In, Out refinements) is introduced to simplify the way to type ports, and specify its direction. We will see in the corresponding sections that there is a systematic way to translate models expressed with this "syntaxic sugar" to more academic UML models. Finally, the Parameter stereotype is introduced to provide a more flexible way to define parameterized components than the classical UML template mechanism.

The name of every component in a Gaspard model must conform to the UML convention, that is begin with an uppercase letter (english only) and then any alpha-numerical character. This is mainly to facilitate the transformation of name into conformant names in the transformation target languages.

Description

GaspardComponent

The GaspardComponent stereotype is the main extension introduced in this package. It is abstract and does not carry any particular semantics, but only provides a context for the definition of common mechanisms and constraints related to the Gaspard component model. All Gaspard models (either Application or Hardware Architecture models) are component based.

This stereotype applies to the UML2 Component metaclass. The introduction of this stereotype enables to specify clear construction rules and ways of using UML components to make them Gaspard RT n°0342 INRIA compatible. Among this constraint, the Gaspard component model imposes a systematic use of ports as interaction points. It means that all connections expressed between components (or more precisely between parts typed by components) will be done through their ports. Moreover, every GaspardComponent is potentially hierarchical (except for the ElementaryComponent refinement), and the Gaspard component model imposes that the topology of the internal structure is specified in an unambiguous way: the description of the internal structure of a component must be done through the use of composite structure diagrams. Finally, the internal parts of a component must be explicitly related to the ports on the boundary of the containing component. This implies the systematic use of delegation connectors expressed between the ports of the concerned internal parts, and the ports on the boundary of the containing component.

Note that this stereotype is abstract, and can not be applied directly. This stereotype will be refined in the application and hardwareArchitecture packages.

Extension

This stereotype applies to the Component metaclass.

Attributes

No additional attributes are defined for this stereotype.

Constraints

• A Component stereotyped GaspardComponent can only contain parts typed by a Component stereotyped GaspardComponent. This is expressed by this OCL constraint: inv: self.part->exists(p|p.stereotype->exists(name='GaspardComponent'))

• A Component stereotyped GaspardComponent can only have ports stereotyped GaspardPort. This is expressed by this OCL constraint: inv: self.OwnedPort.stereotype->forAll(name='GaspardPort')

• Connections between parts of a Component stereotyped GaspardComponent can only be expressed between their ports.

• When connections are expressed between ports, the ports should have compatible types.

• When connections are expressed between ports, then one of the port should be an In, and the other an Out.

• When delegation connections are expressed between ports on the boundary of the Component and parts contained in its structure, the source and target ports should have the same direction.

MainInstance

This stereotype generalizes the InstanceSpecification metaclass. It is applied to an instance of component which is the root of the application or the architecture. This allows to indicate which is the starting point of execution of an application or the container of an architecture. This instance does not have any port.

Generalization

This stereotype applies to the InstanceSpecification metaclass.

RT n°0342

Constraints

One and only one InstanceSpecification must be specified for the application in a model, as well as for the architecture.

ElementaryComponent

This stereotype extends the GaspardComponent stereotype. It is applied to a component which is seen as black box. It means concretely that this component does not have an internal structure description, or at least that the internal structure description will not be specified in the UML model. During the deployment, an "implementation" will have to be associated for Gaspard to be able to implement the model.

Generalization

This stereotype extends the GaspardComponent stereotype.

Attributes

No additional attributes are defined for this stereotype.

Constraints

A component stereotyped ElementaryComponent does not have any internal structure. This is expressed by the following OCL constraint: inv: self.part->select(stereotype->exists(name='GaspardComponent'))->size()=0

GaspardPort

The GaspardPort abstract stereotype applies to the Port metaclass. It is introduced to simplify the way to type ports, and specify their direction. In classical UML models, ports own provided and required interfaces, specifying the interactions that can occur between these ports and the environment of the component. These interactions are basically message oriented, though the emission/reception of operation calls or signals. The provided and required interfaces of a port describe these potential interactions. A required interface is usually seen as the set of services a component may require to its environment, whereas a provided interface represents the set of services a component is supposed to provide to its environment.

This message passing direction is not suited to the scope of Gaspard models (either application or hardware architecture), which are more data oriented. With the GaspardPort concept, we propose to avoid the use of interfaces. The type of data transmitted through a port is directly defined through the type property of the Port metaclass. This type must be defined in UML as a DataType (of UML). The multiplicity of the port specifies the shape of the arrays which pass though it. The direction of the port is explicitly specified via the use of the several refinements of GaspardPort (i.e. In, Out).

Note that this mechanism is only a "syntaxic" sugar. The same semantic could be obtained using interfaces carrying only one signal (with one parameter typed by the type of the transmitted data). The direction would be specified by the way the interface is related to the port: Required for an Out semantics (the component is able to emit signals to its environment through this port), Provided for an In semantics (the component is able to receive signals from its environment through this port).

Note also that this stereotype is abstract, and can not be applied directly. When a port on a GaspardComponenent is not stereotyped, it gets the default meaning that data might flow in either direction. This semantic is not meaningful, and therefore forbidden, on an ApplicationComponent. However, on a HardwareComponent, this can be to express the fact the a same connection can be used either to send or receive data.

Generalization

This stereotype applies to the Port metaclass.

Attributes

No additional attributes defined.

Constraints

• When connections are expressed between ports, the ports should have compatible types.

• When connections are expressed between ports, then one of the port should be an In, and the other an Out.

• When delegation connections are expressed between ports on the boundary of the Component and parts contained in its structure, the source and target ports should have the same direction.

Out

The Out stereotype extends the GaspardPort stereotype. It only specifies that the Gaspard port is an Out port. An ApplicationComponent with such a port will send one array of data which after each iteration through this port. Such a port on a HardwareComponent means that on the connection linked to this port, the component will always be an "initiator", that is will always start any transmition.

Generalization

This stereotype extends the GaspardPort stereotype.

Attributes

No additional attributes defined.

Constraints

No additional constraints defined.

In

The In stereotype extends the GaspardPort stereotype. It only specifies that the Gaspard port is an In port. An ApplicationComponent with such a port will not be run until data has been received on this port. Such a port on a HardwareComponent means that on the connection linked to this port, the component will always be a "target", that is will never initiate any transmition.

Generalization

This stereotype extends the GaspardPort stereotype.

Attributes

No additional attributes defined.

RT n°0342

Constraints

No additional constraints defined.

INRIA

Chapter 3

Package Factorization

Overview

Description

This package introduces mechanisms that enable to express in a compact way the topologies of relations expressed between multi-dimensional arrays of connectable elements. In this section, these mechanisms are introduced in a generic way. The defined extension set will be concretely used in the application, hardware architecture and association packages, where a particular semantic or interpretation will be given to them.

To see a collection of elements (i.e. an element with a multiplicity, called a MultiplicityElement in the UML2 specification) as a multidimensionnal array of elements, we introduce the Shaped stereotype, which enables to specify the shape (i.e. number of dimensions and size of each dimension) of the collection represented by the multiplicity of the element. In our proposal, this stereotype is concretely used with parts and ports.

A set of extensions is then introduced to enable a compact and non ambiguous specification of the topology of the relations between multidimensionnal arrays of elements. These extensions are based on the LinkTopology abstract stereotype. We basically differentiate two use cases (providing two refinements of the LinkTopology): Relations expressed between elements inside of two separate arrays (Reshape and Tiler), and relations expressed between elements inside of the same array (InterRepetition).

The first set of extensions is basically inspired by the Array-OL data parallel language, and concerns a relation expressed between elements contained in two separate arrays. The mechanism relies on a vector based formalisms, that enable to identify patterns of elements inside of each of the arrays (that we will call source and target pattern to ease explanations), and establish unambiguously relations between elements of a source pattern and elements of a corresponding target patterns. This mechanism will be described in the corresponding sections. The main difference between Reshape and Tiler is that Tiler is used only with delegation connectors (i.e. connectors expressed between ports on the boundary of a component, and ports of its internal parts), and can be seen as a Reshape partially specified (i.e. the remaining information could be deduced).

The second set of extensions enables to express relations between elements inside of the same multidimensional array, also using a vector based formalism, through the InterRepetition stereotype. For example, this mechanism enables to express a grid of elements, where each element is connected to neighbours located at south, north, east and west position. Several additional stereotypes (based on the DefaultLink abstract stereotype) are introduced to specify how the default mechanism behaves on the boundaries of the multidimensional array. For example, in the previously introduced grid example, the connections to elements located at north does not exist. The default links enables to specify the connections to take into account in this context.

Shaped

The multiplicity concept of UML enables to give directives concerning the instantiation of the element it is attached to. These directives concern the number of elements that can potentially be instantiated.

The multiplicity concept is familiar to UML users. It is defined as an inclusive interval of positive integer values, starting with a lower bound and ending with an upper bound. It defines the set of valid cardinalities for the element it is attached to. In UML, an element with a multiplicity can be seen as monodimensionnal array of elements (in the case where the isOrdered property of the MultiplicityElement is equal to TRUE).

The Shaped stereotype we introduce enables to provide a multidimensionnal view of this collection. The shape : String tagged value enables to specify the shape of this collection (i.e. number of dimensions and size of each dimension). The String value of the shape tag represents a vector of positive integer values, where the number of elements determines the number of dimensions of the array, and where each integer value determines the size of the corresponding dimension.

We allow users of the profile to specify a value only for the shape tag of a Shaped MultiplicityElement, without specifying a value for the multiplicity property of the MultiplicityElement. If both are specified, then the product of the elements of the shape vector must be equal to the value of the multiplicity property.

Note that the use of this stereotype is optional. We allow users of the profile to directly use the multiplicity property of the MultiplicityElement metaclass to specify the shape of the collection.

Generalization

This stereotype applies to the MultiplicityElement metaclass.

Attributes

• +shape: String, a string representing a vector specifying the shape of the collection.

Constraints

• The vector represented by the shape tag cannot be empty. This constraint can not be expressed in OCL.

• If both a vector is specified for the shape tag and a value is specified for the multiplicity property, the product of the elements of the vector must be equal to the value of the upper bound of the multiplicity. This constraint can not be expressed in OCL.

Optional notation

We allow users to directly specify the shape of a collection using the multiplicity property of the MultiplicityElement, without using the Shaped stereotype.

LinkTopology

In order to take into account modeling of link topologies, we introduce the LinkTopology abstract stereotype. LinkTopology is an optional set of information that can be associated to a connector, between Shaped parts and ports. The LinkTopology does not carry any particular semantics. Semantics will be specified in the context of its three refinements: Reshape, Tiler and InterRepetition. The modulo tagged value is common to the three refinements, and a particular interpretation will be given for this tag according to each refinement. Note that this stereotype is abstract, and can not be applied directly.

Generalization

This stereotype applies to the Connector metaclass. This stereotype is abstract.

Attributes

• +modulo: Boolean = false, a common property for each of the refinements of the LinkTopology stereotype. A particular interpretation will be given for each of the refinement.

Constraints

No additional constraints.

Tiler

The Tiler stereotype extends the LinkTopology abstract stereotype. As a consequence it applies to the Connector metaclass. It also applies to the ConnectorEnd metaclass, in order to use it with Reshape connectors, as illustrated in the next section.

The Tiler stereotype can be applied directly to connectors only if the connectors are "delegation" connectors, i.e. the connectors relate ports on the boundary of component, and port of an internal part. See section 3.3.1 for more details.

A Tiler is always associated to a repetitionSpace, which is usually the Shape of the inner component linked with it. For each repetition within this repetitionSpace the Tiler links a tile in the array, which is of the size the outer port to the pattern, which is of the size of the inner port. The Tiler stereotype enables to express in a compact way all the correspondences existing between ends contained inside the array and the pattern arrays. As a consequence, all the links that will potentially exist at run-time (the term link is used here in its original UML meaning, that is to say an instance of a Connector). The idea is to identify tiles inside the array, and establish relations between points contained in this tile to the pattern (i.e. between potential link ends).

The paving tag of the Tiler stereotype is a String representing a set of vectors. It enables to identify the origin of a pattern inside of the corresponding multidimensionnal array. The number of patterns contained inside of each array is determined by the repetitionSpace. The paving process can be defined as follows: Identifying a pattern origin inside of an array can be seen as an iterative process, where iteration limits are given by the repetitionSpace vector. Each pattern origin is determined by multiplying each index of the repetitionSpace by the paving vectors, adding the origin vector. The origin tag of the Tiler stereotype is then used to define this vector.

From each pattern origin identified with the paving process, the fitting tag of the Tiler stereotype enables to identify the points that belong to this pattern. This set of points define the tile. The patternShape, the shape of the port of the inner component, determines the number of points that belong to a pattern. For the fitting process, each point that belongs to a pattern is determined by multiplying the fitting vectors by each index contained in the repetition space defined by the patternShape tag, adding the origin given by the paving process.

More formally, for a given repetitionSpace, i, 0 ≤ i < pavingLimit, the pattern is composed by the points indexed by the following set:

{origin + paving.i + fitting.j | 0 ≤ j < patternShape} (3.1)
if the modulo attribute is equal to false, and by

{origin + paving.i + fitting.j mod shape | 0 ≤ j < patternShape} (3.2)
if the modulo tag is equal to true. One could note that the modulo is not necessary. It is just an simplification for the transformations. Knowing that it is meaning less to access the array outside its dimensions, if the attribute does not exist, it should be considered as always true. One can then detect when the simpler formula is sufficient: if all the value positions are within the array dimensions. As the function is monotonic, it is easily checked by computing the positions of the last point (patternShape -1) of the last repetition (repetitionSpace -1), if there are all within the array dimension, the modulo can be considered as false, and the optimized formula used.

Generalization

This stereotype extends the LinkTopology abstract stereotype. It also applies to the ConnectorEnd metaclass.

Attributes

• +origin: String, a String representing a vector (cf Section 3.3.2), used as an origin for the paving process.

• +paving: String, a String representing a matrix (cf Section 3.3.2), used for the paving process (i.e. to identify the origin of each pattern inside of a given multidimensionnal array).

• +fitting: String, a String representing a matrix, used for the fitting process (i.e. to identify points that belong to a given pattern).

• +tiler: InstanceSpecification, related to the optional notation for tilers.

Constraints

If the tiler tag is not equal to NULL, then origin, paving and fitting must not be specified. This is expressed by this OCL rule: inv: (self.taggedValue->select(name='tiler' and value<>'NULL')implies self.taggedValue->exclude(name='origin' or name='paving' or name='fitting')) and (self.taggedValue->select(name='tiler' and value='NULL')implies self.taggedValue->exclude(name='tiler'))

Optional notation

The origin, paving and fitting tags can be left empty. The "tiling information" can be specified using the tiler tag, referencing an instance (with proper instance values) of the Tiler class.

Reshape

The Reshape stereotype extends the LinkTopology abstract stereotype. It enables to express complex topologies between parts and ports contained in two separate multidimensionnal arrays. More precisely, a Reshape connector is expressed between Shaped ports of two different Shaped parts. There are as many links as the multiplication of the multiplicity of the port by the multiplicity of its part.

The shape of each multidimensional array is considered to be a concatenation of the shape of the ports and the shape of the part. For example, let us consider a port with a shape equal to (3,3), and a owning part with a shape equal to (10,5). Then the global shape of the multidimensionnal array is equal to (10,5,3,3). In fact, the arrays contains all the potential link ends corresponding to an instantiation of the model. See section 3.3.1 for more details.

When the Reshape stereotype is applied, the Tiler stereotype must be applied to each of the connector end. With those two Tilers, the Reshape stereotype enables to express in a compact way all the correspondences existing between ends contained inside the two multidimensionnal arrays. It is strictly equivalent to a component with two ports and a part linked by the two Tilers of the Reshape. The part is an identity elementary component, it outputs the same pattern as it takes in input. The Shape of the inner part is the repetitionSpace tag of the Reshape, while the Shape of its ports is the patternShape tag of the Reshape. The Shape of the ports of the component is the Shape of the ports to which the Reshape is connected.

Note that when two connector ends have the same shape, it is allowed to specify a connector between the two ends without using the Reshape stereotype. As described in section 3.3.1, the connector is then interpreted as a one to one connection between the potential link ends contained inside of the two multidimensionnal arrays.

Generalization

This stereotype extends the LinkTopology abstract stereotype.

Attributes

• +repetitionSpace: String, a String representing a shape (cf Section 3.3.2), used as a limit for the paving process.

• +patternShape: String, a String representing a shape (cf Section 3.3.2), used as a limit for the fitting process.

Constraints

• For each Tiler connector ends related to a given Reshape connector, the number of vectors contained in the paving tag must be equal to the number of integers contained in the repetitionSpace tag. This constraint can not be expressed in OCL.

• For each Tiler connector end related to a given Reshape connector, the number of vectors contained in the fitting tag must be equal to the number of integers contained in the patternShape tag. This constraint can not be expressed in OCL.

• The number of elements contained in a given paving vector must be equal to the number of dimensions of the corresponding connector end (number of dimensions of the part + number of dimensions of the port). This constraint can not be expressed in OCL.

• The number of elements contained in a given fitting vector must be equal to the number of dimensions of the corresponding connector end (number of dimensions of the part + number of dimensions of the port). This constraint can not be expressed in OCL.

InterRepetition

The InterRepetition stereotype extends the LinkTopology abstract stereotype. It is used to describe topologies where relations are expressed in the context of a repetition of a single element, such as in a grid or a cube topology. Each potential instance of a part is connected to other potential instances of the same part. For example, in the context of a toroidal grid, each instance is connected to neighbours located at north, south, east and west position.

The InterRepetition stereotype enables to specify the position of the neighbours of each potential instance of a Shaped part. Each potential instance is implicitly associated to one point of the multidimensionnal array described by the shape of the Shaped MultiplicityElement.

Contrarily to the Reshape stereotype, the shape of the multidimensionnal array corresponds only to the shape of the part. The shape of the port is not taken into account. The repetitionSpaceDependence tag of the InterRepetition stereotype is a String representing a vector of integer values. It describes a translation vector on the space of the multidimensionnal array. It identifies the position of a given neighbour. The inherited modulo tag of the InterRepetition stereotype indicates if the translation is applied modulo the size of the multidimensionnal array. If modulo is set to false, some translations can not applied, and the corresponding links will not be created. In this case, it is possible to used DefaultLink connectors (described in the next section) to specify a "default behavior" for the creation of links.

Please note that in Gaspard with differentiate the words dependence, and dependency. While the first one is used in the context of data dependence, dependency is used in the context of object oriented programming and inheritance (used mainly in the association package).

Generalization

This stereotype extends the LinkTopology abstract stereotype.

Attributes

• +repetitionSpaceDependence: String, a String representing a vector (cf Section 3.3.2). The vector is a translation vector on the space of the multidimensionnal array specified by the shape of the Shaped part.

Constraints

The number of elements contained in the repetitionSpaceDependence vector must be equal to the number of elements contained in the shape of the Shaped part. When applied on an ApplicationComponent, the modulo tag must be set to false. This is due to the semantic meaning: on an ApplicationComponent, the InterRepetition is considered as a dependence over the time, it is not possible to have the first executed instance dependent on the last executed one.

DefaultLink

The DefaultLink stereotype applies to the Connector metaclass. It is introduced to be used jointly with InterRepetition connectors which have a modulo tag set to false. The DefaultLink connector is then "selected" when a "default behavior" has to be defined for the link creation on the boundaries of the shape of the multi-dimensional array. This "default behavior" is needed when the InteRepetition link has one of its connector ends missing (because it is located on the "border" of the iteration space).

A DefaultLink connector is generally also stereotyped Tiler. In this case, the process for determining the topology of the connector is the same as the one described in the Tiler sections, except that the links that will be created are only the ones concerned by the "default behavior" for links creation. The Tiler is executed with the iteration of instance of the component for which the InterRepetion link failed.

Generalization

This stereotype applies to the Connector metaclass.

Attributes

No additional attributes defined.

Constraints

At least one ConnectorEnd of a DefaultLink connector must be part of the ConnectorEnds of a InterRepetition connector.

Tiler class

This class is introduced in order to provide an optional notation for tiling information, as explained in the Tiler section. The guideline to use this optional notation is to define instances of this Tiler class, with proper instance values. This instance can then be referenced by the tiler tag of the Tiler stereotype. If the same tiling information are reused many times, it avoids repeating the definition of the values of the origin, paving, and fitting tags of the Tiler stereotype.

Syntax and Semantic

Syntax and semantic of plain connectors, tilers, and reshapes

Tilers and reshape cannot be used everywhere. In particular, Tilers, which are a way to express address computation, can only have a meaning within the repetitionSpace of a component. On the opposite, the Reshape have their own repetitionSpace. In this section we will detail the various cases of topology within which connectors can be used and precise their semantics.

For each of the three types of connectors (plain, tiler, reshape), a connector can be either linking two components of the same level (assembly connector) or linking a component and its containing component (delegation connector). This leads to 6 basic topologies.

Plain connectors

A connector with no stereotype linking a part A of shape M from a port of shape N to a port of shape N of a part B of shape M is only allowed if the shapes M, N and M , N are identical . By identical, it means that the string concatenation of M and N is exactly the same as M and N . For instance a task with M = 4, and N null, could be connected with plain connectors to a task with M null and N = 4 but not to a task with M = 4 and N = 1. This topology, schematized on Figure 3.2, means that each element of the array M, N is transmitted to the element having the same position in the array M , N .

Figure 3.2: Two components connected via a plain assembly connector

A connector with no stereotype linking a part A of shape M from a port of shape N to a port of shape P of a containing component is only allowed if the shapes M, N and P are identical. This topology, schematized on Figure 3.3, means that each element of the array M, N is transmitted to the element having the same position in the array P .

Figure 3.3: A part connected via a plain delegation connector to its container

Tilers

A connector with the stereotype Tiler linking two parts through ports is not allowed. This construction, schematized on Figure 3.4, would have no meaning, as a Tiler requires to be in the context of a repetitionSpace.

A connector with the stereotype Tiler linking a part A of shape M from a port of shape N to a port of shape P of a containing component is allowed . This topology, schematized on Figure 3.5, means that each element of the pattern N at the iteration M is transmitted to the element the array P according the origin, paving and fitting attributes of the Tiler following this formula (if the modulo attribute is set, otherwise, it is the same formula without modulo) :

{origin + paving.i + fitting.j mod shape | 0 ≤ i < M | 0 ≤ j < N } (3.3)

Reshapes

A connector with the stereotype Reshape linking a part A of shape M from a port of shape N to a port of shape N of a part B of shape M is allowed. This topology, schematized on Figure 3.6, is equivalent to linking them through a identity task (a task which output is identical to the input) with a its ports of shape patternShape in a repetition of repetitionSpace and linked with two tilers having the properties of the two tilers of the reshape.

3.6: Two components connected via a reshape assembly connector connector with the stereotype Reshape linking a part A of shape M from a port of shape N to a port of shape P of a containing component is is not allowed. This construction, schematized on Figure 3.7, would have no meaning, as a Reshape has its own repetitionSpace.

Vector notations syntax and semantic

Gaspard uses three concepts of derived from the mathematical vectors:

1. The shapes which are an ordered (ordered has the UML meaning: the order is fixed and meaningful) list of non-negative integers, which can be unlimited (expressed by ∼). They are written as (a,b,c). They are used in the Shaped, Reshape, Distribution.

2. The vectors which are an ordered list of integers (positive or negative). They are written as (a,b,c). They are used for the origin of a Tiler, InterRepetition.

3. The matrices which are an ordered list of vectors, each vector representing one row of a mathematical matrix. They are written as ((a1,a2),(b1,b2),(c1,c2)), equivalent to

  a1 a2 b1 b2 c1 c2  
They are used for the fitting and paving of a Tiler.

All these three types of vectors contain expressions, where an expression is an abstraction of an integer value. More precisely, these expressions are affine, and potentially reference a parameter defined at the level of the namespace component. For example, a Shaped port can reference a portSize parameter defined on the owning component, with a shape tag specified as follows: shape=(portSize,portSize).

Additional constants

This set of constants is used to simplify the notation of vectors for simple cases:

• ZERO A vector or a matrix with all values set to 0, with the correct size (as many elements as the array has dimensions or computed from array and pattern, or array and repetitionSpace)

• ONE A vector with all its value set to 1, with the correct size (as many elements as the array has dimensions)

• ALL A vector identical to the input and output arrays of a reshape. This is obviously valid only if the input and output arrays have the same shape.

• IDENTITY A square matrix with 1's on the diagonal and 0's everywhere else. The matrix dimension is computed according to the array and the pattern (or repetitionSpace). As it has to be square, therefore the number of dimensions of the array must be the same as the number of dimensions of the pattern (or repetitionSpace).

Chapter 4

Package HardwareArchitecture

Overview

The hardwareArchitecture package main objective is to satisfy the growing need of embedded systems designers to model a high level modeling. Using this package, a designer shall be able to dimension material resources and to describe interconnection topology at a coarse grain level. The UML representation is available in the

Description

HardwareComponent

A HardwareComponent is an abstraction of a physical material resource. For such a component it is necessary to specify if it is an ElementaryComponent. A HardwareComponent can be refined as a Processor, a Communication or a Memory, using stereotypes.

Generalization

This generalizes GaspardComponent.

Constraints

A HardwareComponent can only contain HardwareComponent.

Communication

The Communication concept represents a material component describing interconnections between component. The Communication supports data and instruction transaction.

Generalization

This generalizes HardwareComponent.

Constraints

A Communication component can only contain Communication components.

IO

IO gives the way the architecture communicates with its environment. Thus, it is allowed to model a part of the architecture environment.

Generalization

This generalizes HardwareComponent.

Sensor

A Sensor is a component which send data to the architecture. They are mainly an abstraction of a real sensor component, like an Analog to Digital Converter (ADC).

Generalization

This generalizes IO.

Actuator

A Sensor is a component which send data to the architecture environment. They are mainly an abstraction of a real actuator component, like a Digital to Analog Converter (DAC).

Generalization

This generalizes IO.

INRIA

Memory

The Memory abstract concept express a component offering a data storage capabilities. A Memory can contain instruction or data. They are considered as a slave, since they are not able to initiate communications.

Generalization

This generalizes HardwareComponent.

Constraints

A Memory component can only contain Memory components.

RAM

RAM memory only contain ports with the In interface. Thus a RAM component is a hardware resource than can only propose read/write services to its environment.

Generalization

This generalizes Memory.

Constraints

A RAM can only contain RAM.

Cache

This concept defines a cache memory abstraction and its controller. A Cache material component has a port with the In interface, providing read/write services to a processor, and a port with the Out interface, offering read service to its environment while a cache miss occurs.

Generalization

This generalizes Memory.

Constraints

A Cache can only contain Caches.

Semantic

Even if a cache is not directly programmable by a programmer (in the association model, we can not directly place data on cache memory), it is useful to know their capabilities and their organization in order to optimized transferred data bloc.

Processor

The Processor material component represents a resource able to realize computation. They are also able to emit read/write request to their environment, event if it also depends on the associated interface and their orientation (In or Out). In the Gaspard association model, Processor are used to support execution of application component.

Generalization

This generalizes HardwareComponent.

Constraints

A Processor can only contain Processor.

ProgrammableProcessor

ProgramableProcessor defines a kind of processor which manipulate one or several instruction set. A ProgramableProcessor can represent a General Purpose Processor (GPP) or a Digital Signal Processor (DSP).

Generalization

This generalizes Processor.

Constraints

A ProgrammableProcessor can only contain ProgrammableProcessor.

HardwareAccelerator

HardwareAccelerator represents an Application Specific Integrated Circuit (ASIC), corresponding to a circuit specialized for a particular function.

Generalization

This generalizes Processor.

Constraints

A HardwareAccelerator can only contain HardwareAccelerator.

Chapter 5

Package Application

Overview

Description

ApplicationComponent

An ApplicationComponent represents a computing component on the application side. For such a component it is necessary to also specify if it is an ElementaryComponent or not.

Generalization

This generalises GaspardComponent.

Constraints

An ApplicationComponent can only contain ApplicationComponents.

ArrayProducer

A physical sensor is modeled as an ArrayProducer in the application level. In this level, only the characteristic of multidimensional array production of a sensor is considered, i.e. an ArrayProducer component produces infinite multidimensional arrays that could be processed by following applications without considering its frequency, its data structure, its data type, etc. This component is the first step of the data processing.

Generalization

This generalises ApplicationComponent.

Constraints

This component has at least one output port, and does not have any input port.

ArrayConsumer

A physical actuator is modeled as an ArrayConsumer in the application level, which acts as a component consuming infinite multidimensional arrays computed by previous tasks. This component is the last step of the data processing. The frequency of the input multidimensional arrays and the constraints of the consumption of these arrays are not considered here.

Generalization

This generalises ApplicationComponent.

Constraints

This component has at least one input port, and does not have any output port.

Semantic

Although the application package might look very simple at first sight, using the factorization concepts and the component concepts, it is possible to create complex applications with the data parallelization fully explicit. The execution model is based on the Array-OL model [START_REF] Amar | Projection of the Array-OL specification language onto the Kahn process network computation model[END_REF]. The model is data flow oriented. Data will flow from ArrayProducers to ArrayConsumers passing by ApplicationComponents through connectors. This representation targets systematic intensive signal processing applications.

A particular point to underline is that the model only specifies an algorithm with data dependences. No direct information about the execution model is specified, this is up to the implementation to decide, using the information brought by the association model.

The only type of transactions possible between ApplicationComponents are the signals. A signal emission can be interpreted as the non-blocking emission of a data. The structure of an application can be described as an directed acyclic graph. Communications between components are therefore only mono-directional. The ports are stereotyped In or Out depending on the direction of the data. In ports can receive signals from outside the component, while Out ports only send signal to outside.

The connectors allow to pass arrays (or patterns when the connector is a Tiler) from a Component to another one. For each execution (an instance of the application in the time) an ElementaryComponent (a component which is not made of part assembly) will be run only once all its input signals have been entirely sent. In Gaspard2, this will be actually corresponding to the call to the function defined by the ElementaryComponent, receiving the data as arguments and providing the results via referenced arguments.

The time is not explicitly mentioned in the model. One or several dimensions of repetition can be computed along the time. When a dimension is infinite (represented by ∼), it will necessarily be computed along the time. No information about which dimension has to be implemented along the time is given by the model excepted in the ArrayConsumer and ArrayProducer.

ArrayProducers (resp. ArrayConsumers) carry special semantic concerning the time: the infinite dimension (∼) of an array is produced (resp. consumed) along the time, while all the other dimensions are produced (resp. consumed) synchronously (all elements at once). If such stereotyped component have an array with no infinite dimension, it means this array can be accessed entirely at any time. If a component produces (or consumes) several infinite arrays, the time of each array may be different, i.e. they are not necessarily produced (or consumed) at the same rate.

Chapter 6

Package Control

Overview

The construction of the Gaspard2 UML profile is mainly made for systematic data parallel algorithms, and parallel architectures. It allows to describe the data dependences and all the potential parallelism present in the studied applications. In order to allow the designer to model applications containing control concepts and changing modes, the control concepts were introduced. This was done by giving a reactive behavior to these applications which has been largely studied in the case of the synchronous reactive systems. This package is summarized in the Figure 6.1.

Description

AutomatonComponent

An AutomatonComponent is a GaspardComponent which manipulates modes (in the meaning of a automaton state). From a previous mode, and possibly other inputs, it computes the new mode.

Generalization

This generalizes GaspardComponent.

Constraints

An AutomatonComponent has only one output port, through which signals about mode will go: inv: self.ownedPort.required->size()=1 and self.ownedPort.required.stereotype->exists(name='ModePort')

RepetitiveTransitionComponent

A RepetitiveTransitionComponent is the way to express an automaton by following the Array-OL view. By repeating over time a TransitionComponent and using an inter-repetition dependence of +1 to report the current state of the automaton to the next instance, the execution of the automaton is indirectly described.

Generalization

This generalizes AutomatonComponent.

TransitionComponent

The TransitionComponent is used to specify the transition function of an automaton.

Generalization

This generalizes AutomatonComponent.

Constraints

A TransitionComponent must have one and only one InterRepetition with a repetitionSpaceDependence of [START_REF] Amar | Projection of the Array-OL specification language onto the Kahn process network computation model[END_REF] though which modes will flow. This is partially expressed by: inv: self.connector->select(stereotype->exists(name='InterRepetition')->size()=1)

A TransitionComponent cannot be modeled alone, it has to be inside a RepetitiveTransitionComponent: inv: self.owner.stereotype->exists(name='RepetiveTransitionComponent')

ElementaryTransitionComponent

This defines a transition function of an automaton which should be regarded as a black box from the Gaspard2 perspective (code is executed from the previous state and the result is the new state but nothing is none about the inner of the code).

Generalization

This generalizes TransitionComponent.

Constraints

ElementaryTransitionComponent is an elementary component, it cannot contain any component, this is expressed by this OCL constraint: inv: self.part->select(stereotype->exists(name='GaspardComponent'))->size()=0

ActivityTransitionComponent

This defines a transition function of an automaton which is specified by a UML activity diagram associated to this component.

Generalization

This generalizes TransitionComponent.

Constraints

ActivityTransitionComponent is an elementary component, it cannot contain any component, additionally it must be an Activity diagram. This is expressed by this OCL constraint: inv: self.feature->forAll(oclIsKindof(Activity)) and self.part->size()=0 Extension ModePort extends Port.

Constraints

It can only be of type ModeLiteral (ie: an automaton mode): inv: self.feature->exists(f|f.oclIsTypeof('ModeLiteral'))

ModeLiteral

A Literal in an Enumeration with the stereotype ModeLiteral defines a mode of an automaton.

Extension

ModeLiteral extends EnumerationLiteral.

Semantic

So far the control semantic has been specified only when associated to the application package of the Gaspard2 profile.

The execution of application mixed with the control is mostly straightforward for the control part: the TransitionComponents are executed as ElementaryComponents . A ControlledComponent is similar to a hierarchic GaspardComponent but instead of executing several tasks simultaneously, one task only is executed at a given time, depending on the value available on the ModePort.

One point which differs mainly from the rest of the application semantic is the information flow of the mode. The flow is asynchronous from the rest of the inputs and outputs. A task will never have to wait for a signal on a ModePort. It executes as if no ModePort was present, as soon as a new array is available on each of the ports. The value of the current mode is the last one effectively sent. Therefore, the granularity of a mode change is the array, once an instance of a ControlledComponent is executed, the mode will never change.

This implies that an application will behave differently to a mode change depending on the platform execution speed, this is an inherent behaviour of reactive systems.

Chapter 7

Package Association

Overview

The previous chapters have presented the mechanisms used to model applications and hardware architectures using the Gaspard2 profile. The objective of the association is to provide tools that bind an application (describing the behavior of the SoC) to an architecture (describing the physical components available on the SoC). The following mechanisms are similar to the concept of Deployment in UML, but allow a finer specification and a wider flexibility. They mainly consist in mapping tasks to active components and mapping data to memories, while handling hierarchy and repetitions. A graphical summary of the concepts is available in Figure 7.1.

Allocation

An Allocation is a dependency going from an ApplicationComponent and going to a HardwareComponent. This symbolises that all the ApplicationComponent executions (or instances) will be done on the HardwareComponent.

Extension

Allocation extends Dependency.

DataAllocation

DataAllocation is used to specify onto which memory an array will be mapped. As arrays do not appear in the Gaspard2 profile, the dependency starts from the ApplicationComponent and owns an attribute portName to indicate the array.

Generalization

This generalizes Allocation.

Attributes

• +portName: String specifies the port which corresponds to the mapped array.

Constraints

This can only connect an ApplicationComponent to a Memory.

TaskAllocation

TaskAllocation is used to specify on which Processor an ApplicationComponent will be mapped.

Generalization

This generalizes Allocation.

Constraints

This can only connect an ApplicationComponent or a Reshape to a Processor.

CommunicationAllocation

CommunicationAllocation is used to specify how to synchronize two memories. It describes how to copy an array available on a Memory to a different Memory when two tasks do not share the same Memory for a array. This is only useful when a connector is linking two ApplicationComponents which have mapped the array associated to this communication on different Memories. The copy of the array is then done following a Route which contains the Memories, the Processors used to read and write the arrays and the Communication paths through which it will be done. A CommunicationAllocation goes from the connector linking the two ApplicationComponents to a CollaborationUse.

Generalization

This generalizes Allocation.

Constraints

This can only be applied from a connector linking two ApplicationComponents together to a Communication.

Route

A Route is used to specify through which HardwareComponents will flow a communication.

Extension

This extends Collaboration.

Attributes

• +route: property, the HardwareComponents through which the route is going, ordered from the first one, transmitting data, to the last one, receiving data.

Constraints

A collaboration must be defined in the same namespace as the HardwareComponents it refers to.

OrderDependency

This dependency allows to specify in which order should two tasks be executed when they are mapped on the same Processor but no data dependency permits to decide when to execute them. This dependency goes from the first TaskAllocation which will be executed to the second TaskAllocation.

Extension

OrderDependency extends Dependency.

Constraints

OrderDependency can only link an Allocation, this is expressed by this OCL rule: inv: self.participant->size()=2 and self.participant.forAll(stereotype->exists(name='Allocation'))

Distribution

Distribution brings the concept of Reshapes (as described in the factorization package) to the association. It is significant only when the target component (hardware architecture) is repeated. By specifying a distribution on an Allocation, complex associations between a regular repeated application and a regular repeated architecture can be described. The array of tasks (resp. data) is mapped (distributed) to the array of Processors (resp. Memories). The attributes have the same meaning has in a Reshape. Each instance of a task being a point of the source array and each instance of processor being a point in the target array.

If the source or the destination component do not have any multiplicity, it is regarded as a array of 1 element. are set on the same point as the origin. The fitting matrix is therefore [0]. In order to associate each pattern to a different processor, the paving matrix has to be the identity: [START_REF] Amar | Projection of the Array-OL specification language onto the Kahn process network computation model[END_REF]. The result can be seen in the Figure 7.2.

Figure 1 . 1 :

 11 Figure 1.1: Packages overview

Figure 2 . 1 :

 21 Figure 2.1: The concepts of Components and Ports in Gaspard2

Figure 3 . 1 :

 31 Figure 3.1: Concepts of the factorization package

Figure 3 . 4 :

 34 Figure 3.4: An illegal syntax: Two components connected via a tiler assembly connector

Figure 3 .

 3 8 demonstrates the use of the three types of connectors in various context, with the equivalence of the Reshapes as Tilers in an Application model.

Figure 3 . 7 :

 37 Figure 3.7: An illegal syntax: A part connected via a reshape delegation connector to its container

Figure 3 . 8 :

 38 Figure 3.8: Equivalence of Reshapes with more basic concepts in an Application model. The first model uses a Reshape to link two repeated components. The second models expresses the same application, in a different way.

  Figure 4.1.

Figure 4 . 1 :

 41 Figure 4.1: Hardware component concepts

Figure 5 . 1 :

 51 Figure 5.1: Application components

Figure 6 . 1 :A

 61 Figure 6.1: Concepts of the control package

Figure

  Figure 7.1: Allocation dependencies

Figure 7 . 2 :

 72 Figure 7.2: Allocation of the columns by blocks

RT n°0342

INRIA

DaRT Project INRIA

ControlledComponent

This component is controlled: it is linked to an AutomatonComponent via a ModePort which will indicates in which mode it has to run. Depending on the mode, the ControlledComponent will run one and only one of the AlternativeComponentParts it is composed of. Internally, the ModePort is not linked to anything.

Generalization

ControlledComponent generalizes GaspardComponent.

Constraints

All the parts which composes this component must be AlternativeComponentPart. This is expressed by this OCL constraint: inv:self.part->forAll(stereotype->exists(name='AlternativeComponentPart'))

Each AlternativeComponentPart must have a different activationCondition, this prevent from two parts to be run at the same time. This is expressed by this OCL constraint: inv:

self.part->select(taggedValue.name='activationCondition' implies forAll(p1, p2 |p1.taggedValue.value<>p2.taggedValue.value))

A ControlledComponent must have one and only one ModePort . This is through this ModePort that signals about the current running mode will be passed. This is expressed by this OCL constraint: inv: self.ownedPort.provided->select(stereotype->exists(name='ModePort')->size()=1)

All the AlternativeComponentParts must have the same interface, that is the same ports (same interface, same shape, and same direction) and each port must be linked to the same port of the ControlledComponent . This is partially said by this OCL constraint: inv:

self.part->forAll(p1,p2| (p1.ownedPort.provided=p2.ownedPort.provided) and (p1.ownedPort.required=p2.ownedPort.required))

At runtime, only the parts which have their activationCondition set to the same value as the current ModePort value are activated.

inv: self->includes(p:part|p.activationCondition.value=ownedPort.provided->select(stereotype->exists(name='ModePort')).value) and self->excludes(p:part|p.activationCondition.value<>ownedPort.provided->select(stereotype->exists(name='ModePort')).value)

AlternativeComponentPart

If a part (an instance of a component) has this stereotype, it will be selected or not depending on the current mode of the automaton linked to the containing ControlledComponent.

Extension

This extends Property.

Attributes

• +activationCondition: EnumerationLiteral This Literal must be a ModeLiteral and it represent the mode into which the part will be executed.

ModePort

This allows to specify a port over which the signals will contain a mode of an automaton.

Extension

Distribution extends Dependency.

Attributes

• +sourceTiler: InstanceSpecification This points to an instance of Tiler which defines the association from the array of ApplicationComponents (task, arrays. . . ) to the pattern.

• +targetTiler: InstanceSpecification This points to an instance of Tiler which defines the association from the pattern to the array of HardwareComponents (processors, memories. . . ).

• +patternShape: String This shape defines the dimensions of the pattern.

• +repetitionSpace: String This shape defines the bounds of repetition for each dimension.

Constraints

This can only be applied to an Allocation.

Semantic

Allocation represents the concept of associating an ApplicationComponent (either a task or an array) to a HardwareComponent (either a Processor or a Memory). Once associated, all the specified instances of the ApplicationComponent will be executed (or saved) on the HardwareComponent. If the component is hierarchic, all the sub-component are mapped on the same HardwareComponent. In the case an ApplicationComponent is connect with Tilers (to ports of a containing component), the Tilers are mapped on the same HardwareComponent than the ApplicationComponent.

If a multiple dependency is used, all the combinations of link between the ApplicationComponents and the HardwareComponents are expressed with the same stereotype and tagged values applied.

Illustrative example

As an example we will show how to use those mechanism to describe the usual "block" distribution pattern. The example is based on an application composed by 32×32 elementary tasks, and an architecture composed by 4 processors. The architecture pattern is made of only 1 processor, that is, 4 patterns. Only the distribution of task is shown in this example, but the usage of distribution of data is very similar.

Block distribution

A block distribution consists in identifying n blocks (n = number of processors) among a set of tasks (represented by an array). All the blocks have the same dimensions and are compact, in this example: 8×32. Following the rules presented in the factorization section, the pattern elements are set out according to the fitting matrix. A compact pattern is represented by an identity matrix: for each dimension, the next element is at the current position translated of 1. The fitting Matrix is therefore [1,0;0,1]. The bounds of the fitting are [8,32], the patternShape.

Identifying the origin of each block of task is fairly straightforward and consists in representing [c/n,0] (where c is the size of a line and n is the number of processors). Therefore the paving vector has to be defined to [8,0]. The bound of the paving being the amount of processors: [4], the repetitionSpace.

The hardwareArchitecture tiler has to express that each pattern will be associated to one processor. This is done by specifying a fitting matrix to null. That is, all the elements of the pattern INRIA


A Benzerrouk
email: ahmed.benzerrouk@lasmea.univ-bpclermont.fr

L Adouane

P Martinet

Altruistic Distributed Target Allocation for Stable Navigation in Formation of Multi-robot System

This paper deals with reaching and keeping the formation for a group of mobile robots. A set of virtual targets (points) form a virtual structure of the same shape as the desired formation. Hence, to join and to keep this formation, each robot has only to track one of these targets. The objective of the paper is mainly to propose a cooperative strategy between the robots in order to rapidly join the virtual structure. Instead of assigning ahead one target per robot, the proposed strategy consists of making each one able to negotiate the closest target. If the latter is desired by more than one robot, it is left for the one which meets more difficulties to find an other target. Negotiation is based on a minimalist communication of relative cost coefficients between the robots. Simulation and experimental results validate the proposed contributions.

I. INTRODUCTION

Controlling and coordinating Multi-robot systems MRS are an attractive research subject thanks to their large application fields (spatial exploration, platooning, rescue, etc.). In this paper, we are particularly interested in the navigation in formation task with a reactive manner. Works given in the literature converge to three principle approaches: hierarchical approach, behavior based, and the virtual structure strategy.

In the first approach, one or many robots are considered as leaders while the other robots are the followers. Generally, the leader tracks a predefined trajectory while the followers track its transformed coordinates [START_REF] Léchevin | Trajectory tracking of leaderfollower formations characterized by constant line-of-sight angles[END_REF], [START_REF] Gustavi | Observer-based leader-following formation control using onboard sensor information[END_REF]. This approach is simple to perform. However, it is noticed that a leader failure leads to stop the whole system. In behavior based approach [START_REF] Antonelli | The nsb control: a behavior-based approach for multi-robot systems[END_REF], [START_REF] Balch | Behavior-based formation control for multirobot teams[END_REF], all the robots are homogeneous. It means that perception and control are equitably distributed on the robots. This method is then much more tolerant to failure [START_REF] Parker | On the design of behavior-based multi-robot teams[END_REF] than the hierarchical approach. Behavior based implies that each one has a set of weighted behaviors (basic tasks) to achieve. The resulting behavior of the group emerges from the basic ones without an explicit model of the overall cooperative behavior. However, this approach is upbraided for the way to choose the applied control to each robot. In fact, according to perception information, control system switches between behaviors (competitive approach [START_REF] Brooks | A robust layered control system for a mobile robot[END_REF]), or merges several controllers (motor schema [START_REF] Arkin | Motor schema-based mobile robot navigation[END_REF]). This naturally makes hard studying the stability of the overall control.

Virtual structure approach considers the formation as a single virtual body. The shape of the latter is the desired formation shape, and its motion is translated into the desired motion of each vehicle [START_REF] Do | Formation tracking control of unicycle-type mobile robots[END_REF], [START_REF] Li | Backstepping based multiple mobile robots formation control[END_REF]. The virtual structure is generally tackled through potential field methods [START_REF] Ogren | Formations with a mission: Stable coordination of vehicle group maneuvers[END_REF], [START_REF] Mastellone | Remote formation control and collision avoidance for multi-agent nonholonomic systems[END_REF]: thus, all members of the formation track assigned nodes which move into the desired configuration. Each node applies an attractive field to the corresponding robot whereas obstacles and other robots apply repulsive field to avoid collision. The weakness of the virtual structure is that potential applications are limited especially when the formation shape needs to be frequently reconfigured.

To overcome drawbacks of these strategies, it was proposed to combine virtual structure and behavior based in [START_REF] Benzerrouk | Navigation of multi-robot formation in unstructured environment using dynamical virtual structures[END_REF]. The achieved task (reaching and maintaining a desired formation while avoiding collision) is divided into two basic tasks (behaviors): attraction to a dynamical target, and obstacle avoidance. These behaviors do not use potential fields which allows possible reconfiguration of the formation.

In this paper, a particular attention is given to the cooperative strategy between the robots. Hence, only the part of maintaining the formation is treated and obstacle avoidance will not be detailed. In fact, in the literature, it is noticed that the formation emerges because each robot tracks its target. These targets are assigned ahead to the robots: In [START_REF] Balch | Behavior-based formation control for multirobot teams[END_REF], relative positions of the robots in the formation are based on an identification number ID. Each robot obtains then the relative position corresponding to its ID. The same strategy is followed in [START_REF] Lewis | High precision formation control of mobile robots using virtual structures[END_REF]. Even in recent works, every robot tracks a target already assigned to it [START_REF] Ghommam | Formation path following control of unicycle-type mobile robots[END_REF], [START_REF] Lalish | Formation tracking control using virtual structures and deconfliction[END_REF], [START_REF] Ren | Formation feedback control for multiple spacecraft via virtual structures[END_REF] and optimizing the allocation of these targets was not studied.

This preliminary assignation allows to avoid conflicts (to not choose the same target) between the robots in a simple way. However, if these robots optimize the way of sharing the targets according to their initial positions, formation can be reached faster and some deadlock situations can be avoided. In fact, by assuming homogeneous robots (they have the same constraints (maximal velocities, accelerations, etc.)), reducing covered distances leads to reducing time to reach the formation.

In this paper, we are then interested in the target negotiation between the robots. It is proposed that each one negotiates, in a distributed manner, the closest target with the others in order to reduce the total distance completed and thus, time to reach the formation. If one target is desired by many robots, it is given up to the one which seems having bigger costs for the other targets. A form of altruism is then observed between the robots.

The idea of the dynamic allocation of the targets is inspired from the auction sales activity. The latter is used in the literature for the task allocation to MRS [START_REF] Dias | Market-based multi-robot coordination: a survey and analysis[END_REF] such as exploration [START_REF] Kalra | Hoplites: a market-based framework for planned tight coordination in multirobot teams[END_REF], visiting different locations [START_REF] Tovey | The generation of bidding rules for auction-based robot coordination[END_REF], and box pushing [START_REF] Brian | Sold!: Auction methods for multirobot coordination[END_REF]. Three main auction mechanisms were developed. Combinatorial auctions [START_REF] Berhault | Robot exploration with combinatorial auctions[END_REF] treat all the possible combination of the tasks. Hence, they give optimal results. However, time computation becomes easily heavy when the number of tasks and robots increase. Moreover, this computation requires a central unit with a total knowledge of the environment. This is inconsistent with our desired distributed architecture of control. Repeated parallel auctions [START_REF] Dias | TraderBots: a market-based approach for resource, role, and task allocation in multi-robot coordination[END_REF], treat each task separately of the other tasks. Auctions are repeated every time interval to test if one task can be improved if it is allocated to an other robot. In sequential mechanisms [START_REF] Tovey | The generation of bidding rules for auction-based robot coordination[END_REF], each robot auctions each task individually taking into account its previous state. Therefore, there is no need to a central coordination. However, robots have to communicate their costs to determine the winner of each task.

As in [START_REF] Nanjanath | Repeated auctions for robust task execution by a robot team[END_REF], our algorithm is close to a combination of the two last methods since each robot wins a target or gives it up to another by computing and comparing (itself) costs of these targets. Allocation of the targets can occur every ∆T to adapt the robots to the formation changes. Only a minimalist communication is needed with the proposed algorithm.

The remainder of the paper is organized as follow: in next section (II), the task of navigation in formation is defined and the dynamic allocation of the targets algorithm is detailed. Section III reminds the proposed control law insuring that each robot joins the formation [START_REF] Benzerrouk | Navigation of multi-robot formation in unstructured environment using dynamical virtual structures[END_REF]. Section IV gives simulation and experimental results. Finally, conclusion and some prospects are given in section V.

II. NAVIGATION IN FORMATION USING VIRTUAL STRUCTURE

A. The virtual structure principle

Before discussing cooperative strategy, the adopted virtual structure principle is reminded. Consider N robots with the objective of reaching and maintaining them in a given formation. The proposed virtual structure that must be followed by the group of robots is defined as follow:

• Define one point which is called the main dynamical target (cf. Figure 1), • Define the virtual structure to follow by defining N T nodes (virtual targets) to obtain the desired geometry. Each node i is called a secondary target and is defined according to a specific distance D i and angle Φ i with respect to the main target. Secondary targets defined by this way have then the same orientation θ T . However, each target i will have its linear velocity v Ti . The number of these targets N T must be N T ≥ N . An exemple to get a triangular formation is given in figure 1.

D i D j ĭ j ș T O w X w Y w Main dynamical target Secondary target v T D k ĭ k ĭ i Robot q Robot p Robot r

B. Cooperative strategy between the robots: dynamic allocation of the targets

The idea is that robots cooperate in order to reduce time of reaching the formation. As already discussed, each robot chooses the closest target to track. However, this may create conflicts when many robots choose the same target. To avoid this conflict, a hierarchy between them was adopted in [START_REF] Benzerrouk | Navigation of multi-robot formation in unstructured environment using dynamical virtual structures[END_REF]. Hence, the desired target is given up to the robot of a higher rank. However, this hierarchy is not justified especially if the robots have the same characteristics. In this paper, it is then proposed that each robot computes a coefficient per target to describe its interest for this one. Computed every time interval ∆T , this coefficient informs if this target is very close or very far from the robot comparing to the other targets. It is called Relative Cost Coefficient (RCC) and is noted δ. Comparing RCCs of the same target allows to each robot to decide if it takes this target or gives it up to an other.

In what follows, the RCC of a robot i for the target j is noted δ ij . It is computed as

δ ij = dS ij N T k=1 dS ik = dS ij dS ij + N T k=1,k =j dS ik (1)
where d Sij is the distance between the robot i and the target j. For a robot i, the set of RCCs for all the targets is put in a vector ∆ i .

It is clear that (cf. Equation 1)

0 ≤ δ ij ≤ 1
Moreover, δ ij is as close to 0 as

d Sij NT k=1,k =j d S ik (2)
Thus, every robot prefers the target with the smallest RCC because it is the closest one. It is then noticed that the same result would be obtained by simply comparing the distances to the different targets and directly choosing the closest one. However, the main objective of the RCC is to negotiate the desired target with the others. Hence, if two robots i and k ask for the same target j (they are in conflict for this target), distances d Sij and d S kj are not sufficient to know which robot has to obtain it in order to reach faster the formation. Therefore, to negotiate their targets, robots act according to the following proposition: Proposition 1. If many robots are in conflict for one target, then this target is left to the robot having the smallest RCC for this target.

In fact, according to (2), the strategy of this proposition is to compare the situation of the robots according to the existing targets and to give up the desired one to the furthest robot from the other targets. The proposed distributed strategy for dynamic allocation of the targets which allows an altruism between the robots is given in algorithm 1.

Require: Vectors ∆i, i = 1..N . Ensure: Choice of the virtual target to follow 1: while (Target not chosen) do

2:
choose the target j corresponding to the smallest RCC ∆i(j);

3: if ∆i(j) < ∆ k (j), ∀k = i, k = 1..N then 4:
go to line 11;

5:

else 6:
choose an other target l such as ∆i(j) < ∆i(l) < ∆i(m), ∀m = j; The proposed algorithm is distributed on all the robots. It requires that each robot i communicates only its vector ∆ i to the other ones. It is also proposed that a vector ∆ i includes the subscript i indicating the robot identifier. Identifiers of the robots are randomly chosen and do not indicate any hierarchy for the target assignment.

According to this algorithm, every robot is able to deduce if the desired target will be really available or it will be taken by an other one having a less corresponding RCC. Negotiation and allocation of the target is then done in a distributed manner.

It is noticed that the required communication process is very basic and can be summarized in algorithm 2. The time interval δ t to wait (line 2, algorithm 2) allows to avoid collision between network packets.

1: receive the vectors ∆ k such that k = 1..i -1; 2: wait a time δt, then send the vector ∆ i ; 3: receive the vectors ∆ k such that k = i + 1..N ; Algorithm 2: Sequential communication process of the robot i with the other robots.

Even if most of conflicts in target assignment are solved thanks to algorithm 1, some points need to be discussed:

• if the robot i has the same RCC value for a target j as an other robot k (which means ∆ i (j) = ∆ k (j)), then i can search the second possible target l for itself such that ∆ i (j) < ∆ i (l) < ∆ i (m), ∀m = l, and the second possible target n for the robot k with ∆ k (j) < ∆ k (n) < ∆ k (m), ∀m = n (robot k has naturally the same reasoning). The robot i keeps the target j if (∆ i (l) > ∆ k (n)), because it means that k will find the target n with a cheaper RCC. Otherwise, if (∆ i (l) < ∆ k (n)), the robot i gives up the target j because l seems cheaper for it than the target n for the robot k. • If the robots i and k have also the same RCC for their next targets (∆ i (l) = ∆ k (n)) (targets l and n are as defined above). In this case, the target j can be indifferently taken by i or k. However, to avoid that both the robot choose the target j, or both leave it, it is proposed that the robot with the higher subscript obtains it. This convention cannot be considered as a hierarchy between the robots since they choose their targets with the same RCCs. • Finally, this distributed reasoning can be easily applied if more than two robots negotiate the same target. Note that according to algorithm 2, communication is done once at the beginning of negotiations. It is then not affected (by becoming tedious) when many robots are in conflict for a target.

III. THE APPLIED CONTROL TO THE ROBOTS

A. Attraction to a Dynamical Target Controller

To remind the attraction to a Dynamical Target Controller which allows to keep the formation, consider a robot i with (x i , y i , θ i ) pose. This robot has to track its secondary dynamical target. To simplify notations in the following, the same subscript of the robot is given to its target. The latter is then noted T i (x Ti , y Ti , θ T ) (cf. Figure 2) and the variation of its position can be described by

ẋTi = v Ti .cos(θ T ) ẏTi = v Ti .sin(θ T ) (3)
Ȗ i Y m X m O m (x i , y i ) d Si O w X w Y w ș i ș T v T i

T i (x Ti , y Ti )

Secondary Virtual Target Let's also introduce the used robot model (cf. Figure 2). Experimental results are made on Khepera robots, which are unicycle mobile robots. Their kinematic model can be described by the well-known equations (cf. Equation 4).

     ẋi = v i .cos(θ i ) ẏi = v i .sin(θ i ) θi = ω i (4)
where θ i , v i and ω i are respectively the robot orientation, the linear and angular velocities.

The set-point angle that the robot must follow, to reach its dynamical target, is given by

θ Sati = arcsin(b sin(θ T -γ i )) + γ i (5)
Where b = vT i vi . γ i is the angle that the robot would have if it was directed to its target (cf. Figure 2). This set-point has been obtained by keeping γ i constant. More details and proofs are available in [START_REF] Benzerrouk | Navigation of multi-robot formation in unstructured environment using dynamical virtual structures[END_REF].

B. The used control law

The used control law, which was proposed in [START_REF] Benzerrouk | Navigation of multi-robot formation in unstructured environment using dynamical virtual structures[END_REF], allows to each robot i to converge to its set-point.

v i = v max -(v max -v Ti )e -(d 2 S i /σ 2 ) ( 6a
)
ω i = ω Sati + k θi (6b)
where • v i and ω i are linear and angular velocities of the robot respectively. It is also noted ω Si = θSati where θSati is the angular variation of θ Sati . • v max is the maximum linear speed of the robot, • σ, k are positive constants,

• θi is the error orientation so that θi = θ Satiθ i which gives θi = ω Satiω i . Lyapunov based stability allowed to prove the convergence of the robot to its target [START_REF] Benzerrouk | Navigation of multi-robot formation in unstructured environment using dynamical virtual structures[END_REF]. Convergence of the whole multi-robot system to the set-point virtual structure can then be derived by studying the following Lyapunov function

V = N k=1 V k (7)
where V k is the Lyapunov function associated to the robot k. This function was defined as

V k = 1 2 θ2 k (8)
It has been proved that Vk < 0 (when θk = 0) [START_REF] Benzerrouk | Navigation of multi-robot formation in unstructured environment using dynamical virtual structures[END_REF]. Therefore, it can be easily deduced that

V = N k=1 Vk < 0 (9)
The global system is then asymptotically stable. Moreover, it can be noticed that the applied angular velocity ω i allows exponential convergence of the error orientation to 0.

However, this theoretical convergence is applied to nonholonomic mobile robots. It means that stability will be insured only if the angular set-point is reachable by the robot while considering its kinematic constraints (maximal velocities, maximal accelerations).

In [START_REF] Benzerrouk | Navigation of multi-robot formation in unstructured environment using dynamical virtual structures[END_REF], it has been proved that the robot converges to its target only if

v i ≥ v Ti ⇔ b ≤ 1 (10)
According to equation (6a), it is noticed that the linear velocity of the robot verifies the condition given by inequation [START_REF] Ogren | Formations with a mission: Stable coordination of vehicle group maneuvers[END_REF], and takes into account its maximal linear velocity. However, it is noted that linear velocity of the secondary targets depends on their relative position in the virtual structure. The choice of D i and angle Φ i affect then v Ti .

Moreover, the variation of the angular set-point θSati has to stay reachable by the robot. Indeed, the angular velocity supported by the robot has a maximal value noted ω max . Defining the bounaries of θSati so that |ω i | ≤ ω max and those of D i and Φ i so that v Ti < v max will be discussed in a future work.

IV. SIMULATION AND EXPERIMENTAL RESULTS

To show the relevance of the proposed algorithm for the dynamic allocation of the targets, it is proposed to simulate a group of 5 robots reaching a formation (N = 5). The MRS is simulated with different initial positions (IPs).

For every IP, the simulation is made twice: one with a prior assignation of the targets (target T i to robot R i ), and one with the proposed algorithm where the robots use the RCC to obtain their targets. In the two cases, time to reach the formation is measured in order to evaluate the proposed algorithm performance. Note that the formation is considered reached if the distance d Sij separating every robot R i from the chosen target T j is such that d Sij ≤ r 0 ; where r 0 is the radius of a small virtual circle in the neighborhood of the targets. Results are given in table I.

Comparing the two approaches, it can be seen that negotiation of the targets using RCC offers a smaller time of convergence. It is noticed that the amount of enhancement depends on the initial position of the robots. In fact, for a prior assignation case (without negotiation), robots may be in the other side of the virtual structure compared to their assigned targets. They have then to avoid each other and to uselessly navigate to far targets. To illustrate this problem, An example of initial positions is given in figure 3(a). In the case of prior assignation, robot R i has to join target T i . To keep obvious the order of the targets in the figures, a straight trajectory is given to the virtual structure (see figure 3(b)) (a circular trajectory is used in experimental results). Taking the exemple of robot R 5 , it can be seen that it has to go until target T 5 when it does not negotiate the closest one (cf. Figure 3(b)). However, by using RCC algorithm (cf. Figure 3(c)), it obtains the target T 2 which is much closer. Meanwhile, R 5 did not choose T 3 even if it was the closest one (cf. Figure 3(a)). In fact, it gives up T 3 to the robot R 3 which was behind it at the beginning of the simulation. In the same manner, R 1 gives up the closest target (T 5 ) to R 4 and takes T 1 .

A. Experimental results: a formation of 3 robots

Experimentations are implemented on Khepera III robots. As first tests, only perception of the MRS is still centralized. Hence, navigation is achieved on a platform equipped with a camera giving positions and orientations of the robots (cf. Figure 4). These one have to join and to maintain a triangular virtual structure. The latter has a circular trajectory such that it stays reachable. First, it has a clockwise motion (cf. Figure 5(a)).Every robot calculates then the RCC for the targets. For the robot R 1 , the smallest RCC corresponds to T 3 . This one is not desired by any other robot since the RCC of R 2 and R 3 for this target is not the smallest one comparing to the other targets. However, R 2 and R 3 ask both for T 2 through their RCC. Since R 2 has the smallest one, R 3 has to search for an other. It takes the remained target T 1 . 5(b)). Also, the dynamic of the virtual structure is changed so that its motion becomes counterclockwise. The robots recalculate the RCC for each target.

The RCC are given in table III. This table shows that all the robots prefer target T 2 . R 1 obtains it because it has the smallest corresponding RCC. R 2 and R 3 search then for the target with the RCC immediately higher than the RCC of T 2 . Again, both are interested by T 1 . The latter is obtained by R 3 because its RCC is smaller. R 2 takes the remained target T 3 . It can be seen that R 2 and R 3 give up T 2 to R 1 (altruism). Distances between the robots and their targets are given in figure 6. They decrease until 0 which confirm that the formation is reached and maintained. When the virtual structure dynamic is changed, robots are far from their targets which explain the observed jumps. The same observations are noticed on the global Lyapunov function (cf. Figure 7).

V. CONCLUSIONS AND FUTURE WORKS

In this paper, the formation of a multi-robot system, based on the virtual structure strategy, was studied. A cooperative protocol between the robots was proposed in order to rapidly join the formation. Instead of a prior assignation of their places in the formation (virtual targets), it is proposed that each robot negotiates its one with the others by communicating relative cost coefficients for each target. An altruism is then observed between the robots. Moreover, simulation results show the performance offered by the proposed algorithm. Time to reach the formation was improved by reducing trajectory of the robots. Even if the obtained results are not the most optimal ones, this work addresses an interesting subject and allows to improve this time by discussing the RCC formula.

In the proposed experimental results, dynamical negotiation of the targets was enabled at the beginning of the experimentation and when switching to the virtual structure dynamic. In order to be done in a completely reactive way, discussing and justifying its frequency (∆T ) will be the subject of future works. Collision avoidance between the robots and with other dynamical obstacles will be detailed in a future paper.

Fig. 1 .

 1 Fig. 1. Keeping a triangular formation by defining a virtual geometrical structure.

10 :Algorithm 1 :

 101 end while; 11: go toward the chosen target ; Distributed virtual target assignment (N T ≥ N ).

Fig. 2 .

 2 Fig. 2. Attraction to a dynamical target.

Fig. 3 .

 3 Fig. 3. Trajectory of the robots reaching the formation: prior assignation versus negotiation of the targets.

Camera

Fig. 4 .Fig. 5 .

 45 Fig. 4. Platform experimentations.

3 Fig. 6 .

 36 Fig. 6. Variation of the distance d S i between the robot i and the chosen target (i = 1..3).

Fig. 7 .

 7 Fig. 7. Evolution of the global Lyapunov function V .

TABLE II RELATIVE

 II COST COEFFICIENT AT MOMENT (t 0 ).

		T 1	T 2	T 3
	R 1	0.41	0.32	0.25
	R 2	0.39	0.23	0.33
	R 3	0.39	0.24	0.41

At moment t 2 + ∆t, a jump of the virtual structure state is produced (cf. Figure

TABLE III RELATIVE

 III COST COEFFICIENT AT MOMENT (t 2 + ∆t).

		T 1	T 2	T 3
	R 1	0.36	0.21	0.38
	R 2	0.37	0.22	0.40
	R 3	0.34	0.26	0.40

This work is supported by the French National Research Agency (ANR) through the R-Discover project.