Littérature scientifique sur le sujet « Interpretative Optimization »

Today's Web browsers provide a platform for the development of complex, richly interactive user interfaces. But, with this complexity come additional challenges for Web developers. The complicated behavioural relationships between user interface components are often stateful, and are difficult to describe, encode and maintain using conventional programming techniques with ECMAScript, the general-purpose scripting language embedded in all Web browsers. Furthermore, user interfaces must be performant, reacting to user input quickly; if the system responds too slowly, the result is a visible UI "lag," degrading the user's experience. Statecharts, a visual modelling language created in the 1980's for developing safety-critical embedded systems, can provide solutions to these problems, as it is well-suited to describing the reactive, timed, state-based behaviour that often comprises the essential complexity of a Web user interface. The contributions of this thesis are then twofold. First, in order to use Statecharts effectively, an interpreter is required to execute the Statecharts models. Therefore, the primary contribution of this thesis is the design, description, implementation and empirical evaluation of the Statecharts Interpretation and Optimization eNgine (SCION), a Statecharts interpreter implemented in ECMAScript that can run in all Web browsers, as well as other ECMAScript environments such as Node.js and Rhino. This thesis first describes a syntax and semantics for SCION which aims to be maximally intuitive for Web developers. Next, test-driven development is used to verify the correct implementation of this semantics. Finally, SCION is optimized and rigorously evaluated to maximize performance and minimize memory usage when run in various Web browser environments. While SCION began as a research project toward the completion of this master thesis, it has grown into an established open source software project, and is currently being used for real work in production environments by several organizations. The secondary contribution of this thesis is the introduction of a new Statecharts-based design pattern called Stateful Command Syntax, which can be used to guide Web user interface development with Statecharts. This design pattern can be applied to a wide class of Web user interfaces, specifically those whose behaviour comprises a command syntax that varies depending on high-level application state. Its use is illustrated through detailed case studies of two highly interactive, but very different applications.<br>Les navigateurs web modernes permettent la création d'interfaces utilisateur particulièrement élaborées et interactives. Mais cela engendre également des difficultés additionnelles pour les développeurs web. Les relations qui existent entre les différentes composantes des interfaces utilisateur sont souvent complexes et difficiles à élaborer, encoder et entretenir en utilisant les techniques de programmation conventionnelles qu'offre ECAMScript, un langage que l'on retrouve dans tous les navigateurs. Or, les interfaces doivent être assez performantes pour répondre rapidement aux actions effectuées par l'utilisateur, car un système trop lent engendre un décalage qui nuit à l'expérience d'utilisation. Statecharts, un langage de modélisation visuelle créé dans les années 80 pour assurer la sécurité des systèmes embarqués, peut offrir des solutions à ces défis : il sait répondre aux impératifs de réactivité, de programmation dans le temps et de comportement fondé sur l'état qui représentent en somme ce qui est le plus difficile avec les interfaces utilisateur sur le web. L'apport de ce mémoire est double. Tout d'abord, l'exécution des modèles Statecharts nécessite un interprète. La première contribution de cet article consiste donc en le design, l'élaboration, l'implémentation et l'évaluation empirique du Statecharts Interpretation and Optimization eNgine (SCION), un interprète en ECMAScript qui peut être exécuté dans tous les navigateurs web ainsi que dans d'autres environnements ECMAScript, comme Node.js et Rhino. SCION est doté d'une syntaxe et d'une sémantique qui se veut la plus intuitive possible pour les développeurs web. De nombreux tests sont ensuite effectués pour en assurer le bon fonctionnement. Enfin, SCION est rigoureusement optimisé afin de maximiser la performance et de minimiser l'utilisation de la mémoire vive dans différents navigateurs web. Bien que SCION ait débuté comme un projet de recherche personnel en vue de l'obtention du diplôme de maîtrise, il est devenu un logiciel libre bien établi et utilisé par plusieurs organisations dans des environnements de travail. La deuxième contribution de ce mémoire est la présentation d'un nouveau patron de conception créé à partir de Statecharts nommé Stateful Command Syntax, qui peut être utilisé pour guider la création d'interfaces utilisateur sur le web. Ce patron de conception peut être employé sur une grande variété d'interfaces, notamment celles dont le comportement inclut une syntaxe de commande qui varie selon le degré d'abstraction de l'application. Son utilisation est illustrée à travers quelques études de cas ainsi que deux logiciels très différents mais hautement interactifs.

The major objective of this work is to analyse possibilities of using simulation within the development of application-specific instruction-set processors, to explore and compare some common simulation techniques and to use the collected information to design a new simulation tool suitable for utilization in the processors development and optimization. This thesis presents the main requirements on the new simulator and describes the design and implementation of its key parts with emphasis on the high performance.

The advances in data-collecting technologies provides great opportunities to access large sample-size data sets with high dimensionality. Variable selection is an important procedure to extract useful knowledge from such complex data. While in many real-data applications, appropriate selection of variables should facilitate the model interpretation and computation efficiency. It is thus important to incorporate domain knowledge of underlying data generation mechanism to select key variables for improving the model performance. However, general variable selection techniques, such as the best subset selection and the Lasso, often do not take the underlying data generation mechanism into considerations. This thesis proposal aims to develop statistical modeling methodologies with a focus on the structured variable selection towards better model interpretation and computation efficiency. Specifically, this thesis proposal consists of three parts: an additive heredity model with coefficients incorporating the multi-level data, a regularized dynamic generalized linear model with piecewise constant functional coefficients, and a structured variable selection method within the best subset selection framework. In Chapter 2, an additive heredity model is proposed for analyzing mixture-of-mixtures (MoM) experiments. The MoM experiment is different from the classical mixture experiment in that the mixture component in MoM experiments, known as the major component, is made up of sub-components, known as the minor components. The proposed model considers an additive structure to inherently connect the major components with the minor components. To enable a meaningful interpretation for the estimated model, we apply the hierarchical and heredity principles by using the nonnegative garrote technique for model selection. The performance of the additive heredity model was compared to several conventional methods in both unconstrained and constrained MoM experiments. The additive heredity model was then successfully applied in a real problem of optimizing the Pringlestextsuperscript{textregistered} potato crisp studied previously in the literature. In Chapter 3, we consider the dynamic effects of variables in the generalized linear model such as logistic regression. This work is motivated from the engineering problem with varying effects of process variables to product quality caused by equipment degradation. To address such challenge, we propose a penalized dynamic regression model which is flexible to estimate the dynamic coefficient structure. The proposed method considers modeling the functional coefficient parameter as piecewise constant functions. Specifically, under the penalized regression framework, the fused lasso penalty is adopted for detecting the changes in the dynamic coefficients. The group lasso penalty is applied to enable a sparse selection of variables. Moreover, an efficient parameter estimation algorithm is also developed based on alternating direction method of multipliers. The performance of the dynamic coefficient model is evaluated in numerical studies and three real-data examples. In Chapter 4, we develop a structured variable selection method within the best subset selection framework. In the literature, many techniques within the LASSO framework have been developed to address structured variable selection issues. However, less attention has been spent on structured best subset selection problems. In this work, we propose a sparse Ridge regression method to address structured variable selection issues. The key idea of the proposed method is to re-construct the regression matrix in the angle of experimental designs. We employ the estimation-maximization algorithm to formulate the best subset selection problem as an iterative linear integer optimization (LIO) problem. the mixed integer optimization algorithm as the selection step. We demonstrate the power of the proposed method in various structured variable selection problems. Moverover, the proposed method can be extended to the ridge penalized best subset selection problems. The performance of the proposed method is evaluated in numerical studies.<br>Doctor of Philosophy<br>The advances in data-collecting technologies provides great opportunities to access large sample-size data sets with high dimensionality. Variable selection is an important procedure to extract useful knowledge from such complex data. While in many real-data applications, appropriate selection of variables should facilitate the model interpretation and computation efficiency. It is thus important to incorporate domain knowledge of underlying data generation mechanism to select key variables for improving the model performance. However, general variable selection techniques often do not take the underlying data generation mechanism into considerations. This thesis proposal aims to develop statistical modeling methodologies with a focus on the structured variable selection towards better model interpretation and computation efficiency. The proposed approaches have been applied to real-world problems to demonstrate their model performance.

Aujourd’hui, la communauté scientifique dispose de jeux de données gravimétriques avec une précision et une résolution spatiale sans précédent qui améliorent nos connaissances du champ gravitationnel terrestre à différentes échelles et longueurs d’ondes, obtenues de mesures du sol à des satellites. Parallèlement à la gravimétrie, l’avancement des observations par satellite fournit à la communauté des modèles d’élévation numérique plus détaillés pour refléter la géométrie de la structure terrestre. Ensemble, ces nouveaux jeux de données offrent une excellente occasion de mieux comprendre les structures et la dynamique de la Terre à l’échelle locale, régionale et mondiale. L'utilisation et l'interprétation de ces données de haute qualité exigent le raffinement des approches standards dans le traitement et l'analyse des données liées à la gravité. Cette thèse consiste en une série d’études visant à améliorer la précision du traitement des données de gravité et gravité de gravité gradients pour les études géodynamiques. Pour ce faire, nous développons un outil, appelé GEEC (Gal Eötvös Earth Calculator), pour calculer précisément les effets gravimétriques dues à tout corps de masse, indépendamment de sa géométrie et de sa distance par rapport aux mesures. Les effets de gravité et des gravité gradients sont calculés analytiquement en utilisant la solution intégrale linéaire d'un polyèdre irrégulier. Les validations aux échelles locale, régionale et mondiale confirment la robustesse des performances du GEEC, où la résolution du modèle, qui dépend à la fois de la taille de la masse corporelle et de sa distance par rapport au point de mesure, contrôle fortement la précision des résultats. Nous présentons une application pour évaluer les paramètres optimaux dans le calcul des gradients de gravité et de gravité dus aux variations de topographie. La topographie joue un rôle majeur dans l'attraction gravitationnelle de la Terre; par conséquent, l'estimation des effets topographiques doit être soigneusement prise en compte dans le traitement des données gravimétriques, en particulier dans les zones de topographie accidentée ou à grande échelle. Pour les études de gravité de haute précision à l'échelle mondiale, le processus de correction de la topographie doit prendre en compte l'effet topographique de la Terre entière. Mais pour les applications locales à régionales basées sur des variations relatives à l'intérieur de la zone, nous montrons que la topographie tronquée à une distance spécifique peut être adéquate, même si ignorer la topographie de cette distance peut générer des erreurs. Pour soutenir ces arguments, nous montrons les relations entre les erreurs relatives à la gravité, la distance de troncature de la topographie et l'étendue de la zone d'étude. Enfin, nous abordons le problème: les mesures GOCE sont-elles pertinentes pour obtenir une image détaillée de la structure d'une plaque de subduction, y compris sa géométrie et ses variations latérales? Les résultats du calcul des avec des modèles de subduction synthétiques calculés à l’altitude moyenne du GOCE (255 km) démontrent que les bords de subduction et les variations latérales du pendage produisent des variations des gradients détectables avec le jeu de données GOCE. Dans l'application à la zone de subduction Izu-Bonin-Mariana (IBM), la topographie et les effets bathymétriques ont été supprimés avec succès. Cependant, dans l'application au cas réel de la zone de subduction Izu-Bonin-Mariana, les caractéristiques géométriques du second ordre du slab sont difficiles à détecter en raison de la présence des effets crustaux restants. Ceci est dû à l'imprécision du modèle crustal global existant qui est utilisée, qui conduit à une élimination impropre de l'effet crustal<br>Nowadays, the scientific community has at its disposal gravity and gravity gradient datasets with unprecedented accuracy and spatial resolution that enhances our knowledge of Earth gravitational field at various scales and wavelengths, obtained from ground to satellite measurements. In parallel with gravimetry, the advancement of satellite observations provides the community with more detailed digital elevation models to reflect the Earth’s structure geometry. Together, these novel datasets provide a great opportunity to better understand the Earth’s structures and dynamics at local, regional, and global scales. The use and interpretation of these high-quality data require refinement of standard approaches in gravity-related data processing and analysis. This thesis consists of a series of studies aiming to improve the precision in the chain of gravity and gravity gradient data processing for geodynamic studies. To that aim, we develop a tool, named GEEC (Gal Eötvös Earth Calculator) to compute precisely the gravity and gravity gradients effects of due to any mass body regardless of its geometry and its distance from measurements. The gravity and gravity gradients effects are computed analytically using the line integral solution of an irregular polyhedron. The validations at local, regional, and global scales confirm the robustness of GEEC’s performance, where the resolution of the model, that depends on both size of the body mass and its distance from the measurement point, control strongly the accuracy of the results. We present an application for assessing the optimum parameters in computing gravity and gravity gradients due to topography variations. Topography has a major contribution in Earth gravitational attraction, therefore the estimation of topography effects must be carefully considered in the processing of gravity data, especially in areas of rugged topography or in large-scale studies. For high-accuracy gravity studies at a global scale, the topography correction process must consider the topography effect of the entire Earth. But for local to regional applications based on relative variations within the zone, we show that truncated topography at a specific distance can be adequate, although, ignoring the topography pas this distance could produce errors. To support these arguments, we show the relationships between gravity relative errors, topography truncation distance, and the extent of study zone. Lastly, we approach the issue: Are GOCE measurements relevant to obtain a detailed image of the structure of a subducting plate, including its geometry and lateral variation? The results of gravity gradient forward modelling using synthetic subduction models computed at GOCE’s mean altitude (255 km) demonstrate that both subduction edges and lateral variations of subduction angle produce gravity gradient variations that are detectable with GOCE dataset (∼100 km wavelength and 10 mE amplitude). However, in the application to the real case of Izu-Bonin-Mariana subduction zone, the second-order geometric features of the subducting plate are difficult to be detected due to the presence of the remaining crustal effects. This is caused by the inaccuracy of the existing global crustal model, that leads to inaccurate crustal effect removal

La rapidité, la consommation énergétique et l'efficacité des systèmes logiciels et matériels sont devenues les préoccupations majeures de la communauté informatique de nos jours. Gérer de manière correcte et efficace les problématiques mémoire est essentiel pour le développement des programmes de grande tailles sur des architectures de plus en plus complexes. Dans ce contexte, cette thèse contribue aux domaines de l'analyse mémoire et de la compilation tant sur les aspects théoriques que sur les aspects pratiques et expérimentaux. Outre l'étude approfondie de l'état de l'art des analyses mémoire et des différentes limitations qu'elles montrent, notre contribution réside dans la conception et l'évaluation de nouvelles analyses qui remédient au manque de précision des techniques publiées et implémentées. Nous nous sommes principalement attachés à améliorer l'analyse de pointeurs appartenant à une même structure de données, afin de lever une des limitations majeures des compilateurs actuels. Nous développons nos analyses dans le cadre général de l'interprétation abstraite « non dense ». Ce choix est motivé par les aspects de correction et d'efficacité : deux critères requis pour une intégration facile dans un compilateur. La première analyse que nous concevons est basée sur l'analyse d'intervalles des variables entières ; elle utilise le fait que deux pointeurs définis à l'aide d'un même pointeur de base n'aliasent pas si les valeurs possibles des décalages sont disjointes. La seconde analyse que nous développons est inspirée du domaine abstrait des Pentagones ; elle génère des relations d'ordre strict entre des paires de pointeurs comparables. Enfin, nous combinons et enrichissons les deux analyses précédentes dans un cadre plus général. Ces analyses ont été implémentées dans le compilateur LLVM. Nous expérimentons et évaluons leurs performances, et les comparons aux implémentations disponibles selon deux métriques : le nombre de paires de pointeurs pour lesquelles nous inférons le non-aliasing et les optimisations rendues possibles par nos analyses<br>This thesis was motivated by the emergence of massively parallel processing and supercomputingthat tend to make computer programming extremely performing. Speedup, the power consump-tion, and the efficiency of both software and hardware are nowadays the main concerns of theinformation systems community. Handling memory in a correct and efficient way is a step towardless complex and more performing programs and architectures. This thesis falls into this contextand contributes to memory analysis and compilation fields in both theoretical and experimentalaspects.Besides the deep study of the current state-of-the-art of memory analyses and their limitations,our theoretical results stand in designing new algorithms to recover part of the imprecisionthat published techniques still show. Among the present limitations, we focus our research onthe pointer arithmetic to disambiguate pointers within the same data structure. We develop ouranalyses in the abstract interpretation framework. The key idea behind this choice is correctness,and scalability: two requisite criteria for analyses to be embedded to the compiler construction.The first alias analysis we design is based on the range lattice of integer variables. Given a pair ofpointers defined from a common base pointer, they are disjoint if their offsets cannot have valuesthat intersect at runtime. The second pointer analysis we develop is inspired from the Pentagonabstract domain. We conclude that two pointers do not alias whenever we are able to build astrict relation between them, valid at program points where the two variables are simultaneouslyalive. In a third algorithm we design, we combine both the first and second analysis, and enhancethem with a coarse grained but efficient analysis to deal with non related pointers.We implement these analyses on top of the LLVM compiler. We experiment and evaluate theirperformance based on two metrics: the number of disambiguated pairs of pointers compared tocommon analyses of the compiler, and the optimizations further enabled thanks to the extraprecision they introduce

This thesis is about minimal transitive factorizations of permutations into transpositions. We focus on finding direct combinatorial proofs for the cases where no such direct combinatorial proofs were known. We give a description of what has been done previously in the subject at the direct combinatorial level and in general. We give some new proofs for the known cases. We then present an algorithm that is a bijection between the set of elements in {1, ..., k} dropped into n cyclically ordered boxes and some combinatorial structures involving trees attached to boxes, where these structures depend on whether k > n, k = n or k < n. The inverse of this bijection consists of removing vertices from trees and placing them in boxes in a simple way. In particular this gives a bijection between parking functions of length n and rooted forests on n elements. Also, it turns out that this bijection allows us to give a direct combinatorial derivation of the number of minimal transitive factorizations into transpositions of the permutations that are the product of two disjoint cycles.