Javier Rojas Balderrama
email: javier.rojas-balderrama@inria.fr

Matthieu Simonin
email: matthieu.simonin@inria.fr

Scalability and Locality Awareness of Remote Procedure Calls: An Experimental Study in Edge Infrastructures

Keywords: Edge computing, Remote Procedure Calls, Message Oriented Middeware, Grid'5000, OpenStack, reproducible research

Cloud computing depends on communication mechanisms implying location transparency. Transparency is tied to the cost of ensuring scalability and an acceptable request responses associated to the locality. Current implementations, as in the case of OpenStack, mostly follow a centralized paradigm but they lack the required service agility that can be obtained in decentralized approaches.

In an edge scenario, the communicating entities of an application can be dispersed. In this context, we focus our study on the inter-process communication of OpenStack when its agents are geo-distributed. More precisely, we are interested in the different Remote Procedure Calls (RPCs) implementations of OpenStack and their behaviours with regards to three classical communication patterns: anycast, unicast and multicast. We discuss how the communication middleware can align with the geo-distribution of the RPC agents regarding two key factors: scalability and locality. We reached up to ten thousands communicating agents, and results show that a router-based deployment offers a better tradeoff between locality and load-balancing. Broker-based suffers from its centralized model which impact the achieved locality and scalability.

I. INTRODUCTION

Telecommunication operators currently push towards novel application deployments that benefit from the distributed nature of the infrastructures. A classical model for such infrastructures considers many sites (i.e., computing resources and storage capacity) along the path from the core to the edge of the network. Few milliseconds of latency may be registered between the core and the closest sites while longhaul communication may occur at the edge of the network. In this context, cloud-based applications can potentially be deployed across different geographically distributed sites. In a standard approach, parts of the application requiring lowlatency interaction with the end user can be placed close to the edge while the others can be placed closer to the core.

OpenStack 1 is largely used to build and manage cloud computing platforms. Nevertheless, the original design of OpenStack targets the case where a small number of large 1 https://openstack.org sites is the norm. In the aforementioned model, OpenStack would need to operate a large number of small sites. Hence, OpenStack control-plane agents (responsible for managing the virtual resources) need to be scaled-out and shifted into geographically dispersed locations. This new deployment model for OpenStack raises different challenges. First, the scalability of the internal management system. OpenStack is designed in an elastic manner: most agents can be replicated for loadsharing purpose. Elasticity defers the scalability challenge to the underlying database and communication middleware. Second, the geo-distribution of agents needs to be taken into account. It is an opportunity to provide a certain level of locality to the end-user. On the one hand, users expect lowlatency access to their application meaning the data path created for an application must remain as local as possible. On the other hand, the control traffic can also benefit from locality by keeping states (e.g., database) and inter-process communication also as local as possible. Thus, locality can reduce the completion time of requests by minimizing longhaul communication.

OpenStack control traffic provides a high-level Remote Procedure Call (RPC) abstraction and endorses different implementations: centralized broker-based implementations sit next to more decentralized brokerless or hybrid approaches such as those described in the AMQP 1.0 standard [START_REF]Advanced Message Queuing Protocol[END_REF].

This paper presents an evaluation of the RPC layer of OpenStack in a geo-distributed context. The study focus more precisely on:

• Scalability. What is the impact of having a massive number of communicating agents on the application and the underlying message bus? • Locality. What is the impact of the geo-distribution of the communicating agents, and how can it be mitigated?

The contribution of this paper is an extensive experimental evaluation of RPC and bus agents deployment in two different configurations: centralized and decentralized. This contribution is aligned to the efforts of the professional community of harnessing current deployment capabilities to edge infrastructures [START_REF] Garcia Lopez | Edge-centric computing: Vision and challenges[END_REF], [START_REF] Varghese | Challenges and opportunities in edge computing[END_REF].

The rest of the paper is structured as follow: Section II reviews the main criteria of the evaluation. Section III describes the metrics we focus on, and the framework we built to perform reproducible and automatized benchmarks in a geo-distributed context. Experimental results are presented and discussed in sections IV, and V. Finally, the paper ends with a conclusion and outlines future directions.

II. EXPERIMENTAL MODEL

Classical unicast RPCs (i.e., point-to-point) require a tight spatial coupling [START_REF] Eugster | The many faces of publish/subscribe[END_REF] of the client and the server (they must know each other) and a strong synchronisation (server should be listening for incoming communication). On a message oriented middleware (MOM), clients and servers may also declare their communication interest through an abstract target. This target allows agents to decouple the messaging entities using higher-level communication patterns like anycast and multicast. OpenStack agents use concurrently those three RPC patterns. They serve us as a reference for designing three evaluation scenarios:

• Anycast Scenario (AS) when a request is delivered to only one server interested in the target. • Unicast Scenario (US) when a request is delivered in a point-to-point fashion.

• Multicast Scenario (MS) when a request is replicated and sent to all servers interested in the target. The identification of above scenarios is the first step to break up the complexity of the evaluation. Indeed, as described in the next sections, there are different parameters that can influence a scenario's behaviour. We provide some background for each identified parameter, and we also state our choices for the evaluation.

A. Agents geo-distribution

RPC agents and bus agents may be deployed on geographically distant locations. This geo-distribution can force the messages exchange by communicating entities to travel over long-haul links. The different network characteristics of those links [START_REF] Nygren | The Akamai network: A platform for high-performance internet applications[END_REF] can result in a degradation of the application performance, or worse, application failures. The former may be mainly due to the introduction of latency in message transfers, and the latter may be the consequence of packet loss that cannot be handled by the application or the underlying protocol (e.g., TCP). In this paper we mainly focus on studying the impact of the geo-distribution of the agents on AS. Indeed in this scenario, the bus usually load balance the requests on the available servers. This strategy could be optimized to take into account the actual distance between the communicating entities. In US and MS the bus has to transfer the requests to a predefined set of agents, this defers any optimization to the initial agents placement.

B. Scenarios size

We evaluate the scalability by increasing the size of the scenario in terms of RPC agents, and the resulting number of transferred messages. We define the size in a different way for each scenario. The size of AS corresponds to the number of RPC clients and RPC servers. The size of US is the number of targets. Therefore, it increases proportionally the number of RPC agents: one client and one server for each target. Finally, the size of MS is only the number of RPC servers receiving the messages. In a realistic deployment there are more clients than servers. That is the case in AS while they are equal in US. Note that in MS only one client is considered.

C. RPCs flavours

A synchronous call blocks the client until the return value goes back to the client application. In some situations, blocking the client control flow is not required and the return value is backtracked to the client application once it is ready. For this reason asynchronous calls are often exposed in RPC libraries. The fire-and-forget pattern is a special type of asynchronous call where the client does not even need to receive the return value of the function. OpenStack specifies different RPC types including rpc-call and rpc-cast. The rpc-call is synchronous and the rpc-cast is fire-and-forget. Both types also differ on the delivery guarantee: rpc-call follows the at-least-once semantics whereas rpc-cast only offers the at-most-once. Moreover, a rpc-cast is likely dropped in case of congested traffic.

In our evaluation, RPCs flavours are tested separately. In OpenStack AS and US support both rpc-call and rpc-cast. MS only supports a special version of rpc-cast, namely rpc-fanout, to broadcast asynchronously a request to a set of servers. Note that the calling is more sensitive to the geo-distribution of the agents than casting because it needs waiting the server response. As a result, it pays twice the latency of the link between the client and the server. Additionally, more resources need being provisioned on the message bus to handle calls (e.g., return channel), so calls may consume more resources.

D. Bus topology

The aforementioned RPCs flavours can be implemented on different backends using different drivers. Most of the time, operators rely on a broker-based backend (e.g., RabbitMQ 2 ) as they are robust, and battle-tested drivers based on the AMPQ 0.9-x standard [START_REF]Protocol Specification v0-9-1, Advancing open standards for the information society OASIS[END_REF]. Nevertheless, the AMQP 1.0 [START_REF]Advanced Message Queuing Protocol[END_REF] defines routers as new type of intermediary. OpenStack supports both backends to implement the previously described patterns. In the following we discuss the deployment strategies implemented in our study.

Broker-based message bus: A broker is a general purpose MOM acting as an intermediary between the messaging entities. A broker stores (in a queue) and forwards messages, allowing a spatial and temporal decoupling between communicating agents. But in the context of RPCs communication, this decoupling is questionable as clients and servers must be synchronised. For scalability reasons, brokers can be clusterized into a big logical broker. RPC clients and servers interact with this logical broker while the load is distributed among different bus agents. In our study we refer to RabbitMQ, the de facto standard in OpenStack, as the reference broker implementation.

Router-based message bus: Routers can be organized in a custom topology and dynamically computes routes for messages. They are stateless and do not store messages. Therefore, routers require producers and consumers to be temporally coupled. Similarly to brokers, a router mesh can be extended by adding new routers and links to the original ones. We use Apache qpid-dispatch-router 3 as the reference implementation in our study.

In our evaluation, we consider two bus configurations: a RabbitMQ cluster, and a complete mesh of qpid-dispatchrouters. In order to embrace the edge requirements in terms of geo-distribution of the agents, we consider two possible deployments for the bus agents shown in Fig. 1: • Centralized deployment. The bus agents are deployed in the same latency domain (e.g., the same location with LAN connectivity). In this deployment long links are found between the RPC agents and the bus agents. • Decentralized deployment. In order to reach a better locality, the bus agents are pushed closer to the RPC agents. Therefore, links between bus agents become longer in comparison to the previous case. Note that RabbitMQ proposes federation as an alternative deployment model. This model has limited support for message routing and requires to statically configure the messages path accross the different brokers. These limitations make this model not applicable to the RPC implementation of OpenStack and thus is not considered in the current study.

III. TOOLS AND METRICS

We have developed the Ombt orchestrator, 4 an application to evaluate the performance of communication agents and RPC agents in synthetic edge configurations. Ombt orchestrator is based on two tools: Ombt and EnOSlib. The Oslo messaging benchmarking tool 5 (Ombt) uses the library of OpenStack for messaging 6 to measure the latency and throughput of RPC and notification transactions. EnOSlib [START_REF] Cherrueau | EnosStack: A LAMP-like stack for the experimenter[END_REF] is a high level library for deploying and executing applications, and collecting results in a distributed fashion.

Ombt orchestrator eases the management of the parameters described in section II. First, the geo-distribution of agents is emulated by means of traffic control capabilities offered by the Linux kernel's network stack. Second, given a size, it deploys any of the three scenarios. Moreover, clusters of brokers of any size and complex topologies of routers are supported. Experimental campaigns can be performed in an automatic manner across a (large) infrastructure with thousands of cores on various testbeds. Alongside the agents, a dedicated controller is deployed assessing system metrics by means of additional tools: Telegraf and InfluxDB. 7In fact, we identify two types of metrics: those from the application layer and those coming from the system. The leveraged applications provide metrics such as latency distribution and message rate. These metrics can be analyzed along with the potential execution errors raised by the applications. It is important to note that we differentiate two types of latency: the round-trip latency (a.k.a. RTT latency) and the one-way latency. The former is associated with RPCs of type rpc-call and it is the time taken from the client application to send the request and receive the answer from the server. It is measured exclusively on the client side. The latter is associated with RPCs of type rpc-cast and corresponds to the time for a request to go from the client application to the server application. Latency is thus measured both in the client and server application. In this case, a strict time synchronisation is required between the RPC agents. In terms of implementation that synchronisation is done with a dedicated NTP cluster. For the system metrics, we are specially interested in CPU and RAM consumption, active TCP connections and network traffic for all agents.

IV. RESULTS

Following subsections present the common experimental setup and results. We performed two set of experiments based on centralized and decentralized deployments of the bus agents as shown in Fig. 1.

A. Setup

All the experiments ran on the Paravance8 cluster of Grid'5000 [START_REF] Cappello | Grid'5000: A large scale and highly reconfigurable grid experimental testbed[END_REF] composed of 72 physical nodes, each having 16 cores and 128 GB RAM. Qpid-dispatch-router 1.0.1 and RabbitMQ 3.7.4 were deployed. Oslo messaging 5.35.0 was used as RPC library on Debian 9.3. The release version of ombt orchestrator was 1.1.1. This testing framework allows running experimental campaigns in a fully automated manner. A campaign corresponds to a set of combined parameters. For each generated combination a benchmark is run and several metrics are collected. For instance, Table I shows a set of parameters where 12 (2 call types×6 bus configurations) combinations of common parameters are combined with 6 agents configurations for each scenario, resulting in 72 combinations of parameters per campaign. Each combination is calibrated to run within 5 minutes with a timeout of double that time. If the timeout is triggered an execution is marked as failed becoming our service-level agreement (SLA). For the sake of conciseness in this paper, we only present a subset of all evaluated combinations.

B. Centralized deployment

In this set of experiments we consider a bus deployed in a centralized way (see Fig. 1 left). Bus agents are located in the core infrastructure. Two different experiments have been performed: a plain scalability study, and a variation in which RPC agents are pushed to the edge of the network.

1) Scalability study: The goal here is to observe the impact of an increasing number of RPC agents (or the targets depending the scenario) requests on the communication bus.

Parameters: Table I shows all parameters considered for these experiments. An execution campaign is associated to each scenario: AS, US, and MS. We consider a LAN connectivity between the bus and the RPC agents. In AS, the number of clients is increased to reach 10K. In parallel, the interrequest delay (pause parameter) is set to maintain a constant request rate on the message bus to 10K/s. 20K messages per second on the bus are generated (requests and return values are accounted for 2 messages) in rpc-call cases. This message rate is the estimated load of the periodic tasks (i.e., heartbeat) of 80K compute nodes deployment in OpenStack. Each client sends 300 messages (300K messages sent in total) to attain the same benchmark duration. Twenty servers are set to keep up all the request load. Then in US, the number of targets evolves as in the previous scenario to have a constant request rate and benchmark duration. Finally, in MS an increasing number of servers is set and only rpc-fanout calls are evaluated. Note that, in this last scenario, one request sent by the client generates 10K requests sent to all servers.

Results: Fig. 2 shows the boxplot for the three scenarios. Each one has a specific behaviour summarized as follows.

In AS, executions for configurations with only one bus agent never completed for more than 6K clients for brokers and 8K for routers as shown in Fig. 2a. It is due to the default maximum system limit of open file descriptors (16384) or the SLA. This effect is partially verified with the number of TCP connections in Table II. The driver implementation for brokers requires twice the number of connections than routers (i.e., one to send and another to receive). Concerning memory and processors consumption metrics. Brokers require a lot more resources compared to routers with ratios going from at least 9 to 17 times in case of RAM, and from at least 8 to 27 in case of CPU cores. Brokers have higher latencies for both messages types. In order to account a complete communication between agents, rpc-call requires at least twice the time. In general, both bus agents perform in the same way. The only difference is brokers report a bigger latency when the number of clients increases.

In US, results of both call types are more similar than AS (Fig. 2b). Since each target is assigned to one client and one server, the number of connected agents is twice the number of targets. Additionally, no extra queuing (in the broker case) nor buffering (in the router case) is expected for any target. Nevertheless, the single bus configuration suffers the same limitation as AS. The system metrics are not presented here but they follow the tendency of the AS scenario.

Finally, in MS (Fig. 2c), we observe that both bus agents support the communication pattern in all configurations. Note 1 -r a b b it m q -1 0 0 0 1 -r a b b it m q -2 0 0 0 1 -r a b b it m q -4 0 0 0 1 -r a b b it m q -6 0 0 0 1 -r a b b it m q -8 0 0 0 1 -r a b b it m q -1 0 0 0 0 1 -r o u t e r -1 0 0 0 1 -r o u t e r -2 0 0 0 1 -r o u t e r -4 0 0 0 1 -r o u t e r -6 0 0 0 1 -r o u t e r -8 0 0 0 1 -r o u t e r -1 0 0 0 0 3 -r a b b it m q -1 0 0 0 3 -r a b b it m q -2 0 0 0 3 -r a b b it m q -4 0 0 0 3 -r a b b it m q -6 0 0 0 3 -r a b b it m q -8 0 0 0 3 -r a b b it m q -1 0 0 0 0 3 -r o u t e r -1 0 0 0 3 -r o u t e r -2 0 0 0 3 -r o u t e r -4 0 0 0 3 -r o u t e r -6 0 0 0 3 -r o u t e r -8 0 0 0 3 -r o u t e r -1 0 0 0 0 5 -r a b b it m q -1 0 0 0 5 -r a b b it m q -2 0 0 0 5 -r a b b it m q -4 0 0 0 5 -r a b b it m q -6 0 0 0 5 -r a b b it m q -8 0 0 0 5 -r a b b it m q -1 0 0 0 0 5 -r o u t e r -1 0 0 0 5 -r o u t e r -2 0 0 0 5 -r o u t e r -4 0 0 0 5 -r o u t e r -6 0 0 0 5 -r o u t e r -8 0 0 0 5 -r o u t e r -1 0 0 0 0 driver -servers that servers do not require any response from the clients to accomplish the message communication, so there are less active TCP connections compared to the two previous scenarios. Although, the difference between brokers and routers in terms of latency is still present.

2) Locality study: Relying on a packet lossless network or a nonexistent latency is not realistic scenario in an edge configuration. The goal of this second experiment is to evaluate the RPC agents behaviour deployed at the edge under influence of a link delay and packet loss.

Parameters: Table III shows all parameters considered for the experiment. The delay and loss rate correspond to the network emulated between the RPC agents and the bus agents. The number of servers remains constant whereas the number of clients increases to generate different load on the bus. For all campaigns a cluster of three brokers and a complete mesh of three routers are considered. The results with more agents does not provide newer elements for discussion. Those results, verified in preliminary tests, are not included here. Only rpc-call messages were evaluated because the results of rpc-cast in the previous experiment did not show a clear difference between brokers and routers. That behaviour was also verified during the preliminary tests with delay and packet loss.

Results: Fig. 3 shows the boxplots of the message latency while varying the link delay, loss rate, and number of clients for both bus implementations (broker and router). We noticed the absence of application errors during all campaigns. It means that the underlying protocols or applications such as TCP or Oslo messaging manage properly the loss of packets. We also observed the introduction of packet loss only increases the inter-quartile range (IQR) because of retries of packet transmission. Latency in all cases is registered as expected according the parameters configuration.

In summary, a centralized deployment of buses may fit well in an edge environment paying the additional latency, slightly bigger with brokers. This configuration is appropriate in most situations where the bus configuration is transparent to the RPC agents because they work as a sole entity beyond the number of configured instances. Routers support better the request message load before crashing because of overload but the magnitude in both configurations remains the same. In contrast, in a centralized configuration there is no benefit of locality between RPC agents since all communications transit the core of the infrastructure where buses are located.

C. Decentralized deployment

In this experiment we consider a bus deployed in a decentralized way (see Fig. 1 right). Bus agents are shifted closer to the edge where RPC clients and RPC servers are deployed. This time, the goal is to observe the impact of the geo-distribution of all actors on the benchmarks completion while decentralizing the communication bus.

Parameters: Table III details all parameters considered for the experiment. The delay and the loss values are only applied between bus agents unlike Section IV-B2. RPC agents and bus agents are considered in the same latency domain.

Results: Fig. 4 shows, similarly to precedent experiment, boxplots of the message latency while varying the execution parameters. We first observe missing results corresponding to a violation of the SLA. Under the influence of delay and packet loss the broker internal communication became very unstable making broker agents crash. Conversely, no timeout violation was observed with routers. In such deployment the brokers scalability is greatly impacted by the presence of delay and loss. For instance, with no loss and high latency, only a limited number of clients were supported (less than 250 for 50 ms). In the same way, the impact on the scalability was bigger with higher loss. Routers did not suffer those problems: low latency (and thus high throughput) was always achieved. Note that, in this experiment, latency remains lower than the imposed between bus agents. Indeed, a router assigns a message cost to each possible link that leads to a server. The router then sends the message on the path achieving the least cost. Initially the cost associated to a remote server is higher than the cost associated to local servers. As the cost associated to a server increases with its load, some messages may be offloaded to remote locations. In proportion non-local delivery was rare in our experiments. As a rough estimate, an imposed message rate of 100 message per second leads to 90% of local delivery. This drops to 66% for 1 000 messages per second. In summary, the routing strategy makes the load-balancing locality aware. This explains why, in most cases, the latency perceived by the application is lower than the actual latency between the bus agents.

Figure 5 (left) provides a more detailed distribution of the latency found in brokers. The anycast target implementation in RabbitMQ leverages a single queue located in a specific bus agent (the agent where the first server was connected). A request from a client to a server can follow one of the three paths identified in same figure (right) leading to the three modes observed in the latency distribution. As a consequence, locality using a cluster of brokers only occurs for a small portion of messages. For higher loss, TCP re-emission may occurs leading to another modes to appear in addition to the three main identified.

In conclusion, decentralizing a cluster of brokers is only possible under small latency constraints as scalability is greatly impacted by bad network conditions. In decentralized scenarios, routers mitigate the effect of the geo-distribution of RPC agents by achieving a locality-aware load balancing. Messages can thus flow directly from the clients to the local servers. Additionally, as suggested by system metrics of the Table II also verified in this case, routers are lightweight and fit better the capacity constraints of micro datacenters at the edge. Fig. 4: Results of the anycast scenario in a decentralized deployment. Latency boxplots for bus implementations, number of clients, and link delay of rpc-call (top 0% loss, bottom 1% loss).

V. RELATED WORK

To the best of our knowledge, very few experimental studies have been conducted on MOM in a cloud context. In [START_REF] Sachs | Performance evaluation of message-oriented middleware using the SPECjms2007 benchmark[END_REF], and more recently in [START_REF] Dobbelaere | Kafka versus RabbitMQ: A comparative study of two industry reference publish/subscribe implementations: Industry paper[END_REF] the study of scalability focuses on raw messages throughput, latency and resource consumption. Those studies stick to a single datacenter use case. Even if our study is limited to OpenStack, it fills a gap by evaluating high level construction such as RPC and by evaluating the impact of having a massive number of geo-distributed agents. As observed in the previous sections, locality plays a key role in various domains. First, scalability by enabling parallel transaction handling among different bus-agents. This leads to decentralize the messages distribution while increasing the overall throughput of the application. Second, reliability by better isolating potential failures domains. A bus-agent is not impacted by a remote network failure since it can deliver message locally. This assumes RPC clients and RPC servers to be co-located. Co-location may not be a general configuration, so in such cases a centralized bus deployment may be considered. However, in the OpenStack, stateless agents (e.g., APIs) are usually load-balanced, and stateful agents (e.g., L3 agents) can be replicated following a leader/slaves design. As a consequence, many geographically distant sites can be equipped with all core services of OpenStack and internal RPC traffic can take advantage of the bus locality. This effect is transparent to the application and may be referred as an implicit locality. Alongside RPC traffic, OpenStack agents use HTTP requests between other agents, and execute database accesses. Leveraging locality during HTTP requests would require to modify the service discovery of OpenStack in order to be also locality aware. However, achieving implicit states locality during databases transactions is still an open research topic [START_REF] Corbett | Spanner: Google's globally-distributed database[END_REF].

VI. CONCLUSION

In this paper, we have studied two different implementations of the Remote Procedure Calls available in OpenStack: a broker-based approach (RabbitMQ) and a router-based approach (Qpid-Dispatch-Router). From the scalability perspective, brokers can be expanded (e.g clustering) by adding new bus agents to cope with an increasing number of connected agents. This allows to distribute the incoming connections and the associated resources consumption among different servers. Nevertheless, under high request rate, message distribution can suffer from bad locality which limits the scalability in this area even in a centralized deployment (e.g RabbitMQ anycast request rate is bound). This locality effect is amplified in a geodistributed context where it plays a critical role. In this context, the implicit locality achieved by a router mesh contribute to a better scalability because distinct bus-agents can parallelize message handling.

More generally, there is a manifest need of making current geo-distributed infrastructures evolve towards local awareness models minimizing the developing and deployment impact. The road to this edgification is not a mere adaptation of current building blocks like communication buses, as it concerns low-level aspects of applications such as messages and data. Implicit locality is a first step in this direction since application code does not require modifications to be applied. In order have a better comprehension, other evaluations are required, namely, configurations with network partitions, fault tolerance.

Our prospective work includes to transpose these results to a fully functional OpenStack and enable locality for the HTTP traffic and database access.

Fig. 1 :

 1 Fig.1: Bus agent configurations. Centralized (left) where agents are interconnected through a LAN and they are connected to RPC agents using a WAN; decentralized (right) where agents are interconnected through a WAN and they are connected to the RPC agents using a LAN. In both cases RPC clients (C) and RPC servers (S) are located in the edge.

  Anycast scenario (top rpc-call, bottom rpc-cast).

  Unicast scenario (top rpc-call, bottom rpc-cast).

  Multicast scenario (rpc-fanout).

Fig. 2 :

 2 Fig. 2: Comparative results of latency for different configurations of bus implementations and number of agents.

Fig. 5 :

 5 Fig. 5: Violin chart (left) showing the latency modes for brokers (rpc-cast, 10 ms inter-agent latency) and the possible message paths in a cluster of three nodes (right).

TABLE I :

 I Parameters of the centralized bus experiments. A campaign involves the combination of call types and bus configurations for each of six sets of number of clients, number of servers, pause between requests to the server and number of messages for the patterns AS US, and MS (72 combinations).

TABLE II

 II

: Results of the anycast scenario. System metrics for rpc-call call type. Maximum values obtained during the benchmark for memory usage, number of processors and TCP connections.

TABLE III :

 III Parameters of anycast scenario. A campaign includes latency and packet loss to the call type for and bus configuration. These parameters are combined with each set of paired parameters: number of clients, number of servers, pause between request to the server and number of messages (288 combinations).

https://qpid.apache.org/components/dispatch-router/

https://github.com/msimonin/ombt-orchestrator

https://github.com/kgiusti/ombt

https://github.com/openstack/oslo.messaging

https://www.influxdata.com

https://www.grid5000.fr/mediawiki/index.php/Rennes:Hardware

ACKNOWLEDGMENT

The authors would like to thank Orange Labs for partially funding this work under a CRE contract. Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations.


Marwa Yusuf
email: marwa.yusuf@ejust.edu.eg

Ahmed El-Mahdy
email: ahmed.elmahdy@ejust.edu.eg

Erven Rohou
email: erven.rohou@inria.fr.

Runtime, Speculative On-Stack Parallelization of For-Loops in Binary Programs

Keywords: Compilers, Runtime, Optimization, Parallelization, Binary, Pthreads, On-Stack Replacement, Speculation. !

Nowadays almost every device has parallel architecture, hence parallelization is almost always desirable. However, parallelizing legacy running programs is very challenging. That is due to the fact that usually source code is not available, and runtime parallelization, without program restarting is challenging. Also, detecting parallelizable code is difficult, due to possible dependencies and different execution paths that undecidable statically. Therefore, speculation is a typical approach whereby wrongly parallelized code is detected and rolled back at runtime. This paper considers utilizing processes to implement speculative parallelization using on-stack replacement, allowing for generally simple and portable design where forking a new process enters the speculative state, and killing a faulty process simply performs the roll back operation. While the cost of such operations are high, the approach is promising for cases where the parallel section is long and dependency issues are rare. Also, our proposed system performs speculative parallelization on binary code at runtime, without the need for source code, restarting the program or special hardware support. Initial experiments show about 2x to 3x speedup for speculative execution over serial one, when three fourth of loop iterations are parallelizable. Also, maximum measured speculation overhead over pure parallel execution is 5.8 %.

INTRODUCTION

N OWADAYS almost every computer has a multicore architecture. However, not every software is designed to utilize this feature. From one side, writing a parallel software is not always an easy task. From the other side, there exist legacy software, possibly running, that were designed for older, serial architectures, and the development cycle has a high cost. Automatic parallelization in these cases may be the only solution. However, there are a number of challenges. First, the source code may not be available (like the case of proprietary software) and/or the program may be already running. Second, the program may have possible dependencies and complex execution paths that cannot be decided until runtime.

In this paper, we propose a speculative parallelization technique that parallelizes for-loops in binary programs at runtime. Our paper assumes that the dependence information for the loop is available through the application of a runtime binary analyzer. The analyzer will essentially mark a parallelizable (dependence-free) execution superpath (which is the union of a set of execution paths) in the forloop, along with exit points from this superpath indicating possible dependence violation that would require rolling back. Based on these information, our mechanism parallelizes the for-loop, but with trampoline jumps added at each exit point. Whenever an exit point is reached, parallel execution stops, state-rolled and the program continues serially. Our approach relies on system processes to implement speculation; fork starts a "backup" version of the current serial loop; the current loop is executed in parallel, and whenever an exit point is reached, the state is recovered by switching to the backup process and killing the parallel process. Moreover, checkpointing is used to decrease the amount of wasted work. This is done through periodic forking of new correct states. The rationale behind this approach is to provide for a simple portable approach. Even though the cost of forking and rolling back is higher, this can be amortized by using more elaborate dependence analysis as well as using loops with rare dependence violations. Moreover, this technique does not require source code information making it directly applicable to binary codes.

Our mechanism is implemented as an extension to the Padrone platform [START_REF] Riou | Padrone: a platform for online profiling, analysis, and optimization[END_REF]. Also, this work is an extension to our previous parallelization technique [START_REF] Yusuf | Runtime on-stack parallelization of dependence-free for-loops in binary programs[END_REF].

To summarize, this paper introduces the following contributions:

1) Running a binary for-loop iterations in parallel, speculatively, using processes. 2) Selective partial parallelization of the remaining loop iterations. 3) Conducting an initial performance investigation of the proposed mechanism.

The rest of this paper is organized as follows: Section 2 discusses related work. Section 3 provides a brief background about the Padrone system, and the parallelization technique used. Section 4 presents the proposed mechanism design and implementation. Section 5 presents the experiments and discusses the results. Finally, Section 6 concludes the paper and suggests future work.

RELATED WORK

Estebanez et al. [START_REF] Estebanez | A survey on thread-level speculation techniques[END_REF] made a comprehensive survey about speculation. They made a taxonomy of speculation's different techniques and contexts, e.g. hardware vs. software based, control vs. data speculation, and binary vs. source code speculation. They also discussed different design questions needed for any speculation system, e.g. lazy vs. eager version management, and lazy vs. eager conflict detection. Based on these different classifications, our system is a software-based control speculation system for running binary code using processes with eager conflict detection and eager version management.

While most speculation systems use threads, we use processes instead for speculation and use threads only to parallelize within the speculative process. This helps in separating the state of the speculative parallel and the serial processes, without the need for special mechanism for buffering state or for committing or rolling back the state later on. While creating and killing processes are expensive operations, this cost is compensated by the gain from parallelization and the lack of need to buffer and commit the execution state. Ding et al. [START_REF] Ding | Software behavior oriented parallelization[END_REF] introduce a speculation technique based on processes, also. However, their system needs compiler cooperation to insert markers in the code to identify speculative regions of code, to be run in parallel speculatively, and this requires recompiling the program. Our system works on binary code directly at runtime, with no need for source code or even restarting the program. Also, their system runs several processes, with one lead and the others speculative, and they execute different parts of code each, and combine the states at commit. Our system has only one executing process at a time, either parallel one that fully utilizes the underlying architecture, or the serial one. Execution continues from only the right one of them, hence no need for synchronizing state at commit. Synchronization is done implicitly at each checkpoint by the forking of a new process that automatically inherits the current state.

Hertzberg and Olukotun [START_REF] Hertzberg | Runtime automatic speculative parallelization[END_REF] introduce RASP, an automatic speculative parallelization system that uses their dynamic binary translation system, DBT86 [START_REF]DBT86: A dynamic binary translation research framework for the CMP era[END_REF] to speculatively parallelize running binary code at runtime, without the need for source code or recompilation. However, their system assumes special features needed in the underlying architecture, e.g. the ability to restore the register file to checkpoint state, the ability to buffer speculative state in memory, and the ability to detect dependency violations. In contrast, our system assumes no specific needs from the underlying hardware.

To conclude, our system combines the advantages of runtime automatic speculative parallelization without the need for source code, debugging information, compiler cooperation or execution restarting. Hence, it can be applied directly on a running program. And this is done without the need for special hardware features, which makes it applicable to current available architectures. Also, our system eliminates the need for buffering and synchronizing state through using processes. The cost of managing processes is amortized by the speedup gained from parallelization. Also, using Padrone system, enables doing all the preparation steps (like profiling, analyses and code generation) during target process execution. Only code injection requires stopping the process. Hence, minimal overhead is achieved.

BACKGROUND

Padrone system is a platform that provides an API to create clients for profiling, analyzing and optimizing running binary codes. These clients can be run without the need for either source code, debugging information or restarting the program. Using the ptrace system call, Padrone attaches to (and detaches from) the running target process and reads (and writes) its memory registers. The distinctive characteristic of Padrone is that it executes in a different process from its target, hence it minimizes its effect on the target behaviour, while analyses and optimizations can be applied during the target process execution, it needs to be stopped only during new code injection (a mere memcopy). Also, Padrone's code generation does not rely on basic blocks that need to be combined into traces to reduce overhead, as Pin [START_REF] Luk | Pin: Building customized program analysis tools with dynamic instrumentation[END_REF] or DynamoRio [START_REF] Bruening | Efficient, transparent, and comprehensive runtime code manipulation[END_REF] do. As such, it does not degrade performance of unmodified code.

This work is expanding our previous parallelization mechanism [START_REF] Yusuf | Runtime on-stack parallelization of dependence-free for-loops in binary programs[END_REF]. This previous work introduces a parallelization mechanism of dependence-free for-loops in running binary programs. It works by extracting the considered loop into a separate function into a code cache, (loopy). Then it changes the start of the original loop to jump to a previously prepared function (parallel). Parallel function creates a number of threads, copies the modified stack of the considered loop into the stacks of these threads, and starts them with the extracted loop function loopy as the start routine. Parallel distributes the remaining loop iterations among threads. After the threads complete their work, the execution continues from after the original loop address. This In this paper, we extend this mechanism to add speculation. The new speculative parallelization mechanism deals with possibly notparallelizable codes, and adapts at runtime.

PROPOSED DESIGN

This work is a part of a bigger system, that is explained briefly in Section 4.1. However, due to page limit, this paper's scope is the speculative parallelization subsystem, which is explained thoroughly in Section 4.2. 1

Full System Design

Fig. 1 shows the flowchart of the full system. A lightweight profiler pass is applied on the input running binary code to determine the hot function and for loop that is candidate for parallelization with the frequent superpath. A superpath is the union of execution paths. Then, an abstract interpretation analysis pass is applied to this hot execution superpath to decide if it is parallelizable or not, based on the dependencies detected in this superpath. However, if the execution exits this superpath, the correctness of parallel execution is not guaranteed. Hence, with the approval of parallelization, the set of possible exit points from this superpath are input to our speculation system in the form of an array passed to the following speculative parallelization step. Each exit point is an address of a conditional jump instruction with the decision that causes exit (whether the exit is the taken jump or notTaken jump). Our system, using these information, parallelizes the running binary superpath with instrumentation at each exit point. Finally, the instrumented code is run speculatively. If the analysis decision is not to parallelize, the code is left intact to run serially.

Speculative Parallelization Subsystem Design

Fig. 2 is an overview of the design of our proposed speculation system. The modification to the running code is done in a Padrone client. The client performs the following steps: 1) A code cache is created to accommodate for the following steps' results.

2) The target for-loop code is extracted into a separate function (loopy) (Procedure 1), into the code cache. This function is parameterized with the loop boundaries. The prologue of the function prepares a stack that is an extended version of the Then, the loop head is modified to take the function parameters as the initialization and condition of the loop. Also, jumps are modified as needed. Then, only the loop body and back edge are copied to this function, as they are. Only jumps and calls' addresses are modified. Finally, a return is added. This function is used later for serial run, as will be explained shortly.

Procedure 1 loopy function procedure LOOPY(lower, higher) for i ← lower, higher do loop body end for end procedure

3) Another similar but instrumented version of loopy is created in the code cache, (specLoopy). In this function, each conditional jump instruction that is marked as an exit point is instrumented. The exit could be a taken jump or notTaken jump. In both cases, the instrumentation code (Procedure 2) is added after the jump instruction. The instrumentation code simply fires an abort signal to the running parallel process. This abort signal causes the parallel process to wake the serial process, waits for it to finish, and then exits. This will be explained in more detail shortly. If the exit is a taken jump, the jump is inverted (greater than becomes less than or equal, for example), and the jump target is modified to the address of the instruction directly after instrumentation code (that follows the jump in the original code).

Procedure 2 instrumentation code

procedure INSTRUMENTATION pid ← parallel process pid sig ← signal number call abort(pid, sig) end procedure 4) A previously prepared function code (parallelSpec) is compiled (using Padrone special compilation) and inserted into the code cache. This function code is a part of the proposed system. However, its compilation is deferred till the actual run to be fed with the actual runtime addresses of loopy, specLoopy and other required system functions. ParallelSpec takes as parameters both loop remaining iterations boundaries, and the size and contents of the original function stack.

If the remaining iterations are so few, parallelSpec just runs them serially. Otherwise it starts speculative parallel run. ParallelSpec creates phases of parallel execution (using a loop), each executes a chunk of the remaining loop iterations. Each phase start is a check point. At each check point, a new serial process is forked and suspended. This is to guarantee that new serial process has the execution state at this check point. Then, the original parent process (which is now the parallel process) creates a number of threads, populates their stacks with the extended original function's stack, and distributes the selected iterations among them. This distribution is done through the parameter passed to the thread start routine. The start routine is specLoopy.

The parallel process waits for the threads to finish. If the threads finish normally, then the commit of this phase is done by simply killing the serial process and continuing to the next phase. If, however, an abort signal is received, parallel process stops execution, wakes the serial process, waits for it to finish, then exits. Upon wake up, the serial process starts executing the remaining iterations from the last committed check point till the end serially, by creating only a single thread and calling loopy as the start routine. Then it returns.

Whether the parallel process continues to the end of iterations or the serial process finishes the last iterations, parallelSpec function returns to the instruction address that follows the original loop directly (afterLoopAddress). Hence, original program continues after the parallelized loop normally. 5) ParallelSpec is inserted into code cache. 6) The start of the original loop is modified to a jump to Par-allelSpec address in code cache. Hence, in the first coming loop iteration, execution switches to parallelSpec. 7) Original function's stack frame is copied to code cache. The address of this copy is copied to right parameter registers, to be passed to parallelSpec. 8) Original loop remaining iterations' boundaries are copied also to right parameter registers, to be passed to parallelSpec.

Fig. 3 gives an arbitrary execution scenario of the speculative parallel runtime of 2mm kernel. In this scenario, the loop has 1600 iterations and parallelization is started after 12 iterations. The parallelization is done on phases, each phase executes 128 iterations on 4 threads. Phases 1 to 9 are executed in parallel. At phase 10, an exit point is encountered at iteration 1200 in thread 2. This triggers an abort which is performed by waking the serial process and dropping the parallel one. The serial process continues from the last consistent state till the end of the loop. Then execution continues after the loop normally.

Discussing memory and time costs

Time costs are due to three main operations: process fork, kill, and copy-on-write (COW) which happens at first write on a memory page in the parallel process. Generally, these operations have relatively high cost. However, they are masked by the speedup gained from parallel operation. The only possible case where there is no speedup at all and only overhead is there, is when abort happens from the first parallel execution phase (before first checkpoint). This is very unlikely, due to the profiling and analysis phase. On the other hand, the simplicity of commit and abort operation, which is only to kill and fork, without memory copying or rolling back, minimizes the overhead greatly.

This simplicity comes by the extra cost in memory, due to redundant serial process. However, as the underlying architecture is fit for parallelized version of the target application, having an extra (idle) serial process is most probably not a problem.

EXPERIMENTS, RESULTS AND ANALYSIS

To provide an initial performance study, three benchmarks from the Polybench benchmark suite [START_REF] Pouchet | Polybench: The polyhedral benchmark suite[END_REF] are used (listed in Table 1, with the number of hot for-loops to parallelize shown for each kernel). Polybench kernels are simple and consist mainly of for-loops. However, to assess speculation, we modified kernels by adding an exit point in each for loop. This forces serial execution of the last quarter of the loop iterations. We run the speculative parallelization mechanism during the execution of the kernel function.

An Optiplex 980 Dell desktop with Intel Core i7 CPU 860 @ 2.80 GHz and 15.6 GiB and running Ubuntu 16.04 is used for experiment. The kernel programs are compiled using gcc 5.4 using -O0 (no optimization). Parallelization is done over 4 threads, to reflect the underlying architecture with four cores.

For each benchmark three runs are performed. First, serial run; the whole loop is run serially. Second, parallel run; the loop is run in parallel except for the last quarter, without any speculation. Finally, speculative run; the whole loop is optimistically run in parallel, until exit point is met, where speculation turns execution into serial. Comparing between speculative and serial runs gives the speculation speedup, while comparing between speculative and parallel runs gives the speculation process overhead. This overhead is mainly due to fork and kill of processes and the time of faulty process squash.

Fig. 4 shows the results. Comparing speculative run to serial run, 2× speedup for 2mm and 3mm benchmarks and 3× speedup for covariance benchmark are achieved. This is for parallelizing only three fourth of the iterations. Comparing speculative run to parallel run, the overhead due to speculation is maximum 5.8%, which is almost negligible.

As the number of parallelized loops in an application increases, the speedup is expected to increase accordingly, because larger parts of the application would run in parallel. I.e, the percentage of execution time spent in loops that can benefit from speculative parallelization increases, the whole application performance would enhance greatly.

CONCLUSION AND FUTURE WORK

In this paper, we presented an initial design of a speculative parallelization runtime system. The system creates a serial process and suspends it at each checkpoint, to save work done so far and continue execution in parallel, until committing at the next checkpoint, or switching to serial if an abort happens. Using processes for separation between serial and parallel executions simplifies managing state of speculative execution. Our system needs no source code, debugging information, compiler or hardware support, or restarting the program. Our system achieves from 2× to 3× speedup on selected Polybench kernels, with maximum 5.8 % speculation overhead.

In future work, we intend to extend the system to be applicable to more kinds of loops. We intend to experiment and analyze its performance with more benchmarks, like SPEC. Also, we intend to integrate with other project modules (profiling and analyses) and experiment the whole system performance. Also, we could monitor how execution goes and adjust parallelization per chunk. For example, the number of threads may vary from chunk to another, or even parallelization could be turned off if not profitable.

Fig. 1 :

 1 Fig.1: Full system overview mechanism needs no source code, no debugging information, no restarting of the program or uplifting it to a higher representation. It works directly on the running binary.In this paper, we extend this mechanism to add speculation. The new speculative parallelization mechanism deals with possibly notparallelizable codes, and adapts at runtime.

Fig. 3 Fig. 4 :

 34 Fig. 3: Example Kernel

TABLE 1 :

 1 Polybench kernels used in the experiments

	Benchmark	Description	# loops
	2mm	2 Matrix Multiplications (D=A.B; E=C.D)	2
	3mm	3 Matrix Multiplications (E=A.B; F=C.D; G=E.F)	3
	covariance	Covariance Computation	1

ACKNOWLEDGMENTS

This research is supported by a Ph.D. scholarship from the Egyptian Ministry of Higher Education (MoHE). Also, this work is partially funded by the PHC IMHOTEP 35236SM project.


Carlos Martínez

Francis Mairet

Pierre Martinon

Olivier Bernard

Dynamics and control of a periodically forced microalgae culture

Keywords: Dynamics and control, Industrial biotechnology, Wastewater, Biomass productivity, Microalgae

Microalgae cultivation with wastewater is a promising way of reducing the energetic needs for wastewater treatment and the costs of biofuel production. However, the very turbid medium is not favorable for the development of microalgae. Indeed, light, the key element for photosynthesis, rapidly vanishes along depth due to absorption and scattering. Therefore it is crucial to understand the effects of the depth on turbid cultures. In this work, we study theoretically the long-term behavior of a continuous culture of microalgae exposed to a periodic source of light. By allowing periodic variations of the depth and the hydraulic retention time, we show that the microalgae population is forced to a periodic regime. Finally, we address numerically the problem of determining the optimal variations of the depth and the hydraulic retention time for maximizing the productivity of the culture in the periodic regime.

INTRODUCTION

Microalgae grown as a by-product of wastewater treatment in high rate algal ponds (HRAPs) represents a great opportunity for reducing costs of biofuel production [START_REF] Park | Wastewater treatment high rate algal ponds for biofuel production[END_REF]; [START_REF] Christenson | Production and harvesting of microalgae for wastewater treatment, biofuels, and bioproducts[END_REF]). Moreover, HRAPs show a great potential for nutrient removal in wastewater treatment [START_REF] Abdel-Raouf | Microalgae and wastewater treatment[END_REF]). One problem with the cultivation of algae in wastewater systems is that light, one of the main factors affecting microalgae growth, rapidly becomes limiting after its decrease due to absorption and scattering by algal cells and the high content of particulate matter and colored substances [START_REF] Morel | Theoretical results concerning light absorption in a discrete medium, and application to specific absorption of phytoplankton[END_REF]; [START_REF] Borowitzka | Limits to growth[END_REF]). We refer to the light extinction due to all non-microalgae components as background turbidity. In the standard analyses of microalgae cultures, background turbidity is neglected. However, [START_REF] Martínez | Theory of turbid microalgae cultures[END_REF] showed theoretically that background turbidity results in a reduction of the productivity when increasing the depth of the system. Indeed, according to [START_REF] Larsdotter | Wastewater treatment with microalgae-a literature review[END_REF], depths of the HRAP between 15 and This work was supported by the CONICYT doctoral grant (Carlos Martínez), and by the Phycover (ANR-14-CE04-0011) and IPL-Algae in silico projects. 1 INRIA Sophia Antipolis, 2004, route des Lucioles BP 93, 06902 Sophia Antipolis Cedex, France (e-mail {carlos.martinez,olivier.bernard}@inria.fr) 2 pierre.martinon@inria.fr 3 francis.mairet@ifremer.fr 50 cm are generally recommended.

The objective of this paper is to give some insights in the optimization of biomass productivity by playing with the depth of the culture and considering a natural light source. In our approach, we combine the modelling approaches of [START_REF] Droop | Vitamin b 12 and marine ecology. iv. the kinetics of uptake, growth and inhibition in monochrysis lutheri[END_REF] and [START_REF] Huisman | Principles of the light-limited chemostat: theory and ecological applications[END_REF] to build a model accounting for light and substrate limitation. Our model is periodically forced by the incident light with period of one day. We argue that by providing periodic input and output flows to the system, any solution of the model reaches a 1-day periodic regime i.e. approaches asymptotically a periodic solution. Thus, we study the productivity of the system in a periodic regime by controlling the input and output flow rates, or equivalently, the depth of the system and the hydraulic retention time. This article is organized as follows. In section 2, we introduce the model of a microalgae culture given by a system of nonautonomous differential equations. In section 3, we study the dynamics of the model. The main result of this section (Theorem 2) gives sufficient conditions to ensure that any solution approaches asymptotically to a periodic solution characterized by the presence of microalgae (i.e. different from the washout). This result follows from reducing the model to a cooperative system and following some ideas of [START_REF] Smith | The periodically forced droop model for phytoplankton growth in a chemostat[END_REF]. In section 4, we state an optimal control problem for maximizing the microalgae productivity per day in the periodic regime. Periodic optimal problems have already been studied by [START_REF] Grognard | Optimal strategies for biomass productivity maximization in a photobioreactor using natural light[END_REF]; [START_REF] Bayen | Analysis of a periodic optimal control problem connected to microalgae anaerobic digestion[END_REF]. Here, we present some numerical solutions obtained with the software BOCOP. Finally, we illustrate the asymptotic behavior of the model when repeating each day the 1-day periodic optimal control.

MODEL DESCRIPTION

Let us consider a perfectly mixed microalgae culture of depth L illuminated from above with an incident light I in . We assume that light is attenuated exponentially according to the Lambert-Beer law i.e. at a distance z ∈ [0, L] from the illuminated surface, the corresponding light intensity I(x, z) satisfies

I(x, z) = I in e -(kx+K bg )z , (1)
with x the microalgae concentration, k > 0 the specific light attenuation coefficient of microalgae, and K bg ≥ 0 the background turbidity. We assume that microalgae growth is limited by light and a substrate s. Based on the model of [START_REF] Droop | Vitamin b 12 and marine ecology. iv. the kinetics of uptake, growth and inhibition in monochrysis lutheri[END_REF], we assume that the specific growth rate µ depends on an internal cell quota q. The latter corresponds to an internal pool of nutrient per unit of biomass. The light intensity effects are described by a Monod type function. Thus, the specific growth rate is taken to be

µ(I, q) = µ max 1 - q 0 q I K I + I -r, (2)
where r > 0 is the respiration rate, q 0 > 0 represents the value of q at which growth ceases, K I > 0 is a halfsaturation constant, and µ max > 0 is the maximal specific growth rate. Following [START_REF] Huisman | Principles of the light-limited chemostat: theory and ecological applications[END_REF], we compute the average growth rate in the reactor, denoted μ, by integrating the local growth rates over all the reactor μ(•) := 1 L L 0 µ(I(z), q)dz.

(3)

A simple computation leads to

μ(•) := µ max (kx + K bg )L ln K I + I in K I + I out (x) 1 - q 0 q -r,( 4
)
with I out (x) = I(x, L) the light intensity at the bottom of the culture.

Cell quota q decreases with cell growth and increases with nutrient uptake, whose rate function is taken to be

ρ(q, s) = ρ max s K s + s d(q) if q ≤ q L , 0 if q > q L , (5)
where ρ max is the maximal uptake rate of nitrogen, q L is the hypothetical maximal quota, and K s is a halfsaturation constant. d(q) ∈ [0, 1] is a down regulation term. While d(q) is usually taken as a linear function [START_REF] Bougaran | Modeling continuous cultures of microalgae colimited by nitrogen and phosphorus[END_REF]; [START_REF] Morel | Kinetics of nutrient uptake and growth in phytoplankton 1[END_REF]), here we take d(q) as d(q) = q L -q q L -q 0 2 q L -q q L -q 0 + 3 q -q 0 q L -q 0 (6)

We note that d is the unique cubic function satisfying

d(q 0 ) = 1 , d(q L ) = 0 , and d (q 0 ) = d (q L ) = 0. (7)
The volume (V ) of the culture varies with the supply flow rate (Q in ) and the withdrawal rate

(Q out ) according to V = Q in -Q out . (8)
The transversal area (A) of the culture is constant in time and along the depth of the culture. After dividing both sides in Eq.( 8) by A, we obtain the following equation for the depth of the culture

L = F in -F out , (9)
with

F in := Q in /A and F out := Q out /A
)) ẋ = [μ(t, x, q, L) - F in L ]x q = ρ(q, s) -μ(t, x, q, L)q ṡ = F in L (s in -s) -ρ(q, s)x, 2010
where s in is the (constant) substrate influent concentration.

PERIODIC SYSTEM AND ASYMPTOTIC BEHAVIOR.

We assume that the incident light is variable in time according to

I in (t) = I max max{0, sin(2πt/ω)} 2 , ( 11
)
with ω > 0 the length of a day. Thus, by assuming that F in and F out vary periodically with a period ω, the system (9)-( 10) becomes an ω-periodic system.

We use the following notation for the time-average of an ω-periodic function4

< f >:= 1 ω ω 0 f (t)dt. ( 12
)
By integrating Eq.( 9) we obtain that

L(t) = L(0) + t 0 [F in (s) -F out (s)]ds. ( 13
)
We assume that < F in (t) -F out (t) >= 0. Then L is an ω-periodic function.

We define the total amount of limiting element both in the substrate and in the biomass by means of

S = s + xq. (14)
A simple calculation shows that S satisfies the differential equation

Ṡ = D(t)(s in -S), (15)
with D(t) : Fin(t) L(t) known as the dilution rate. We can rapidly verify that S(t) → s in as t → ∞ for any value of S(0). Thus, the solutions of Eq.( 10) approach the surface s in = s + xq. We take advantage of this by dropping the equation for s and replacing s in Eq.( 10) by s = s in -xq in the second equation. This results in the two-dimensional system ẋ = [μ(t, x, q) -D(t)]x q = ρ(q, s in -xq) -μ(t, x, q)q .

(16)

In the following we study the asymptotic behavior of Eq.( 16). Care must be exercised in extrapolating results obtained from the analysis of Eq.( 16) to analogous results for Eq.( 9)-( 10). A discussion about this can be found in [START_REF] Smith | The periodically forced droop model for phytoplankton growth in a chemostat[END_REF].

As s must be non-negative, initial conditions for Eq. ( 16) must satisfy x(0)q(0) ≤ s in . We note that if x(0) = 0 (resp.

x(0) > 0), then x(t) = 0 (resp. x(t) > 0) for all t ≥ 0 (see [START_REF] Zanolin | Permanence and positive periodic solutions for kolmogorov competing species systems[END_REF] to find rigorous arguments). We also note that q(0) ≥ q 0 implies q(t) ≥ q 0 for all t ≥ 0. Therefore we are only interested in solutions starting on the set P := {(x, q) ; x > 0, q ≥ q 0 , and xq ≤ s in }.

A solution (x, q) of Eq.( 16) will be called an ω-periodic solution provided each component is ω-periodic. There is a trivial periodic solution corresponding to the absence of microalgae in the chemostat. Putting x = 0 in the second equation of ( 16) results in q = ρ(q, s in ) -μ(t, 0, q)q.

(18)

The following proposition guarantees the uniqueness of the washout.

Proposition 1. Eq. ( 18) has a unique periodic solution q * to which all solutions are attracted.

Proof. Since q is strictly decreasing with q, we can use the same arguments as in the proof of Proposition 1.1 in [START_REF] Smith | The periodically forced droop model for phytoplankton growth in a chemostat[END_REF].

Thus, the trivial periodic solution is given by

x = 0, q = q * (19)
The change of variables x s := qx leads the system (16

) to ẋ = [μ(t, x, x s /x) -D(t)]x ẋs = ρ(x s /x, s in -x s )x -D(t)x s . (20)
Eq. ( 20) is a cooperative system i.e.

∂ ẋ ∂x s , ∂ ẋs ∂x ≥ 0.
The importance of this system lies on the fact that any bounded solution of a planar, cooperative, periodic system of differential equations is asymptotic to a periodic solution ( see Chapter 7 in [START_REF] Smith | The theory of the chemostat: dynamics of microbial competition[END_REF]).

Since x s satisfies the differential equation

dx s dt = x s ρ(q, s in -x s ) q -D , (21)
we have that x s (t) = x(t)q(t) ≤ s in for all t ≥ 0. Consequently, P is positively invariant with respect to Eq. ( 16). Thus, if x(0) > 0, then x(t) ≤ s in /q 0 for all t ≥ 0. This implies that the set K := {(x, x s ) ; x ∈ (0, ∞), q 0 < x s /x, x s ≤ s in } is positively invariant with respect to (20). Consequently, any solution of (20) starting on K is bounded. Thus, any solution of Eq.( 20) starting on K, or any solution of Eq. ( 16) starting on P , approaches a periodic solution. The following theorem gives conditions to avoid the washout (0, q * ) as an attracting periodic solution.

Theorem 2. If < μ(t, 0, q * (t)) -D(t) > is greater than 0, then any solution of Eq. ( 16) starting in P is asymptotic to an ω-periodic solution of Eq.( 16) with positive xcomponent.

Proof. We use the Floquet theory (see Chapter 7 in the book of Sideris ( 2013)) to determine the stability of the washout. The characteristic multipliers of the washout (0, q * ) are given by ρ 1 = exp(ω < a(t) >) and ρ 2 = exp(-ω < c(t) >) with

a(t) = μ(t, 0, q * (t)) -D(t), (22)
and

c(t) = - ∂ρ ∂q (q * (t), s in ) + μ(t, 0, q * (t)) +q * (t) + ∂ μ ∂q (t, 0, q * (t)) > 0. (23)
Thus, ρ 1 > 1 and ρ 2 < 1, and the washout is not stable. This implies that not all the solutions of Eq.( 16) starting on P are asymptotic to the washout. Since any solution converges to an ω-periodic solution, there exists an ωperiodic solution different from the washout that attracts some solutions. Following the same arguments as in the proof of Proposition 1.3 in [START_REF] Smith | The periodically forced droop model for phytoplankton growth in a chemostat[END_REF], we can conclude that this is true for any solution starting on P .

Note that Theorem 2 does not say anything about the number of periodic solutions with positive x-component.

OPTIMAL CONTROL PROBLEM

We define the areal biomass harvest on the interval of time [t i , t f ] as

H = t f ti F out (t)x(t)dt. ( 24
)
H represents the quantity of biomass that is harvested on the interval of time [t i , t f ] per unit of area.

Here we consider the case where the chemostat is operated in long term, with a periodic daily biomass production from the reactor outlet. The problem that we consider is the maximization of the biomass production over a single day. The control variables are F in (u 1 ) and F out (u 2 ). The problem can be stated as

max H(u 1 , u 2 ) = ω 0 u 2 (t)x(t)dt, s.t. ẋ = [μ(t, x, q, L) -u 1 /L]x, q = ρ(q, s in -xq) -μ(t, x, q, L)x, L = u 1 -u 2 x(0) = x(ω) > 0, q(0) = q(ω), L(0) = L(ω) u 1 (t) ∈ [0, F in,max ] , u 2 (t) ∈ [0, F out,max ] (25)
In the formulation of our problem we use Eq. ( 16) together with Eq. ( 9).

Numerical results

We solve numerically the problem ( 25), with a direct method implemented in the sofware BOCOP [START_REF] Bonnans | Bocop, the optimal control solver, open source toolbox for optimal control problems[END_REF]) (version 2.10). The problem is discretized by a two-stage Gauss-Legendre method of order 4 with 200 time steps. We consider a constant initialization, and the tolerance for IPOPT NLP solver is set at 10 -12 .

We consider two microalgae cultures; culture 0 without background turbidity i.e. K bg = 0, and culture 1 with a background turbidity K bg = 10 m -1 . For both cultures the rest of parameters are given in Table 1. The value of K bg for the culture 1 was set as high as the numerical method allowed. We were not able to obtain convergence for values of K bg equal to or higher than 11 m -1 . [START_REF] Huisman | Principles of the light-limited chemostat: theory and ecological applications[END_REF] reported a background turbidity of 7.2 m -1 for a nutrient-rich medium used in a laboratory culture.

Figures 1 and2 show the results. In both cultures, algae concentration increases during half or almost all the day (first half of the period), then decreases at night (see Figure 1A). We note that in culture 1 the microalgae concentration is higher, and consequently the nutrient in the medium is lower (see Figure 1C). However, the daily microalgae productivity is 1.7 gC m -2 in contrast to the culture 0 that reaches a daily microalgae productivity of 4.0 gC m -2 (i.e. 8.0 gDW m -2 ).

The control structures are Bang-Singular (u 1 ) and Bang-Bang (u 2 ) for both cultures (see Figure 2A). These controls result in a different depth for each culture. Figure 2B shows that there is a difference of almost 40 cm during all the period of 24 hours with a lower depth for the culture that accounts for background turbidity.

Consider the controls (u 1 , u 2 ) (see Fig. 2A) obtained from the optimization of one periodic day-night cycle. We apply the respective control to each culture (i.e. to solve Eq.( 9)-( 16)) repeatedly for a long interval of time. The initial depth for each culture is equal to the initial depth of the respective optimal solution (see Figure 2B). The initial microalgae concentration and the initial quota are 5 gC/m 3 and 0.28 gN/gC respectively for both cultures. Figures 3 and4 show that the microalgae concentration approaches the optimal periodic microalgae concentration (Fig. 1A) found previously. For the culture 1 the microalgae concentration approaches more slowly to the periodic solution. Indeed, it needs 50 days in contrast to 30 days for the Fig. 3. Comparison of the optimal 1-day periodic microalgae concentration and the evolution of the microalgae with a low initial concentration when the periodic 1-day optimal periodic control is applied. Culture without background turbidity.

sufficient condition given in Theorem 2. For both cases, we have that < μ(0, q * (t), t) -D(t) >≥ 0.3, thus, any solution to Eq. ( 16) starting in P should converge to an ωperiodic solution of the system with a positive microalgae concentration.

CONCLUSIONS AND FUTURE WORK

A first series of numerical simulations using a direct method illustrates the impact of the background turbidity on the choice of the depth of the culture for maximizing the microalgae productivity. We have shown that a background turbidity of 10 m -1 can result in a reduction of 40 cm of the optimal depth and a productivity loss of 55 %. Thus, the background turbdity should not be neglected. The choice of the depth is not trivial and should be adapted to the overall turbidity, in particular when both light and nutrient limitations can occur. This choice should also include thermal considerations, since low depth induces lower thermal inertia. Processes with low depth are likely to overwarm very rapidly in hot seasons [START_REF] De-Luca | Exploiting meteorological forecasts for the optimal operation of algal ponds[END_REF]) and a trade-off between light and temperature performances should be found.

We also studied theoretically the long-term behavior of the microalgae population when the system is operated periodically in agreement with the period of the light source. We established sufficient conditions to ensure that any solution of the model, independently of the initial conditions, is attracted to an oscillatory solution with a positive microalgae concentration.

Photoinhibition (i.e. reduction of the photosynthetic rate due to high light intensities) should be included in a future work. Low depths of the culture could enhance the photoinhibtory process resulting in a lower productivity, and for low initial microalgae concentrations the population could go extinct (see [START_REF] Gerla | Photoinhibition and the assembly of light-limited phytoplankton communities[END_REF][START_REF] Martínez | Maximizing microalgae productivity by shading outdoor cultures[END_REF]).

In this work, we emphasized the productivity of microalgae using wastewater streams without paying attention to the aspect of wastewater treatment. In a future work, other

  linear flows. Mass balances in the culture give the following equations (see Chapter 2 in Dochain (2013) and Bougaran et al. (

Fig. 1 .Fig. 2 .

 12 Fig. 1. Optimal solutions for problem (25) with two different background turbidities. A. Microalgae concentration. B. Cell quota. C. Substrate concentration in the medium. culture 0.

Fig. 4 .

 4 Fig. 4. Comparison of the optimal periodic microalgae concentration and the evolution of the microalgae with a low initial concentration when the periodic optimal control is applied all the time. With background turbidity.

Table 1 .

 1 Parameters

	Parameter Value	Unit		Reference
	µmax		1.72	d -1		Huisman et al. (2002)
	K I			107	µmol m -2 s -1	Huisman et al. (2002)
	k			0.2	m 2 gC -1		Béchet et al. (2013)
	ρmax		11.2	gN gC -1 d -1	Bougaran et al. (2010)
	q L			0.28	gN gC -1		Bougaran et al. (2010)
	q 0			0.07	gN gC -1		Bougaran et al. (2010)
	Ks			0.0007	gN m -3		Bougaran et al. (2010)
	r			0.1	d -1		-
	s in			10	gN m -3		-
	Imax		2000	µmol m -2 s -1	-
	K bg			0 or 10	m -1		-
	F in,max	1000	L m -2 d -1		-
	Fout,max	1000	L m -2 d -1		-
	)	40
	Microalgae (gC/m 3	30 35
			25
			0	0.2	0.4	0.6	0.8	1
		0.29
	Quota (gN/gC)	0.27 0.28
		0.26
			0	0.2	0.4	0.6	0.8	1
			0	0.2	0.4	0.6	0.8	1
					Time (d)

A function f is ω-periodic if f (t + ω) = f (t) for all t

optimization problems will be studied. For example, the maximization of the removal of nitrogen with restrictions over the volume of wastewater to be treated.