Sylvain Genevès
email: sylvain.geneves@inria.fr

An Analysis of Web Servers Architectures Performances on Commodity Multicores

Keywords: Multicore architectures, Web servers, performance, scalability, parallelism, memory

We study the impact of concurrent programming models on multicore performances of Web servers. More precisely, we consider three implementations of servers, each being representative of a particular model: Knot (threadbased), µserver (event-driven), Watpipe (stage-based). Our experiments show that memory access costs increase with the number of cores. We also show that at 8 cores we reach a point where the memory is fully saturated, leading to all Web server implementations having the same performance. Using fine-grain profiling, we are able to pinpoint the cause of this issue as a hardware bottleneck: the saturation of the address bus. Further memory benchmarking on a 24-cores machine show that a memory-related scalability issue is still present beyond this point.

I. INTRODUCTION

As traditional monocore architectures reach electrical and power limits, multicore processors arise as a solution to continue to gain performance. The current hardware trend is to add more and more cores on a chip. Multicore is now mainstream on general-purpose processors as well as on specialized hardware, thus we believe that every developer should feel concerned about parallelism.

In this context, this paper focuses on the increasingly important issue of data server scalability. As the Internet is growing wider and wider, popular websites must now handle an incredible load. For example, Wikipedia's website has to deal with periods of up to 90 000 requests/second for several hours, every day 1 . We focus our study on servers serving static content. This, however, does not limit the scope of this paper only to static Web sites. Indeed, high-traffic dynamic Web sites wide use of proxies and caches make studies of servers serving static content relevant. As an example, when at peak, Facebook serves over 1,000,000 images per second [START_REF] Beaver | Finding a needle in haystack: facebook's photo storage[END_REF].

Unfortunately, it is well-known that Web server throughput does not scale well with the number of cores. With the spreading of multicores technologies, this is becoming an increasing economic concern for building efficient data centers. 1 http://en.wikipedia.org/wiki/Wikipedia:Statistics Our overall goal is to search for the most efficient ways to serve many concurrent client requests. There exist several concurrent programming models to develop software leveraging multicores, each of them being of very different nature. This paper aims at comparing the different programming models from the point of view of scalability. For this purpose we focus on the three mainly used models in the data server context: the thread-based model, the event-driven model and a stage-based hybrid model.

Contributions

The main contribution of this paper is a thorough comparative analysis of the scalability of the different programming models and a report on extensive experiments that provide clear -and sometimes surprising -insights about the identified bottlenecks. Those insights include the following:

• Unexpectedly, the same scalability issue is observed on all the tested Web servers once a certain threshold on the number of cores is reached. Profiling shows that the encountered bottleneck is memory-related, indicating that a solution residing in hardware memory management should be looked for, independently from any chosen programming model. • Fine-grain profiling helped us to pinpoint the root of the encountered hardware issues. The cause lies in the cache coherence protocol implementation that saturates the address bus. • A direct approach to reduce memory sharing between cores (NCOPY) shows an improvement of 13% at 4 cores for event-driven and stage-based implementations. This is however not enough to solve our scalability concern, as performances at 8 cores are not improved. • Finally, our experiments show that the impact of system-wide tuning prior to Web server tuning is nonnegligible, as Web servers cannot use 100% of each available core's computational power with standard system tunings.

Outline

The paper is organized as follows. We describe the programming models and the reference implementations we choose for our analysis in Section II. Then in Section III we describe our experimental setup including preliminary work needed for a fair analysis. Section IV comments analysis results. We then discuss related work in Section V before concluding in Section VI.

II. PARALLEL PROGRAMMING MODELS

In this section we describe the three commonly used models to program data server applications that we consider in our analysis: threads, events and stages. We also introduce the corresponding implementations that we use in our experiments, as well as the modifications we brought to them in order to bring each model to its best potential on multicores, and thus allow for a fair comparison.

A. Threads

The most direct way to program a parallel server is to use one thread per connection and blocking I/O. Throughout this paper we use the common definition of a thread, as seen in standards such as POSIX: a schedulable entity with an automated stack management. The thread-per-connection model usually uses a pool of threads, thus avoiding thread creation/destruction costs with each new connection. The widely used Apache [START_REF]The apache http server project[END_REF] Web server uses this model. However, Apache supports a lot of features, such as virtual hosts, which could incur additional costs which are irrelevant in this study. For this reason, using this implementation for reprensenting the thread-per-connection model in our comparison would be unfair.

Knot: We choose the Knot Web server to represent the threaded server implementations. Our choice is directed by a previous study of this kind by Pariag et al. [START_REF] Pariag | Comparing the Performance of Web Server Architectures[END_REF]. Knot is a fast, efficient C implementation built to prove the efficiency of the cooperative threading Capriccio [START_REF] Von Behren | Capriccio: Scalable threads for internet services[END_REF] library. As Capriccio uses strictly one core, we modified Knot to leverage multicore architectures. To achieve that we made it link against the standard Linux threading package, the NPTL [START_REF] Drepper | The Native POSIX Thread Library for Linux[END_REF]. In the NPTL implementation, each thread is mapped on a kernel thread. This gives the kernel the power to decide how to map threads on cores, thus leveraging multicore architectures. The scheduling policy is also different from Capriccio, as it is preemptive. Though this was originally the purpose of the design of the Capriccio library, the NPTL can also handle thousands of threads, while leveraging multicores. We also added support for the zero-copy sendfile syscall. Since the contents of the files are not copied in userland, only the kernel memory is used, thus allowing to fully leverage the filesystem cache.

B. Events

In event-driven programming, the application only reacts to (mostly external) events, such as network I/O. An event loop is in charge of polling for new events and calling the appropriate application handlers. The common model is knowm as SPED 2 . Event handlers should not block in any way, since there is only one execution thread involved for the whole application. Instead of using blocking calls, one can postpone a computation until it can be executed in a non-blocking fashion. This results in event handlers calling one another asynchronously. Taken as it is, the SPED model cannot leverage multicores since there is only one thread for the whole application. The most direct approach to do so is to use NCopy. NCopy consists in duplicating the process onto each core of the machine. It can then leverage multicores, even if the main known drawback of this approach is the absence of data sharing between cores. To overcome this, the SYMPED3 architecture allows to share the listening socket among SPED processes.

Userver: µserver is an efficient, event-driven Web server implementation. It is written in C, and has support for the SYMPED architecture. Thus, there is no need for external load balancing like in traditional NCopy, where each copy must listen to a different port. We choose to use the sendfile and epoll primitives, as those lead to better performances than their alternatives in our setup.

C. Stages

The stage-based model has been introduced a decade ago [START_REF] Welsh | SEDA: An architecture for well-conditioned scalable internet services[END_REF], [START_REF] Larus | Using Cohort Scheduling to Enhance Server Performance[END_REF]. In this model the application is composed of stages, that look like event handlers at first sight. The idea behind this is to give a set of execution resources to a stage. Those resources can be threads for example, or anything that the runtime controls. Thus there is a difference with event handlers: a single stage can be executed simultaneously by multiple threads. This allows for the runtime to finely control execution of an application, by dynamically reallocating the number of threads on a stage, or ease the use of admission control.

Watpipe: Watpipe [START_REF] Harji | Performance comparison of uniprocessor and multiprocessor web server architectures[END_REF] is a C++ implementation of a stage-based Web server, derived from µserver's code. Watpipe's stage system does not dynamically tune the server according to the load. However, since our workload does not evolve over time, and since in addition we finely tune each server there is no need for dynamic auto-tuning in our setting.

D. Remark

As we saw in this section, changing the concurrency programming model in a Web server has a big impact on code paths. Thus comparing different Web server implementations makes sense, as long as they provides a similar set of features. To the best of our knowledge no Web server implementation provide more than one concurrency model. Even if Apache's httpd provides different Multi-Processing Modules (MPM), in the end they all use the thread-perconnection model 4 . The difference lies in that the worker MPM uses a hierarchy of threads and processes, whereas the prefork MPM uses only process and no threads.

III. EXPERIMENTAL SETUP

Each of the Web server implementations we chose thus leverages multicores. More precisely, the load is evenly balanced among cores for each of the three implementations. Thus we expect some sort of performance scalability with the number of cores, at least until the reach of maximum network bandwidth.

In order to make a fair comparison from which we can extract meaningful results, several additional aspects of crucial importance must be taken into account. We present them below, while detailing the hardware setup and the workload we consider.

A. Important aspects for a fair comparison

Same set of features for each implementation: Implementations must be comparable in terms of kind and quantity of computations associated with each request. Features in Apache such as virtual hosts, security checks or other hooks for optional plugins would make a performance comparison with µserver unfair. By choosing Knot, µserver and Watpipe we ensure a very similar set of features. To be even closer, we added support in Knot for the sendfile primitive that µserver and Watpipe use. Comparing these implementations against the same workload thus makes sense.

Reaching the optimal performance for each model: To enforce fairness in our comparison we must make sure that each server works at full capacity. To do this, we finely and independently tune each server until it reaches its maximum throughput. We detail the tuning procedure that we applied in III-D, after presenting the hardware setup and considered workload.

Reproducibility of results: For all the results presented in this paper, we make sure that the standard deviation is under 4% over at least 10 runs for Web server experiments, and 100 runs for memory benchmarks. All the discussions in this paper are based on performance differences significantly greater than observed standard deviation.

B. Hardware setup

We use the hardware from Grid5000 experimental platform. More precisely the cluster "chinqchint" from Lille's site is composed of 46 identical nodes. Each of those is a bi 4-cores Intel Xeon E5440 clocked at 2.83 GHz, totalling 8 cores per machine. Each core has a 32KB L1 instruction cache and a 32KB data cache. All L1 caches are private. A unified 6MB L2 cache is shared by two cores on the same package. Each node has 8GB of main memory. Each node is also equipped with 10Gb Myri-10G (10G-PCIE-8A-C) network card and two 1Gb Intel e1000, totalling 12Gb of network bandwith capacity. The network interrupts are affinitized to all the cores, as it is the most efficient way to balance the load among all the cores in our setup. For all experiments, the machines run a 2.6.37 Linux kernel, with the 2.11.2 libc. For reproducibility purposes, Table I shows our main changes in the system configuration. We found those changes necessary to benchmark the system at full capacity, especially the ones related to the maximum number of connections, files and backlog queue size.

We use one of these nodes as a server, and 35 others as clients. All the nodes are connected via a 128-port 10Gb switch for their 10Gb interface, and gigabit switches for the other two network cards.

Each client machine runs 6 instances of the workload generator. In this way, we ensure that the clients are sufficiently provisioned not to constitute a bottleneck. We also check that a client is never saturated, would it be in terms of available file descriptors, network bandwidth, CPU or memory resources.

C. Workload

We use the same HTTP workload as in [START_REF] Pariag | Comparing the Performance of Web Server Architectures[END_REF]. This workload is based on the static part of SpecWeb99 [START_REF]Standard Performance Evaluation Corporation)[END_REF]. We note that static content is still a large part of each workload in the recent SpecWeb2009 [10]. Besides, using dynamic workloads would impose the use of external processes accessed by the server through CGI. The evaluation of the impact of those additional processes with the different programming models and their scheduling is beyond the scope of this paper. Our file distribution consists of 24480 files, totalling 3.3GB of data. For all experiments, this distribution is prefetched in RAM using the filesystem cache. This way we avoid limitations due to disk I/O. The access pattern to the files recreate a Zipf distribution, we can note that this is also the case for the static part of SpecWeb2009.

As in [START_REF] Pariag | Comparing the Performance of Web Server Architectures[END_REF], we use httperf [START_REF] Mosberger | Httperf, a tool for measuring web server performance[END_REF] to replay HTTP access log files. This addresses two problems of the SpecWeb99 benchmark suite. First, SpecWeb99 uses a closed-loop injection scheme which leads to the injection being driven by the server at some point [START_REF] Schroeder | Open Versus Closed: a Cautionary Tale[END_REF]. The second problem noticed in SpecWeb99 is the lack of think times. We thus use the partially-open loop injection scheme suggested in [START_REF] Schroeder | Open Versus Closed: a Cautionary Tale[END_REF] to address the first problem, and the same HTTP trace files as in [START_REF] Pariag | Comparing the Performance of Web Server Architectures[END_REF] to solve the second one, since they contain think times. Two types of think times are used: inactive off-period and active off-period. Inactive off-periods model the time taken by the user between two consecutive requests, taking into account actions such as reading the page, as well as other delays occurring between user requests. Active off-periods model the time needed by the browser for parsing an initial page, initiating requests to fetch objects embedded in this page, and waiting for the responses. For the sake of allowing comparisons with the study described in [START_REF] Pariag | Comparing the Performance of Web Server Architectures[END_REF], we choose the same parameters: 3.0 seconds for inactive off-periods and 0.343 for active off-periods.

D. Tuning

In this study we carefully tune each server independently to reach its peak performance. As previously shown by [START_REF] Pariag | Comparing the Performance of Web Server Architectures[END_REF], server tuning is crucial prior to any performance comparison. In the present work, we further observed that, even prior to server tuning, system tuning is critical in order to bring all the software stack at its full potential. Indeed, the Linux kernel is shipped with standard tunings that do not meet the requirements for Web server benchmarking. Our first experiments with standard backlog queues tunings show that the server cannot use all CPU resources when the load increases. The most dramatic case appears with Knot, where at 8 cores the average CPU usage is stuck at 33%, the throughput remaining flat as the load increases from 5000 connections/sec to 20000 connections/sec. We observe similar behaviour with µserver and Watpipe.

Once the system is properly tuned, the CPU and network load on the server increase along with the clients inputs, until we reach CPU saturation of the server. We are then able to finely tune each server independently, as done in [START_REF] Pariag | Comparing the Performance of Web Server Architectures[END_REF]. Since our workload is partially-open loop, it consists in finding the appropriate number of concurrent requests for a server to reach its maximum throughput, while avoiding to trash the system. This tuning phase is done for 1, 2, 4 and 8 cores. In Knot, the number of concurrent connections is directly connected to the number of threads in the pool. For µserver, this corresponds to the size of the event queue. The corresponding Watpipe's parameter is the number of threads associated to read and write stages.

IV. RESULTS

This section comments our analysis results. For the sake of comparison fairness, only results pertaining to the best throughput of each server are discussed.

A. Performance comparison of programming models

Figure 1 shows our results using only 1 core on the server, reproducing Pariag et al. [START_REF] Pariag | Comparing the Performance of Web Server Architectures[END_REF] work. Instead of the 18% maximum throughput difference observed in their setup, we observe a 35% maximum difference between Knot and Watpipe. The throughput observed here is globally much higher than the one observed in [START_REF] Pariag | Comparing the Performance of Web Server Architectures[END_REF]. For example, when using a similar configuration (one core server), we obtain throughputs up to 2.8Gb/s instead of the barely reached 1.5 Gb/s in [START_REF] Pariag | Comparing the Performance of Web Server Architectures[END_REF]. Nonetheless, if the numbers change because of the setup, our conclusions remain globally similar as those drawn by [START_REF] Pariag | Comparing the Performance of Web Server Architectures[END_REF]. That is, Watpipe and µserver clearly outperform Knot's performances. The fact that we use the standard NPTL instead of the Capriccio library when running Knot is worth noticing because it results in a pure threaded execution.

Figure 2 presents the Web servers throughput when using 8 cores on the server machine. Only the best configurations for 8 cores of each server are considered. It is worth noticing that the peak throughput point is simultaneously reached by all the three implementations, and at this point the throughputs coincide (6.6Gb/s). After this point, all the servers are saturated, and throughput decreases. The network is not the bottleneck here, as we can achieve throughputs up to 11Gb/s using network benchmarking tools such as netperf or iperf. This is surprising since it corresponds to an improvement of only 2.3 times of the performances observed using 1 core. As all of the three models fully leverage multicores architectures, one could expect a better scalability, at least until the network becomes a bottleneck. However, our experimental data indicate that the full network capacity is not reached and the servers expose poor scaling. At this stage we perform a further scalability analysis in order to better understand the performances of the three servers.

B. Performance scaling analysis

Figure 4 presents the scalability of the three server implementations. This plot is obtained using the highest throughput configuration for each server on each core configuration. The most obvious behaviour is a scalability issue arising at 4 cores. This issue is so important that all the implementations expose the same highest performance at 8 cores. We use the profiling tool OProfile [START_REF] Johnson | OProfile homepage[END_REF] to pinpoint the possible causes of this issue. A good metric to start with is cycles per instructions, also known as CPI. Table II summarizes the CPI of each Web server for all core configurations. We observe that the number of cycles needed to execute one instruction doubles when switching from 1 to 8 cores. We eliminate the possibility of lock contention as a cause of the issue encountered at 8 cores, as the use of standard locks would put the competing process to sleep and prevent a full usage of the CPU (at least for the event-driven case, since there is only one process per core). As well, contention on spinlocks would cause a CPI decrease, as the number of lock acquiring instructions would dramatically increase. An increase of CPI usually corresponds to stalls. Using more advanced hardware performances counters 5 we can break down the increase of CPI. Figure 3 shows a decomposition of CPI for µserver in five categories. The cycles presented here are classified as:

• "Branch": which corresponds to stalls cycles due to Branch misprediction • "ROB": which represents cycles where the pipeline blocked any further execution due to the Re-Order Buffer being full • "Other": which is the remaining cycles. It corresponds both to cycles spent executing usefull instructions, and possibly other stalls not counted here. We observe that stalls due to Loads&Stores instructions and full Reservation Station put together represent 40% of the total CPI at 8 cores.

The full Reservation Station event indicates long latency operations in the pipeline, most likely memory accesses, and other instructions that depend on these cannot execute until the former instructions complete their execution. In this situation new instructions can not enter the pipeline and start execution. This means that 40% of the cycles at 8 cores are spent accessing memory. From these numbers we deduce that the main causes of non-scalability of Web servers are related to high memory latencies. Those can be explained by further fine-grain profiling.

Note that, at 4 cores, Knot is performing better than µserver and Watpipe. The fact that Knot's CPI is smaller than the other two proves that it suffers less from stalls. Scalability of a memory-bound application can benefit from high context switches rate, but only if it decreases the number of memory stalls. This corresponds to the behaviour observed here for Knot.

C. Memory scalability

To analyze the origin of the high memory latencies, we conducted profiling experiments similar to the ones found in Veal et al. [START_REF] Veal | Performance Scalability of a Multi-Core Web Server[END_REF]. We did not notice any irregularity in caches and TLB behaviours, thus we analyzed the front side bus usage, as shown in Figure 5. In our experiments the data bus seems to stall around 20% at 4 and 8 cores, not increasing anymore as it does from 1 to 4 cores. When analyzing the address bus, we find an abnormal high usage for all servers: around 50% at 4 cores and over 80% at 8 cores. We believe this situation corresponds to address bus contention, leading to data bus not being able to deliver more throughput. This saturation happens because all cache coherence protocol messages (also known as cache snoops) are sent on the address bus. The cache coherence protocol used in our case is the MESI protocol. In this implementation, many of the messages are broadcasted to all the cores, especially on every load from main memory. This is why the saturation happens so fast.

The case of NUMA architectures: The hardware used in this study is UMA: Uniform Memory Access. In NUMA (NonUniform Memory Access) hardware, there is no more data and address buses, instead high-bandwidth nodes interconnect, and the memory is distributed among NUMA nodes. We use Corey's memory benchmark [START_REF] Wickizer | Corey: An Operating System for Many Cores[END_REF] to investigate what can be expected as a worst case scenario concerning Web servers scalability. In this benchmark, each core allocates a 1GB memory area on its local node, and accesses it sequentially, no data sharing is involved. We run this benchmark on a 24-cores NUMA machine (2x12 cores), and measure the memory throughput in terms of bytes accessed per CPU cycle. Our experiments show that the worst case scenario (using optimized MMX instructions) can only achieve a 4.8 speedup (12.1 speedup with standard instructions) using 24 cores. These preliminary experiments tend to show that the scalability issue due to memory access costs also occurs with NUMA architectures. Extending our investigations to NUMA architectures, which is beyond the scope of the present paper, nevertheless constitutes an interesting direction for future work.

D. Using NCOPY to reduce sharing

Since the memory coherence protocol is the cause of the scalability problem here, we are interested in reducing data sharing among cores. To reduce sharing in our experiments, we benchmark NCOPY solutions for each model. This allows us to evaluate the impact of sharing a single socket for accepting connections. Indeed, in NCOPY, each copy is a completely independent process, and thus listen to a different port. Note that contrary to previous experiments, an external load-balancer is needed in this case. We benchmark each model with all possible NCOPY partitionnings.

The table III presents the results of our NCOPY experiments along with previous results. 1 copy results corresponds to our previous plots. Numbers of interest are red. Interestingly, at 4 cores, when original configurations of Watpipe and µserver cannot keep up with Knot's throughput, the NCOPY versions expose the similar performances as Knot. For µserver and Watpipe, this is a 13% improvement over their respective original configurations. This means that the sharing cost is reduced by using NCOPY. More precisely here, accepting connections on more than one socket reduces memory contention enough to provide better performances, except for Knot which reduces contention by having a inherently higher cost of context switching.

We also note that no configuration is always the best. NCOPY is better at 4 cores to reduce sharing of eventdriven and stage-based implementations. At 2 cores, original SYMPED and stage-based configurations have higher throughput than their NCOPY configurations, or any of Knot configuration. It is because the duplication of data have a cost, and is not always worthy, as Web server performances also depend on their memory footprint [START_REF] Harji | Performance comparison of uniprocessor and multiprocessor web server architectures[END_REF]. Besides, the best 2 cores configurations in our experiments always happen with 2 cores sharing a L2 cache.

All of this suggests that paying attention to the underlying hardware setup can help predicting the best configuration to achieve good performances. For example, we know that if we choose 2 cores sharing a cache then choosing a NCOPY configuration is paradoxal, regarding memory sharing. The same goes at 4 cores, as we know that in our setup the last level of cache cannot be shared by all the chosen cores, then NCOPY is a good lead. More precisely, if we choose two pair of cores sharing a L2 cache, then we will choose to have two copies, each working on such a pair of cores. Our experiments show that having four copies in such a case decrease performance. We want to emphasize here the impact of hardware setup, and especially memory hierarchy, on Web server performances.

The figure 6 presents the best peak throughput achieved for each server among all its possible configurations (including NCOPY). We can observe a better performance scaling than without NCOPY at 4 cores for µserver and Watpipe. This is however not enough to provide better performance at 8 cores for any of the servers studied.

V. RELATED WORK

The three programming models studied here have been extensively studied in a monocore context by Pariag et al. [START_REF] Pariag | Comparing the Performance of Web Server Architectures[END_REF]. The main -and crucial -difference is that our comparative analysis deals with the multicore setting, and can thus be seen as a generalization of their work. Our methodology is inspired by the one found in [START_REF] Pariag | Comparing the Performance of Web Server Architectures[END_REF]: in particular, we use the same workload and similar Web server implementations. A notable difference is that we changed the underlying thread library used for Knot. There are two reasons for this change: first, the legacy Capriccio [START_REF] Von Behren | Capriccio: Scalable threads for internet services[END_REF] library is event-based and we want Knot to be representative of the thread-based model. Second, Capriccio cannot leverage multicore architectures and is thus inappropriate in our case.

A similar comparative study has recently been conducted by Harji et al. [START_REF] Harji | Comparing highperformance multi-core web-server architectures[END_REF] on small multicore hardware (4 cores). In this paper though, the authors have removed the threadper-connection model from their comparison. Our study differs in that we use larger hardware, which allows us to observe a new behaviour at 8 cores, not present with smaller hardware, and we include the thread-per-connection model in our comparison.

Multicore Web servers have been studied in the past. Choi et al. [START_REF] Choi | A Multi-Threaded PIPELINED Web Server Architecture for SMP/SoC Machines[END_REF] simulate simple hardware to compare different server designs with workloads built on real-world traces. We believe their workloads are not appropriate in the data server case that we consider due to their high I/O rate. In comparison, our approach considers a real hardware setup with recent hardware and in-memory data fileset. Though we do not deny the interests of simulation, we also believe that experiments on real hardware can lead to significantly different results.

Veal et al. [START_REF] Veal | Performance Scalability of a Multi-Core Web Server[END_REF] have also studied the scalability of the Apache Web server on very similar 8-cores machines. Using the SpecWeb2005 workload, they are able to show that Apache does not scale with the number of cores. They conclude that their address bus is the primary cause of this performance issue. The major difference with the work presented here is that we consider three programming models in a comparative analysis (through 3 representative implementations), whereas their study is limited to the Apache Web server (relying on the thread-based model). We can therefore draw more general conclusions that span over the three considered models.

Other works such as Corey [START_REF] Wickizer | Corey: An Operating System for Many Cores[END_REF] and Barrelfish [START_REF] Baumann | The multikernel: a new OS architecture for scalable multicore systems[END_REF] have made multicore Web servers experiments with ad-hoc implementations. PK [START_REF] Boyd-Wickizer | An Analysis of Linux Scalability to Many Cores[END_REF] and DProf [START_REF] Pesterev | Locating Cache Performance Bottlenecks Using Data Profiling[END_REF] have also benchmarked Apache in a multicore context. All these experiments were mostly aimed at stressing the kernel or the software stack, whereas we use a much more sophisticated workload (based on SpecWeb99) that simulates access patterns to a large file distribution, which are much closer to those encountered in the real-world. Furthermore, instead of using a modified kernel such as the ones found in [START_REF] Wickizer | Corey: An Operating System for Many Cores[END_REF], [START_REF] Baumann | The multikernel: a new OS architecture for scalable multicore systems[END_REF], [START_REF] Boyd-Wickizer | An Analysis of Linux Scalability to Many Cores[END_REF], we use a standard, unchanged kernel running on a commodity Linux operating system.

Finally, Voras et al. [START_REF] Voras | Characteristics of multithreading models for high-performance io driven network applications[END_REF] compare some known multithreading models for high-performance I/O network servers in a small multicore environment. Though they compare event and stage architectures within their database, they omit to compare them with the thread-per-connection model. They also notice biais in their methodology as the client and the server are run on the same machine, leading to an execution without any actual network I/O, and impacting the scheduling of the server. Such results are difficult to apply to Web servers in our context.

VI. CONCLUSIONS

We carried out a thorough comparative analysis with extensive experiments that bring new insights on current limitations concerning the scalability of the three main models used for implementing Web servers on multicores.

Unlike the monocore case where the thread-based, eventdriven and stage-based implementations are known to exhibit very different performances, surprisingly, we show that the situation is significantly different in the multicore setting. First, at 4 cores, the thread-per-connection implementation naturally outperforms original event-driven and stage-based ones in our case. Careful use of NCOPY configurations can improve the performance of event-driven and stagebased implementations, thus balancing the performances of all implementations. Second, When the number of cores increases, a point can be reached from which the different programming model's implementations tend to show very similar performances. Our experiments show that this point is already reached at 8 cores. Specifically, we show that at this threshold, all implementations of a programming model run into the same problematic memory limitation: a saturation of the address bus caused by the cache coherency protocol.

To the best of our knowledge, the fact that the different Web servers implementations, which reflect the main three programming models for data servers, tend to exhibit the same performance limits when increasing the number of cores is a new result. Furthermore, our experiments shed light on the nature of this bottleneck originating from the cache coherence protocol. Our experiments confirm the importance of tuning the operating system prior to tuning the Web server in order to bring the performances to their full potential, which we believe would be true for every I/O intensive application. Finally, we show that deployment configuration of a Web server should be done regarding the underlying hardware, and more precisely the memory architecture.

We believe that these contributions provide important insights for the further development and deployment of scalable data servers. Some of the possible solutions for better scalability of data servers could take place in hardware, by modifying the memory behaviour. More precisely, one could change the cache coherency protocol. On manycore architectures, another approach could consist in having only a local per-NUMA-node memory consistency and no hardware global memory consistency. This behaviour has been adopted with the new Intel's SCC prototype [START_REF] Van Der Wijngaart | Light-weight communications on intel's single-chip cloud computer processor[END_REF]. This will obviously result in huge changes in software development, if this solution becomes mainstream.

An interesting direction for future work consists in conducting similar investigations for NUMA architectures, since our preliminary experiments in this direction show that the cache coherency protocol also greatly affects scalability on NUMA 24-cores machines.

Figure 1 .Figure 2 .

 12 Figure 1. Performance comparison of the three servers at 1 core.

Figure 4 .

 4 Figure 4. Scalability of the 3 Web servers.

Figure 5 .

 5 Figure 5. Data and Address bus usage.

Figure 6 .

 6 Figure 6. Scalability of the 3 Web servers including NCOPY configurations.

SPED: Single Process Event-Driven

SYmmetric Multiple Process Event-Driven

there is an event MPM but it is still based on threads and does not uses the event-driven programming model.

The counters used here are named RESOURCE STALLS.* for Intel Core2 Microarchitecture.

Reservation stations permit the CPU to fetch and re-use a data value as soon as it has been computed, rather than waiting for it to be stored in a register and re-read. From http://en.wikipedia.org/wiki/Reservation stations.


Judshylqh Ri

Ploghzv O Djdlqvw

Naud

A Fofack-Kitio

B Leger

:RUNIORZ PRGHOOLQJ IRU H[SHULPHQWLQJ D GHFLVLRQ V\VWHP RQ SURWHFWLRQ

Keywords: Formal Modelling, Decision Support Systems, Crop Protection

Works initiated in 2001 by our partners phytopathologists at INRA Bordeaux led to the design of a decision system against both powdery and downy mildews of grapevine, which has been named "GrapeMilDeWS", in French "POD Mildium". GrapeMilDeWS is decomposed in 7 stages distributed all along the vegetative season. Each leads basically to two decisions made at the plot scale: whether or not to spray against each of the two diseases. Our contribution to system design has been on knowledge elicitation and formal modelling, with Statecharts. Statecharts describe processes with states and events, and are a formal construct built upon finite state automata. Details and complex time behaviour can be described thanks to hierarchy and concurrency mechanisms. The modelling was undertaken in order to produce a fully explicit and logically consistent decision protocol, so that many users would test it on many different plots, in different regions. The protocol now exists in a written form and has been tested on a network that has grown up to 35 plots in 2009.

Experimenting on a such a large scale, and getting back data and knowledge from this, causes numerous new challenges: (i) the decision system has to be robust to various conditions, while avoiding two loopholes: too much flexibility in the specification with risk of inappropriate implementation, or too many details (ii) the data to collect are numerous and include weather forecasts that are evolving by nature and need to collected in a timely manner; (iii) people involved are numerous: regional disease risk analysts, decision-makers for each plot, advisers who provide assistance to decision-makers and check conformance of decision to the original protocol.

We have thus undertaken to develop an experimentation support system that is based on workflow nets by van Der Aalst (YAWL framework). Workflow nets are derived from Petri nets, which like Statecharts are based on processes with events and states. The emphasis of Petri nets is on management of resources, represented by tokens, and control of concurrent process. With workflow nets, tokens represent cases to handle. The workflow system allows to manage processes and associated data in a consistent manner. The paper is about how GrapeMilDeWS, which we call a Decision Worklow, is being implemented in YAWL. The advantages of workflows nets for this application are discussed in regards to alternatives like Statecharts and Colour Petri Nets.

Introduction

In 2001, phytopathologists at INRA Bordeaux undertook to design and experiment a series of guidelines, which they called "decision rules", to handle grapevine diseases. This work was started within the French research network initiative on Integrated Crop Protection (or Integrated Pest management -IPM). One of these "decision rules" concerned management of downy mildew, another concerned powdery mildew. Both were designed as crop protection strategies with low fungicide input and significant information input from surveys in the plot. For downy mildew, other input data were weather forecasts and local bioclimatic risk. In 2005, they drafted new guidelines for managing both diseases in the same decision process. Combining the reasoning about downy and powdery mildews is consistent with practices of growers, who often mix specialties against both diseases in the same spraying operation. We started in the same time to collaborate to this research with computer and automation modelling techniques [START_REF] Léger | Recueil et Formalisation de procédés experts pour conduire une protection intégrée du vignoble[END_REF]. The modelling work had three purposes: facilitate the design of a decision process, check consistency and completeness of the design, ease communication between designers and people in charge of experimenting the decision process.

The result of this collaboration is GrapeMilDeWS, where DeWS stands for Decision Workflow System and GrapeMilDeWS stands for Grape Mildews DeWS. GrapeMilDeWS is alternatively named "POD Mildium" in France. The elicitation of knowledge for GrapeMilDeWS with the modelling language Statecharts is reported in (Léger, 2009). The resulting model is explained in detail in (Léger et al, 2010a).

The purpose of this paper is to explain why and how to move from a DeWS modelled in the Statecharts language to a management system for this DeWS, based on the workflow language YAWL (for Yet Another Workflow Language; van der [START_REF] Van Der | Modern Business Process Automation -YAWL and its support environment[END_REF].

Decision Workflow

GrapeMilDeWS is about how to decide when to spray and when not to spray for powdery and downy mildews of grapevine. These diseases are polycyclic: untreated, the pathogen agents perform a number of contamination-latency-activity-sporulation and further contamination cycles during the season. Infecting leaves and young berries, they can potentially destroy the yield of a year. Roughly said, the current infections cannot be really cured, and the way to break or slow down the cycles is to spray preventively to further contaminations and infections. Yet, there is social demand in favour of diminishing the quantity of sprayings [START_REF] Léger | Contribution of formal modelling and field experiment to leverage knowledge and expertise for designing crop protection guidelines[END_REF][START_REF] Bonicelli | The challenge for precision spraying[END_REF]. Optimising the spraying process itself in order to get all fungicide on target, and according to the quantity of vegetal to protect, is indeed relevant. Besides, the potential savings in quantities sprayed, by adapting dosage and timing of sprayings, is very much dependent on clever tactics. Let us illustrate this by sample information about each disease.

Tactical ingredients for managing the mildews

Once primary contaminations have started, the propagation of downy mildew within a plot is due to rainy events. Each fungicide is labelled with an Active Period (AP) in days. This duration is calculated after normalised trials where treatment is repeated periodically. In fact, most products do not have a constant efficiency during this Active Period. One obvious reason is that vine is growing. Systemic products dilute. So, for a heavily contaminating rain, there is better protection if the previous treatment is not at the very end of its Active Period. Choosing the appropriate timing for spraying according to rain forecasts is thus a useful tactical ingredient for managing downy mildew.

As for powdery mildew, the number of contaminations on each cycle is dependent on the number of previously infected and sporulating sites. The dynamics of typical epidemics follow "logistic curves". It is therefore quite obvious that these epidemics are more easily managed by early actions. Furthermore, it has been shown by experiments that early epidemics are often the most severe. Yet, one has to optimize quantities and define when and how much to spray. Spraying too early may be a waste of chemicals and spraying too late may reduce or destroy the yield. Indeed, early symptoms of powdery mildew are located on the rear-side of leaves and very inconspicuous (with the exception of the "flag-shoots" for certain cultivar like Carignan). The strategy of GrapeMilDeWS is to spend observation time in fields by checking a number of leaves, twice before flowering as the flowering period is the most critical for the yield. Tactics corresponds to the careful positioning in time of observations, sampling methods and thresholds, in order to discriminate best the cases of low epidemics from the severe ones [START_REF] Léger | An expert based crop protection decision strategy against grapevine's powdery and downy mildews epidemics: Part 1) Formalization[END_REF].

Describe tactics by sequences of tasks and information events

The timeline for describing the tactics for crop protection has two clocks. The first follows the annual calendar in days, because the Active Periods are specified in days, and the resources, human as well as equipment, are managed on this basis, and so are the weather forecasts. The second clock provides the phenological status of the vine, that is the mediane CIGR-Ageng 2010; International Conference on Agricultural Engineering, 06-08 Octobre 2010, Clermont-Ferrand growth stage of vineyard. This clock tics from bud-break to ripening and maturity, via the critical and short period of flowering. The designers of GrapeMilDeWS have chosen to breakdown the season in 7 management stages, where each stage leads to at most one treatment per disease. Within each stage, there are tactics to appropriately place in time sprayings and information retrieval according to indicators. This is why we chose Statecharts [START_REF] Harel | Statecharts: A visual formalism for complex systems[END_REF] for eliciting and modelling GrapeMilDeWS (Léger, 2009). The hierarchical construction provides abstraction features. It is possible during one interview to focus on one part of the Statecharts or another, to enhance details progressively during the series of interviews. The diagrams depict clearly both sequential and logical aspects of the process, as shown in the example of stage 0 on Figure 1. The original exhaustive set of Statechart diagrams of GrapeMilDeWS as of 2007 can be found in [START_REF] Léger | Recueil et Formalisation de procédés experts pour conduire une protection intégrée du vignoble[END_REF]. About notations for transitions (arcs from one state to another) in Figure 1, please note that represents variable assignment and is the equality operator. The path that is taken depends on two variables ,/0 and 0, which have qualitative values (integer or boolean codes). It also depends on the occurrence of two events: an update in ,/0, and forecast of a rain. ,/0 is about risk of downy mildew estimated in the area, 0 is about the presence of downy mildew spots within the plot under control. It is worth noticing that the GrapeMilDeWS design is cycle-less, which makes the enumeration of possible behaviour patterns straightforward. The system however includes implicit poling loops which are external to the core statechart: i.e. routines which monitor ILM changes and rain forecasts. In stage 0, this affects only the two "ZDLW" states. It should also be noticed that VWDJH , which is a super-state can be terminated by an event at upper level that provokes change to next super-state. For example, if downy mildew has been found in the plot (which can only happen if >,/0 5,6.@ is true once), then the decision system would stand in the ZDLW UDLQ state. If the checking of phenology (another implicit monitoring) shows that C1 should be performed because there are more than 5 leaves unfolded, then the ZDLW UDLQ would be cancelled as a consequence, and no spraying would be done in stage 0. GrapeMilDeWS had been modelled with the experts checking the statechart diagrams. The modelled was then verified against the actual past decision behaviour of experts, both qualitatively [START_REF] Léger | Experimenting statecharts for multiple experts knowledge elicitation in agriculture[END_REF] and quantitatively [START_REF] Léger | Contribution of formal modelling and field experiment to leverage knowledge and expertise for designing crop protection guidelines[END_REF][START_REF] Léger | Recueil et Formalisation de procédés experts pour conduire une protection intégrée du vignoble[END_REF]. Once it was confirmed that the model was the best expression of GrapeMilDeWS that was available, it was deemed the official specification of the system and from then on the norm to refer to when communicating all the decision logics and processes between the expert designers and the number of people who would apply GrapeMilDeWS in different plots of different regions. As explained in [START_REF] Léger | Contribution of formal modelling and field experiment to leverage knowledge and expertise for designing crop protection guidelines[END_REF], the performance and robustness of this decision system needs to be evaluated through field experiments. Yet, besides the core decision system, there was also need to document the testing protocol: plot choice, sampling methods in the field, data to collect, and protocols to assess quality and efficacy of the protection. It was then decided to derive tree structures of quasi-natural language statements from the Statecharts, one tree for each stage. This transcription could then be included into the testing protocol. The "no-loop" feature and the decomposition in different stages over the season of the core model greatly eased this work. A sample of this transcription process is given in table 1. Note that the "ASAP" (As Soon As Possible) for spraying of Statechart has been replaced by a "before rain" statement which is more functional. Generally speaking, the original reactive system assumption [START_REF] Léger | Contribution of formal modelling and field experiment to leverage knowledge and expertise for designing crop protection guidelines[END_REF] of common Statecharts was replaced by explicit deadlines (rain events, duration related to activity period of products). The modelling of time deadlines, or >GDWHPLQ GDWHPD[@ time periods in which an action should be performed according to the protocol, can be achieved by timed flavours of discrete event systems such as timed automata or timed statecharts.

Stakes of GrapeMilDeWS experiment

The network for experimenting GrapeMilDeWS has been continuously growing since 2007. It included more than 20 plots in 2008, and 35 plots in 2009 [START_REF] Naud | Modelling and experimenting crop protection decision workflows, some lessons from GrapeMilDeWS research[END_REF]. Since 2008, the experiment is based on a protocol document introduced above, and which includes a tree-structured written version of GrapeMilDeWS (denominated hereunder "tree").

Yet, a few cases have shown that stage 0 as of 2007 should be ameliorated, at least for early and quick epidemics of downy mildew (e.g. some cases in 2008 in Bordeaux region). A modification about powdery mildew management was also introduced in stages 0, 1 and 2. As a consequence, because GrapeMilDeWS describes precisely the appropriate timing of actions, the specification and its protocol transcription grew in size. For instance, stage 0 could be translated in 2008 in just 7 lines, (as seen in table 1) and grew to be 28 lines long in 2010. The new details are hereunder exemplified in table 2. The changes in stage 0 did propagate need for change in stage 1, to account for example of the remaining protective activity during stage 1 of an eventual spraying during stage 0. In 2008 the protocol's stage 1 was 28 lines and has grown in 2010 to be 97 lines long. It has become more tedious for people in charge of testing to follow the decision procedure from the protocol. The tree for certain stages like stage 1 contains details that are necessary in order to guaranty the completeness and consistency of system's logics but which may have little use except in special circumstances.

The design and evolution of GrapeMilDeWS, and probably of any Decision Workflows (DeWS) for other pathosystems, raises contradictory concerns. The initial design should have a simple structure in order to be discussed between experts, to trigger innovative idea and foster creative risk management. The reasoning principles and the requirements should be understood by people who test the DeWS. The DeWS should cover situations with intermediate epidemics, as well as cases with low or strong dynamics. Yet, to be operational, it should provide some time flexibility, with well-defined limits. Finally, it should be robust to special circumstances, and be sufficiently adapted to many of the various bioclimatic and terroir conditions found in France.

We believe that the main cases, the most frequent configuration, should be outlined in a natural language protocol document. The complete specification, with the finer details and time constraints, needs to be implemented into a workflow management system. This is reason number 1 for implementing GrapeMilDeWS in the YAWL framework. Besides providing the guidance and calculation to choose the right decision path, the program should allow user to make anticipations, make these persistent in the system as provisional decisions, and revise the latter according to changes in resources availability or weather forecasts. The user should also be able to store comments in the system, for his own use or feedback to DeWS designers.

The second reason for implementing the DeWS with YAWL is the need for collecting data about the tests for later analysis. Without a support program for GrapeMilDeWS, the data have been collected in electronic forms, and aggregated later. This makes work of people testing the DeWS partly redundant, because they have to gather information to build the decision, and then store this same information, with all details such as evolution of rain forecasts, in electronic forms. Systems dedicated to workflow management seamlessly integrate procedures, web services and databases.

Last, collecting numerous test data about GrapeMilDeWS in many places has much interest beyond GrapeMilDeWS itself. Data about non-treated plots, either for epidemic studies or for crop health vigilance, are available in many regions. Yet, there is currently a lack of data about plots with few or very few treatments. Data from GrapeMilDeWS experiment could serve other experts to design their own candidate DeWS. They should contribute to practical epidemiological knowledge, with characteristic facts for each period of the season.

From decision procedure to workflow

Concurrent processes

The table 2 shows the 2010 version of the transcription of stage 0. Most details are related to the case of one important cultivar of southern east of France. More important to our point about concurrent processes: it can be noticed that pre-scheduling of important dates such as one that ends stage 0 (C1) has been mentioned. This fixes a date for which concurrent monitoring processes such as rain forecast and updating ILM can be ended. With the tree structure, concurrency of such processes can only be suggested by appropriate terms. The Statechart (Figure 1) insisted on the preferred sequence: first check ILM, then rain forecasts, after having done a C0 survey on the plot. This C0 survey is no longer part of the protocol. A few cases in 2008 suggested that this optional survey could be counter-productive. If we ignore the case of Carignan, Stage 0 is meant to handle early downy mildew epidemics without forcing to schedule the C1 survey (survey of both diseases) too early. In stage 1, the result of C1 for 0 can take 3 values: 1,/ /2: +,*+. Both conditions >,/0 5,6.@ or >0 /2:@ trigger the same pattern in stage 1: protect grapevine of the next rain that could spread contamination. Depending on manpower, the scheduling of plot survey C0 could delay such an appropriate pattern, in case of quick and strong epidemics, so it was discarded and replaced by careful estimation of ILM.

The implementation of a software support for experimenting GrapeMilDeWS requires that the concurrent processes are checked with the user and synchronised appropriately. The YAWL language has synchronisation mechanisms with formal semantics and graphic symbols. The Event Process Chain (EPC) schematics were designed to specify business process specifications, with semantics that were initially not completely formal (van der Aalst et al, 2010). In order to prepare the modelling in YAWL, we sketched the processes with EPC like schematics, using abbreviated quasi-natural language statements. The result for stage 0 is given in Figure 2. In Figure 2, it can be seen that monitoring for rain and change in ILM are concurrent processes. One can also check the pattern "schedule a decision deadline (action planned, like survey or spraying, or reference phenological stage)" THEN "monitor till this deadline". The monitoring will end before this deadline if an event occurs and conditions for action are verified. This pattern can be found in a number of stages of GrapeMilDeWS.

Roles in a multi-actor process

The workflow is a flow of work within an organisation. The decision workflow is related to actual physical and human resources through information need about results of plot surveys, acknowledgment about achievement of scheduled actions like spraying or surveys, updated ILM information with a forecast horizon that also depends on resource management, updated rain forecasts. It does make sense that several persons will receive work items to do and information to report, according to their role in the organisation. A decision workflow is similar to any workflow in that sense. Furthermore, when it comes to experimenting the decision protocol in a network of plots in different regions, some roles concern decision about several plots or giving advice to the whole network. More structure is then needed.

To manage one plot, the following roles have been defined for implementing the worklow: Manager of downy mildew bioclimatic risk (ILM manager); Manager of crop surveys who For managing the whole network, other roles are: Expert adviser about the decision protocol (mainly, its designers or people with extensive experience and critical analysis on the decision protocol); local adviser; data analyst. Besides, the managers of ILM and crop surveys often have several plots under supervision.

Defining precise roles helps to set up easily the workflow for a given organisation, by affecting the roles to the different people participating. Each user of the system has access to a list of work items (one work item is an instantiation of a task of the workflow) that are to be done. YAWL allows defining if a work item should be assigned each time "manually" by an administrator to a given person or automatically proposed to a group. In the latter case, once a user starts one item, it will not appear in the to-do list of the others.

Revision of decisions

Within the management system of the decision workflow, there is no assumption that the decisions of treatment are immediately and automatically applied. This is replaced by the following mechanism to ensure best application of the decision protocol. When the decision manager calculates with the system that a spraying should be performed, the spraying decision receives the status "scheduled". A special process monitors if the scheduled sprayings have been done and gives them this status when it is the case. While the decision is still in the "scheduled" status, it can be aborted or re-scheduled by the decision manager. This can be important for example when adapting to sudden change or precision in weather forecasts, or when a spraying initially targeted to "powdery mildew alone" should be revised to target both mildews. The workflow management system will let the crop manager know if the deadline of a scheduled treatment has passed and no "done" acknowledgement has been given for this treatment.

Weather forecasts and ILM information also can be revised.

Workflow Architecture

The three tier nature of the YAWL system is detailed in (van der [START_REF] Van Der | Modern Business Process Automation -YAWL and its support environment[END_REF]. The core of the system is the YAWL engine. The designer of the workflow will upload the process model onto a server which runs this engine. The specifications are created using a dedicated graphical YAWL editor. As seen above, the workflow includes the "control flow logics" which is created with the graphical editor. The workflow also includes an "organisational model" which will handled by the YAWL engine as well. Finally, the data that support this "control flow", which are inputs, state variables and outputs of the workflow, are specified in an XML schema.

For workflow execution, the YAWL system provides basic user interfaces calculated from the workflow. Although it is not included in the design environment, the architecture makes it possible to use dedicated web-interfaces for the users, which will be developed separately.

Conclusion

The implementation in a workflow management system of the GrapeMilDeWS was an obvious objective so as facilitate extensive testing of this decision protocol, and harvesting the test data in the same time. We have detailed what is at stake. We also have shown the importance of concurrent processes and timing details, which are more easily managed with the assistance of a workflow management system than by reading a potentially complex hierarchy of statements written in a document.

Yet, the workflow for testing the decision protocol is a more detailed model than the model of the abstract decision protocol itself, which we will call "core model". The pragmatic choice that we made at this stage of this research is to complement the original core model by scheduling and revision processes, which are not formally separated of this core. Yet, we have seen that the core model is susceptible to be enhanced thanks to feedback provided by testing. The testing workflow will have to be maintained accordingly.

Figure 1

 1 Figure 1 Sample from GrapeMilDeWS: stage 0

  Super-state: stage 0 Super-state: Downy mildew in plot to handle Super-state: Downy mildew in plot to handle check[leaves have started to unfold] super-state CIGR-Ageng 2010; International Conference on Agricultural Engineering, 06-08 Octobre 2010, Clermont-Ferrand

•

  Start : bud-break, first leaf unfolded Quit : 5-7 leaves unfolded. Goto plot survey C1 provided security delay if there was a spraying Procedure : Schedule date of plot survey C1 (date code : D(C1))• Watch-out ILM (daily if possible) • Watch-out rain forecasts • Case of Carignan cultivar if powdery mildew flag-shoots observed year before o Estimate possible evolutions of ILM till stage 5 leaves unfolded o If ILM should stay NO_RISK till stage 5 leaves unfolded Schedule a treatment against powdery mildew (date code : D(T0)) preferably at stage 3 leaves unfolded and latest stage 5 leaves (Re-)schedule D(C1)) accordingly (delay for going in plot after treatment) Perform the treatment according to schedule (see above) o Otherwise: if ILM susceptible to reach RISK (ILM init to NO_RISK on stage0 start) Schedule a treatment against powdery mildew (date code : D(T0)), stage 5 leaves latest (Re-)schedule D(C1)) accordingly (delay for going in plot after treatment) On occurrence of ILM reaching RISK • If rain forecasted before D(C1) o Perform a mixed (downy/powdery) treatment before this rain • Otherwise (no occurrence of rain forecast before D(C1) o Perform the treatment powdery against powdery mildew as scheduled If no such occurrence of ILM reaching RISK • Perform the treatment powdery against powdery mildew as scheduled • Other cultivar cases or Carignan without flag-shoots observed year before o On occurrence of ILM reaching RISK If rain forecasted before D(C1) • Perform a treatment against downy mildew before this rain Otherwise (no occurrence of rain forecast before D(C1) • End of stage without spraying o If no such occurrence of ILM reaching RISK Keep checking ILM and rain forecasts till D(C1) When D(C1) occurs • End of stage without spraying

Figure 2

 2 Figure 2 Sample informal EPC of GrapeMilDeWS: stage 0

  needs one event/condition) CIGR-Ageng 2010; International Conference on Agricultural Engineering, 06-08 Octobre 2010, Clermont-Ferrand reports about execution and results of crop surveys; Crop Manager who reports about execution of scheduled spraying; Decision manager who takes and revise decisions.

Table 1 Sample from GrapeMilDeWS written protocol as of 2008: stage 0

 1

	Stage 0

• Watch-out ILM (daily if possible) • If ILM goes positive (ILM = RISK) and as soon as this happens o Proceed to plot survey C0 (downy mildew) (Sampling Protocol of plot Survey omitted) o If M result of C0 is positive (M = PRESENT) Watch-out weather forecast and wait a rain is forecasted If rain is forecasted • Spray against downy mildew before date of this rain

Table 2 Sample from GrapeMilDeWS written protocol as of 2010: stage 0

 2

CIGR-Ageng 2010; International Conference on Agricultural Engineering, 06-08 Octobre 2010, Clermont-Ferrand


Antoine Mazières
email: antoine.mazieres@gmail.com

Samuel Huron
email: samuel.huron@cybunk.com

Toward Google Borders

Keywords: ACM Classification H, 5 Group and Organization Interfaces: Web-based interaction Digital humanities, Digital Studies, Human Factors, Cultural Trends, Autocompletion, Suggestion, Web, Reflexivity

Figure 1. The three most popular suggestions on Google Search for the query "Why society" represented on a world map (suggestions in red).

Introduction

A great amount of information is produced by the use of web search-engines, allowing whoever possesses this data to know who searches for what, along with several characteristics about each user (location, time, device, etc). The analysis of these logs allows for improving the user experience by suggesting or automatically completing search query. For instance, a user of Google Deutschland's search engine who queries "how to cook" will learn that the most associated query with "how to" on google.de is "how to save a life". Query suggestion has several purposes, among them less typing, catching mistakes or repeating frequent searches. Additionally, suggestion might induce serendipity through surprising or complementary propositions.

These suggestions reflect the most popular associations between words and letters. This happens within a specific group into which users are categorized, e.g. by country, interest, search history. It gives an immediate feedback to the user about the search of others users within this group, or subset. The user reflects his query to a greater number of similar queries that reveal a common behaviour among the specific set of users to which he is identified. This informations enables the user to reverse-engineer the behaviour of this subset, by revealing its most common query. For instance, the French media compared suggestions on Google France to other domains and noticed the specific suggestion of "juif" (the French word for Jew) for queries about public persons [START_REF] Anizon | Et franc ¸ois hollande, il est juif ? Telerama[END_REF][START_REF] Foucart | juif", une requete très franc ¸aise[END_REF]. Questionning suggestions reveals cultural facts about the users from which the suggestions are produced and the learning and sharing of this information is one of the possible uses of search engines.

In this paper we argue that multiplying and combining the possible sub-sets of users from which suggestions are made, enables unexpected observations that could lead to new insights in fields such as journalism, ethnography, sociology, political science, among others. After identifying the Top Level Domains (TLD, e.g. .fr, .com, .de, .in) as a sub-set used by Google for providing its suggestions, we created Zeitgeist Borders (ZB), an interactive visualization of all suggestions made to all sub-sets, allowing a greater capacity of inquiry for the user.

Previous work

Query completion and recommendation systems are a widely studied topic in several domains of computer science such as database technology [START_REF] Baeza-Yates | Query recommendation using query logs in search engines[END_REF][START_REF] Deshpande | Adaptive query processing[END_REF], information retrieval [START_REF] Magennis | The potential and actual effectiveness of interactive query expansion[END_REF][START_REF] Nemeth | Evaluation of the real and perceived value of automatic and interactive query expansion[END_REF][START_REF] Tan | Term feedback for information retrieval with language models[END_REF] and Web [START_REF] Zhang | Mining search engine query logs for query recommendation[END_REF].

However, less research has been done about using this type of system to study cultural trends at a world scale. Google Zeitgeist [START_REF]Google zeitgeist[END_REF] shows the most common requests over a one year period and provide an interface to explore this topic over a world map. Google Trends [START_REF]Google trends[END_REF] is a webservice providing trends on a user defined query relative to the total search-volume distributed over the world. Baram-Tsabari et al. [START_REF] Baram-Tsabari | Exploring new web-based tools to identify public interest in science[END_REF] studied the potentials and limitations of Google trends. Also, Ginsberg et al. [START_REF] Ginsberg | Detecting influenza epidemics using search engine query data[END_REF] presented a method to analyse search query logs to track influenza-like illness arround the world, this technique being now provided as a service called Google Flue [START_REF]Google flue[END_REF]. Specifically related to Google suggestions, Baker et al. [START_REF] Baker | Why do white people have thin lips? google and the perpetuation of stereotypes via auto-complete search forms[END_REF] focus on racist, sexist or homophobic suggestions to argue that the Google Autocomplete algorithm can reinforce stereotypes.

A Reverse engineering approach to Google Autocomplete

Google Autocomplete (GA) [START_REF]Google autocomplete[END_REF] is the name of the suggestion system used by Google since 2008 and enhanced in 2010 by Google Instant [START_REF]Google instant[END_REF] making suggestion available on-the-fly while the user is typing.

While several publications describe it [START_REF] Bialczak | Sending hidden data via google suggest[END_REF][START_REF] Harik | Automatic completion of fragments of text[END_REF], the system internals are not available to the public. For this reason, we decided to use a reverse-engineering approach to understand if different suggestions are served to different users and to understand the criterias for those differences. A reverse engineering approach is defined, in this case, by the analysis of an existing obfuscated system to identify its behaviour and create representations of it in a simplified form for a purpose [START_REF] Chikofsky | Reverse engineering and design recovery: a taxonomy[END_REF].

We listened to the network traffic of a computer while queries were being typed in the search box of a Chrome browser. This revealed an HTTP request 1 transmitting what is being typed. A response occurs, indicating the suggestions to be made (Fig. 2). The absolute URL of the HTTP request transmit the query along with 3 pieces of informations about the user: his browser, his query and which Google's domain, i.e. TLD, is being used. Top Level Domains (TLD) are assigned by an American NGO (ICANN) and most of them refer to a specific country, such as .fr refers to France, .de to Germany or .in to India. We reproduced a same query over all supported TLDs supported by Google 2 referring to a country and observed differences among the responses. As a simple measure of these differences, we quantified the occurences of every first suggestion received by typing each letter of the Latin alphabet among all TLDs. On average, approximately 30% of TLDs (57 over 186), were served with the exact same first suggestion for each letter. This means that an average of 72 different first suggestions are distributed over the other 128 TLDs. For approximately 70% of Google's domains, a unique first suggestion was shared by only two of them 3 . While this statistical inquiry does not allow us to deduce that this ratio is true for all queries, it is sufficient to affirm that TLDs, and GA is a system thats return the top matching queries as suggestions to queries being typed by users. Through our analysis of this system, we have shed light on the fact that suggestions differ from one user to another, including on the base of the TLD requested. Consequently, TLDs are a significant sub-set for Google's suggestion system, and for every query made, users are shown the most common associated Google search queries from their country.

Tool design

We built a tool enabling users to map, worldwide the suggestions made by Google for a specific query. Through local suggestion, the user is given some knowledge about the other users with whom he is associated to. Given that GA associates users by the domain they use, those domains define the borders within which this knowledge is acquired about other users. Our tool allows one to abstract himself from these borders and acquire knowledge about any possible sub-set or combination of sub-sets of users.

Data is collected by the user defined query on every Google domains. We collect completions over 186 TLDs. Zero to four completions are received after each of our requests, as a list of string ordered by relevance. In order to scale the local ranking of suggestion to a world-wide view, we defined a score for each suggestion. A global ranking is built by making the sum of those scores for each similar suggestion over all TLDs. This score allow us to rank TLD suggestions at a world scale and let one knows wether suggestions are shared or not with other countries. Once collected, this data is stored and sent to the web interface.

By entering a query, the user get a list of all suggestions made by the search engine on all its domains, ranked by number of occurrences. As shown in Fig. 3, a mouse over a specific suggestion highlights the relevant countries on a world map. Also, a mouse over a specific country returns the suggestions made by the related domain.

Our software is called Zeitgeist Borders (ZB) and is released under the GPL [START_REF] Mazieres | Zeitgeist borders[END_REF].

Limitations Every query on ZB triggers as many queries on Google servers as there are TLDs. For example, six queries using our software causes over 1000 queries on GA's infrastructure. Tens of queries in a row cause the user's IP address to be banned from interacting with GA for a few hours. Such a limitation prevented us from collecting significant volumes of data for making statistical assumptions on the suggestion topology. However, with or without this limitation, important biases remain in the system:

• While Google is the most used search-engine on the web, its marketshare varies from one country to another. As an illustration, it has 97% of the market shares in Italy, Spain and Germany, while it is only below 40% of the market share in Japan, Russia and China [START_REF] Light | Search engine marker share around the world -q4[END_REF]. This means that the use of Google search is in several countries limited to specific regions, users or topics.

• English appeared to be the language the most suitable for collecting suggestion from every domain. However, focusing on this language in a non-english speaking country constrains the returned suggestions to specific users (i.e. English-speakers) or matters (e.g. international news).

• GA's presence varies among domain and over time, sometimes along with Google search. This has been true during our research for Cuban and Chinese TLDs.

• According to GA policies [START_REF]Google autocomplete[END_REF], suggestions are turned off for certain sequences of characters associated with, for example, racism or pornographic topics.

Observations

As previously stated, our research does not pretend to shed light on the suggestion topology and distribution, since acquiring a volume of data that would be statistically relevant was not possible. However, we believe it is still worth reporting qualitative observations to build assumptions of the interests of the approach prototyped by our tool. Within these boundaries, we collected all suggestions of all TLDs for several list of queries:

• Letters of the Latin alphabet. This list was used in to assert the TLD-based system behind GA.

• Interrogative pronouns followed by most common verbs or pronouns: what, where, when, how, who, why followed by is, are, was, I, he, she. This list narrows suggestions to general-purpose interrogative queries.

• Intuitive queries according to our experience using ZB. These are mostly derived from the previous dataset with some added words making references to concept, name or thing. This non-structured list allows us to report unexpected observations without a specific methodology of inquiry.

With the Latin alphabet dataset, we noticed a strong presence of American or British companies. A measure revealed that 56% of the three most popular suggestions for each TLD among all letters are names of brands or products from USA or UK. For example, "amazon" is served as first suggestion among 40% of all TLDs over the letter "a". This means that the majority of suggestions over a single letter are linked to a few companies from only two countries in the world. Beyond highlighting an interesting economical and political fact, a generalized measure of this phenomenon would allow plotting of a semantic market share of those companies over their letter.

Interrogative pronouns are fundamental components of questions, and therefore a query with these is usually a formulated question. Adding pronouns or verb narrow the range to a category such as time (based on tense used) or gender ("he" or "she"). For instance, "what if" returns the hypothetical condition the most tested by Google's users. Whether from worry, fear or curiosity, users ask mostly about "if god was one of us", "if money didn't matter" and "if there was no google". The pronoun "why" asks for the meaning or cause of a phenomenon, the most common being "why is the sky blue". By adding a subject we can learn for what meaning is queried about a specific gender. For example, questions asked about the male gender include "why he disappeared" and "why he doesn't call", while those about the female gender asked "why she buys" and "why she slap". Also, different questions for different levels of languages can be identified by adding elements making a grammatically correct formulation.

In that sense, being for she or he, "why does" returns "ignore me" and "love me".

Adding a concept to a pronoun-based query enable one to figure out what is mostly asked about this concept, or what other concept is linked to it. As shown in Figure 1, "why society" trigger a relation with complexity ("is a complex matter"), religion ("needs religion") and truth ("is wrong"). With names, ZB enables one to rank the popularity of a name and at the same time discover some elements of this popularity.

In that sense, among all the Josephs, Joseph Gordon-Levitt is the more queried, this for his "girlfriend" and his role in "batman".

The visualization offered by our tool through a world map allow one to immediately test combinations or comparisons of group of users. For instance, the query "how to" clearly draw the north/south political separation over the world, with "how to kiss" for the south and "how to tie a tie" for the north. Also, different sub-groups can be tested for similarities. For instance, if communities of language seems also to provide similitude in queries, some sub-categories seems more tied together than others. For example, France and French-speaking African countries are frequently highlighted together while other French-speaking countries are not.

Last but not least, paying attention to uncommon suggestions allow identification of users with very specific preoccupations. For instance, while most of the countries ask if "why kids are the worst", or "lie", India is the only one asking why they "vomit" and "don't eat".

Discussion and future work

We have shown how monitoring results brought by searchengine suggestions can provide insights of cultural patterns across the world.

Our system is bound by the TLD-based Google suggestion system that was the only one available when conducting our research. TLDs are usually tied to political or administrative entities that do not necessarily match coherent cultural or even linguistic communities. Unfortunately, finer-grained information, such as individual search history or any data stored by Google other services, is not readily available. Obtaining richer information about users would allow aggregation of suggestions into a larger number and more diverse categories.

Moreover, a larger-scale analysis would allow systematic analysis of the cultural differences between countries. For example, two countries could be compared based on the Spearman coefficient [START_REF] Spearman | The proof and measurement of association between two things[END_REF] between exhaustive ordered sets of suggestions. We are currently working on a system enabling one to perform enough queries on GA's infrastructure to do so and to statistically ground any technical or social assertion.

Conclusion

This paper explored the possiblity of using Google Autocomplete (GA) suggestions for tracking cultural differences over the world. The tool, along with its method and system, enables users to collect, process, visualize and eventually analyze these suggestions.It also helps users to reveal how the group he belongs to biases the suggestions returned. We argue that autocompletion could provide a broad possibility for trend and social analysis. To that end, we reported several unexpected observations. By releasing our code as open source we hope to open doors and help future studies in this field.

Figure 2 .

 2 Figure 2. Response to a HTTP request on GA

Figure 3 .

 3 Figure 3. User interaction example on Zeitgeist Borders

Acknowledgments

We would like to thank very much Julien Palard for his great contributions to Zeitgeist Borders and to the vision it empowers. Also, we thank Jean-Philippe Cointet, Christophe Prieur, Joaquin Keller, Dusan Misevic, Camille Delebecque and Jagoda Walmy for their feedback and reviews on our research. Last but not least, we are very grateful to the communities of Fabelier 4 and the Center of Interdisciplinary Research 5 for the great environment they created.