Emulation is the practice of simulating one computer system on another. There are many methods of implementing an emulator. They exist on a performance continuum from simple interpretation to dynamic binary translation extended with various optimizations. Optimizations are diverse, including just in time compilation, large translation units, shadow stack, register mapping and many more. The goal of this thesis is to develop a high performance, portable emulator for the ARM v4 architecture without requiring substantial code analysis. This thesis describes the implementation of a dynamic binary translator translating to an intermediate language targeting a virtual machine. Targeting a virtual machine ensures that the emulator is portable. Optimizations implemented include forming large translation units and branch straightening in hot regions. The particular combination of translating to intermediate form for a virtual machine, and creating large translation units from hot regions does not seem to appear in the literature. The performance of the described dynamic binary translator exceeds the performance of an interpreter on the same platform by an order of magnitude. Code analysis was only used to straighten branches in hot regions. While many popular dynamic binary translation optimizations are not readily applicable when using a virtual machine target, the performance achieved shows that using virtual machine as translation target is viable method of implementing dynamic binary translator. / Graduate

Machine emulation allows for the simulation of a real or virtual machine, the source machine, on various host computers. A machine emulator interprets programs that are compiled for the emulated machine, but normally at a much reduced speed. Therefore, in order to increase the executions peed of such interpreted programs, a machine emulator may apply different dynamic optimization techniques. In our research we focus on emulators for real machines, i.e. existing computer architectures, and in particular on dynamic binary translation as the optimization technique. With dynamic binary translation, the machine instructions of the interpreted source program are translated in to machine instructions for the host machine during the interpretation of the program. Both, the machine emulator and its dynamic binary translator a resource and host machine specific, respectively, and are therefore traditionally hand-written. In this thesis we introduce the Walkabout/Yirr-Ma framework. Walkabout, initially developed by Sun Micro systems, allows among other things for the generation of instrumented machine emulators from a certain type of machine specification files. We extended Walkabout with our generic dynamic optimization framework ‘Yirr-Ma’ which defines an interface for the implementation of various dynamic optimizers: by instrumenting a Walkabout emulator’s instruction interpretation functions, Yirr-Ma observes and intercepts the interpretation of a source machine program, and applies dynamic optimizations to selected traces of interpreted instructions on demand. One instance of Yirr-Ma’s interface for dynamic optimizers implements our specification-driven dynamic binary translator, the major contribution of this thesis. At first we establish two things: a formal framework that describes the process of machine emulation by abstracting from real machines, and different classes of applicable dynamic optimizations. We define dynamic optimizations by a set of functions over the abstracted machine, and dynamic binary translation as one particular optimization function. Using this formalism, we then derive the upper bound for quality of dynamically translated machine instructions. Yirr-Ma’s dynamic binary translator implements the optimization functions of our formal framework by modules which are either generated from, or parameterized by, machine specification files. They thus allow for the adaptation of the dynamic binary translator to different source and host machines without hand-writing machine dependent code.

Dynamic binary translation allows us to analyze a program during execution without the need for a compiler or the program's source code. In this work, we present two applications of dynamic binary translation: tracematches and unread memory detection. Libraries are ubiquitous in modern software development. Each library requires that its clients follow certain conventions, depending on the domain of the library. Tracematches are a particularly expressive notation for specifying library usage conventions, but have only been implemented on top of Java. In this work, we leverage dynamic binary translation to enable the use of tracematches on executables, particularly for compiled C/C++ programs. The presence of memory that is never read, or memory writes that are never read during execution is wasteful, and may be also be indicative of bugs. In addition to tracematches, we present an unread memory detector. We built this detector using dynamic binary translation. We have implemented a tool which monitors tracematches on top of the Pin framework along with unread memory. We describe the operation of our tool using a series of motivating examples and then present our overall monitoring approach. Finally, we include benchmarks showing the overhead of our tool on 4 open source projects and report qualitative results.

Dynamic binary translation allows us to analyze a program during execution without the need for a compiler or the program's source code. In this work, we present two applications of dynamic binary translation: tracematches and unread memory detection. Libraries are ubiquitous in modern software development. Each library requires that its clients follow certain conventions, depending on the domain of the library. Tracematches are a particularly expressive notation for specifying library usage conventions, but have only been implemented on top of Java. In this work, we leverage dynamic binary translation to enable the use of tracematches on executables, particularly for compiled C/C++ programs. The presence of memory that is never read, or memory writes that are never read during execution is wasteful, and may be also be indicative of bugs. In addition to tracematches, we present an unread memory detector. We built this detector using dynamic binary translation. We have implemented a tool which monitors tracematches on top of the Pin framework along with unread memory. We describe the operation of our tool using a series of motivating examples and then present our overall monitoring approach. Finally, we include benchmarks showing the overhead of our tool on 4 open source projects and report qualitative results.

<div><p>Modern mobile devices have numerous ephemeral tasks. These tasks are driven by background activities, such as push notifications and sensor readings. In order to execute these tasks, the whole platform has to periodically wake up beforehand, and go to sleep afterwards. During this process, the OS kernel operates on power state of various IO devices, which has been identified as the bottleneck for energy efficiency. To this end, we want to offload this kernel phase to a more energy efficient, microcontroller level core, named peripheral core.</p></div><div><p> </p></div><div><p>To execute commodity OS on a peripheral core, existing approaches either require much engineering effort or incur high execution cost. Therefore, we proposed a new OS model called transkernel. By utilizing cross-ISA dynamic binary translation (DBT) technique, transkernel creates a virtualized environment on the peripheral core. It relies on a small set of stable interfaces. It is specialized for frequently executed kernel path. It exploits ISA similarities to reduce DBT overhead.</p></div><div><p> </p></div><div><p>We implement a transkernel model on ARM platform. With novel design and optimization, we demonstrate that a transkernel can gain energy efficiency. Moreover, it provides a new OS design to harness heterogeneous SoCs.</p></div>

This thesis presents new simulation techniques designed to speed up the simulation of microprocessor systems. The advanced simulation techniques may be applied to the simulator class which employs dynamic binary translation as its underlying technology. This research supports the hypothesis that faster simulation speeds can be realized by translating larger sections of the target program at runtime. The primary motivation for this research was to help facilitate comprehensive design-space exploration and hardware/software co-design of novel processor architectures by reducing the time required to run simulations. Instruction set simulators are used to design and to verify new system architectures, and to develop software in parallel with hardware. However, compromises must often be made when performing these tasks due to time constraints. This is particularly true in the embedded systems domain where there is a short time-to-market. The processing demands placed on simulation platforms are exacerbated further by the need to simulate the increasingly complex, multi-core processors of tomorrow. High speed simulators are therefore essential to reducing the time required to design and test advanced microprocessors, enabling new systems to be released ahead of the competition. Dynamic binary translation based simulators typically translate small sections of the target program at runtime. This research considers the translation of larger units of code in order to increase simulation speed. The new simulation techniques identify large sections of program code suitable for translation after analyzing a profile of the target program’s execution path built-up during simulation. The average instruction level simulation speed for the EEMBC benchmark suite is shown to be at least 63% faster for the new simulation techniques than for basic block dynamic binary translation based simulation and 14.8 times faster than interpretive simulation. The average cycle-approximate simulation speed is shown to be at least 32% faster for the new simulation techniques than for basic block dynamic binary translation based simulation and 8.37 times faster than cycle-accurate interpretive simulation.

Les unités de calculs qui composent les systèmes intégrés numériques d'aujourd'hui sont complexes, hétérogènes, et en nombre toujours croissant.La simulation, largement utilisée tant dans les phases de conception logicielle que matérielle de ces systèmes devient donc un vrai défi.Lors de la simulation du système, la performance est en grande partie édictée par la stratégie de simulation des jeux d'instructions des processeurs.La traduction binaire dynamique (DBT) est une technique qui a fait ses preuves dans ce contexte.Le principe de cette solution est de traduire au fur et à mesure les instructions du programme simulé (la cible), en instructions compréhensibles par la machine exécutant la simulation (l'hôte).C'est une technique rapide, mais la réalisation de simulateurs fondée sur cette technologie reste complexe.Elle est d'une part limitée en terme d'architectures cibles supportées, et d'autre part compliquée dans sa mise en œuvre effective qui requiert de longs et délicats développements.Les travaux menés dans cette thèse s'articulent autour de deux contributions majeures.La première s'attaque au support des architectures cibles de type Very Long Instruction Word (VLIW), en étudiant leurs particularités vis-à-vis de la DBT.Certaines de ces spécificités, tel le parallélisme explicite entre instructions, rendent la traduction vers un processeur hôte scalaire non triviale.La solution que nous proposons apporte des gains en vitesse de simulation d'environ deux ordres de grandeur par rapport à des simulateurs basés sur des techniques d'interprétation.La seconde contribution s'intéresse à la génération automatique de simulateurs basés sur la DBT.À partir d'une description architecturale de la cible et de l'hôte, nous cherchons à produire un simulateur qui soit optimisé pour ce couple.L'optimisation est faite grâce au processus de mise en correspondance des instructions du couple afin de sélectionner la ou les meilleures instructions hôtes pour simuler une instruction cible.Bien qu'expérimental, le générateur réalisé donne des résultats très prometteurs puisqu'il est à même de produire un simulateur pour l'architecture MIPS aux performances comparables à celles d'une implémentation manuelle. / Computing units embedded into modern integrated systems are com-plex, heterogeneous and numerous. Simulation widely used during both software and hardware designof these systems is becoming a real challenge. The simulator performance ismainly driven by the processors instruction set simulation approach, among which Dynamic BinaryTranslation (DBT) is one of the most promising technique. DBT aims at transla-ting on the fly instructions of the simulated processor (the target) into instructions that canbe understood by the computer running the simulation (the host). This technique is fast,but designing a simulator based on it is complex. Indeed, the number of target architecturesis limited, and furthermore, implementing a simulator is a complicated process because oflong and error prone development.This PhD contributes to solve two major issues. The first contribution tackles the problem ofsupporting Very Long Instruction Word (VLIW) architectures as simulation targets,by studying their architecture peculiarities with regards to DBT. Some of these specificities,like explicit instruction parallelism make the translation to scalar hosts nontrivial. Thesolutions we propose bring simulation speed gains of two orders of magnitude compared tointerpreter based simulators. The second contribution addresses the problem of automaticgeneration of DBT based simulators. With both target and host architectural descriptions,we produce a simulator optimised for this pair. This optimisation is done with an instructionsmatching process that finds host instruction candidates to simulate a target instruction.Although being experimental, our generator gives very promising results. It is able toproduce a simulator for the MIPS architecture whose performances are close to a hand writtenimplementation.

Orientador: Edson Borin / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T09:40:30Z (GMT). No. of bitstreams: 1 Gomes_GabrielFerreiraTeles_M.pdf: 1568441 bytes, checksum: b0b5fb8e25907bd153706a27a9b597ea (MD5) Previous issue date: 2014 / Resumo: Tradução dinâmica de binários é uma técnica de emulação comumente utilizada na implementação de máquinas virtuais. Neste contexto, a emulação de saltos indiretos é uma das principais fontes de perda de eficiência, o que atrapalha a aplicabilidade de tradutores dinâmicos de binários. Essa dissertação descreve diversas técnicas que tentam melhorar o desempenho e a eficiência da emulação de saltos indiretos em máquinas virtuais eficientes. O DynamoRIO é uma máquina virtual que se enquadra nessa categoria e que utiliza características de diversas dessas técnicas. Nessa dissertação, nós apresentamos a implementação atual do DynamoRIO, modificamos seu código para incluir duas novas técnicas de emulação de saltos indiretos (Inline Caching e IBTC) e as comparamos com outras técnicas descritas na literatura / Abstract: Dynamic binary translation is an emulation technique commonly employed in the implementation of virtual machines. One of the main sources of overhead that hinder the applicability of dynamic binary translators is that caused by the emulation of indirect branch instructions. This master thesis describes several techniques that try to improve the performance and efficiency of indirect branch emulation in efficient virtual machines. DynamoRIO is one of such machines and it implements features used by several of those techniques. In this master thesis, we present current implementations of DynamoRIO, modify its code to include two new techniques (Inline Caching and IBTC) and compare it with other techniques described in the literature / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

As computer systems become increasingly complex and diverse, so too do the architectures they implement. This leads to an increase in complexity in the tools used to design new hardware and software. One particularly important tool in hardware and software design is the Instruction Set Simulator, which is used to prototype new architectures and hardware features, verify hardware, and test and debug software. Many Architecture Description Languages exist which facilitate the description of new architectural or hardware features, and generate a tools such as simulators. However, these typically suffer from poor performance, are difficult to test effectively, and may be limited in functionality. This thesis considers three objectives when developing Instruction Set Simulators: performance, correctness, and completeness, and presents techniques which contribute to each of these. Performance is obtained by combining Dynamic Binary Translation techniques with a novel analysis of high level architecture descriptions. This makes use of partial evaluation techniques in order to both improve the translation system, and to improve the quality of the translated code, leading a performance improvement of over 2.5x compared to a naïve implementation. This thesis also presents techniques which contribute to the correctness objective. Each possible behaviour of each described instruction is used to guide the generation of a test case. Constraint satisfaction techniques are used to determine the necessary instruction encoding and context for each behaviour to be produced. It is shown that this is a significant improvement over benchmark-driven testing, and this technique has led to the discovery of several bugs and inconsistencies in multiple state of the art instruction set simulators. Finally, several challenges in ‘Full System’ simulation are addressed, contributing to both the performance and completeness objectives. Full System simulation generally carries significant performance costs compared with other simulation strategies. Crucially, instructions which access memory require virtual to physical address translation and can now cause exceptions. Both of these processes must be correctly and efficiently handled by the simulator. This thesis presents novel techniques to address this issue which provide up to a 1.65x speedup over a state of the art solution.

Dans cette thèse nous nous intéressons à l'accélération des accès mémoire dans la traduction binaire dynamique.Pour cela, nous nous basons sur des méthodes dont la principale finalité est de gérer l'espace mémoire de la cible avec le matériel de l'hôte.Deux grandes méthodes pour cela ont été exploré, l'une basé sur la support matériel à la virtualisation, et l'autre sur un module Linux.Dans le cas du support matériel à la virtualisation, nous avons utilisé le simulateur comme un invité spécifique.Celui ci jouant un rôle analogue à celui d'un OS, en plus de son rôle de simulateur, pour la cible.En particulier il se charge de lui créer un espace d'adressage enchevêtré, qui puisse être utiliser directement, sans simulation logicielle de la gestion de la mémoire virtuelle.Dans le cas de la méthode basée sur un module Linux, les mêmes finalités sont poursuivi.Mais le simulateur continue de fonctionner comme un processus normal.En revanche, il possède désormais un module compagnon, avec lequel il peut communiquer au travers d'ioctl.Ce module est chargé de manipuler la gestion de la mémoire virtuelle de l'hôte et ce afin de créer un espace d'adressage enchevêtré pour la cible.Ces méthodes ont été implémenté dans Qemu et Linux et mène à des gains de performances significatifs. / In this thesis we are interested in the acceleration of memory accesses in dynamic binary translation.For this, we base ourselves on methods whose main purpose is to manage the target's address space with the host's hardware.Two main methods for this have been explored, one based on hardware assisted virtualization, and the other on a Linux module.In the case of hardware assisted virtualization, we used the simulator as a specific guest.This one playing a role similar to that of an OS, in addition to its role of simulator, for the target.In particular, it is responsible for creating an enmbedded address space that can be used directly, without software simulation of an MMU.In the case of a method based on a Linux module, the same purpose is pursued.But the simulator continues to operate as a normal process.On the other hand, it now has a companion module, with which it can communicate through ioctl.This module is responsible for manipulating the host's virtual memory management to create an embedded address space for the target.These methods have been implemented in Qemu and Linux and lead to significant performance gains.