Madalina Olteanu
email: madalina.olteanu@univ-paris1.fr

Esther García-Garaluz

Miguel Atencia

Gonzalo Joya

Modelling dengue epidemics with autoregressive switching Markov models (AR-HMM) ⋆

In this work, autoregressive switching-Markov models (AR-HMM) are applied to the dengue fever epidemics (DF) in La Havana (Cuba). This technique allows to model time series which are controlled by some unobserved process and finite time lags. A first experiment with real data of dengue is performed in order to obtain the characterization of different stages of the epidemics. The aim of this work is to present a method which can give valuable information about how an efficient control strategy can be performed.

Introduction

Since the eighteen century, mathematical models of infectious diseases have been developed and used for providing information to health authorities [START_REF] Blower | An attempt at a new analysis of the mortality caused by smallpox and of the advantages of inoculation to prevent it: 1766[END_REF]. During the 60s, the improvements in the prevention programs turned the research interests in the industrialized countries to other diseases. However, during the last few years dengue fever (DF) has become a major health problem affecting tropical and sub-tropical regions around the world, especially urban and suburban areas [2]. Thus, the question of modelling infectious diseases arose again. For health authorities, a well fitted mathematical model may help in figuring out new strategies for an efficient fight against the epidemics.

In this paper, a method based on hidden Markov models is described. For vector-borne diseases, this is a very suitable technique since it enables characterization of unknown processes. The method presented herein allows to take into account finite-time feedback as well. This is an interesting feature since incubation and transmission rates may be considered. The rest of the paper is organized as follows: in section 2, the autoregresive switching-Markov model (AR-HMM) is described. Section 3 presents the features of dengue fever epidemics. In section 4, AR-HMM is applied to real data of dengue fever epidemics. Finally, in section 5, conclusions and future work are proposed.

Autoregresive Switching-Markov models

In some cases, time series may be explained not only by their past values, but also by some unknown, random process. Typical examples are economic cycles (recession and growth periods) or DNA identification (coding and non-coding regions). For these examples, the observed series will depend on the "state" or the "regime" of the unknown, hidden process. Usually, the hidden process is supposed to have a finite and fixed number of regimes, corresponding to the expected states of the phenomena to be modelled (for example, recession versus growth periods)

Notations and definitions

Let us start by introducing hidden Markov chains (HMC) and recall the definition.

A bivariate process (X t , Y t ) t∈Z is a hidden Markov chain if:

-(X t ) is a homogeneous Markov chain valued in a finite state space E = {e 1 , ..., e N }, N ∈ N ⋆ , with transition matrix A = (a ij ) i,j=1,...,N ,

a ij = P (X t+1 = e j | X t = e i ) -(Y t ) valued in R d , d ≥ 1, conditionally independent w.r.t. (X t ) and L (Y t | X t = e i ) ≡ L i .
The hidden Markov chain is described in Figure 1.

a . . . . . . . . . . . . Y 1 2 Y X2 X1 X t-1 Yt-1 Y t Xt X X t-1 t

Fig. 1. Representation of Hidden Markov chains (HMC)

Hidden Markov models were introduced by [START_REF] Baum | Statistical inference for probabilistic functions of finite state Markov chains[END_REF] in 1966. They soon became essential tools in speech-recognition ( [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF], [START_REF] Bourlard | Connectionist speech recognition: a hybrid approach[END_REF]), bioinformatics and analysis of biological sequences ( [START_REF] Durbin | Biological sequence analyses: probabilistic models of proteins and nucleic acids[END_REF]). Hidden Markov models have been already used for modelling epidemics data, with promising results ( [START_REF] Rath | Automated Detection of Influenza Epidemics with Hidden Markov Models[END_REF]).

Hidden Markov chains may be generalized by letting Y t depend on its past values and on X t . This new class of models may be defined as an autoregresive switching-Markov model (AR-HMM). AR-HMM were initially proposed in [START_REF] Hamilton | A New Approach to the Economic Analysis of Nonstationary Time Series and the Business Cycle[END_REF] and were extensively used in the sequel for modelling financial and economic time series. However, to our knowledge, there are no current applications for epidemics data.

An autoregressive switching-Markov process is a bivariate process (X t , Y t ) t∈Z such that:

-(X t ) is a homogeneous Markov chain valued in E = {e 1 , ..., e N }, N ∈ N ⋆ , with transition matrix A = (a ij ) i,j=1,...,N , a ij = P (X t+1 = e j | X t = e i ) -Y t = F Xt (Y t-1 , ..., Y t-p ) + σ Xt ε t -F ei is a parametric function (linear or nonlinear) depending on some θ i -σ ei ∈ {σ 1 , ..., σ N } ⊂ R ⋆ + N and (ε t ) is an iid sequence
We will suppose that the noise ǫ t is a standard Gaussian. The parameter to be estimated contains the transition probabilities of the hidden Markov chain, the parameters in the regression functions and the standard deviations for the noise:

Θ = (a ij , θ i , σ i , i, j = 1, ..., q)
The size of the parameter Θ is q(q -1) + dq An autoregresive switching-Markov model is represented in Figure 2. The estimation procedure may be summarized as follows:

+ q = q 2 + dq. Y Y Y X X X X ... ...
1. First, the user has to set the number of regimes, q, the number of time lags, p (p may be chosen using some AIC/BIC information criteria or by cross-validation) and the type of regression functions (linear, MLP, ...). 2. The parameter Θ is estimated using the EM-algorithm (see [START_REF] Rynkiewicz | Estimation of Hybrid HMM/MLP models[END_REF] for more details). A first characterization of the regimes (stability, influence of the past values,...) will be done using these results. 3. With the estimated values of the parameters, one may compute the posterior probabilities of belonging to each of the regimes, at any moment. These probabilities will allow the a posteriori identification and characterization of the regimes.

Dengue Epidemics

Dengue Fever (DF) and Dengue Haemorragic Fever (DHF) are infectious diseases transmitted to humans by the bites of Aedes mosquitoes. If a mosquitoes bites a Dengue Fever infected, it gets the disease and, after an incubation period, is capable of transmitting the infection to other people. That kind of disease, where an infectious organism that does not cause diseases itself transmits infection by contact among different hosts, is called a vector-borne disease [2] and Aedes mosquito is the vector. The disease of Dengue fever shows a resurgent pattern worldwide in the last years, becoming one of the most important health problems in subtropical countries. WHO estimates [2] there may be 50 million dengue infections every year in the world, and two fifths of the world population are now at risk of Dengue. In the Americas more than 890 000 cases of Dengue fever were reported, of which 26 000 was of Haemorragic Fever.

There is not vaccine against dengue fever. Besides, people who suffer dengue are immune against that dengue strain. For these reasons, Dengue fever is frequently described as an epidemic SIR model for a short or medium-term model (under the assumption that only one strain of the virus exists). In this model the whole population is classified in three groups: susceptible, infected an recovered people. Susceptible people are those who are not immunized against the disease and do not present symptoms. Infected people are who present symptoms of the disease. Recovered are those who got the disease in the past and are immunized against it.

Several models have been proposed for dengue fever which depend on the vector population [START_REF] Esteva | A Model for Dengue Disease with Variable Human Population[END_REF], [START_REF] Coutinho | Threshold Conditions for a Non-Autonomous Epidemic System Describing the Population Dynamics of Dengue[END_REF]. This becomes an important limitation since generally it is not possible to have enough real information about it. On the other hand, dengue fever, as most biological processes, has a feedback which affects the system in a finite time way. This is the case of human and mosquito incubation periods or recovering rate.

The ability to model systems in which the influence of an unknown process appears and with a finite-time feedback make an utoregresive switching-Markov model specially suitable for dengue fever characterization.

A first attempt to model Dengue epidemics using HMM-AR

A first toy model

In order to perform the experiment, a 274-day register of new infections for Dengue Fever in La Havana is aavailable From that database and the known recovering rate of the disease, the time series for the global number of infected people was obtained (Figure 3). In it, the decrease periods are related with the fumigation programs performed by the health authorities. One of the important considerations is the time lags in the experiment. Because of the incubation rate of human and mosquito lags between 8 and 15 days are considered.

For these epidemic data, we shall test three regimes: epidemics, non-epidemics and decrease periods. In all cases, each regime will be characterized a posteriori using these estimated probabilities. In the Figure 4 the probability of every regime is plotted.

From the whole results the obtained regimes can be characterized. The first and third regimes represent the non-epidemic and the epidemic periods respectively. Besides, it is necessary that the epidemics reach a high enough incidence to be removed. The decrease period is represented by the second regime.

Conclusion and future works

In this work the aautoregresiveswitching-Markov model is described. This modelling technique is applied to an epidemiological model of dengue fever. Autoregresive switching-Markov model is specially intended for model it because of its ability to consider both finite feedback and the influence of hidden process. An experiment with a real data-base of the dengue epidemics in La Havana (Cuba) has been made. The results enable the characterization of three different regimes: the epidemic, the no-epidemic and the decrease period. Some ideas can be iinferredform the results, among them, that a high enough value of the epidemic prevalence is necessary in order to reach the non-epidemic state.

Some future works can be proposed. The next step is to test other configurations with different lags of time and different regression functions. The consideration of vertical transmission of dengue, that is, the transmission form the female to the eggs would be interesting as well. On the other hand, another future work line is extracting information from the available data with this technique in order to develop more efficient fumigation strategies. It would allow to perform prevention measures while the prevalence of the disease is still reduced.

Fig. 2 .

 2 Fig. 2. Autoregresive switching-Hidden Markov Model (AR-HMM)

Fig. 3 .Fig. 4 .

 34 Fig. 3. Number of Dengue infected individuals in Havana (Cuba)

⋆

  This work has been partially supported by the Agencia Española de Cooperación Internacional para el Desarrollo (AECID), project no. D/017218/08. Thanks are due to Dr. Hector de Arazoza for his useful suggestions and, in particular, for providing the model of Dengue epidemics. The authors are grateful to Dr. Joseph Rynkiewicz for the REGRESS software.


Lionel Brunie

Laurent Lefèvre

Modèle de mémoire distribuée-partagée pour machine massivement parallèle

Actes des 6 es francophones du parall elisme, RenPar'6, L. Boug e ( r ed.), ENS Lyon, France, 6{10 juin 1994. 1 Mod ele de m emoire distribu ee-partag ee pour machine massivement parall ele Lionel Brunie Laurent Lef evre e-mail:(lbrunie,llefevre)@lip.ens-lyon.fr L.I.P., ENS Lyon,46,all ee d'Italie,69364 LYON Cedex 07 Deux classes d'architectures se confrontent dans le monde des machines parall eles MIMD. La premi ere est celle des machines a m emoire partag ee dans laquelle tous les processeurs ont a c c es a une seule m emoire physique. Beaucoup de ces machines sont limit ees en nombre de processeurs mais leur programmation est facile (pas de phases de communication). A l'inverse, les machines a m emoire distribu ee peuvent i n t egrer un grand nombre de processeurs, elles permettent ainsi d'atteindre de bonnes performances. Mais la programmation d'applications sur ces machines est di cile toutes les communications etant a l a c harge de l'utilisateur. Un compromis logiciel entre ces deux types de machines est un syst eme a b a s e d e m emoire partag ee-distribu ee. Par l'ajout d'une couche logicielle, ce mod ele o re, ainsi, la facilit e de programmation des machines a m emoire partag ee tout en utilisant l'e cacit e des machines a m emoire distribu ee.

N eanmoins la plupart des syst emes de m emoire distribu ee-partag ee ( a base de pages comme a base d'objets) ne supportent qu'un nombre r eduit de processeurs pour être encore e caces.

Cet article pr esente un mod ele de syst eme de m emoire partag ee-distribu ee a base d'objets partag es adapt e a l'impl ementation sur une machine massivement parall ele. Ce mod ele comporte deux classes de processus, ceux qui ex ecutent l'application et les processus d edi es a l a gestion des objets partag es. Le syst eme doit eviter au maximum les communications globales qui bloquent l'ensemble des processus. On peut ainsi envisager deux types de partitionnements (domaines d'objets ou groupes de processus) pour r eduire volume et distance des communications n ec essaires a la gestion de nos objets partag es. On d e nit le domaine d'un objet comme l'ensemble des processus qui partagent cet objet. Ce d ecoupage fonctionnel assure le fait que les processus d'un domaine n'auront pas besoin, au cours de l'application, d'acc eder a d'autres domaines d'objets. La di cult e r eside dans le placement et la distribution des objets dont les domaines sont fortement i n tersect es. On pr ef ere donc utiliser une organisation de groupes hi erarchiques dans lesquels les processus partagent des objets communs. Par contre les processus peuvent exceptionnellement utiliser les objets d'autres groupes. Cette organisation n'est pas fonctionnelle. Si un processus se met a a c c eder fr equemment a un objet d'un autre groupe le syst eme de gestion de la m emoire sera surcharg e.

Pour eviter qu'un processus ne d evie ainsi en cours d'application, nous proposons un mod ele hybride qui permet l' evolution de la r epartition des processus dans les groupes. Si un processus e ectue souvent de nombreuses demandes sur un objet hors de son groupe, il faudra peut-être envisager de l'inclure dans le groupe acc edant souvent a cet objet. Bien entendu, les communications intra-groupe pour maintenir la coh erence des donn ees (processus chefs) et communications inter-groupes (grâce a des processus passerelles) sont prises en compte par le syst eme.

A n de d emontrer la faisabilit e de notre mod ele sur une machine parall ele, un d eveloppement logiciel de notre syst eme (appel e DOSMOS 1 ) est en cours de r ealisation. Nous esp erons ainsi pouvoir pr esenter au cours de ces journ ees des r esultats d'exp erimentations d'applications tournant sous le syst eme DOSMOS.

1: DOSMOS: Distributed Objects Shared MemOry System -Syst eme de m emoire partag ee d'objets distribu es


Laurent Lef Evre

PARALLEL PROGRAMMING ON TOP OF DSM SYSTEM AN EXPERIMENTAL STUDY

Keywords: Distributed Shared Memory System, Programming Environment, Shared Objects

Parallelization of an application with a message-passing model requires time, e ort and an important parallel programming knowledge from the programmer.

By using a Distributed Shared Memory model, programming a parallel application seems easy but reaching good performances becomes more di cult.

In this paper we propose an experimental study of the way to program parallel applications with the DOSMOS DSM system which provides an original programming model with shared distributed objects. Moreover by integrating a development platform and monitoring facilities, the DOSMOS system has been designed to o er a performant user-friendly programming environment.

1. Introduction. Parallelization of an application with a message-passing model requires time, e ort and an important parallel programming knowledge from the programmer.

The purpose of Distributed Shared Memory systems (DSM) is to implement, above a distributed memory architecture, a programming model allowing a transparent manipulation of virtually shared data. Thus, in practice, a DSM system has to handle all the communications and to maintain the shared data coherence. By this way, by using a Distributed Shared Memory model, programming a parallel application seems easy but reaching good performances becomes more di cult.

In our laboratory we have developped an original programming environment, the so-called DOSMOS1 system. This system is based on a structural approach of parallel programming. In other words, DOSMOS proposes to the user to hierarchically structure the processes into groups and sub-groups of processes sharing a same set of variables. This feature, combined with weak consistency protocols reduces the amount of communications required for the management of the shared data, and, as a consequence, ensures e ciency and scalability of the applications.

However, it would be unrealistic to argue that DOSMOS, or any other DSM system, deals e ciently with any kind of applications. That is why DOSMOS allows the programmer to mix both message-passing (PVM GBD + 93]) and DOSMOS code. To complete the programming environment, DOSMOS integrates a dedicated monitoring tool (DOSMOS-Trace) which has been added to the system to allow the user to understand the behavior of his applications.

At last, this programming environment has been designed to run both on distributed systems and on parallel machines. Thus, to ensure the portability of both the system and the applications, DOSMOS (as well as DOSMOS-Trace) has been developed on top of PVM.

But the main and open problems are \How to program a Distributed Shared Memory System like DOSMOS ? Is it well adapted for beginners or only for expert end-users ? Which is the best programming model to use for implementing parallel scienti c applications, a shared model or a message-passing one ?" Laboratoire de l'Informatique du Parallelisme, Ecole Normale Sup erieure de Lyon, 69364 LYON Cedex 07, France, llefevre@lip.ens-lyon.fr This year, for the rst time, DOSMOS has been teached like any other system in parallel courses of our university. Thus we have chosen among the students, a few parallel programming beginners and we analysed their reactions and behaviour in front of our DSM system when they had to parallelize their sequential algorithms.

This paper is divided into ve parts. After a short description of previous works (section 2), we analyse the basics of the DOSMOS DSM system in terms of management of shared data and process structuring (section 3). Then a description of the programming environment is proposed (development platform, basic routines and programming model). In section 5, we discuss the way to program a DSM system like DOSMOS and the di erences of programming and of performances between a DSM and a Message-passing system. At last, section 6 proposes a discussion both on the features of this programming environment and on its interest in terms of parallel programming.

Purpose of Distributed Shared Memory systems and previous works.

By allowing the programmer to share "memory objects" (i.e. programming variables) in a transparent way, Distributed Shared Memory Systems (DSM) propose a interesting trade-o between the easy-programming of shared memory machines and the e ciency and scalability of distributed memory systems. Basically, a Distributed Shared Memory system is a mechanism that allows application processes to access shared data in a transparent way. In other words, a DSM system relaxes the programmer from the management of all inter-process communications.

Even if both hardware and software implementations have been proposed, most of the systems require the implementation of an additional software layer :

Virtual Shared Memory systems (V.S.M.) propose to share data pages, i.e. to merge into a single wide address space a set of memory pages distributed in the network like MIRAGE FP89] or MUNIN CBZ91].

Object-based Distributed Shared Memory systems (D.S.M.) work at the program level, i.e. they implement a software layer that automatically generates, on the user's behalf, all the communications required to manipulate shared data. In other words, instead of de ning (and writing in the code) the inter-process communications, the programmer only speci es which data are actually shared. Then he can use these data as if they were local. On its side, the DSM system takes into charge all the needed communications (as a message-passing programmer would do). Such DSM systems as ORCA TKB92] or CLOUDS RAK89] have been implemented on parallel or distributed architectures. DOSMOS BL94, BL96] system belongs to this kind of systems. While a lot of DSM systems have been proposed, only few of them CBZ91, SN93, BEP93, BBP94] describe the way to program and to obtain good performances with them.

3. Basics of DOSMOS. DOSMOS is an object-based DSM system which allows processes to share in a transparent way a set of passive objects (i.e. of users programming variables) distributed and replicated in the network.

Moreover, DOSMOS integrates novel features :

DOSMOS Processes : Basically, a DOSMOS application is composed of two types of processes:

{ Application processes (A.P.) contain and execute the code (written in C) of the application.

{ Memory processes (M.P.) manage the whole DSM system, i.e. they provide A.P. with the objects they request and maintain data coherence. Each A.P. is connected to one and only one memory process. On the contrary, an M.P. can be connected to several A.P. and several M.P.

Array allocation : DOSMOS allows to manipulate both basic type variables (integer, oat, char. .. ) and distributed arrays. These arrays are split into several \system objects", replicated among the processes. Various splittings are provided : by row, by column, by block and by cyclic block. The system ensures a transparent access to arrays, whatever the splitting implemented.

Weak consistency protocols : for e ciency and scalability purpose, DOS-MOS gives the opportunity to duplicate shared objects. It is clear that these replicas have to be kept coherent. Most of actually implemented models are strong consistency oriented. DOSMOS implements a weak protocol: the release consistency. This model GLL + 90] provides two synchronization operators: acquire and release. These operators allow processes which want to modify shared objects to lock and unlock them in order to implement a mutual exclusion of accesses on shared objects.

Hierarchical structuring of the application processes: Previous DSM systems have always proposed \ at" models in which any shared object is accessible from any process. Such \anarchical" models cannot be scalable. In DOSMOS, processes can be grouped into groups and sub-groups in order to optimize the management of the data coherence.

When one observes the behaviour of a DSM application, and more particularly the behaviour of a process participating in the application, it appears that if some shared data are intensively accessed by this process, some are either scarcely or even never accessed. This leads us to introduce some de nitions (see g. Let P be a process. We have : G:V:S:(P ) = Local V irtual Space(P ) + Extern V irtual Space(P ) Usually, in previous systems, when an object O is modi ed, an invalidation message is sent to all the processes P such that O 2 GV S(P ). This prevents, as noted before, to ensure a good scalability. By using a hierarchical grouping of processes, DOSMOS limits the invalidation messages to processes such that O 2 LV S(P ). Basically, DOSMOS proposes to structure the application into hierarchical groups of processes sharing the same objects. In practice, a group is de ned by a set of processes and a set of shared objects. Processes of a same group share all the objects attached to the group, i.e. if they request an object, they will receive a copy of this object which will be automatically updated by the system. Moreover, DOSMOS allows processes to access extra-group shared objects. For this purpose, in each group, a dedicated memory process, called Link 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 With this model, access to shared objects is optimized and maintenance of the consistence is kept cheap. We obtain good performances improvements with experiments (like in gure 5.7) using hierarchical groups on network of workstations. Preprocessing level: this layer analyses the user's application in order to detect and generate accesses to shared objects ( g. 4.2). This layer makes the system \transparent"; DSM level: this layer assumes the creation and management of shared objects, groups and of various processes involved in execution of the application (APs, MPs, LPs). This management is performed using message-passing routines hidden to the user. Use Dosmos() and End Dosmos() allow the beginning and the end of sharing of the objects. All data accesses are not speci ed by the user but in order to access exclusively shared objects, two operators are proposed to the user : Acquire and Release. The synchronization routine allows to synchronize all processes sharing a given object or all processes of a given group. 4.3. Programming model. As soon as the Use Dosmos() primitive has been executed, the user can access the shared objects in a transparent way. However, DOSMOS, as any DSM system, does not pretend to be e cient in all the situations. Consequently, in order to help the user to optimize his applications, DOSMOS allows the combination of di erent programming models for user's comfort. Consequently, three programming models are available :

111
Local programming : in order to minimize accesses to shared objects, it is sometimes more performant to work on local variables before modifying shared variables. D.S.M. programming : the user can use DOSMOS primitives to declare and access shared variables.

Mixing of DSM and message-passing programming : the user can integrate message-passing communications (with PVM routines) into DOS-MOS applications. This feature presents two advantages. First, it permits to deal with speci c applications. Second, it allows to port PVM applications on DOSMOS with slight modi cations of the code.

5. Programming on top of DOSMOS. 5.1. E ciency of data accesses. First of all, a battery of tests has been designed and implemented in order to validate the system e ciency. Usually, most of scalability problems encountered with DSM systems occur when several processes try to modify the same object. To understand DOSMOS behaviour with such problems, the next experiments involve a LAN of 8 workstations. Each processor runs both an Application Process and its dedicated Memory Process. No grouping of processes is performed. The 8 APs recursively attempt to access the same shared object in order to modify it. Figure 5.1 displays the execution time of these applications with respect to the number of write accesses performed. In the rst example, relaxed write modi cations are performed without synchronization (i.e. without acquire operations). In the second experiment, before each write access, an acquire operation is triggered in order to lock the object. As we can see, both experiments express quasi-linear results which prove the e ciency. The system is not overloaded when the amount of concurrent accesses is high (e.g. 500 write operations performed per second). Furthermore, these experiments outline the cost of the acquire/release operations (response time multiplied by 100). This argues for an optimization of the consistency protocols implemented (see section 3) and for the introduction of group management facilities (see section 5.3).

Write Operations Relaxed

Scalability. In the following two applications, as previously, an Application

Process and its dedicated Memory Process are mapped on each processor. AP Exec. Time E ciency 1 3.33 2 1.8 0.92 4 0.93 0.9 8 0.5 0.83 Next experiment ( gure 5.3) shows the speed-up obtained by an application which computes the maximum value of a distributed set of data mapped on di erent processors. Thus, we obtain speedups of more than 6 and a good e ciency of more than 0.8 when using 8 processors.

In all experiments, a quasi-linear scalability is reached which con rms the e ectiveness of the concepts introduced in the DOSMOS system.

Improving DOSMOS applications. Previous experiments have shown

that designing small applications with DOSMOS permits to easily program parallel applications with e ciency. But reaching good performances with more important applications can be di cult. As DSM systems hide all communications and optimizations to the user, the performances can greatly vary depending on the user knwoledge of the system.

In gure 5.4, we can see the easiness of programming with DOSMOS but also the di erences of codes between two DOSMOS users, a beginner and an expert one. As DOSMOS provides various consistency protocols, beginner users prefer to guaranty the data accesses by choosing strong consistency schemes ( rst code). All put and get operations are exclusive and synchronized. So performance of the application decreases as all accesses are sequentialized. But this code can be greatly improved by using local variables and by relaxing some matrix accesses which do not need to be modi ed in a exclusive way for this application. An execution of DOSMOS Gauss with the rst version takes 26 seconds instead of 13.1 seconds with the optimized version.

When the code is cleaned of all artifacts, we can reach scalable performances with a DOSMOS execution. We can see in gure 5.5 that when the amount of data treated increases of more than two times, execution times follow the same behaviour.

Matrix Size Execution Time 10 10 1.05 20 20 6.6 30 30

13.1 After optimizing the code itself, many parameters concerning the shared objects must be tuned to improve performances. The previous Gauss experiment has to deal with various shared matrices which can be split in several blocks. On gure 5.6 we can see the great importance of that parameter on execution time with matrices of 30 30 elements. If the matrix is not splitted, performances decrease because each access generates a sending of the whole shared matrix. On the other side, choosing a really small object size is worst because the system has to deal with a lot of very small messages for each access. For this experiment, the trade-o is to choose blocks with medium size. Here, blocks of 2x5 elements permit to reach the best execution time of 13 seconds oppositely of the worst case with up to 20s of execution time.

At last, the hierarchical structuring of application processes must be done to bene t of hierarchical groups provided by DOSMOS to reduce coherence costs.

In the next experiments ( gure 5.7), we compute an approximation of with an interval discretizing method. We use 12 Application Processes, mapped on 12 processors. With no group structuring, the computation requires 3.95 seconds. However, with the same number of processors, structuring the processes into two groups (each of them being in charge of one half of the interval), improves drastically the performances (new computation time: 2.56 s).

Like the other parameters, hierarchical grouping allows to obtain very good performances, on condition that it is pertinently used. Thus, we can obtain performances really close to the message-passing ones (see gure 5.8). The DOSMOS application is really easier to implement and only 8% slower than the PVM version with 16 processes. But the choice of the parallel programming model depends also on various parameters.

DOSMOS or Message-passing.

To choose its programming model, the user must know which is the best-tted to his applications' requirements. First, we see the di erences between DOSMOS and PVM on basic accesses to data and then we compare the two environements in terms of performance and easiness of programming.

Processors Groups Exec.Time computation times (in sec.). One MP also runs on each processor. asks to its dedicated M.P. the value of a shared object. This M.P. tries to know the value from the object owner and sends it back. Meanwhile, for the PVM Read version, a slave sends a message to a given process and waits for the value to come back. We can see in gure 5.9 that the DOSMOS Read operations are a little slower than PVM ones due to the DSM management layer. But with write operations, DOSMOS obtains better performances than the PVM version due to the bottleneck which occurs with the message-passing model. The DOSMOS relaxed consistency allows 5 processes to perform 1000 write modi cations in less than 2 seconds. These experiments (see also gure 5.8) exhibit that PVM and DOSMOS can be equally compared on the basic access concepts. After these experiments, we can note several behaviours (also summarized in gure 5.11) :

L. Lef evre Programming with DOSMOS is easier than with PVM, and the code is close to the sequential version ; Designing an application with a message-passing model like PVM takes 4 more times than with a DSM model like DOSMOS ; Already written PVM codes can be easily ported and transformed to bene t of distributed shared objects because DOSMOS hidden underlying layer is based on PVM ; The code of the application is twice smaller by using DOSMOS primitives. Moreover, maintenance of a PVM code is much more di cult ; Understanding the behaviour and optimizing application performances are easier with PVM for an experimented programmer ; DOSMOS is more adapted to coarse grain or irregular parallel applications while PVM more designed for regular parallel algorithms ; Di erences of performances between the two environments are slight with a small decrease for the DSM due to DOSMOS management layer; By analysing the behaviour of users implementing DOSMOS applications, we can detect advantages and drawbacks of our DSM system. Moreover this study allows a better understanding of users requirements for a DSM environment comparing to the message-passing one.

6. Discussion and future works. This paper shows that DSM systems can be an e ective way to implement distributed and parallel applications. But implementing a DOSMOS application deals with two main problems : the easiness of programming and the execution performances.

All communications of a parallel application can be totally hidden to the user by the DSM system. DOSMOS allows to program applications in a quick and easy way. Programming, testing and debugging are simpli ed and guaranteed by the reliability and e ciency of the system. But such a system can also appear as a black box as it is really di cult to understand applications behaviour. That's why, we have added a dedicated tool (called DOSMOS-Trace BLR96]) which allows to precisely understand data access patterns of applications. This tool provides several visualizations and informations about the execution (like statistics on shared objects, histories. . .). Such views are extremely useful for the user to correct problematical situations. Indeed they allow to detect ping-pong e ects, over-accessed variables, bottlenecks (like in gure 6.1), not actually shared variables, etc. . .So DOSMOS is a programming environment which can be used by beginners (at least as their rst parallel programming approach). DOSMOS is also well designed for expert programmers which can improve and optimize the code as with any other parallel programming environment.

Many parallel programmers usually think that a DSM application will never beat an optimized message-passing application performances. Due to shared objects management, it is often true. But the costs (in terms of time, e ort, debugging, maintenance. . .) to implement such performant message-passing applications are usually too expensive compared to the good results of DSM version. However, a lot of users prefer to implement themselves all the communications of the application. One possible trade-o is to use one of the interesting features of DOSMOS which allows to mix together PVM and DOSMOS code in a same application. By this way, the user can take advantage of each programming model without their drawbacks. It is also a good way to implement PVM code on DOSMOS to add shared objects with only small modi cations on the original program. More experiments using both programming models are currently done on this domain.

  3.1) :{ G.V.S. : The Global Virtual Space (GVS) of a process is the set of the shared objects accessed (in read or write mode) by a process during the execution of the application. { L.V.S. : The Local Virtual Space (LVS) of a process is the set of the shared objects intensively accessed by this latter. { E.V.S. : The Extern Virtual Space (EVS) of a process is the set of the shared objects rarely accessed by the process.

Fig. 3

 3 Fig. 3.1. Accesses distribution of an application using an object-based DSM system

  4. Programming environment. 4.1. Development platform. The implementation of DOSMOS is based on two di erent layers :

Fig. 4

 4 Fig. 4.3. DOSMOS primitives

Fig. 5

 5 Fig. 5.1. Write accesses to a single shared object with or without acquire/release calls

FigFig. 5. 3 .

 3 Fig. 5.2. Concurrent accesses to a shared object : a distributed array lling 0 1 2 3 4 5 6 7

Fig. 5

 5 Fig. 5.4. From a rst version of DOSMOS Gauss (left side) to an optimized code (right side)

FigFig

  Fig. 5.5.Execution times of Gauss with DOSMOS

  Fig. 5.7.

  Fig. 5.8. Computation of ; comparison of the speedups obtained when using DOSMOS and when using PVM

Fig. 5 .

 5 Fig. 5.9. DOSMOS and PVM Read operations with 5 processes

  Fig.

Fig. 6. 1 .

 1 Fig. 6.1. Object activity vs execution time : a bottleneck occurs during execution. All the processes exclusively access same shared data.

DOSMOS is the acronym for a Distributed Objects Shared MemOry System. 1


Laurent Lefèvre
email: laurent.lefevre@inria.fr

Paul Roe
email: p.roe@qut.edu.au

Improving the flexibility of Active Grids through Web Services

Keywords: active and programmable networks, grid computing, web services

Active Grids are a form of grid infrastructure where the grid network is active and programmable. These grids directly support applications with value added services such as data migration, compression, adaptation and monitoring. Services such as these are particularly important for eResearch applications which by their very nature are performance critical and data intensive.

We propose an architecture for improving the flexibility of Active Grids through web services. These enable Active Grid services to be easily and flexibly configured, monitored and deployed from practically any platform or application. The architecture is called WeSPNI ("Web Services based on Programmable Networks Infrastructure"). We present the architecture together with some early experimental results on using web services to monitor data movement in an active grid.

Introduction

eResearch is an important new research area which uses Grid computing to virtualize people, resources and information. This enables the active and dynamic collaboration of researchers from different organizations and across different geographic regions. eResearch enables collaborative research. Grid computing provides the infrastructure for eResearch it enables the transparent sharing of information, computational resources, and devices.

eResearch applications running on grids are typically performance critical and data intensive. To address this active networking has been applied to Grids to yield Active Grids where the grid network is active and programmable. This enables applications and users to customize the grid for specific applications through value added services which can perform dedicated operations (for example, adapt and compress data, monitor data communications and migrate data).

Active Grids [START_REF] Gelas | Towards the design of an active grid[END_REF] build on the Active Networking vision, routers can perform computations on user data in transit and users can modify the behavior of the network by supplying programs, called Programmable Network Services (PNS) that perform these computations. These routers are called active routers and provide great flexibility towards the deployment of new functionality, more adapted to architecture, users and service providers' requirements.

INRIA researchers have proposed the first execution environment Tamanoir [START_REF] Gelas | Towards the design of an high performance active node[END_REF][START_REF] Lefèvre | Heavy and lightweight dynamic network services : challenges and experiments for designing intelligent solutions in evolvable next generation networks[END_REF]) designed for the support of Gigabit networks and to provide Grid network services. The Tamanoir Active node software suite is based on widely used components and tools: Myrinet [START_REF] Arora | Web services for management[END_REF] and Giga Ethernet for NIC level, Netfilter/Linux for kernel space support, Java for user space level and Linux Virtual Server for distributed infrastructure. This Tamanoir software is deployed for experimental use on various local and long distance platforms.

Recent research has involved utilizing active network technology inside Grids in order to add the network component part to Grid infrastructure [START_REF] Mohamed | Active networks and their utilization in the computational grid[END_REF]. INRIA researchers have proposed solutions to merge the active networking and Grid fields by developing the Active Grid Architecture (A-Grid) which focuses on active network adaptation for supporting Grid environments and applications [START_REF] Gelas | Towards the design of an active grid[END_REF]. This active Grid Architecture allows solutions to support multi-cluster and P2P Grid configurations. In this architecture the network will take part in the Grid computing session by providing efficient and intelligent services dedicated to Grid data stream transport. This Active Grid provides an overlay infrastructure on Grids.

However until now managing PNS in Active Grids has been done through ad hoc protocols and services. We propose an architecture where services in Active Grids are managed through web services. This enables programmable network services to be easily and flexibly configured, monitored and deployed from practically any platform or application. Furthermore web services themselves can be used by Active Grid services to further enhance their processing capabilities, to provide non-performance critical functionality. While Web Services can now be used in various gateways and end host equipment [START_REF] Bulut | A web services based streaming gateway for heterogeneous a/v collaboration[END_REF], mixing active networks and web services is still not deeply explored [START_REF] Takashi | Largescale high-quality communication service solution using active network technology[END_REF]. Web services are important for next generation networking and grid computing; in particular the next generation Globus (the de facto standard grid computing Middleware (Globus Grid Middleware n.d.)) infrastructure is now adopting web services for communications. Web services are highly configurable and can be described by lots of semantic information.

In this paper we present the architecture and some preliminary results for Active Grids utilizing web services for improved flexibility.

The paper is organized as follows. Section 2 briefly describes the Active Grid infrastructure. The We-SPNI architecture is presented in Section 3. An eResearch scenario using the proposed framework is described in Section 4. Experimental evaluation on local platforms are analyzed in Section 5. Section 6 concludes the paper and presents the on-going work.

2 Inside the Active Grid infrastructure

Programmable network nodes

We have designed an architecture for a high performance active router capable of being deployed around a high performance backbone: the Tamanoir Execution Environment [START_REF] Gelas | Towards the design of an high performance active node[END_REF][START_REF] Lefèvre | Heavy and lightweight dynamic network services : challenges and experiments for designing intelligent solutions in evolvable next generation networks[END_REF].

We define an Active Network Execution Environment (EE) as an environment able to load and deploy network services. It must be also able to direct packets towards the required service thanks to appropriate header filtering.

Programmable Network Services can be deployed at various levels depending on resources (e.g. processing capabilities, memory consumption and storage capacity) and intelligence (flexibility of the execution environment) they need. In order to provide an adapted EE for each of service and to limit packets ascent, we design an active node architecture on four levels: Network Interface card (NIC), Kernel space, User space and distributed resources. (see Figure 1). 3. Services repository: specific servers (service repositories (see Figure 3)) are distributed in the Grid infrastructure. They own collections of active services and can provide them to requesting active nodes (scenario 3 (a, b in Figure 2).

Figure 3: Services repository

Active Grid architecture

We propose an active network architecture dedicated to Grid environments and Grid applications requirements: the Active Grid architecture [START_REF] Gelas | Towards the design of an active grid[END_REF]).

An Active Grid architecture is based on a virtual topology of active network nodes spread on programmable routers of the network. Active routers, also called Active Nodes (AN), are deployed around backbone networks.

Since we are concerned with a wide active routers approach, we do not consider the deployment of Gigabit active routers in backbones. This is because the future of WAN backbones will be based on all-optical networks, no dynamic services will be allowed to process data packets. Thus active operations occur on edge routers/nodes mapped at network periphery.

Active nodes manage communications for a set of Grid nodes. Grid data streams cross various active nodes up to passive backbone and then cross another set of active nodes up to receiver node. The Active Grid architecture is based on Active Node approach: programs, called services, are injected into active nodes independently of data stream. Services are deployed on demand when streams arrive on an active node. Active nodes apply these services to process data streams packets.

To support most of Grid applications, the Active Grid architecture deals with the two main Grid configurations:

• Multi-cluster computing (Figure 4):

In this highly coupled configuration, an active node is mapped on network head of each cluster or parallel machine. This node manages all data streams coming or leaving a cluster. All active nodes are linked with other AN mapped at backbone periphery. An Active node delivers data streams to each node of a cluster and can aggregate output streams to others clusters of the Grid.

• Global and P2P computing (Figure 4):

In this loosely coupled configuration, an AN can be associated with each Grid node or can manage a set of aggregated Grid nodes. Hierarchies of active nodes can be deployed at each network heterogeneity point.

Each AN manages all operations and data streams coming to Grid Nodes : subscribing operations of voluntary machines, results gathering, nodes synchronization and check-pointing. . . For both configurations, active nodes will manage the Grid environment by deploying dedicated services adapted to Grid requirements, including: dynamic topology re-configuration, fault tolerance. . .

The WeSPNI architecture

We focus on the design of Web Services for Programmable Network Infrastructure (WeSPNI). We observe a real convergence between Grid infrastructure and Web Service solutions. Based on the Open Grid Service Infrastructure, Grid researchers have proposed the WSRF (Web Service Resource Framework) [START_REF] Czajkowski | The WS-Resource Framework[END_REF] where Web Services support the stateful computation necessary for Grid computing. This convergence currently needs to be efficiently exploited by providing network solutions adapted to Grid requirements.

Flexible network services

Programmable network nodes must embed heterogeneous dynamic services from management and control plane (e.g. monitoring, accounting) to data plane (e.g. streams adaptation, storage on the fly) (see Figure 5).

In the active network research field, network services are pieces of code deployed on programmable network equipment. We propose to add the possibility of high level service composition through calls of web services from programmable network services.

In the WeSPNI architecture, network services consist of portions of local code combined with web services invocations (See Fig. 6). Active nodes support a pipelined execution of functionalities of PNS. This original approach can allow a flexible autonomic composition of services and can propose high level interactions between active nodes and migration of expensive functionality to remote servers.

Management and Control plane

We propose an architecture where services in Active Grids are managed through web services. This enables services to be easily and flexibly configured, monitored and deployed from practically any platform or application.

With the WS-Management (Arora, Geller, He, Kaler, McCollum, Milenkovic, Montgomery, Saiyed & Suen 2005) framework, Web Services allow a flexible management of servers and remote devices. With this framework, active networks can be remotely managed and monitored in order to control the autonomic deployment of programmable network services.

Active networks and Web services for the data plane

• Deploying web services blocks inside networks: Currently available web services frameworks and implementation are based on generic and complex solutions. Lack of efficiency of these solutions remain an open problem. We propose to deploy some parts of Web Services inside dynamic network equipment by linking with programmable network solutions (Figure 7). This will allow efficient and flexible solutions for Web Services infrastructure. For example, in figure 7, a programmable network service is based on some code and four remote functions calls. These functions are available through web services in some network equipment. So the code is dynamically deployed on network nodes and benefits from Web Services on the nodes.

• Value added services inside non re-programmable networks: Deploying functionality inside networking equipment requires the dynamic programming of equipment. This is not always possible, thus WeSPNI explores solutions based on adaptive routing functionality inside the network, allowing the possibility to route streams to required services present on end machines. In figure 8, network nodes have limited processing capabilities. So local code of programmable network services are deployed on active nodes and remote functions remain on distributed web servers off data path.

Exposing network services

To enable eResearch, end-users should be able to exchange and use dynamic network services provided by others Grid sites. So after deploying some network services, users should be able to advertise capabilities and functionality of these services. Web services are distributed application components that conform to standards that make them externally available. As active network services need to be deployed on heterogeneous platforms and called and interfaced with E2E applications, they face the same problem as web services.

Exposing an active network services means publishing a description of the service interface, as Web Services description consists of the service's Web Services Description Language (WSDL) description and XML schema referenced by the service description. These input parameters contain the service reference which must be deployed into the nodes and some specific states.

• Processing: contains the description of the functionality applied in programmable network services. It is based on a pipelined execution of local functions and remote functions through web services available on remote capabilities (see Figure 9).

processing = { service 1 & service i & service n }
The description of the processing can also include the storage of some states useful for the service.

• Output: precises the level of modification from the PNS : discarding of a packet, duplicating broadcasting, modifying header or payload. output = { modified header || modified payload }

eResearch Scenario

In this section we describe a eResearch scenario requiring Active Networking, and argue how that is made more flexible through web services.

In eResearch, distributed sources (repositories) of data are linked by a Grid infrastructure. These data repositories are used for global collaborative computing purposes and are shared and moved between Grid sites to facilitate collaboration. In order to optimize data locality, the network should provide monitoring of applications level data communications through programmable network services. These value-added services (which must not be included in the application) can be enabled by the grid's active network nodes. The active nodes must exchange collected data between themselves and provide summaries of logging information to distributed portals (Figure 10). Users can dynamically change the frequency of monitoring collection to efficiently deal with the impact of intrusive collection on the overall performance. More generally higher level grid services may wish to automatically move and replicate data based on information gathered from these programmable network services, or to cache such data. Thus exposing PNS in a general way has many benefits and greatly adds to the flexibility of the active grid. Web services do exactly this. They enable the flexible exposure of programmable network services in a decoupled manner so that other platforms and applications can easily consume such information with no knowledge and hence dependency of the underlying active nodes implementation. The use of extensive meta-data in web services and standards for securing information further benefits the active grid.

Experimental Validation

The experimental platform consists of two Grid clients exchanging data streams through a Tamanoir active network node (TAN). This programmable node embeds dynamic services which are deployed from a service repository and which call remote web services (Figure 11).

We design the MonitorS active service as:

• a Java part deployed in the Tamanoir active nodes. This service monitors packets crossing the node and collect logging information. With a frequency specified by the end-users, the TAN compresses logs tables and exchanges it with remote active nodes or Web Servers. We evaluate the impact of a remote invocation to the web service due by modifying the frequency of update of logging table and show that the cost of sending uncompressed data to the Web Services through SOAP greatly impacts the performance of a Tamanoir Monitoring service, whose bandwidth is around 220 Mbits (see figure 12). We show that compression of the logging table and increasing the size of data packets greatly improves the performance of the Web Service (see figure 13). Figure 13 also demonstrates the approximate bandwidth of the active node using a basic forwarding service.

Conclusion and future works

In this paper we have proposed using web services to make the active grid architecture more flexible. Web services enable services of active nodes to be monitored, managed, deployed and controlled easily. The services for doing this are well described We have undertaken some initial experiments using web services to provide a monitoring interface to active nodes. The example interface enables application level data communication to be monitored; this can be used for a variety of purposes including monitoring portals or data oriented middleware. These first experiments have used HTTP and Unicode based web services, the performance of which limits the use to non-performance critical code, off the main data path.

Our long term goal is to move remote functionality to distributed in path and out of the path infrastructure.

We believe binary implementations of web services will make this feasible.

Figure 1 :

 1 Figure 1: Tamanoir active node

Figure 2 :

 2 Figure 2: Programmable Network Services deployment 2. Node to node: the active node owning the requested service is able to provide the service to

Figure 4 :

 4 Figure 4: Multi-cluster and P2P computing Active Grid Architecture

  Figure 5: Classes of services

Figure 6 :

 6 Figure 6: A network service

Figure 7 :

 7 Figure 7: If network nodes are dynamically programmable equipments, some parts of Web Services are deployed inside the network.

Figure 9 :

 9 Figure 9: Exposing active network services capabilities We propose a simplified exposition facility based on the triplet { input, processing, output } • Input: programmable network services are packet based. So input parameters are fitted in data packets crossing the active nodes and can concern packet header or payload. input = { packet header || packet payload } These input parameters contain the service reference which must be deployed into the nodes and some specific states.

Figure 8 :

 8 Figure 8: Web Services are deployed on Web Servers while adaptive routing is allowed inside network equipments

FigureFigure 12 :

 12 Figure 11: Experimental platform

Figure 13 :

 13 Figure 13: Communication performance improvements due to compression

This research is partially supported by FAST project number 10466QH between French Ministry of Foreign Affairs and Australian Government.

Acknowledgments

The authors wish to thank Chien Jon Soon for his help during the experimental validation step.