1,721,024 research outputs found
Techniques for fine-grained, multi-site computation offloading
No full textMobile devices are increasingly becoming the preferred platform of computation for many users. Unfortunately, its resource limitations in terms of battery life, computation power and storage, restricts the richness of applications that can be run on such devices. Another trend becoming increasingly popular today is that of cloud computing, which allows access to a practically limitless pool of resources on demand. Notably, it is increasingly common that the data users desire to access and manipulate already lies in the cloud. The common approach to solving the problem of limited resources on mobile devices that has gained currency in recent years is computation offloading, where a portion of an applications is run off-site, leveraging the far greater resources of the cloud. Most prior work in this area has focused on a constrained form of the problem: a single mobile device offloading computation to a single server. However, with the increased popularity of cloud computing and storage, it is more common for the data accessed by an application to be distributed among several servers. This work describes approaches for performing fine-grained, multi-site computation offloading. This allows portions of an application to be offloaded in a data-centric manner, even if that data exists at multiple sites. Our approach, based on a novel partitioning algorithm and a program representation, is shown to outperform other partitioning algorithms and allow more efficient, fine-grained offloading than prior approaches
Recursive tree traversal dependence analysis
Get PDFWhile there has been much work done on analyzing and transforming regular programs that operate over linear arrays and dense matrices, comparatively little has been done to try to carry these optimizations over to programs that operate over heap-based data structures using pointers. Previous work has shown that point blocking, a technique similar to loop tiling in regular programs, can help increase the temporal locality of repeated tree traversals. Point blocking, however, has only been shown to work on tree traversals where each traversal is fully independent and would allow parallelization, greatly limiting the types of applications that this transformation could be applied to. The purpose of this study is to develop a new framework for analyzing recursive methods that perform traversals over trees, called tree dependence analysis. This analysis translates dependence analysis techniques for regular programs to the irregular space, identifying the structure of dependences within a recursive method that traverses trees. In this study, a dependence test that exploits the dependence structure of such programs is developed, and is shown to be able to prove the legality of several locality— and parallelism-enhancing transformations, including point blocking. In addition, the analysis is extended with a novel path-dependent, conditional analysis to refine the dependence test and prove the legality of transformations for a wider range of algorithms. These analyses are then used to show that several common algorithms that manipulate trees recursively are amenable to several locality— and parallelism-enhancing transformations. This work shows that classical dependence analysis techniques, which have largely been confined to nested loops over array data structures, can be extended and translated to work for complex, recursive programs that operate over pointer-based data structures
Mitigating Adversarial Interference in Deep Learning-based Wireless Signal Classification Receivers
No full textAutomatic modulation classification (AMC) aims to improve the efficiency of crowded radio spectrums by automatically predicting the modulation constellation of wireless RF signals. Recent work has demonstrated the ability of deep learning (DL) to achieve robust AMC performance using raw in-phase and quadrature (IQ) time samples. Yet, deep learning models are highly susceptible to adversarial interference, which cause intelligent prediction models to misclassify received samples with high confidence. As a result, these attacks present significant security risks and inhibit the widespread deployment of deep learning in wireless communication channels. In this thesis, we propose and evaluate several defensive algorithms to mitigate such interference in a variety of threat models. We begin by considering the white box threat model, in which the adversary has complete knowledge of the classification models at the receiver allowing the transmission of the most potent attack. In this capacity, we present a two-fold defense mechanism, which consists of correcting misclassifications and detecting the presence of an adversary in a wireless channel. The former is designed by training the underlying model to correctly classify inputs with subtle perturbations whereas the latter is designed using manifold learning to identify samples further away from the manifold of the training data as adversarial inputs. Next, we consider the black box threat model, where the adversary uses partial or no system knowledge to craft an adversarial interference signal. Here, we develop a novel receiver architecture and show that adversarial attacks crafted to fool targeted AMC DL architectures are not transferable to different AMC network architectures, with classification performance improvements of up to 75%. Furthermore, we show that time-domain and frequency-domain trained classifiers are resilient to adversarial attacks crafted to induce misclassification in the altering domain. Finally, we propose our wireless receiver’s assorted deep ensemble (ADE) defense, consisting of both time-domain and frequency-domain trained classifiers, which effectively mitigate the effects of imperceptible black box adversarial interference increasing classification performance by up to 70%
SemCache: Semantics-aware caching for efficient GPU offloading
Get PDFGraphical Processing Units (GPUs) offer massive, highly-efficient parallelism, making them an attractive target for computation-intensive applications. However, GPUs have a separate memory space which introduces the complexity of manually handling explicit data movements between GPU and CPU memory spaces. Although GPU kernels/libraries have made it easy to improve application performance by offloading computation to GPUs, unfortunately it is very difficult to manually optimize CPU-GPU communication between multiple kernel invocations to avoid redundant communication when using these kernels with complex applications. In this thesis, we introduce SemCache, a semantics-aware GPU cache that automatically manages CPU-GPU communication in addition to optimizing communication by eliminating redundant transfers using caching. It uses library semantics to determine the appropriate caching granularity for a given offloaded library (e.g., matrices). Our caching technique is efficient; it only tracks matrices instead of tracking every memory access at fine granularity. We applied SemCache to Basic Linear Algebra Subprograms (BLAS) library to provide a GPU drop-in replacement library which requires no program rewriting or annotations. SemCache++ extends SemCache to support offloading to multiple GPUs. SemCache++ is used to build the first multi-GPU drop-in replacement library that (a) uses the virtual memory to automatically manage and optimize multi-GPU communication and (b) requires no program rewriting or annotations. SemCache++ also enables new features like asynchronous transfers, parallel execution and overlapping communication with computation. Experimental results show that our system can dramatically reduce redundant communication for real-world computational science application and deliver significant performance improvements, beating GPU-based implementations like MAGMA, CULA, CUBLAS, StarPU and CUBLASXT
Designing Agora: A Shared Multi-User Programming Environment
No full textShared programming systems typically fall into one of two categories: systems to distribute code between users, and systems to allow shared access to editing or debugging facilities. Version-control systems allow distribution of code and are often more than adequate for large-scale software development occurring over a long period of time, but they can become unwieldy for fast iterative or exploratory development in which multiple users wish to participate. In these situations, shared editors or pair programming tools may suffice, with the caveat that any user of the system can typically modify any of the code at will. Rather than connecting several users to the same editor session, it would be more effective to allow users to maintain separate sessions while quickly sharing selected chunks of code at will.To enable this paradigm, we have designed a new interpreter to allow distributed users to selectively share code and data at run-time. Our solution consists of a bytecode virtual machine back-end with access to a shared environment and a management mechanism to control creation and usage of these resources. By providing access to interpreter sessions over a network connection, we do not tie our interpreter to executing code from any one particular programming language, allowing any conforming front-endcompiler and user interface to be used. This solution allows the development burden of shared programs to be distributed dynamically between users at run-time through the shared environment while still affording control over what and when to share, thereby facilitating more effective incremental or experimental multi-user programming
Data-structure-aware computation offloading
No full textHandheld smart devices are a trend nowadays. Such devices are shipped loaded with high-end processing cores yet a limited battery life. With the emerging of fast data connections, users tend to use these devices as a replacement of desktops and laptops. Since these devices are resources-constrained, there is a limit to how much computation that can be done locally. Computation offloading is the go-to solution for overcoming smart phones resources limitations. A lot of research has been done on computation offloading in terms of program representation and offloading granularity. Most offloading granularities used in previous work are code-driven such as class-based and function-based offloading. Allocation-site-based offloading has been proposed as an approach for data-centric, rather than code-centric offloading. However, although it is a step in the right direction, purely allocation-sites-based offloading suffers from a crucial flaw: due to the prevalence of data structure libraries, different data structures often use the same allocation sites, forcing logically distinct data structures to share offloading decisions and hence to be co-located. We present a novel two-steps program analysis that captures ownership relations between objects to identify which parts of the source code can be carefully cloned to achieve a better data-centric offloading. The second contribution is a code generation and rewriting strategy that transforms the program to deploy data-structures-based offloading on the fairly mature class-based offloading tools. Running a partitioned version of the Java Grande Benchmarks Suite showed a reduction of the number of messages between servers compared to the pure allocation-sites-based offloading and class-based offloading
Techniques for Automatic Fusion of General Tree Traversals
No full textTrees are common data structures that are used in many programs and applications. In its simplest form, a binary tree can be used to store numbers in sorted manners. Kd-trees, render trees and abstract syntax trees are more sophisticated examples of tree structures. Furthermore, in functional programming algebraic data types are essentially tree structures as well.In several tree-based applications, a tree is constructed, and several traversals traverse the tree to perform different computations. Tree fusion is a transformation that targets combining and fusing different traversals that traverse the same tree and perform them together (ideally in one traversal). Traversal fusion has several performance benefits such as reducing the traversing overhead and the memory accesses, enhancing locality, and eliminating intermediate structures.Previous work has been done on fusion and was mostly successful either in specific domains or limited scopes. This work introduces novel techniques for performing fusion in both imperative and functional programming settings with a focus on generality. The new techniques target general traversals; minimizing the burden on programmers and increasing the coverage of the transformation. Furthermore, it exploits fusion opportunities that previous approaches do not, achieving significant speedups for a wider range of programs
Distributed Execution of Recursive Irregular Applications
No full textMassive computing power and applications running on this power, primarily confined to expensive supercomputers a decade ago, have now become mainstream through the availability of clusters with commodity computers and high-speed interconnects running big-data era applications. The challenges associated with programming such systems, for effectively utilizing the computing power, have led to the creation of intuitive abstractions and implementations targeting average users, domain experts, and savvy (parallel) programmers. There is often a trade-off between the ease of programming and performance when using these abstractions. This thesis develops tools to bridge the gap between ease of programming and performance of irregular programs—programs that involve one or more of irregular- data structures, control structures, and communication patterns—on distributed-memory systems.Irregular programs are focused heavily in domains ranging from data mining to bioinformatics to scientific computing. In contrast to regular applications such as stencil codes and dense matrix-matrix multiplications, which have a predictable pattern of data access and control flow, typical irregular applications operate over graphs, trees, and sparse matrices and involve input-dependent data access pattern and control flow. This makes it difficult to apply optimizations such as those targeting locality and parallelism to programs implementing irregular applications. Moreover, irregular programs are often used with large data sets that prohibit single-node execution due to memory limitations on the node. Hence, distributed solutions are necessary in order to process all the data.In this thesis, we introduce SPIRIT, a framework consisting of an abstraction and a space-adaptive runtime system for simplifying the creation of distributed implementations of recursive irregular programs based on spatial acceleration structures. SPIRIT addresses the insufficiency of traditional data-parallel approaches and existing systems in effectively parallelizing computations involving repeated tree traversals. SPIRIT employs locality optimizations applied in a shared-memory context, introduces a novel pipeline-parallel approach to execute distributed traversals, and trades-off performance with memory usage to create a space-adaptive system that achieves a scalable performance, and outperforms implementations done in contemporary distributed graph processing frameworks.We next introduce Treelogy to understand the connection between optimizations and tree-algorithms. Treelogy provides an ontology and a benchmark suite of a broader class of tree algorithms to help answer: (i) is there any existing optimization that is applicable or effective for a new tree algorithm? (ii) can a new optimization developed for a tree algorithm be applied to existing tree algorithms from other domains? We show that a categorization (ontology) based on structural properties of tree-algorithms is useful for both developers of new optimizations and new tree algorithm creators. With the help of a suite of tree traversal kernels spanning the ontology, we show that GPU, shared-, and distributed-memory implementations are scalable and the two-point correlation algorithm with vptree performs better than the standard kdtree implementation.In the final part of the thesis, we explore the possibility of automatically generating efficient distributed-memory implementations of irregular programs. As manually creating distributed-memory implementations is challenging due to the explicit need for managing tasks, parallelism, communication, and load-balancing, we introduce a framework, D2P, to automatically generate efficient distributed implementations of recursive divide-conquer algorithms. D2P automatically generates a distributed implementation of a recursive divide-conquer algorithm from its specification, which is a high-level outline of a recursive formulation. We evaluate D2P with recursive Dynamic programming (DP) algorithms
Composable, Sound Transformations for Nested Recursion and Loops
No full textPrograms that use loops to operate over arrays and matrices are generally known as regular programs. These programs appear in critical applications such as image processing, differential equation solvers, and machine learning. Over the past few decades, extensive research has been done on composing, verifying, and applying scheduling transformations like loop interchange and loop tiling for regular programs. As a result, we have general frameworks such as the polyhedral model to handle transformations for loop-based programs. Similarly, programs that use recursion and loops to manipulate pointer-based data structures are known asirregular programs.Irregular programs also appear in essential applications such as scientific simulations, data mining, and graphics rendering. However, there is no analogous framework for recursive programs. In the last decade, although many scheduling transformations have been developed for irregular programs, they are ad-hoc in various aspects, such as being developed for a specific application and lacking portability. This dissertation examines principled ways to handle scheduling transformations for recursive programs through a unified framework resulting in performance enhancement.Finding principled approaches to optimize irregular programs at compile-time is a longstanding problem. We specifically focus on scheduling transformations that reorder a program’s operations to improve performance by enhancing locality and exploiting parallelism. In the first part of this dissertation, we present PolyRec, a unified general framework that can compose and apply scheduling transformations to nested recursive programs and reason about the correctness of composed transformations. PolyRec is a first-of-its-kind unified general transformation framework for irregular programs consisting of nested recursion and loops. It is built on solid theoretical foundations from the world of automata and transducers and provides a fundamentally novel way to think about recursive programs and scheduling transformations for them. The core idea is designing mechanisms to strike a balance between the expressivity in representing the set of dynamic instances of computations, transformations, and dependences and the decidability of checking the correctness of composed transformations. We use multi-tape automata and transducers to represent the set of dynamic instances of computations and transformations, respectively. These machines are similar yet more expressive than their classical single-tape counterparts. While in general decidable properties of classical machines are undecidable for multi-tape machines, we have proven that those properties are decidable for the class of machines we consider, and we present algorithms to verify these properties. Therefore these machines provide the building blocks to compose and verify scheduling transformations for nested recursion and loops. The crux of the PolyRec framework is its regular string-based representation of dynamic instances that allows to lexicographically order instances identically to their execution order. All the transformations considered in PolyRec require different ordering of these strings representable only with additivechanges to the strings.Loop transformations such as skewing require performing arithmetic on the representation of dynamic instances. In the second part of this dissertation, we explore this space of transformations by introducing skewing to nested recursion. Skewing plays an essential role in producing easily parallelizable loop nests from seemingly difficult ones due to dependences carried across loops. The inclusion of skewing for nested recursion to PolyRec requires significant extensions to representing dynamic instances and transformations that facilitate performing arithmetic using strings. First,we prove that the machines that represent the transformations are still composable. Then we prove that the representation of dependences and the algorithm that checks the correctness of composed transformations hold with minimal changes. Our new extended framework is known as UniRec, since it resembles the unimodular transformations for perfectly nested loop nests, which consider any combination of the primary transformations interchange, reversal, and skewing. UniRec opens possibilities of producing newly composed transformations for nested recursion and loops and verifying their correctness. We claim that UniRec completely subsumes the unimodular framework for loop transformations since nested recursion is more general than loop nests
Characterization of vectorization strategies for recursive algorithms
Get PDFA successful architectural trend in parallelism is the emphasis on data parallelism with SIMD hardware. Since SIMD extensions on commodity processors tend to require relatively little extra hardware, executing a SIMD instruction is essentially free from a power perspective, making vector computation an attractive target for parallelism. SIMD instructions are designed to accelerate the performance of applications such as motion video, real-time physics and graphics. Such applications perform repetitive operations on large arrays of numbers. While the key idea is to parallelize significant portions of data that get operated by several sequential instructions into a single instruction, not every application can be parallelized automatically. Regular applications with dense matrices and arrays are easier to vectorize compared to irregular applications that involve pointer based data structures like trees and graphs. Programmers are burdened with the arduous task of manually tuning such applications for better performance. One such class of applications are recursive programs. While they are not traditional serial instruction sequences, they follow a serialized pattern in their control flow graph and exhibit dependencies. They can be visualized to be directed trees data structures. Vectorizing recursive applications with SIMD hardware cannot be achieved by using the existing intrinsic directly because of the nature of these algorithms. In this dissertation, we argue that, for an important subset of recursive programs which arise in many domains, there exists general techniques to efficiently vectorize the program to operate on SIMD architecture. Recursive algorithms are very popular in graph problems, tree traversal algorithms, gaming applications et al. While multi-core and GPU implementation of such algorithms have been explored, methods to execute them efficiently on vector units like SIMD and AVX have not been explored. We investigate techniques for work generation and efficient vectorization to enable vectorization in recursion. We further implement a generic tree model that allows us to guarantee lower bounds on its utilization efficiency
- …
