Proliferation of new computing hardware platforms that support increasing numbers of cores, as well as increasing ISA heterogeneity, is creating opportunity for systems software developers to question existing software architecture. One promising emerging systems architecture is the multikernel, pioneered in Barrelfish OS. The multikernel directly addresses the challenges of high core counts and increased heterogeneity by partitioning the system into multiple independently running kernel instances which cooperate to form a single operating system. Popcorn Linux is an adaptation of the multikernel concept to a Linux environment, melding the multikernel concept with the power and ubiquity of the Linux platform. The goal of the Popcorn Linux project is to provide a Linux-based single-system image environment for heterogeneous hardware. In constructing this environment, Linux must be extended to distribute the plethora of operating system services that it provides across kernel instances. This thesis presents the newly developed Popcorn Linux mechanism for migrating tasks and their address spaces between kernel instances at arbitrary points in their execution. Both process and thread migration is supported, and distributed address spaces are maintained and guaranteed to remain consistent between distributed thread group members running on different kernel instances. Tasks can migrate through an unlimited number of kernel instances, as well as back to previously visited kernel instances. Additionally, the full task life-cycle is supported, allowing migrated tasks to exit and create new children on whichever kernel instance happens to be hosting them. The mechanisms developed were vetted through unit testing, review, and a number of compute-bound benchmarks in a homogeneous x86 64bit environment. Correctness was demonstrated, and performance metrics were acquired. Popcorn Linux performance was shown to be reasonable when compared to SMP Linux. The mechanisms developed are therefore deemed feasible. Scalability was determined to be a function of workload characteristics, where in some cases Popcorn Linux out-scales SMP Linux and in other cases SMP Linux out-scales Popcorn Linux. Optimizations are recommended to reduce the maturity gap between Popcorn Linux and SMP Linux, improving Popcorn Linux performance. / Master of Science

Recent trends in the computer market suggest that emerging computing platforms will be increasingly parallel and heterogeneous, in order to satisfy the user demand for improved performance and superior energy savings. Heterogeneity is a promising technology to keep growing the number of cores per chip without breaking the power wall. However, existing system software is able to cope with homogeneous architectures, but it was not designed to run on heterogeneous architectures, therefore, new system software designs are necessary. One innovative design is the multikernel OS deployed by the Barrelfish operating system (OS) which partitions hardware resources to independent kernel instances that communicate exclusively by message passing, without exploiting the shared memory available amongst different CPUs in a multicore platform. Popcorn Linux implements an extension of the multikernel OS design, called replicated-kernel OS, with the goal of providing a Linux-based single system image environment on top of multiple kernels, which can eventually run on different ISA processors. A replicated-kernel OS replicates the state of various OS sub-systems amongst kernels that cooperate using message passing to distribute or access various services uniquely available on each kernel. In this thesis, we present mechanisms to distribute signals, namespaces, inter-thread synchronizations and socket state replication. These features are built on top of the existing messaging layer, process or thread migration and address space consistency protocol to provide the application with an illusion of single system image and developers with the SMP programming environment they are most familiar with. The mechanisms developed were unit tested with micro benchmarks to validate their correctness and to measure the gained speed up or additive overhead. Real-world applications were also used to benchmark the developed mechanisms on homogeneous and on heterogeneous architectures. It is found that the contributed Popcorn synchronization mechanism exhibits overhead compared to vanilla Linux on multicore as Linux's equivalent mechanisms are tightly coupled with underlying hardware cache coherency protocol, therefore, faster than software message passing. On heterogeneous platforms, the developed mechanisms allow to transparently map each portion of the application to the processor in the platform on which the execution is faster. Optimizations are recommended to further improve the performance of the proposed synchronization mechanism. However, optimizations may force the userspace application and libraries to be rewritten in order to decouple their synchronization mechanisms of shared memory, therefore losing transparency, which is one of the primary goals of this work. / Master of Science

Barrelfish operating system is an experimental instance of multikernel structure which exhibits good features such as hardware heterogeneity, scalability, dynamicity, etc. Barrelfish is in progress and lacks applications. Therefore, there is a need to investigate the efficiency of applications running in Barrelfish and one of candidates is a shared-memory application. To conduct an empirical study, Cilk is chosen inasmuch as its runtime library is designed for shared-memory architectures and it has been known to expose good performance. This thesis focuses on making Cilk run on top of Barrelfish in order to reach two goals: portability which is described to be supported by Barrelfish, and good speed afterwards. The porting involves compiling Cilk runtime source code by replacing its pthread subroutines with set of APIs in Barrelfish and then changing the way Cilk scheduler spawns worker thread on multiple cores. However, the main point of the porting is to make different cores access to the same virtual address space. Luckily, Barrelfish provides a notion of domain which specifies the number of cores in an application so that these cores can share the same memory space. This thesis also has carried out benchmarks on some Cilk programs and found that Cilk does not perform as well as it is expected. In addition measurements on parallel workers shows that Cilk on Barrelfish takes more cycles to perform computation. Although Cilk still maintains work-first principle, it cannot achieve the time bound. The spanning domain cost is proportional to the number of cores, but it will matter if applications take small time to complete.

As manufacturers introduce new machines with more cores, more NUMA-like architectures, and more tightly integrated heterogeneous processors, the traditional abstraction of a monolithic OS running on a SMP system is encountering new challenges.  One proposed path forward is the multikernel operating system.  Previous efforts have shown promising results both in scalability and in support for heterogeneity.  However, one effort\'s source code is not freely available (FOS), and the other effort is not self-hosting and does not support a majority of existing applications (Barrelfish). In this thesis, we present Popcorn, a Linux-based multikernel operating system.  While Popcorn was a group effort, the boot layer code and the memory partitioning code are the author\'s work, and we present them in detail here.  To our knowledge, we are the first to support multiple instances of the Linux kernel on a 64-bit x86 machine and to support more than 4 kernels running simultaneously. We demonstrate that existing subsystems within Linux can be leveraged to meet the design goals of a multikernel OS.  Taking this approach, we developed a fast inter-kernel network driver and messaging layer.  We demonstrate that the network driver can share a 1 Gbit/s link without degraded performance and that in combination with guest kernels, it meets or exceeds the performance of SMP Linux with an event-based web server.  We evaluate the messaging layer with microbenchmarks and conclude that it performs well given the limitations of current x86-64 hardware.  Finally, we use the messaging layer to provide live process migration between cores. / Master of Science

L’objectif principal de cette thèse est de décliner et d’analyser l’algorithme kernel-LMS à noyau Gaussien dans trois cadres différents: celui des noyaux uniques et multiples, à valeurs réelles et à valeurs complexes, dans un contexte d’apprentissage distributé et coopératif dans les réseaux de capteurs. Plus précisement, ce travail s’intéresse à l’analyse du comportement en moyenne et en erreur quadratique de cas différents types d’algorithmes LMS à noyau. Les modèles analytiques de convergence obtenus sont validés par des simulations numérique. Tout d’abord, nous introduisons l’algorithme LMS, les espaces de Hilbert à noyau reproduisants, ainsi que les algorithmes de filtrage adaptatif à noyau existants. Puis, nous étudions analytiquement le comportement de l’algorithme LMS à noyau Gaussien dans le cas où les statistiques des éléments du dictionnaire ne répondent que partiellement aux statistiques des données d’entrée. Nous introduisons ensuite un algorithme LMS modifié à noyau basé sur une approche proximale. La stabilité de l’algorithme est également discutée. Ensuite, nous introduisons deux types d’algorithmes LMS à noyaux multiples. Nous nous concentrons en particulier sur l’analyse de convergence de l’un d’eux. Plus généralement, les caractéristiques des deux algorithmes LMS à noyaux multiples sont analysées théoriquement et confirmées par les simulations. L’algorithme LMS à noyau complexe augmenté est présenté et ses performances analysées. Enfin, nous proposons des stratégies de diffusion fonctionnelles dans les espaces de Hilbert à noyau reproduisant. La stabilité́ de cas de l’algorithme est étudiée. / The main objective of this thesis is to derive and analyze the Gaussian kernel least-mean-square (LMS) algorithm within three frameworks involving single and multiple kernels, real-valued and complex-valued, non-cooperative and cooperative distributed learning over networks. This work focuses on the stochastic behavior analysis of these kernel LMS algorithms in the mean and mean-square error sense. All the analyses are validated by numerical simulations. First, we review the basic LMS algorithm, reproducing kernel Hilbert space (RKHS), framework and state-of-the-art kernel adaptive filtering algorithms. Then, we study the convergence behavior of the Gaussian kernel LMS in the case where the statistics of the elements of the so-called dictionary only partially match the statistics of the input data. We introduced a modified kernel LMS algorithm based on forward-backward splitting to deal with $\ell_1$-norm regularization. The stability of the proposed algorithm is then discussed. After a review of two families of multikernel LMS algorithms, we focus on the convergence behavior of the multiple-input multikernel LMS algorithm. More generally, the characteristics of multikernel LMS algorithms are analyzed theoretically and confirmed by simulation results. Next, the augmented complex kernel LMS algorithm is introduced based on the framework of complex multikernel adaptive filtering. Then, we analyze the convergence behavior of algorithm in the mean-square error sense. Finally, in order to cope with the distributed estimation problems over networks, we derive functional diffusion strategies in RKHS. The stability of the algorithm in the mean sense is analyzed.