Search

Reliable software is vital to society. Much effort has been spent to ensure the robustness and reliability of the software, including unit testing, model checking, static analysis, etc. However, these approaches do not scale well.Greybox fuzzing can test the software with little or no human intervention. A greybox fuzzer utilizes a mutator to automatically generate inputs to test the program. Unlike a random input generator, greybox fuzzer also monitors the program behavior to determine if the generated input triggers a new behavior. Inputs that trigger new behaviors are saved for future mutation. This monitoring is simple yet effective in practice. As a result, much work have focused on different parts of the fuzzer to improve its overall performance and applications. Despite its popularity, some aspects of greybox fuzzing and its applications have not been thoroughly studied. In this thesis, we cover three aspects of greybox fuzzing. First, many fuzzers aim to increase branch coverage. However, high branch coverage is only a sufficient condition for triggering bugs. We revisit some designs of the fuzzing process to increase the likelihood of finding bugs. We first design a tool called Integrity. Integrity sanitizes integer operations within the program, which are harder to spot compared with memory errors. Integrity has discovered eight new integer errors in open-source programs. While randomized fuzzers excel at increasing branch coverage, they struggle with solving predicates set by Integrity. To trigger bugs more effectively, we propose a deterministic fuzzer Valkyrie. Valkyrie uses principled approaches, such as gradient descent and compressed branch coverage, to eliminate the randomness in fuzzers while increasing throughput. Our evaluation shows that Valkyrie can find bugs faster than the state-of-the-art in many cases.Second, generic fuzzing is often less effective than specialized fuzzing. By incorporating expert knowledge into the fuzzer, a specialized fuzzer can reach deeply nested code more quickly. We select the LLVM backend as a test bed to see if a specialized strategy can find bugs in compilers. We develop IRFuzzer with a tailored mutation and monitoring method customized for the LLVM backend. We model LLVM intermediate representation (IR) so that IRFuzzer guarantees to generate valid input for the LLVM backend. IRFuzzer monitors matcher table coverage to track “behavior” in a more fine-grained manner with little overhead. IRFuzzer has found 78 new bugs in upstream LLVM, with 57 of them fixed, five of which have been backport to LLVM 15. These findings demonstrate that specialized fuzzing provides useful, actionable insights to LLVM developers. Finally, fuzzers generate large quantities of inputs as a byproduct, which are often discarded after the fuzzing process is completed. These inputs trigger different behaviors of the program. We notice that these behaviors can be vital for training large language models (LLMs). With this observation, we propose using source code coupled with their test cases for LLM training, where each test case is composed of a fuzzer-generated input and its corresponding output. We first build a dataset on top of an existing one by pairing test cases. Then, we develop methods to fine-tune a trained model and pretrain a new model on this dataset. With this new training scheme, wecontribute a new code understanding model, FuzzPretrain. Our evaluation shows that FuzzPretrain yielded more than 6%/19% mean average precision (mAP) improvements on code search over its baseline trained with only source code or abstract syntax trees (AST), respectively.

Deep learning has achieved remarkable success across various domains, ranging from computer vision to healthcare. General-Purpose Graphics Processing Unit (GPGPU) is one of the major driving forces behind this revolution. GPGPUs offer massive parallel computational power, enabling the training and deployment of large-scale neural networks within practical time and resource constraints. Their programmability also enables adaptability to emerging network architectures. However, entering the post-Moore’s Law era, the scaling of computational power offered by GPGPUs struggles to meet the demands of novel neural networks. On the other hand, existing GPGPUs face under-utilization challenges despite the computation power shortage.This dissertation addresses the computation power shortage by improving the utilization of GPGPUs when running deep learning workloads. It presents a kernel-centric optimization approach with a focus on mapping neural networks to a more efficient set of kernels (parallel functions executed on GPGPUs) that ensures better utilization. This involves optimizations from multiple levels: algorithm level aiming to leverage more hardware-friendly formulations, operator level to harness on-chip high bandwidth on GPGPUs, and kernel implementation level that maximizes the utilization of computational resources.

The once exponential general purpose processors’ (e.g. CPUs) growth of speedup driven bytransistor scaling is fading, which urges both industry and academia to find more energy-efficient and performant architecture organization. Therefore, research on accelerators specialized for applications of interest emerges because of their promising speedup and energysaving while retaining flexibility. To design and implement specialized accelerators, intensivehuman effort is required to study the target applications and determine tradeoffs betweenperformance and cost. In addition, these newly proposed hardware often implies laggingcompilation techniques, which hinders the programming productivity. All these facts significantly limits the programmable accelerator adoption.Moreover, all the prior development effort can hardly be reused in other applicable do-mains, because the current software/hardware co-designed innovations seldom consider modularity for future integration. Therefore, research projects presented in this dissertation aimat significantly reforming the full-stack reconfigurable accelerator design paradigm: Ideally,each software/hardware co-design feature can be comprised in a universal design space for further accelerator composition so that people no longer build accelerators from scratch.Further, an accelerator can be automatically generated based on the given applications ofinterest written in a unified high-level programming interface.To achieve this goal, this dissertation develops the framework, DSAGEN, including anaccelerator design space with rich software/hardware co-design features, a compiler targetsto accelerators with arbitrary design points within this space, and a design automationalgorithm that efficiently searches this space. According to our evaluation, the compiler canrobustly target multiple application suites on hardware with arbitrary feature combinations.The framework-generated accelerators can have comparable perf/mm2 compared with priorhandcrafted domain-specific accelerators.In addition, to demonstrate the wide applicability of our approach, the insights andprinciples learned along with this goal are also applied to applicable research questions: Bydeploying the DSAGEN-generated accelerator as a reconfigurable overlay on FPGA, it savesorders-of-magnitude time on compilation and reconfiguration compared with conventionalhigh-level synthesis, while retaining flexibility. This approach suggests that a deeply spe-cialized programmable overlay accelerator can potentially supplement the existing FPGA’shigh-level programming paradigm. Also, the compilation techniques for spatial architecturesdeveloped in DSAGEN can be applied to compiling an emerging instruction paradigm specialized for tensor operations — a productive and extensible compilation framework, UNIT,is presented for these instructions. The extensibility of this framework allows developers toeasily integrate new instructions by describing the instruction semantics. High-performancecode, that outperforms vendor provided libraries up to 2.2�, for end-to-end inferences canbe generated by tensorized rewriting, accompanied with our automated tuning strategies.

Memory-intensive applications suffer significant performance degradation when their working sets exceed available memory capacity, which can result in swapping with slow disks. Far memory, where memory accesses are directed to other connected nodes, has become more popular in recent years as a solution to expand memory size and avoid memory stranding.Prior far memory systems have taken two approaches: 1) devising a swap system that uses far memory as a backup device and transparently exposes these regions to unmodified applications, and 2) introducing a new programming model/data structure that interfaces with far memory runtime. The former requires no program changes but comes with a significant performance penalty, while the latter requires considerable developer efforts to adopt and tune new APIs despite potential performance gains.Our key insight is that by capturing both statically known and dynamically monitored program behaviors, we can optimize both the program itself and the underlying runtime, resulting in a notable performance boost. Furthermore, we propose automating this process within the compiler to achieve a certain level of transparency. In this thesis, we introduce Mira, a far-memory system that transforms unmodified C/C++ programs to adopt remote memory accesses and optimizes them by tailoring runtime support to their specific behaviors. Our evaluation demonstrates that Mira significantly enhances workload performance, particularly in terms of execution time, surpassing previous swap-based systems and programming models by up to 18×.

This thesis presents the design and implementation of a hardware language, Pyrope. It first describes Pyrope’s distinct language features with their design rationales and compares Pyrope with the mainstream language, SystemVerilog. It then shows the implementation of the Pyrope compilation flow that translates the language specification into low-level intermediate representation in a compiler framework, LiveHD. Several improvements to LiveHD as part of this work are also presented. Finally, the thesis shows the result of compiling an example design written in Pyrope.

Many attacks on modern software begin when the application processes untrusted data. Often attackers exploit a lack of memory safety in the underlying program, which is frequently written in unsafe languages, like C or C++. While memory-safe alternatives, like Rust, are emerging as a viable replacement for these languages, many applications implemented in a memory-safe language will still need to rely on external code that lacks memory safety until safe alternatives exist. Unfortunately, process-level isolation can incur substantial overheads, leading to high risk components often being embedded within the process, thereby exposing the rest of the application to memory corruption by an adversary. Today, new hardware features, like Memory Protection Keys, are being used to create efficient intra-process data isolation schemes. However, adapting existing software to correctly enforce the desired isolation policy can be challenging due to the complex inter-procedural data flows present within modern applications.To address these issues, we propose a general architecture for compartmentalizing memory- safe applications from components written in memory-unsafe languages using efficient hardware enforcement. Our architecture limits memory access to these components in a manner that aligns with the principle of least privilege, only granting them access to their own private data and data directly shared with them from the memory-safe portion of the application.Next, we identify cross-compartment data flow as one of the key challenges to automating intra-process compartmentalization. We demonstrate how type systems can be used to guide refactoring efforts and identify cross-compartment data flows that conflict with the desired isolation policy. Further, we show how a simple, yet practical, dynamic analysis can be used to automate the process of isolating program data without significant effort by programmers. Our extensive evaluation on the Servo web browser demonstrates our system’s practicality, scalability, and efficiency, as it automatically compartmentalizes one of the largest Rust programs available, while only introducing overheads between 1-11.5% on average.

The rapid advancement of Artificial intelligence (AI) is making our everyday life easier with smart assistants, automatic medical analyzer, bank plagiarism checkers and traffic predictions, etc. Deep learning algorithms, especially deep convolutional neuron networks (DCNNs), achieve top performance on AI tasks, but suffers from dense computational requirements, which calls for hardware acceleration. In this thesis we propose several architectures including compilation flow for general DCNN acceleration using FPGA platform.Starting from late 2015 we began to design customized accelerators for popular DCNNs such as VGG and YOLOv2. We reformulate the convolution computation by flattening it to large-scale matrix multiplication between feature maps and convolution kernels, which can be computed as inner product. With this formulation, the accelerators across all layers can be unified to enhance resource sharing, and maximize utilization of computing resources. We also quantized the network into 8bit with negligible accuracy loss to reduce memory footprint and computation resources. Different parallelism optimization strategies are explored for different networks. The VGG16 accelerator achieved 1.15x throughput under 1.5x lower frequency compared with state-of-the art designs. The YOLOv2 accelerator was commercialized and employed for real-time subway X-ray auto-hazard detection.Based on the experience we gained through customized accelerator designing, we designed a RTL compiler as an end-to-end solution to automatically generate RTL design for given CNN network and FPGA platform, which greatly reduced the human effort in developing a specific network accelerator. The compiler applies analytical performance models to optimize parameters for modules based on a handwritten template library, such that the overall throughput is maximized. Several levels of parallelism for convolution are explored, including inter feature-map, intra-kernel-set, input/output channel, etc. We also optimize architectures for block RAM and input buffers to speed up data flow. We tested our compiler on several well-known CNNs including AlexNet and VGGNet for different FPGA platforms. The resulting AlexNet is 113.69 GOPS on Xilinx VCU095 and 177.44 GOPS on VC707, and VGGNet is 226 GOPS on VCU095 under 100MHZ. These are 1.3x, 2.1x and 1.2x better than the best reported FPGA accelerators at that time, respectively.However, network-specific accelerator requires regeneration of logic and physical implementation whenever network is updated. Moreover, it certainly cannot handle cascaded network applications that are widely employed in complex real-world scenarios. Therefore, we propose a domain-specific FPGA overlay processor, named OPU to accelerate a wide range of CNN networks without re-configuration of FPGA for switch or update of CNN networks. We define our domain-specific instruction architecture with optimized granularity to maintain high efficiency while gaining extra progammability. We also built hardware micro-architectures on FPGA to verify ISA efficiency, and a compiler flow for parsing, optimization ans instructuin generation. Experiments show that OPU can achieve an average of 91% run-time MAC efficiency (RME) among various popular networks. Moreover, for VGG and YOLO networks, OPU outperforms automatically compiled network-specific accelerators in the literature. In addition, OPU shows 5.35x better power efficiency compared with Titan Xp. For a case using cascaded CNN networks, OPU is 2.9x faster compared with edge computing GPU Jetson Tx2 with a similar amount of computing resources. Our OPU platform was employed in an automatic curbside parking charging system in real-world. Using OPU as base design, we extend different versions of OPU to handle the newly emerged DCNN architectures. We have Light-OPU for light-weight DCNNs acceleration, where we modified the OPU architecture to fit the memory bounded light-weight operations. Our instruction architecture considers the sharing of major computation engine between LW operations and conventional convolution operations. This improves the run-time resource efficiency and overall power efficiency. Our experiments on seven major LW-CNNs show that Light-OPU achieves 5.5x better latency and 3.0x higher power efficiency on average compared with edge GPU NVIDIA Jetson TX2. Moreover, we also have Uni-OPU for the efficient uniform hardware acceleration of different types of transposed convolutional (TCONV) networks as well as conventional convolution (CONV) networks. Extra stage in compiler would transform the computation of Zero-inserting based TCONV (Zero-TCONV), nearest-neighbor resizing based TCONV (NN-TCONV) and CONV layers into the same pattern. The compiler conducts the following optimizations: (1) Eliminating up to 98.4% of operations in TCONV by making use of the fixed pattern of TCONV upsampling; (2) Decomposing and reformulating TCONV and CONV processes into streaming paralleled vector multiplication with uniform address generation scheme and data flow pattern. Uni-OPU can reach throughput up to 2.35 TOPS for TCONV layer. We evaluate \textit{Uni-OPU} on a benchmark set composed of six TCONV networks from different application fields. Extensive experimental results indicate that Uni-OPU is able to gain 1.45x to 3.68x superior power efficiency compared with state-of-the-art Zero-TCONV accelerators. High acceleration performance is also achieved on NN-TCONV networks, whose acceleration have not been explored before. In summary, we observe 15.04x and 12.43x higher power efficiency on Zero-TCONV and NN-TCONV networks compared with Titan Xp GPU on average. To the best of our knowledge, we are the first in-depth study to completely unify the computation process of both Zero-TCONV, NN-TCONV and CONV layers. In summary, we have been working on FPGA acceleration for deep learning vision algorithms. Several hand-coded customized accelerator as well as an auto-compiler that generates RTL code for customized accelerator have been developed. An initial tool-chain for an FPGA based overlay processor was also finished, which can compile DCNN network configuration file from popular deep learning platforms and map to processor for acceleration.

The hardware industry is currently beginning a trend towards a more productive hardware design flow. Many designers have been noticing for years a lack of efficiency when it comes to the design process. In response, research groups have been proposing tools and languages to improve productivity in this domain. Two such examples are LiveHD and Chisel. LiveHD is a framework that seeks to perform live synthesis and simulation, where live means that results for these tasks are achieved in seconds or minutes rather than hours. Chisel is a new hardware description language that focuses on using software abstractions to improve design reuse. The compilers for both works rely upon intermediate representations to model a design for their compiler. Having LiveHD and Chisel interact is currently impossible since the way in which they model hardware designs is different. This paper proposes an implementation of a translator that would bridge the gap between these two research efforts, allowing designers to reap the benefits of both and thus greatly improve their productivity during the design process.

As an Electronic System Level (ESL) design language, the IEEE SystemC standard is widely used for testing, validation and verification of embedded system models. Discrete Event Simulation (DES) has been used for decades as the default SystemC simulation semantic. However, due to the sequential nature of DES, Parallel DES has recently gained an increasing amount of attention for performing high speed simulations on parallel computing platforms. To further exploit the parallel computation power of modern multi- and many-core platforms, Out-of-order Parallel Discrete Event Simulation (OoO PDES) has been proposed. In OoO PDES, threads comply with a partial order such that different simulation threads may run in different time cycles to increase the parallelism of execution. The Recoding Infrastructure for SystemC (RISC) has been introduced as a tool flow to fully support OoO PDES.To preserve the SystemC semantics under OoO PDES, a compiler based approach statically analyzes the race conditions in the input model. However, there are severe restrictions: the source code for the input design must be available in one file, which does not scale. This disables the use of Intellectual Property (IP) and hierarchical file structures. In this dissertation, we propose a partial-graph based approach to scale the static analysis to support separate files and IP reuse. Specifically, the Partial Segment Graph (PSG) data structure is proposed and is used to abstract the behaviours and communication of modules within a single translation unit. These partial graphs are combined at top level to reconstruct the complete behaviors and communication of the entire model.We also propose new algorithms to support the static analysis for modern SystemC TLM-2.0 standard. SystemC TLM-2.0 is widely used in industrial ESL designs for better interoperability and higher simulation speed. However, it is identified as an obstacle for parallel SystemC simulation due to the disappearance of channels. To solve the problem, we propose a compile time approach to statically analyze potential conflicts among threads in SystemC TLM-2.0 loosely- and approximately-timed models. A new Socket Call Path (SCP) technique is introduced which provides the compiler with socket binding information for precise static analysis. Based on SCP, an algorithm is proposed to analyze entangled variable pairs for automatic and accurate conflict analysis.Besides the works on the compiler side, we focus as well on increasing the simulation speed of OoO PDES. We observe that the granularity of the Segment Graph (SG) data structure used in static analysis has a high impact on OoO PDES. This motivates us to propose a set of coding guidelines for the RISC users to properly refine their SystemC model for a higher simulation speed. Furthermore, in this dissertation, an algorithm is proposed to optimize directly the event delivery strategy in OoO PDES. Event delivery in OoO PDES was very conservative, which often postponed the execution of waiting threads due to unknown future behaviors of the SystemC model, and in turn became a bottleneck of simulation speed. The algorithm we propose takes advantage of the prediction of future thread behaviors, and therefore allows waiting threads to resume execution earlier, resulting in significantly increased simulation speed.To summarize, the contributions of this dissertation include: 1) a scalable RISC tool flow for statically analyzing and protecting 3rd party IPs in models with multiple files, 2) an advanced static analysis approach for modern SystemC TLM-2.0 models, 3) a set of coding guidelines for RISC users to achieve higher simulation speed, and 4) a more efficient event delivery algorithm in OoO PDES scheduler using prediction information.Together, these compiler and simulator advances enable OoO PDES for larger and modern model simulation and thus improve the design of embedded systems significantly, leading to better devices at lower cost in the end.

Legacy binaries need to continue functioning even when no source code has been preserved, to support the workflows of government and industry. The binaries often lack recent improvements in compiler design and software engineering practices, causing them to be slower and less secure than modern binaries. Binary rewriting seeks to patch, optimize, instrument, or harden binaries to bridge this gap, but existing practice is limited by the underlying static analysis. We created a framework, BinRec, to use dynamic analysis to lift binaries to LLVM IR then recompile them, which overcomes the limitations of static analysis.The protection of software against memory corruption exploits has a rich history, which this thesis both systematizes and extends. We present a study of the performance, precision, and security of control-flow integrity (CFI). Data-only attacks can bypass CFI, and so we present a defense against these attacks. The application of these hardening techniques to binaries deserves further study, and we discuss the extent to which security hardening can be applied to recompiled binaries.This dissertation presents building blocks for the securing of legacy binaries using dynamic analysis, which we hope will become a dominant paradigm in the secure software ecosystem of tomorrow.

The demand for scalable, high-performance computing has increased as the size of datasets has grown in recent years. However, the breakdown of Dennard's scaling has led to energy efficiency becoming an important concern in datacenters, and spawned exploration into using power-efficient processors such as GPUs (Graphic Processing Units) and FPGAs (Field-Programmable Gate Arrays) as accelerators in datacenters. In particular, the FPGA's low power consumption and the re-programmability allow datacenters to use FPGAs as highly energy-efficient accelerators for a variety of application. On the other hand, FPGA has poor programmability compared to instructions-based architectures like CPU and GPU. To facilitate the process of implementing and deploying FPGA accelerators, High-Level Synthesis (HLS) that generates functional-equivalent RTL from C-based programming languages attracts more and more attention since past decades. Nowadays, both FPGA vendors have their commercial HLS products -- Xilinx SDx and Intel FPGA SDK for OpenCL. However, modern HLS is still not friendly for software designers who have limited FPGA domain knowledge. Since the hardware architecture inferred from a syntactic C implementation could be ambiguous, current commercial HLS tools usually generate architecture structures according to specific HLS C code patterns. As a result, even though the authors have illustrated that the HLS tool is capable of generating FPGA designs with competitive performance as the one in RTL, designers must manually reconstruct the HLS C kernel with specific code patterns to achieve high performance. This problem becomes one of the main impediments to consolidating the FPGA community on cooperation and developments.In this dissertation, we first present an automated framework that frees human efforts from code reconstruction and design space exploration (DSE). The framework creates a more comprehensive micro-architecture design space from user-written C-based kernel with the Merlin compiler, so the design point should cover the design point with better performance when compared to the HLS-pragma-based design space. To efficiently identify the best design configuration in the tremendous design space, we first propose efficient design space pruning processes that reduce the design space by 24.65x. Accordingly, we develop and evaluate several approaches, including multi-armed bandit hyper heuristic approach, gradient-based approach, and design bottleneck optimization approach. The evaluation result shows that our DSE framework is able to identify the design point that achieves on average (using geometric mean) 93.78% QoR compared to the corresponding manual design.Based on the proposed DSE framework, we further support automated design optimization for high level domain specific languages (DSLs). Since DSLs might not explicitly provide interfaces for users to specify design configurations, automatic DSE becomes even more important when supporting DSLs for FPGAs. Specifically, we adopt Merlin C, an OpenMP-like C-based programming model, as the intermediate representation (IR) and implement DSL-to-Merlin front-end compilers while preserving the semantic and domain-specific information such as parallel patterns, systolic patterns, and scheduling functions. We first implement Spark-to-Merlin front-end compiler that translates Spark applications in Scala to Merlin C for FPGA acceleration. By leveraging parallel patterns as scheduling hints, the generated accelerators are able to achieve 50x speedup on geometric mean for a set of machine learning kernels. In addition, we also demonstrate that our DSE framework can be even more practical for the DSLs with plenty scheduling functions. Specifically, we implement HeteroCL-to-Merlin front-end that takes HeteroCL programming model embedded in Python. Our DSE framework is capable of exploring a subset of HeteroCL scheduling primitives and let users focus on the platform independent loop transformations. With the help from the DSE framework, we achieve 27.62x speedup on geometric mean over a CPU core for a variety of compute-intensive kernels (chapter 3).On the other hand, a main challenge of performing design space exploration for a design with arbitrary functionality is the lack of the assumption to underlying micro-architectures. As we will illustrate in the dissertation, the cost of evaluating the quality of a design point is extremely expensive (15-60 minutes) so only a limited number of design points can be explored. In addition, due to the uncertainty of vendor tool behaviors, the development of performance and resource modeling is also unrealistic. As a result, we propose composable, parallel and pipeline (CPP) architecture template to limit the design space to a certain region that is more practical and has less exceptions (chapter 4). With the CPP architecture, we are able to derive an incremental analytical model, which only requires a few HLS run to be initialized, to facilitate the DSE process.In the last part of this dissertation, we use convolutional neural network (CNN) to demonstrate that the HLS runtime cost can be totally saved with the use of a more domain specific architecture (chapter 5). Specifically, we leverage a systolic array architecture template for CNN accelerator generation. By mapping a CNN model to the pre-defined systolic array template, we can guarantee the model accuracy and DSE efficiency. The experimental result shows that our analytical model for the architecture template achieves 96% accuracy, and the mapped CNN model achieves up to 1.2 Tops throughput on Intel Arria 10 FPGA.

Emerging applications from the edge to the cloud are constantly increasing demand for energy efficient and performant computation. While specialized hardware can meet these power and performance goals, the high non-reoccurring engineering (NRE) costs of designing, testing, and verifying custom hardware severely hinders its supply. Hardware construction languages such as Chisel enable hardware designers to write parameterized hardware libraries which increase design reuse by turning NRE effort into reusable solutions for future specialized chips. This thesis introduces FIRRTL, Chisel’s hardware compiler framework, which enables automatic and custom RTL-transformations including logic optimization and design instrumentation. In addition, this thesis proposes an aspect-oriented-inspired paradigm, Colla-Gen, as a mechanism to improve design collateral reuse (e.g. physical design floorplanning or verification instrumentation), which forms another large portion of chip NRE costs.

Modern processors continue to aggressively scale down the feature size and reduce voltage levels to run faster and be more energy efficient. However, this trend also poses significant reliability concern as it makes transistors more susceptible to soft errors. Soft errors are transient. Although they don't impair the computing systems permanently, these errors can corrupt the output of a program or even crash the entire system. Hardware or software redundant techniques could be used to detect errors during the execution of a program. However, hardware redundancy, e.g. DMR (dual-modular redundancy) and TMR (triple-modular redundancy), leads to significant area overhead and very high energy cost. Software redundancy, e.g. instruction duplication, has lower performance and energy penalty and virtually no hardware cost by sacrificing a small degree of error coverage. Yet commodity processors generally don't require ``five-nines'' reliability as they are not mission-critical. Instead, performance and energy consumption have more priority. This dissertation proposes a novel approach to instruction duplication, which exploits the redundancy within SIMD instructions. The key idea is to pack the original data and its duplicate in the different lanes of the same vector register instead of executing two scalar instructions separately as these registers are underutilized on most applications. The proposed solution is implemented in the LLVM compiler as a stand-alone pass. Evaluation on a host of benchmarks reveal that proposed SIMD-based error detection technique causes much less performance, code size, and energy overheads.This dissertation further extends the proposed approach as a countermeasure to protect cryptographic algorithms. These algorithms are widely adopted in modern processors and embedded systems to protect information. A number of popular cryptographic algorithms in the Libgcrypt library are protected using the SIMD-based instruction duplication technique. A large amount of errors are injected to these algorithms. The results show that almost all injected faults can be detected with reasonable performance and code size cost.

Today's cutting-edge applications, ranging from wearable devices and embedded medical sensors to high-performance data centers, put new demands on computer architectures. Those demands include more computation capability, a tight power budget, low latency, high throughput, and many more. To meet these requirements, specialized architectures with low energy consumption are becoming more prevalent. Many of these architectures trade off programmability features for gains in energy efficiency and performance. Hence, programmability challenges are inevitable as applications continue to evolve and make new demands on computing architectures.I propose key principles for improving programmability intended for application writers as well as compiler developers and language designers. First, I address programmability issues by providing a programming model that hides low-level details but sufficiently exposes essential details for application writers to control. Second, to compile and optimize programs, I apply a new compilation methodology based on synthesis. Unlike a classical compiler's transformation, synthesis obtains a correct and optimal solution by searching for an optimal candidate that is semantically equivalent to a specification program. This search helps compilers generate efficient code without deriving a program via a sequence of transformations, which are challenging for compiler developers to design for new unconventional architectures.In this thesis, I demonstrate the key principles in three projects: Chlorophyll, a language and compiler for low-power spatial architectures; Floem, a programming system for NIC-accelerated data center applications; and GreenThumb, a framework for building a superoptimizer (an assembly program optimizer based on synthesis).

Live Graph (lgraph) is a graph optimized for live synthesis (Live Synthesize Graph orlgraph for short). By live, we mean that small changes in the design should have resultsin few seconds. The goal is that any code change can have its synthesis and simulationsetup ready under 30 seconds with a goal of under 4 seconds in most cases.Notice that this is a different goal from having an incremental synthesis where manyedges are added and removed. The typical graph reconstruction is on the order ofthousands of nodes.lgraph is optimized for synthesis, allowing forward and backward traversals in thenodes (bidirectional graph).Once the graph is built, some optimization can be applied to the input design, includingDead Code Elimination (DCE), Common Sub-expression Elimination (CSE),Copy Propagation, Fluid flop insertion and so forth.

The performance gap between CPUs, and memory memory has diverged significantly since the 1980's making efficiency memory utilization a key concern for any application developer. Modern CPUs will process orders of magnitude more data than their memory architectures can sustain. Multiple levels of caches are used by the major CPU architects to cope with this issue. Frequently used data is stored as close as possible to the core, which allows it to be retrieved in a few cycles. Compared to the thousands of cycles it would take to be retrieved from main memory. However, data locality is important for caches to be effective, and as applications become more and more irregular the CPU's performance drops. This causes many important applications (e.g. sparse matrices, graphs, hash tables) to suffer from poor performance. This thesis explores how custom hardware accelerators using memory masking multithreaded techniques can be used to improve performance. In hardware multithreaded designs thread states are managed directly in hardware, and with enough application parallelism they can fully mask memory latency without storing data in caches. Designs scale well to match the memory architectures bandwidth. The emergence of heterogeneous FPGA platforms has made it easier to build and test the design on real world hardware.This thesis starts with the issue of programmability. Hardware development is notoriously difficult and time consuming. The CHAT tool, a C-to-VHDL compiler, is presented that assists developers by generating custom multithreaded kernels from high level software descriptions. The thesis proceeds by using CHAT to generate a custom Sparse Matrix Vector (SpMV) kernel. Results show how multithreading can provide data independent performance. Compared to the software and GPU performance which drops significantly as the benchmark's irregularity increases. Cache miss rates increase on the CPU, and memory cannot be coalesced as efficiently on the GPUs. Finally we use multithreading to accelerate two common database operations: Hash join, and aggregation. They are the first in-memory implementations on FPGA hardware. The hash join design shows an improvement of 2x over the best multicore software designs available, and does so with 33% less memory bandwidth. Aggregation shows comparable performance when generating hash tables. However, it generates multiple tables that need to be merged, and this step reduces performance on high cardinality datasets.

Motivated by high development costs, production compilers and virtual machines, often support more than one language. This strategy is most effective when the language family is homogeneous. Many languages are very amenable to static program analysis, however, dynamic languages are not. Consequently, a single VM cannot deliver peak performance for both types of languages without adapting its optimization strategy accordingly.Informally, we host a “highly dynamic” language (Python) on the Java Virtual Machine, a VM for “moderately dynamic” languages. While we are not the first to do so, our approach diverges from current practice by representing Python programs as abstract syntax trees, ASTs, rather than bytecode. Not only are ASTs the simplest and most natural programming language implementation, they also lend themselves well to optimizations those are particularly beneficial to highly dynamic languages. Compared to Jython, which compiles Python programs to Java bytecode, our Python prototype is faster and requires less implementation effort.

In academia, many Application Specific Integrated Circuits and System-on-Chip design methodologies are limited by the availability of memories. As process technologies shrink, the size and number of memories on a chip are constantly increasing and memory designs become a more significant part of the overall system performance, efficiency, and cost. Random-Access Memories can be time consuming and tedious to custom design, and there are not many options for automating this process. Process design kits from foundries and vendors do not include memory compilers and commercial solutions require expensive licenses and are often un-modifiable and process specific. This thesis introduces OpenRAM, an open-source memory compiler and characterization methodology. The main objective of the OpenRAM compiler is to promote memory research in academia by providing a flexible and portable platform for generating and verifying memory designs across different technologies. Currently, the compiler generates GDSII layout and Spice netlists for single-port SRAM's using the FreePDK 45nm process design kit, and provides timing/power characterization through Spice simulation. Verification of OpenRAM designs in both 130nm (IBM 8RF) and 180nm (IBM 7SF) technologies are in progress.

Energy consumption is a primary concern of current day computing systems -- from handheld battery operated systems to servers in data centers connected to wall power. Research in academia as well as industry has focused on a variety of techniques for minimizing energy consumption while maintaining a good level of performance. The most effective techniques combine the best of static (or offline) and dynamic (or online/runtime) optimizations to obtain the best solution. Static optimizations can be more complex and can afford to take a global view of the application/computation being executed on the system -- however, such optimizations have to be conservative in nature because they cannot anticipate all the different scenarios that can appear at runtime. Dynamic optimizations have more information aboutthe application/computation for the given input -- however, since such optimizations have to have low overhead, they can afford to have only a local view of the computation/ application and the complexity of the optimization has to be relatively low. An additional direction that needs to be considered is to determine whether dynamic optimizationsshould be implemented in software or hardware. In this thesis, I present a study of three aspects of energy efficient computing that use a combination of static and dynamic optimizations to minimize energy consumption. The first aspect is to consider variability in the execution time of applications during scheduling for dynamic voltage frequency scaling (DVFS) capable systems to minimize energy consumption and yet maintain a desired level of performance. The main idea is to construct a schedule table offline and perform a simple table look-up at runtime. The second aspect is to consider application-level reliability for applications that can tolerate certain error in the outputs. I present the study of a profile-guided offline compilation strategy to identify critical instructions and a monitoring technique in software to handle corner cases at runtime. Finally, the third aspect of energy efficient computing I investigate is flexibility -- customizing the instruction sets of processors to improve energy efficiency. I study the benefits of compiler directedoptimizations for generating custom instructions which are executed within a modified processor pipeline and an architecture mechanism for detecting corner cases and to roll-back to a safe state. Additionally, I investigate the benefits of customizing the instruction set dynamically in hardware.

In recent years, scientific exploration has become more reliant upon computers. Certain scientific frontiers, such as the study of fluid dynamics, are difficult to study empirically, as measurement devices interfere with what they are measuring. By using computers to simulate known low-level physical interactions, scientists can reproduce higher-level phenomena than they can through physical experiments, and at a much lower cost. With the growth of high-performance computing, computer simulations are able to generate enormous amounts of data.Analyzing large-scale scientific data is expensive both in terms of computational power and time, and in terms of programming effort. For some fields, such as Computational Fluid Dynamics (CFD), scientists are still searching for mathematical models to explain observations. Such models are part of the scientific inquiry and so are continually under development. As a consequence, data analysis in these fields is largely ad hoc. Many different queries are asked of the data, queries which are not known ahead of time. Current libraries do a poor job optimizing the execution of such ad hoc queries.In this thesis we introduce Saaz, a C++ library for analyzing turbulent flow. While Saaz makes analysis codes easier to write, maintain, and share, it significantly harms performance. Compared to plain C++ (C++ with no user-defined abstractions), Saaz code can perform as poorly as 97 times slower. To address these issues we present Tettnang, a source-to-source translator which uses semantic knowledge of the Saaz library to track the data schemas being used. Saaz library calls are then re-written at the call-site to remove the abstraction overheads of the library. After being optimized by Tettnang, ad hoc queries written in Saaz perform comparably to the plain C++ implementation. Of the queries we tested, the slowest was 18% slower than the plain C++ implementation, while the fastest was 16% faster.Our success with Tettnang demonstrates the power and effectiveness of custom translation in creating an Embedded Domain-Specific Language (EDSL) from an application library. The EDSL technique allows powerful transformations that are not available through existing techniques such as Expression Templates, or existing library annotation systems such as Broadway.

As parallel systems become ubiquitous, exploiting parallelism becomes crucial for improving application performance. However, the complexities of developing parallel software are major challenges. Shared memory parallel programming models, such as OpenMP and Thread Building Blocks (TBBs), offer a single view of the memory thereby making parallel programming easier. However, theysupport limited forms of parallelism. Distributed memory programming models,such as the Message Passing Interface (MPI), support more parallelism types; however, their low level interfaces require great deal of programming effort.This dissertation presents the SpiceC system that simplifies the task of parallel programming while supporting different forms of parallelism and parallel computing platforms. SpiceC provides easy to use directives to express different forms of parallelism, including DOALL, DOACROSS, and pipelining parallelism. SpiceC is based upon an intuitive computation model in which each thread performs its computation in isolation from other threads using its private space and communicates with other threads via the shared space. Since, all data transfers between shared and private spaces are explicit, SpiceC naturally supports both shared and distributed memory platforms with ease. SpiceC is designed to handle the complexities of real world applications.The effectiveness of SpiceC is demonstrated both in terms of delivered performance and the ease of parallelization for applications with the following characteristics.Applications that cannot be statically parallelized due to presence of dependences, often contain large amounts of input dependent and dynamic data level parallelism. SpiceC supports speculative parallelizationfor exploiting dynamic parallelism with minimal programming effort. Applications that operate on large data sets often make extensive use of pointer-based dynamic data structures. SpiceC provides support for partitioning dynamic data structures across threads and then distributing the computation among the threads in a partition sensitive fashion. Finally, due to large input sizes, many applications repeatedly performI/O operations that are interspersed with the computation. While traditionalapproach is to execute loops contain I/O operations serially, SpiceC introduces support for parallelizing computations in the presence of I/O operations. Finally, this dissertation demonstrates that SpiceC can handle the challengesposed by the memory architectures of modern parallel computing platforms.The memory architecture impacts the manner in which data transfers betweenprivate and shared spaces are implemented. SpiceC does not place thethe burden of data transfers on the programmer. Therefore portability of SpiceCto different platforms is achieved by simply modifying the handling of data transfers by the SpiceC compiler and runtime. First, it is shown how SpiceC can be targeted to shared memory architectures both with and without hardware support for cache coherence. Next it is shown how accelerators such as GPUs present in heterogeneous systems are exploited by SpiceC. Finally, the ability of SpiceC to exploit the scalability of a distributed-memory system, consisting of a cluster of multicore machines, is demonstrated.

With the advent of multicore processors, extracting thread level parallelism from a sequential program has become crucial for improving performance. However, many sequential programs cannot be easily parallelized due to the presence of dependences. To solve this problem this dissertation presents a thread-based execution model, called Copy-or-Discard (CorD), that supports speculative parallelization. In CorD, the state of speculative threads is maintained separately from the non-speculative computation state. If speculation is successful, the results of the speculative computation are committed by copying them into the non-speculative state. If a misspeculation is detected, no costly recovery mechanisms are needed as the speculative state can be simply discarded.To illustrate the applicability of CorD, this dissertation first shows how to apply it to streaming applications. Optimizations are proposed to reduce data copying overhead. A lightweight scheme based on version comparison is also presented to detect misspeculations. It is observed that when misspeculation rate becomes high, the benefits of parallelism are usually nullified. To address this problem two techniques, Multiple Speculations and Incremental Recovery, are proposed. The first technique creates multiple versions of speculatively-executed code using different value predictions. If any one of these versions is found to be correct, the speculation is successful. The second technique focuses on reducing misspeculation cost. Instead of discarding all results, it allows saving and reuse of the results that are not affected by the variables that cause the misspeculation. Finally, this dissertation shows the applicability of CorD in the presence of dynamic data structures. Such data structures pose many new challenges. The copying of data structures from non-speculative to speculative state is expensive due to the large sizes of data structures. The copying of updated data structures from speculative state to non-speculative state are complex due to the changes in the shape of dynamic data structures. In addition, translating pointers internal to dynamic data structures between their non-speculative and speculative memory addresses has to be addressed. This dissertation proposes an augmented design for the representation of dynamic data structures such that all of the above operations are performed efficiently.

This unit is designed to assist the technical GIS educator in identifying the computer skills required for GIS tasks. Basic computer literacy skills are presented as a foundation for technical GIS computing skills. The latter are organized into several categories (e.g. 'Systems', 'Programming', 'Databases'), with lists of skills at different levels of achievement (Awareness, Competency, Mastery).