Thuy Linh Nguyen

Adrien Lebre

Conducting Thousands of Experiments to Analyze VMs, Dockers and Nested Dockers Boot Time

Keywords: Virtual Machine, Docker, Nested Docker, Boot Time

While many studies have been focusing on reducing the time to manipulate Virtual Machine/Container images in order to optimize provisioning operations in a Cloud infrastructure, only a few studies have considered the time required to boot these systems. Some previous researches showed that the whole boot process can last from a few seconds to few minutes depending on co-located workloads and the number of concurrent deployed machines. In this paper, we discuss a large experimental campaign that allows us to understand in more details the boot duration of both virtualization techniques under various storage devices and resources contentions. Particularly, we analyzed thoroughly the boot time of VMs, Dockers on top of bare-metal servers, and Dockers inside VMs, which is a current trend of public Cloud Computing such as Amazon Web Services or Google Cloud. We developed a methodology that enables us to perform fully-automatized and reproducible experimental campaigns on a scientific testbed. Thanks to this methodology, we conducted more than 14.400 experiments on Grid'5000 testbed for a bit more than 500 hours. The results we collected provide an important information related to the boot time behavior of these two virtualization technologies. Although containers boot much faster than VMs, both containers and VMs boot time are impacted by the co-workloads on the same compute node.

Comment conduire des milliers d'expériences pour analyser les temps de démarrage d'un environment d'exécution de type machines virtuelle ou conteneur Résumé : Si de nombreuses études se sont concentrées sur la réduction du temps nécessaire pour manipuler les images de machines virtuelles/conteneurs afin d'optimiser les opérations de provisionnement dans une infrastructure Cloud, seules quelques études ont examiné le temps requis pour le démarage de ces systèmes. Plusieurs travaux antérieurs ont montré que l'ensemble du processus de démarrage peut durer de quelques secondes à plusieurs minutes en fonction des charges de travail co-localisées et du nombre de machines déployées simultanément. Dans cet article, nous expliquons la méthodologie mise en place afin de conduire une grande campagne expérimentale sur les technologies de machines virtuelles et de conteneurs afin de comprendre plus en détail l'impact des conflits d'accès aux ressources tels que les périphériques de stockage. En particulier, nous avons analysé et comparé le temps de démarrage des machines virtuelles, des conteneurs Docker hébergés sur des serveurs physiques et de ceux hébergés sur des serveurs virtualisés, ce dernier correspondant à une tendance actuelle du Cloud Computing public tel qu'Amazon Web Services ou Google Cloud Platform. Nous avons développé une méthodologie permettant de conduire des campagnes expérimentales entièrement automatisables et facilement reproductibles sur une plateforme scientifique telle que l'infrastructure Grid'5000. Grâce à cette méthodologie, nous avons pu réaliser plus de 14400 expériences pour une durée totale d'un peu plus de 500 heures. Les résultats que nous avons collectés fournissent des informations importantes sur le comportement au démarrage de ces deux technologies de virtualisation.

Mots-clés : Machine virtuelle, conteneur, temsp de démarrage, reproductibilité, experimentation

Conducting Thousands of Experiments to

Analyze VMs, Dockers and Nested Dockers Boot Time Thuy Linh Nguyen, Adrien Lebre IMT Atlantique INRIA, LS2N, France thuy-linh.nguyen@inria.fr, adrien.lebre@inria.fr While many studies have been focusing on reducing the time to manipulate Virtual Machine/Container images in order to optimize provisioning operations in a Cloud infrastructure, only a few studies have considered the time required to boot these systems. Some previous researches showed that the whole boot process can last from a few seconds to few minutes depending on colocated workloads and the number of concurrent deployed machines. In this paper, we discuss a large experimental campaign that allows us to understand in more details the boot duration of both virtualization techniques under various storage devices and resources contentions. Particularly, we analyzed thoroughly the boot time of VMs, Dockers on top of bare-metal servers, and Dockers inside VMs, which is a current trend of public Cloud Computing such as Amazon Web Services or Google Cloud. We developed a methodology that enables us to perform fullyautomatized and reproducible experimental campaigns on a scientific testbed. Thanks to this methodology, we conducted more than 14.400 experiments on Grid'5000 testbed for a bit more than 500 hours. The results we collected provide an important information related to the boot time behavior of these two virtualization technologies. Although containers boot much faster than VMs, both containers and VMs boot time are impacted by the co-workloads on the same compute node.

I. INTRODUCTION

Resource virtualization technologies play an essential role in plenty of Cloud Computing infras-tructures. For many years, applications developers embrace either hypervisor-based virtualization (a.k.a. virtual machine) or OS-based virtualization (a.k.a. container) to benefit from cloud resources. When comparing these two technologies, prior researches [START_REF] Morabito | Hypervisors vs. lightweight virtualization: a performance comparison[END_REF], [START_REF] Felter | An updated performance comparison of virtual machines and linux containers[END_REF], [START_REF] Sharma | Containers and virtual machines at scale: A comparative study[END_REF], [START_REF] Sonone | On exploiting page sharing in a virtualised environmentan empirical study of virtualization versus lightweight containers[END_REF] mainly focused on the application's performance aspect where containers were presented as a better alternative to VMs. All these works presented the same conclusion: the performance of a container-based application is close to that of the bare metal, while there was a significant performance degradation when running the same application in a VM. Although valuable, these studies did not examine the boot duration of VMs/containers. The boot operation is a key factor in the resources provisioning process in a cloud system. Because the VM/container boot process consumes CPU, I/O and possibly network resources, understanding how co-located VMs/containers impact the boot process of a new VM/container (and reciprocally) is important. For example, without the proper understanding of the VMs/containers boot time behaviors, it can take some minutes to boot a VM/container if it is allocated on a high resources contention compute node. This situation is critical when the customers need to turn on a VM/container to handle a burst of incoming requests to their systems and potentially causes the economic loss. To the best of our knowledge, only a few studies have investigated the question of the boot time. Sonone et al. [START_REF] Sonone | On exploiting page sharing in a virtualised environmentan empirical study of virtualization versus lightweight containers[END_REF] proposed a preliminary analysis of containers and VMs boot time. However, this study has been limited to one constrained scenario. Xavier et al. [START_REF] Xavier | Time provisioning evaluation of kvm, docker and unikernels in a cloud platform[END_REF] compared the boot time between KVM, Docker and Unikernel in the concurrent boot scenarios on OpenStack platform. Recent works [START_REF] Wu | A reference model for virtual machine launching overhead[END_REF], [START_REF] Nguyen | Virtual machine boot time model[END_REF] showed that under resource contentions, the boot time of one VM can take from few seconds up to more than a minute.

Because the duration of a boot process is essential to the provisioning operation in a cloud infrastructure, it is important to understand how resource workloads such as CPU utilization, memory usage, I/O and network bandwidth on several storage devices and different boot parameters impact the behavior of booting VMs as well as containers. In this paper, we conducted thousands of experiments in order to investigate in details the boot time of VMs, containers and nested containers (i.e., a container running inside a VM). We choose KVM [START_REF] Kivity | kvm: the linux virtual machine monitor[END_REF] and Docker [START_REF] Merkel | Docker: lightweight linux containers for consistent development and deployment[END_REF] for our evaluation because they are the most widely used virtualization solutions. From this point forward, the term "docker" is used interchangeably with "docker container".

As far as we know, this is the first study that deals with many different resource contention scenarios for the boot time. Our results first confirm that with different configured parameters, the boot time of VMs can last few seconds to minutes. Second, containers achieve generally better boot performance when compared with traditional virtual machines. However, both VMs and containers boot time generally share the same patterns under high I/O utilization. While we discuss some of the results we collected, the contribution of the paper is twofold as it also presents in details the method we used to achieve such a large-scale campaign of experiments. All the scripts we used, are available on a public git repository 1 . The code can be reused in order to perform similar experiments on other testbeds such as the Chameleon [START_REF] Mambretti | Next generation clouds, the chameleon cloud testbed, and software defined networking (sdn)[END_REF] (with slight adaptations in order to remove the dependency to Grid'5000).

The rest of this article is organized as follows. Section II presents related works. Section III describes the script we conducted to execute all experiments automatically. We present the experiment protocol in Section IV and analyze the results of differrent scenarios in Section V and 1 https://github.com/ntlinh16/vm5k Section VI. Finally, the conclusion is in Section VII.

II. RELATED WORK

Most of the researches in literature performed experiments to evaluate the performance of containers and virtual machines. Morabito et al. [START_REF] Morabito | Hypervisors vs. lightweight virtualization: a performance comparison[END_REF] and Felter et al. [START_REF] Felter | An updated performance comparison of virtual machines and linux containers[END_REF] used various benchmarks to stress different resources on the compute node to explore the difference in performance aspects. These studies concluded that running an application on container have a better performance than on a VM. They both agreed the disk I/O path is a bottleneck for hypervisor-based virtualization. From a data center perspective, Sharma et al. [START_REF] Sharma | Containers and virtual machines at scale: A comparative study[END_REF] conducted a comparative study from the perspective of performance, isolation and resource allocation of hardware and OS-level virtualization. Sonone et al. [START_REF] Sonone | On exploiting page sharing in a virtualised environmentan empirical study of virtualization versus lightweight containers[END_REF] focused on evaluating the memory utilization between container and VM. Besides, their work compared boot time of containers and VMs. However, there was only one simple experiment, which analyzed the boot time of 10 VMs/containers. They avoided disk utilization during boot up by caching all required disk blocks. The results showed that containers boot in a relative short time with a CPU resource usage less than the VMs one. In [START_REF] Wu | A reference model for virtual machine launching overhead[END_REF], the authors performed a detailed study of the boot time of a VM under different workload contentions and introduced a reference model to represent the resource overhead during the VM boot process. Xavier et al. [START_REF] Xavier | Time provisioning evaluation of kvm, docker and unikernels in a cloud platform[END_REF] launched multiple VMs/containers/unikernels concurrently to measure the boot time within the full provisioning process of OpenStack platforms. The experiment only focused on starting multiple instances in parallel. Although valuable, we underline that all these studies have been unfortunately done in an ad-hoc manner. That is, they did not provide scripts or enough information to reproduce and extend them.

In our previous work [START_REF] Nguyen | Virtual machine boot time model[END_REF], we conducted a first series of experiments measuring VM boot times. Besides CPU, I/O and network usages, we found that there are multiple other factors to take into account to deliver an accurate model of VM boot operations (cache modes, VM disk types, storage device types etc.). In order to identify how these factors impact on the boot duration, we conducted

III. A SOFTWARE DEFINED EXPERIMENT

All our experiments have been performed on top of the Grid'5000 testbed [START_REF] Balouek | Adding virtualization capabilities to the Grid'5000 testbed[END_REF]. We created a dedicated script to create and manage VMs automatically by leveraging the Execo framework [START_REF] Imbert | Using the execo toolbox to perform automatic and reproducible cloud experiments[END_REF] and libvirt. Precisely, our script extends vm5k2 -a python module to perform reproducible experiments of VMs on the Grid'5000 platform. At coarse-grained, vm5k relieves researchers of the burden of deploying virtualization stack on baremetal servers: (1) it deploys and configures servers with all necessary packages, (2) it creates the VMs templates according to the defined parameters, (3) it starts VMs and (4) it performs specific benchmarks and collect information. By extending vm5k and using advanced features of Execo, we completely scripted our experimental campaign in order to measure the boot time and monitor the resource usage during the boot process for both VMs and containers. We underlined this script allows any researchers to reproduce all experiments anytime as it performs all scenarios in an isolated environment.

Figure 1 shows the workflow of our script. First, the script reserves compute nodes in Grid'5000's clusters by using OARSUB software suite [START_REF] Capit | A batch scheduler with high level components[END_REF]. Then Kadeploy3 [START_REF] Jeanvoine | Kadeploy3: Efficient and scalable operating system provisioning for clusters[END_REF] is used to deploy these compute nodes with specific Linux environment and set up the network. Next, we install some software and tools required for our experiments by utilizing Taktuk [START_REF] Claudel | Taktuk, adaptive deployment of remote executions[END_REF] to send installation commands. When the compute nodes are ready, we loop through all the combinations of scenarios for our experiment, which will be explained in Section IV. For each combination, we use Execo [START_REF] Imbert | Using the execo toolbox to perform automatic and reproducible cloud experiments[END_REF] with Taktuk to run the scripted scenario and collect results from the compute nodes. All the results are gathered and saved on a machine where the script is executed.

IV. EXPERIMENTS SETUP A. Infrastructure

Each compute node has 2 Intel Xeon E5-2660 CPUs (8 physical cores each) running at 2.2GHz; with 64GB of memory, and 10 Gigabit Ethernet. We evaluated our results on three different storage devices: HDD, SSD and CEPH. We have 10.000 rpm Seagate Savvio 200GB HDD with 148MB/s throughput, Toshiba PX04SMB040 400GB SSDs with 700MB/s throughput, and a 5-nodes CEPH system with HDD. We used CEPH 10.2.5, and mount it as a block device with ext4 format on the compute node.

B. VM and Docker Configurations

We set up all VMs and containers with 1 vCPU and 1 GB of memory. In our experiments, we defined two type of machines:

• e -machine is an experimenting machine (i.e., VM, docker or nested docker) which is used to measure the boot time; • co -machine is a co-located machine, it is allocated on the same compute node as emachine and runs competitive workloads; We used Docker [START_REF] Merkel | Docker: lightweight linux containers for consistent development and deployment[END_REF] version 17.05.0-ce, build 89658be, with auf s storage driver. For VM, the hypervisor is Qemu/KVM (Qemu-2.1.2 and Linux-3.2) [START_REF] Kivity | kvm: the linux virtual machine monitor[END_REF], virtio [START_REF] Russell | virtio: towards a de-facto standard for virtual i/o devices[END_REF] is enabled for network and disk device drivers. The I/O scheduler of VMs and the compute node are CFQ. We created the combinations of booting VMs by using the following parameters:

• cpu_policy: whether all VMs/dockers are started on the same physical core or each VM/docker is isolated on a dedicated core. • cache_mode: we use writeback, writethrough and none when configuring a VM. A detail explanation for each cache mode is available at [START_REF]Description of cache modes[END_REF] fully cloned from the original VMI. All read/writes accesses generated from the VM will be performed on this standalone disk. We combined the above parameters to cover a maximum of boot scenarios because the boot time is not only impacted by resource contention on the same compute node but also the way VMs are booted and the way they are created. We underline that we did not consider the configuration of a VM. Indeed, Wu et al [START_REF] Wu | A reference model for virtual machine launching overhead[END_REF] showed the capacity of a VM does not impact the duration of a VM boot process (i.e., a VM with 1 core and 2G memory takes a similar time to boot as a VM with 16 cores and 32GB). We also did not consider the size of a VMI. Although the application files can significantly increase the size of the VMI, only the kernel data is loaded for the boot process. Several studies [START_REF] Razavi | Scalable virtual machine deployment using vm image caches[END_REF], [START_REF] Zhang | Large-scale virtual machines provisioning in clouds: challenges and approaches[END_REF], [START_REF] Nicolae | Optimizing multi-deployment on clouds by means of self-adaptive prefetching[END_REF] confirmed that a small portion of a VMI is loaded during a VM boot process.

C. Benchmark Tools 1) LINPACK:3 is used to produce CPU workloads. LINPACK estimates a system's floating point computing power by measuring how fast a computer solves a dense n by n system of linear equations Ax = b.

2) CacheBench:4 is a benchmark to evaluate the raw bandwidth in megabytes per second of the memory of computer systems. It includes read, write and modify operations on the memory to fully simulate the effect of memory usage.

3) Stress:5 simulates an I/O stress by spawning a number of workers to continuously write to files and unlink them.

4) Iperf:6 measures the maximum achievable bandwidth on IP networks. Iperf creates TCP and UDP data streams to measure the throughput of a network that is carrying them.

D. Boot time

In our work, the boot time is calculated as the duration to perform only the boot process. We did not take into account the duration of VM/container placement nor the VMI transferring process. The boot duration is measured as follows:

VM boot time: we assume that a VM is ready to be used when the guest OS is deployed completely and clients can log into the VM, therefore, we calculated the VM boot duration as the time to have the SSH service started. This time can be retrieved by reading the system log, and it is measured with milliseconds precision. In our setup, we configured SSH as the first service to be started.

Docker boot time:

The main idea behind a container is running applications in isolation from each other [START_REF] Merkel | Docker: lightweight linux containers for consistent development and deployment[END_REF]. For this reason, docker boot duration is considered as the time to get a service runs inside a docker. Specifically, by using Docker CLI7 , we measured the boot time as the duration for starting the SSH service inside a docker.

Nested Docker boot time: We measured this boot time in the same manner as the Docker boot time. We did not include the host VM boot time in this calculation.

V. BOOT TIME IN NO-WORKLOAD ENVIRONMENT

This scenario aims to evaluate how the boot time is affected when multiple machines are We boot several e-machine on a "fresh" compute node (i.e., a compute node without the co-located workload and an empty page cache). Each e-machine is assigned to a single core to avoid CPU contention, the number of e-machines has been increased from 1 to 16 because the compute node we used only has 16 physical cores.

For VMs, we created them with two types of disk creation strategies, three cache modes and they are booted in two ways: all at once and one then others.

A. VM Boot Time

Figure 2 reveals that even on a "fresh" node when we boot 16 VMs simultaneously, the boot duration can last more than one minute in the worse case. In comparison, it only takes 4.5 seconds to boot one VM. The expected impact on VM boot time in this experiment is mostly the I/O throughput from loading the kernel files and writing the system log from VMs.

On HDD, the boot time of VMs with shared image disk is always faster than the no shared one in three cases of cache mode. When the cache mode is on (i.e., writeback and writethrough), the boot time of VM with shared image disk is much faster. The reason is when the very first VM boots, the mandatory data for VM boot process on the backing file is loaded on the memory, and then, because all VMs are sharing the same backing file, the following VMs can access this data directly from the memory and do not generate read access to the storage device. In the meanwhile, with no shared image strategy, because every VM has its standalone disk, the mandatory data has to be read many times even all these VMs are created from the same VMI. In case of none cache mode, VMs with shared image disk also have to read the boot data from backing file many times. Moreover, there is the overhead of read access checking of shared image strategy. Therefore, the boot time is less faster than the no shared one.

To compare one then others and all at onces boot policy, we should only consider scenarios where VMs get benefit from the cache, specifically, VMs are created by using share image disk with writeback or writethrough cache mode. In this condition, the one then others policy boots faster than all at once. In case of one then others, only the first VM generates read operations to the disk, the other VMs read mandatory data from memory so that the I/O contention only comes from write operations (VMs write log files during boot process). On the other hand, when all VMs are booted at the same time, the I/O contention comes from read and write access of all VMs. The difference in the amount Thuy Linh Nguyen, Adrien Lebre of I/O requests between these two cases leads to the faster boot of one then others boot policy.

On SSD, the boot time of one VM is around 2.5 seconds, and it is mostly constant when we increase the number of VMs from 1 to 16, and the VM boot time is neither not impacted by different cache modes or image policies. The boot duration does not increase because the I/O throughput of the SSD is five times bigger than HDD, all I/O requests generated by VMs are not enough to stress the I/O and they are handled very quickly. The boot time of one then others is longer because we accumulate the boot time of the first VM.

On CEPH, with writeback and writethrough cache mode, we observe that there is not a big difference in boot time between two image policies as on HDD. The shared image disk VMs still gain the benefit from the cache, however, the VMs with no shared image disk do not directly suffer the bad overhead of the random read as on HDD. With none cache mode, VMs with no shared disk boot much faster than VM with share image disk. There are two reasons. First, with the good I/O performance of CEPH, random read access from different VM disks in case of no shared image on CEPH is responded faster. Second, when there is no cache, we have already explained that VMs with share image disk have to load mandatory data many times. Plus, the overhead of checking where the needed data is stored to read of the shared image mechanism becomes significant in case of the appearance of the latency.

In brief, without co-workloads, VMs with various installations have different boot duration, and even booting multiple VMs with the same installations have diverse behaviors on different storage devices. Shared image policy always have better performance on all storage devices if the cache mode of VMs is on. Although the I/O performance of writeback is the best, the data is not protected in a power failure situation and it is recommended only for temporary data where data loss is not a concern. With one then others boot policy, the boot time is good only on HDD where the random read is costly; on CEPH and SSD, with good I/O performance the all at once boot policy is slightly better.

To compare the boot time of VMs and contain-ers in the next section, we illustrate in Figure 3a the boot time of VMs with writethrough cache mode, share image disk and one then others boot policy.

B. Docker Boot Time

Figure 3b depicts that the boot time of docker increases linearly along with the increasing of the number of dockers on three storage devices. The result also shows that dockers boot faster than VMs, as expected, even in case of the best configured of VMs (Figure 3a). On HDD, booting one docker in an idle node takes 1.7 seconds and 16 dockers need around 10.5 seconds. On CEPH, the boot duration is slightly better on HDD because of the higher I/O performance of CEPH. It takes around 1.5 second to 10 seconds to boot 1 to 16 dockers simultaneously. On SSD, the boot time also has the upward trend with smaller slope compared to HDD and CEPH. This is the result of having the highest I/O throughput between the 3 types of disks.

C. Nested Docker Boot Time

Boot duration of nested docker has the same trend as docker as illustrated in Figure 3c. However, the nested docker boot time is a bit longer compared to docker. The nested docker is located inside a VM placed on the compute node. Therefore, the nested docker also suffers from the reduced performance of the virtualization technology.

D. Discussion

In general, booting one docker or nested docker is faster than booting a VM in an idle environment. The main reason is the number of I/O operations during their boot processes. When a VM is booted, a normal Linux boot process is in place. VM loads the kernel data from the VM disk, performs some computations, and then writes the log files to VM disk. The full Linux boot process runs inside a VM on restricted pre-assigned resources. On the contrary, when we boot a container, Docker engine initializes the file system for a container and mount the read-write layer for it. Then Docker engine assigns the CPU and memory of the container using resources of the compute node. Finally, the (c) Nested Docker Fig. 3: Boot time of multiple VMs, Dockers and Nested Dockers on 3 storage devices requested service is executed inside that container with limited resources. In brief, containers do not need to load the kernel data or go through the full Linux boot process. Plus, Docker engine prepares the environment to run a service inside a container without any restriction on the physical resources. In Figure 4, we compared the amount of I/O usage for VMs, dockers and nested dockers. The amount of I/O read shown in Figure 4a is steady for VMs and containers when the number of machines increases because they all use the shared image disk strategy. In other words, all mandatory data for their boot processes are read only once. However, VMs read much more than dockers do. Figure 4b depicts that the amount of written data of VMs and containers increase linearly. VMs also have much higher I/O writes than dockers because of the "copy-on-write" mechanism of the VM disk. When a VM writes new data to a COW image, the relevant blocks are read from the backing file, modified with the new data and written into that COW image. This mechanism leads to 2 read and 3 write operations for every single write operation on the COW image [START_REF] Garcia | Improving the performance of the qcow2 format[END_REF]. The amount of read and write data of nested docker is higher than that of a docker because a nested docker is booted inside a VM with shared image disk so that it is suffered from the COW image mechanism.

VI. BOOT TIME UNDER WORKLOADS CONTENTION

This experiment focuses on understanding the boot time of a single machine in the presence of concurrent workloads. On a compute node, first, we boot n co-machines (n ∈ [0, 15]) and then run workload on them. After that, we start one e-machine. In the case where we want to generate CPU stress, all co-machines are allocated on the same physical core with the e-machine. For the other experiments where CPU contention should be avoided (i.e., when we want to stress either only the memory, network or the I/O bus), every machine has to be assigned to different cores. In this scenario, all VMs are configured with writethrough cache mode. Because we only measure the boot duration of one VM, the parameters cache_mode and boot_policy do not have an important effect.

A. Memory Impact

As shown in Figure 5, when we increase the number of co-machines to stress the memory, the boot duration of e-machine does not change on all three storage devices. The boot time of VM is consistently slower than nested docker and docker, and nested docker boots a little bit slower than docker. In conclusion, the effect of memory competition on boot time is negligible.

On HDD (Figure 5a), the boot time of the VM that has shared image disk is 4.5 seconds while no shared image disk is 4 seconds. The overhead of checking where is the needed data to read of shared image strategy make it 0.5 seconds longer than no shared image when booting only one VM. On CEPH (Figure 5c), we also see 1 second difference between two disk creating strategies. This gap becomes bigger on CEPH because of the latency when accessing data on a remote storage device. We also have differences between two image policies in case of CPU and network contention as discussed in the next paragraph.

B. CPU Impact

Figure 6 reveals that VM boot time is impacted by CPU contention while docker and nested docker boot time are stable. For VMs, there is a clear linear correlation between the boot time of a VM and the number of co-allocated VMs, and the same increasing trend for three types of storage devices. Because all e-VM and co-VMs are assigned to one core, and the workload on each co-VM is always 100% full capacity of CPU usage, the more co-VMs running on one physical core, the more the VM has to wait until it can access the CPU core to perform the computation for the boot process. This leads to a longer boot time when we increase the number of co-VMs. In general, it takes around 4.5 seconds to boot a VM without CPU contention and increases to 40 seconds when we have 16 co-VMs generating CPU contention.

In case of containers, under CPU stress, the boot time of both docker and nested docker are not affected on any storage devices. In this experiment, to generate CPU contention, we assign all co-machines into the same physical core where the e-machine is allocated. As explained before, during a docker boot process, when docker engine prepares the environment for a docker (i.g., mounting root file system, limiting resource), the engine may not run in the core that has been stressing. Only the starting process of the containers actually run under the constrained resources and affected by the CPU contention.

C. Network Impact

As we expected, Figure 7 reveals the network contention does not have any effect on the boot time of e-machine on local storage (HDD and SSD) and only affects the remote storage device. It is reasonable since, on the local storage, the boot process of a VM or a docker does not require network operations. On CEPH, in the case of VM (Figure 8c), the e-VM uses bandwidth to load the kernel files remotely. The boot time of a VM with CEPH is quite stable around 4.5 seconds until we have 10 stressing the 10 Gigabit Ethernet interface of the compute node. When we keep increasing the network usage by growing the number of co-VMs, the remaining network bandwidth for the e-VM is limited, therefore, the boot time rises from 4.5 seconds to around 15 seconds. However, even on remote storage device -CEPH, docker and nested docker boot time are not significantly impacted under network stress. The VM boot time increases linearly with the increased number of co-VMs for both disk creation strategies. Under CPU, memory and network contention, the boot time of e-VMs with no shared image is faster than the shared image one and this gap is stable. However, the gap behaves differently under I/O contention. On HDD (Figure 8a), boot time of no shared image VM increases longer than the shared image one (from 4 seconds to over 120 seconds, compared to 4.5 seconds to 85 seconds, respectively), but the boot time between these two disk creating strategies is similar on SSD (Figure 8b). On CEPH, the overhead of checking data to read from shared image is again significant, this leads to the boot time of VM with shared image disk is longer. Docker and nested docker boot time also in-crease under I/O contention but they are faster than VMs on both HDD and SSD storage devices. The boot time of docker and nested docker increases when there is more stress on I/O, then becomes stable. In case of CEPH, the boot time of a docker is abnormally much longer than that of one VM. The reason for this phenomenon could be that there are high competitions in kernel system calls. However, to fully explain this, a number of intensive experiments has to be conducted.

D. I/O Disk Impact

E. Discussion

Workloads that are already executed on a compute node obviously increase the time to boot an additional VM/docker and this should be considered. While comparing the workloads together, our results show that VM, docker and nested docker boot time introduce negligible overhead for memory and network bandwidth (except in the case of remote attached volume such as CEPH). I/O disk is the most influence factor for both VM and docker on different types of storage devices. Even though the impact of CPU is rather small as compared to I/O factor in case of VM (docker is not impacted by CPU contention), we cannot simply ignore CPU factor, since it is still significant enough to alter the boot time. In general, dockers have better boot time compared to nested dockers.

VII. CONCLUSION

Performing reproducible experiments on cloud computing platforms imply complex tasks which require to evaluate a large number of configurations. The analysis of VMs and containers boot times is a such kind of this task. In this work, we presented how we conducted, in a softwaredefined manner, more than 14400 experiments.

The gathered results give us a comprehension about the VM boot time. The VM boot duration is not only affected by the co-workloads and the number of VMs simultaneously deployment but also the parameters that we use to configure VMs. Furthermore, on different storage devices, booting VMs with the same configuration even have varied behaviors. Having the comprehension of the VM boot time will allow us to choose the best way to boot new VMs within a cloud infrastructure. When comparing the boot time between containers and VMs, it is obvious that containers boot much faster than VMs. However, the boot duration of containers also has an increasing trend like the VM boot time when we boot multiple VMs/containers at the same time or under a workload contention environment. Especially, I/O throughput is the most significant factor on both VMs and containers boot duration. This behavior of VMs/containers boot time should be taken into account when we want to deploy new VMs/containers.

In this paper, we also discussed the boot process of VM and docker. The initialization of dockers does not perform with restricted resources. Plus, we highlighted the difference in the amount of loaded data between VMs and dockers during their boot process. These two observations could be applied to propose improvements for VM boot time. While containers can be booted faster than a VM even under I/O intensive environment, VM boot time still plays a major role in provisioning resources on demand within a cloud infrastructure. Instead of using a full Linux boot process for a VM, mitigating the number of I/O operations is a promise direction to achieve the same effect as containers.

Fig. 1 :

 1 Fig. 1: Engine Architecture

  • boot_policy: defines the way to boot e-VMs -(a) one then other: the first VM is booted completely, then we boot the rest of VMs simultaneously. -(b) all at once: all VMs are booted at the same time.

Fig. 2 :

 2 Fig. 2: Boot time of VMs with different installations on three storage devices

  I/O write Fig. 4: I/O usage during boot process of multiple machines

Fig. 5 :Fig. 6 :

 56 Fig. 5: Boot time of 1 VM, Docker and Nested Docker on three storage devices under memory contention

InriaFig. 8 :

 8 Fig. 8: Boot time of 1 VM, Docker and Nested Docker on three storage devices under I/O contention

Figure 8

 8 Figure 8 depicts the boot time of a machine on three storage devices under I/O stress. Similarly to other experiments, a docker boots faster than a VM on different storage devices under high I/O contention.The VM boot time increases linearly with the increased number of co-VMs for both disk creation strategies. Under CPU, memory and network contention, the boot time of e-VMs with no shared image is faster than the shared image one and this gap is stable. However, the gap behaves differently under I/O contention. On HDD (Figure8a), boot time of no shared image VM increases longer than the shared image one (from 4 seconds to over 120 seconds, compared to 4.5 seconds to 85 seconds, respectively), but the boot time between these two disk creating strategies is similar on SSD (Figure8b). On CEPH, the overhead of checking data to read from shared image is again significant, this leads to the boot time of VM with shared image disk is longer. Docker and nested docker boot time also in-

  .

	• image_policy : is the way to create a VM
	disk. There are two strategies:
	-(a) shared image: a VM disk has two
	components: a backing file and a COW
	(copy-on-write) image. Backing file is an
	original VM image (VMI) and shared
	between many VMs. When a VM gener-
	ates read accesses, the hypervisor checks
	if the needed data is not on the COW
	image, it will read from the backing file.
	All write operations from VM are stored
	on the COW image directly;
	-(b) no shared image: a VM disk image is

http://vm5k.readthedocs.io/

RR n°9221

http://people.sc.fsu.edu/ jburkardt/c_src/linpack_bench/ linpack_bench.html

http://icl.cs.utk.edu/llcbench/cachebench.html

http://people.seas.harvard.edu/~apw/stress/

https://iperf.fr/

https://docs.docker.com/engine/reference/commandline/cli/ Inria

Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

ACKNOWLEDGMENT

All 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 (see https://www.grid5000.fr). This work is also a part of the BigStorage project, H2020-MSCA-ITN-2014-642963, funded by the European Commission within the Marie Skłodowska-Curie Actions framework.


Eric Badouel
email: eric.badouel@inria.fr

Rodrigue Aimé

Djeumen Djatcha
email: djeumenr@yahoo.fr

Modular Design of Domain-Specific Languages using Splittings of Catamorphisms ⋆

Keywords: Abstract Syntax Trees, Catamorphisms, Bekić's Theorem, Component-based Design, Domain Specific Languages

Language oriented programming is an approach to software composition based on domain specific languages (DSL) dedicated to specific aspects of an application domain. In order to combine such languages we embed them into a host language (namely Haskell, a strongly typed higher-order lazy functional language). A DSL is then given by an algebraic type, whose operators are the constructors of abstract syntax trees. Such a multi-sorted signature is associated to a polynomial functor. An algebra for this functor tells us how to interpret the programs. Using Bekić's Theorem we define a modular decomposition of algebras that leads to a class of parametric multi-sorted signatures, associated with regular functors, allowing for the modular design of DSLs.

Introduction

Component-based design is acknowledged as an important approach to improving the productivity in the design of complex software systems, as it allows predesigned components to be reused in larger systems [START_REF] Krueger | Software reuse[END_REF]. Instead of constructing standalone applications the focus is on the use of libraries viewed as toolboxes for the development of software product lines dedicated to some specific application domain. Using such "components on the shelf" improves productivity in developing software as well as the adaptability of the produced software with respect to changes. Thus intellectual investment is better preserved. In order to avoid redundancies a well designed domain specific library should have generic constituents (using parametrization, inheritance or polymorphism) and then it can be seen as a small programming language in itself. Language oriented programming [START_REF] Ward | Language-oriented programming[END_REF][START_REF] Dmitriev | Language oriented programming: The next paradigm[END_REF] is an approach to software composition based on domain specific languages (DSL) dedicated to specific aspects of an application domain. A DSL captures the semantics of a specific application domain by packaging reusable domain knowledge into language features. It can be used by an expert of that domain who is provided with familiar notations and concepts rather that confronted with a general purpose programming language.

Many DSLs have been designed and used in the past decades, however their systematic study is a more recent concern. The design and implementation of a programming language, even a simple one, is a difficult task. One has to develop all the tools necessary to support programming and debugging in that language: a compiler for source text analysis, type checking, generation and optimisation of code, handling of errors... and also related tools for the generation of documentation, the integration of graphic and text editing facilities, the synchronization of multiple partial views, etc. Language adaptivity is another concern: it is very hard to make a change to the design of a programming language. However some domains of expertise may evolve in time, calling for frequent redesigns of the associated DSL: will we have to go through the process all over again every time? Finally, it might be difficult, if not impossible, to make different DSLs collaborate within some application even though most applications do involve different domains of expertise.

To alleviate these difficulties Hudak [START_REF] Hudak | Building domain-specific embedded languages[END_REF] suggested embedding the DSL into a chosen general-purpose host language; and coined the expression Domain-Specific Embedded Languages (or DSEL) to qualify them. Each DSEL inherits from the host language all parts that are not specific to the domain. It also inherits the compiler and the various tools used as a support to programming. Finally each DSEL is integrated into a general-purpose language, namely its host language; and several DSELs can communicate through their common host language. A higher-order strongly-typed lazy functional language like Haskell is an ideal host language since it can be viewed as a DSL for denotational semantics: a language that can be used to describe the semantics of various programming languages and thus also to combine them.

Recent language workbenches [START_REF] Fowler | Language workbenches: The killer-app for domain specific languages[END_REF] like Intentional Programming [16,[START_REF] Van Wyk | Intensional programming: A host of language features[END_REF] or the Meta Programming System [START_REF] Dmitriev | Language oriented programming: The next paradigm[END_REF] from JetBrains envisage a system where one could systematically scope and design DSLs with the ability to compose a language for a particular problem by loading DSLs as various plug-ins. Each such plugin would incorporate meta-programming tools allowing one to program in the corresponding DSL (browsing, navigating and editing syntax, extracting multiple views or executable code). The core of such intensional representations are abstract syntax trees associated to a multi-sorted signature whose operators are the basic contructions of the language. These operators are usually interpreted as closed higher-order functions (i.e., combinators). Following the higher-order interpretation of attribute grammars [START_REF] Johnsson | Attribute grammars as functional programming paradigm[END_REF][START_REF] Fokkinga | A Translation from Attribute Grammars to Catamorphisms[END_REF][START_REF] Backhouse | A functional semantics of attribute grammars[END_REF] we shall assume that these combinators derive from the semantic rules of an attribute grammar built on the multi-sorted signature.

Combining such DSLs requires considering a global grammar such that each DSL is associated with some subgrammar. The global grammar need not be constructed explicitly but we should be able to evaluate its abstract syntax trees by combining the catamorphisms of the corresponding subgrammars.

In this paper we address this problem by introducing the so-called modular grammars. The initial algebra of the polynomial functor associated with the operators of the language coincides with its least fixed-point. This fixed-point can be computed by a method of substitution using Bekić's Theorem [START_REF] Bekic | Definable operation in general algebras, and the theory of automata and flowcharts[END_REF]. By doing so the system of polynomial functors is transformed into a related system of regular functors. We introduce a splitting operation on algebras producing an algebra for the resulting system of regular functors from an algebra of the original system of polynomial functors. This transformation preserves the interpretation function (catamorphism).

Modular Domain Specific Languages

The syntax of a DSL is given by a multi-sorted signature Σ = (S, Ω) consisting of a set of sorts S and a set of operators ω ∈ Ω where each operator has an arity in S * and a sort in S. We let Ω(s 1 • • • s n , s) denote the set of operators ω ∈ Ω with arity s 1 • • • s n ∈ S * and sort s ∈ S. Let us first assume that each sort appears as the sort of some operator. Then the signature can be associated with the endofunctor

F : |Set| S → |Set| S such that F (X) s = ω∈Ω(s1•••sn,s) X s1 × . . . × X sn which we may write F (X) s = {ω(x 1 , . . . , x n ) | ω ∈ Ω(s 1 • • • s n , s), (∀1 ≤ i ≤ n) x i ∈ X si }
where ω(x 1 , . . . , x n ) is used to denote the element (x 1 , . . . , x n ) ∈ X s1 × . . . × X sn that lies in the component indexed by ω. It is a polynomial functor (a sum of products) and it has a least fixed-point F † made of the sorted Σ-trees. We readily show by induction that it is also the initial algebra. Hence there exists a unique morphism of F -algebra ([ϕ]) F : F † → A, called a catamorphism associated with each F -algebra ϕ : F (A) → A. Note that such an F -algebra is nothing more than a Σ-algebra, namely a carrier set A s associated with each sort s ∈ S together with an interpretation function ω ϕ : A s1 × A sn → A s for each ω ∈ Ω(s 1 • • • s n , s). And the catamorphism amounts to interpreting the tree in the algebra by replacing each symbol ω by its interpretation ω ϕ and evaluating the resulting expression.

Sorts that are used (they appear in arities of some operator) but not defined (they do not coincide with the sort of any operator) are called the parameters of the signature. When parameters exists the corresponding functor is no longer an endofunctor but has the form F : |Set| p+n → |Set| n where we have assumed an enumeration of the sorts with parameters coming first. Since |Set| p+n ∼ = |Set| p × |Set| n , functor F can be viewed as a parametric endofunctor F : |Set| p → (|Set| n → |Set| n ), and we can apply the results of the above discussion to each of the endofunctors F ζ for ζ ∈ |Set| p . We readily verify that the fixed-point construction gives rise to a functor (the so-called type functor such that

F † ζ = (F ζ) † ) and the isomorphim Fζ F † ζ ∼ = F † ζ is natural in ζ. We let in F,ζ : Fζ F † ζ → F † ζ and out F,ζ : F † ζ → Fζ F † ζ
([ϕ]) F,ζ • in F,ζ = ϕ • Fζ ([ϕ]) F,ζ
Haskell functions are however interpreted in the category H = DCPO ⊥ of pointed dcpos and continuous functions. Thus we should replace the category of sets and functions in the above discussion by H. However (see [START_REF] Plotkin | Post-graduate lectures notes in advanced domain theory[END_REF][START_REF] Abramsky | Handbook of Logic in Computer Science[END_REF]) the category of pointed dcpos and continuous functions does not have coproducts and thus the above functorial interpretation of a signature does not seem to be possible. The trick used by Haskell to represent its data types is to resort to the subcategory C = DCPO ⊥! of pointed dcpos and strict continuous functions. Finite products in C are given by the cartesian products and the finite coproduct of two dcpos is their coalesced sum A ⊕ B obtained from their disjoint union by identifying their respective least elements: ⊥ A⊕B = ⊥ A = ⊥ B . The lifting operator (-) ⊥ consists in adding a new least element to a given dcpo: A ⊥ = A ⊎ {⊥}. Finally, we let the sum of pointed dcpos be given by 1≤i≤n

A i = (A 1 ) ⊥ ⊕ • • • ⊕ (A n ) ⊥ or equivalently by 1≤i≤n A i = (A 1 ⊎ • • • ⊎ A n ) ⊥ .
When this sum has only two operands it will be written with an infix notation: A+ B = (A ⊎ B) ⊥ . However, we should pay attention to the fact that this binary operation is not associative and that the corresponding n-ary operation cannot be presented as an iterated application of the binary one: we rather have a family of operators indexed by non-negative integers. The unary sum coincides with the lifting operator and the nullary sum gives 1 = () ⊥ = {⊥, ()}. With these notations the following data type definition in Haskell is associated with the (parametric) polynomial functor F :

C 3 → C 2 such that F (A, T, F ) = ((A × F ) ⊥ , 1 + (T × F )). Now, by observing that C(A ⊥ , B) ∼ = H(A, B)
we deduce that an F -algebra ϕ : F ζα → α boils down to a continuous Σ-algebra in the sense that all the carrier sets are pointed dcpos and the interpretation functions are continuous functions. Hence the constituents of an algebra can be expressed by Haskell functions as intended.

All mentioned results holds more generally for locally continuous functors and in particular for the class of regular functors which is the least family of functors from C n to C m that contains the projections and is closed by sum, product, composition and the formation of type functors.

In the remaining parts of this section we introduce an example that will help us to explain our approach to modularity of domain specific languages embedded in Haskell.

DSL associated with an algebra

Let us consider a toy language for assembling elementary boxes. The following is an Haskell definition of a data structure for such boxes. Thus a box is either an elementary box (which we suppose has a unit size: its depth and height is 1) or is obtained by composing two sub-boxes. Two boxes can be composed either vertically with a left or right alignment or horizontally with a top or bottom alignment. The corresponding signature has a unique sort (Box), a constant standing for an elementary box and four binary operators associated with the various ways of assembling two sub-boxes in order to obtained a new box. The related notions of algebra and evaluation morphism can be expressed in Haskell as follows.

data AlgBox a = AlgBox {elembox :: a, comp ::

Pos -> a -> a -> a} eval :: AlgBox a -> Box -> a eval (AlgBox elembox comp) = f where f Elembox = elembox f (Comp pos box1 box2) = comp (f box1) (f box2)
Now we need to make explicit the semantic aspects attached to a box: these are methods to extract useful information from a box. For instance we might be interested in representing a box by the list of origins of its elementary boxes, which of course depends on its own origin. Another property is the size of the box given by its height and depth. Thus a semantical domain for boxes would be an element of the following class: An implementation of the language of boxes is given by an algebra whose domain of interpretation for boxes is an element of the class SemBox. One needs to specify the computations of the attributes size and list of a given box. For that purpose we use an attribute grammar that provides the required algebra following the higher-order functional approach to attribute grammars introduced in [START_REF] Johnsson | Attribute grammars as functional programming paradigm[END_REF][START_REF] Fokkinga | A Translation from Attribute Grammars to Catamorphisms[END_REF][START_REF] Backhouse | A functional semantics of attribute grammars[END_REF]. and the expression list box (P oint 0 0) returns the corresponding list of located elementary boxes when the box is positioned at the origin.

list box (Point 0 0)= [Point{xcoord=0,ycoord=1}, Point{xcoord=1 ,ycoord=1}, Point{xcoord=0,ycoord=2}, Point{xcoord=3,ycoord=0}, Point{xcoord=2,ycoord=1}, Point{xcoord=2,ycoord=2}, Point{xcoord=3,ycoord=2}]
Therefore we have interpreted some static data structure as an active object on which one may operate using the corresponding methods ebox :: SBox cmp :: P os → SBox → SBox → SBox size :: SBox → Size list :: SBox → P oint → [P oint] (together with the derived operators: hb, ht, vl, and vr and their inductive extensions). That set of functions constitutes the interface of this embedded tiny language with its host language (Haskell).

Note that this language contains both the interpretation functions of the algebra (ebox and cmp) and the methods of the considered semantic domain (size and list). The description of the datatype SBox is not exported by the module dedicated to the language of boxes but only the functions that allows to build such boxes (ebox and cmp) or to use them (size and list).

Extension of a domain specific language

Now, imagine that we seek to extend this language to allow an elementary box to contain an image data Image = Image {image :: a -> Point -> Maybe Color, bb:: a -> Size} represented as a function that returns the color of the point whose coordinates relative to the upper left corner of the image are given as arguments. This function returns the undefined value N othing (interpreted as "transparency") if the coordinates exceed the bounding box of the image. However, the image itself may contain some transparent parts. In addition we may wish to allow sub-boxes to be centered when composed (horizontally and vertically, see Fig. 2). The interface of a DSL is given by its algebra. An algebra consists of the choice of a carrier set for each sort (the semantic domains of interpretation) and a function of interpretation for each operator. Note that the precise definitions of the carrier sets are not made visible. They are represented as abstract data types (given by the two functions list and size for the basic version of our example). If we want to reuse this DSL without modifying the existing code we should kept the carrier sets unchanged. We may associate new methods with the carrier sets of the algebra. But we are limited in this if the carrier sets cannot simultaneously be extended. As far as the type SBox is concerned, it is clear that any such function should be definable directly in terms of list and size; so these are just derived methods. Still, we may envisage adding new operators. For instance we may add the two operators vc = Vert (Vpos Center ) and hc = Hor (Hpos Center) to allow for extra ways of combining boxes. Then we should be able to extend the interpretation functions (elembox and comp) for handling these new operators while preserving the existing code. This problem has been referred to as the "expression problem" by Philip Walder:

Hor

The goal is to define a data type by cases, where one can add new cases to the data type and new functions over the datatype, without recompiling existing code, and while retaining static type safety.

An elegant solution to this problem has been proposed by Wouter Swierstra in [START_REF] Swierstra | Data types à la carte[END_REF] using a method akin to an implementation of the visitor pattern. Nonetheless this method is no longer applicable if we are forced to reshape the carrier sets of the algebra, which is indeed the case for the extension considered here. We may even face more drastic changes imposed by the introduction of new operators. For instance the semantic representation of a box as a of elementary boxes (containing an image of a given size) will not allow us to add a frame (of a given width and color) around a box using a function:

f rame :: SBox → Double → Color → SBox
The only reasonable choice to interpret the corresponding boxes seems to be the following:

class SemBox a where at :: a -> Point -> Image size :: a -> Size where box ′ at ′ pt provides the image formed by anchoring the box at the given point. As in the preceding case, we have no other choice than to completely overwrite the interpretation functions elembox and comp.

Decomposition of catamorphisms

Modular grammar

The above example and discussion make it clear that a modular approach to DSLs requires that a basic module is dedicated to a specific set of sorts. Its interface is given by an algebra presented both by a set of interpretation functions for the operators and by methods that allow using objects of the carrier sets of the algebra. To be more precise let L be a language with signature Σ = (S, Ω) and F : C p+n → C n be its associated polynomial functor. Suppose that n = n 1 + n 2 and that the sorts S 2 corresponding to indices in n 2 are those defined by a particular module L 2 of L. Note that S = S 0 ⊎ S 1 ⊎ S 2 where S 0 , such that |S 0 | = p are the parameters of the grammar and S 1 , such that |S 1 | = n 1 , are the sorts defined by L outside the considered module. The signature of L 2 is Σ 2 = (S, Ω 2 ) where Ω 2 is the set of operators in Ω whose sorts belong to S 2 . Its associated polynomial functor is the composition of F with the second projection π (n1,n2) 2

: C n → C n2 , namely F 2 = π (n1,n2) 2
• F : C p+n → C n2 . Note that the parameters of Σ 2 are the elements of S 0 ∪ S 1 . Thus the sorts defined outside the module are extra parameters for this module. Of course a module would normally be given on a smaller set of sorts S ′′ ⊆ S because it is usually defined prior to the language that uses it and we cannot anticipate all the potential usages of a module. Nonetheless, and for ease of presentation we assume as above that S ′′ = S. Indeed any signature can be viewed as a signature over a larger set of sorts where the additional sorts play the role of extra parameters, even though the interpretation functions will not use these arguments.

In order to implement language L, assuming that its submodule L 2 already exists, we have to define the interpretation functions for the operators in \ Ω 2 , namely to provide an algebra for the functor

F 1 = π (n1,n2) 1 • F : C p+n → C n1 .
The parameters of this polynomial functor are the elements of S 0 ∪ S 2 . However we should distinguish between the parameters of the overall language L whose carrier sets ζ ∈ |C| p can be arbitrarily chosen (parametric polymorphism) the sorts of S 2 whose value should lie in F † 2 ζα 1 if α 1 ∈ |C| n1 corresponds to the carrier sets for sorts in S 1 . Hence the data that is needed to reconstruct the overall language from its submodule is an algebra for the residual functor F/F 2 defined in the following categorical version of Bekić's Theorem [START_REF] Bekic | Definable operation in general algebras, and the theory of automata and flowcharts[END_REF].

Theorem 1. Let a locally continuous functor

F : C p+n → C n with n = n 1 + n 2 be decomposed on the form F = F 1 , F 2 where F 1 = π (n1,n2) 1 • F : C p+n → C n1 and F 2 = π (n1,n2) 2 • F : C p+n → C n2 where functors π (n1,n2) 1 : C n → C n1 and π (n1,n2) 2 : C n → C n2 are the two canonical projections. Then F † ζ = H ζ × K ζ where F/F 2 = F 1 • id p+n1 , F † 2 : C p+n1 → C n1 H = (F/F 2 ) † : C p → C n1 F ′ 2 = F 2 • ( id p , H × id n2 ) : C p+n2 → C n2 K = F ′ † 2 : C p → C n2
and id ℓ : C ℓ → C ℓ stands for the identity functor of C ℓ .

Bekić's Theorem corresponds to the classical method of resolution by substitution. Indeed let y, x 1 and x 2 be variables ranging respectively over |C| p , |C| n1 and |C| n2 . Variable x 1 of system F becomes a parameter for its subsystem F 2 . By solving the latter we obtain a parametric solution F † 2 : C p+n1 → C n2 . We substitute this solution for variable x 2 in the system F 1 thus leading to a new system

F/F 2 = F 1 • id p+n1 , F † 2 : C p+n1 → C n1
in which variable x 2 no longer appears. Solving this new system provides us with the x 1 component of the solution of the original system thus given by H = (F/F 2 )

† : C p → C n1 . We can substitute that value into F 2 in order to derive the system

F ′ 2 = F 2 • ( id p , H × id n2 ) : C p+n2 → C n2
whose resolution gives the x 2 component of the solution of the original system. The following lemma says that the x 2 component of the solution of the original system can alternatively be obtained by substituting the x 1 component of the solution of the original system (given by H) in the parametric solution

F † 2 : C p+n1 → C n2 .
The condition expressed by this lemma appears in several axiomatizations of parametric fixed-point operators [START_REF] Simpson | Complete axioms for categorical fixed-point operators[END_REF], and in particular in the theory of traced monoidal categories [START_REF] Joyal | Traced monoidal categories[END_REF].

Lemma 1. K ζ ≃ F † 2 ζ (H ζ) Proof. First notice that F ′ 2 ζ (Kζ) = F 2 ζ (Hζ) (Kζ). The initial F ′ 2 , ζ-algebra in F ′ 2 ,ζ : F 2 ζ (Hζ) (Kζ) → Kζ is thus an F 2 -algebra with parameters ζ × Hζ. We let ι 1 = in F ′ 2 ,ζ F2,ζ×Hζ : F † 2 (H ζ) → Kζ
be the corresponding catamorphism which, by definition, satisfies

ι 1 • in F2,ζ×Hζ = in F ′ 2 ,ζ • F 2 ζ (Hζ) ι 1 Symmetrically, since F 2 ζ(Hζ) F † 2 ζ (Hζ) = F ′ 2 ζ F † 2 ζ (Hζ) , we deduce that the initial F 2 , ζ × Hζ-algebra in F2,ζ×Hζ : F 2 ζ(Hζ) F † 2 ζ (Hζ) → F † 2 ζ (Hζ) is an F ′ 2 , ζ-algebra. Let ι 2 = ([in F2,ζ×Hζ ]) F ′ 2 ,ζ : Kζ → F † 2 ζ (Hζ) denote the corresponding catamorphism which, by definition, satisfies ι 2 • in F ′ 2 ,ζ = in F2,ζ×Hζ • F 2 ζ(Hζ)ι 2 .
On the one hand it follows

ι 1 • ι 2 • in F ′ 2 ,ζ = ι 1 • in F2,ζ×Hζ • F 2 ζ(Hζ)ι 2 = in F ′ 2 ,ζ • F 2 ζ (Hζ) ι 1 • F 2 ζ(Hζ)ι 2 = in F ′ 2 ,ζ • F 2 ζ (Hζ) (ι 1 • ι 2 ) = in F ′ 2 ,ζ • F ′ 2 ζ (ι 1 • ι 2 )
and thus

ι 1 • ι 2 = in F ′ 2 ,ζ F ′ 2 ,ζ = id Kζ .
On the other hand

ι 2 • ι 1 • in F2,ζ×Hζ = ι 2 • in F ′ 2 ,ζ • F 2 ζ (Hζ) ι 1 = in F2,ζ×Hζ • F 2 ζ(Hζ)ι 2 • F 2 ζ (Hζ) ι 1 = n F2,ζ×Hζ • F 2 ζ(Hζ) (ι 2 • ι 1 ) and thus ι 2 • ι 1 = ([in F2,ζ×Hζ ]) F2,ζ×Hζ = id F † ζ(Hζ) . The pair of morphisms ι 1 : F † 2 ζ (H ζ) → Kζ and ι 2 : Kζ → F † 2 ζ (Hζ) thus constitutes the required isomorphism K ζ ≃ F † 2 ζ (H ζ). ⊓ ⊔ Corollary 1. F † = (F/F 2 ) † ⋊ F † 2
where operation ⋊ is given by Definition 1. The semidirect product (or cascaded composition) of functors H : C p → C n and T : C p+n → C m is given by

H ⋊ T = H, T • id p , H : C p → C n+m
A module should be able to import other modules. This means that we should be able to apply a hierarchical decomposition of a signature. However, because of the presence of the type functor F † 2 , we shall no longer stay within the frame of polynomial functors. Nonetheless, if we start from polynomial functors all constructions involved in Beckić's Theorem remain in the family of regular functors. We thus model a modular grammar as a combination of a polynomial functor, that describes the operators whose sorts are locally defined, and a regular functor associated with the imported definitions.

F G = F • id p+n , D : C p+n → C n
We let F (G) = F and D(G) = D denote the respective components of modular grammar G.

The following proposition states that the family of modular grammars is closed by the operation of decomposition of a system into a subsystem and the corresponding residual system as described in Bekić's Theorem.

Proposition 1. Let G = (F, D) be a modular grammar with polynomial functor F : C p+n+m → C n and regular functor D :

C p+n → C m . If n = n 1 + n 2 then π (n1,n2) 2 • F G = F G2 and F G/G2 = F G /F G2 where the second projection G 2 = π (n1,n2) 2 (G) of modular grammar G is given by F (G 2 ) = π (n1,n2) 2 • F (G) : C (p+n1)+n2+m → C n2 D(G 2 ) = D(G) : C (p+n1)+n2 → C m
and the residual operation is defined as

F (G/G 2 ) = π (n1,n2) 1 • F (G) : C p+n1+(n2+m) → C n1 D(G/G 2 ) = F † G2 ⋊ D(G) : C p+n1 → C n2+m
The situation is depicted in Figure 3 where we note that the sorts defined by the residual grammar G/G 2 (its outputs) are additional parameters for the subgrammar G 2 , whereas the outputs of G 2 are additional imported sorts for

G/G 2 Proof. The identity π (n1,n2) 2 • F G = F π (n 1 ,n 2 ) 2 (G) is immediate. F G /F G2 = π (n1,n2) 1 • F G • id p+n1 , F † G2 = π (n1,n2) 1 • F (G) • id p+n1+n2 , D(G) id p+n1 , F † G2
F G/G2 = F (G/G 2 ) • id p+n1 , D(G/G 2 ) = π (n1,n2) 1 • F (G) • id p+n1 , F † G2 ⋊ D(G) = π (n1,n2) 1 • F (G) • id p+n1 , F † G2 , D(G) • id p+n1 , F † G2 In order to prove F G /F G2 = F G/G2 if suffices to show that id p+n1+n2 , D(G) id p+n1 , F † G2 = id p+n1 , F † G2 , D(G) • id p+n1 , F †

G2

These two expressions are equal because they give rise to the same results when composed with the three projections from C (p+n1)+n2+m to C p+n1 , C n2 , and C m respectively:

π p+n1,n2,m 1 • E = id p+n1 π p+n1,n2,m 2 • E = F † G2 π p+n1,n2,m 3 • E = D(G) • id p+n1 , F † G2 ⊓ ⊔ By Corollary 1 it follows that Corollary 2. F † G = F † G/G2 ⋊ F † G2

Decomposition of algebras

Using Bekić's Theorem we now define a decomposition of algebras.

Definition 3. We let F : C p+n → C n be a locally continuous functor with n = n 1 + n 2 . Let moreover Φ :

F ζα 1 α 2 → α 1 × α 2 be an F ζ-algebra (ζ ∈ |C| p ) on the domain α = α 1 × α 2 (α 1 ∈ |C| n1
, and α 2 ∈ |C| n2 ). Φ can be decomposed into

ϕ 1 = π (n1,n2) 1 (Φ) : F 1 ζ α 1 α 2 → α 1 ϕ 2 = π (n1,n2) 2 (Φ) : F 2 ζ α 1 α 2 → α 2 The (n 1 , n 2 )-splitting of Φ is the pair consisting of the (F/F 2 ) ζ-algebra of domain α 1 π F/F2 Φ ϕ 1 • F 1 ζ α 1 (|ϕ 2 |) F2,ζ×α1 : F 1 ζ α 1 F † 2 ζ α 1 → α 1 together with the F 2 (ζ × α 1 )-algebra of domain α 2 π F2 Φ ϕ 2 : F 2 ζ α 1 α 2 → α 2
The operation of decomposition of algebras is thus given as:

Split (n.m) : Alg F,ζ (α 1 × α 2 ) → Alg F/F2,ζ (α 1 ) × (Alg F2,ζ×α1 (α 2 )) Split (n1,n2) Φ = π F/F2 Φ, π F2 Φ Thus an algebra Φ = ϕ 1 × ϕ 2 : F ζα 1 α 2 → α 1 × α 2 is decomposed into an algebra π F2 Φ = ϕ 2 : F 2 ζ α 1 α 2 → α 2
for the "subsystem" F 2 together with an algebra π F/F2 Φ : F/F 2 ζα 1 → α 1 for the "residual system" F/F 2 . The following result shows that the catamorphism (evaluation function) associated with the algebra Φ for the overall system can be reconstructed from the catamorphisms associated respectively with π F2 Φ and π F/F2 Φ using a semidirect product operation which we first introduce.

In Definition 1 we defined the semidirect product of two functors H :

C p → C n and T : C p+n → C m as H ⋊ T = H, T • id p , H : C p → C n+m
: C p+n → C m is the map f ⋊ g : (H ⋊ T ) ζ → α × β given by (f ⋊ g) = f × (g • T ζf ).
Using this operation we can now state Theorem 2. Up to the isomorphisms

F † ζ = Hζ × Kζ and Kζ = F † 2 ζ (Hζ) one has ([Φ]) F,ζ = π F/F2 Φ F/F2,ζ ⋊ ([π F2 Φ]) F2,ζ×α1 Lemma 2. Up to the isomorphism F † ζ = Hζ × Kζ the initial algebra in F,ζ : F ζ F † ζ → F † ζ decomposes to the form in F,ζ = in H,ζ × in K,ζ where in H,ζ : F 1 ζ(Hζ)(Kζ) → Hζ and in K,ζ : F 2 ζ(Hζ)(Kζ) → Kζ are respectively given by in H,ζ = in F/F2,ζ • (F 1 ζ(Hζ)ι 2 ) and in K,ζ = in F ′ 2 ,ζ .
Proof. The initial algebra is an isomorphism and the converse also holds true (any algebra which is an isomorphism is initial) when we have uniqueness of fixed-point (up to isomorphism) which is indeed the case here.

in H,ζ = in F/F2,ζ • (F 1 ζ(Hζ)ι 2 ) : F 1 ζ(Hζ)(Kζ) → Hζ and in K,ζ = in F ′ 2 ,ζ : F 2 ζ(Hζ)(Kζ) → Kζ are isomorphisms and thus in H,ζ × in K,ζ : F ζ(Hζ)(Kζ) → Hζ × Kζ is the initial algebra of functor F . ⊓ ⊔ Corollary 3. Up to the isomorphism F † ζ = Hζ × Kζ, the two parts f : Hζ → α 1 and g : Kζ → α 2 of catamorphism ([Φ]) F,ζ = f × g are characterized by f • in H,ζ = ϕ 1 • F ζf g and g • in K,ζ = ϕ 2 • F 2 ζf g.
Lemma 3. For any morphism f : Hζ → α 1 one has

([ϕ 2 • F 2 ζf α 2 ]) F ′ 2 ,ζ = ([ϕ 2 ]) F2,ζ×α1 • F † 2 ζf • ι 2 : Kζ → α 2 and that morphism g(f ) satisfies g(f ) • in K,ζ = ϕ 2 • (F 2 ζ f g(f )). Proof. By definition F † 2 ζf = in F2,ζ×α1 • F 2 ζ f F † 2 ζα 1 F2,ζ×Hζ
and that morphism satisfies

F † 2 ζf • in F2,ζ×Hζ = in F2,ζ×α1 • F 2 ζ f F † 2 ζα 1 • F 2 ζ (Hζ) F † 2 ζf
It follows that

([ϕ 2 ]) F2,ζ×α1 • F † 2 ζf • ι 2 • in F ′ 2 ,ζ = ([ϕ 2 ]) F2,ζ×α1 • F † 2 ζf • in F2,ζ×Hζ • F 2 ζ(Hζ)ι 2 = ([ϕ 2 ]) F2,ζ×α1 • in F2,ζ×α1 • F 2 ζ f F † 2 ζα 1 • F 2 ζ (Hζ) F † 2 ζf • F 2 ζ(Hζ)ι 2 = ϕ 2 • F 2 ζα 1 ([ϕ 2 ]) F2,ζ×α1 • F 2 ζ f F † 2 ζα 1 • F 2 ζ (Hζ) F † 2 ζf • ι 2 = ϕ 2 • F 2 ζf α 2 • F 2 ζ (Hζ) ([ϕ 2 ]) F2,ζ×α1 • F 2 ζ (Hζ) F † 2 ζf • ι 2 = (ϕ 2 • F 2 ζf α 2 ) • F 2 ζ (Hζ) ([ϕ 2 ]) F2,ζ×α1 • F † 2 ζf • ι 2 and thus ([ϕ 2 • F 2 ζf α 2 ]) F ′ 2 ,ζ = ([ϕ 2 ]) F2,ζ×α1 • F † 2 ζf • ι 2 . If we let g(f ) ([ϕ 2 ]) F2,ζ×α1 • F † 2 ζf • ι 2 denote this morphism, we deduce g(f ) • in K,ζ = ϕ 2 • F 2 ζf α 2 • F 2 ζ (Hζ) g(f ) = ϕ 2 • F 2 ζ f g(f ) because in K,ζ = in F ′ 2 ,ζ . ⊓ ⊔ Lemma 4. If f : Hζ → α 1 and g : Kζ → α 2 are, up the isomorphism F † ζ = Hζ × Kζ, the two parts of catamorphism ([Φ]) F,ζ = f × g then f = ϕ 1 • F 1 ζα 1 ([ϕ 2 ]) F2,ζ×α1 F/F2,ζ and g = ([ϕ 2 • F 2 ζf α 2 ]) F ′ 2 ,ζ .
Proof. By Corollary 3 the two parts f : Hζ → α 1 and g : Kζ → α 2 of the catamorphism (

[Φ]) F,ζ = f × g are characterized by f • in H,ζ = ϕ 1 • F ζf g and g • in K,ζ = ϕ 2 • F 2 ζf g. Set f ′ = ϕ 1 • F 1 ζα 1 ([ϕ 2 ]) F2,ζ×α1 F/F2,ζ and g ′ = g(f ′ ) = ([ϕ 2 • F 2 ζf ′ α 2 ]) F ′ 2 ,ζ . By the preceding lemma g ′ • in K,ζ = ϕ 2 • F 2 ζ f ′ g ′ , moreover f ′ • in H,ζ = f ′ • in F/F2,ζ • F 1 ζ(Hζ)ι 2 = ϕ 1 • F 1 ζα 1 ([ϕ 2 ]) F2,ζ×α1 • F 1 ζf ′ F † 2 ζf ′ • F 1 ζ(Hζ)ι 2 = ϕ 1 • F 1 ζα 1 ([ϕ 2 ]) F2,ζ×α1 • F 1 ζα 1 F † 2 ζf ′ • F 1 ζf ′ F † 2 ζ(Hζ) • F 1 ζ(Hζ)ι 2 = ϕ 1 • F 1 ζα 1 ([ϕ 2 ]) F2,ζ×α1 • F 1 ζα 1 F † 2 ζf ′ • F 1 ζα 1 ι 2 • F 1 ζf ′ (Kζ) = ϕ 1 • F 1 ζα 1 ([ϕ 2 ]) F2,ζ×α1 • F † 2 ζf ′ • ι 2 • F 1 ζf ′ (Kζ) = ϕ 1 • F 1 ζα 1 g ′ • F 1 ζf ′ (Kζ) = ϕ 1 • F 1 ζf ′ g ′
From which it follows that f ′ = f and g ′ = g.

⊓ ⊔

Theorem 2 follows from Lemma 3 and Lemma 4.

Conclusion

In this paper we relied on a modular decomposition of a (multi-sorted) signature based on a hiearchical decomposition of its set of sorts in order to reconstruct a language, specified by an algebra, by composition of the algebras associated with its sublanguages. As mentioned in the introduction the global laguage would normally be left implicit. Our result represents it as a cascaded composition of its constituent sublanguages. This representation preserves catamorphisms. One can then adopt an incremental approach consisting of growing a DSL by an operation of composition of modular grammars derived from Bekić's Theorem. This approach differs from the solution of the "expression problem" proposed by Swierstra in [START_REF] Swierstra | Data types à la carte[END_REF] which allows adding new operators for a fixed sort (or a fixed set of sorts) and thus stays confined to a given module in our context.

We intend to apply the work presented in this paper to Guarded Attribute Grammars [START_REF] Badouel | Active workspaces: Distributed collaborative systems based on guarded attribute grammars[END_REF]. It is a declarative model that describes the different ways of performing a task by recursively decomposing it into more elementary subtasks. This is formalized by the productions of an abstract context-free grammar (i.e. a multi-sorted signature). The actual way a task is decomposed depends on the choices made by the person to whom the task is assigned and on the data attached to the task (inherited attributes whose values are refined over time). Productions of the grammar are associated with guards that filter the rules applicable in a given configuration. The evaluation of these guards is done incrementally which means that a rule is allowed as soon as its guard is satisfied. This allows the workspaces of different users to operate concurrently and in reactive mode. The local grammar of a user specifies how he can behave in order to solve the pending tasks in his workspace. It defines a DSL that captures the user's domain of expertise (his role). The lazy composition of roles is compatible with the choice of Haskell as host language. Still, it remains to take side effects into account, in particular for modelling user interactions. We might use the approach proposed in [START_REF] Swierstra | Data types à la carte[END_REF] to represent the set of involved input-output actions as a datatype in order to isolate the input-output side effects from the hiearchical description of the system that would be specified, using the method presented in this paper, with ordinary Haskell functions (without side effects).

As we have seen above, the splitting of algebras is an approach to modular attribute grammars. This approach is orthogonal to, and thus can be combined with, alternative approaches of modularity in attribute grammars [START_REF] Kastens | Modularity and reusability in attribute grammars[END_REF] such as the descriptional composition [START_REF] Ganzinger | Attribute coupled grammars[END_REF][START_REF] Giegerich | Composition and evaluation of attribute coupled grammars[END_REF] or the composition by aspects [START_REF] Van Wyk | Aspects as modular language extensions[END_REF][START_REF] Van Wyk | Implementing aspect-oriented programming constructs as modular language extensions[END_REF].

data

  Tree a = Node a (Forest a) data Forest a = Leaf | Cons (Tree a) (Forest a)

data

  Box = Elembox | Comp {pos :: Pos, first, second :: Box} data Pos = Vert VPos | Hor HPos data VPos = Left | Right data HPos = Top | Bottom

  data Size = Size {depth , height :: Double} deriving Show data Point = Point {xcoord, ycoord :: Double} deriving Show class SemBox a where list :: a -> Point -> [Point] size :: a -> Size

Fig. 1 .

 1 Fig. 1. A language of boxes

Fig. 2 .

 2 Fig. 2. A richer language of boxes

Definition 2 .

 2 A modular grammar G = (F, D) is a pair that consists of a polynomial functor F : C p+n+m → C n and a regular functor D : C p+n → C m . The signature Σ = (S, Ω) associated with F concretizes the sorts and operators of the grammar where S = S p ⊎ S d ⊎ S i with |S p | = p, |S d | = n, and |S i | = m. Sorts in S p are the parameters of G. A sort is said to be defined (respectively imported) by G if it belongs to S d (resp. S i ). The regular functor represents the imported definitions of the grammar. The functor associated with the modular grammar is the (regular) functor

Fig. 3 .

 3 Fig. 3. Decomposition of modular grammars

  By functoriality of the product and composition we deduce a related operation of semidirect product of natural transformations η :H • → H ′ and τ : T • → T ′ where H, H ′ : C p → C n and T, T ′ : C p+n → C m given by (η ⋊ τ ) ζ = η ζ × (τ ζ,H ′ ζ • T ζη ζ ) = η ζ × (T ′ ζη ζ • τ ζ,Hζ )Considering the special case where the target functors H ′ and T ′ are constant functors leads us to the following definition Definition 4. The semidirect composition of two maps f : Hζ → α and g : T ζα → β where H : C p → C n and T

  stand for the inverse bijections associated with this isomorphism. Again a Σ-algebra is nothing more than a map ϕ : F ζξ → ξ where ζ ∈ |Set| p and ξ ∈ |Set| n . The catamorphism ([ϕ]) F,ζ : F † ζ → ξ associated with ϕ and ζ is characterized by the identity:

Acknowledgement

We are very grateful to the reviewers for the relevance of their comments which greatly helped us to improve the presentation of this work.

⋆ This work was partially supported by ANR Headwork.


Tonametl Sanchez
email: tonametl.sanchezramirez@inria.fr

Andrey Polyakov
email: andrey.polyakov@inria.fr

Laurent ¸iu Hetel
email: laurentiu.hetel@ec-lille.fr

Emilia Fridman
email: emilia@eng.tau.ac.il

A switching controller for a class of MIMO bilinear time-delay systems

In this paper we propose a switching controller for a class of MIMO bilinear systems with constant delays in both the state and the input. The motivation to consider such a class of systems is that, in the scalar case, it has shown to be suitable for modelling and controller design of some turbulent flow control systems.

I. INTRODUCTION

Control of Turbulent Flows is a fundamental problem in several technology areas, e.g. transportation systems as road vehicles or aircraft. Advances in control of turbulent flows produce important benefits, e.g. reduction of fuel consumption in vehicles [START_REF] Brunton | Closed-Loop Turbulence Control: Progress and Challenges[END_REF]. However, existing control techniques find several barriers to be applied on flow systems. On one hand, the main model for flow is the set of Navier-Stokes equations which can be very complex for design purposes. Besides, the computational cost for the implementation of a controller that requires to solve on-line the Navier-Stokes model is not realizable with the present-day technology [START_REF] Brunton | Closed-Loop Turbulence Control: Progress and Challenges[END_REF]. On the other hand, model approximations, e.g. finite-dimensional linear systems, can be more appropriate for control design or implementation. Unfortunately, many relevant features of the flow are not well reproduced by such models. As a consequence, the obtained controllers only work satisfactorily in a narrow range of situations.

A model for separated flow control was proposed in [START_REF] Feingesicht | A bilinear input-output model with state-dependent delay for separated flow control[END_REF]. With only few parameters, that model succeeded in reproducing the system behaviour, with a low margin error, in different experimental configurations [START_REF] Feingesicht | Nonlinear active control of turbulent separated flows: Theory and experiments[END_REF]. Such a model consists in a bilinear differential equation with delays in the input and in the state. The argument to propose such a kind of equations as models for flow systems was presented in [START_REF] Feingesicht | Nonlinear active control of turbulent separated flows: Theory and experiments[END_REF]. There, the author shows that a spatial discretization of the Burgers' equation (which is a unidimensional approximation of the Navier-Stokes equations) produces a bilinear timedelay differential equation.

For a particular case of the model introduced in [START_REF] Feingesicht | A bilinear input-output model with state-dependent delay for separated flow control[END_REF], a sliding mode controller was proposed in [START_REF] Feingesicht | SISO model-based control of separated flows: Sliding mode and optimal control approaches[END_REF]. That control technique was chosen due to the on-off characteristic of the actuators. A good experimental performance was obtained with such a controller1 . Hence, it is worth continuing with the study of the class of bilinear delayed systems and to develop general schemes for analysis and control design.

Unfortunately, the controller proposed in [START_REF] Feingesicht | SISO model-based control of separated flows: Sliding mode and optimal control approaches[END_REF] was designed only for SISO systems, and its generalization to the MIMO case is not obvious. In this paper we design a switching controller for a class of MIMO bilinear systems with constant delays in both the state and the input. Such systems can be rewritten as switched affine systems with delay in the state and in the switching signal. The switching strategy presented in this paper is an extension of a control technique developed for switched affine systems without delay, see for example [START_REF] Bolzern | Quadratic stabilization of a switched affine system about a nonequilibrium point[END_REF], [START_REF] Deaecto | Switched affine systems control design with application to DC-DC converters[END_REF], [START_REF] Hetel | Robust Sampled -Data Control of Switched Affine Systems[END_REF].

Paper organization: In Section II we describe briefly the control problem. The controller design is explained in Section III. In Section IV a simulation example is given. Some final conclusions are stated in Section V.

Notation: R and Z denote the set of real and integer numbers, respectively. For any a ∈ R, R ≥a denotes the set {x ∈ R : x ≥ a}, and analogously for R >a . For a matrix A ∈ R n×n , we mean by A > 0 (A < 0) that A is positive definite (negative definite).

II. PROBLEM STATEMENT

Consider the following bilinear time-delay system

ẋ(t) = A 0 x(t) + [A(x(t -τ )) + B] u(t -ς) , (1)
A(x(t -τ )) = Ā1 x(t -τ ) , . . . , Ām x(t -τ ) , where x(t) ∈ R n is the (instantaneous) state, u(t) ∈ R m is the control input, A 0 , Āk ∈ R n×n , k = 1, .
. . , m, are constant matrices, and τ, ς ∈ R ≥0 are constant delays. We consider (1) equipped with the output y(t) = x(t). We also assume the following for (1).

Assumption 1:

The matrix A 0 is Hurwitz, and τ ≥ ς > 0.

The problem we want to solve is stated as follows:

• to design a controller u to track asymptotically a desired constant reference y * ∈ R n , taking into account that each control component u i : R → R can only take a finite number of values. Observe that, under the restriction on the controller, we can only have N different values of the input vector u, for some N ∈ Z >0 . If we give a certain order to such N vectors, then we obtain the ordered set

U = {u 1 , . . . , u N } , (2)
where each u j ∈ R m , j = 1, . . . , N , is a constant vector.

III. CONTROLLER DESIGN

In this section we develop the control law to solve the problem established in the previous section. To this end, we first state some basic preliminary considerations.

Observe that (1) can be rewritten as follows

ẋ(t) = A 0 x(t) + m k=1 u k (t -ς) Āk x(t -τ ) + Bu(t -ς) . (3)
Now, for j = 1, . . . , N , define the vectors B j = Bu j and the matrices A j = m k=1 u j k Āk . Hence, we can consider (3) as an affine switched system given by

ẋ(t) = A 0 x(t) + A σ(t-ς) x(t -τ ) + B σ(t-ς) , (4)
where σ : R → {1, . . . , N } is the switching signal. Obviously, the system's output remain the same, i.e. y(t) = x(t).

Thus we have changed the original problem to the problem of designing the switching rule for σ.

A. On the assignable references

As stated in Section II, the control objective is to track asymptotically a constant reference y * ∈ R n . Since y(t) = x(t), we define the change of coordinates z(t) = x(t) -y * . The dynamics in variable z is given by

ż(t) = A 0 z(t) + A σ(t-ς) z(t -τ ) + B σ(t-ς) + (A 0 + A σ(t-ς) )y * .
(5)

Thus, we have to design σ such that z(t) → 0 as t → ∞. However, observe that in general z = 0 is not an equilibrium point of (5), i.e. the terms

B σ(t-ς) + (A 0 + A σ(t-ς) )y * (6)
can be different from zero. Note that to ask for the condition B σ(t-ς) + (A 0 + A σ(t-ς) )y * = 0, for any value of σ, could be very restrictive. Nevertheless, we can achieve that (in average [START_REF] Wicks | Construction of piecewise Lyapunov functions for stabilizing switched systems[END_REF], [START_REF] Bolzern | Quadratic stabilization of a switched affine system about a nonequilibrium point[END_REF]) the terms in [START_REF] Feingesicht | A bilinear input-output model with state-dependent delay for separated flow control[END_REF] do not influence the steady-state of (5). Thus, according to the switching nature of the control scheme designed below, we have to restrict the set of assignable references y * . Define the set

Γ = {γ ∈ R N : 0 ≤ γ i ≤ 1, N j=1 γ j = 1} ,
and the matrices

Āγ = N j=1 γ j A j , Bγ = N j=1 γ j B j . (7)
Thus, a necessary condition for y * to be an admissible reference is that it is contained in the set

{y * ∈ R n : (A 0 + Āγ )y * + Bγ = 0, γ ∈ Γ} .

B. State-delay-independent control rule

Note that in (4), the controller σ is delayed in time, i.e., at time t the system receives the signal σ(t -ς). However, we can design a state dependent switching signal σ that drives the trajectories of (4) to a desired reference point y * .

Theorem 1: Consider (4) and a given y * ∈ R n . If there exist γ ∈ Γ and symmetric positive definite matrices P, Q ∈ R n×n such that the following holds, (A 0 + Āγ )y * + Bγ = 0 , and Mγ < 0 ,

where

Mγ = P A 0 + A 0 P + Q P Āγ Ā γ P -Q ,
then the output y of (4) in closed-loop with the switching controller

σ(t) = arg min j (w(t) -y * )P [A j y(t -τ + ς) + B j ] , (9)
w(t) = e A0ς y(t) + 0 -ς e -A0η × A σ(t+η) y(t + η -τ + ς) + B σ(t+η) dη ,
converges asymptotically to y * . The proof of Theorem 1 is given below, but first, let us enunciate the following remarks.

Remark 1 (On the solutions): Note that, for any t ∈ R ≥0 , the switching signal σ(t) depends on x(ϑ), ϑ ∈ [t -τ, t]. Hence, the delayed switching signal σ(t -ς) depends on x(ϑ), ϑ ∈ [t -τ -ς, t -ς]. Thus, for ς > 0, (4) in closedloop with (9) can be seen as a linear time delay system with time varying coefficients. Therefore, the method of steps2 is still valid to guarantee the existence and uniqueness of Carathéodory solutions of the closed-loop.

Remark 2: For the delay-free case (ς = 0 and τ = 0), Theorem 1 reduces to a result given in [Theorem 1, [START_REF] Deaecto | Switched affine systems control design with application to DC-DC converters[END_REF]], i.e.: If there exist γ ∈ Γ and a symmetric positive definite matrix P ∈ R n×n such that (8) holds, with Mγ = P (A 0 + Āγ ) + (A 0 + Āγ ) P , then the switching controller

σ(t) = arg min j (y(t) -y * )P [A j y(t) + B j ] ,
is such that the output y converges asymptotically to y * .

C. Proof of Theorem 1

The proof consists in verifying, by means of a Lyapunov-Krasovskii functional, that the solutions of the closed-loop (5), ( 9) converge asymptotically to the origin. Consider the following standard Lyapunov-Krasovskii functional candidate (see e.g. [START_REF] Fridman | Introduction to Time-Delay Systems[END_REF])

V (φ) = φ (0)P φ(0) + 0 -τ φ (ν)Qφ(ν) dν , (10)
whose derivative along ( 5) is given by

V (z t ) = z (t)(P A 0 + A 0 P + Q)z(t)- z (t -τ )Qz(t -τ ) + 2z (t)P B σ(t-ς) + A σ(t-ς) z(t -τ ) + (A 0 + A σ(t-ς) )y * , ( 11
)
for almost all t ∈ R ≥0 . Define the vector

ζ(t) = [z (t), z (t -τ )] ,
and let us rewrite [START_REF] Wicks | Construction of piecewise Lyapunov functions for stabilizing switched systems[END_REF] as

V (z t ) = W (ζ; σ(t -ς))
where

W (ζ; σ(t -ς)) = ζ (t)M (σ(t -ς))ζ(t) + 2z (t)P × B σ(t-ς) + (A 0 + A σ(t-ς) )y * , (12)
M (σ(t -ς)) = P A 0 + A 0 P + Q P A σ(t-ς) A σ(t-ς) P -Q . Now define the function W γ : R 2n → R, given by W γ (ζ) = ζ (t) Mγ ζ(t) + 2z (t)P B γ + (A 0 + Āγ )y * .
Observe that, according to the hypotheses of the theorem, W γ is negative definite and can be rewritten as

W γ (ζ) = N j=1 γ j W (ζ; j) .
Since W γ is negative definite, and each γ i is nonnegative, we can assure that for each ζ ∈ R 2n \ {0}, there exists (at least) one j ∈ {1, . . . , N } such that W (ζ; j) < 0. Therefore, the switching law

σ(t -ς) = arg min j W (ζ; j)
guarantees that (12) is negative definite. Now consider [START_REF] Wicks | Construction of piecewise Lyapunov functions for stabilizing switched systems[END_REF] to note that

min j W (ζ; j) = z (t)(P A 0 + A 0 P + Q)z(t)- z (t -τ )Qz(t -τ ) + 2 min j z (t)P × [A j z(t -τ ) + (A 0 + A j )y * + B j ]) ,
nonetheless, by using the change of coordinates for z we obtain the equality

min j z (t)P [A j z(t -τ ) + (A 0 + A j )y * + B j ] = min j (x(t) -y * ) P [A j x(t -τ ) + B j ] + z (t)P A 0 y * .
Hence we can assert that the switching law σ(t -ς) = arg min j W (ζ; j) is equivalent to the delayed switching law

σ(t -ς) = arg min j (x(t) -y * )P [A j x(t -τ ) + B j ] .
By advancing in time this equation, we obtain σ(t) = arg min j (x(t+ς)-y * )P [A j x(t-τ +ς)+B j ] , (13) but this switching law requires the prediction of the state at t + ς. Since the solution of (4) can be written as the prediction of the state at t + ς is given by

x(t) = t t0 e A0(t-ν) A σ(ν-ς) x(ν -τ ) + B σ(ν-ς) dν+ e A0(t-t0) x(t 0 ) ,
x(t + ς) = e A0ς x(t) + t+ς t e A0(t+ς-ν) × A σ(ν-ς) x(ν -τ ) + B σ(ν-ς) dν .
Observe that in [START_REF] Löfberg | YALMIP : A Toolbox for Modeling and Optimization in MATLAB[END_REF], w(t) = x(t + ς) by means of the change of variable η = -t -ς + ν. This completes the proof of Theorem 1.

For Remark 2, the proof is analogous but considering the Lyapunov function candidate V (z) = z P z.

IV. EXAMPLE

Consider [START_REF] Bolzern | Quadratic stabilization of a switched affine system about a nonequilibrium point[END_REF] with n = 2, m = 2, τ = 1, ς = 1/2, and

A 0 = -3 1 2 -5 , Ā1 = 4 2 1 6 , Ā2 = 1 1 2 2 .
The control components are assumed to be on-off, i.e. u i : R → {0, 1}, i = 1, 2, hence U = {u 1 , . . . , u 4 } where u The LMI in [START_REF] Hetel | Robust Sampled -Data Control of Switched Affine Systems[END_REF] was solved in MATLAB by using the solver SeDuMi [START_REF] Jos | Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[END_REF] version 1.3, and the toolbox YALMIP [START_REF] Löfberg | YALMIP : A Toolbox for Modeling and Optimization in MATLAB[END_REF].

1 = [0 0] , u 2 = [1 0] , u 3 = [0 1] ,
For the simulation, we used Simulink with the fixed step Euler integration method. The initial conditions were chosen as x(t) = 0, u(t) = 0 for all t ≤ 0, and the integration step was equal to 0.1ms.

Fig. 1 shows the system's states converging to the reference point. The vertical doted lines indicate the time when the delayed inputs start to switch in a high-frequency regime. Such a switching can be appreciated in the nondelayed control signals shown in Fig. 2.

V. CONCLUSION

A standard technique to control affine switched systems was extended to a class of bilinear time-delay systems. The importance of this controller lies on its potential applicability to turbulent flow control systems. The conceptual simplicity of the controller allows us to use it for both SISO and MIMO systems. Interestingly the proposed controller is very suitable for the kind of on-off actuators used in several flow control applications, see e.g. [START_REF] Brunton | Closed-Loop Turbulence Control: Progress and Challenges[END_REF], [START_REF] Feingesicht | SISO model-based control of separated flows: Sliding mode and optimal control approaches[END_REF].

Future work: There are several aspects that have to be considered to improve the control approach considered in this paper. We can mention, e.g. reduction of computational cost in the predictor implementation, relaxations or modification of the system's assumptions, robustness analysis, and generalization to a wider set of systems.

Fig. 1 .

 1 Fig. 1. States of the system.

Fig. 2 .

 2 Fig. 2. Control signals.

A video with some experiments, reported in[START_REF] Feingesicht | SISO model-based control of separated flows: Sliding mode and optimal control approaches[END_REF], can be seen at https://www.youtube.com/watch?v=b5NnAV2qeno.

In this case, the method of steps consists in studying the systems in the intervals [t 0 , t 0 + ς], [t 0 + ς, t 0 + 2ς], . . . , and so on, see e.g.[START_REF] Fridman | Introduction to Time-Delay Systems[END_REF].

ACKNOWLEDGMENT

This work was carried out within the framework of the CNRS Research Federation on Ground Transports and Mobility, in articulation with the ELSAT2020 project supported by the European Community, the French Ministry of Higher Education and Research, the Hauts de France Regional Council. This work was also supported by Agence Nationale pour la Recherche ROCC-SYS, ANR-14-CE27-0008; the Israel Science Foundation, grant No. 1128/14; the Ministry of Education and Science of Russian Federation, project 14.Z50.31.0031; and the Goverment of Russian Federation, grant 08-08. The authors gratefully acknowledge the support of all these institutions.