MSc Christine Arsac

Ckcile Raymond

PhD Nicole Martin-Moutot

PhD," Bknkdicte Dargent

MD Frangois Couraud

PhD Jean Pouget

MD,? Michael Seagar

Jean Roche

Immunoassays Fad to Detect Antibodies Against Neuronal Calcium Channels in zimyotrophc Lateral Sclerosis Serum

Recent studies suggested that autoantibodies that bind to voltage-dependent calcium channels and activate calcium entry may play a role in the progressive degeneration of motoneurons in sporadic amyotrophic lateral sclerosis. Immunoassays were performed to assess autoantibody titer in patients with amyotrophic lateral sclerosis or Lambert-Eaton myasthenic syndrome, a disease in which the presence of anti-calcium channel antibodies is well documented. Based on immunoprecipitation assays for antibodies against N-type calcium channels, only 8% ( 2 / 2 5 ) of amyotrophic lateral sclerosis patients had marginally positive titers, whereas 58% (18/31) of patients with Lambert-Eaton myasthenic syndrome had positive titers. Enzyme-linked immunosorbent assays with purified neuronal N-type calcium channels revealed immunoreactivity in 2 of 25 amyotrophic lateral sclerosis sera and 12 of 31 Lambert-Eaton myasthenic syndrome sera, which is not compatible with suggestions that enzyme-linked immunosorbent assay is a more sensitive technique for the detection of autoantibodies in amyotrophic lateral sclerosis. Furthermore, based on immunoprecipitation assays, amyotrophic lateral sclerosis sera were totally negative for antibodies against L-type calcium channels from skeletal muscle or brain. These data do not support the hypothesis that an autoimmune response against calcium channels plays a primary role in amyotrophic lateral sclerosis.

A series of reports by Appel and colleagues (reviewed in [START_REF] Appel | Auroimmunity as an etiological factor in sporadic amyorrophic lateral sclerosis[END_REF] ) provides evidence that autoantibodies that activate voltage-gated calcium channels may be involved in initiating neurotoxicity. Immunoglobulins from ALS patients increase spontaneous quantal acetylcholine release from mouse motor neuron terminals, suggesting that calcium influx through the voltage-dependent calcium channels coupled to exocytosis may be enhanced [START_REF] Od | Immunoglobulins from amyotrophic lateral sclerosis patients enh.ince spunraneous transmitter release from motor nerve tcrminds[END_REF]. At least five distinct classes of calcium channels are expressed in neurons [START_REF] Biriibaunier | The naming of calciuni channels[END_REF]. P/Q-Type channels are thought to play a major role in controlling transmission at the mammalian neuromuscular junction IS], although N-type channels may also be involved [START_REF] Rossoni | w-Conotoxin GVIA binds to and blocks rat nruromuscular junction[END_REF]. Voltage clamp recording has shown that ALS IgG can increase channel activity in cerebellar Purkinje neurons where P-type currents predominate [START_REF] Llinas | et ' 1 1 . IgG from aniyotrciphic lateral sclerosis patients increases currcnt through 1' type calcium channels in mammalian cerebellar Purkinje cells and in isolared channel protein in lipid hilayer[END_REF], in Xenopus oocytes heterologously expressing Ntype currents [S], and in a hybrid motor neuron cell line [START_REF] Mosier | Aniyorrophic lxeral sclerosis immunoglobulins increase Ca'+ currents in a moroneuron cell line[END_REF]. Results of further experiments in the motor neuron cell line were consistent with the hypothesis that antibody-mediated channel activation triggers neurotoxicity. Incubation with ALS IgG reduced cell survival and an evaluation of the protective effects of selective channel antagonists indicated that Nand P/Qtype, but not L-type channels, mediated toxicity [ 101.

Immunoassay of an anti-calcium channel specificity in ALS sera would provide crucial support for antibody-mediated channel activation. Appel and colleagues [ l l ] reported that 75% of patients with sporadic ALS produce antibodies that react with L-type calcium channels purified from rabbit skeletal muscle in enzyme-linked immunosorbent assays (ELISAs). However the observations outlined in the preceding paragraph predict that autoantibodies also react with N-or P/Q-type calcium channels. Calcium channels solubilized from neuronal membrane preparations can be specifically labeled with radioactive antagonists. Assays based on the capture of channel-radioligand complexes have been used to quantify autoantibodies in Lambert-Eaton myasthenic syndrome (LEMS) [ 12-171, a disease in which a primary role for anti-calcium channel autoantibodies is more clearly established (reviewed in [START_REF] Vincent | Auroimrriuniry to the voltage-gated calcium channels underlies the Lamberr-Earon myasthenic syndrome, a paraneoplastic disorder[END_REF]).

In this report we describe the use of immunoprecipitation assays and ELISA with purified N-type calcium channels from rat brain [ 131 to detect anti-neuronal calcium channel antibodies. Although both methods revealed autoantibodies in LEMS sera, immunoreactivity was not consistently detected in sera from patients with ALS.

Materials and Methods

Patients

Twenty-five patients had a diagnosis of probable or definite ALS as outlined by the El Escorial World Federation of Neurology crireria for the diagnosis of ALS [20]. The 31 patients given a diagnosis of LEMS included 15 patients with no detected neoplasm, 15 patients with small-cell lung carcinoma, and 1 patient with epidernioid carcinoma.

Im munoprecipitation Assajis

w Conoroxin GVIA (wGVIA) was purchased from the Peptidc Institute and sodium''' iodide (Na'"1) (2,200 Ci/mrnol) from New England Nuclear. WGVIA was radio-iodinated by the lactoperoxidase method, and mono[ "iI]-iodo COGVIA was purified by reverse-phase high-performance liquid chromatography (HPLC) on an analytical C18 column. A crude synaptosome (P2) fraction from rat brain (0.3 nig of protein/ ml) was incubated with 0.2 nM ['"I]-wGVIA in 25 mM Tris and 0.15 M sodium chloride (NaCI), adjusted to pH 7.4 with hydrochloric acid (HCI) (buffer A), overnight at 4°C. Membranes were pelleted and then resuspended and solubilized in buffer A containing 1.5% (wtlwt) Triton X-100. Insoluble material was removed by ultracentrifugation. Aliquots of the supernatant containing 6 to 8 fniol of ['''I]-ctK;VIA-labeled N-type calcium channels were incubated with 5 1. 11 of serum for 4 hours at 4°C in a final volume of 0.1 ml, completed with 20 mM sodium phosphate buffer and 0.1% Triton X-100. pH 7.4 (buffer B). One-tenth of a milliliter of protein A-cross-linked agarose beads (Sepharose Fast Flow) equilibrated in buffer B was added, followed by rotary mixing for 1 hour at 4°C. The beads were then recovered by centrifugation. washed by resuspension in 1 ml of buffer A containing 0.1Yo Triron X-100, and immune complexes were measured by gatnnia counting.

[ 'H]Isradipine (PN200-110) (70-85 Ci/nimoI) from Aniersham was used to label L-type calcium channels in rat brain synaptosomal membranes or skeletal muscle microsonies. Solubilization, partial purification on wheat germ agglutinin (WGA)-cross-linked 4% agarose beads (Sepharose 4BCL) and imniunoprecipitation assays were performed as previously described [ 161.

Enzyme-Lin ked Im m u nosorben t Assq

N-type calcium channels were purified from 3-([3-cholamidopropyl] diniethylammonio)-1 -propanesulfonate (CHAPS) extracts of rat brain synaptosomes by sequential chroniatography on chelating Sepharose Fast Flow (Sigma) and heparin-cross-linked 4% agarosc beads (Ultrogel) (Sepracor) according to the method of Leveque and colleagues [START_REF] Lcveque | Purification of the N-type c&iurn chmnel associated with synr;Luin and synqxotagmin[END_REF]. Purified proteins were dialyzed against 0.1 M sodium bicarbonate, pH 9.5, and then adsorbed onto inicrotitration plates (Costar) by adding 0.1 ml containing 0.3 pg of protein per well and incubating overnight a t 4°C. Plates were washed with buffer A, blocked with 5% low-6at-milk powder and 0.05% Tween 20 in buffer A for 2 hours at 3 7 °C and then incubated wirh sera diluted tenfold in the blocking buffer, for 2 hours at 37°C. Plates were washed four rimes with 0.05% Tween 20 in buffer A, incubated with anti-human polyvalent immunoglobulins-alkaline phosphatase conjugate (Sigma) diluted 4,500-fold for 1 hour at 37"C, and again washed four times with 0.0j'Yo Tween 20 in buffer A. The optical densiry a t 405 nm was measured 1 hour after the addition of 0.5 mg/ml of p-nitrophenyl phosphate in 10 mM diethanolatnine containing 0.5 niM magnesium chloride.

Results

A membrane preparation containing rat brain nerve terminals was incubated with 0.2 nM '"I-coGVIA, a specific ligand for N-type calcium channels, and ligand-receptor complexes were extracted with Triton X-100. Sera were incubated with Triton X-100 extracts containing the prelabeled N-type channels, and imm u n e complexes were trapped o n protein A-Sepharose beads. G a m m a counting provides a measurement of the recovery of calcium channels and thus of anti-Ntype calcium channel autoantibody titer. Autoantibodies were not consistently detecred by this method in sera from a group of ALS patients (Fig 1). O n l y 2 ALS patients (8%) from a group of 25 displayed titers marginally above (260 and 190 pniol) the limir of the normal range (160 pmol) defined as the mean titer + 3 standard deviations [SDs] of a group of 14 normal subjects. I n contrast, sera from 18 LEMS patients (58%) from a group of 31 gave a positive response.

In view of reports that ALS IgG reacts with L-type calcium channels from skeletal muscle [ 1 I], immunoprecipitation assays were also performed using ['HI PN200-I 10, a radioligand that binds specifically to L-type calcium channels. [ 'H]PN200-110-receptor complexes were solubilized in digitonin from either rat brain nerve terminals or skeletal muscle niicrosomes, a n d incubated with sera, and immune complexes were detected by methods similar to those for the N-type channel immunoprecipitation assay described already.

No inimunoreactivity against either neuronal or skeletal muscle 1,-type calcium channels was detected in ALS sera (Table 1). W e previously reported that this technique detects autoantibodies against neuronal a n d muscle L-type channels from some LEMS sera [START_REF] El Far 0. Marqueze | Antigens associared with N and L type calcium channels Lambert-Earon myasthenic syndrome[END_REF].

However, only sera from a small group of patients displaying exceptionally high titers of antibodies against N-type channels reacted with L-type channels. Two of these samples were included in the series of assays shown in Table 1 as positive controls.

O u r inimunoprecipitation procedure is potentially limited by the fact that certain human immunoglobulin classes do not bind to protein A, which could account for our failure to demonstrate significant levels of reactivity against either N-type or L-type calcium channels in sera from ALS patients. Assays for antibodies against both Nand L-type channels were therefore repeated using polyvalent anti-human IgG, A, and M antibodies bound to protein A-Sepharose beads to capture immune complexes. This method also failed to reveal anti-calcium channel antibodies with ALS sera, but with LEMS sera gave similar results to those obtained when secondary antibodies were omitted (not shown).

It has been proposed that ELISA may be a more sensitive technique than immunoprecipitation for the detection of autoantibodies in ALS sera [START_REF] Appel | Auroimmunity as an etiological factor in sporadic amyorrophic lateral sclerosis[END_REF] . Consequently ELISA was carried out using N-type channels, purified from rat brain by a method that we recently reported [ 191, as an antigen. Purified proteins were dialyzed to reduce detergent concentration and then adsorbed to the wells of microtitration plates. Following blocking and incubation with tenfold diluted sera, immune complexes were detected using an anti-human immunoglobulin-alkaline phosphatase conjugate. Sera from 2 ALS patients (8%) gave responses slightly above (0.28 and 0.26) the limit of the normal range (0.24), whereas sera from 12 LEMS patients (39%) were immunoreactive (Fig 2). Therefore, ELISA did not reveal a higher percentage of positive ALS sera than did the inimunoprecipitation assay. Furthermore, a smaller number of LEMS sera were positive, suggesting that ELISA is a less sensitive technique than immunoprecip- 1,700 "Serum titers above the mean titer + 3 standard deviations (SDs) for the normal subjects were scored as positive.

hSerurn from 2 Larnbert-Eaton rnyasthenic syndrome patients previously reported to react with L-type calcium channels [151 were included as positive controls.

0.9 [START_REF] Takahashi | Subunit structure of dihydropyridine-sensitive calcium channels from muscle[END_REF] or Lambert-Eaton myasthenic syndrome (LEMS) (31) orfiom healthy subjects [START_REF] Lang | Autoantibody specificities in Lambert-Eaton myasthenic syndrome[END_REF], and washing, immune complexes were detected with anti-human immunoglobulin antibodies conjugated to alkaline phosphatase. The optical density at 405 nm was measured 1 hour after the addition of 0.5 mglml of p-nitrophenyl phosphate.

" O 1 ALS NORMAL LEMS SUBJECTS

Fig 2. Enzyme-linked immunosorbent assay for anti-N-type calcium channel antibodies. N-type calcium channels were purified fiom rat brain membranes and adsorbed to microtitration plates (0.3 pg/weLl). Ajer incubation for 2 hours at 3 7 C with tenfold-diluted serum fiom patients with amyotrophic lateral sclerosis (ALS)

itation for the detection of autoantibodies against neuronal calcium channels.

Discussion

Reports from Appel and colleagues provided persuasive evidence that autoantibody-mediated activation of voltage-gated calcium channels may underly the degeneration of motor neurons in ALS. Immunoglobulins from ALS patients were shown to enhance acetylcholine release at the neuromuscular junction [START_REF] Od | Immunoglobulins from amyotrophic lateral sclerosis patients enh.ince spunraneous transmitter release from motor nerve tcrminds[END_REF] and increase voltage-dependent calcium currents in cerebellar neurons [START_REF] Llinas | et ' 1 1 . IgG from aniyotrciphic lateral sclerosis patients increases currcnt through 1' type calcium channels in mammalian cerebellar Purkinje cells and in isolared channel protein in lipid hilayer[END_REF], oocytes injected with rat brain messenger RNA [START_REF] Mosier | Amyotrophic laterdl sclerosis IgG enhances brain calcium currents expressed in >;enopus oocytes[END_REF], and a motor neuron cell line [START_REF] Mosier | Aniyorrophic lxeral sclerosis immunoglobulins increase Ca'+ currents in a moroneuron cell line[END_REF]. Surprisingly effects were not restricted to neurons, as ALS IgG inhibited calcium currents in skeletal muscle by shifting the activation curve to more positive potentials and stabilizing the closed state [21]. However, ELISA findings were consistent with functional effects and ELISA detected antibodies that bind to purified L-type calcium channels from skeletal muscle in 75% of patients with sporadic ALS [l 11.

More recent data from the Appel group show that ALS IgG mediated cytotoxicity in a hybrid motor neuron line which was prevented by either co conotoxin GVIA or o agatoxin IVA, selective antagonists of neuronal Nand P-type calcium channels, respectively [lo]. Although no protection was afforded by L-type channel antagonists, neurotoxicity was reduced when ALS IgG was preincubated with purified L-type calcium channels from muscle, presumably due to the removal of a specific antibody population [ 101.

These observations suggest that cytotoxicity is initiated by ALS antibodies interacting directly with neuronal N -and P-type calcium channels, and also imply that these antibodies can cross-react with multiple types of calcium channel. However, direct evidence for binding of ALS IgG to neuronal calcium channels is sparse, although appropriate methods are available and anti-calcium channel autoantibodies in LEMS have been well documented by immunoassay in multiple independent studies [12-18, 22, 231. We therefore performed assays using both immunoprecipitation and ELISA to compare anti-calcium channel reactivity of sera from patients with ALS or LEMS and from normal subjects.

The results obtained in assays for anti-N-type calcium channels are summarized in Table 2. Only 8% (2125) of ALS patients had titers marginally above the upper limit of those in the normal subjects, whereas the assay method did reveal antibodies in the sera of 58% (18/31) of LEMS patients. It has been suggested that ELISA may be a more sensitive method than im- W e recently reported that immunoprecipitation of solubilized ['H]I'N200-110-labeled receptors can be used to assay autoantibodies that bind to L-type calcium channels [START_REF] El Far 0. Marqueze | Antigens associared with N and L type calcium channels Lambert-Earon myasthenic syndrome[END_REF]. LEMS sera that are positive in this assay react with neuronal, cardiac, and skeletal muscle L-type calcium channels and with neuronal N-type channels [START_REF] El Far 0. Marqueze | Antigens associared with N and L type calcium channels Lambert-Earon myasthenic syndrome[END_REF], a lack of specificity similar to that observed by Appel's group in ALS sera. Consequently, ALS sera were screened for immunoprecipitation of neuronal or skeletal muscle L-type calcium channels, but no reactivity was detected in either assay.

W e did not perform systematic immunoprecipitation assays using '"I-o conotoxin MVIIC wMVIIC), which binds to P/Q-type calcium channels and provides a sensitive test for autoantibodies in LEMS sera 117, 23). However, preliminary experiments with a restricted group of ALS patients did not reveal reactive sera (not shown). A recent report showed that 22% of ALS sera were positive in this assay (231, but this was not confirmed in another study in which only 1 of 27 ALS sera gave a weakly positive response [START_REF] Ilrachniari | Amyotrophic lateral sclerosis: an autoimniunc disease?[END_REF] (B. Lang, personal communication, 1996).

In conclusion, our results are not consistent with significant levels of autoantibodies directed against calcium channels in the sera of patients with sporadic and it is therefore unlikely that the discrepancy between our findings and those of Appel and colleagues is due to our patients constituting a distinct group. Appel and colleagues reported antibodies against muscle L-type calcium channels in 75% of patients and hypothesized that these antibodies directly trigger cell toxicity by binding to neuronal N-type calcium channels [START_REF] Mosier | Amyotrophic laterdl sclerosis IgG enhances brain calcium currents expressed in >;enopus oocytes[END_REF][START_REF] Smith | Cytotoxicity of immunoglobulins from amyotrophic lateral sclerosis patients on a hybrid motoneuron cell line[END_REF]111. W e cannot rule out the possibility that ALS sera contain low-affinity autoantibodies against muscle L-type calcium channels that may only be assayed by ELISA. However, we did not detect immunoreactivity with N-type calcium channels using both immunoprecipitation assay and ELISA, indicating that if ALS sera do contain anti-muscle calcium channel autoantibodies, these antibodies do not cross-react with neuronal channels. Consequently, our data do not support the hypothesis that antibodies that bind to and activate neuronal calcium channels initiate events resulting in motor neuron degeneration in ALS.

~~~ ~ ~~

Financial support was provided from the Association Frdngaisr conire les Myoparhies and the Programme Hospitalier de Recherche Clinique.

  From * I N S E M U374, Institut Jean Roche, Facultk de Mkdecine Secteur Nord, and ?Service de Neurologie et Maladies Neuromusculaires, Centre Hospiralo-Universitaire de la Timone, Marseille, France.

Fig 1 .

 1 Fig 1. Inimunoprecipitation assay f o r anti-N-type calcium channel autoantibodies. N-typt calcium channels in rat brain membranes were labeled ruitb E I-wGVIA and extracted with Triton X-100. Extracts containing 6 to 8 f i o l of lrtbeled Ntype crrlcium channel were incubated with 5 p l of serum )om patients with amyotrophic lateral sclerosis (ALS) (25) or Lambert-Euton iryasthic syndrome (LEMS) (31) or fronz bealthy subjects (14) for 4 hours at 4°C. The amount of radioartiuity recovered in immune complexes iuas counted and antibody titer was expressed in picomoles of crrlciirm channel immunoprecipitated per liter of serum.

  ALS. Diagnosis was established according to the ElEscorial World Federation of Neurology criteria [20],

Table 1 .

 1 Immunoprec+itation Assay f i r Anti-L-Type Calcium Channel Automtibodies

		Amyot rop hic		Lambert-Eaton
		Lateral Sclerosis	Normal Subjects	Myasthenic Syndrome
	Brain [311]PN200-1 10 receptors
	No. of patients	14	11	l h
	No. of positive samplesa	0	0	1
	Mean titer (pniol/liter of serum -t SD)	84 f 29	131 2 40	684
	Muscle [ 'Hll'N200-1 10 receptors
	No. of patients	24	18	lh
	No. of positive samples"	0	0	1
	Mean titer (pmollliter of serum 2 SD)	125 f 30	151 2 22

Table 2 .

 2 Detection of Anti-N-Type Calcium Channel Autoantibodiesa 32%) of 31 LEMS sera reacted with Ntype channels both in solution and in solid phase, none of the ALS sera were positive in both assays.

	Amyotrophic		Lamberr-Eaton
	Lateral Sclerosis	Normal Subjects	Myasthenic Syndrome

'Dam are numbers of serum samples, with percenrages in paientheses.


Tiago Carneiro
email: tiago.carneiro-pessoa@inria.fr

Nouredine Melab
email: nouredine.melab@univ-lille.fr

Productivity-aware Design and Implementation of Distributed Tree-based Search Algorithms

Keywords: Tree search algorithms, High productivity, PGAS, Chapel, MPI+OpenMP

Parallel tree search algorithms offer viable solutions to problems in different areas, such as operations research, machine learning and artificial intelligence. This class of algorithms is highly computeintensive, irregular and usually relies on context-specific data structures and hand-made code optimizations. Therefore, C and C++ are the languages often employed, due to their low-level features and performance. In this work, we investigate the use of Chapel high-productivity language for the design and implementation of distributed tree search algorithms for solving combinatorial problems. The experimental results show that Chapel is a suitable language for this purpose, both in terms of performance and productivity. Despite the use of high-level features, the distributed tree search in Chapel is on average 16% slower and reaches up to 85% of the scalability observed for its MPI+OpenMP counterpart.

Introduction

Tree-based search algorithms are strategies that implicitly enumerate a solution space, dynamically building a tree. This class of algorithms is often used for the exact resolution of permutation combinatorial optimization problems (COP) and offers viable solutions to problems in different areas, such as operations research, artificial intelligence, bioinformatics and machine learning [START_REF] Grama | A survey of parallel search algorithms for discrete optimization problems[END_REF][START_REF] Zhang | Branch-and-bound search algorithms and their computational complexity[END_REF]. As the decision version of permutation COPs are usually NP-Complete, the size of problems that can be solved to optimality is limited, even if large-scale distributed computing is used [START_REF] Crainic | Parallel branch-and-bound algorithms[END_REF][START_REF] Mezmaz | A grid-enabled branch and bound algorithm for solving challenging combinatorial optimization problems[END_REF]. In this sense, it is expected that exascale computers are willing to allow a significant decrease in the execution time required to solve COP instances to optimality. However, such large scale systems are going to be complex to program, and efforts towards programmability are crucial for better exploiting this future generation of computers [START_REF] Asanovic | The landscape of parallel computing research: A view from berkeley[END_REF][START_REF] Fiore | On the road to exascale: Advances in high performance computing and simulationsan overview and editorial[END_REF].

Tree-based search algorithms are compute-intensive and highly irregular, which demands hand-optimized data structures for efficient search and load balancing [START_REF] Carneiro Pessoa | GPU-accelerated backtracking using CUDA dynamic parallelism[END_REF][START_REF] Gmys | Ivm-based parallel branch-andbound using hierarchical work stealing on multi-gpu systems[END_REF][START_REF] San Segundo | Recent developments in bitparallel algorithms[END_REF]. Thus, high-productivity languages are not often employed within the scope of tree search, as they historically suffer from severe performance penalties [START_REF] Da Costa | Exascale machines require new programming paradigms and runtimes[END_REF]. Instead, this kind of application is frequently written in either C or C++, due to low-level features present in both languages [START_REF] Carneiro | Um levantamento na literatura sobre a resolução de problemas de otimização combinatória através do uso de aceleradores gráficos[END_REF][START_REF] Crainic | Parallel branch-and-bound algorithms[END_REF].

Chapel is a productivity-aware programming language for high-performance computing that is competitive to both C-OpenMP and C-MPI+OpenMP in terms of performance, considering different benchmarks [START_REF] Chamberlain | Chapel comes of age: Making scalable programming productive[END_REF]. The objective of the present research is to investigate Chapel's features to design and implement distributed tree search algorithms for solving permutation combinatorial problems. To the best of our knowledge, the present research is the first one that investigates the use of a high-productivity language for this purpose.

The experimental results show that Chapel is a suitable language for the design and implementation of distributed tree search algorithms, both in terms of performance and productivity. It is possible to conceive a distributed tree search algorithm starting from its multicore counterpart by adding few modifications. The distributed algorithm performs load balancing among different computer nodes and also uses all CPU cores that a computer node has. Despite the high level of its features, the distributed tree search in Chapel is on average 16% slower and reaches up to 85% of the scalability achieved by its C-MPI+OpenMP counterpart. Finally, the distributed load balancing strategies provided are effective: the dynamic load balancing version is up to 1.5× faster than its static counterpart.

The remainder of this paper is structured as follows. Section 2 brings background information and related works. The distributed tree-based search in Chapel is detailed in Section 3. Section 4 presents a performance evaluation. Then, Section 5 brings a discussion in terms of performance, programmability, and limitations of Chapel for programming distributed tree search algorithms. Finally, conclusions are outlined in Section 6.

Background and Related Works

The Chapel Programming Language

Chapel is an open-source parallel programming language designed to improve the programmability for high-performance computing. It incorporates features from compiled languages such as C, C++, and Fortran, as well as high-level elements related to Python and Matlab. The parallelism is expressed in terms of lightweight tasks, which can run on several locales or a single one. In this work, the term locale refers to a symmetric multiprocessing computer in a parallel system [START_REF]Chapel language specification v[END_REF].

In Chapel, both global view of control flow and global view of data structures are present [START_REF] Chamberlain | Chapel comes of age: Making scalable programming productive[END_REF]. Concerning the first one, the program is started with a single task and parallelism is added through data or task parallel features. Moreover, a task can refer to any variable lexically visible, whether this variable is placed in the same locale on which task is running, or in the memory of another one. Concerning the second one, indexes of data structures are globally expressed, even in case the implementation of such data structures distributes them across several locales. Thus, Chapel is a language that realizes the Partitioned Global Address Space (PGAS) programming model [START_REF] Almasi | Pgas (partitioned global address space) languages[END_REF].

Finally, indexes of data structures are mapped to different locales using distributions. Contrasting to other PGAS-based languages, such as UPC and Fortran, Chapel also supports user-defined distributions [START_REF] Chamberlain | User-defined parallel zippered iterators in chapel[END_REF].

Tree-based Search Algorithms

Tree-based search algorithms are strategies that implicitly enumerate a solution space, dynamically building a tree [START_REF] Grama | A survey of parallel search algorithms for discrete optimization problems[END_REF]. The internal nodes of the tree are incomplete solutions, whereas the leaves are solutions. Algorithms that belong to this class start with an initial node, which represents the root of the tree, i.e., the initial state of the problem to be solved. Nodes are branched during the search process, which generates children nodes more restricted than their parent node. Generated nodes are evaluated, and then, the valid and feasible ones are stored in a data structure called Active Set.

At each iteration, a node is removed from the active set according to the employed search strategy [START_REF] Zhang | Branch-and-bound search algorithms and their computational complexity[END_REF]. The search generates and evaluates nodes until the data structure is empty or another termination criterion is reached. If an undesirable state is reached, the algorithm discards this node and then chooses an unexplored (frontier) node in the active set. This action prunes some regions of the solution space, keeping the algorithm from unnecessary computation. The degree of parallelism of tree-based search algorithms is potentially very high, as the solution space can be partitioned into a large number of disjoint portions, which can be explored in parallel.

As these algorithms are compute-intensive, diverse strategies have been used for improving performance, such as instruction-level parallelism, architecturespecific code optimizations and problem-specific data structures [START_REF] Carneiro Pessoa | GPU-accelerated backtracking using CUDA dynamic parallelism[END_REF][START_REF] Feinbube | Nqueens on cuda: Optimization issues[END_REF][START_REF] Gmys | Ivm-based parallel branch-andbound using hierarchical work stealing on multi-gpu systems[END_REF][START_REF] San Segundo | Recent developments in bitparallel algorithms[END_REF]. Thus, parallel tree-based search algorithms are frequently written in C/C++, due to their low-level features and supported parallel computing libraries [START_REF] Carneiro | Um levantamento na literatura sobre a resolução de problemas de otimização combinatória através do uso de aceleradores gráficos[END_REF]. In the context of distributed algorithms, the same performance-aware strategies are combined with distributed programming libraries for implementing load balancing and explicit communication between processing nodes [START_REF] Crainic | Parallel branch-and-bound algorithms[END_REF][START_REF] Mezmaz | A grid-enabled branch and bound algorithm for solving challenging combinatorial optimization problems[END_REF][START_REF] Tschoke | Solving the traveling salesman problem with a distributed branch-and-bound algorithm on a 1024 processor network[END_REF]. As a consequence, programming distributed tree search algorithms can be challenging and time-consuming.

Distributed Tree-based Search Algorithms in Chapel

A major objective of Chapel concerning productivity is allowing distributed programming using concepts close to the ones of shared-memory programming [START_REF] Chamberlain | Chapel comes of age: Making scalable programming productive[END_REF]. In this section, a multicore single-locale tree-search algorithm is initially proposed. Then, it is extended using Chapel's productivity-aware features for distributed programming.

Algorithm Overview

This work focuses on permutation combinatorial problems, for which an N -sized permutation represents a valid and complete solution. Permutation combinatorial problems are used to model diverse real-world situations, and their decision versions are often NP-Complete [START_REF] Mezmaz | A grid-enabled branch and bound algorithm for solving challenging combinatorial optimization problems[END_REF][START_REF] Zhang | Branch-and-bound search algorithms and their computational complexity[END_REF].

This section presents two backtracking algorithms for enumerating all complete and feasible solutions of the N-Queens problem. Backtracking is a fundamental problem-solving paradigm that consists in dynamically enumerating a solution space in a depth-first fashion. Due to its low memory requirements and its ability to quickly find new solutions, depth-first search (DFS) is often preferred [START_REF] Zhang | Branch-and-bound search algorithms and their computational complexity[END_REF].

The N-Queens problem consists in placing N non-attacking queens on a N ×N chessboard, and it is often used as a benchmark for novel tree-based search algorithms [START_REF] Bell | A survey of known results and research areas for n-queens[END_REF][START_REF] Feinbube | Nqueens on cuda: Optimization issues[END_REF]. The N-Queens is easily modeled as a permutation problem: position r of a permutation of size N designates the column in which a queen is placed in row r. Furthermore, the concepts herein presented are similar to any permutation combinatorial problem and can be adapted for solving other problems of this class with straightforward modifications [START_REF] Carneiro Pessoa | GPU-accelerated backtracking using CUDA dynamic parallelism[END_REF][START_REF] Gmys | Ivm-based parallel branch-andbound using hierarchical work stealing on multi-gpu systems[END_REF].

The Single-Locale Multicore Implementation

Algorithm 1 presents a pseudocode for the single-locale backtracking in Chapel. The algorithm starts receiving the problem to be solved (line 1 ) and the cutoff depth (line 2 ). Then, it is required to generate an initial load for the parallel search. For this purpose, task 0 performs backtracking from depth 1 (initial problem configuration) until the cutoff depth cutof f , storing all feasible, valid, and incomplete solutions at depth cutof f in the active set A (line 4 ). After generating the initial load, the parallel search strategy begins through a forall statement (line 5 ). As one can see in Fig. 1, nodes in the centralized active set A are assigned to tasks in chunks. Each task has its active set and executes a backtracking search strategy. In turn, nodes are used to initialize the backtracking, which enumerates the solution space rooted by a node. The load balancing is done through the iterator (DynamicIters) used to assign indexes of A to tasks, like in OpenMP. Metrics are reduced through Reduce Intents. In Chapel, it is possible to use the Tuple data type (equivalent to C-structs) and reduce all metrics at once (line 6 ). Differently from OpenMP, it is not required to define a tuple reduction. Finally, the parallel search finishes when the active set A is empty.

The Multi-locale Distributed Implementation

One can see in Algorithm 2 a pseudocode for the distributed tree-based search algorithm in Chapel. Thanks to Chapel's global view of control flow, the search also starts serially, with task 0 generating the initial load to populate the active set A (line 4 ). To make it possible to distribute A, it is required to define a domain (line 5 ) and define how this domain it is going to be distributed across different locales (line 6 ) [START_REF] Chamberlain | User-defined parallel zippered iterators in chapel[END_REF]. In this work, only standard distributions are used 3 . Finally, the distributed active set A d of type Node is defined over the domain D (line 8 ).

After the initial load generation, the nodes of A are distributed across several locales by using a parallel forall (line 9 ), which generates the distributed active set A d . Thanks to Chapel's global view of A d , the indexes of both active sets are directly accessed in line 9. The compiler is responsible for the communication code. Moreover, as shown in Fig. 2,A d is an abstraction. The distributed active set A d consists of several sets A i d , i ∈ {0, ..., l -1}, where l is the number of locales on which the application is going to run.

The parallel search takes place in line 12. As one can see in Algorithm 2, its forall is similar to the one of Algorithm 1. However, distributed iterators are used instead (DistributedIters). Additionally, the distributed search exploits two levels of parallelism, and the compiler is also responsible for generating the code that exploits all CPU cores a locale has. Finally, the metrics are reduced in the same way as in the single-locale algorithm.

Algorithm 2: The multilocale tree-based search algorithm.

1 I ← get problem() 2 cutof f ← get cpu cutof f depth() 3 A ← ∅ 4 A ← generate initial active set(cutof f, I) 5 Range ← 0..(|A| -1) 6 D ← Range mapped according to a standard distribution 7 A d ← ∅ 8 A d ← [D] : N ode 9 forall s in Range do 10 A d [s] ← A[s] 11 end
12 forall node in A d following the iterator with(+ reduce metrics) do 13 metrics+ = tree search(node, cutof f, I) 14 end

Search Procedure and Data Structures

The kernel of both parallel algorithms previously presented is based on a serial and hand optimized backtracking for solving permutation combinatorial problems, originally written in C [START_REF] Carneiro Pessoa | GPU-accelerated backtracking using CUDA dynamic parallelism[END_REF]. The serial backtracking was then adapted to Chapel, obeying the handmade optimizations, instruction-level parallelism, data structures, and C-types. The data structure Node is similar to any permutation combinatorial problem. It contains an unsigned 8-bit integer vector of size cutof f , identified by board, and an unsigned integer variable. The vector board stores the feasible and valid incomplete solution. In turn, the integer variable, identified by bitset, keeps track of board lines by setting its bit n to 1 each time a queen is placed in the n-th line.

The search performed by the kernel is a non-recursive backtracking that does not use dynamic data structures, such as stacks. Initially depth receives the value of cutof f . Next, board and bitset are initialized with Node[i].board and Node[i].bitset, respectively. The semantics of a stack is obtained by trying to increment the value of the vector board at position depth. If this increment results in a feasible and valid incomplete solution, the depth variable is then incremented, and the search proceeds to the next depth. After trying all configurations for a given depth, the search backtracks to the previous one.

The objective of this section is to show that it is possible to use a high-productivity language for programming distributed tree-based search algorithms and achieve metrics similar to MPI+X.

Protocol

The following programs were conceived for enumerating all valid and complete configurations of the N-Queens problem.

-Chapel: implementation of the multi-locale backtracking search algorithm described in Algorithm 2, written in Chapel.

-MPI+X: single program -multiple data (SPMD) counterpart written in C of the program above introduced. This program uses MPI for communication and X means the use of OpenMP for exploiting all cores/threads a locale has.

Both implementations use the data structures and search procedure detailed in Section 3.4. In this section, it is investigated how the application scales according to the number of locales. Furthermore, the influence of the PGAS data structure distribution on the application execution time is also studied. Tree search algorithms for solving combinatorial problems are usually highly irregular applications. Therefore, the influence of the distributed load balancing strategies on the overall performance of the application is also investigated. Finally, all metrics collected for the implementation in Chapel are compared to the ones achieved by its MPI+X counterpart.

Parameters Settings

Problems of size (N ) ranging from 15 to 20 are considered. The experiments take from few seconds to several hours of parallel processing. The number of locales ranges from 1 to 32, and the application is the same for either one or more than one computer node(s). The number of locales is passed to the application using Chapel's built-in command line parameter -nl l (-np l for MPI), where l is the number of locales on which the application is executed.

All computer nodes are symmetric and operate under Debian 4.9.130 -2, 64 bits. They are equipped with two Intel Xeon X5670 @ 2.93 GHz (a total of 12 cores/24 threads), and 96 GB RAM. Thus, up to 384 cores/768 threads are used in the experiments. All locales are interconnected through an Infiniband network: Mellanox Technologies MT26428 (ConnectX VPI PCIe 2.0 5GT/s -IB QDR / 10GigE).

Concerning the MPI+X implementation, OpenRTE 2.0.2 along with gcc 6.3.0 and OpenMP 4.5 were used for compilation and execution. The Chapel implementation was programmed in its current version (1.18), and the default task layer (qthreads) is the one employed. Chapel's multi-locale code runs on top of GASNet, and several environment variables should be set with the characteristics of the system the multi-locale code is supposed to run. One can see in Table 1 a summarization of the runtime configurations for multi-locale execution. The Infiniband GASNet implementation is the one used for communication (CHPL COMM SUBSTRATE) along with MPI, which is responsible for getting the executables running on different locales (GASNET IBV SPAWNER).

Chapel provides several standard distributions to map data structures onto locales. Different tests were also carried out to identify the best option in the context of this work. The one chosen was the one-dimension BlockDist, which horizontally maps elements across locales. For instance, in case l = 3 and |A d | = 8, elements 0, ..., 2 are on locale l 0 , 3, .., 5 on locale l 1 , and 6, 7 on locale l 2 . In the scope of the present research, choosing a different standard distribution does not lead to performance improvements.

Experiments were carried out to choose a suitable cutoff depth. This parameter directly influences the size of A d , and therefore the time spent in distributing the active set across locales. As observed in Fig. 3, the fastest data structure distribution is observed for cutof f = 3. However, such a cutoff value limits parallelism, resulting in a slow distributed search. In contrast, when the cutoff is set to 6, the distribution of A d becomes 10× slower than the search procedure itself. This behavior happens due to the combinatorial nature of N-Queens: a cutoff depth twice deeper results in an active set 725× bigger. When choosing cutof f = 5, the search takes the same time as for cutof f = 4. Despite that, the distribution of A d is on average 9× slower for cutof f = 5. Thus, the cutoff depth chosen is 4. Preliminary experiments also show that cutof f = 4 is the best value for the MPI+X implementation.

Chapel also provides two different distributed load balancing iterators: guided and dynamic, which are also similar to OpenMP's schedules of the same name. Experiments were carried out to identify the best chunk for both guided and dynamic multi-locale load balancing strategies. Both strategies present the best performance using the default chunk size.

Results

First of all, concerning the distributed load balancing strategies provided by Chapel, using the dynamic iterator is from 1.17× to 1.51× times faster than using no load balancing (static version). Moreover, the guided iterator does not seem a suitable load balancing in the scope of this work: it shows benefits compared to the static version only for sizes ranging from 18 to 20. For these problem sizes, using the guided iterator makes the search up to 1.21× faster than its static counterpart. In turn, using the dynamic distributed iterator results in a search from 1.21× to 1.25× faster than using the guided one. The benefits of using load balancing are not observed for the smallest solution space, i.e., for the problem of size N = 15. In such a situation, the static search performs better because there is no communication among locales during the search. As shown in Fig. 4, the overhead of data structure initialization and distribution becomes less detrimental as the solution space grows, and the benefits of using distributed load balancing can be observed.

It is shown in Fig. 5 how the distributed search scales according to the number of locales. The worst scalability is observed for the smallest size (N = 15). In such a situation, the initialization and distribution of A d amount for almost the whole execution time (see Fig. 4). For problem sizes ranging from 17 to 20, the dynamic version scales up to 20.5× (N = 19), whereas guided and static scale up to 16.8× and 16.9×, respectively (also for N = 19). The MPI+X version scales up to 25.4× (N = 18). Therefore, the distributed search in Chapel achieves up to 80% of the scalability observed for its MPI+X counterpart.

As shown in Fig. 4, running the Chapel program on multiple locales comes with the overhead of distributing A d across several nodes. However, the scalability results previously discussed take into account the search on (-nl 1). In such a situation, the active set is distributed across different nodes, the search similarly to a multicore and single locale one. One can see in Fig. 6 the best speedup reached for 4 to 32 locales compared to the search running on 2. Results closer to the linear speedup are observed: for 32 locales (16× more nodes) all three variations of the search written in Chapel and the MPI implementation reach a speedup of almost 13×, which corresponds to 81% of the linear speedup.

It is worth to mention that the time spent on distributing A d does not grow linearly according to the number of locales. As one can see in Fig. 7, the time required to distribute A d grows up to size N = 16, then it becomes almost constant. This behavior comes from the fact that the size of A d is the same for one or more locale(s). Thus, as the number of locales grows, the number of messages sent grows as well, but their size decreases. Moreover, the A d distribution is performed in parallel (Algorithm 2, line 9 ), and the Infiniband GASNet implementation supports one-sided communication.

In terms of wall-clock time, Chapel is equivalent to MPI+OpenMP when running on one locale. For the smaller solution space (i.e., N = 15), Chapel stands out and it is up to 25% faster than MPI+X. In such a situation, A d is not distributed, and the program behaves like a single-locale and multicore one. Moreover, MPI implements the SPMD programming model. This way, MPI is started, and its functions are called even for one locale. Additionally, it is worth to mention that Chapel is a compiled language and it is possible to program in Chapel both search strategy and data structures equivalent to the ones present in its counterpart written in C. In contrast, for multiple locales and bigger problem sizes, the Chapel distributed search is on average 16% slower than its MPI+X counterpart.

Discussion

Chapel's high-productivity features make it straightforward to design and implement a distributed backtracking based on a multicore and single-locale version.

There is no need for dealing with communication, metrics reduction, or distributed load balancing. Moreover, differently from the classic MPI+X, there is no need for using a different parallel library for each level of parallelism. Thanks to Chapel's global view of the control flow and data structures, the main difference between the multi-and single-locale versions lies mainly in the use of the PGAS data structures and distributed iterators for load balancing. As a consequence, the multi-locale version is only 8 lines longer than its singlelocale counterpart, which results in a code 33% bigger. In contrast, it is required to add 24 lines to the backtracking written in C-OpenMP to use MPI, which almost doubles the program size.

Chapel also shows to be competitive to MPI+OpenMP regarding performance. It is possible to program the search and data structures in a way equivalent to C, resulting in efficient single-core use. Additionally, the compiler also generates code for exploiting all cores a locale has, and the load balancing provided by Chapel is effective. One would argue that it could be possible to program an MPI+X version faster than the one used, and the results of the last section could have been more advantageous for MPI+X. However, that is also the case for Chapel.

The multicore portion of the MPI+X implementation was programmed by hand, differently from its counterpart written in Chapel. Therefore, a first improvement in the Chapel implementation is programming the code for using all CPU cores a locale has. Additionally, It is worth to mention that Chapel also supports MPI and ZeroMQ libraries for programming inter-locale communication and the distributed load balancing. However, it does not seem necessary, as the use of high-productivity features resulted in performance competitive to MPI+OpenMP.

Concerning limitations, it took much more time to configure the GASNet library for running on a cluster than programming the multi-locale code itself. Moreover, Chapel's documentation is restricted to a few system configurations, e.g., Infiniband network with Slurm for job spawning. In our case, GASNet could not run on an MXM network with a non-default partition key, and a modification in the GASNet code was necessary. This problem would keep a not so enthusiastic user from Chapel. The bright side is that it was not a Chapel-only effort, as other PGAS libraries, such as UPC, Fortran, SHMEM use GASNet as communication layer.

Finally, graphics processing units are crucial for solving big and challenging combinatorial optimization problems [START_REF] Carneiro | Um levantamento na literatura sobre a resolução de problemas de otimização combinatória através do uso de aceleradores gráficos[END_REF][START_REF] Gmys | Ivm-based parallel branch-andbound using hierarchical work stealing on multi-gpu systems[END_REF]. The adoption of Chapel by the parallel optimization community, besides performance and productivity, also depends on the support of GPUs. According to Chapel's official documentation, the Xeon Phi accelerator is supported. However, there is no information concerning the support of GPUs.

Future Works

Permutation combinatorial optimization problems are commonly solved to optimality by using Branch-and-Bound search algorithms (B&B) [START_REF] Crainic | Parallel branch-and-bound algorithms[END_REF]. Therefore, a first future research direction is to extend the proposed multi-locale backtracking into a distributed B&B. This way, it will be possible to solve challenging optimization problems, such as the Quadratic Assignment and the Flow-shop Scheduling Problem. Additionally, this future work will aim at larger scale clusters. Thus, it will be possible to investigate the limits of the productivity-aware features of Chapel concerning performance and scalability. A final future work is to compare Chapel to other PGAS-based libraries and high-productivity languages, such as SHMEM, UPC, and Julia. This work investigated the use of Chapel high-productivity language for the design and implementation of distributed tree search algorithms. A distributed backtracking for enumerating all valid solutions of the N-Queens problem was conceived. The concepts herein presented can be adapted for solving other permutation combinatorial problems by performing straightforward modifications.

Programmers familiarized with OpenMP can easily conceive a distributed tree-based search in Chapel. Despite the high level of its features, the distributed search written in Chapel scales well and the distributed load balancing schemes are effective. Experimental results show that Chapel is competitive to C-MPI+OpenMP in terms of performance and scalability. The most significant drawbacks found do not concern performance nor scalability. Instead, they are related to the configuration of the communication layer, which can be more time consuming than programming the distributed application itself.

It is worth to point out that the parallel optimization community already possesses legacy code mainly written in C, C++. Therefore, programmers may be resistant to learn another language and translate programs to Chapel. The capacity of Chapel to include C code can be a partial solution for this situation. One can reuse C code for node bounding and search procedure, whereas Chapel distributed programming features are employed for load balancing and communication. Finally, the lack of support for accelerators may also limit the adoption of Chapel by the parallel optimization community.

Fig. 1 .Fig. 2 .

 12 Fig.1. Task 0 is responsible for managing the centralized active set A and performing load balancing. The searches are independent, and metrics are reduced using the Reduce Intents of Chapel (Own representation adapted from[START_REF] Crainic | Parallel branch-and-bound algorithms[END_REF]).

Algorithm 1 :

 1 The multicore tree-based search algorithm.1 I ← get problem() 2 cutof f ← get cutof f depth() 3 A ← ∅ 4 A ←generate initial active set(cutof f, I) 5 forall node in A with(+ reduce metrics) do 6 metrics+ = tree search(node, cutof f, I) 7 end

Fig. 3 .Fig. 4 .

 34 Fig.3. Influence of the cutof f choice on the execution time. Values are for the N-Queens of size N = 17 and 32 locales (384 cores). On the X axis: the cutoff depth and the distributed active set size in parentheses (in 10 6 nodes).

Fig. 5 .

 5 Fig. 5. The highest speedup achieved by Chapel and MPI+X implementations when executed on 2 (24) to 32 locales (384 cores).

Fig. 6 .

 6 Fig.6. The highest speedup achieved by Chapel and MPI+X implementations when executed on 4 (48) to 32 locales (384 cores) and compared to the execution on 2 (24).

Fig. 7 .

 7 Fig. 7. Normalized time required to initialize and distribute A d . Results are for 2 (24) to 32 locales (384 cores).

Table 1 .

 1 Summary of the environment configuration for multi-locale execution and compilation.

	Variable	Value
	CHPL RT NUM THREADS PER LOCALE	24
	CHPL TARGET ARCH	native
	CHPL COMM	gasnet
	CHPL COMM SUBSTRATE	ibv
	GASNET IBV SPAWNER	mpi

https://chapel-lang.org/docs/modules/layoutdist.html

http://www.grid5000.fr

Acknowledgments

The experiments presented in this paper were carried out on the Grid'5000 testbed [4], hosted by INRIA and including several other organizations 4 . We thank Bradford Chamberlain, Elliot Ronaghan (from Cray inc.) and Paul Hargrove (Berkeley lab.) for helping us to run GASNet on GRID5000. Moreover, we also thank Paul Hargrove for the modifications in GASNet InfiniBand implementation necessary to run GASNet on GRID'5000 MXM InfiniBand networks.


Georis Creseveau

Claramunt Christophe

International Journal of Geographical Information Science

Keywords: Spatial Data Infrastructures (SDI), coastal stakeholders, use, Social Network Analysis (SNA), Data Flow Diagram (DFD)

Nowadays the continuous development of Spatial Data Infrastructures provides a favorable context for environmental management. But in fact, the real contribution of SDIs depends on the answers they provide to their users. To the best of our knowledge, few studies have addressed SDI uses at large. The research presented in this paper introduces a novel methodological approach for the study of SDI uses within the context of Integrated Coastal Zone Management (ICZM) in France. We develop a two)tier approach that combines a structural and data flow modeling analysis based on Social Network Analysis (SNA) and Data Flow Diagrams (DFD) applied to an online questionnaire and semi)structured interviews. The results reveal a multi)SDIs and multi)levels use which is structured around several key SDIs whose role is particularly significant, but complemented by a series of 'minor' SDIs. This use is also based on information flows between SDIs and other entities (e.g. institutional partners, working group) involved in the sharing of the geographical information within the framework of French coastal management.

Since the mid)1990s, the development of Spatial Data Infrastructures (SDI) matches the urgent need expressed at the international level to facilitate access, exchange and sharing of geographical information held by different producers in order to maximize their use, management and production [START_REF] Crompvoets | Assessing the worldwide developments of national spatial data clearinghouses[END_REF]. A SDI can be defined as a set of technological and non)technological components [START_REF] Rajabifard | Future directions for SDI development[END_REF] constituting an intra and inter)organizational network [START_REF] Vandenbroucke | A Network Perspective on Spatial Data Infrastructures: Application to the Sub)national SDI of Flanders (Belgium)[END_REF] contributing to broader goals such as economic development, social stability, good governance and sustainable management of the environment [START_REF] Williamson | Developing spatial data infrastructures: from concept to reality[END_REF][START_REF] Masser | Building European spatial data infrastructures[END_REF]. The development and implementation of SDIs at multiple levels [START_REF] Rajabifard | The role of sub-national government and the private sector in future spatial data infrastructures[END_REF] and the resulting geographical information flows should provide a favourable context for land management and planning. However, and as mentioned by many authors (Masser, 2005, Nedović) [START_REF] Budić | SDI effectiveness from the user perspective[END_REF][START_REF] Hennig | Spatial data infrastructures, spatially enabled society and the need for society's education to leverage spatial data[END_REF] the technological advances and operational frameworks behind the implementation of SDIs are not sufficient to ensure the achievement of this objective. In fact, taking into account the users' needs is a key factor for successful SDIs' development. However, while substantial efforts have been devoted to the definition of standards and technology platforms, little attention is given to users' expectations [START_REF] Vandenbroucke | INSPIRE & NSDI State of Play: D3.2 . Detailed survey on use and usability[END_REF]. This can be explained by the fact that SDIs are complex and large information systems implemented on top of different data infrastructures from conventional to web)based architectures, developed at different local, regional and national levels. Therefore, the search for a comprehensive view of the information that flows through these decentralized platforms, and identification of users' profiles, requests and expectations are far from being a straightforward task (Budhathoki et al., 2008, Nedović) [START_REF] Budić | SDI effectiveness from the user perspective[END_REF][START_REF] Hennig | Spatial data infrastructures, spatially enabled society and the need for society's education to leverage spatial data[END_REF].

The research developed in this paper introduces a methodological approach for the study and analysis of SDIs' use. The objective is to study SDIs' use through users' appropriation in their professional environment, the information flows, and the relationships that emerge, with a focus on the relationships between the different users' levels and SDIs' levels (e.g., from local to regional, regional to national). Our approach combines a structural and data flow modelling analysis based on Social Network Analysis (SNA) [START_REF] Wasserman | Social network analysis: Methods and applications[END_REF] and Data Flow Diagrams (DFD) [START_REF] Mylopoulos | Information modeling in the time of the revolution[END_REF]. The objective is the identification of the SDI structural characteristics on the one hand, and the information flows associated on the other hand. This should allow an exploration of SDIs uses and structural properties at the The SNA approach is based on a bipartite graph, a method relatively untapped in the field of SNA [START_REF] Borgatti | Network analysis of 2)mode data[END_REF] and where users as well as SDIs are modelled as nodes, and data flows between SDIs and users as arcs. We applied several graph)based operators that provide a series of structural analysis whose most significant patterns are explored by a visual exploratory framework as suggested by [START_REF] Tukey | Exploratory data analysis[END_REF] and [START_REF] Brandes | Explanation through network visualization[END_REF]. This SNA approach is complemented by a conceptual DFD representation that characterises the information flows between the SDIs and their users.

The objective is to reveal the main patterns that emerge from the local to the global levels. Finally, a visual integration of the SNA and DFD approaches provide a global structural and conceptual representation of the SDIs studied, thus highlighting the multi) level dimension of public policies related to land management and planning as well as the multiple levels of SDIs implementations.

The remainder of the paper is organised as follows. Section 2 develops the main modelling principles behind the SNA and DFD approaches. Section 3 briefly introduces the main properties of the case of French stakeholders while Section 4 presents the experimental study. Finally Section 5 discusses the main findings while Section 6 draws the conclusions and outlines further work.

!

Inspired by network theory, SNA approaches study humans' social networks to identify the structural properties and trends that emerge [START_REF] Wasserman | Social network analysis: Methods and applications[END_REF]Faust, 1994, Scott, 2000). The relations between the individuals of a given system, the local and global shapes are the focus of analysis [START_REF] Hanneman | Introduction to social network methods[END_REF]. The corpus is organized as a matrix that defines the relationships between the different individuals of the network and the analysis is based on a series of mathematical measures and graphical exploration. Several mathematical measures can be derived to characterize a social network, the individuals and their relationships.

Among them, the notion of centrality can express the involvement of an individual in the network [START_REF] Borgatti | Centrality and network flow[END_REF] through various measures such as the local measure of degree and the global measures of closeness centrality and betweenness centrality [START_REF] Freeman | Centrality in social networks conceptual clarification[END_REF].

The main advantage of an SNA analysis lies in its ability to not only provide a series of mathematical values that outline some local and global structural properties, but also to represent graphically and visually the relationships that emerge within the network [START_REF] Brandes | Explanation through network visualization[END_REF] in a sort of visual exploratory framework [START_REF] Card | Readings in information visualization: using vision to think[END_REF]. The SNA approach provides the structural component of our modelling approach. It is particularly suited to the representation of the individuals involved in a given network, and has the advantage of providing a series of mathematical measures to evaluate local and global properties.

While SNA provides a sort of static view of the interactions and individuals involved in a given social network, a behavioural approach should support the representation of the dynamics of a given system. The selected approach, Data Flow Diagrams (DFD), came from the domain of information design, and while initially applied to software engineering although its scope has been now largely extended to a wide range of data and information modelling [START_REF] Mylopoulos | Information modeling in the time of the revolution[END_REF]. Based on a graphic formalism, DFD diagrams denote how data are used by a system on the one hand, and on the other hand, [START_REF] Li | Data Flow Diagram[END_REF]. Thanks to a hierarchical decomposition of data processes, the DFD approach provides a series of nested diagrams; from the most general diagram called context diagram (also known as "level 0" diagram), to the increasingly more specific diagrams describing in greater detail, processes and data flow [START_REF] Whitten | Systems analysis and design methods[END_REF][START_REF] Li | Data Flow Diagram[END_REF][START_REF] Shelly | Systems analysis and design[END_REF].

So far SNA and DFD analysis have been often applied to model humans' social network and the dynamics of some systems of interest, respectively. However, and to the best of our knowledge, they are hardly applied together. The approach developed in this paper combines the two approaches in order not only to study the main patterns that emerge from several SDIs modelled as a social network where actors interact with the SDIs, but also as a set of SDIs and actors interacting according to some general use patterns.

The SNA approach represents explicitly the relationships between a series of SDIs and users interacting with them as part of their professional practices. The network representation developed is based on a bipartite directed graph relating two types of nodes: users and SDIs. Links model uses, that is, relationships between users and SDIs, and are oriented from the users to the SDIs. The network that emerges not only provide an explicit representation of all uses of a large set of SDIs (macro view), but also a detailed representation of the uses of a given SDI (micro view). A series of graph)based measures are applied to reflect the local and global specific properties of the network, that is, the measures of degree, betweenness centrality and closeness centrality. The degree of a node is given by the number of nodes connected to that node, it is a local The betweenness centrality evaluates the proportion of the shortest paths between the nodes pairs which pass through a given node. The closeness centrality reveals whether a given node can reach other nodes with a path on the graph comprising a fairly limited number of arcs. The betweenness centrality C b (n) (1) of a node n is given as follows [START_REF] Newman | The Structure and Function of Complex Networks[END_REF]:

Cb(n) = ∑s≠n≠t (σst (n) / σst) (1)
where s and t are nodes in the network different from n, σ st denotes the number of shortest paths from s to t, and σ st (n) is the number of shortest paths from s to t that n lies on.

The closeness centrality C c (n) (2) of a node n is defined as the reciprocal of the average shortest path length and is computed as follows [START_REF] Sabidussi | The centrality index of a graph[END_REF]:

Cc(n) = 1 / avg( L(n,m) ) (2)
where L(n,m) is the length of the shortest path between two nodes n and m. The closeness centrality of each node is a number between 0 and 1.

The figures that emerge from the application of these measures are often complemented by the visual analysis of the represented graphs for exploration purpose [START_REF] Tukey | Exploratory data analysis[END_REF]. In particular, the graph)based and exploratory analyses are applied to the bipartite graph at two levels of abstraction: the institutional level upon which the user works, and the one that models the institutional level upon which the SDI is implemented. The application of these two criteria takes into account the multi)level dimension of public policies reflected by land management and planning activities, by the SDIs implementation, as well as the importance of reflecting the collaborative interactions between the different SDIs considered [START_REF] Vandenbroucke | Spatial Data Infrastructures in France: State of play 2011[END_REF]. The network and structural components of our modelling approach and the SNA represented have been implemented on top of the SNA software UCINET and NETDRAW [START_REF] Borgatti | Ucinet for Windows: Software for Social Network Analysis[END_REF] that respectively provides several graph)based measure analysis and visual functions [START_REF] Knoke | Social network analysis[END_REF]Yang, 2008, Huisman and[START_REF] Huisman | Software for social network analysis[END_REF].

Based on a conceptual and graphical representation of the users' professional practices, the DFD analysis represents and categorizes information flows between the SDIs identified by the SNA approach, as well as the other institutional entities and relationships to them.

The DFD analysis is materialized by a context diagram. This allows a generalization of the main functions of the networks of SDIs, as well as the external entities interacting with them. The context diagram is developed according to several modelling abstractions [START_REF] Yourdon | Structured design: Fundamentals of a discipline of computer program and systems design[END_REF]) that represent SDIs, users and information flows. SDIs are represented by "system" symbols (i.e., circles) while users by the symbols "external entity" (i.e., rectangles) and information flows by the symbol "flow" (i.e., arrow). As for the SNA analysis, the DFD analysis is also based on a multi) level structure in order to take into account both the territorial levels of public policies as well as the different levels of the SDIs implementation.

" # $ $ % &

The experimental framework has been applied to the coastal zone management context in France. Across the land)sea interface, coastal areas are complex territories [START_REF] Sale | Stemming decline of the coastal ocean: rethinking environmental management[END_REF] whose management is supported by a wide range of actors and institutions involved at various scales and with differing objectives. Indeed, management and planning tasks require appropriate geographical information at the most relevant scales [START_REF] Bartlett | GIS for coastal zone management[END_REF]. In particular, the need for multiple informational resources (i.e., environmental, economic, social, cultural, etc.) on several coastal regions, and this at complementary scales, implies collaboration and information between data producers and users [START_REF] Gillespie | MGDI: An information infrastructure to support integrated coastal management in Canada[END_REF][START_REF] Sale | Stemming decline of the coastal ocean: rethinking environmental management[END_REF][START_REF] Butler | Spatial Data Infrastructures in Support of Ecosystem Based Management and Ecosystem Approach to Fisheries in the Caribbean[END_REF].

The continuous search for a better wealth, as well as the need for a better use of the potential of French marine and coastal zones, has placed these territories at the heart of the national policy. This has led to identify the collection and sharing of geographical information via SDIs as a major component to favor the development of coastal and marine public policies. Our study considers coastal stakeholders from the public sphere and involved at different institutional levels (i.e., local, regional, national) in the implementation of management policies of French coastal areas. The data collection strategy combines an online questionnaire with the participation of 196 coastal stakeholders from all over the country and semi)structured interviews conducted with 30 key)informants [START_REF] Tremblay | The Key Informant Technique: A Nonethnographic Application[END_REF], with varied profiles and chosen among all respondents of the online questionnaire.

The 196 responses to the online questionnaire were represented by the SNA approach, while the minutes of the 30 semi)structured interviews have been modelled

by the DFD approach (Table 1).

! " # #

The 196 coastal stakeholders who cooperated in the investigation and submitted replies to the questionnaire overall identified 80 SDIs used for coastal practices. More than half of the respondents (56.5%) reported using several SDIs (from 2 to 11).

Amongst several trends observed and measured, the SNA analysis outlines the multiplicity of the SDIs use reported by the coastal respondents. It also appears from this analysis, that the resulting graph of the nodes and links is highly polarized, this denoting a scale)free network [START_REF] Barabási | Emergence of scaling in random networks[END_REF]. This reflects the fact that a few SDIs are connected with a large number of users, while many SDIs are used by only one or a small number of coastal users.

The SNA analysis also characterizes the "multi)SDIs" use, and this both by the graph)based measures previously introduced and by a visual exploration of the graph produced. The degree reveals the most connected nodes (Table 2 and Figure 1). The measure of degree identifies the most important SDIs having many coastal users, such as the Geoportail, French national SDI or the CRIGE)PACA, the oldest French regional SDI with a community of more than 1,200 partner organizations.

The measure of betweenness (Table 3 andFigure 2) continues the analysis by highlighting SDIs whose users are likely to interact with other SDIs. Some complementarity trends can be observed, for instance between the SDIs Geoportail and CRIGE)PACA as several users are interacting between them. Other complementarity trends can be observed between these important SDIs and SDIs that play a minor role, located at the periphery of the network. Amongst a set of SDIs that play a minor role, let us mention the ones that provide some thematic geographical information (e.g., InfoTerre 7 , SIT PNR PACA 8 ) or European data (e.g., INSPIRE 9 ).

While the previous measures highlight the important SDIs in the network, the measure of closeness (Table 4 and Figure 3) reveals the SDIs at the periphery of the network, that is, the ones that play a secondary role in the network. In fact these SDIs are connected to a few users, those users being also not very active in the network. For instance, on the periphery of the graph there is a SDI related to an overseas area (e.g. Martinique for SIG 972), or another one that provides access to information of lesser geographical relevance (e.g. statistical information for SOeS), or another one whose access is restricted to a certain category of users (e.g., public servants for Prodige)Picardie).

In order to further characterize the "multi)SDIs" use, the bipartite graph has been structured by levels (Figure 4). The interest of this multi)level representation is that the respective importance of each institutional level, as well as the SDI territorial levels, can be visually revealed. In particular the prominent role of regional SDIs in the circulation of coastal information can be clearly observed, with 51% of the total number of links. The national SDIs play also an important role with 29% of the total number of links. These links come from users working mainly at regional and national levels.

Last but not least the SNA analysis can also show the specific properties of a given SDI at the micro level as illustrated in Figure 5 for the SDI Geoportail and for the SDI CRIGE)PACA in Figure 6. This local analysis shows notably that the large majority of users (98 %) of the national SDI Géoportail combine others SDIs while just over half of the users (53 %) of the regional SDI CRIGE)PACA interact with other SDIs than CRIGE)PACA.

! $ "

The DFD approach is applied to the interview minutes that describe the professional practices of 30 coastal key)informants interacting with the SDIs identified by the SNA analysis according to the implementation level of the SDI and the professional level of the key)informant. The diagram focuses on the Geoportail and CRIGE)PACA.

The analysis reveals the main actions carried out by the coastal key informants and the noticeable geographical information flows. These actions include (1) access to geographical information ("search/find" flow) and ( 2) sharing geographical information ("disseminate" flow) (Figure 7).

The DFD approach also identifies a series of additional sources of geographical resources that the coastal key)informants are searching for, while non)accessible via the available SDIS, but necessary to carry out their tasks (Figure 8). These additional sources of geographical informational are mainly obtained from the (1) generation of new information through field observations ("gather" flow) and (2) solicitation of institutional partners involved in the management of the coastal territory. The latter are essentially provided by some informal exchanges ("request / receive" flow) but that sometimes doesn't succeed ("request" flow).

Finally, the DFD approach also stresses the importance for the key)informants to be involved in working groups implemented by some SDIs ("contribute" and "disseminate" flows) (Figure 9). These groups are dedicated to certain themes such as "coastal and marines zones", their goals are to ease and enhance the access and the sharing of geographical information at all levels. The groups identified are specific means that favour exchange and cooperation between coastal stakeholders at different territorial levels. They act as communities of practice [START_REF] Wenger | Communities of practice: Learning, meaning, and identity[END_REF], and allow the actors to act together for management and planning purposes.

! %& #

Overall the experimental study of coastal stakeholder practices has been developed using a "user)centred" approach as suggested by a series of previous works (Masser, 2005, Nedović) [START_REF] Budić | SDI effectiveness from the user perspective[END_REF], Sadeghi)Niaraki et al., 2010[START_REF] Hennig | Spatial data infrastructures, spatially enabled society and the need for society's education to leverage spatial data[END_REF].

The analysis and interpretation have been performed thanks to the combination of SNA and DFD modelling methods applied to an online questionnaire and semi)structured interviews. The results reveal a better understanding of the SDIs' use. The SNA analyses have identified the main SDIs used by coastal stakeholders and the main structural properties that emerge. For instance, the bipartite graph visually presented by institutional levels, highlights the respective roles of the SDIs at each institutional level in the exchange and sharing of geographical information. This multi)SDIs and multi) levels use is structured around several key SDIs (e.g., Geoportail and CRIGE)PACA)

whose role is particularly significant, but complemented by a series of 'minor' SDIs.

This reveals the fact that most users interact with key SDIs while also interacting with SDIs playing a minor role, this combination being necessary for coastal stakeholders acting in specific territories.

The DFD approach reveals the main information flows between the SDIs identified by the SNA analysis and the role played by the other entities (e. However, the results also emphasize the fact that geographical information provided by the coastal community is still scarce. The main reasons given by the coastal actors to explain these difficulties to access and share geographical information are not technological, but social and institutional as emphasized by many authors [START_REF] Canessa | Spatial Information Infrastructure for Integrated Coastal and Ocean Management in Canada[END_REF][START_REF] Wright | Spatial Data Infrastructures for Coastal Environments[END_REF][START_REF] Gourmelon | Geographic Information System for Integrated Coastal Zone Management in Developing countries: cases studies in Mauritania, Côte d'Ivoire, Guinea)Bissau and Morocco[END_REF]. Whith this in mind, the DFD approach highlights the key role of the working groups implemented by the SDIs by encouraging information flows between the partners. Therefore, members gradually become "produsers" [START_REF] Budhathoki | Reconceptualizing the role of the user of spatial data infrastructure[END_REF] that use, provide and disseminate geographical information via the SDIs. These working groups act as strong catalysts for geographical information flows in the coastal community.

-

The objective of the research presented in this paper is to provide an integrated approach for the study of SDIs uses. Amongst the many actors involved in the implementation of the SDIs, users have a special and key position [START_REF] Omran | Spatial-Data Sharing: Applying Social-Network Analysis to study individual and collective behaviour[END_REF][START_REF] Grus | Spatial data infrastructures as complex adaptive systems[END_REF], Nedović)Budić et al., 2008[START_REF] Mäkelä | Competence management within organisations as an approach to enhancing GIS maturity[END_REF][START_REF] Van Loenen | Assessing geoportals from a user perspective[END_REF]. The in)depth analysis of 28 definitions of SDIs conducted by [START_REF] Hendriks | Reconsidering the definition of a spatial data infrastructure[END_REF], highlights the significant role played by these users. It clearly appears that a better knowledge of the users' practices and feedbacks are surely important factors within the context of the democratization of geographical information [START_REF] Mcdougall | From silos to networks)will users drive spatial data infrastructures in the future? 24[END_REF], and the emergence of Volunteered Geographic Information [START_REF] Goodchild | Citizens as sensors: the world of volunteered geography[END_REF]. The experimentation also provides some insights for further developments. For instance, the SNA approach can be extended to the temporal domain in order to analyze the evolution of the SDIs uses over time. Indeed, the objective is to repeat the on line survey in 2017, this allowing a comparison of practices and SDIS' structural properties over time [START_REF] Knoke | Social network analysis[END_REF].

Several mathematical measures have been applied in this paper to reveal some structural network properties. We plan in future work to explore the interest of several additional measures (e.g., information centrality [START_REF] Stephenson | Rethinking centrality: Methods and examples[END_REF])) as well as additional visual variables for the study of SDIs' uses. We would like to also explore the way DFD representations can outline the respective roles of the different working groups within a particular coastal community. Amongst several avenues still opened, geographical information flows between SDIs and stakeholders are still to be categorized and studied. Such flows might be evaluated according to several parameters such frequency of use, level of satisfaction, etc. Finally, the method and formalisms developed should be transferred to other methodological approaches in different contexts at the international level as well as to the terrestrial and marine domains. This paper introduces an integrated SNA and DFD approaches for the study of SDI uses within a coastal community. By applying the method and models developed to a wide range of use contexts and various territorial levels (from the local level to the national level), the study reveals the complexity of SDIs uses. In particular, the combination of the SNA and DFD approaches favours a global interpretation of the graphs and diagrams generated, as well as some "micro" analysis.

While the SNA analysis focuses on the characterization of a large set of SDIs used by a broad coastal community, the DFD approach analyses more finely how these SDIs fit into the daily life of coastal managers and how they contribute to coastal zones management. The analytical methods are based on a series of graph)based and graphical analyses, visually enhanced by a multi)level representation that favours an identification of the respective roles played by the different institutional levels and SDI implementation levels. This integrated strategy and combination of analytical and modelling analyses constitute the fundamentals of a replicable approach that links the macro and micro visions of SDIs' uses. This in fact generates a sort of global view of a SDI system and also favours a better understanding of the SDIs appropriation in the context of complex multi)actor and multi)level territorial governance.

The proposed methodology can be applied to the study of the roles played by the users involved in third generation SDIs implementations [START_REF] Mcdougall | From silos to networks)will users drive spatial data infrastructures in the future? 24[END_REF][START_REF] Hennig | Spatial data infrastructures, spatially enabled society and the need for society's education to leverage spatial data[END_REF] and should contribute to the Multi)View Framework to assess SDI [START_REF] Crompvoets | A Multi. View Framework to Assess Spatial Data Infrastructures[END_REF]. Topic)wise, the methodology allow to assess how the flow of geographic information affects environmental management practices and environmental governance [START_REF] Mol | Environmental reform in the information age[END_REF].

  levels, as well as an exploration of users' patterns at the individual level.

  entities involved (i.e., people or systems). It allows primarily to materialize the data flows between the involved entities

  measures of betweenness centrality and closeness centrality consider the network as a whole.

  g. institutional partners, working group) involved in the sharing of the geographical information within the framework of French coastal management. The combination of SDIs, information flows and informational resources provide a global view of a given coastal zone, not straight availability of geographical information. Such information frameworks can be used as public policy instruments to understand, act, communicate and cooperate; the objective being to provide a better support for coastal zones management.

  combination of graph)based measures and visual exploration of the SNA approach, different SDI behaviors and complementarities can be observed. In particular, this study shows the multi)SDIs use reported by the respondents. The DFD analysis allows us to analyze the existence (and non)existence) of geographical information flows between the SDIs and additional geographical resources. Thanks to an integration of the multiple territorial levels of both the SDIs implementation and coastal manager interactions, the multi)level framework of the SNA and DFD analysis adds an extra dimension to the study. This favors an analysis of the respective roles played by each institutional level, as well as the information flows between them.

Figure 1 .Figure 2 .Figure 3 .Figure 4 .Figure 5 .Figure

 12345 Figure 1. Degree graph (Nuser=196, NSDI = 80, Narc =403

Table 1 .

 1 Main methods and data applied to the study

	'		&	) $*
		(
	1. Online	SNA	coastal stakeholders from the public sphere	196
	questionnaire		involved at different institutional levels
			(local, regional, national)
	2. Semi)structured	DFD	Key)informants chosen among all the	30
	interviews		respondents of step 1

Table 2 .

 2 Degree values of the six most connected SDIs in the network

	SEXTANT 1

4 http://www.geopal.org/accueil 5 http://www.geoportail.gouv.fr/accueil 6 http://www.crige)paca.org/ Page 9 of 29 http://mc.manuscriptcentral.com/tandf/ijgis

Table 3 .

 3 SDIs with the highest betweeness values

	! %	,

Table 4 .

 4 SDIs with the highest closeness values

	International Journal of Geographical Information Science

7 http://infoterre.brgm.fr/ 8 http://www.pnrpaca.org/index.php?cont=login 9 http://inspire)geoportal.ec.europa.eu/ Page 10 of 29 http://mc.manuscriptcentral.com/tandf/ijgis

http://mc.manuscriptcentral.com/tandf/ijgis International Journal of Geographical Information Science

http://mc.manuscriptcentral.com/tandf/ijgis

http://mc.manuscriptcentral.com/tandf/ijgis International Journal of Geographical Information Science Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org)