Luc Courtrai
email: luc.courtrai@univ-ubs.fr

Frédéric Yves Mahéo
email: yves.maheo@univ-ubs.fr

Raimbault Orcade
email: frederic.raimbault¡@univ-ubs.fr

Java Objects Communication on a High Performance Network

Local high performance networks availability already makes workstations clusters a serious alternative for parallel computing. However, a high level and effective programming language for such architecture is still missing. Recent works show the interest in Java for cluster programming. One of the main issues is to handle efficiently the communication of objects to really take advantage of the network speed. The paper presents an alternative to the standard serialization process through the proposal of a Java object communication library. Object allocation is controlled in such a way that the transfer of objects between two nodes comes to a direct memory to memory dump. We show how specific allocation mechanisms can cooperate with a Java Virtual Machine so that fast transfers of graphs of objects can be achieved. Experimental results are given for basic operations and for a genetic programming application; they demonstrate a dramatic change in the transfer speed.

Introduction

Local high performance networks availability already makes workstations clusters a serious alternative for parallel computing infrastructure. However, an effective high level programming language for such architecture is still missing. Recent works show a growing interest in Java for cluster programming [START_REF] Forum | Java Grande Forum Report: Making Java work for high-end computing[END_REF].

One of the main issues in Java for high performance distributed applications remains the transfer speed of objects. On one side, the object paradigm implies that an object may have references to others objects, so that a complete graph of objects must be communicated. On the other side, communication libraries such as Unix sockets or PVM/ MPI API offer the transmission of a simple memory buffer. So the gap must be filled between the needed ability to send a whole graph of objects and the basic message passing functionality.

The most common way to handle object communication in Java is to apply a serialization on the sending side and an unserialization on the receiving side: the graph of references is explored and data representing each node of the graph is copied into a memory buffer that can be sent by the underlying communication primitive. A deep copy of the graph can be rebuild from the received buffer as far as enough type information is encapsulated in the message. This method can be applied in Java by using the standard interfaces 1 that allow an object to be serialized into a stream (so possibly an array of bytes). Marshalling relies on introspection mechanisms to automatically define the bytes array layout. Unfortunately, this shows very poor performance though the programmer may provide methods to specialize operations.

Firstly, serialization in Java has been designed in a very general way in terms of portability and heterogeneity. Much type information must be computed and put in the buffer. Besides, many method calls and object creations are involved when marshalling and unmarshalling the graph of objects. This makes the serialization a very time consuming operation. And serialization is especially disadvantageous in the context of high speed networks as demonstrated by the following experiment.

We have timed separately the marshalling process and the pure communication on a standard (¢ ¤£ ¦¥ ¨ § © Ethernet) network and on a high-speed (¢ § ¤© Myrinet) network 2 . Results for the transfer of a graph of objects (a binary tree of ¢ ¤£ £ £ integers) are reported on table 1. Three available Java API have been tested. When using the most general one -the standard JDK Serializable API -the speedup API Serializable Externalizable XSerializable serialization (& unserialization) time in

¢ ¤£ ! ¢ #" " ¢ ¢ %$ '& (¢ ) ! %$ '& 10 communication time in Ethernet ) ! 2& 1£ £ ¢ ¤ ( 2& 30 £ ¢ 4 ! 2& 30 £ Myrinet $ 1$ " 5 " ) total transfer time in Ethernet ¢ & 15 ! 2& 3" " ) !¢ ¢ 46 !¢ 0 ) ! ¢ 46 0 Myrinet ¢ ¤£ ! 7 1" 0 ¢ 40 ! 7) ) & ( 7) ) " speedup Ethernet 8 Myrinet ¢ 9 ) " 0 !9 " 0 " @9 ) & serialization time total transfert time in A Ethernet $ ) ) 3$ ¢ ¤6 Myrinet 1" 5 6
Table 1. Marshalling process costs on standard and high speed networks obtained on the high speed network is only ¢ 9 ) 1" while the communication speed is increased by " £ ! Explanation lies on the last row where it appears that the serialization and the unserialization process represent $ ) BA of the total transfer time. So the increase of the communication speed benefits only to a quarter of the transfer time. A common way of improvement is the use the Externalizable API. The marshalling method is provided by the programmer instead of relying on an introspection mechanism; it reduces the graph traversal time and the size of the message representing the object transferred. But the speedup obtained in this case grows only to 0 @9 C" when migrating from the Ethernet to the Myrinet network while the communication speed is increased by ) 10 . Things improve slightly because the part of the serialization process in the total transfer time remains high () 3$ DA ). Finally, we tested an optimized version of the Externalizable API (noted XSerializable) provided by the JavaParty team at Karlsruhe University [START_REF] Philippsen | More efficient object serialization[END_REF]. It improves considerably the marshalling process and allows the speedup to reach " @9 ) & . But, despite the various optimizations included in the XSerializable implementation, the programmer does not benefit much from the communication speed improvements: about 5 6 1A of the transfer time on the high speed network is spent in communication packaging and unpackaging. We claim that the serialization mechanism should be reconsidered when one wants to take full advantage of the network technology improvement. In some cases where heterogeneity and portability are not the prior concerns, fast object communication could be achieved by avoiding serialization. In this article, we present an experimental library called Expresso that provides efficient communications of Java objects.

Our transfer scheme does not need any memory copy nor graph traversal; objects are managed in clusters in order to allow the straight communication of the whole graph of objects. Section 2 describes two kinds of object clustering: the ISO-address scheme which leads to best performance and the relocatable scheme which offers more flexibility.

Of course these models imply that the data layout of the objects is accessible and so prevent us from developing a pure Java solution. We detail our implementation in section 3 and report some performances results. Current status and perspectives conclude this article.

Related Works

In the context of high performance networks, many researches on Java and message passing systems have been conducted in the last few years [START_REF] Forum | Java Grande Forum Report: Making Java work for high-end computing[END_REF][START_REF] Fox | Editorial: Java for high performance network computing[END_REF]. Most of them want to stick to the Java standards by providing an efficient RMI (Remote Method Invocation) mechanism and consequently an efficient object serialization. For example, in [START_REF] Philippsen | More efficient object serialization[END_REF], a pure Java solution is adopted that reduces the quantity of information that must be put in the buffer and optimizes buffer management. In [START_REF] Maassen | An Efficient Implementation of Java's Remote Method Invocation[END_REF], a native serializer, aware of objects layout, is automatically generated. Other works try to provide MPI facilities in the context of Java. If some early studies did not fully allow for graphs of objects, focus is now put on serialization by trying to extend MPI data-types with the OBJECT type [START_REF] Judd | Design Issues for Efficient Implementation of MPI in Java[END_REF][START_REF] Carpenter | Object Serialization for Marshalling Data in a Java Interface to MPI[END_REF]. Several distributed shared objects services have been proposed on top of Java libraries, e.g. in [START_REF] Hagimont | Javanaise: Distributed Shared Objetcs for Internet Cooperative Applications[END_REF][START_REF] Philippsen | Javaparty -transparent remote objects in java[END_REF]. Performance issues such as clustering of objects we use in our implementation have been pointed out. However, to our knowledge, there is no proposal that questions the principle of serialization when communicating graphs of Java objects.

Expresso

Expresso is a Java library that aims at providing objects exchange capabilities to an object oriented language as MPI or PVM provides values exchange capabilities to procedural languages through the message passing paradigm. Expresso does not introduce a new object distributed model; it is inherited from the MPI library upon which Expresso is built: a E -node network is seen as a set of processes numbered from 0 to E GF H¢ communicating on a fully connected network through send and receive operations. So only one thread of each Java virtual machine (JVM ) communicate with the others. Emphasis is on performance rather than on expressiveness: as mentioned in the introduction, very fast object transfer between two machines is achieved thanks to a direct memory to memory dump in replacement of the usual marshalling of structured values.

Object clustering

Simple and efficient communication is obtained through the clustering of objects. The allocation of the objects is controlled in order to maintain the entire representation of a graph of objects in a single memory region that can be easily transferred: the cluster. A set of clusters is managed in a specific memory area on each node. Virtual memory (not physical memory) is reserved for this cluster space. Enough space can be considered available given the size of the addressing space of a process (& gigabytes on current 32-bit architectures).

A cluster is the unit of communication on the network and it may contain many objects. Firstly it allows communication granularity management. Without clusters, one would have to explore the complete graph of objects to know which memory words have to be transferred (this is the serialization process); or conversely it would be necessary to transfer the whole cluster space of the emitting node (transferring one big chunk of several megabytes is too expensive, even on a high speed network). So the cluster is an intermediate whose size is somehow tunable. Moreover, it makes sense to group the representations of certain objects as this grouping reflects the logical grouping that frequently already exists in applications, even if it is often implicit.

Only objects that may be exchanged are allocated in clusters; the others are left in the heap managed by the JVM . Clusters are exchanged between nodes with asynchronous send and receive operations. As a cluster may contain several linked objects, one object -called the root object -acts as a handle to access the others indirectly. Some objects stored in a cluster may be out of the graph that is to be communicated, thus incurring extra data transfer. However, in the context of high-bandwidth networks, this should not be too expensive.

It should be noticed that our objective is not to propose a new programming model; as a consequence, coherency of inter-cluster references is not treated. We focus here on the transfer of a graph of objects contained in a single cluster.

Actually, Expresso provides two types of clusters that are stored in separated areas and may be used simultaneously: ISO-address and relocatable clusters. ISO-address clusters lead to better performances whereas relocatable clusters offer a more classical communication model. Both are described in the following.

ISO-address clusters

Expresso runs on a set of workstations connected through a high speed network. Computing resources are supposed to be homogeneous, from the hardware and the operating system and the JVM point of view. The principle of the ISO-address transfer is to put a transferable object on the receiver at the same (virtual) memory address as on the sender. In this way, references inside an object remain valid and do not need to be updated. Therefore an object transfer becomes a simple memory block transfer analogous to a DMA operation. The same kind of idea has been applied to thread migration in [START_REF] Antoniu | And efficient and transparent thread migration scheme in the PM2 runtime system[END_REF].

The key point is to manage the memory between the nodes to ensure that an object can be copied at the same address on another node without a crash. Any transferable object created on one a node has to be allocated in an reserved range of addresses for this node, within the ISOaddress cluster space. Figure 1 contains the ISO-address cluster space layout for a two-node network. In this case, the ISO-address space is divided into two parts: the higher one is devoted to the objects allocated on the first node; the lower one is devoted to the objects allocated on the second one.

Figure 1. ISO-address memory for a two-node network

The size of clusters are identical and fixed at initialization time. Thus the exact memory location of a cluster can be deduced from its identity and duplicated at the same address on another node without any calculation nor any cluster overlapping problem. Two numbers identify a cluster: its origin node -the node where it has been created -and its rank on this node.

Communications. ISO-cluster transfer is intended to be very efficient. On one side, the send operation transmits the entire content of a cluster to the destination node. On the receiving side, the cluster content is replaced by the incoming one. Therefore only one copy of a distant cluster is available at a time. Having received a cluster, a reference on the cluster root object can finally be obtained. Note that a receiving node is free to specify the node from which the cluster is awaited: it may or not be the origin node of the cluster; it may also be any node when the sender is not specified at all. This simple protocol doesn't take care of coherency between multiple copies of clusters. This is left under the programmer's responsibility or to an upper layer library.

Relocatable clusters

Relocatable clusters can be used in addition or as an alternative to ISO-address clusters. In some cases, they offer more flexibility at the cost of a slight computing overhead.

Relocatable clusters are dynamically allocated within a specific memory space The size of the clusters is specified at creation time and may be different for each cluster. Freeing relocatable clusters is done explicitly.

The use of relocatable clusters is identical to the use of ISO-address clusters. Once created, a cluster can be set as the current cluster where new objects will be stored. A relocatable cluster can be transfered to another node by using the send and receive operations. No numbering of clusters is necessary: a copy of a cluster is sent and a new cluster is created upon receipt. In this respect, relocatable clusters offer the usual message passing facilities. There is no coherency problem due to cluster overwriting as with ISOaddress clusters; still, inter-cluster references are not managed either.

Figure 2 depicts the layouts of the relocatable spaces in a two-node network after three cluster transfers. It can be seen that two copies of the second cluster on node 1 are received by node 0 after a possible modification. As mentioned earlier, this was not possible with ISO-address clusters.

Expresso API

ISO-address and relocatable clusters are implemented through a Java package. The main class of the package is the Cluster class. Two sub-classes (ClusterISO and ClusterRELOC) provide the implementation of the ISOaddress clusters and the relocatable clusters.

We present in figure 3 a brief example of a Java program using Expresso classes.

Figure 2. Relocatable memory for a two-node network

This program runs on a two-node network. A simple graph of objects (a car object referring to an engine object) is created on one side and sent to the other side where it is printed. As the same program runs on both nodes -this is the SPMD parallel programming model -a conditional tests the running node number to select the code to execute. The first node creates a cluster, allocates a car object inside it, fills it and sends it to the second node. The second node receives the cluster, extracts the car and prints it.

The class method Cluster.newObject must be used to create transferable objects in the current cluster. An object allocated this way is stored in the current cluster with the same structure as a Java object; the JVM can operate on it as on an ordinary object. All the others objects are allocated through the Java new operator.

A cluster can be sent to a node with the instance method send and received with the instance method recv. The destination of the message is a node number. When receiving a cluster, parameters are slightly different according to the type of clusters used. For ISO-address clusters, one should specify the cluster identity (i.e. the origin node and the rank) and optionally the number of the node from which the message is received if it is different from the origin node. For relocatable clusters, only the emitting node is required. In both cases, if the source of the message does not matter, ANY can be passed to the recv method in replacement of a node number. The recv method returns a handle to a newly created cluster -of the proper type -filled with the objects that were in the message.

Implementation

The main part of Expresso is written in C and is called by the interface through the JNI (Java Native Interface) mechanism. It is composed of a memory management module and a communication module. The implementation details of these modules are explained in the following subsections.

Memory management

Ordinary objects are normally allocated by the JVM in its heap located in the data segment of the Unix process. For Expresso needs, a memory space distinct from the JVM heap is required to host the ISO-address space and the relocatable space. The memory management module of Expresso asks the operating system a large zone within the part of the 0 I QP bytes of memory available to the process that is left free between the stack and the heap segment. Thus, at initialization time, a brk system call allocates two spaces. The first one is the ISO-address space; it is split up into as many chunks as the number of nodes. An extra chunk is also needed for the dispatch tables copies (see below). The second one is dedicated to the relocatable clusters. This last one is managed dynamically as a segmented memory.

The newObject method reserves a placeholder for an object in the current cluster. In the case of an ISO-address cluster, the allocation takes place within the pre-determined local part of the ISO-address space dedicated to the executing node. When the current cluster is a relocatable cluster, the object is added to the chained list of objects managed by the cluster. In both cases, the structure of the created object conforms to the running JVM machine implementation; so the JVM can apply any operation on it as on an object allocated by the new primitive. The current version of Expresso is bound to the Kaffe JVM implementation (version ¢ 9 £ (9 " )3 : figure 4 shows the layout of a Kaffe object. A header contains garbage collector and lock information, and a link to the object's dispatch table (for direct access to the object's methods). The object's fields reside in the words following the header. The memory management module of Expresso takes all the information needed to size the object structure and to fill the dispatch table reference from the class parameter of newObject. Figure 5 exemplifies the links between the ISO-address memory space, the relocatable space and the JVM objects heap; it represents a situation where several objects allocated via Expresso and via the JVM share the same class data.

The classes of the program are loaded by a custom class loader during Expresso initialization. Class data are allocated normally within the JVM heap but copies of the dispatch tables are placed in a dedicated zone within the ISO-address space. Every node load all the classes; consequently, the dispatch tables are allocated at the same address on all the nodes. So the dtable link between an object and its dispatch table is preserved during transfer and does not need any updating.

Communication management

The communication management module of Expresso runs over a Myrinet high speed network [START_REF] Boden | Myrinet -A Gigabit-persecond Local-Area Network[END_REF], from the Myricom company. Very low level communications are managed by the proprietary library GM (version ¢ 9 £ (¢ ). A MPI implementation upon GM (gm-mpich ) is also provided by Myricom. This communication layer offers all the message passing facilities needed to implement object transfer in Expresso.

Expresso methods recv and send are Java wrappers which call the C functions expresso_recv() and expresso_send() through the JNI mechanism. We have written these C functions using the underlying gmmpich library.

The send method call on one node and its recv method counterpart on another node, act as a memory block dump between the corresponding machines.

When receiving an ISO-address Cluster, the message content is written at the same virtual address which is computed from the cluster number and the origin node number (see paragraph 2.2). No extra calculation is required.

A few operations are necessary when receiving a relocatable cluster: a new cluster is allocated according to the size of the incoming message before the actual receipt. After receipt, the references contained in the objects of the cluster are relocated: the list of objects is traversed so that the reference fields of each of them are modified by a constant value (the difference between the address of the cluster on the emitting node and its local address) if they are not null. In order to avoid class introspection, an offset table for references fields is built when the class is loaded. This table is accessed through the dispatch table link of the object.

Although the set of objects received must be examined, relocatable clusters management offers important advantages over the classical serialization-unserialization process: no treatment is done on the sending side and on the receiving side, cycles in the graph are not considered, no object allocation is needed and no class references are manipulated.

Performances

We have experimented the Expresso library on a cluster of Linux PCs (Pentium II 400Mhz) linked by a 1 Gb/s Myrinet network (processor Lanai 4, PCI 33 Mhz interface adapter). In the following, we show performance figures of basic Expresso primitives and of an application program.

Object creation and access. The newObject method is slightly faster than the Java new primitive as we do not have to deal with the garbage collector. The difference between the use of ISO-address clusters and relocatable clusters is negligible. Of course, the time for accessing an object created by newObject is strictly identical to the time for accessing an object created by the new primitive since the JVM is not aware of the difference.

Cluster communication. We have compared the global cluster transfer time using Expresso with a classical method that builds a buffer with the standard Java interfaces Serializable and Externalizable before sending it with MPI (in Java). The graph of objects transferred is a random graph representing a map (towns, crossroads and roads linked to each other). Each object has four references. The average number of non-null references per object is about 2.5. Table 2 shows times in obtained with the three versions. It is clear that avoiding serialization leads to a dramatic improvement. Because we use a high bandwidth network, global performances are not really affected by the fact that the message is larger (twice the size of the message generated by the serializable version) in the case of Expresso. Indeed, the message contains the complete memory representation of the object and not only its attributes. Besides, the overhead induced by relocatable clusters, compared to ISO-address clusters stays relatively low, and does not change the comparison between cluster-based transfer and serialization-based transfer.

Application Even if ISO-address clusters are not primarily intended to be used at the application level, we have experimented their use in a parallel genetic programming application. A simple parallelization method has been applied to the sequential Java code (a block data distribution is performed at each step of the algorithm with a scattergather phase) [START_REF] Courtrai | Expresso : transfert d'objets Java sur réseau haut-débit[END_REF]. The objective was to compare the impact of the efficiency of objects communication in the overall parallel performance, not to obtain the peak performance by designing a parallel algorithm (namely load balancing issues are not really taken into account). The speedups obtained are presented in figure 6 for a 120-individual population. The efficiency of the code using serialization falls down rapidly when the number of nodes increases whereas it remains very correct with Expresso.

Conclusion

We have presented in this paper Expresso, a library dedicated to the transfer of complex Java objects. The allocation of objects is controlled so that objects belonging to the same graph are allocated in a cluster that consists in contiguous memory regions. Two types of cluster have been implemented, ISO-address clusters and relocatable clusters so as to fulfill a wider range of application needs. These clusters can be efficiently communicated because no serialization is required. This enables the full exploitation of the capabilities of high speed networks. Indeed, experimental results show that the transfer times for graphs of objects involving several types and containing cycles are very close to the times needed for a simple data transfer. These performance cannot be obtained with classical serialization whose relative costs can be considered prohibitive when using networks with low latencies and high bandwidth.

However, the communication library we proposed is at a very low level: the user has to handle the clustering of objects. It must be proposed a higher level programming paradigm that can take benefit of Expresso cluster exchanges. In this framework, we investigate how the RMI protocol can be built on top of Expresso. Another research direction is to integrate this kind of objects transfer in the JVM in order to develop object sharing between distant JVMs.

Figure 3 .

 3 Figure 3. Transfer of a simple graph of objects between two nodes with Expresso

Figure 4 .

 4 Figure 4. Object structure in the Kaffe virtual machine

Figure 5 .

 5 Figure 5. Links between memory spaces

Figure 6 .

 6 Figure 6. Speedup for a genetic programming application

Table 2 . Performances of Java API and Expresso

 2

The standard JDK API provides the Serializable and Externalizable interfaces in conjunction with the RMI mechanism for communication

purpose.[START_REF] Boden | Myrinet -A Gigabit-persecond Local-Area Network[END_REF] Technical characteristics of the experimental platform is given

in section 3

Kaffe is available from http://www.kaffe.org


Luc Courtrai

Yves Mahéo

Frédéric Raimbault

Expresso: a library for fast transfers of Java objects

Expresso is a Java library dedicated to cluster-based computing on a high speed network. It aims at providing objects exchange capabilities to an object oriented language as MPI or PVM provides values exchange capabilities to procedural languages through the message passing paradigm. Expresso does not introduce a new object distributed model; the emphasis is on performance rather than on expressiveness: very fast object transfer between two machines is achieved thanks to a direct memory to memory dump in replacement of the usual marshalling of structured values. We develop the ISO-address concept to manage the memory on the network nodes and implement it upon available communication libraries. Experimental results demonstrate a dramatic change in the objects transfer speed. Application programmers or higher level libraries are able to capitalize on such communication mechanism and to exploit the potential of high speed network even through an object language.

Introduction

Workstation clusters are emerging as the new parallel computing architectures. This is possible thanks to the relative low cost of local area high performance networks and the use of standard hardware for computing nodes. On the software side, the message passing paradigm has proven to be effective. It is widely adopted in the parallel an distributed programming community for its efficiency and the programmer is now provided with communication libraries that fully exploit the capabilities of high speed networks. However, widely used portable libraries such as MPI or PVM have been designed for procedural languages. C or Fortran programming is not sufficient for a range of novel high performance applications and object oriented languages offer a lot more comfortable environment for this kind of development. In particular, recent works show the interest in Java for cluster programming and the joint use of Java and message passing is the subject of numerous researches [START_REF] Grande | JGF Report: Making Java work for highend computing[END_REF].

One of the main issues is to handle efficiently the communication of objects. Since an object may have references to others objects, a graph of objects that possibly contains cycles must be communicated. However, the gap must be filled between the needed ability to send a whole graph of objects and the basic message passing functionality that consists in the transmission of a simple memory buffer.

The most common way to handle object communication is to apply a serialization on the sending side and an unserialization on the receiving side: the graph of references is explored and data representing each node of the graph is copied into a memory buffer that can be sent by the underlying communication primitive. A deep copy of the graph can be rebuild from the received buffer as far as enough type information is encapsulated in the message.

This method can be simply applied in Java by using the standard interfaces that allow an object to be serialized into a stream (so possibly an array of bytes). Marshalling relies on introspection mechanisms to automatically define the bytes array layout. Unfortunately, this shows very poor performance though the programmer may provide methods to specialize operations. Firstly, serialization in Java has been designed in a very general way in terms of portability and heterogeneity. For instance, the class of the object put in the message may only have a compatible equivalent on the receiving end. This increases the size of type information inside the buffer. Besides, many method calls and object creations are involved when marshalling and unmarshalling the graph of objects. This makes the serialization a very time consuming operation. This is especially disadvantageous in the context of high speed networks. Measurements show that the time required to build the buffer can be more than an order of magnitude longer than the time of pure communication [START_REF] Courtrai | Expresso : transfert d'objets Java sur réseau haut-débit[END_REF].

When designing communication protocols in low-level message passing libraries for high speed networks, efforts have been done in order to reduce computing overhead, namely through zero-copy strategies. We believe that these efforts must be extended to object communication in upper layer libraries. In some cases where heterogeneity and portability are not the prior concerns, fast object communication should be achieved by applying this zero-copy strategy. Of course, this implies that the data layout of the objects is accessible and so prevents from developing a pure Java solution.

In this article, we present an experimental library called Expresso that provides efficient communications of objects that do not rely on any serialization. The transfer scheme does not need any memory copy nor graph traversal. The allocation of objects is controlled in order to allow an ISOaddress communication of the whole graph of objects: a simple memory transfer through the network is sufficient.

Related Works

In the context of high performance networks, many researches on Java and message passing systems have been conducted in the last few years [START_REF] Grande | JGF Report: Making Java work for highend computing[END_REF][START_REF] Fox | Editorial: Java for high performance network computing[END_REF]. Some of them want to stick to the Java standards by providing an efficient Remote Method Invocation mechanism and consequently an efficient object serialization. In [START_REF] Philippsen | More efficient object serialization[END_REF], a pure Java solution is adopted that reduces the quantity of information that must be put in the buffer and optimizes buffer management. In [START_REF] Maassen | An Efficient Implementation of Java's Remote Method Invocation[END_REF], a native serializer, aware of objects layout, is automatically generated. Another objective is to provide MPI facilities in the context of Java. If some early work did not fully allow for graphs of objects, focus is again put on serialization by trying to extend MPI datatypes with the OBJECT type [START_REF] Judd | Design Issues for Efficient Implementation of MPI in Java[END_REF][START_REF] Carpenter | Object Serialization for Marshalling Data in a Java Interface to MPI[END_REF]. To our knowledge, there is no proposal that questions the principle of serialization when communicating graphs of Java objects.

Expresso

Expresso is a Java library dedicated to cluster-based computing. It aims at providing objects exchange capabilities to an object oriented language as MPI or PVM provides values exchange capabilities to procedural languages through the message passing paradigm. Expresso does not introduce a new object distributed model; the emphasis is on performance rather than on expressiveness: as explained in the introduction, very fast object transfer between two machines is achieved thanks to a direct memory to memory dump in replacement of the usual marshalling of structured values.

Expresso runs on a set of workstations connected through a high speed network. Computing resources are supposed to be homogeneous, from the hardware and the operating system and the Java virtual machine (JVM ) point of view. More technical details are given in the next section (section 3). In this section we focus on the ISO-address principle and its use for the transfer of objects. Then the Expresso API is presented and exemplified.

ISO-address transfer

The principle of the ISO-address transfer is to put the transferable objects at the same (virtual) memory address on the receiver as on the sender. In this way, references inside an object remain valid and do not need to be updated. Therefore an object transfer becomes a simple memory block transfer analogous to a DMA operation. The same kind of idea has been applied to thread migration in [START_REF] Antoniu | And efficient and transparent thread migration scheme in the PM2 runtime system[END_REF].

ISO-address memory

The key point is to manage the memory between the nodes to ensure that an object can be copied at the same address on another node without a crash. Any transferable object created on one a node has to be allocated in an reserved range of addresses for this node. Each node has such a separate memory so the whole set of memory parts forms what we call an ISO-address memory space. Figure 1 contains the ISO-address memory layout for a two-node network. In this case, the ISO-address space is divided into two parts: the higher one is devoted to the objects allocated on the first node; the lower one is devoted to the objects allocated on the second one.

It should be noticed that the ISO-address mechanism uses virtual memory reservation, not physical memory reservation. Besides, the size of the ISO-address space can be considered sufficient, given the size of the addressing space of a process (£ gigabytes on current 32 bits architectures).

Memory clusters

The ISO-address space is divided into consecutive chunks of memory called ISO-clusters. An ISO-cluster is the unit of communication on the network. It may contain many objects. The reason for the clustering is twofold:

1. It allows communication granularity management.

Without clusters, one would have to explore the complete graph of objects to know which memory words have to be transferred (this is the serialization process); or conversely it would be necessary to transfer the whole ISO-address of the sending node (transferring one big chunk of several megabytes is too expensive, even on a high speed network). So the cluster is an intermediate whose size is somehow tunable. 2. An another interest of clusters lies in the references between objects. References between two objects of different ISO-clusters may be broken if one object is accessed before the second is transferred. Only pointers confined to a cluster are safeguard against transfer.

The size of clusters are identical and fixed at initialization time. Thus the exact memory location of a cluster can be deduced from its identity and duplicated at the same address on another node without any calculation nor any cluster overlapping problem. Two numbers identify a cluster: its origin node -the node where it has been created -and its rank on this node.

Taking back to the previous example, the memory layout in figure 1 contains two clusters in the ISO-cluster space of node ¤ and three clusters in the ISO-cluster space of node ¥ , numbered from ¦ §¤ ©¤ to ¦ ¥ . On node ¤ , four linked objects have been allocated in cluster ¦ ¤ ¨ ¤ and three objects in cluster ¦ ¤ ©!¥ " . On node ¥ , one cluster contains two linked objects, the others are empty. Node ¥ memory also contains an object in cluster ¦ ¤ ©¤ transferred from node ¤ . Similarly node ¤ memory has received an object from node ¥ in cluster ¦ ¥ ¨ ¤ # . The communication protocol is explained below.

As a cluster may contain several linked objects, one object -called the root object -acts as a handle to access the others indirectly.

Communications

Objects that may be exchanged are allocated in clustersthe others are left in the heap managed by the JVM . Clusters are exchanged between nodes with asynchronous send and receive operations.

On one side, the send operation transmits the entire content of a cluster to the destination node. On the receiving side, the cluster content is replaced by the incoming one. Therefore only one copy of a distant cluster is available at a time. Once a cluster has been received, a reference to the cluster root object can finally be obtained. Note that a receiving node is free to specify the node from which the cluster is awaited: it may or not be the origin node of the cluster; it may also be any node when the sender is not specified at all.

This simple protocol doesn't take care of coherency between multiple copies of clusters. This is left under the programmer's responsibility or to an upper layer library.

Expresso API

The ISO-address concept described above is implemented through a Java package. The main operations are located in the ClusterISO class. A brief overview and a simple example follow.

Class methods and attributes

The class method init makes all the necessary Expresso initializations and reserves memory from the operating system for the ISO-address space. Parameters may be given to adjust the size of the clusters and others details. Class method quit marks the end of the use of Expresso. It releases the ISO-address space memory. The class field myNode contains (after initialization) the current node number in the network.

Clusters creation

Clusters must be created to store transferable objects. Creation of a new cluster is obtained through the class constructor ClusterISO. Only one cluster can be accessible at a time. One chooses the cluster in which future objects will be allocated by calling the instance method setCurrent.

Transferable objects allocation

The class method newObject must be used to create transferable objects. This method takes the class of the object as parameter and returns a handle on a Java Object that should be cast to the desired class. An object allocated this way is stored in the current cluster with the same structure as a Java object; the JVM can operate on it as on an ordinary object. When an array of objects is communicated, it must also have been allocated with a similar method (newArray) from ISO-cluster. All the others objects should be allocated through the Javanew operator. Two complementary instance methods set (method setRootObject) and get (method getRootObject) the root object of a cluster.

Clusters exchange

A cluster can be sent to a node with the instance method send and received with the instance method recv. The destination of the message is a node number. When receiving a cluster, one should specify the cluster identity (i.e. the origin node and the rank) and optionally the number of the node from which the message is received if it is different from the origin node. If the source of the message does not matter, ANY can be passed to the recv method in replacement of a node number.

Example

Figure 2 contains a simple illustration of the use of Expresso. This Java program runs on a two-node network. A binary tree is created on one side and sent to the other side where it is printed. As the same program runs on both nodes -SPMD parallel programming model -a conditional tests the running node number to select the code to execute. The first node creates a cluster, allocates a binary tree inside it, fills it and sends it to the second node. The second node receives the cluster, extracts the binary tree and prints it.

Implementation

The ClusterISO class described in the previous section is the user interface of the Expresso library. This section contains a picture of how things are implemented. Performance figures are given afterwards.

The main part of Expresso is written in C and is called by the interface through the JNI (Java Native Interface) mechanism. It is composed of a memory management module and a communication module. The implementation details of these modules are explained in the following subsections.

Memory management

Ordinary objects are normally allocated by the JVM in its heap located in the data segment of the Unix process. A memory space distinct from the JVM heap is required to implement the concept of ISO-address. The memory management module of Expresso asks the operating system for this ISO-address space within the very large part of the

Figure 2. Binary tree transfer between two nodes with Expresso

bytes of memory available to the Unix process that is left free between the stack and the heap segment (see figure 3).

At initialization time, the local ISO-address space is allocated by a brk system call. It is managed as explained in the previous section. Expresso splits it up into as many chunks as the number of nodes: each of these chunks is numbered and is dedicated to objects created on a particular node. An extra chunk is also needed for the dispatch tables copies (see below).

The Expresso newObject method reserves a placeholder for an object in the local ISO-address space part dedicated to the executing node. The structure of this object conforms to the running JVM machine implementation; so the JVM can apply any operation on it as on an object allocated by the new primitive. The current version of Expresso is figure 4 shows the layout of a Kaffe object. A header contains garbage collector and lock information, and a link to the object's dispatch table (for direct access to the object's methods). The object's fields reside in the words following the header. The memory management module of Expresso takes all the information needed to size the object structure and to fill the dispatch table reference from the class parameter of newObject. Figure 5 exemplifies the links between the ISO-address memory space and the JVM object heap; it represents a situation where several objects allocated in the ISO-address memory (a1, a2) and in the JVM memory (a3) share the same class data (data of class A). The classes of the program whose instances may be transferable are loaded by a custom class loader during Expresso initialization. For a given class, the class data (methods' code, attributes,...) are allocated normally within the JVM heap. Similarly, the dispatch table, which serves as an intermediate between the object reference and the methods' code, is loaded normally, within the JVM heap. At this stage, Expresso copies the dispatch table in a specific zone within the ISO-address space. Objects created with newObject contain a pointer to the copy of the dispatch table whereas objects created by the JVM contain a pointer to the original dispatch table. As every node load all the classes, the dispatch tables are allocated at the same addresses on all the nodes. So the dtable link between an Expresso object and its dispatch table is preserved during transfer and does not need any updating.

Communication management

The communication management module of Expresso runs over a Myrinet high speed network [START_REF] Boden | Myrinet -A Gigabit-persecond Local-Area Network[END_REF], from the Myricom company. Very low level communications are man- aged by the proprietary library GM (version ¥ ( ¤ ©¥ ). A MPI implementation upon GM (gm-mpich ) is also provided by Myricom. This communication layer offers all the message passing facilities needed to implement object transfer in Expresso. Figure 6 summarizes the communication layers stacking.

Expresso methods ClusterISO.recv and ClusterISO.send are Java wrappers which call the C functions expresso recv() and expresso send() through the JNI mechanism. We have written these C functions using the underlying gm-mpich library.

The send method call on one node and its recv method counterpart on another node, act as a memory block dump between the corresponding machines. On message receipt, words of memory are written at the same virtual address. which is computed from the cluster number and the origin node number (see paragraph 2.1).

Libraries

Performances

We have experimented the Expresso library on a cluster of Linux Workstation (Pentium 400 Mhz, kernel 2.0.36). The nodes are linked by a Myrinet network with PCI 33 Mhz interface adapters (processor Lanai 4) and a 8-port switch. In the following, we show performance figures of basic Expresso primitives.

Object creation and access

The newObject method is slightly faster than the Java new primitive as we do not have to deal with the garbage collector. Of course, the time for accessing an object created by newObject is strictly identical to the time for accessing an object created by the new primitive since the JVM is not aware of the difference.

Cluster communication

We have compared the global cluster transfer time using Expresso with a classical method that builds a buffer with the standard Java interfaces serializable and externalizable before sending it with MPI (in Java). With the first interface (serializable), serialization is automatically performed and relies on introspection mechanisms. With the externalizable interface, we had to implement the two methods writeObject() and readObject() that produces and exploits the serialized form of an object. The graph of objects transferred is a binary tree. Each node is composed of an integer and two references (to the left and right sub-trees). Table 1 shows times in 0 21 obtained with the three versions. The last two columns give the gain factor of Expresso.

Times for Expresso objects transfer are very close to those of a simple message passing by MPI since there is nearly no extra work to perform. This is obviously not the case when using the standard Java interfaces.

Conclusion

We have presented in this paper Expresso, a library dedicated to the transfer of complex Java objects. It allows clusters of objects to be efficiently communicated between two nodes thanks to an ISO-address transfer of the memory representation of the objects. No costly serialization is thus needed, bringing up performances that make possible the full exploitation of the capabilities of high speed networks.

Although Expresso should mainly be used by upper level libraries, it can also be used to program distributed applications directly. This way, we have written with Expresso a genetic programming application [START_REF] Courtrai | Expresso : transfert d'objets Java sur réseau haut-débit[END_REF]. The overall performances obtained show that a simple parallelization method can give good results as far as efficient object transfer is possible.

Our prototype can be improved in many ways. We should be able to provide object communication facilities at the thread level. This will be possible when underlying communication libraries fully support multi-threading. Another improvement would be to integrate the ISO-address space into the JVM .

More generally, the good performances of our prototype indicate that the use of a high performance network tends to question established methods tested for "slow" networks. Serialization for object transfer has been our prior concern. It appeared that the way objects are allocated is of importance. Similarly, other mechanisms should be examined to be adapted, regarding communication in a high performance network.

3 54 76 98 A@ CB ED %F GD %8 IH @ CP RQ 1 S @ CB "T VU W T 1 U X8 AW §@ Y a7Q V@ CB "b cU #W dT Ve U X8 AW §@ Y af 7B "@ 1 "1

Figure 1 .

 1 Figure 1. ISO-address memory for a two-node network

Figure 3 .

 3 Figure 3. Address space of a Unix process

Figure 4 .

 4 Figure 4. Object structure in the Kaffe virtual machine

Figure 5 .

 5 Figure 5. Links between memory spaces

Figure 6 .

 6 Figure 6. Communication layers

Table 1 . Performances of Java API and Expresso

 1 Dg h i p rq As tp vu Vq Rw §s th x 2y A i h u Iu V x cy ! h Ii q As tp vu Vq Rw §s th x 2y A i h u Iu V

	¥ C¤	¥ ¥ %¤ ¤	¨ ¤ ¤	©¥ !¤	) )	£
	¥ C¤ ¤	X¥ ¨ ¤ ¤	¥ C¤ ©¨ ¤ ¤	£ X ¤	£ #)
	¥ C¤ ¤ ¤	¥ R£ ©R¥ C¤ ¤	) X¨ ¤ ¤	¥ %¤ ¤	£	%¤
	¥ C¤ ¤ ¤ ¤	) ©¨ ¤ ©¤ ¤ ¤	¥ %¤ ©¤ ¤ ¤	¥ C © ¤ ¤	©¥ C	"£

Kaffe is available from http://www.kaffe.org


Julien Siebert
email: julien.siebert@loria.fr

Laurent Ciarletta
email: laurent.ciarletta@loria.fr

Vincent Chevrier
email: vincent.chevrier@loria.fr

Agents & Artefacts for Multiple Models coordination Objective and decentralized coordination of simulators

Keywords: Multiple interacting models, A&A paradigm, Data-driven coordination model, Decentralization

Complex systems simulation implies the interaction of different scientific fields. However, most of the time people involved into the simulation process do not know intricate distributed simulation tools and only care about their own domain modelling. We propose a framework (called AA4MM) to build a simulation as a society of interacting models. The main goal is to reuse existing models and simulators and to make them interact. The coordination challenges remain to the AA4MM framework so that the simulation design and implementation stay as simple as possible. In this paper, we present the coordination model which intends to decentralize the simulators interactions. We propose to use the environment through the notion of artefact in order to deal with the coherence, compatibility and coordination issues that appear in parallel simulations.

INTRODUCTION

A complex system is composed of a set of interacting parts that, as a whole, exhibits properties that cannot be predicted from the simple sum of the individual parts properties. Human economies, social structures, climate or ecosystems are good examples of complex systems. Equation based modelling cannot represent interactions among components and their impact on the global system behaviour. Multiagent approach offers an interesting alternative [START_REF] Van Dyke | Agent-based modeling vs. equation-based modeling: A case study and users' guide[END_REF] Complex systems modelling also involves the interaction of different scientific domains or different abstraction levels. In biology for example, in order to understand and to predict the impact of a molecule on a specific organism, both models from chemistry (chemical reaction) and biology (cellular, tissue, organ) are needed [START_REF] Southern | Multi-scale computational modelling in biology and physiology[END_REF]. This way, different specialists work on the same simulation. Each one brings its own models and simulators.

The challenge is then to allow those scientists to build a complex simulation from their own building blocks. Moreover, we should keep in mind that they are probably not familiar with the intricate modelling and simulation tools and theories. One way to facilitate the design and the implementation of such a simulation is to build it as a society of interacting models. Models should be seen as components we can weave together (as in component-based software engineering).

We propose a framework (called AA4MM) to build a simulation as a society of interacting models. The main goal is to reuse existing models and simulators and to make them interact. However, the main constraint is that people involved into the simulation process do not know intricate distributed simulation tools and only have to care about their own domain modelling. Coordination challenges remain to the AA4MM framework.

CHALLENGES AND RELATED WORKS

Contrary to the work in [START_REF] Quesnel | The virtual laboratory environment: A multimodelling and simulation framework[END_REF], where all models are integrated into DEVS formalism and run in a single simulator, we assume that each model has been created independently and implemented in its own simulator. Consequently, each model has its own representation of time and data. In the same way, each simulator proceeds its own execution. The following sections list issues that appear when coupling different models and simulators.

Coherence and compatibility issues

Coherence between models

Scales or dimensions in which a piece of data is represented could be different from a model to another. For example, a position: pos 1 = < x, y, z > (with x, y and z expressed in meters) in a first model can be represented only in two dimensions in a second one: pos2 = < x , y > (with x and y expressed in kilometers). A solution proposed in [START_REF] Bonneaud | Pattern oriented agent-based multi-modeling of exploited ecosystems[END_REF] is to define operations (projection, discretisation, reduction) in order to achieve this coherence.

Moreover, each model could have its own time representation. We need to assure, for example, that a time value t 1 ∈ R + in a first model correspond to a time value t 2 ∈ N in a second one. A possible solution is to express an operation that makes the correspondence between both time values.

Compatibility between simulators

Each simulator could implement a single piece of data in its own way (integer, float...) or some simulators may not implement all aspects of a given model. These challenges are discussed in [START_REF] Riley | A federated approach to distributed network simulation[END_REF]. A solution is to add an entity (a program) between the simulators. Its role is to translate the data in order to respect the compatibility between simulation tools.

Coordination issues

The goal of time management in distributed simulation is to ensure that simulation events (or steps) are executed in the correct order. Two main approaches have been proposed to coordinate interacting simulators: optimistic and conservative [START_REF] Fujimoto | Parallel simulation: parallel and distributed simulation systems[END_REF]. We assume that the existing simulators we reuse have been developed independently and where not thought for distributed simulations. So they do not have a roll-back capability (see optimistic approach): they cannot go back into the simulation process in order to take new input events into consideration. As a consequence, we focus on the conservative mode. In the latter, the coordination model has to determine when a simulation event (or step) is safe to process. Definition 2.2.1. For a model M i , a simulation event (or step) associated with the current simulation time ct i is said to be safe to process if all the input events received after this event execution are timestamped with a time value > cti.

Conservative coordination can be done by using a central and global scheduler that synchronizes all the simulators as in [START_REF] Bonneaud | Pattern oriented agent-based multi-modeling of exploited ecosystems[END_REF][START_REF] Riley | A federated approach to distributed network simulation[END_REF][START_REF] Kuhl | Creating computer simulation systems: an introduction to the high level architecture[END_REF]. These solutions prevent to easily reuse the existing models and simulators since they need substantial modifications in order to be controlled by the scheduler. Moreover, a global scheduler imposes a bottleneck that arduously allows the simulation to scale up in terms of either systems size or number of abstraction levels. In section 3, we remove this central scheduler and we propose a decentralized coordination model.

PROPOSAL

Hypothesis and requirements

We do not target on-line nor real time simulations, which directly interact with the reality. Instead we focus on a model that fits our initial requirements. We try to facilitate the design of a society of interacting models by suppressing the global scheduler and by modifying as little as possible the existing models and simulators used.

We propose to use objective coordination. That is, coordination does not rely on a single entity but is provided by the surrounding environment. This method is well known in the field of situated multiagent systems [START_REF] Van Dyke | Digital pheromone mechanisms for coordination of unmanned vehicles[END_REF][START_REF] Rupert | The web from a complex adaptive systems perspective[END_REF] (stigmergy) or in parallel systems [START_REF] Schumacher | Objective coordination in multi-agent system engineering: design and implementation[END_REF] (shared memory). This provides a way to loosely couple and to coordinate the interacting processes. In our case, the simulators interact through the set of data they exchange.

Validity interval and coordination

Description

Each model Mi holds a current simulation time value cti. The simulator Si knows the simulation time value for the next event to be processed nt i . When a model M i is executed, it produces data δ i at time ct i . These data δ i will not change until the next time M i is executed (at time nt i ). As a result, we can say that δ i are valid for the simulation time interval Γi = [cti, nti[.

A simulator can execute a model if the simulation event to process is safe (see definition 2.2.1). Then, the issue for the simulator is to know when an event is safe. It can be solved if the simulators exchange both the data and the corresponding validity interval: < δj; Γj >. Indeed, a simulation event is safe to process if and only if:

∀j = i : cti ∈ Γj
This way, the input data < δ j ; Γ j > are safe for the simulator Si and the latter can process the simulation event at time cti.

Properties

We have developed a formal specification (in event-B) of this coordination model. Describing the whole specification is out of the scope of this article. However, it is available in [START_REF] Siebert | Aa4mm coordination model: event-b specification[END_REF]. This formal specification is used to prove that coordination occurs between models and that the system is alive and deadlock free with k models (k ∈ N). A sketch of the proof, using reductio ad absurdum is presented hereafter.

Assume, within this coordination model, that a simulator S i is stopped at time ct i . It is waiting for input data < δj, Γj > from another simulator Sj (i = j). This simulator cannot send data because it is also stopped but at a time ct j < ct i . S j also wait for input data. Two cases appear. Either the simulator S j is waiting for input data from S i . In this case it means that S i is waiting for itself, that contravenes our assumption. Or the simulator Sj is waiting for input data < δ k , Γ k > from another simulator S k at time ct k < ct j < ct i with (i = j = k). In this case, we come back to the very first case. Since the number of simulators and the number of simulation events are assumed to be finite, and since ∀i : cti ≥ 0, we can show by recursion that the latter case means that initial conditions are not set correctly and then that the simulation cannot happen. This contravenes our initial assumption. We target the initial conditions on an example in section 5.2.

FRAMEWORK OVERVIEW

In this section, we present how the A&A paradigm is used to take up the coupling challenges and how it implements the coordination model.

Architecture

In agent oriented software engineering, agents are autonomous entities that interact with each other and with their environments in order to solve a given task [START_REF] Van Dyke | Agent-based modeling vs. equation-based modeling: A case study and users' guide[END_REF]. In the A&A paradigm [START_REF] Omicini | Artifacts in the a&a meta-model for multi-agent systems[END_REF], the artefacts are used to design and to implement the interactions. They can be seen as tools used by the agents. In the case of building a simulation as a society of interacting models and simulators, the agents are in charge of the models execution and they interact through some specific artefacts. The coupling-artefact allows the agents to exchange data. It is in charge of coherence and compatibility issues and it implements the coordination model. The model-artefact allows the agents to initialize, to execute the model, to send input data and to get output data. The figure 1 depicts this architecture. An implementation example is given in the section 5 and the corresponding agents and artefacts used are described by figure 4.

Artefacts functions

In A&A paradigm [START_REF] Omicini | Artifacts in the a&a meta-model for multi-agent systems[END_REF], artefacts hold functions that agents can use. In this section, we present details about the modelartefact and the coupling-artefacts.

Model-artefact

The model-artefact role is to allow the agents to operate on a given model. We propose 6 functions. Init() allows to create a model instance and to initialize it. Run() allows to run the simulation only for one step or for one event. Then, in order to exchange some data between models, next functions are getOutputData() and setInputData(). Finally, as they are needed for the coordination process, last functions are getCurrentTime() that returns ct i and getNextTime() that returns nt i (Cf 3.2).

Coupling-artefact

The coupling-artefact allows the agents to post() and read() data δi. However, this artefact also intends to prepare data and to filter them. Thus, the post() function adds the validity interval Γ i to the data δ i . The read() function includes the guard condition ct i ∈ Γ j to coordinate models. read() only returns valid and last produced data to the agent. Moreover, it is possible to add operations (as in [START_REF] Bonneaud | Pattern oriented agent-based multi-modeling of exploited ecosystems[END_REF]) in order to deal with coherence and compatibility issues (Cf 2).

Agents behaviour

The role of the agent (a model-agent in our case) is to run a specific task. The artefacts are tools it can use. The very first role of a model-agent is to execute the model and to read and post data. We distinguish three major phases. First, the agent has to create and initialize the artefacts it is going to use (at least one model and one coupling-artefact). Then, the agent manages the simulation process as describe on figure 2. It loops over the five steps. Finally, once the simulation is over, this agent can retrieve results and save them for analysis.

IMPLEMENTATION EXAMPLE

In this section, we present an example of a simulation made of different interacting simulators. We choose to use Netlogo [START_REF] Netlogo | Center for Connected Learning and Computer-Based Modeling[END_REF] since it is easy to understand and well known. Note that each model is executed independently in its own Netlogo instance, i.e. there are as many simulators running in parallel as interacting models. Implementation details and other use cases are discussed in section 6. The example is the following: assume we want to build a simulation of a sheepfold. We are interested into the influence between the sheep movements and the dynamic of sheep grazing. Models already exist for each dynamic [START_REF] Wilensky | Netlogo shepherds model[END_REF][START_REF] Wilensky | Netlogo rabbits grass weeds model[END_REF]. The first one M 1 , the sheep model, depicts the sheep movements: sheep move randomly, lose some energy and shepherds try to gather them. The second model M2, the grass model, represents sheep1 eating grass and gaining energy. We want these two dynamics to influence each other. That is, M 1 must send the sheep positions to M 2 while M 2 gives the sheep energy levels back to M1 (see figure 3). The architecture with A&A concepts is represented by figure 4.

Coordination of existing Netlogo models

Model artefacts design

In order to make both simulators S 1 and S 2 (and their own models M1 and M2) interact, we need to interface them by creating the model-artefacts (one for each). In 4.2, we define model-artefact functions. We implement them, without modifying the original models, by simply calling procedures through the provided Netlogo API.

For example, the functions of the model-artefact in charge of M 1 are designed as follows. The Init() function, that sets the number of sheep, shepherds and their initial positions in M 1 , is a call for the "setup" Netlogo procedure. The Run() function, that runs one simulation step of M 1 , calls the "go" procedure. getCurrentTime() and getNextTime(), that returns ct1 and nt1, report the number of "ticks" and "ticks + 1" (as we process simulation step by step). getOutput-Data() function, that returns the sheep positions δ 1 , reports all sheep present in the model and gathers their positions. setInputData() sets into M 1 the sheep energy δ 2 produced by M2. This is done by invoking the "set energy"Netlogo command on all the sheep in M1.

Coupling-artefacts design and architecture overview

Once the dependency network is done (figure 3), we can design the coupling-artefacts. We propose that each couplingartefact is in charge of only one set of data < δi, Γi >. In our example, one coupling-artefact, cA1, is in charge of sheep positions < δ 1 , Γ 1 >. The other one, cA 2 , is in charge of the sheep energy levels < δ 2 , Γ 2 >.

This way, the model-agent in charge of M 1 can post sheep positions < δ1, Γ1 > to cA1 and read sheep energy levels < δ2, Γ2 > from cA2 (Cf section 3.2).

Finally, we link each model-agent with its dedicated artefacts. Thus, the implementation strictly follows the initial dependency network. The whole architecture is represented in figure 4.

Model and simulators coordination

We saw on figure 3 that each model is waiting for data from the other one. In order to bootstrap the simulation, each model-agent must post initial data to the couplingartefacts. Initial sheep positions < δ 1 ; [0, 1[> and initial sheep energy levels < δ2; [0, 1[> have to be sent to their respective coupling-artefacts before the simulation process begins.

Then, the models execution follows the process described by figure 2. Once the model-agent 1 has read the sheep energy levels from the coupling-artefact 2, it sends them to the sheep model-artefact, executes M 1 , gets the sheep positions and posts them to the coupling-artefact 1. On the other side, the model-agent 2 reads and sends the sheep positions to the grass model-artefact, executes M2, gets sheep energy levels and posts them. In fact model-agents wait for each other and synchronize themselves thanks to the exchanged data δ i present in their environment.

Scales differences

Until now, we have assumed that time and space scales in both models M1 and M2 were the same. In the next sections, we present how that framework is useful to make models with different scales interact.

Different space scales

It may not be necessary to represent grass as precise as sheep are. That is, one patch of grass may correspond to a square of 2 × 2 patches in the sheep model M1 (Cf figure 5). Since it is not possible to change the patches size in the grass model M 2 , sheep positions produced by M 1 does not fit anymore with space in M 2 . As a consequence, we need to add an operation in the coupling-artefact cA 1 when the grass model-agent reads the sheep positions. This operation consists in dividing each sheep position coordinates by a factor 2.

Here, we target a challenge due to the exchanged data

Different time scales

The grass model M 2 may no longer be executed step-bystep but 2 steps by 2 steps; while the sheep model execution remains step-by-step (Cf figure 6). This is related

DISCUSSION

All the framework has been developed in Java since it makes Java Messaging Service platform2 and Netlogo integration easier. JMS platform is used for shared memory purposes. In this article, we present an example based upon the Netlogo platform that makes only two simulators (and their models) interact. Due to space constraints, we do not present all the features allowed by that framework. Indeed, coupling and synchronizing the model-agents through their environment deeply simplify the addition of a new model. We have made experiments with three Netlogo models (both M 1 and M 2 plus a model of wolves predation).

Changing the dependences between the models is also simplified by the use of one coupling-artefact for each kind of dependence. That is, if M 1 and M 2 both depends on the data δ 3 provided by a third model M 3 , we just need to build a coupling-artefact in charge of δ3. M1 and M2 will read that data from this new coupling-artefact.

In this article, we only talk about step-by-step simulation. We currently work on mobile ad hoc networks (MANET) simulations in which an event-driven simulator interact with a step-by-step multiagent simulator. The coordination model is exactly the same as the one described here. No additional modification is needed in order to integrate an event-driven simulator into the AA4MM framework.

The technical details, the examples and source code are available on the framework webpage3 .

CONCLUSION

We propose a framework (called AA4MM) to build a simulation as a society of interacting models. The main goal is to reuse existing models and simulators and to make them interact. However, the main constraint is that people involved into the simulation process do not know intricate distributed simulation tools and only care about their own domain modelling. That is, coordination challenges remain to the AA4MM framework.

In this paper, we present the coordination model in order to decentralize the simulator interactions. We propose to use the through the notion of artefact in order deal with the coherence, compatibility and coordination issues that appear in parallel simulations. We have developed a framework that intends to deeply simplify the simulation of complex systems by easily building a society of interacting models and simulators.

We do not target the implementation performances. Indeed, parallel simulations have the advantage of theoretically scaling up. Large size systems or numerous abstraction levels may be simulated. However, the data exchange between simulators can cause a huge overhead and can slow down the whole simulation. These scalability issues are plan as future work.

We do not mention the open system consideration. That is, we only focus on different interacting models where agents do not enter or leave their model. We think that when an agent leaves, enters or goes from one model to another, exchanging data is not sufficient. We plan to extend our framework in order to deal with that issue. The challenge here is to respect our requirements of coordination via the environment.

This work has been motivated by our initial studies on the interactions between humans behaviour and dynamic networks. Since we have now the tools to reuse existing models and simulators, we plan to focus on the experiments in this domain.

Figure 1 :

 1 Figure 1: Architecture overview

Figure 2 :

 2 Figure 2: A model-agent managing the simulation process

Figure 3 :

 3 Figure 3: Sheep -grass models dependency network

Figure 4 :

 4 Figure 4: Sheep and grass models implementation

Figure 5 :

 5 Figure 5: Sheep and grass models spaces correspondence

Figure 6 :

 6 Figure 6: Sheep and grass models execution times correspondence to the model execution process. So we modify the grass model-agent Run() and getNextTime() functions. That is, instead of calling the "go" Netlogo procedure only once in the Run() function, the model-agent calls it twice. Then get-NextTime() returns now the number of "ticks + 2". These are the only modifications to do since the coordination occurs only thanks to time values given by getCurrentTime() and getNextTime() functions.

Originally rabbits, we changed species.

Java Messaging Service. http://java.sun.com/products/jms/

http://www.loria.fr/∼siebertj/aa4mm/aa4mm.html

joris.rehm@loria.fr; MOSEL Team, LORIA.

virginie.galtier@supelec.fr; Supelec Metz.

ACKNOWLEDGEMENTS

The authors would like to thank the ANR SARAH project and La Region Lorraine for their financial support. Coordination formal specification in event B has been developed in collaboration with Joris Rehm 4 . JMS implementation has been done in collaboration with Virginie Galtier 5 .


Marc Le Fur

Yves Mah

E cient C o m m unications in Parallel Loop Distribution

published or not. The documents may come

Introduction

In the framework of the compilation of Hpf-like languages on distributed memory parallel computers, the distribution of regular parallel loops is studied extensively 9, 4, 1, 5, 6, 10]. Indeed, this kind of loops composes most computation-intensive parts of scienti c applications and contains a great amount o f p o t e n tial parallelism. The techniques embedded in data-parallel compilers are often based on the owner-computes rule: e a c h processor modies only the variables assigned to it by the user-speci ed distribution. For regular parallel loops, the compiler usually produces a Spmd target code composed of a communication code, during which distant data are received from other processors, and a computation code.

In this paper, we focus on the generation and on the e cient execution of the communication code and address the problem regarding both its compile-time and run-time aspects. Indeed, communication optimizations (vectorization, aggregation, etc.) are often described at a high level in the literature through send or receive sets. However, in order to obtain performances, the gap between sets and communication bu ers has to be lled in a non naive w ay. Run-time implementation strategies have a great importance therein.

Our approach applies to parallel loop nests with one statement, a ne loop bounds and array subscripts. Regarding data distribution, it is assumed that each distributed array is partitioned into rectangular blocks of equal dimensions (known at compile-time) but any mapping for these blocks is supported. In Hpf, t h i s h ypothesis encompasses for instance arrays distributed onto an abstract processor structure using the DISTRIBUTE directive. Thus each dimension of the array can be distributed with CYCLIC(k), CYCLIC, BLOCK or BLOCK(k).

The techniques we propose here have been implemented i n t h e Pandore environment 3], which is dedicated to the compilation, the execution and the observation of programs written in C-Pandore or in a subset of Hpf. One of the originalities of Pandore lies in the separation between the compilation scheme and the management o f distributed arrays. Both the compile-time and the run-time techniques bene t from this array management for communication optimization.

The paper is organized as follows. Section 2 recalls the distributed array management used in Pandore. The basic principles of our communication code generation for parallel loops is explained in section 3. An enhancement of this basic method is then presented in section 4 it reduces the complexity of the description of communication sets by taking advantage of the layout of distributed arrays.

Distributed Array Management

In the Pandore environment, distributed arrays are managed by a software paging system. The run-time uses the addressing scheme of standard paging systems but is not a virtual shared memory: the compiler always generates communication when distant data are needed, so we do not need to handle page faults.

The array management is based on the paging of arrays: the multi-dimensional index space of each array is linearized and then broken into pages. Pages are used to store local blocks and distant data received. If data have to be shared by t wo processors, each processor stores a copy of the page (or a part of the page) in its local memory. Array elements are accessed through a table of pages allocated on each processor.

Principle

To access an element referred to by an index vector (i 0 : : : i n;1 ) in the source program, a page number and an o set (PG and OF ) are computed from the index vector with the linearization function L and the page size S: PG = L(i 0 : : : i n;1 ) div S OF = L(i 0 : : : i n;1 ) mod S. F o r a g i v en distributed array, the page size S and the linearization function L are computed by the compiler so that the evaluation of PG and OF is e cient. Time consuming operations are avoided by u s i n g p o we r s o f t wo, turning integer division, modulo and multiplication into simple logical operations (shifts and masks).

For this, the compiler rst choose the dimension in which the size of the blocks is the largest. Function L is the C linearization function applied to a permutation of the access vector that puts index number in last position. The page size S is then de ned by the following (s is the block size in dimension ): if s is a power of two or dimension is not distributed, S is the smaller power of two greater than s otherwise S is the largest power of two less than s . Moreover simpli cations in the expression of PG and OF are performed when the is a non-distributed dimension. Figure 1 illustrates this paging in the 2D case.

Actually, an optimized computation of (PG,OF ) i s a c hieved by a voiding the explicit computation of the linear address L(i 0 : : : i n;1 ): we express PG and OF directly as a function of the index vector, thus, when dimension is not distributed, mod and div operations are removed. A more detailed description of this array management can be found in 8].

Bene ts

With this software paging, access times remain very close to those without index conversion. The memory overhead induced does not exceed a few percents for most distributions it is almost entirely due to the tables of pages: when a page contains elements that have no equivalent in the original sequential space, or when just a part of a distant page is accessed in a loop, only a portion of the page is actually allocated. Moreover, paging distributed arrays o ers several worthwhile characteristics. First, the scheme is always applicable as it is independent of the analysis of the code: it only depends on distribution parameters. The scheme is uniform: as far as accesses are concerned, no di erence is made between local elements and distant elements previously received. Finally, the memory contiguity is preserved in the direction of the pages: contiguous elements of the original array are still contiguous in the local representation. This facilitates the exploitation of caches and vector processors and helps to optimize communications as it will be shown later.

Basic Communication Code for Parallel Loops

Let us brie y explain the principle of our communication code generation through the example given in gure 2. Loop bounds and array subscripts but also the distribution of arrays A and B are analyzed by the compiler. The generated code comprises two parts: a communication part |in charge of pre-fetching non-local data from other processors| followed by a computation part. The communication code is itself divided into a send code and a dual receive code. The basis of each code consists in the scanning of a polyhedron 7] that characterizes the set of data associated with B j i + j ; 2] that must be exchanged between processors.

In the analysis of array distributions, only the partitioning into blocks is considered by the compiler. In the example, array A is divided into 8 blocks of size 500 4000 whereas array B is decomposed into 8 blocks of size 4000 500. The mapping of the blocks (CYCLIC in the example) is taken into account at run-time through guards depending on the processor identity. The send code generated by the compiler is given in gure 3.

In this code, the (i j)-loop describes the set Block send set(A k A B k B ): the set of elements of block n umber k B of B that must be sent to the owner of block n umber k A of A straightforward implementation of the run-time primitive elt send consists in a simple send of the element B j i + j ; 2]. This is not a satisfactory solution because it leads to a great number of small messages, and so to a prohibitive latency cost. One can think optimizing this implementation by aggregating all the elements to be sent from a processor to another. In this case, the primitive elt send adds a couple (address, value) to a bu er that can be sent at the end of the (i j)-loop. This reduces the number of messages but several drawbacks remain. First, the number of data transferred is not optimal since an address has to be attached to each element. Second, it necessitates memory copies between local representations of arrays and communication bu ers (packing/unpacking). The fact that intermediate communication bu ers are allocated constitutes also a memory overhead.

Moreover, in these two solutions, the time spent in the description of the send set is high since the scanning is performed element-wise.

To summarize, an e cient communication code needs to reduce memory overhead (communication bu ers, etc.) and the time passed in: the description of the communication sets the packing/unpacking of the communication bu ers the e ective data transfer (i.e. the number of messages and their size must be minimized). Minimizing all these parameters may be contradictory: for instance, a coarse description of send sets (e.g. surrounding rectangular sections) can be rapidly performed but is likely to bring about transfers of useless elements. Therefore, it is clear that a compromise must be reached that allows for the layout of arrays and that involves both the compiler and the run-time system. Next section presents such a compromise that is implemented in the Pandore environment.

E cient Communication Code for Parallel Loops

A solution for optimizing communications consists in sending supersets of send sets, while exploiting the memory contiguity i n t h e l a yout of distributed arrays. The choice adopted in Pandore consists in transferring the convex-hull of each send set associated with a pair of blocks i.e., for the example of gure 2, the convex-hull of each Block send set(A k A B k B ). Thus, in the general case, Send set(B p p 0 ) is a non necessarily disjoint union of convex-hulls.

Enhancing the Compilation Technique

Allowing for the memory contiguity ( i.e. the direction of pages) and representing send sets by their convex-hulls nd their expression in the de nition of new polyhedrons at compile-time. See 3] for more details about the static analysis performed to construct these polyhedrons.

The communication code obtained for the example given above is shown in gure 4.

It comprises three parts:

The rst one computes, on a given processor p, the set of processors p 0 that must receive data from p and for each p 0 , a description of Send set(B p p 0 ). In the second part, each processor p determines the set of processors that will send distant data to p. There is no computation of any receive set here since the description of the send sets will be included in the messages received by p. The third part is only a call to a run-time routine that is in charge of the interprocessor communications according to the di erent sets computed in the previous parts. As it can be seen on the code, the scanning of the convex-hull of a Block send set(A k A B k B ) is performed e ciently |no longer element-wise| by e n umerating its extremal points in a given direction. The (i j)-loop of gure 3 has been replaced by a single loop scanning the columns of array B, since the pages of B are column-wise oriented. For a given column v, the routine portion_pack adds a portion of column v (B u inf::u sup v]) to the current Send set(B myself p A ). Moreover, in this example, the convex-hull is exact since the linear part of the access function of reference B j i + j ; 2] is unimodular, which is generally the case in regular scienti c applications.

Enhancing the E ective D a t a T ransfers

The notion of segments is used to reduce the amount of memory needed for the storage of the description of send sets. It also permits data transfers to be and optimized. A segment is a contiguous set of elements within a page. It is represented by a triplet (pg, ofs, ofe) w h e r e pg is the page number and ofs (resp. ofe) is the o set of the beginning (resp. the end) of the segment. In gure 4, the call portion_pack(B v uinf u sup pA) adds the segments intersected by the portion of column B u inf::u sup v] to the list of segments to be sent t o pA. Only one segment per page is memorized in this list this segment is de ned by the convex union of the segments within the page. This mechanism ensures that an array element is recorded only once and prevents from redundant transfers, notably in the case of multiple right hand side reference to the same array.

The routine exchange(B) performs the sends and the receives of all the segments related to B. Segments are communicated di erently according to their size. Small segments are aggregated in a unique message whereas direct communication is used for big segments. In the latter case, the segment is transferred in a single message directly from the page on the sender side to the page on the receiver side, without any p a c king/unpacking. The threshold between small and big segments is determined from platformspeci c parameters such as the message latency and the memory copy bandwidth. In the current implementation of exchange, all the sends are performed prior to all the receives. A more asynchronous solution may b e e n visaged in which c o m m unication overlaps the construction of bu ers for aggregation.

This approach leads to a good compromise between the number of messages, the total amount of data transferred, the memory overhead and the time required for packing/unpacking bu ers.

Conclusion

In this paper, we h a ve presented original techniques for the generation and the e cient execution of communication code for parallel loop nests. The problem has been studied through its two components: on one hand, the generation of a fast description of communication sets by the compiler and, on the other hand, the implementation of e cient transfers at run-time. Both take i n to account t h e c haracteristics of the distributed array management, notably the memory contiguity.

These optimizations have been integrated in the Pandore environment. They lead to good performances for a number of numerical applications 2]. Figure 5 shows the speedups obtained on the Jacobi kernel on the Intel iPSC/2 and on a network of workstations.

Although the approach w e h a ve presented here applies to Hpf direct distributions, we are currently investigating the adaptation of our array management and of our static analysis in order to allow for alignment.

Figure 1 :

 1 Figure 1: Paging of 2D arrays

Figure 3 :

 3 Figure 2: HPF Source code

Figure 4 :

 4 Figure 4: Optimized communication code

Figure 5 :

 5 Figure 5: Speedups obtained on the Jacobi kernel