La projection est une des techniques utilisées pour permettre de réduire les besoins en terme de taille mémoire nécessaire aux moteurs de requêtes XML (in-memory). L'idée sous-jacente à cette technique est simple : étant donnée une requête Q à évaluer sur un document XML D, au lieu de procéder sur D, la requête est évaluée sur un document D', plus petit que D, construit lors du chargement de ce dernier en mémoire, par élagage des parties de D inutiles pour Q. Le document D', est une projection du document initial D. Il est souvent de taille drastiquement inférieure à celle de D.Alors que cette technique de projection a été étudiée et développée assez largement pour l'interrogation de document XML, à notre connaissance, ce type de technique n'a pas été explorée ni appliquée aux mises à jour de documents XML.L'objet de cette thèse a donc été de proposer une technique d'optimisation de mises à jour de documents au format XML exploitant le typage des documents.La contribution a porté sur la spécification de l'algorithme Merge, c'est-à-dire la fusion des modifications avec le document initial, ainsi que sur le développement d'un prototype sur lequel des tests ont été effectués. / XML projection is one of the main adopted optimization techniques for reducing memory consumption in XQuery in-memory engines. The main idea behind this technique is quite simple: given a query Q over an XML document D, instead of evaluating Q on D, the query Q is evaluated on a smaller document D' obtained from D by pruning out, at loading-time, parts of D that are unrelevant for Q. The actual queried document D' is a projection of the original one, and is often much smaller than D due to the fact that queries tend to be quite selective in general.While projection techniques have been extensively investigated for XML querying, we are not aware of applications to XML updating.This Thesis investigates application of a projection based optimization mechanism for XQuery Update Facility expressions in the presence of a schema. The current work includes study of the method and a formal development of Merge algorithm as well as experiments testifying its effectiveness.

No description available.

<div>In the era of big data, the sheer volume and widespread spatial distribution of information has been promoting extensive research on distributed optimization over networks. Each computing unit has access only to a relatively small portion of the entire data and can only communicate with a relatively small number of neighbors. The goal of the system is to reach consensus on the optimal parametric model with respect to the entire data among all computing units. Existing work has provided various decentralized optimization algorithms for the purpose. However, some important questions remain unclear: (I) what is the intrinsic connection among different existing algorithms? (II) what is the min-max lower complexity bound for decentralized algorithms? Can one design an optimal decentralized algorithm in the sense that it achieves the lower complexity bound? and (III) in the presence of asynchrony and imperfect communications, can one design linearly convergent decentralized algorithms?</div><div><br></div><div> This thesis aims at addressing the above questions. (I) Abstracting from ad-hoc, specific solution methods, we propose a unified distributed algorithmic framework and analysis for a general class of optimization problems over networks. Our method encapsulates several existing first-order distributed algorithms. Distinguishing features of our scheme are: (a) When each of the agent’s functions is strongly convex, the algorithm converges at a linear rate, whose dependence on the agents’ functions and network topology is decoupled; (b) When the objective function is convex, but not strongly convex, similar decoupling as in (a) is established for the coefficient of the proved sublinear rate. This also reveals the role of function heterogeneity on the convergence rate; (c) The algorithm can adjust the ratio between the number of communications and computations to achieve a rate (in terms of computations) independent on the network connectivity; and (d) A by-product of our analysis is a tuning recommendation for several existing (non-accelerated) distributed algorithms, yielding provably faster (worst-case) convergence rate for the class of problems under consideration. (II) Referring to lower complexity bounds, the proposed novel family of algorithms, when equipped with acceleration, are proved to be optimal, that is, they achieve convergence rate lower bounds. (III) Finally, to make the proposed algorithms practical, we break the synchronism in the agents’ updates: agents wake up and update without any coordination, using information only from immediate neighbors with unknown, arbitrary but bounded delays. Quite remarkably, even in the presence of asynchrony, the proposed algorithmic framework is proved to converge at a linear rate (resp. sublinear rate) when applied to strongly convex (resp. non strongly convex) optimization problems.</div>

In recent years with the exponential growth in web-based applications the amount of data generated has increased tremendously. Quick and accurate analysis of this 'big data' is indispensable to make better business decisions and reduce operational cost. The challenges faced by modern day data centers to process big data are multi fold: to keep up the pace of processing with increased data volume and increased data velocity, deal with system scalability and reduce energy costs. Today's data centers employ a variety of distributed computing frameworks running on a cluster of commodity hardware which include general purpose processors to process big data. Though better performance in terms of big data processing speed has been achieved with existing distributed computing frameworks, there is still an opportunity to increase processing speed further. FPGAs, which are designed for computationally intensive tasks, are promising processing elements that can increase processing speed. In this thesis, we discuss how FPGAs can be integrated into a cluster of general purpose processors running iterative algorithms and obtain high performance. In this thesis, we designed a heterogeneous cluster comprised of FPGAs and CPUs and ran various benchmarks such as PageRank, Katz and Connected Components to measure the performance of the cluster. Performance improvement in terms of execution time was evaluated against a homogeneous cluster of general purpose processors and a homogeneous cluster of FPGAs. We built multiple four-node heterogeneous clusters with different configurations by varying the number of CPUs and FPGAs. We studied the effects of load balancing between CPUs and FPGAs. We obtained a speedup of 20X, 11.5X and 2X for PageRank, Katz and Connected Components benchmarks on a cluster cluster configuration of 2 CPU + 2 FPGA for an unbalancing ratio against a 4-node homogeneous CPU cluster. We studied the effect of input graph partitioning, and showed that when the input is a Multilevel-KL partitioned graph we obtain an improvement of 11%, 26% and 9% over randomly partitioned graph for Katz, PageRank and Connected Components benchmarks on a 2 CPU + 2 FPGA cluster.

This thesis investigates a method for efficiently updating the software of anhttps://www.overleaf.com/project/60104b7e4b5c604828be9768 Electronic Control Unit (ECU) in a car. The patch sent to the car should be as small as possible and optimally only contained the changed part of the software. A popular algorithm for creating the patch is bsdiff. However, it is not made for filesystem images, but for binaries. Therefore, an alternative is investigated. The alternative algorithm method is based on the update engine in Android. A standalone version of the Android A/B Update is implemented and compared to bsdiff, in the aspect of the time it takes to generate the patch and the size of the patch. The result shows that bsdiff generates a slightly smaller patch. However, bsdiff is also a lot slower at generating the patch. Furthermore, the time increases linearithmic with the size of the filesystem image. This gives reason to believe that the Android A/B Update algorithm might be a better solution when updating an ECU that contains a full filesystem. However, this depends on if it is most valuable that the patch is as small as possible, or that the process of generating it is fast. / Detta examensarbete undersöker en metod för att effektivt uppdatera mjukvaran i en styrenhet i en bil. En patch som skickas till en bil ska vara så liten som möjligt och helst enbart innehålla de delar av mjukvaran som ändrats. En populär algorithm för att skapa en sådan patch är bsdiff. Den är dock inte gjord för filsystemsavbildningar, utan för binärer. Därför studeras här ett alternativ. Denna alternativa metod är baserad på Androids updateringsprocess. En fristående variant av Android A/B Update är implementerad och och jämförd med bsdiff, med avseende på tiden det tar att generera en patch och storleken av den. Resultatet visar att bsdiff genererar mindre patchar. Däremot är bsdiff också betydligt långsammare. Vidare ökar tiden linearitmisk då storleken på patchen ökar. Detta innebär att Android A/B Update kan vara en bättre lösning för att updatera en styrenhet som innehåller ett filsystem. Det beror dock på vad som värderas högst; en mindre patch eller att processen att skapa patchen ska vara snabbare.

No description available.

CubeSat satellites have redefined the standard solution for conducting missions in space due to their unique form factor and cost. The harsh environment of space necessitates examining features that improve satellite robustness and ultimately extend lifetime, which is typical and vital for mission success. The CubeSat development team at Cal Poly, PolySat, has recently redefined its standard avionics platform to support more complex mission capabilities with this robustness in mind. A significant addition was the integration of the Linux operating system, which provides the flexibility to develop much more elaborate protection mechanisms within software, such as support for remote on-orbit software updates. This thesis details the design and development of such a feature-set with critical software recovery and multiple-mission single-CubeSat functionality in mind. As a result, features that focus on software update usability, validation, system recovery, upset tolerance, and extensibility have been developed. These include backup Linux kernel and file system image availability, image validation prior to boot, and the use of multiple file system devices to protect against system upsets. Furthermore, each feature has been designed for usability on current and future missions.

Dynamic software updates change the code of a computer program while it runs, thus saving the programmer's time and using computing resources more productively. This dissertation establishes the value of and recommends practices for applying dynamic software updates to computationally-intensive applications—a computing domain characterized by long-running computations, expensive computing resources, and a tedious deployment process. This dissertation argues that updating computationally-intensive applications dynamically can reduce their time-to-discovery metrics—the total time it takes from posing a problem to arriving at a solution—and, as such, should become an intrinsic part of their software lifecycle. To support this claim, this dissertation presents the following technical contributions: (1) a distributed consistency algorithm for synchronizing dynamic software updates in a parallel HPC application, (2) an implementation of the Proxy design pattern that is more efficient than the existing implementations, and (3) a dynamic update approach for Java Virtual Machine (JVM)-based applications using the Proxy pattern to offer flexibility and efficiency advantages, making it suitable for computationally-intensive applications. The contributions of this dissertation are validated through performance benchmarks and case studies involving computationally-intensive applications from the bioinformatics and molecular dynamics simulation domains. / Ph. D.

Recent studies show that deep learning can be employed to learn from sensor data to improve accuracy and robustness of sensor fusion algorithms. In the same vein, in this thesis we use a state-of-the-art temporal convolution network to predict zero velocity updates (ZUPT) from raw inertial measurement unit (IMU) signals, and use the network output to improve the performance of an optimization-based pose estimator. Experiments were conducted on publicly available datasets, and results show that (i) the network can distinguish a car in motion vs. a car standing still by observing an IMU signal, and (ii) that ZUPT detection enhances the observability of states in the optimization-based pose estimation, thus reducing local drift. / Nyligen gjorda studier visar att djupinlärning kan användas för att lära av sensordata för att förbättra noggrannhet och robusthet hos sensorfusionsalgoritmer. På samma sätt använder vi i denna avhandling en tidsberoende faltnings neuronnätsmodell (TCN) för att detektera om ett fordon står stilla även kallat zero velocity updates (ZUPT) från IMU rå- data och använder neuronnätsprediktionen för att förbättra prestandan hos en optimeringsbaserad positionsuppskattning. Experiment utfördes på allmänt publicerade datamängder, och resultaten visar att (i) neuronnätsmodellen kan läras till att urskilja en bil i rörelse kontra en bil som står stilla genom att observera en IMU- signal, och (ii) att ZUPT- detektering förbättrar observerbarheten för tillstånd i den optimeringsbaserade positioneringsuppskattningen, vilket minskar lokal drift.

Durant cette dernière décennie, la diffusion du format XML pour représenter les données générées par et échangées sur le Web a été accompagnée par la mise en œuvre de nombreux moteurs d’évaluation de requêtes et de mises à jour XQuery. Parmi ces moteurs, les systèmes « mémoire centrale » (Main-memory Systems) jouent un rôle très important dans de nombreuses applications. La gestion et l’intégration de ces systèmes dans des environnements de programmation sont très faciles. Cependant, ces systèmes ont des problèmes de passage à l’échelle puisqu’ils requièrent le chargement complet des documents en mémoire centrale avant traitement.Cette thèse présente une technique de partitionnement des documents XML qui permet aux moteurs « mémoire principale » d’évaluer des expressions XQuery (requêtes et mises à jour) pour des documents de très grandes tailles. Cette méthode de partitionnement s’applique à une classe de requêtes et mises à jour pertinentes et fréquentes, dites requêtes et mises à jour itératives.Cette thèse propose une technique d'analyse statique pour reconnaître les expressions « itératives ». Cette analyse statique est basée sur l’extraction de chemins à partir de l'expression XQuery, sans utilisation d'information supplémentaire sur le schéma. Des algorithmes sont spécifiés, utilisant les chemins extraits par l’étape précédente, pour partitionner les documents en entrée en plusieurs parties, de sorte que la requête ou la mise à jour peut être évaluée sur chaque partie séparément afin de calculer le résultat final par simple concaténation des résultats obtenus pour chaque partie. Ces algorithmes sont mis en œuvre en « streaming » et leur efficacité est validée expérimentalement.En plus, cette méthode de partitionnement est caractérisée également par le fait qu'elle peut être facilement implémentée en utilisant le paradigme MapReduce, permettant ainsi d'évaluer une requête ou une mise à jour en parallèle sur les données partitionnées. / With the widespread diffusion of XML as a format for representing data generated and exchanged over the Web, main query and update engines have been designed and implemented in the last decade. A kind of engines that are playing a crucial role in many applications are « main-memory » systems, which distinguish for the fact that they are easy to manage and to integrate in a programming environment. On the other hand, main-memory systems have scalability issues, as they load the entire document in main-memory before processing. This Thesis presents an XML partitioning technique that allows main-memory engines to process a class of XQuery expressions (queries and updates), that we dub « iterative », on arbitrarily large input documents. We provide a static analysis technique to recognize these expressions. The static analysis is based on paths extracted from the expression and does not need additional schema information. We provide algorithms using path information for partitioning the input documents, so that the query or update can be separately evaluated on each part in order to compute the final result. These algorithms admit a streaming implementation, whose effectiveness is experimentally validated. Besides enabling scalability, our approach is also characterized by the fact that it is easily implementable into a MapReduce framework, thus enabling parallel query/update evaluation on the partitioned data.