In reasoning about multi-agent systems, it is important to look beyond the realm of propositional logic and to reason about the knowledge of agents within the system, as what they know about the environment will affect how they behave. A useful tool for formalizing and analyzing what agents know is epistemic logic, a modal logic developed by philosophers in the early 1960s. Epistemic logic is key to understanding knowledge in multi-agent systems, but insufficient if one wishes to study how the agents' knowledge changes over time. To do this, it is necessary to use a logic that combines dynamic and epistemic modalities, called dynamic epistemic logic. Some formalizations of dynamic epistemic logic use Kripke semantics for the states and actions, while others take a more algebraic approach, and use order-theoretic structures in their semantics. We discuss several of these logics, but focus predominantly on the algebraic framework for dynamic epistemic logic. / Past approaches to dynamic epistemic logic have typically been focused on actions whose primary purpose is to communicate information from one agent to another. These actions are unable to alter the valuation of any proposition within the system. In fields such as security and economics, it is easy to imagine situations in which this sort of action would be insufficient. Instead, we expand the framework to include both communication actions and actions that change the state of the system. Furthermore, we propose a new modality which captures both epistemic and propositional changes that result from the agents' actions. / En raisonnement sur les systemes multi-agents, il est important de regarder au-dela du domaine de la logique propositionnelle et de raisonner sur les con- naissances des agents au sein du syst`eme, parce que ce qu'ils savent au sujet de l'environnement influe sur la mani`ere dont ils se comportent. Un outil utile pour l'analyse et la formalisation de ce que les agents savent, est la logique epistemique, une logique modale developpee par les philosophes du debut des annees 1960. La logique epistemique est la cle de la comprehension des connaissances dans les systemes multi-agents, mais elle est insuffisante si l'on veut etudier la facon dont la connaissance des agents evolue a travers le temps. Pour ce faire, il est necessaire de recourir a une logique qui allie des modalites dynamiques et epistemiques, appele la logique epistemique dynamique. Certaines formalisations de la logique epistemique dynamique utilisent la semantique de Kripke pour les etats et les actions, tandis que d'autres prennent une approche algebrique, et utilisent les structures ordonne dans leur semantique. Nous discutons plusieurs de ces logiques, mais nous nous concentrons principalement sur le cadre algebrique pour la logique epistemique dynamique. / Les approches adoptees dans le passe a la logique epistemique dynamique ont generalement ete axe sur les actions dont l'objectif principal est de communiquer des informations d'un agent a un autre. Ces actions sont dans l'impossibilite de modifier l' evaluation de toute proposition au sein du systeme. Dans des domaines tels que la securite et l' economie, il est facile d'imaginer des situations dans lesquelles ce type d'action serait insuffisante. Au lieu de cela, nous etendons le cadre algebrique pour inclure a la fois des actions de communication et des actions qui changent l' etat du systeme. En outre, nous proposons une nouvelle modalite qui permet de capturer a la fois les changements epistemiques et les changements propositionels qui resultent de l'action des agents.

The modeling of hair and hair-like patterns, including those of grass and fur, is recurrent in the computer graphics literature. The reproduction of the extensive variety of these arrangements, and their generation from scarce information, remains a challenge for the computational models that describe them. This thesis introduces a novel mathematical model of hair-like patterns to the field of computer graphics, one that is based on a class of minimal surfaces called generalized helicoids. This representation is characterized by intuitive parameters that control the curvature of a hair along its tangent, normal and binormal directions, and its elevation angle. This representation equips a hair with information not only about its own geometry but also about the geometric behavior of other hairs in its vicinity. A hair modeling framework is proposed to investigate these properties. This framework includes an implicit surface sampling method based on interacting particles for determining hair root locations. It also introduces algorithms for interpolating generalized helicoids from sparse hair samples as well as a fitting algorithm for modeling unparameterized hair datasets. The usefulness of the generalized helicoid is motivated via several applications including the generation of different types of hair geometry, hair interpolation, hair fitting and wisp generation. / La modélisation de cheveux et de structures s'apparentant aux cheveux, incluant celles de l'herbe et de la fourrure, est courante dans la littérature en informatique graphique. La reproduction de divers arrangements de cheveux, et leur génération à partir d'information limitée, reste un défi pour les modèles mathématiques de cheveux. Cette thèse introduit une nouvelle représentation mathématique de structures de cheveux au domaine de l'informatique graphique. Cette représentation est basée sur une classe de surfaces minimales appelée hélicoïdes généralisés, et est caractérisée par des paramètres intuitifs contrôlant la courbure d'un cheveux le long de ses directions tangents, normales, et binomiales, ainsi que son angle d'élévation. Non seulement cette représentation équipe-t-elle un cheveux avec de l'information sur sa propre géométrie, mais elle indique aussi le comportement géométrique des autres cheveux dans son voisinage. Afin d'étudier ces propriétés, une plateforme de modélisation de cheveux est proposée. Cette plateforme inclut une méthode d'échantillonnage pour surface implicite basée sur l'interaction de particules afin de déterminer l'emplacement de la racine des cheveux. Elle présente aussi des algorithmes pour interpoler des hélicoïdes généralisés à partir d'échantillons de cheveux clairsemés ainsi qu'un algorithme de fitting (ajustement) pour la modélisation d'ensembles de données comportant des cheveux non paramétrisés. L'utilité de l'hélicoïde généralisé est motivée par plusieurs applications, notamment la reproduction de différents types de géométrie de cheveux, l'interpolation de cheveux, le fitting de cheveux, et la génération de brins de cheveux.

Data are produced in large quantities and in various forms around the globe everyday. Researchers advance their research depending on the availability of necessary data and the discovery of them. As people's demand to manage the data grows, however, three problems appear to hinder the attempts to effectively leverage the data. One is the semantic heterogeneity found in linking different data sources. Database designers create data with different semantics; even data within the same domain may differ in meaning. If users want to acquire all the obtainable information, they have to write different queries with different semantics. One solution to such a problem is the use of ontology. An ontology is defined as a specification for the concepts of an agent (or a community of agents) and the relationships between them (Gruber 1995). Concepts and relationships between concepts are extracted from the data to form knowledge network. Other parties wishing to connect their data to the knowledge network could share, enrich and distribute the vocabulary of the ontology. Users could also write queries to the ontology by any RDF query language (Brickly 2004). The use of ontology is part of the Web 3.0's effort to provide a semantic-sensitive global knowledge network. A second problem is about new ways to access data resources with ontology information. People used to build application-specific user interfaces to databases, which were offline. Now many choose to expose data in Web Services. Web services are a system to provide HTTP-based remote request calling services that are described in a machine-readable format (Haas and Brown 2004). They usually provide application (or web) programming interfaces to manage data. The question is Web Services are born in a world of applications relying on conventional ways to connect to data sources. For example, D2RQ (Bizer and Seaborne 2004) translates queries against ontology to SQL queries and it depends on JDBC to read from relational databases. Now the interfaces for these data sources are going to be changed. The Semantic Web world faces the challenge to lose data sources. If Web Services were going to spread over the Internet one day, this lack of connection would hold back me from applying the ontology to connect to heterogeneous data sources.A third problem (or constraint) is working within the specific project domain. I embed this within a humanities cyberinfrastructure that integrates Chinese biographical, historical and geographical data. The data sources come in various forms – local and remote relational databases and, RESTful Web Services. Working with both legacy databases and the new web application interfaces narrowed down my choice of solutions. Commercial products provide ways to "ontologicalize" the Web Services. I argue that they are heavyweight (e.g. unnecessary components bound with the product) and cost-prohibitive for small-scale projects like ours. Several mature open source solutions featuring working with relational databases provide no or very limited access to Web Services. For example, no clue is found in D2RQ to join Web Services into their system, while OpenLink Virtuoso answers calls for SOAP but cannot manage data from RESTful Web Services. I propose to build a connection between ontologies and Web Services. I devise the metadata to represent non-RDF Web Services in ontology, and I revise the code and create new data structures in D2RQ to support ontology queries to data from RESTful Web Services. / Les données sont produites en grandes quantités et sous diverses formes dans le monde et tous les jours. Les chercheurs avancer leurs recherches en fonction de la disponibilité des données nécessaires et la découverte de leur. Comme la demande des gens pour gérer les données croît, toutefois, trois problèmes semblent entraver les tentatives d'exploiter efficacement les données. La première est l'hétérogénéité sémantique dans reliant différentes sources de données. Concepteurs de créer des données de base de données avec une sémantique différente; même les données dans le même domaine peuvent avoir une signification différente. Si les utilisateurs souhaitent obtenir toute l'information obtenue, ils doivent écrire des requêtes différentes avec une sémantique différente. Une solution à ce problème est l'utilisation de l'ontologie. Une ontologie est définie comme une spécification pour les concepts d'un agent (ou d'une communauté d'agents) et les relations entre eux (Gruber 1995). Concepts et les relations entre les concepts sont extraites des données pour former réseau de connaissances. Les autres parties qui souhaitent se connecter leurs données au réseau de connaissances pourraient partager, enrichir et diffuser le vocabulaire de l'ontologie. Les utilisateurs peuvent aussi écrire des requêtes à l'ontologie par une requête RDF langue (Brickley 2004). L'utilisation de l'ontologie est une partie de l'effort de Web 3.0 pour fournir un réseau de connaissances sémantiques sensibles mondiale.Un deuxième problème est sur le point de nouvelles façons d'accéder aux données des ressources de l'information ontologie. Les gens de construire des interfaces utilisateur des applications spécifiques aux bases de données, qui ont été mises hors. Maintenant, de nombreux fournisseurs de données choisir pour exposer les données des services web. Les services web sont un système pour fournir la demande HTTP à distance d'appeler les services qui sont décrits dans un format lisible par machine (Haas and Brown 2004). Par exemple, D2RQ (Bizer and Seaborne 2004) se traduit par des requêtes sur l'ontologie de requêtes SQL, et cela dépend de JDBC pour lire à partir des bases de données relationnelles. Maintenant, les interfaces de ces sources de données vont être modifiées. Le monde du web sémantique doit relever le défi de perdre des sources de données. Si les services web ont été va se répandre sur Internet, un jour, ce manque de connexion tiendrait nous ramène de l'application de l'ontologie de se connecter à des sources de données hétérogènes.Un troisième problème (ou contrainte) est travailler dans le domaine des projets spécifiques. Nous incorporer cela dans une cyber-infrastructure qui intègre les sciences humaines chinois biographiques, des données historiques et géographiques. Les sources de données prennent des formes diverses - bases de données locales et distantes relationnelles et, les services web RESTful. Travailler avec les anciennes bases de données à la fois et l'application web de nouvelles interfaces rétréci vers le bas notre choix de solutions. Produits commerciaux offrent des moyens à ontologicalize les services web. Nous soutenons qu'ils sont lourds (par exemple, les composants inutiles liés au produit) et ils sont coûteuse pour les projets à petite échelle, comme notre projet. Plusieurs solutions open source mature offrant de travailler avec des bases de données relationnelles ne fournissent pas ou peu accès aux services Web. Nous proposons de construire un lien entre les ontologies et les services web. Nous trouver les métadonnées pour représenter les non-RDF services web dans l'ontologie, et nous revoir le code et créer de nouvelles structures de données en D2RQ à l'appui des requêtes ontologie à partir des données des services web RESTful.

Parallelization and optimization of the MATLAB® programming language presents severalchallenges due to the dynamic nature of MATLAB. Since MATLAB does not have statictype declarations, neither the shape and size of arrays, nor the loop bounds are known atcompile-time. This means that many standard array dependence tests and associated transformationscannot be applied straight-forwardly. On the other hand, many MATLAB programsoperate on arrays using loops and thus are ideal candidates for loop transformationsand possibly loop vectorization/parallelization.This thesis presents a new framework, McFLAT, which uses profile-based training runs todetermine likely loop-bounds ranges for which specialized versions of the loops may begenerated. The main idea is to collect information about observed loop bounds and hotloops using training data which is then used to heuristically decide upon which loops andwhich ranges are worth specializing using a variety of loop transformations.Our McFLAT framework has been implemented as part of the McLAB extensible compilertoolkit. Currently, McFLAT is used to automatically transform ordinary MATLAB code intospecialized MATLAB code with transformations applied to it. This specialized code can beexecuted on any MATLAB system, and we report results for four execution engines, Mathwork'sproprietary MATLAB system, the GNU Octave open-source interpreter, McLAB'sMcVM interpreter and the McVM JIT. For several benchmarks, we observed significantspeedups for the specialized versions, and noted that loop transformations had differentimpacts depending on the loop range and execution engine.This thesis reports on the design and implementation of McFLAT, a framework that isdesigned to study the effect of various loop transformations on different loop-bound rangesby introducing loop-level specializations in MATLAB programs. / La parallelisation et l'optimisation du langage de programmation informatique MATLAB®représente plusieurs défis compte tenu du caractère dynamique de ce dernier.Puisque MATLAB ne possède pas de déclaration de type statique, ni son profil et la tailledes matrices ni les boucles limites, sont connus au temps de compilation. Cela signifieque plusieurs tests standardisés de la dépendance des matrices et de ses transformationsassociées ne peuvent pas ˆ etre appliqués dans une manière directe. D' autre part, plusieursprogrammes MATLAB sont opérés sur les matrices en utilisant les boucles et donc sontdes candidats idéals pour la transformation en boucle et possiblement la vectorisation enboucle/parallelisation.Cette hypothèse présente un nouveau cadre, McFLAT, qui exécute des entrainements basessur des profils afin de déterminer la portée des éventuelles boucles-limites pour qui des versionsspécialisées des boucles pourraient ˆ etre générées. L'idée principale est de faire une collecte d'information concernant les boucles en observation ainsi que les boucles chaudsen capitalisant sur les données d'entrainement qui sont ensuite utilisées pour décider heuristiquementsur quels boucles et limites il faut se spécialiser en utilisant une variété detransformateurs de boucles.Notre cadre McFLAT a été implémenté en tant que composant de McLAB extensible compilertoolkit. Actuellement, McFLAT, est utilisé pour transformer automatiquement le codeordinaire MATLAB en code spécialisé MATLAB avec des transformations appliquées à cedernier. Ce code spécialisé pourrait ensuite être exécuté sur tout systéme matlab et nouslivrons les résultats de quatre moteurs d'exécution, Mathwork's proprietary MATLAB system,le GNU Octave source-libre interprète, l'interprète McVM de mclab et le McVM JIT. Pour plusieurs repères, nous observons une rapidité significative pour les versions spécialisées, et on note que les transformations en boucle ont eu différents impacts qui dépendent de la limite des boucles et du moteur d'exécution.Ce mémoire se focalise sur le dessin et l'implémentation de McFLAT, un cadre qui estdésigné pour étudier les effets de plusieurs transformations en boucle sur plusieurs niveauxde boucles-limites en introduisant des spécialisations au niveau des boucles dans les programmes MATLAB.

The Internet has broadened the meaning of identity. In real life, we normally have fixed identities. Earlier on the Internet, pseudonym was invented to identify users. As social networks came into play, social identity was introduced. While fixed identity is the most secure one, it restricts the freedom people have on the Internet. Although pseudonym is the easiest one to create among the three identity types, it makes it equally easy for malicious users to cheat on other people. One way malicious users can perform attacks on others with pseudonym is by whitewashing, where the malicious user takes advantage of the victim, with either pre-designed plots or simply by breaking pre-defined rules, and disappear on the network but later re-join the network with a new identity so that no one would know about his previous activities. Social identity differs from the other two by making use of the relations between two people and protecting both the individual user's privacy and the organization's security. This thesis studies the effect of whitewashing under different identity types and compares their behaviors of resisting whitewashing. We use game theory to model the process of whitewashing and compute its effect upon the whole population for each identity type. In most of the cases, social identity is better at eliminating whitewashers. Besides, the Matlab simulation experiments reveal additional interesting facts about the three identity types that might shed light on future identity management schemes. / Le sens du mot "identité" s'élargit dans le contexte d'Internet. Dans la vraie vie, sauf dans des cas très particuliers, nous avons une identité fixe. Très tôt sur Internet, on a eu recours aux pseudonymes pour identifier les usagers. Avec l'évolution des réseaux sociaux est venue l'identité sociale ("social identity" en Anglais). Bien qu'elle représente le mode d'identité le plus sécuritaire, l'identité fixe impose des limites importantes qui la rendent difficile d'utilisation sur Internet. Parmi les trois modes d'identité, le pseudonyme est le plus facile à créer, mais il permet aussi aux usagers malveillants de facilement abuser de la confiance des autres. Suite aux actes malhonnêtes (arnaques ou non respect des règles établies, par exemple), un usager malveillant peut changer de pseudonyme pour blanchir son identité ("whitewashing" en anglais). Il disparaît donc du réseau pendant un certain temps pour réapparaitre plus tard sous une nouvelle identité aucunement liée à l'ancienne. L'identité sociale diffère de l'identité fixe et des pseudonymes en se basant sur les relations entre deux personnes tout en protégeant la vie privée de l'utilisateur et la sécurité de l'organisation.Cette thèse analyse les effets du blanchissage selon le mode d'identité utilisé et compare les différents comportements de résistance au blanchissage. La théorie des jeux est utilisée pour modéliser le blanchissage et calculer son effet sur la population pour chaque mode d'identité utilisé. Dans la majorité des cas, l'identité sociale est plus apte à éliminer les blanchisseurs. Des simulations Matlab révèlent aussi des faits intéressants au sujet des trois modes d'identité qui pourraient aider à l'élaboration de futurs systèmes de gestion d'identité.

Security has emerged as the most feared aspect of cloud computing and a major hindrance for the customers. Current cloud framework does not allow encrypted data to be stored due to the absence of efficient searchable encryption schemes that allow query execution on a cloud database. Storing unencrypted data exposes the data not only to an external attacker but also to the cloud provider itself. Thus, trusting a provider with confidential data is highly risky. To enable querying on a cloud database without compromising data confidentiality, we propose to use data obfuscation through visual cryptography. A new scheme for visual cryptography is developed and configured for the cloud for storing and retrieving textual data. Testing the system with query execution on a cloud database indicates full accuracy in record retrievals with negligible false positives. In addition, the system is resilient to attacks from within and outside the cloud. Since standard encryption and key management are avoided, our approach is computationally efficient and data confidentiality is maintained. / La sécurité a émergé comme l'aspect le plus redouté de l'informatique en nuage et comme un obstacle majeur pour les clients. Le cadre actuel de l'informatique en nuage ne permet pas que les données chiffrées soient stockées en raison de l'absence de schémas efficaces de cryptage qui permettent l'exécution des requêtes sur une base de données des nuages. Le stockage des données non cryptées expose les données non seulement à un agresseur extérieur, mais aussi au fournisseur de nuage lui-même. Ainsi, faire confiance à un fournisseur avec des données confidentielles est très risqué.Afin de permettre des requêtes sur une base de données des nuages sans compromettre la confidentialité des données, nous proposons d'utiliser l'obscurcissement des données à travers la cryptographie visuelle. Un nouveau schéma pour la cryptographie visuelle est développé et configuré pour le nuage pour stocker et récupérer des données textuelles. Tester le système avec l'exécution des requêtes sur une base de données nuée indique une grande précision dans la récupération des enregistrements avec négligeables faux positifs. En outre, le système est résistant aux attaques de l'intérieur et l'extérieur du nuage. Parce que le cryptage standard et la gestion des clés sont évités, notre approche est mathématiquement efficace et la confidentialité des données est assurée.

Current business applications use a multi-tier architecture where business processing is done in a cluster of application servers, all querying a single shared database server making it a performance bottleneck. A prevalent solution to reduce the load on the database is to cache database results in the application servers as business entities. Since each of the in-memory application cache is small and independent of each other, a naïve load balancing algorithm like round-robin would result in cache redundancy and lead to cache evictions. By clustering these caches, we get a distributed cache with a larger aggregate capacity, where an object is retrieved from the remote cache if it is not found in local cache. This approach eliminates redundancy and reduces load on the database by a great extent. However, accessing remote objects incurs network latency affecting response time. In this thesis, we transform the distributed cache into a hybrid one that supports replication so that popular requests could be served locally by multiple application servers. We take advantage of this hybrid cache by developing a holistic caching infrastructure. This infrastructure is comprised of an application monitoring tool and an analysis framework that work continuously alongside live application to generate content-aware request distribution and caching policies. The policies are generated by request-centric strategies that aim to localize popular requests to specific servers in order to reduce remote calls. These strategies are flexible and can be adapted easily for various workloads and application needs. Experimental results show that we indeed derive substantial gain in performance using our infrastructure. Our strategies resulted in faster response time under normal workload and scaled much better with higher throughput than existing approaches under peak workload. / Les applications commerciales courantes utilisent une architecture multi-tiers où le traitement logique est effectué en un groupe de serveurs qui accèdent à une seule base de données partagée, ce qui la rend un point d'encombrement. Une solution répandue qui réduit la charge sur la base de données est la sauvegarde des résultats de requetes à la base de données au niveau des serveurs d'applications comme des entitiés logiques. Tandis que chaque cache local de chaque serveur est limité et est indépendant des autres, un algorithme naïve de balancement de la charge, comme round-robin, résultera en des duplications de copies dans les différents caches et mènera à des explusions de ceux-ci. En regroupant ces caches, nous formons un seul cache distribué avec une large capacité, où un objet est extrait à partir d'un cache distant s'il n'est pas trouvé localement. Cet approche élimine la redondance et réduit considérablement la charge sur la base de données. Cependant, accéder à des objets distants encours une latence au niveau du réseau ce qui affecte les temps de réponses.Dans cette thèse, nous transformons le cache distribué en un cache hybride qui supporte la duplication ce qui permet de servir les requêttes les plus populaires localement par plusieurs serveurs d'applications. Nous prenons avantage de cette structure hybride du cache en developpant une infrastructure holistique du cache. Cette infrastrcuture comprend un outil de surveillance et une infrastructure d'analyse qui fonctionne d'une façon continue et parallèle avec l'application afin de générer un contenu qui prend en considération la distribution de requêtes et les politiques du cache. Les politiques sont générées par des stratégies orientées requêtes qui visent à localizer les requêtes populaires à des serveurs spécifiques et ce pour réduire les appels distants. Ces stratégies sont flexibles et peuvent être ajustées facilement pour different charges de travail et besoins d'applications. Des résultats expérimentaux montrent qu'effectivement nous dérivons un gain substantial en utilisant notre infrastructure. Nos stratégies ont resulté en des temps de réponses rapides sous une charge de travail normale et donnent des bons résultats lors d'un débit élevé comparativemnt à d'autres approches sous des charges de travail de pointe.

Speculative multithreading (SpMT), also known as thread level speculation (TLS), is a dynamic parallelization technique that relies on out-of-order execution, dependence buffering, and misspeculation rollback to achieve speedup of sequential programs on multiprocessors. A large number of hardware studies have shown good results for irregular programs, as have a smaller number of software studies in the context of loop level speculation for unmanaged languages.In this thesis we explore software method level speculation for Java. A software environment means that speculation will run on existing multiprocessors, at the cost of extra overhead. Method level speculation (MLS) is a kind of SpMT / TLS that creates threads on method invocation, executing the continuation speculatively. Although MLS can subsume loop level speculation, it is still a relatively unexplored paradigm. The Java programming language and virtual machine environment are rich and complex, posing many implementation challenges, but also supporting a compelling variety of object-oriented programs.We first describe the design and implementation of a prototype system in a Java bytecode interpreter. This includes support for various MLS components, such as return value prediction and dependence buffering, as well as various interactions with features of the Java virtual machine, for example bytecode interpretation, exception handling, and the Java memory model. Experimentally we found that although high thread overheads preclude speedup, we could extract significant parallelism if overheads were excluded. Furthermore, profiling revealed three key areas for optimization.The first key area for optimization was the return value prediction system. In our initial model, a variety of predictors were all executing naïvely on every method invocation, in order that a hybrid predictor might select the best performing ones. We developed an adaptive system wherein hybrid predictors dynamically specialize on a per-callsite basis, thus dramatically reducing speed and memory costs whilst maintaining high accuracy.The second area for optimization was the nesting model. Our initial system only allowed for out-of-order nesting, wherein a single parent thread creates multiple child threads. Enabling support for in-order nesting exposes significantly more parallelization opportunities, because now speculative child threads can create their own children that are even more speculative. This required developing a memory manager for child threads based on recycling aggregate data structures. We present an operational semantics for our nesting model derived from our implementation.Finally, we use this semantics to address the third area for optimization, namely a need for better fork heuristics. Initial heuristics based on online profiling made it difficult to identify the best places to create threads due to complex feedback interactions between speculation decisions at independent speculation points. This problem grew exponentially worse with the support for in-order nesting. Instead, we chose to clarify the effect of program structure on runtime parallelism. We did this by systematically exploring the interaction between speculation and a variety of coding idioms. The patterns we identify are intended to guide both manual parallelization and static compilation efforts. / L'exécution spéculative multifils (SpMT), aussi connue sous le nom de spéculation au niveau des fils d'exécution (TLS), est une technique de parallélisation dynamique qui se base sur l'exécution dans le désordre, la mise en mémoire tampon des dépendances spéculatives, et le refoulement des erreurs de spéculation pour atteindre l'accélération des programmes séquentiels sur les multiprocesseurs. D'extensives études architecturales ont révélé de bons résultats dans le cas des programmes irréguliers, tout comme plusieurs études logiciel dans la spéculation au niveau des boucles dans un langage non géré. Dans ce mémoire, nous explorons la spéculation logiciel au niveau des méthodes pour Java. Un environnement logiciel signifie que la spéculation s'exécute sur les multiprocesseurs existants, au coût de charge additionnelle. La spéculation au niveau des méthodes (MLS) est une sorte de SpMT / TLS où des fils d'exécution sont créés à chaque invocation de méthode, exécutant les instructions qui suivent de manière spéculative. Malgré la possibilité de subsomption de la spéculation au niveau des boucles par la spéculation au niveau des méthodes, ce paradigme est relativement peu exploré. Le langage de programmation Java, ainsi que l'environnement de sa machine virtuelle, sont riches et complexes, ce qui pose plusieurs difficultés à l'implémentation, mais qui a l'avantage de supporter une grande variété de programmes orientés objet. Nous décrivons d'abord la conception et l'implémentation d'un système prototype dans un interpréteur de code-octet Java. Cette implémentation supporte une variété de composantes de la spéculation au niveau des méthodes, telles la prédiction des valeurs de retour, la mise en mémoire tampon des dépendances spéculatives, ainsi qu'une variété d'interactions avec des caractéristiques de la machine virtuelle Java (JVM), par exemple, l'interprétation du code-octet, le gestion des exceptions et le modèle de la mémoire de Java. Des expériences nous ont permis de constater d'encourageants résultats quant à la parallélisation des programmes, malgré une charge additionnelle importante dû à l'embranchement des fils d'exécution, ce qui empêche d'obtenir une accélération significative. De plus, le profilage effectué a révélé trois secteurs d'optimisation importants. La première optimisation étudié est la prédiction des valeurs de retour. Notre modèle initial utilisait plusieurs outils de prédiction différents pour chaque invocation de méthode, afin qu'un outil de prédiction hybride puisse choisir les plus performants. Nous avons développé un système adaptatif où les outils de prédiction hybrides se spécialisent dynamiquement pour chaque site d'invocation, réduisant drastiquement la charge mémoire additionnelle et les ralentissements tout en préservant un haut degré de précision. Le deuxième secteur d'optimisation étudié est celui des modèles d'emboîtement. Notre modèle initial permettait seulement l'emboîtement dans le désordre, où un seul fil d'exécution peut en créer plusieurs fils d'exécution spéculatifs. L'introduction du support de l'emboîtement en ordre expose un nombre conséquent d'opportunités de parallélisation, parce qu'un fil d'exécution spéculatif peut maintenant en créer un autre, encore plus spéculatif. Pour ce faire, nous avons développé un gestionnaire de mémoire pour les fils d'exécution spéculatifs basé sur le recyclage des structures de donnée agrégés. Nous présentons une sémantique des opérations de notre modèle d'emboîtement dérivée de notre implémentation. Finalement, nous utilisons cette sémantique des opérations pour optimiser nos heuristiques d'embranchement. Nous avons choisi de clarifier l'effet de la structure des programmes sur son parallélisme. Pour ce faire, nous avons exploré systématiquement l'interaction de la spéculation avec une variété d'idiomes de programmation. Les patrons identifiés sont utiles pour guider les efforts de parallélisation manuelle ainsi que de compilation statique.

Online identities play critical roles in the current Internet world. One of the virtues of traditional online identities, in forms of pseudonyms, is the privacy protection of online users. Users can create as many anonymous identities as they want with only an email account. However, the anonymity itself could be a limitation because of the lack of accountability.The prevalence of online social networks inspires us to create a social pseudonym framework through which it is possible to determine proximity between pseudonyms while retaining privacy. The basic idea of this work is mapping the online social network into a geometric space and assigning each user a coordinate according to the relationship with his/her neighborhood. The coordinate itself will not disclose any information of a user, but by computing the coordinates distance, proximity between users could be estimated with a certain probability. I evaluated the framework with several real online social network datasets. The results indicate that the proposed framework is promising under certain conditions. / Dans le contexte d'Internet, les identifiants des usagers jouent un rôle critique. L'un des avantages des identifiants traditionnels, soient les pseudonymes, est de fournir une protection de la vie privée des usagers. Les usagers peuvent créer autant d'identifiants anonymes qu'ils le désirent simplement en utilisant une adresse courriel. Par contre, l'anonymité même peut devenir un facteur limitant dû à la déresponsabilisation des usagers. L'importance des réseaux sociaux en ligne nous inspire à créer un système de pseudonymes sociaux à travers lequel il sera possible de déterminer la proximité entre pseudonymes tout en conservant la confidentialité. Le système se base sur l'idée d'associer un réseau social à un espace géométrique et d'assigner des coordonnées à chaque usager qui dépendent de la relation entre l'usager et son voisinage. Les coordonnées elles-même ne fournissent aucune information confidentielle à propos d'un usager. Cependant, en calculant la distance entre différentes coordonnées, la proximité entre usagers peut être estimée avec une certaine probabilité. J'ai évalué le système avec des données provenant de réseaux sociaux réels. Les résultats indiquent que le système proposé, en imposant certaines conditions, est prometteur.

Developer documentation helps developers learn frameworks and libraries, yet developing and maintaining accurate documentation require considerable effort and resources. Contributors who work on developer documentation need to at least take into account the project's code and the support needs of users. Although related, the documentation, the code, and the support needs evolve and are not always synchronized: for example, new features in the code are not always documented and questions repeatedly asked by users on support channels such as mailing lists may not be addressed by the documentation. Our thesis is that by studying how the relationships between documentation, code, and users' support needs are created and maintained, we can identify documentation improvements and automatically recommend some of these improvements to contributors. In this dissertation, we (1) studied the perspective of documentation contributors by interviewing open source contributors and users, (2) developed a technique that automatically generates the model of documentation, code, and users' support needs, (3) devised a technique that recovers fine-grained traceability links between the learning resources and the code, (4) investigated strategies to infer high-level documentation structures based on the traceability links, and (5) devised a recommendation system that uses the traceability links and the high-level documentation structures to suggest adaptive changes to the documentation when the underlying code evolves. / La documentation pour les développeurs aide ces derniers à apprendre à utiliser des bibliothèques de fonctions et des cadres d'applications. Pourtant, créer et maintenir cette documentation requiert des efforts et des ressources considérables. Les contributeurs qui travaillent sur la documentation pour les développeurs doivent tenir compte de l'évolution du code et des besoins potentiels des utilisateurs de la documentation. Même s'ils sont reliés, la documentation, le code et les besoins des utilisateurs ne sont pas toujours synchronisés: par exemple, les nouvelles fonctionnalités ajoutées au code ne sont pas toujours documentées et la documentation n'apporte pas nécessairement de réponse aux questions posées à répétition sur des forums de discussion. Notre thèse est qu'en étudiant comment les relations entre la documentation, le code, et les besoins des utilisateurs sont crées et maintenues, nous pouvons identifier des possibilités d'améliorations à la documentation et automatiquement recommander certaines de ces améliorations aux contributeurs de documentation. Dans cette dissertation, nous avons (1) étudié la perspective des contributeurs de documentation en interviewant des contributeurs de projets en code source libre, (2) développé une technique qui génère automatique un modèle de la documentation, du code, et des questions des utilisateurs, (3) développé une technique qui recouvre les liens de traçabilité entre les ressources d'apprentissage et le code, (4) examiné des stratégies pour inférer des structures abstraites de documentation à partir des liens de traçabilité et (5) développé un système de recommandation qui utilise les liens de traçabilités et les structures abstraites de documentation pour suggérer des changements adaptatifs quand le code sous-jacent évolue.