With the advent of energy harvesters, supporting fast and efficient computation on energy harvesting devices has become a key challenge in the field of energy harvesting on ubiquitous devices. Computation on energy harvesting devices is equivalent to spreading the execution time of a lasting application over short, frequent cycles of power. However, we must ensure that results obtained from intermittently executing an application do produce results that are congruent to those produced by executing the application on a device with a continuous source of power. The current state-of-the-art systems that enable intermittent computation on energy harvesters make use of novel compiler analysis techniques as well as on-board hardware on devices to measure the energy remaining for useful computation. However, currently available programming models, which mostly target devices with FRAM as the NVM, would cause failure on devices that employ the Flash as primary NVM, thereby resulting in a non-universal solution that is restricted by the choice of NVM. This is primarily the result of the Flash's limited read/write endurance. This research aims to contribute to the world of energy harvesting devices by providing solutions that would enable intermittent computation regardless of the choice of NVM on a device by utilizing only the SRAM to save state and perform computation. Utilizing the SRAM further reduces run-time overhead as SRAM reads/writes are less costlier than NVM reads/writes. Our proposed solutions rely on programmer-guidance and compiler analysis to correct and efficient intermittent computation. We then extend our system to provide a complete compiler-based solution without programmer intervention. Our system is able to run applications that would otherwise render any device with Flash as NVM useless in a matter of hours. / Master of Science / As batteries continue to take up space and make small-scale sensors hefty, battery-less devices have grown increasingly popular for non-resource intensive computations. From tracking air pressure in vehicle tires to monitoring room temperature, battery-less devices have countless applications in various walks of life. These devices function by periodically harvesting energy from the environment and its surroundings to power short bursts of computation. When device energy levels reach a lower-bound threshold these devices must power off to scavenge useful energy from the environment to further perform short bursts of computation. Usually, energy harvesting devices draw power from solar, thermal or RF energy. This vastly depends on the build of the device, also known as a microprocessor (a processing unit built to perform small-scale computations). Due to these devices constantly powering on and off, performing continuous computation on such devices is rather more difficult when compared to systems with a continuous source of power. Since applications can require more time to complete than one power cycle of such devices, by default, applications running on these devices will restart execution from the beginning at the start of every power cycle. Therefore, it is necessary for such devices to have mechanisms to remember where the were before the device lost power. The past decade has seen many solutions proposed to aid an application in restarting execution rather than recomputing everything from the beginning. Solutions utilize different categories of devices with different storage technologies as well different software and hardware utilities available to programmers in this domain. In this research, we propose two different low-overhead, long-life computation models to support intermittent computation on a subset of energy harvesting devices which use Flash-based memory to store persistent data. Our approaches are heavily dependent on programmer guidance and different program analysis techniques to sustain computation across power cycles.

In recent years there has been a proliferation of parallel and heterogeneous architectures. As chip designers have hit fundamental limits in traditional processor scaling, they have begun rethinking processor architecture from the ground up. In addition to creating new classes of processors, chip designers have revisited CPU microarchitecture in order to target different computing contexts. CPUs have been optimized for low-power smartphones and extended for high-performance computing in order to achieve better performance energy efficiency for heavy computational tasks. Although heterogeneity adds significant complexity to both hardware and software, recent works have shown tremendous power and performance benefits obtainable through specialization. It is clear that emerging systems will be increasingly heterogeneous. Many of these emerging systems couple together cores of different instruction set architectures (ISA), due to both market forces and the potential performance and power benefits in optimizing application execution. However, differently from symmetric multiprocessors or even asymmetric single-ISA multiprocessors, natively compiled applications cannot freely migrate between heterogeneous-ISA processors. This is due to the fact that applications are compiled to an instruction set architecture-specific format which is incompatible on other instruction set architectures. This creates serious limitations, as execution migration is a fundamental mechanism used by schedulers to reach performance or fairness goals, allows applications to migrate between heterogeneous-ISA CPUs in order to accelerate parallel applications or even leverage ISA-heterogeneity for security benefits. This dissertation describes system software for automatically migrating natively compiled applications across heterogeneous-ISA processors. This dissertation describes the implementation and evaluation of a complete software stack on commodity scale heterogeneous-ISA CPUs, emulating datacenters with heterogeneous-ISA systems or future systems that tightly integrate heterogeneous-ISA CPUs via point-to-point interconnect. This dissertation describes a compiler which builds applications for heterogeneous-ISA execution migration. The compiler generates machine code for every architecture in the system and lays out the application's code and data in a common format. In addition, the compiler generates metadata used by a state transformation runtime to dynamically transform thread execution state between ISA-specific formats, allowing application threads to migrate between different ISAs. The compiler and runtime is evaluated in conjunction with a replicated-kernel operating system, which provides thread migration and distributed shared virtual memory across heterogeneous-ISA processors. This redesigned software stack is evaluated on a setup containing and ARM and an x86 processor interconnected via point-to-point interconnect over PCIe. This dissertation shows that sub-millisecond state transformation is achievable. Additionally, it shows that for a datacenter-like workload using benchmarks from the NAS Parallel Benchmark suite, the system can trade some performance for up to a 66% reduction in energy and up to an 11% reduction in energy-delay product. This dissertation then describes an exploration into using hardware transactional memory (HTM) to maximize scheduling flexibility. Because applications can only migrate between ISAs at program locations with specific properties, there may be a significant delay between when the scheduler wishes to migrate an application and when the application can respond to the migration request. In order to reduce this migration response time, this dissertation describes compiler instrumentation which uses HTM to allow the scheduler to force applications to roll back to the most recently encountered program location suitable for migration. This is evaluated both in terms of overhead and responsiveness to migration requests. In addition to showing the viability of the infrastructure for optimizing workload placement in a heterogeneous-ISA datacenter, this dissertation also demonstrates utilizing the infrastructure to accelerate multithreaded applications. This dissertation describes a new OpenMP runtime named libopenpop that is optimized for executing applications in heterogeneous- ISA systems with distributed shared virtual memory. The runtime utilizes synchronization primitives that enable scale-out execution across rack-scale systems and new work distribution mechanisms that predict the best partitioning of parallel work across CPUs with diverse architectural characteristics. libopenpop demonstrates sizable improvements over a na¨ıve OpenMP implementation – a 38x improvement in multi-server barrier latency, a 5.4x improvement in multi-server data reductions and a geometric mean speedup of 4.04x for scalable applications in an 8-node x86-64 cluster. For a heterogeneous system composed of a highly-clocked x86 server and a highly-parallel ARM server, libopenpop delivers up to a 4.7x speedup and a geometric mean speedup of 41% across benchmarks from several benchmark suites versus the best single-node homogeneous execution. Finally, this dissertation describes leveraging the compiler and state transformation runtime to provide enhanced security for applications. Because the compiler provides detailed information about the stack layout of applications, it can be leveraged to defend against exploits such as stack smashing attacks and return-oriented programming attacks. This dissertation describes Chameleon, a runtime which uses the compiler and state transformation infrastructure to continuously re-randomize the stack layout and code of vulnerable applications to thwart attackers. Chameleon attaches to applications using existing operating system interfaces and periodically switches the application to new randomized stack layouts and code by rewriting the stack. Chameleon enhances security with little overhead – it disrupts a geometric mean 76.32% of code gadgets in benchmark binaries, randomizes stack element locations with geometric mean 3 potential randomized locations, and has 1.1% overhead when re-randomizing every 50 milliseconds, making it extremely difficult for attackers to exploit target applications. / Doctor of Philosophy / Computer processors have experienced unprecedented performance improvements over the past 50 years. However, due to physical limitations of how processors execute, in recent years this performance growth has started to slow. In order to continue scaling performance, chip designers have begun diversifying processor designs to meet different performance and power consumption targets. Processors specialized for different contexts use various instruction set architectures (ISAs), the operations made available for use by the hardware. Programs built for one instruction set architecture are not compatible with others, requiring developers to build complex applications to manually bridge the gap. This leads to brittle applications and prevents the system software managing the processors from adapting workloads to match processor characteristics. This dissertation presents the Popcorn Linux system software which provides transparent support for running applications across computers composed of processors of multiple ISAs. Popcorn Linux provides the ability to migrate applications between these processors without requiring developers to add any application instrumentation – the system software manages all the details of building and migrating applications. An evaluation of Popcorn Linux shows that transparently migrating applications between diverse processors provides power and performance benefits in a variety of scenarios. Additionally, this dissertation describes leveraging the Popcorn Linux software infrastructure to harden applications against attackers seeking to hijack applications for malicious purposes.

The primary goal of the register allocation phase in a compiler is to minimize register spills to memory. Spills, in the form of store and load instructions, affect execution time as the processor must wait for the slower memory system to respond. Deciding which registers to spill can benefit from execution frequency information yet when this information is available it is not fully utilized by modern register allocators. We present a register allocator that fully exploits profiling information to mini- mize the runtime costs of spill instructions. We use the Furthest Next Use heuristic, informed by branch probability information to decide which virtual register to spill when required. We extend this heuristic, which under the right conditions can lead to the minimum number of spills, to the control flow graph by computing Expected Distance to next use. The furthest next use heuristic, when applied to the control flow graph, only par- tially determines the best placement of spill instructions. We present an algorithm for optimizing spill instruction placement in the graph that uses block frequency infor- mation to minimize execution costs. Our algorithm quickly finds the best placements for spill instructions using a novel method for solving placement problems. We evaluate our allocator using both static and dynamic profiling information for the SPEC CINT2000 benchmark and compare it to the LLVM allocator. Targeting the ARMv7 architecture, we find average reductions in numbers of store and load instructions of 36% and 50%, respectively, using static profiling and 52% and 52% using dynamic profiling. We have also seen an overall improvement in benchmark speed. / Graduate

The efficient execution of sequential legacy applications on modern, parallel computer architectures is one of today’s most pressing problems. Automatic parallelization has been investigated as a potential solution for several decades but its success generally remains restricted to small niches of regular, array-based applications. This thesis investigates two techniques that have the potential to overcome these limitations. Beginning at the lowest level of abstraction, the binary executable, it presents a study of the limits of Dynamic Binary Parallelization (Dbp), a recently proposed technique that takes advantage of an underlying multicore host to transparently parallelize a sequential binary executable. While still in its infancy, Dbp has received broad interest within the research community. This thesis seeks to gain an understanding of the factors contributing to the limits of Dbp and the costs and overheads of its implementation. An extensive evaluation using a parameterizable Dbp system targeting a Cmp with light-weight architectural Tls support is presented. The results show that there is room for a significant reduction of up to 54% in the number of instructions on the critical paths of legacy Spec Cpu2006 benchmarks, but that it is much harder to translate these savings into actual performance improvements, with a realistic hardware-supported implementation achieving a speedup of 1.09 on average. While automatically parallelizing compilers have traditionally focused on data parallelism, additional parallelism exists in a plethora of other shapes such as task farms, divide & conquer, map/reduce and many more. These algorithmic skeletons, i.e. high-level abstractions for commonly used patterns of parallel computation, differ substantially from data parallel loops. Unfortunately, algorithmic skeletons are largely informal programming abstractions and are lacking a formal characterization in terms of established compiler concepts. This thesis develops compiler-friendly characterizations of popular algorithmic skeletons using a novel notion of commutativity based on liveness. A hybrid static/dynamic analysis framework for the context-sensitive detection of skeletons in legacy code that overcomes limitations of static analysis by complementing it with profiling information is described. A proof-of-concept implementation of this framework in the Llvm compiler infrastructure is evaluated against Spec Cpu2006 benchmarks for the detection of a typical skeleton. The results illustrate that skeletons are often context-sensitive in nature. Like the two approaches presented in this thesis, many dynamic parallelization techniques exploit the fact that some statically detected data and control flow dependences do not manifest themselves in every possible program execution (may-dependences) but occur only infrequently, e.g. for some corner cases, or not at all for any legal program input. While the effectiveness of dynamic parallelization techniques critically depends on the absence of such dependences, not much is known about their nature. This thesis presents an empirical analysis and characterization of the variability of both data dependences and control flow across program runs. The cBench benchmark suite is run with 100 randomly chosen input data sets to generate whole-program control and data flow graphs (Cdfgs) for each run, which are then compared to obtain a measure of the variance in the observed control and data flow. The results show that, on average, the cumulative profile information gathered with at least 55, and up to 100, different input data sets is needed to achieve full coverage of the data flow observed across all runs. For control flow, the figure stands at 46 and 100 data sets, respectively. This suggests that profile-guided parallelization needs to be applied with utmost care, as misclassification of sequential loops as parallel was observed even when up to 94 input data sets are used.

Reconfigurable computing is a method of development that provides a developer with the ability to reprogram a hardware device. In the specific case of FPGAs this allows for rapid and cost effective implementation of hardware devices when compared to standard a ASIC design, coupled with an increase in performance when compared to software based solutions. With the advent of development tools such as Celoxica's DK package and Xilinx's Forge package, that support languages traditionally associated with software development, a change in the skill sets required to develop FPGA solutions from hardware designers to software programmers is possible and perhaps desirable to increase the adoption of FPGA technologies. To support developers with these skill sets tools should closely mirror current software development tools in terms of language, syntax and methodology, while at the same time both transparently and automatically take advantage of as much of the increased performance that reconfigurable architectures can provide over traditional software architectures by utilizing the parallelism and the ability to create arbitrary depth pipelines which is not present in traditional microprocessor designs. A common feature of many programming languages that is not supported by many higher level design tools is recursion. Recursion is a powerful method used to elegantly describe many algorithms. Recursion is typically implemented by using a stack to store arguments, context and a return address for function calls. This however limits the controlling hardware to running only a single function at any moment which eliminates an algorithm's ability to take advantage of the parallelism available between successive iterations of a recursive function. This squanders the high amount of parallelism provided by the resources on the FPGA thus reducing the performance of the recursive algorithm. This thesis presents a method to address the lack of support for recursion in design tools that exploits the parallelism available between recursive calls. It does this by unrolling the recursion into a pipeline, in a similar manner to the pipeline obtained from loop unrolling, and then streaming the data through the resulting pipeline. However essential differences between loops and recursive functions such as multiple recursive calls in a function, and hence multiple unrollings, and post-recursive statements add further complexity to the issue of unrolling as the pipeline may take a non-linear shape and contain heterogeneous stages. Unrolling the recursive function on the FPGA increases the parallelism available, however the depth of the pipline and therefore the amount of parallelism available, is limited by the finite resources on the FPGA. To make efficient use of the resources on the FPGA the system must be able to unroll the function in a way to best suit the input but also must ensure that the function is not unrolled past its maximum recursive depth. A trivial solution such as unrolling on-demand introduces a latency into the system when a further instance of the function is unrolled that reduces overall performance. To reduce this penalty it is desirable for the system to be able to predict the behaviour of the recursive function based on the input data and unroll the function to a suitable length prior to it being required. Accurate prediction is possible in cases where the condition for recursion is a simple function on the arguments, however in cases where the condition for recursion is based on complex functions, such as the entire recursive function, accurate prediction is not possible. In situations such as this a heuristic is used which provides a close approximation to the correct depth of recursion at any given time. This prediction allows the system to reduce the performance penalty from real time unrolling without over utilization of the the FPGA resources. Results obtained demonstrate the increase in performance for various recursive functions obtained from the increased parallelism, when compared to a stack based implementation on the same device. In certain instances due to constraints on hardware availability results were gained from device simulation using a simulator developed for this purpose. Details of this simulator are presented in this thesis.

Program optimizations analyze and transform the programs such that better performance results can be achieved. Classical optimizations mainly use the static properties of the programs to analyze program code and make sure that the optimizations work for every possible combination of the program and the input data. This approach is conservative in those cases when the programs show the same runtime behaviors for most of their execution time. On the other hand, profile-guided optimizations use runtime profiling information to discover the aforementioned common behaviors of the programs and explore more optimization opportunities, which are missed in the classical, non-profile-guided optimizations. Redundancy elimination is one of the most powerful optimizations in compilers. In this thesis, a new partial redundancy elimination (PRE) algorithm and a partial dead code elimination algorithm (PDE) are proposed for a profile-guided redundancy elimination framework. During the design and implementation of the algorithms, we address three critical issues: optimality, feasibility and profitability. First, we prove that both our speculative PRE algorithm and our region-based PDE algorithm are optimal for given edge profiling information. The total number of dynamic occurrences of redundant expressions or dead codes cannot be further eliminated by any other code motion. Moreover, our speculative PRE algorithm is lifetime optimal, which means that the lifetimes of new introduced temporary variables are minimized. Second, we show that both algorithms are practical and can be efficiently implemented in production compilers. For SPEC CPU2000 benchmarks, the average compilation overhead for our PRE algorithm is 3%, and the average overhead for our PDE algorithm is less than 2%. Moreover, edge profiling rather than expensive path profiling is sufficient to guarantee the optimality of the algorithms. Finally, we demonstrate that the proposed profile-guided redundancy elimination techniques can provide speedups on real machines by conducting a thorough performance evaluation. To the best of our knowledge, this is the first performance evaluation of the profile-guided redundancy elimination techniques on real machines.

Thesis (Ph. D.)--University of Texas at Austin, 2003. / Vita. Includes bibliographical references. Available also from UMI Company.

Not available / text

Not available / text

Τα σύγχρονα υπολογιστικά περιβάλλοντα χαρακτηρίζονται από έντονη χρήση διερμηνευτών (scripting languages). Μεταξύ άλλων, διερμηνευτές χρησιμοποιούνται για τη διαχείριση συστήματων (bash, powershell, msi), την αυτοματοποίηση διαδικασιών σε εφαρμογές (Microsoft Office, Alias Maya, Sonar, AutoCad), τη δημιουργία ψηφιακών παιχνιδιών (UnrealScript, LUA) αλλά και για την ανάπτυξη εφαρμογών για τον Παγκόσμιο Ιστό. Ειδικά για τη περίπτωση του Διαδικτύου, φαίνεται ότι η εξέλιξη του Παγκόσμιου Ιστού είναι συνυφασμένη με την παράλληλη εξέλιξη των διερμηνευτών: νέες γλώσσες δημιουργούνται ώστε να υποστηρίξουν νέες τεχνολογίες. Σήμερα, πολλές ετερογενείς τεχνολογίες αλληλεπιδρούν ώστε εξυπηρετητής και φυλλομετρητής να παράγουν και να παρουσιάσουν διαδραστικό περιεχόμενο στο χρήστη. Από τη μεριά του εξυπηρετητή, χρησιμοποιούνται γλώσσες όπως οι Php, Jsp και Asp.Net. Το περιεχόμενο που παράγεται παρουσιάζεται στο χρήστη με τη χρήση γλωσσών όπως οι html, Javascript και Actionscript. Οι διερμηνευτές γίνονται όλο και πιο διαδεδομένοι, καθώς προσφέρουν ευελιξία στην ανάπτυξη του κώδικα, ανεξαρτησία από την υπολογιστική αρχιτεκτονική και μειωμένους χρόνους ανάπτυξης, αφού δεν απαιτείται μεταγλώττιση ενώ το συντακτικό είναι απλο¬ποιημένο. Για τη βελτίωση της απόδοσης, οι σύγχρονοι διερμηνευτές χρησιμοποιούν Just-in-time compilation τεχνικές: ουσιαστικά μετατρέπουν το πηγαίο κώδικα σε ενδιάμεσο κώδικα, άμεσα εκτελέσιμο από μια μηχανή εκτέλεσης (ιδεατή μηχανή). Αυτό δυσχεραίνει περαιτέρω το διαχωρισμό μεταξύ διερμηνευτή και μεταγλωττιστή. Λόγω των παραπάνω χαρακτηριστικών και κυρίως λόγω της ανεξαρτησίας τους από την αρχιτεκτονική, οι διερμηνευτές αποτελούν τη βάση για τη συντριπτική πλειοψηφία των Εφαρμογών Ιστού. Εντούτοις, καθώς η πολυπλοκότητα των διαδικτυακών εφαρμογών αυξάνεται, η χρήση των υπαρχόντων τεχνολογιών επιβραδύνει σημαντικά την ανάπτυξη: Για μια απλή δυναμική ιστοσελίδα απαιτείται η συγγραφή κώδικα σε τουλάχιστον τρεις γλώσσες: Κάθε στοιχείο της εφαρμογής (βάση δεδομένων, εξυπηρετητής, πελάτης) προγραμματίζεται σε διαφορετικό γλωσσικό περιβάλλον. Ο προγραμματιστής καλείται να διαχειριστεί την επικοινωνία και αλληλεπίδραση των ετερογενών στοιχείων αυτών και να επιλύσει τυχόν ασυμβατότητες. Ένα μεγάλο μέρος του χρόνου ανάπτυξης μιας εφαρμογής καταναλώνεται στη διαχείριση αυτού του ετερογενούς συστήματος. Με την άφιξη νέων τεχνολογιών, όπως για παράδειγμα οι Ajax, Silverlight, JavaFX, η διαχείριση των εγγενών προβλημάτων του συστήματος αυτού δυσχεραίνεται ακόμη περισσότερο. Στα πλαίσια της εργασίας αυτής διερευνώνται οι κυριότερες σύγχρονες τεχνολογίες διερμηνευτών για ανάπτυξη εφαρμογών, με έμφαση στις τεχνολογίες Ιστού. Κάθε γλώσσα αναλύεται ξεχωριστά και σχολιάζονται οι ιδιαιτερότητες και τα ειδικά χαρακτηριστικά της. Παράλληλα εντοπίζονται τα εγγενή προβλήματα ασυμβατότητας που συναντώνται στο υπάρχον μοντέλο ανάπτυξης και παρουσιάζεται ένα εναλλακτικό, ενοποιημένο μοντέλο ανάπτυξης διαδικτυακών εφαρμογών, το οποίο ομαδοποιεί και απλοποιεί τις προγραμματιστικές διαδικασίες των συστημάτων πελάτη και εξυπηρετητή. / Scripting languages find many applications in modern computing environments. Scripts are used in various scenarios, including system administration (bash, powershell, msi), job automation (Microsoft Office, Alias Maya, Sonar, AutoCad), logic programming in computer entertainment and of course in Internet Applications. Internet technologies are the primary example application of scripts (interpreters in general): a connection between scripts and the development of the World Wide Web can be observed: new scripting systems arise to support newly developed technologies. In modern internet applications, different technologies co-exist and interact so that the server and the client can present interactive content to the end user. On the server side, technologies like Php, Jsp and As[.Net are used. The resulting content is presented on the client side with technologies such as html/xml, Javascript, Flex and Actionscript. Scripting Languages (interpreters) are becoming increasingly popular, as they offer versatility, platform-independence and reduced development times, since they feature a simplified syntax and they do not require complex compilation procedures. To increase performance, modern Scripting systems feature Just-In-Time compilation techniques, effectively creating a compiled version of their input source code. This version of the code can be easily executed by the system’s Virtual Machine (Execution Engine). Such techniques blur the borders between Compilers and Interpreters. The features detailed above make interpreters the ideal solution for web application development, mainly because they are inherently cross-platform. Most of the available web-technologies expose an interpreted language system. However, as the complexity in modern web-applications and related technologies increases, current scripting systems are becoming a bottleneck in the development process: To develop a proper dynamic web page, the programmer will be required to use at least three different languages: A language for accessing the data base (sql), a language to program the server side of the application (Php, Jsp, Asp) and a set of languages to present content to the end user (javascript). It is up to the programmer to orchestrate the various scripts and manage any incompatibilities arising, when using those independent systems. This hampers the development process, as extra effort is taken to manage the programming environment rather than actually develop the program. With new technologies, like Silverlight, Ajax and Flex arising, managing inherent incompatibilities becomes even more difficult. To tackle the increased development complexity, a new web application development paradigm is explored and the features of the corresponding language are detailed, as is a simple implementation scheme. A study of available mainstream scripting languages, with a focus in Web development, is also presented. Each language is presented with a description of its key features and syntax and a comparison with similar development systems.