M Devers Lamrani

Stéphane Pesce

Nadine Rouard

F Martin Laurent

Marion Devers-Lamrani

Fabrice Martin-Laurent

Evidence for cooperative mineralization of diuron by Arthrobacter sp. BS2 and Achromobacter sp. SP1 isolated from a mixed culture enriched from diuron exposed environments

Keywords: Pesticide, Biodegradation, Soil microbiology, Buffer strip, Sediments, 3,4-DCA

published or not. The documents may come     Evidence for cooperative mineralization of diuron by Arthrobacter sp. BS2 and Achromobacter sp. SP1 isolated from a mixed culture enriched from diuron exposed environments

Introduction

The diuron (DIU,-1,1-dimethylurea) is widely used on a range of crops to control the development of weeds. It is also used in urban areas, as an algicide in antifouling paints and as herbicides on non-crop areas. Having half live ranging between 100 and 134 d [START_REF] Moncada | Environmental Fate of Diuron[END_REF], DIU is relatively persistent in soil. Although considered to be moderately mobile, it contaminates surface-and ground-water resources world widely [START_REF] Schuler | Aquatic risk assessment of herbicides in freshwater ecosystems of south Florida[END_REF][START_REF] Schuler | Aquatic risk assessment of herbicides in freshwater ecosystems of south Florida[END_REF][START_REF] Stork | The environmental fate of diuron under a conventional production regime in a sugarcane farm during the plant cane phase[END_REF]. Environmentally realistic concentrations of DIU can affect aquatic microalgal [START_REF] Pesce | Effects of organic herbicides on phototrophic microbial communities in freshwater ecosystems[END_REF] and bacterial communities [START_REF] Tadonleke | Responses of lake bacterioplankton activities and composition to the herbicide diuron[END_REF]. Combined presence of DIU and its main metabolites N-(3,4-dichlorophenyl)-N-methylurea and 3,4-dichloraniline (3,4-DCA) has been reported in surface freshwaters [START_REF] Claver | Study of the presence of pesticides in surface waters in the Ebro river basin (Spain)[END_REF][START_REF] Morin | Linking diatom community structure to pesticide input as evaluated through a spatial contamination potential (Phytopixal): a case study in the Neste river system (South-West France)[END_REF], this last one being highly toxic to the bacteria Vibrio fischeri and the Ciliate Tetrahymena pyriformis [START_REF] Bonnet | Assessment of the potential toxicity of herbicides and their degradation products to nontarget cells using two microorganisms, the bacteria Vibrio fischeri and the ciliate Tetrahymena pyriformis[END_REF] but also to macro-organisms, with no observed effect concentrations of only a few µg L-1 [START_REF] Giacomazzi | Environmental impact of diuron transformation: a review[END_REF]. DIU has been classified as a primary dangerous substance (Directive 2000/60/CE) and accordingly it has been banned in Europe but remains used in numerous regions of the world.

The major route for natural attenuation of DIU in the environment is microbial degradation [START_REF] Sharma | Biotransformation and biomonitoring of phenylurea herbicide diuron[END_REF]. Several studies showed its rapid degradation in different soils repeatedly treated with DIU in reason of the emergence of bacterial populations using it as a nutrient and an energy source [START_REF] Dellamatrice | Isolation of diuron-degrading bacteria from treated soil[END_REF][START_REF] Dellamatrice | Isolation of diuron-degrading bacteria from treated soil[END_REF][START_REF] Pesce | Potential for microbial diuron mineralisation in a small wine-growing watershed: from treated plots to lotic receiver hydrosystem[END_REF]. Various microorganisms such as Arthrobacter globiformis D47 [START_REF] Cullington | Rapid biodegradation of diuron and other phenylurea herbicides by a soil bacterium[END_REF] able to transform DIU have been isolated from various contaminated environments [START_REF] Sorensen | Rapid mineralisation of the herbicide isoproturon in soil from a previously treated Danish agricultural field[END_REF]. Except for Variovorax sp. SRS16 which entirely mineralizes DIU [START_REF] Sorensen | Rapid mineralization of the phenylurea herbicide diuron by Variovorax sp. strain SRS16 in pure culture and within a two-member consortium[END_REF], most of the isolates transform DIU to 3,4-DCA which accumulates in soil. Strains isolated from DIU-contaminated soils, Pseudomonas fluorescens 26-K and Acinetobacter baylyi strain GFJ2 [START_REF] Travkin | Degradation of 3,4-dichloro-and 3,4-difluoroaniline by Pseudomonas fluorescens 26-K[END_REF][START_REF] Hongsawat | Biodegradation pathways of chloroanilines by Acinetobacter baylyi strain GFJ2[END_REF][START_REF] Hongsawat | Biodegradation pathways of chloroanilines by Acinetobacter baylyi strain GFJ2[END_REF] have been shown to degrade 3,4-DCA. The importance of mixed bacterial cultures for the complete mineralization of DIU was underlined and catabolic cooperation between microbial populations to fulfill DIU mineralization was hypothesized [START_REF] Sorensen | Rapid mineralization of the phenylurea herbicide diuron by Variovorax sp. strain SRS16 in pure culture and within a two-member consortium[END_REF][START_REF] Ellegaard-Jensen | Fungal-bacterial consortia increase diuron degradation in waterunsaturated systems[END_REF]. Only two genes coding for the first enzyme involved in the transformation of dimethyl-substituted phenylureas into their aniline derivatives have been reported; the phenylurea hydrolase A gene (puhA) was the first one identified in A. globiformis strain D47 [START_REF] Turnbull | Degradation of substituted phenylurea herbicides by Arthrobacter globiformis strain D47 and characterization of a plasmidassociated hydrolase gene, puhA[END_REF] and the phenylurea hydrolase B gene (puhB) was characterized in Mycobacterium brisbanense JK1 isolated from an Australian soil [START_REF] Khurana | Characterization of the phenylurea hydrolases A and B: founding members of a novel amidohydrolase subgroup[END_REF]. These two genes encode amidohydrolases sharing 82% identity at the amino acid level but diverged from other related sequences forming a amidohydrolase superfamily sub-group [START_REF] Khurana | Characterization of the phenylurea hydrolases A and B: founding members of a novel amidohydrolase subgroup[END_REF]. Recently, dcaQTA1A2BR genes encoding a multi-component chloroaniline dioxygenase responsible for 3,4-DCA degradation were identified in Variovorax sp. SR16 [START_REF] Bers | A novel hydrolase identified by genomic-proteomic analysis of phenylurea herbicide mineralization by Variovorax sp strain SRS16[END_REF].

Studies carried out at a small-scale watershed level (Morcille river, Beaujolais, France) constituted of a vineyard treated with DIU, a grass buffer strip adjacent to it and the sediments of this river have clearly shown that in situ DIU exposure provokes an increase in the tolerance of phototrophic biofilm communities towards DIU ( Pesce et al., 2010a) and the DIU degrading potential of both terrestrial and aquatic microbial communities [START_REF] Pesce | Potential for microbial diuron mineralisation in a small wine-growing watershed: from treated plots to lotic receiver hydrosystem[END_REF]. DIU-degrading genetic potential quantified by quantitative PCR targeting puhA and puhB genes was detected in both terrestrial and aquatic compartments showing DIU-degrading abilities [START_REF] Pesce | Response of a diuron-degrading community to diuron exposure assessed by real-time quantitative PCR monitoring of phenylurea hydrolase A and B encoding genes[END_REF]. At the watershed level, soil erosion was suggested as a possible mechanism responsible of the transfer of the DIU genetic potential from the soil to the sediments ( Pesce et al., 2010b).

Even though bacterial populations, genes and catabolic enzymes involved in DIU transformation have been identified, not much is known about the functioning of the DIU-degrading microbial community. In order to fill this gap of knowledge, we carried out experiments aiming at isolating and characterizing members of DIU-degrading microbial communities enriched from soil and sediment samples collected from the Morcille watershed. Isolated members able to degrade DIU or its aniline derivative 3,4-DCA were taxonomically characterized by sequencing 16S rRNA gene. Degrading genetic potential was monitored by studying puhA and puhB or dcAQ genes involved in DIU or 3,4-DCA transformation, respectively. The ability of these bacterial strains to degrade various phenylureas and anilines was studied. The efficiency of mixed culture made of DIU-and 3,4-DCA degraders for DIU mineralization was estimated.

Material and Methods

Soil and sediments

Soil was collected from upper horizon (0-20 cm) of a grass buffer strip (BS) located (longitude 4°60′E, latitude 46°15′N) at the interface between a vineyard and the Morcille river, a small first-order stream (7 km long) subjected to a strong agricultural pressure (Beaujolais, France). A composite BS soil sample was prepared according to ISO 10381-6 guidelines. Sediment samples (SED) were collected in the downstream section of the Morcille river (Saint Ennemond station). Soil and sediments were sieved to 5 mm and stored at 4 °C until their use.

Enrichment procedure

Enrichment cultures were done starting from either BS or SED samples. About 10 g of soil or sediment equivalent dry weight was suspended in 90 mL of mineral salt (MS) medium [START_REF] Devers | Horizontal gene transfer of atrazinedegrading genes (atz) from Agrobacterium tumefaciens St96-4 pADP1::Tn5 to bacteria of maizecultivated soil[END_REF] added with sodium citrate (1 g L-1) and DIU (MS-DIU, 25 mg L-1) as sole nitrogen source, incubated at 20 °C under agitation (150 rpm). Aliquots were taken regularly and DIU remaining in the medium was quantified using HPLC. When about 50% of the initial amount was dissipated, 10 mL of this suspension was transferred to 90 mL of fresh MS-DIU medium and incubated under the same conditions. After 3 enrichment cycles, 100 µL serial tenfold dilutions (from 10-3 to 10-6) were plated onto solid MS-DIU medium or MS-3,4-DCA medium (1 g L-1). Single colonies isolated from the plates were stricken on new plates to purify isolates. Pure colonies were selected for DIU or 3,4-DCA degradation in corresponding liquid media incubated at 28 °C under agitation (150 rpm). After a few days, the bacterial cells were harvested (3,220 g, 10 min) and the supernatant was analyzed by HPLC to determine the amount of the remaining DIU or 3,4-DCA.

DNA extraction

DNA was extracted from 75 mL of bacterial suspension using the QIAGEN Blood and Cell culture DNA Midi Kit (QIAGEN, France).

PCR analysis

PCR were conducted in 25 µL by using 25 ng of extracted DNA, 0.2 µM of dNTPs, 1 µM of specific primers (puhA/puhB, dcaQ and 16S rRNA primers according to [START_REF] Pesce | Response of a diuron-degrading community to diuron exposure assessed by real-time quantitative PCR monitoring of phenylurea hydrolase A and B encoding genes[END_REF], [START_REF] Bers | A novel hydrolase identified by genomic-proteomic analysis of phenylurea herbicide mineralization by Variovorax sp strain SRS16[END_REF] and [START_REF] Gürtler | New approaches to typing and identification of bacteria using the 16S-23S rDNA spacer region[END_REF]), and 1.25 U of Taq DNA polymerase (Q-biogene, France). DNA amplifications were carried out in a PTC 200 gradient cycler (MJ Research, Waltham, MA, USA) as follows: 5 min at 95 °C, 35 cycles of 1 min at 94 °C, 1 min at annealing temperature and 2 min at 72 °C, plus an additional 10-min cycle at 72 °C. PCR products were separated by electrophoresis and visualized under UV.

Repetitive extragenic palendromic (REP)-PCR

REP PCR was carried out in a 25-µL mixture using 50 ng of bacterial DNA as template and separated by electrophoresis according to [START_REF] Devers | Horizontal gene transfer of atrazinedegrading genes (atz) from Agrobacterium tumefaciens St96-4 pADP1::Tn5 to bacteria of maizecultivated soil[END_REF].

Southern blot analysis

NruI or SmaI digested DNA was separated by electrophoresis, in the presence of digoxigenin-labelled DNA molecular weight marker II (Roche Applied Science, France) and vaccum-transferred to a Biodyne Plus membrane (Gelman Sciences, Merck Eurolab, France). The puhA and dcaQ probes labelled with digoxigenin produced by PCR were hybridized as previously described [START_REF] Devers | Horizontal gene transfer of atrazinedegrading genes (atz) from Agrobacterium tumefaciens St96-4 pADP1::Tn5 to bacteria of maizecultivated soil[END_REF].

DNA sequencing

16S rRNA PCR products were cloned into the pGemT-EasyII vector (Promega, Madison, WI, USA). Recombinant clones were identified by a SP6/T7 PCR and plasmids extracted using QIAprep spin miniprep kit and sequenced by Beckman Coulter Genomics (Takeley, USA). The puhA gene, its upstream (For_CCGTAGAGCTCGAAGAGGAA; Rev_GCATCGGTGTTCATGAGGAT) and downstream (For_ GAGGTCATGTTCGAGGAAGC; Rev_TCGGAGGTGTAGCGGTAGAG) sequences, and the partial sequence of dcaQ gene were directly sequenced from PCR products (GATC Biotech, France). Sequences were assembled using SeqMan software (DNASTAR) Sequence comparison was done using BlastN (http://www.ncbi.nlm.nih.gov/BLAST). Multiple alignments were done using ClustalX [START_REF] Thompson | The ClustalX Windows interface: flexible strategies for multiple sequence alignment aided by quality analysis tools[END_REF]. Phylogenetic tree was processed from the alignment with the neighbor joining method using NJ Plot.

The 16S rRNA sequences of BS1, BS2, and SED1 DIU-degrading strains and of SP1 3,4-DCA degrading strain were deposited into the GenBank database (KJ162357, KJ127007, KJ162358, KJ127008, respectively). puhA, puhB and dcaQ sequences, were deposited in the GenBank database (KJ127011, KJ127010, KJ127009, respectively).

Mineralization of diuron

BS2 and SP1 strains were grown in MS-DIU or MS-3,4-DCA media at 28 °C, and then centrifuged at 6000 rpm for 5 min. The pellets were washed twice in Knapp buffer [START_REF] Devers | Horizontal gene transfer of atrazinedegrading genes (atz) from Agrobacterium tumefaciens St96-4 pADP1::Tn5 to bacteria of maizecultivated soil[END_REF] and resuspended to an OD (600 nm) of 0.2 in Knapp buffer containing 30 mg L-1 of DIU and 170 Bq mL-1 of 14C ring-labelled DIU. Mixed bacterial culture suspensions were incubated at 28 °C in a sterile jar under agitation (150 rpm). 14CO2 was trapped in 5 mL of 0.2 M NaOH and radioactivity was periodically measured by liquid scintillation counting (Packard). This experiment was performed in triplicate.

The DIU-mineralization parameters were determined using the Gompertz model [START_REF] Gompertz | On the nature and function expressive of the law of human mortality, and on a new mode of determining the value of life contingencies[END_REF] with the SigmaPlot 4.0 software: y = a exp(-exp(-k(t-ti))), where y is the percentage of DIU mineralization (%), a the maximum percentage of DIU mineralization (%); k the maximum rate of DIU mineralization (d-1); t the time (d), and ti the abscissa of the inflection point (d) (p < 0.005, n= 3, Student t test).

Diuron and 3,4-DCA degradation

DIU or 3,4-DCA degradation ability was evaluated. To produce microbial biomass, cell aliquots were inoculated in MS-DIU or MS-3,4-DCA medium and incubated at 28 °C at 150 rpm. The cells were centrifuged at 6000 rpm for 5 min, and the pellets were washed twice in Knapp buffer. The cells were then suspended at an OD600 of 0.2 in Knapp buffer containing either DIU or 3,4-DCA (30 mg L-1), and incubated as previously described. At different times of incubation, supernatant was collected and analyzed by HPLC (LC Star system, Varian) equipped with a Microsorb-MV C18 column (length 25 cm, internal diameter 4.6 mm, Varian). The solvent system used was methanol added with 0.1% of H3PO4 (75/25; v/v) delivered at a flow rate of 1 mL min-1. DIU and 3,4-DCA were detected at 254 nm at different retention times. These experiments were performed in triplicate and a control was included. Kinetics parameters were determined using the Gompertz model as described in Section 2.8.

Characterization of degrading-or growing-capabilities of the isolated strains

DIU-or 3,4-DCA degrading bacterial strains were grown in corresponding MS medium. Degrading capabilities were assessed by resting cell experiments: bacterial cultures were washed twice in Knapp buffer and then suspended at 0.2 OD600nm in Knapp buffer containing 50 mg L-1 of the phenylureas (isoproturon, linuron, monolinuron, chlorotoluron) or anilines (4-isopropyl-aniline, 3,4-DCA, 3chloroaniline, 4-chloroaniline, 4-bromoaniline and 3-chloro-4-methylaniline). They were incubated at 28 °C under agitation. Aliquots were regularly taken, centrifuged (3,220 g, 10 min) and the supernatants were analyzed by HPLC. Three replicates were performed for each compound.

Growing capabilities were assessed by inoculating hardly any of bacterial culture (0.002 OD600nm) in corresponding MS-medium added with sodium citrate (1 g L-1) and each of the phenylureas or in MS-medium with each of the anilines.

Results

Isolation of diuron-degrading strains

In a previous study, [START_REF] Pesce | Potential for microbial diuron mineralisation in a small wine-growing watershed: from treated plots to lotic receiver hydrosystem[END_REF] showed that repeated applications of DIU had led to the adaptation of the microflora to the mineralization of DIU in the vineyard soil, in the adjacent BS and in the sediments (SED) of the receiving river. To isolate the microorganisms responsible for this mineralization, enrichments were performed on BS and SED samples leading to the isolation of consortia able to degrade DIU without accumulation of metabolites. From these consortia, trials were conducted to isolate pure bacterial strains involved in the process of DIU degradation.

As a result, we isolated three bacteria able to grow on MS-medium containing DIU as sole nitrogen source namely BS1, BS2, and SED1 originating from BS-and SED-samples, respectively. HPLC analyses showed that DIU was entirely dissipated during the growth of these isolates and that concomitantly a metabolite presenting the same retention time that 3,4-DCA was accumulated (data not shown).

To taxonomically characterize these three DIU-degrading isolates, their 16S rRNA sequences were analysed revealing that they were taxonomically close to A. globiformis strain K01-01 (99.3% of similarity) ( Figs. 1 and SM1 of Supplementary Material). Isolates BS1, BS2 and SED1 were named Arthrobacter sp. BS1, Arthrobacter sp. BS2 and Arthrobacter sp. SED1, respectively. They were classified as Bacteria, phylum Actinobacteria, order Actinomycetales, family Micrococcaceae and genus Arthrobacter. These three strains presented identical REP-PCR patterns ( Fig. 2) suggesting that they are either identical or closely related deriving from the same ancestor.

Strain BS2 was further used to characterize DIU-degrading ability in Knapp buffer containing 30 mg L-1 of DIU (128 µM). HPLC monitoring showed that DIU was entirely degraded within 24 h, the maximum degradation rate being of 24.8 ± 1.9 µM h-1 (Fig. 3,panel A). Concomitantly, the accumulation of a metabolite showing identical retention time to that of 3,4-DCA was observed. Its accumulation was equimolar to the dissipation of DIU, its maximum apparition rate being of 24.5 ± 3.5 µM h-1. The ability of strain BS2 to degrade and to grow on different phenylureas was checked (Table 1) showing that it was able to use DIU and chlorotoluron for its growth. Interestingly, even if resting cells showed that BS2 was able to degrade linuron and monolinuron to their corresponding aniline derivatives, it cannot grow on them. Finally, BS2 was unable to degrade isoproturon and to use it for its growth (Table 1). puhA and puhB DIU-degrading gene sequences, were searched by PCR on DNA extracted from the enrichment culture or pure degrading-strains. puhB amplicon of 665 bp was obtained with DNA from enrichment cultures. Interestingly, PCR analyses carried out with the pure degrading strains produced puhA amplicon and not puhB (data not shown). Sequencing of the PCR products revealed that the puhB amplicon amplified from the enrichment culture shared more than 95% of similarity with the puhB gene from M. brisbanense strain JK1 (593/624 bp). In addition, sequencing of puhA amplicons amplified from DIU-degrading strains were 99% of similarity with that of A. globiformis strain D47 (653/655 pb). Southern blot analysis of DIU-degrading isolates hybridized with puhA probe gave a single signal on a 3.1 kb NruI fragment and 8.2 kb SmaI fragment ( Fig. 4).

PCR reactions were performed to determine whether the upstream-and downstream-sequences surrounding puhA gene in BS2 strain were similar to those of A. globiformis strain D47 (EU851877). Amplifications performed using primers either located 464 bp upstream or 524 bp downstream puhA coupled with primers anchored in puhA sequence yielded in two PCR products of expected sizes (data not shown). Sequencing of these PCR products led to the complete sequence of puhA as well as its upstream (444 bp) and downstream (473 pb) sequence on BS2 (GenBank accession number KJ127011). It revealed that puhA sequence shared 99.8% similarity with puhA form A. globiformis strain D47 (1369/1371 bp). At the protein level, two amino acids were substituted as compared to the known PuhA (146L-146M and 335L-335I), these substitutions being positive. We found that both the sequences located upstream and downstream to puhA were 100% similar to those found in A. globiformis strain D47 ( Fig. 5).

Isolation of 3,4-DCA degraders

We attempted to isolate the strains responsible for the degradation of 3,4-DCA in the enrichment culture. One isolate able to degrade 3,4-DCA was isolated from the SED enrichment culture using MS medium containing 3,4-DCA as sole nitrogen and carbon sources. Unfortunately, isolation of 3,4-DCA degraders from BS enrichment culture was unsuccessful. 16S rRNA sequence indicated that this was highly similar to Achromobacter sp. Ch1 (99.4% on 1453 bp) ( Fig. 1). Consequently, the isolate was named Achromobacter sp. SP1 and classified as Bacteria, class Betaproteobacteria, order Burkholderiales, family Alcaligenaceae and genus Achromobacter.

The ability of SP1 to degrade 3,4-DCA was evaluated by monitoring its dissipation by HPLC (Fig. 3, panel B). SP1 was able to completely dissipate 185 µM of 3,4-DCA in 21 h, and no metabolites were detected. The study of catabolic ability of SP1 was assessed against a range of anilines showed that it was able to grow and degrade 3-chloro-4-methyl-aniline, 4-isopropylaniline, 4-chloroaniline, 3chloroaniline and 4-bromoaniline (Table 1). PCR targeting the gene dcaQ encoding a part of a multicomponent enzyme responsible for 3,4-DCA degradation was performed on SP1. It revealed the presence of this gene sharing 99% similarity with the one from Comamonas testosteroni (227/229 bp); at the amino acid level, it shares 93-97% identity with other known DcaQ sequences.

Diuron mineralizing ability of the Arthrobacter sp. BS2 and Achromobacter sp. SP1 consortium

The ability of an artificial consortium made of BS2 and SP1 to entirely degrade DIU was assessed revealing that it was able to entirely dissipate DIU within 35 h. Transient accumulation of 3,4-DCA was observed (Fig. 3,panel C). This accumulation was equimolar to the degradation of DIU indicating that in the early stage, SP1 was not active. However, after 20 d incubation, no more 3,4-DCA was detected in the culture medium indicating that SP1 had degraded it all. DIU mineralization observed in the artificial consortium showed that more than 50% of 14C-DIU evolved to CO2 within 5 d of incubation (Fig. 3, panel D).

Discussion

DIU mineralization has already been reported from different compartments at the watershed level of the Morcille river [START_REF] Pesce | Potential for microbial diuron mineralisation in a small wine-growing watershed: from treated plots to lotic receiver hydrosystem[END_REF]. Our study aimed at studying microbial populations involved in DIU degradation. To do so samples were collected in the buffer strip (BS) and sediments (SED) of the watershed. As expected BS and SED samples periodically exposed to DIU, were able to mineralize up to 20% of the 14C-ring-labeled DIU. Analyse of the DIU-genetic potential indicated the presence of puhB gene sequence in enrichments cultures confirming [START_REF] Pesce | Response of a diuron-degrading community to diuron exposure assessed by real-time quantitative PCR monitoring of phenylurea hydrolase A and B encoding genes[END_REF] reporting its presence in a vineyard plot adjacent to BS. Surprisingly, puhA sequence which was neither detected in the enrichment culture nor in BS and SED samples was found in DIU-degrading isolates. To explain this discrepancy between molecular and Pasteurian approaches, one could hypothesize on one hand, that puhA sequences were below PCR detection limit in the enrichment cultures or on the other hand, that microbial populations harbouring puhB were not culturable in our conditions. Anyhow, this is the first report of the co-occurrence of puhA and puhB genes in the same environment. It confirmed the existence of DIU-degrading genetic potential and of DIU-mineralizing ability among BS and SED microflora which might be attributed to the adaptation of indigenous microbiota to metabolize DIU.

Enrichment cultures were conducted from composite BS or SED samples with DIU used as a sole nitrogen source. Although both BS and SED enrichment cultures were able to mineralize DIU, no bacterial populations able to fully mineralize this herbicide was isolated. Isolation trials led to the isolation of three DIU-degrading pure isolates, two originating from BS (i.e. BS1 and BS2) and one from SED samples (SED1). This further confirms that both BS and SED samples harbour similar microbial populations able to transform DIU as observed earlier [START_REF] Pesce | Potential for microbial diuron mineralisation in a small wine-growing watershed: from treated plots to lotic receiver hydrosystem[END_REF]Pesce et al., 2010b). None of these isolates mineralize DIU, but equimolarly transformed DIU to 3,4-DCA. These isolates did not only have similar phenotypes and REP profiles. In addition, their 16S rRNA sequences were up to 99.3% similar to A. globiformis strain K01-01. Interestingly, 16S rRNA sequences showed 97% with that of A. oxydans (X83408) the closest relative of A. globiformis strain D47 and 99% of similarity with A. globiformis (X80736) [START_REF] Turnbull | Degradation of substituted phenylurea herbicides by Arthrobacter globiformis strain D47 and characterization of a plasmidassociated hydrolase gene, puhA[END_REF]. Although Arthrobacter sp. BS1, BS2 and SED1 are grouped with A. globiformis strain D47 within the A. globiformis group, our isolates diverged slightly from the last which is inferred to A. oxydans type. The isolation of BS1, BS2 and SED 1 isolates from Beaujolais vineyard (France) highly similar to A. globiformis D47 isolated one decade ago from Deep Slade soil (UK) poses a challenging question regarding their evolutionary origin [START_REF] Cullington | Rapid biodegradation of diuron and other phenylurea herbicides by a soil bacterium[END_REF]. It suggests that DIU-degradation ability is specific to Arthrobacter taxa. One may nevertheless keep in mind that this specificity can also reflect a good culturability of Arthrobacter species compared to possible other DIU-degrading populations. However, similar observations have been done for other phenylureas such as isoproturon which was found to be mineralized by different populations related to Sphingomonads such as Sphingomonas sp. SRS2, Sphingobium YBL10 and Sphingomonas sp. SH isolated from Danish, Chinese and French agricultural soils, respectively [START_REF] Sorensen | Isolation from agricultural soil and characterization of a Sphingomonas sp. able to mineralize the phenylurea herbicide isoproturon[END_REF][START_REF] Sun | Isolation and characterization of three Sphingobium sp. strains capable of degrading isoproturon and cloning of the catechol 1,2-dioxygenase gene from these strains[END_REF][START_REF] Hussain | Isolation and characterization of an isoproturon mineralizing Sphingomonas sp. strain SH from a French agricultural soil[END_REF]. However, the opposite figure is found for s-triazine degraders which are spread in various Gramnegative and Gram-positive bacteria populations [START_REF] Udikovic-Kolic | Evolution of atrazine-degrading capabilities in the environment[END_REF]. In order to study in more details, DIU-degrading genetic potential, we searched among our isolates for the presence of phenylurea hydrolase genes. Although puhB gene was detected in the enrichment cultures, only puhA was found in our isolates, indicating that we only partially characterized the populations involved in the biodegradation of DIU. Interestingly, Southern blot analysis revealed the existence of 8.2 kb SmaI fragment harbouring puhA gene in our isolates corresponding to a fragment similar in size of pHRIM622 the catabolic plasmid of A. globiformis strain D47 [START_REF] Khurana | Characterization of the phenylurea hydrolases A and B: founding members of a novel amidohydrolase subgroup[END_REF]. In addition, sequencing showed that the puhA sequence of BS2 was 99.8% to that of A. globiformis strain D47 and that upstream and downstream sequences of BS2 were 100% similar to that of A. globiformis strain D47. This indicates that the DIU-degrading genetic potential of our three isolates is similar to that of A. globiformis strain D47 although they have been isolated from distinct geographic regions at different periods of time. Interestingly, one could noticed that BS1/BS2 and SED1strains isolated from BS and SED samples respectively, were belonging to the same genus, having identical REP profiles and DIU-degrading genetic potential thereby suggesting that similar DIU-degraders can be found in different environmental niches. This is in accordance with previous report highlighting the importance of run-off in the connection of terrestrial and aquatic compartments ( Pesce et al., 2010b).

We showed that like A. globiformis strain D47 [START_REF] Cullington | Rapid biodegradation of diuron and other phenylurea herbicides by a soil bacterium[END_REF], BS2 was able to transform a range of phenylureas including DIU, chlorotoluron, linuron and monolinuron to corresponding derivative anilines but not isoproturon. This might be explained by the catalytic efficiency of PuhA which is higher for DIU or chlorotoluron (kcat/Km value of 0.5 and 0.2 µM-1 min-1, respectively) than for isoproturon (kcat/Km value of 0.0074 µM-1 min-1) [START_REF] Khurana | Characterization of the phenylurea hydrolases A and B: founding members of a novel amidohydrolase subgroup[END_REF]. Interestingly, one could observe that BS2 only grew on N-Dimethyl ureas (DIU and chlorotoluron) and not on N-Methoxy-N-methyl ureas (linuron and monolinuron) although it was able to degrade all of them. One could hypothesize either that DIU degradation pathway is induced by N-Dimethyl ureas but not by N-Methoxy-N-methyl ureas or that N-methyl-N-methoxy-carbamic acid resulting from monolinuron and linuron transformation cannot be used for its growth.

Having isolates transforming DIU to 3,4-DCA we have been intensively searching for 3,4-DCA degraders. This led to the isolation of Achromobacter sp. SP1 able to use 3,4-DCA as sole carbon and nitrogen sources solely from the SED enrichment culture. Environmental survey of the quality of this river regularly shows the presence of traces of 3,4-DCA ( Pesce et al., 2010a) suggesting that microbial community of the sediments have a chronic history of exposure to this pollutant thereby explaining their adaptation to its degradation. One could hypothesize a low exposure of soil microbial community to 3,4-DCA in reason of its adsorption to soil thereby explaining why no 3,4-DCA degraders can be isolated from soil. SP1 was not only able to degrade 3,4-DCA but also a wide range of related anilines such as 3-chloro-4-methyl-aniline, 4-isopropylaniline, 4-chloroaniline, 3chloroaniline or 4-bromoaniline. This wide range catabolic ability has also been observed for Variovorax sp. WDL1 a linuron mineralizing strain which degrades 3,4-DCA, 3-and 4-chloroaniline and aniline [START_REF] Dejonghe | Synergistic degradation of linuron by a bacterial consortium and isolation of a single linuron-degrading Variovorax strain[END_REF]. It is opposite to the specificity of Sphingomonas sp. SH an isoproturon mineralizing isolate only able to degrade 4-isopropylaniline (4-IA) [START_REF] Hussain | Isolation and characterization of an isoproturon mineralizing Sphingomonas sp. strain SH from a French agricultural soil[END_REF]. Interestingly we showed that SP1 had dcaQ gene which was 99% similar to that of C. testosteroni WDL7. This gene belonging to the dcaQTA1A2BR gene cluster encodes an enzyme responsible for the transformation of 3,4-DCA to chlorocatechol in Variovorax sp. Strain SRS16 [START_REF] Bers | A novel hydrolase identified by genomic-proteomic analysis of phenylurea herbicide mineralization by Variovorax sp strain SRS16[END_REF]. This suggests that SP1 catalyses the degradation of anilines to chlorocatechol which might then be metabolized through the ortho-cleavage pathway [START_REF] Bers | A novel hydrolase identified by genomic-proteomic analysis of phenylurea herbicide mineralization by Variovorax sp strain SRS16[END_REF].

Our study suggests that the DIU-mineralization observed in the BS and SED enrichment cultures may result from the cooperation between two microbial populations one harbouring the puhA gene catalysing the upper pathway transforming DIU to 3,4-DCA and another one harbouring the dcaQ gene catalysing the lower pathway leading to the degradation of 3,4-DCA. This is an example of patchwork assembly of catabolic gene modules in different microbial populations (Arthrobacter sp. BS1, BS2 or SED1 [puhA]; Achromobacter sp. SP1 [dcaQ]) in order to use phenylurea herbicide as a source of carbon and energy. On different chemicals such as s-triazines, similar examples of cooperative metabolism were shown between populations catalyzing the upper pathway transforming atrazine to cyanuric acid and populations metabolising the lower pathway opening the s-triazine ring to completely degrade cyanuric acid [START_REF] Smith | Cooperative catabolic pathways within an atrazinedegrading enrichment culture isolated from soil[END_REF][START_REF] Martin-Laurent | of the maize rhizosphere on the genetic structure, the diversity and the atrazine-degrading gene composition of the cultivable atrazine-degrading communities[END_REF][START_REF] Udikovic-Kolic | Taxonomic and functional diversity of atrazine-degrading bacterial communities enriched from agrochemical factory soil[END_REF][START_REF] Udikovic-Kolic | Evolution of atrazine-degrading capabilities in the environment[END_REF]. The artificial consortium made of BS2 and SP1 led to the mineralization of DIU offering interesting perspectives to develop mixed inoculants for the bioaugmentation of buffer strip to improve their mitigation ability.

Conclusions

The isolation of different isolates able to degrade DIU confirmed that both terrestrial and aquatic microbial communities adapted in a similar manner to accelerated biodegradation of DIU. Interestingly, these isolates are closely related to A. globiformis strain D47 another DIU degrader isolated one decade ago. In addition, the DIU-degrading genetic potential was shown to be extremely conserved suggesting its widespread dispersion. Achromobacter sp. SP1 was shown to degrade 3,4-DCA formed during DIU degradation as well as a range of anilines. Altogether this study suggests that DIU mineralization is occurring through a cooperative metabolism between microbial populations catalysing the transformation of DIU to 3,4-DCA and others degrading this intermediary metabolite.

Acknowledgments

This project was supported by the French National Office for the Aquatic Environment (ONEMA). The authors thank Céline Guillemain of Irstea's Water Chemistry Laboratory (LAMA) for analysis of DIU.

Supplementary data

Phylogenetic tree was established with 16S rRNA sequences used in the paper of [START_REF] Turnbull | Degradation of substituted phenylurea herbicides by Arthrobacter globiformis strain D47 and characterization of a plasmidassociated hydrolase gene, puhA[END_REF] describing the isolation and the characterization of Arthrobacter sp. D47 from Deep Slade soil (UK).Only branches having a bootstrap values up to 900 of 1000 iterations are highlighted by a black dot. The strains used for phylogenetic analysis and the GenBank accession numbers of the 16S rRNA genes are: Arthrobacter agilis (X80748), Renibacterium salmoninarum (X51601), Arthrobacter globiformis (X80736), Arthrobacter ramousus (X80742), Arthrobacter pascens (X80740), Arthrobacter oxydans (X83408) and Arthrobacter polychromogenes (X80741).


Yinan Li

• Asim

Jack Dongarra

Keith Seymour

Aurèlie Hurault

A Yarkhan
email: yarkhan@eecs.utk.edu

Enabling workflows in GridSolve: request sequencing and service trading

Keywords: Grid computing, Workflow applications, Service trading

GridSolve employs a RPC-based client-agent-server model for solving computational problems. There are two deficiencies associated with GridSolve when a computational problem essentially forms a workflow consisting of a sequence of tasks with data dependencies between them. First, intermediate results are always passed through the client, resulting in unnecessary data transport. Second, since the execution of each individual task is a separate RPC session, it is difficult to enable any potential parallelism among tasks. This paper presents a request sequencing technique that addresses these deficiencies and enables workflow executions. Building on the request sequencing work, one way to generate workflows is by taking higher level service requests and decomposing them into a sequence of simpler service requests using a technique called service trading. A service trading component is added to GridSolve to take advantage of the new dynamic request sequencing. The features described here include automatic DAG construction and data dependency analysis, direct interserver data transfer, parallel task execution capabilities, and a service trading component.

Introduction

GridSolve [8] employs a brokered-RPC client-agent-server model for handling computational problems in a distributed computing or grid environment (Fig. 1). A complete RPC session in GridSolve consists of two stages. In the first stage, the client sends a request for a remote service to the agent, which returns a list of capable servers ordered by some measure of their capability. The actual remote service call takes place in the second stage. The client sends input data to a selected server; the server handles the request and returns the result back to the client.

This request-reply RPC model forms a star topology of requests and replies with the client at the center, since all data traffic must involve the client. The is efficient for solving computational problems consisting of a single task. However, when a computational problem forms a workflow consisting of a set of service requests with data dependencies, this model is highly inefficient due to two deficiencies. First, intermediate results are passed among tasks via the client, resulting in additional, unnecessary data traffic between the client and the servers. Second, since the execution of each individual task is a separate RPC session, it is difficult to exploit the potential parallelism among tasks. For example, consider the following sequence of GridRPC calls: grpc_call("func1", ivec, ovec1, ovec2, n); grpc_call("func2", ovec1,n); grpc_call("func3", ovec2, n); grpc_call("func4", ovec1, ovec2, ovec, n);

In this example, the outputs of func1, namely ovec1 and ovec2, are returned back to the client and immediately sent from the client to the servers running func2 and func3, resulting in two unnecessary data movements. Figure 2 illustrates the data flow for the above calls. This example demonstrates that when data dependencies exists among tasks, it may be unnecessary to transfer intermediate results back to the client, since such results will be needed immediately by the subsequent tasks.

To eliminate unnecessary data traffic involving the client, GridSolve has incorporated and enhanced a technique called request sequencing. An earlier version of GridSolve implemented a much simpler version of request sequencing [START_REF] Arnold | Request sequencing: optimizing communication for the grid[END_REF][START_REF]The NetSolve Project[END_REF] which avoided unnecessary data transfers back to the client, but forced all the requests involved in the sequence to run on a single server and ignored any potential parallelism in the tasks. The current work improves on the older request sequencing techniques by exposing and exploiting parallelism in the tasks.

The objective of this work is to provide a technique for users to efficiently solve computational problems in GridSolve by constructing workflow applications that consist of a set of tasks, among which there exist data dependencies.

In GridSolve request sequencing, a request is defined as a single GridRPC call to an available GridSolve service. GridRPC [START_REF] Seymour | Overview of GridRPC: a remote procedure call API for grid computing[END_REF] is a standardized API that describes a Remote Procedure Call (RPC) interface in a Grid computing environment. The terms request, service request, and task are used interchangeably in this paper. For each workflow application, the set of requests is scanned, and the data dependency between each pair of requests is analyzed. The output of this analysis is a DAG representing the workflow. The workflow scheduler then schedules the DAG to run on the available servers. A set of tasks can potentially be executed concurrently if the DAG permits it. In Sect. 2, the details of request sequencing are presented.

In order to eliminate unnecessary data transport when tasks are run on multiple servers, the standard RPC-based computational model of GridSolve must be extended Fig. 2 An example of the standard data flow in GridSolve Fig. 3 The data flow in Fig. 2 with direct interserver data transfer to support direct data transfer among servers. Figure 3 illustrates the alternative data flow of Fig. 2, with direct data transfer among servers. Supporting direct inter-server data transfer requires server-side data storage. A server may have already received some input arguments and stored them to the local storage, while waiting for the additional arguments. In addition, a server may store its outputs to the local storage in order to later transfer them to the servers that need them. In Sect. 3, we present a method of using special data files as data storage. Section 4 discusses approach to scheduling the workflow on the available resources, and Sect. 5 presents the request sequencing API in GridSolve.

Building on the request sequencing work, one possible way to generate workflows is by taking higher level service requests and decomposing them into a sequence of simpler service requests using a technique called service trading. Section 6 presents some of the ideas involved in service trading, though a detailed presentation of service trading in GridSolve is available separately [START_REF] Hurault | Intelligent service trading for distributed network services in GridSolve[END_REF].

Workflow modeling and automatic dependency analysis

Data dependencies and directed acyclic graphs

In GridSolve request sequencing, the workflow is represented by a DAG. Each node in the DAG represents a request (task), and each edge represents the data dependency between requests. Consider our usual example of GridRPC requests, which have various input (ivec) and output (ovec) data items. grpc_submit("return_int_vector",ivec,n,ovec); grpc_submit("vpass_int", ovec, n); grpc_submit("iqsort", ovec, n); grpc_submit("int_vector_add5",n,ovec,ovec2);

The dependencies between the requests are implicit in the definition of the data items (input, output, inout) and in the sequential order that the requests are submitted. Given a set of GridRPC calls, we identify four types of data dependencies: Fig. [START_REF] Berriman | Montage: a grid-enabled engine for delivering custom science-grade mosaics on demand[END_REF] An example DAG with all three kinds of non-scalar data dependencies Input-After-Output (RAW) Dependency A service reads a data argument after a previous service writes that data argument. The actual data involved in the dependency will be transferred directly between servers, without the client being involved. Output-After-Input (WAR) Dependency One service writes an data argument after a previous service reads that data argument. The write cannot proceed until the read completes. This is sometimes also called a false dependency, since it can be eliminated by creating copies of the data. However, we do not attempt to eliminate false dependencies at this time. Output-After-Output (WAW) Dependency This represents the case where two requests in the sequence write the same output argument. The output of the request that is depended on will not be transferred back to the client since the shared data will be overwritten shortly by the depending request. Conservative-Scalar Dependency This type of scalar data dependency occurs in the conservative sequencing mode that will be introduced shortly.

If all these dependencies are maintained, then the sequential program order will be preserved. The first three types of dependencies apply to nonscalar arguments such as vectors and matrices. Figure 4 gives an example DAG with all types of nonscalar data dependencies (RAW, WAR, and WAW). For scalar arguments, it is much more difficult, and even impossible to determine if two scalar arguments are actually referencing the same data, since in GridSolve scalar data can be passed by value as well as by reference. Our solution is to provide users with several modes that use different approaches for analyzing data dependencies among scalar arguments. The supported modes are as follows:

Optimistic Mode In this mode, scalar arguments are ignored when analyzing data dependencies. Conservative Mode In this mode, two successive requests with one having an input scalar argument and the other having an output scalar argument, are viewed as having a conservative-scalar dependency, if these two scalar arguments have the same data type. Restrictive Mode In this mode, scalar arguments are restricted to be passed by reference, and data dependencies among scalar arguments are analyzed as usual. Fig. 5 The example DAG in Fig. 4 with an additional scalar data dependency

Figure 5 depicts what it looks like in Fig. 4 with one conservative scalar dependency.

Automatic dependency analysis and DAG construction

In GridSolve, nonscalar arguments are always passed by reference. In addition, each argument has some attributes associated with it specified in the service description. These attributes describe the data type of the argument (integer, float, double, etc.), the object type of the argument (scalar, vector, or matrix), and the input/output specification of the argument (IN, OUT, or INOUT). These attributes, along with the data reference, can be used to determine if two arguments refer to the same data item. The pseudocode of the algorithm for automatic DAG construction and dependency analysis is presented in Algorithm 1. Notice that in the algorithm, each node is assigned a rank, which is an integer representing the scheduling priority of this node. The algorithm for workflow scheduling and execution uses this rank information to schedule nodes to run. The algorithm for workflow scheduling and execution is presented in Sect. 4.

As an example, considering the following workflow (this workflow is programmed using the API functions that will be introduced in Sect. 5): grpc_sequence_begin(OPTIMISTIC_MODE); grpc_submit("return_int_vector",ivec,n,ovec); grpc_submit("vpass_int", ovec, n); grpc_submit("iqsort", ovec, n); grpc_submit("int_vector_add5",n,ovec,ovec2); grpc_sequence_end(0);

The DAG produced by the above algorithm (Fig. 6) may contain redundant edges from the perspective of both execution and data traffic. For example, in Fig. 6, the RAW dependency between return_int_vector and int_vector_add5 is redundant, since the input argument ovec of int_vector_add5 will come from iqsort instead of return_int_vector. Removing this redundant edge will affect neither the execution order nor the effective data flow of the DAG. The final step in building and analyzing the DAG is to remove all such redundant dependencies. Figure 7 shows the DAG in Fig. 6 after all redundant edges are removed.

Algorithm 1

The algorithm for automatic DAG construction and dependency analysis 1: Scan the set of tasks, and create a DAG node for each task; 2: Let NodeList denote the list of nodes in the DAG; 3: Let N denote the number of nodes in the DAG; 4: for i = 1 to N -1 do

5:

Let P denote node NodeList[i], and PArgList denote the argument list of node P;

6: Assign the appropriate rank to node P ; 24: end for 3 Interserver direct data transfer One approach to interserver data transfer via a Grid file system called Gfarm was introduced in [START_REF] Tanimura | Design and implementation of distributed task sequencing on GridRPC[END_REF]. This is similar to the Distributed Storage Infrastructure (DSI) implementation [START_REF] Beck | The Internet2 distributed storage infrastructure project: an architecture for Internet content channels[END_REF] in GridSolve. In GridSolve, DSI is mainly used for building external data repositories to provide large chunks of input data and output storage to tasks running on servers. Both approaches use external libraries that must be installed and configured prior to use.

for j = i + 1 to N do 7: Let C denote node NodeList[j ],
In this paper, we describe our approach to direct interserver data transfer via file staging. File staging is a service in GridSolve that moves files between two servers. Our approach uses file staging as a medium of transferring intermediate data between two servers. Specifically, intermediate results are first saved as data files, and are then staged to the target servers, on which they are restored by the tasks depending on Fig. [START_REF] Cosnard | Automatic task graph generation techniques[END_REF] An example DAG before redundant edges are removed Fig. 7 The example DAG in Fig. 6 after all the redundant edges are removed them. This approach not only eliminates unnecessary data transport, it also protects the system from losing data, since data can be easily retrieved from locally saved files. In our approach, servers that need an intermediate result "pull" the that data from the servers that produce it. It is therefore necessary for the server that needs an intermediate result to know which server produces it. Our solution is to have the server that produces the intermediate result send a data handle via the client to the servers that need the result. A data handle is a small data structure that describes various aspects of an argument in GridSolve, including object type, data type, storage pattern, task name, server name, data size, file name, and file path. The "pull" approach to data-movement was used because it allows a more dynamic approach to scheduling.

In GridSolve request sequencing, data handles are used as virtual pointers to intermediate results stored in special data files. Data handles are passed between two servers via the client. The recipient of a data handle, the server that needs the data referenced in the data handle, asks for the intermediate data by sending a request to the server that stores the data. Upon receiving the request, the server that stores the intermediate data sends it directly to the requester via file staging, without the client being involved.

Workflow scheduling and execution

As mentioned in Sect. 2, after the dependency analysis, a DAG is built for a workflow and each node in the DAG is assigned an integer representing the rank of that node. The rank of a node indicates the scheduling priority of the node. The client will schedule and execute a workflow based on the rank of each node. Specifically, nodes with the same rank are independent of each other and can be scheduled to run simultaneously. Initially, the client will schedule the nodes with the highest rank (rank 0) to start executing. Notice that all the input arguments for such nodes should be available at the time of execution. The client will schedule the remaining nodes to run if and only if both the following two conditions are satisfied: (1) all the input arguments are available, and (2) all the dependencies involving the node are resolved.

A dependency is resolved if the parent node in the DAG has finished its execution. A resolved dependency is removed from the DAG. The algorithm for workflow scheduling and execution is shown in Algorithm 2. The client executes the algorithm and acts as the manager of DAG execution. The algorithm uses level-based clustering to group nodes that can be scheduled to run simultaneously. Nodes with the same rank are viewed as on the same scheduling level, and are clustered and scheduled to run simultaneously. Notice that the routine AssignRequestToServers assigns the nodes on the current scheduling level to the available servers. The assignment of requests to the available servers is critical to the overall performance of the execution of a DAG. In our current implementation, we use a simple round-robin strategy to assign tasks on a specific level onto the available servers.

The above round-robin scheduling algorithm is primitive and probably will be highly inefficient when the workflow is complex. A major deficiency of the algorithm is that it does not take into consideration the differences among tasks and does not really consider the mutual impact between task clustering and network communication. In addition, sometimes it will be helpful for reducing the total execution Algorithm 2 The algorithm for workflow scheduling and execution 1: Let N denote the total number of nodes in the workflow to be scheduled; 2: Let M denote the number of requests that have been scheduled; time if some tasks on a specific scheduling level are scheduled to run before other tasks on the same level. The algorithm, however, does not support this kind of out-oforder execution of tasks on the same scheduling level. This primitive algorithm will be replaced by a more advanced one in our future work.

M = M + K; 12: until M = N

GridSolve request sequencing API

One important design goal of GridSolve request sequencing is to ease the programming of workflow applications by providing users with a small set of API functions, presented in Table 1. During the execution of the client code after gs_sequence_begin is called, GridSolve collects each service request submitted via gs_submit commands and creates a dependency-based DAG from those requests. It is during the dependency analysis stage that the dependency mode is used to determine scalar dependencies. Once gs_sequence_end is called, and no other services requests will be added to the DAG, then the DAG is scheduled and executed.

The current API does not support advanced workflow patterns such as conditional branches and loops. We are planning to investigate such advanced workflow patterns in the future to make GridSolve request sequencing a more powerful technique for workflow programming.

Generating workflows via intelligent service trading

We have defined an API for submitting a sequence of service requests to GridSolve so that a workflow DAG can be automatically inferred from the sequence of GridSolve requests. The DAG can be executed using GridSolve so that it preserves the sequential semantics of the original sequence of service requests, reduces data movement requirements, and allows potential parallelism to be exploited.

However, the users still needs to know about the services that are currently available, and to choose the appropriate sequence of services that will satisfy the users overall goal. In recent work, we have turned our attention to considering techniques for the generation of a workflow from a higher level description of a problem. Many complex problems can be handled by the combination of different sets of available services. The process of service trading [START_REF] Hurault | Mathematical service trading based on equational matching[END_REF] searches for the appropriate sequence of services to satisfy the complex problem at hand.

A service trading framework has been incorporated into the GridSolve middleware system on an experimental basis [START_REF] Hurault | Intelligent service trading for distributed network services in GridSolve[END_REF]. A complex problem request is described within the system using a higher-level mathematical description. The services provided by GridSolve are described using similar mathematical descriptions. For example, matrix addition (saxpy) and multiplication (sgemm) can be described using this algebraic specification as: Matrix x, y : daxy(x, y) = x + y Scalar α, β, Matrix x, y, z : dgemm(α, x, y, β, z) = α * x * y + β * z When a request for a higher-level problem is received, the service trader component examines the available services and uses equational unification to search for and compose a sequence of available services that satisfy the complex higher-level request. This sequence of related service requests is then executed as a distributed workflow using the request sequencing API in GridSolve. Please see [START_REF] Hurault | Intelligent service trading for distributed network services in GridSolve[END_REF] for details about the integration of service trading into GridSolve.

As a demonstration of the capabilities of the combination of GridSolve with service trading, a set of linear algebra services (e.g., level 3 BLAS and LAPACK) have been enhanced with algebraic descriptions in order to support service trading. However, the ideas behind service trading are generalizable, so any complex process that can be described with the appropriate algebraic description can be incorporated in this framework.

The ease-of-use of this approach is demonstrated from the Matlab client interface supported by GridSolve: The service trader analyzes the input data items and their operations, discovers available services that could be composed to satisfy these operations (e.g., daxpy, dgemm), tries multiple methods of composing these services, selects an appropriate sequence of services, and submits the services requests via the GridSolve request sequencing API. Please see [START_REF] Hurault | Mathematical service trading based on equational matching[END_REF] for more information about the equational matching used in intelligent service trading. Using the service trader with GridSolve makes the users service requests more efficient by the following two factors. First, the service trader evaluates the computational cost of the various service choices for the users specific data in order to choose more efficient services. Second, the request sequencing API enables the parallelism in the sequence of requests. There is a cost to the analysis performed by the service trader, but we expect to minimize this cost in future work.

The major advantages provided by the combined framework are ease-of-use and transparency. The end user does not have to be knowledgeable in grid computing, mathematical libraries, algorithmic complexity, data dependency analysis, parallel asynchronous execution, fault-tolerance, or any of the details that are transparently handled by this system. The framework provides fault tolerance at various levels of failure. If a single service fails, it is transparently retried; if all copies of a service have failed, the trader can formulate the complex request as different combination of services. The user need not be aware of the exact composition of services that satisfies the request.

Applications and experiments

This section presents experiments using GridSolve request sequencing to build practical workflow applications. The first application is to implement Strassen's algorithm for matrix multiplication. As shown below, Strassen's algorithm works in a layered fashion, and there are data dependencies between adjacent layers. Thus, it is natural to represent Strassen's algorithm as a workflow using GridSolve request sequencing.

The second application is to build a Montage [START_REF] Berriman | Montage: a grid-enabled engine for delivering custom science-grade mosaics on demand[END_REF][START_REF]The Montage Project[END_REF] workflow for creating science-grade mosaics of astronomical images. Montage is a portable toolkit for constructing custom science-grade mosaics by composing multiple astronomical images.

Experiments with Strassen's algorithm

This subsection discusses a series of experiments with the implementation of Strassen's algorithm using GridSolve request sequencing. The servers used in the experiments are Linux boxes with Dual Intel Pentium 4 EM64T 3.4 GHz processors and 2.0 GB memory. The client, the agent, and the servers are all connected via 100 Mb/s Ethernet.

Implementation

Strassen's algorithm is a fast divide-and-conquer algorithm for matrix multiplication. The computational complexity of this algorithm is O(n 2.81 ), which is better than the O(n 3 ) complexity of the classic implementation. Strassen's algorithm is recursive and works in a block, layered fashion, as shown by Table 2. Table 2 illustrates the outline of a single level recursion of the algorithm [START_REF] Song | Experiments with Strassen's algorithm: from sequential to parallel[END_REF].

As shown in Table 2, Strassen's algorithm is organized in a layered fashion, and there are data dependencies between adjacent layers. Thus, it is natural to represent a single level recursion of the algorithm as a workflow and construct the algorithm using GridSolve request sequencing. It can be seen that on each layer, tasks can be performed fully in parallel, since there is no data dependency among tasks on the same layer. For instance, the seven submatrix multiplications (Q1 to Q7) can each be executed by a separate process running on a separate server. 2 The outline of a single level recursion of Strassen's algorithm

Results and analysis

T 1 = A 11 + A 22 T 2 = A 21 + A 22 T 3 = A 11 + A 12 T 4 = A 21 -A 11 T 5 = A 12 -A 22 T 6 = B 11 + B 22 T 7 = B 12 -B 22 T 8 = B 21 -B 11 T 9 = B 11 + B 12 T 10 = B 21 + B 22 Q 1 = T 1 × T 6 Q 2 = T 2 × B 11 Q 3 = A 11 × T 7 Q 4 = A 22 × T 8 Q 5 = T 3 × B 22 Q 6 = T 4 × T 9 Q 7 = T 5 × T 10 C 11 = Q 1 + Q 4 -Q 5 + Q 7 C 12 = Q 3 + Q 5 C 21 = Q 2 + Q 4 C 22 = Q 1 -Q 2 + Q 3 + Q 6
Fig. 8 The execution time of Strassen's algorithm as a function of N on a single server, both with and without interserver data transfer server is used. It can be seen in the figure that the computational performance with direct interserver data transfer is consistently better than that without the feature. This figure shows the case that only one server is used. In this case, intermediate results are passed between tasks locally within the single server when direct inter-server data transfer is enabled. When multiple servers are used, intermediate results are transferred directly among servers. Considering that servers are typically connected using high-speed interconnections, the elimination of unnecessary data traffic will still be helpful in boosting the performance in the case that multiple servers are used. Figure 9 plots the execution time as a function of N of Strassen's algorithm on 4 servers, both with and without interserver data transfer. The same conclusion that eliminating unnecessary data transport is beneficial can be obtained as in Fig. 8. It can be seen in Figs. 8 and9 that parallel execution in this case is disappointingly ineffective in improving the computational performance. This is attributed to several important reasons. As discussed above, in the case that a single server is used, intermediate results are passed between tasks locally within the single server, resulting in no real network communication. In contrast, when multiple servers are used, some intermediate results have to be passed among tasks running on different servers, resulting in real network transfer of large chunks of data. Considering that the client, the agent, and the servers are all connected via 100 Mb/s Ethernet, the overhead of Fig. 9 The execution time of Strassen's algorithm as a function of N on four servers, both with and without interserver data transfer network traffic can be relatively large. Therefore, the effect of parallel execution in improving the overall performance is largely offset by the overhead of additional network traffic. In addition, the overhead within the GridSolve system further reduces the weight of the time purely spent on computation in the total execution time, making it even less effective to try to reduce the computation time by parallel execution. Another important reason is that the primitive algorithm for DAG scheduling and execution is highly inefficient for complex workflows, as discussed in Sect. 4. The above result indicates that GridSolve request sequencing is not an appropriate technique for implementing fine-grained parallel applications, since the overhead of network communication and remote service invocation in GridSolve can easily offset the performance gain of parallel execution.

Experiments with montage

Montage is program for building highly detailed mosaics of astronomical images. It uses three steps to build a mosaic: Reprojection of input images this step reprojects input images to a common spatial scale and coordinate system. Modeling of background radiation in images this step rectifies the re-projected images to a common flux scale and background level. Coaddition this step co-adds reprojected, background-rectified images into a final mosaic.

Each step consists of a number of tasks that are performed by the corresponding Montage modules. There are dependencies both between adjacent steps and among tasks in each step. We present a series of experiments with a simple application of the Montage toolkit, introduced in the following subsection. Unlike Strassen's algorithm for matrix multiplication, this is essentially an image processing application and is more coarse-grained. The servers used in the experiments are Linux boxes with Dual Intel Pentium 4 EM64T 3.4 GHz processors and 2.0 GB memory. The client, the agent, and the servers are all connected via 100 Mb/s Ethernet.

A simple Montage application

We use the simple Montage application introduced in "Montage Tutorial: m101 Mosaic" [START_REF]Montage Tutorial: m101 Mosaic[END_REF], which is a step-by-step tutorial on how to use the Montage toolkit to create a mosaic of 10 2MASS [START_REF]The 2MASS Project[END_REF] Atlas images. This simple application generates both background-matched and uncorrected versions of the mosaic [START_REF]Montage Tutorial: m101 Mosaic[END_REF]. The step-bystep instruction in the tutorial can be easily converted to a simple workflow, which is illustrated by the left graph in Fig. 12. The rest of this section refers to this workflow as the naive workflow. The detailed description of each Montage module used in the application and the workflow can be found in the documentation section of [START_REF]The Montage Project[END_REF].

The output of the naive workflow, both the uncorrected and background-matched versions of the mosaic, are given in Figs. 10 and11, respectively. It can be seen that the background-matched version of the mosaic has a much better quality than the uncorrected version.

Parallelization of image reprojection

The execution time of the naive workflow on a single server is approximately 90 to 95 seconds, as shown below. The most time-consuming operation in the naive workflow is mProjExec, which is a batch operation that reprojects a set of images to a common spatial scale and coordinate system, by calling mProjectPP for each image internally. mProjectPP performs a plane-to-plane projection on the single input image, and outputs the result as another image. It is obvious that the calls to mProjectPP are serialized in mProjExec. Thus, an obvious way to improve the performance of the naive workflow is replacing the single mProjExec operation with a set of independent mProjectPP operations and parallelize the execution of

Results and analysis

Figure 13 shows the execution time (sorted) on a single server of the best 10 of 20 runs of both the naive and modified workflows. It can be seen that the performance of the modified workflow is significantly better than that of the naive workflow. The reason is that the single server has two processors as mentioned above and, therefore, can execute two mProjectPP operations simultaneously. This result demonstrates the benefit of parallelizing the time-consuming image re-projection operation by replacing the single mProjExec with a set of independent mProjectPP operations. It is still interesting to see whether using more than one server can further speed up the execution. This is investigated by the following experiment. The next experiment is based on a smaller workflow, which is the left branch of the modified workflow, i.e., the smaller branch that produces the uncorrected version of the mosaic. The reason for using a smaller workflow is that we want to minimize the influence of the fluctuating execution time of the right branch on the overall execution time. The expectation that using more than one server can further speed up the execution is demonstrated by Fig. 14. The figure shows the execution time (sorted) of the best 10 out of 20 runs of the left branch of the modified workflow on different numbers of servers (1, 2, and 3). It is not surprising to see in the figure that the performance is better as more servers are used to increase the degree of parallelization.

Related work

There is much research in the area of workflow management on grid resources; one taxonomy of relevant projects can be found in [START_REF] Yu | A taxonomy of scientific workflow systems for grid computing[END_REF]. Many of these projects have represented workflows explicitly; for example, explicit textual representations (e.g., Condor DAGMan [START_REF] Couvares | Workflow in Condor[END_REF], connected web services (e.g., Taverna [START_REF] Oinn | Taverna: lessons in creating a workflow environment for the life sciences: research articles[END_REF] GUI environment), and parameterized task graphs (e.g., communication patterns between task nodes [START_REF] Cosnard | Automatic task graph generation techniques[END_REF]). In our work, we have chosen to emphasize ease-of-use, and use automatic dependency analysis to implicitly construct the workflow from a sequence of service requests. This has led to certain difficulties in detecting the use of scalar variables, however, we believe that the ease of use cancels the difficulties.

SmartGridSolve [START_REF] Brady | Experiments with SmartGridSolve: achieving higher performance by improving the GridRPC model[END_REF] is a project that has very similar goals with respect to workflow processing in GridSolve. It is an extension to GridSolve that provides workflow processing for grid environments by enabling the collective mapping of a group of tasks to a fully connected network topology. SmartGridSOlve reduces communication volume by enabling direct data transfer between GridRPC servers, and it balances computation and communication loads among the servers. Language specific features (i.e., C macros) are used to do two passes over the service requests; during the first pass the structure of the workflow is determined; during the second pass the service requests are scheduled and executed . This two-pass approach makes it difficult to extend the SmartGridSolve interface to additional client interfaces such as Fortran, Matlab, and Octave, since those client languages may not provide the equivalent of C macros. Our implementation provides a smoother interface to additional GridSolve client bindings.

Conclusions and future work

GridSolve request sequencing is a technique developed for users to build workflow applications for efficient problem solving in GridSolve. GridSolve request sequencing completely eliminates unnecessary data transfer during the execution of tasks. In addition, it is capable of exploiting the potential parallelism among tasks in a workflow. The experiments discussed in the paper promisingly demonstrate the benefit of eliminating unnecessary data transfer taking advantage of the potential parallelism. An important feature of GridSolve request sequencing is that the analysis of dependencies among tasks in a workflow is fully automated; users are not required to manually specify the dependencies among tasks in a workflow. These features plus the easy-to-use API make GridSolve request sequencing a powerful tool for building workflow applications for efficient parallel problem solving in GridSolve.

The service trading component integrated on top of the GridSolve request sequencing infrastructure provides additional advantages to a user in terms of easeof-use and transparency. The combination of request sequencing and service trading provides fault tolerance at various levels of failure. If a single service fails, it is transparently retried by GridSolve; if all copies of a service have failed, the trader can formulate the complex request as different combination of services. The user need not be aware of the exact composition of services that satisfies the request.

In future work, the request sequencing scheduler will be improved to make more intelligent resource management decisions rather than using the simple level based scheduler. The service trader will be optimized to reduce the associated with generating DAGs from complex service requests.

A integrating theme in GridSolve research is ease-of-use and our goal in this work is to make GridSolve an easy-to-use yet powerful tool to enable an end user to write workflow programs. The user should not have to be knowledgeable in grid computing, mathematical libraries, algorithmic complexity, data dependency analysis, parallel asynchronous exaltation, fault-tolerance, or any of the details that are transparently handled by this system.

Fig. 1

 1 Fig. 1 The standard RPC-based computation model of GridSolve

3 :

 3 M = N = 0; CurrentSchedRank = 0;

  10,20,30;40,50,60;70,80,90] [output] = gs_call_service_trader("(a+(b*a))

Figure 8

 8 Figure 8 plots the execution time as a function of N (matrix size) of Strassen's algorithm on a single server, both with and without interserver data transfer. This figure demonstrates the advantage of eliminating unnecessary data traffic when a single

Fig. 10

 10 Fig. 10 The uncorrected version of the mosaic

Fig. 11 Fig. 12

 1112 Fig. 11 The backgroundmatched version of the mosaic

Fig. 13

 13 Fig.[START_REF]The NetSolve Project[END_REF] The execution time (sorted) on a single server of the best 10 of 20 runs of both the naive and modified workflows

  and CArgList denote the argument list of node C;

	17:	end if
	18:	end if
	19:	end for
	20:	end for
	21:	Assign the appropriate rank to node C;
	22:	end for
	23:

8:

for each argument PArg in PArgList do 9: for each argument CArg in CArgList do 10: if Parg and CArg have identical references then 11: if PArg.inout = (INOUT OR OUT) AND CArg.inout = (IN OR INOUT) then 12: Insert a RAW dependency RAW(P , C); 13: else if PArg.inout = IN AND CArg.inout = (INOUT OR OUT) then 14: Insert a WAR dependency WAR(P , C); 15: else if PArg.inout = (INOUT OR OUT) AND CArg.inout = OUT then 16:

Insert a WAW dependency WAW(P , C);

Table 1

 1 GridSolve request sequencing API

	Function prototypes
	gs_sequence_begin(int mode)
	gs_submit(char*, ...)
	gs_submit_arg_stack(char* service, arg_stack* args)
	gs_sequence_end(int)

Acknowledgements This research made use of Montage, funded by the National Aeronautics and Space Administration's Earth Science Technology Office, Computation Technologies Project, under Cooperative Agreement Number NCC5-626 between NASA and the California Institute of Technology. Montage is maintained by the NASA/IPAC Infrared Science Archive.