228 research outputs found
Linear Loop Transformations in Optimizing Compilers for Parallel Machines
No full textWe present the linear loop transformation framework which is the formal basis for state of the art optimization techniques in restructuring compilers for parallel machines. The framework unifies most existing transformations and provides a systematic set of code generation techniques for arbitrary compound loop transformations. The algebraic representation of the loop structure and its transformation give way to quantitative techniques for optimizing performance on parallel machines. We discuss in detail the techniques for generating the transformed loop and deriving the desired linear transformation. Key Words: Dependence Analysis, Iteration Spaces, Parallelism, Locality, Load Balance, Conventional Loop Transformations, Linear Loop Transformations Corresponding author. y Parallel Systems Group, Department of Computer Science, 10 King's College Road, University of Toronto, Toronto, ON M5S 1A4, CANADA. Email: [email protected] Kulkarni and Stumm: Linear Loop Transformations 2 1..
Otherworld - Giving Applications a Chance to Survive OS Kernel Crashes
No full textThe default behavior of all commodity operating systems today is to restart the system when a critical error is encountered in the kernel. This terminates all running applications with an attendant loss of "work in progress" that is non-persistent. Our thesis is that an operating system kernel is simply a component of a larger software system, which is logically well isolated from other components, such as applications, and therefore it should be possible to reboot the kernel without terminating everything else running on the same system.
In order to prove this thesis, we designed and implemented a new mechanism, called Otherworld, that microreboots the operating system kernel when a critical error is encountered in the kernel, and it does so without clobbering the state of the running applications. After the kernel microreboot, Otherworld attempts to resurrect the applications that were running at the time of failure. It does so by restoring the application memory spaces, open files and other resources. In the default case it then continues executing the processes from the point at which they were interrupted by the failure. Optionally, applications can have user-level recovery procedures registered with the kernel, in which case Otherworld passes control to these procedures after having restored their process state. Recovery procedures might check the integrity of application data and restore resources Otherworld was not able to restore.
We implemented Otherworld in Linux, but we believe that the technique can be applied to all commodity operating systems. In an extensive set of experiments on real-world applications (MySQL, Apache/PHP, Joe, vi), we show that Otherworld is capable of successfully microrebooting the kernel and restoring the applications in over 97\% of the cases. In the default case, Otherworld adds negligible overhead to normal execution. In an enhanced mode, Otherworld can provide extra application memory protection with overhead of between 4% and 12%.Ph
Otherworld - Giving Applications a Chance to Survive OS Kernel Crashes
No full textThe default behavior of all commodity operating systems today is to restart the system when a critical error is encountered in the kernel. This terminates all running applications with an attendant loss of "work in progress" that is non-persistent. Our thesis is that an operating system kernel is simply a component of a larger software system, which is logically well isolated from other components, such as applications, and therefore it should be possible to reboot the kernel without terminating everything else running on the same system.
In order to prove this thesis, we designed and implemented a new mechanism, called Otherworld, that microreboots the operating system kernel when a critical error is encountered in the kernel, and it does so without clobbering the state of the running applications. After the kernel microreboot, Otherworld attempts to resurrect the applications that were running at the time of failure. It does so by restoring the application memory spaces, open files and other resources. In the default case it then continues executing the processes from the point at which they were interrupted by the failure. Optionally, applications can have user-level recovery procedures registered with the kernel, in which case Otherworld passes control to these procedures after having restored their process state. Recovery procedures might check the integrity of application data and restore resources Otherworld was not able to restore.
We implemented Otherworld in Linux, but we believe that the technique can be applied to all commodity operating systems. In an extensive set of experiments on real-world applications (MySQL, Apache/PHP, Joe, vi), we show that Otherworld is capable of successfully microrebooting the kernel and restoring the applications in over 97\% of the cases. In the default case, Otherworld adds negligible overhead to normal execution. In an enhanced mode, Otherworld can provide extra application memory protection with overhead of between 4% and 12%.Ph
AutoVM: Accelerating Convolutional Neural Network Training with Actively Managed GPU Virtual Memory
No full textThe size of neural networks a GPU can train is limited by the GPU’s memory capacity. Although GPU virtual memory enables training arbitrarily large neural networks, such trainings are often accompanied by severe performance penalties. Furthermore, popular frameworks for constructing machine learning applications, like TensorFlow, have disabled using GPU virtual memory by default. We propose AutoVM, a software layer that can better manage GPU virtual memory in neural network training by incorporating our understandings of neural networks. AutoVM schedules data transfers between GPU and CPU memory to relieve the memory pressure on GPU; and in turn optimizes training speed. We have integrated AutoVM into TensorFlow such that existing machine learning applications can benefit from AutoVM with minimal effort. Our tests suggest that training VGG-19 using AutoVM can be at most 2.5× faster compared to using default Nvidia virtual memory.M.A.S
Methods for GPU acceleration of Big Data applications
No full textBig Data applications are trivially parallelizable because they typically consist of simple and straightforward operations performed on a large number of independent input records. GPUs appear to be particularly well suited for this class of applications given their high degree of parallelism and high memory bandwidth. However, a number of issues severely complicate matters when trying to exploit GPUs to accelerate these applications. First, Big Data is often too large to fit in the GPUâ s separate, limited-sized memory. Second, data transfers to and from GPUs are expensive because the bus that connects CPUs and GPUs has limited bandwidth and high latency; in practice, this often results in data-starved GPU cores. Third, GPU memory bandwidth is high only if data is layed out in memory such that the GPU threads accessing memory at the same time access adjacent memory; unfortunately this is not how Big Data is layed out in practice.
This dissertation presents three solutions that help mitigate the above issues and enable GPU-acceleration of Big Data applications, namely BigKernel, a system that automates and optimizes CPU-GPU communication and GPU memory accesses, S-L1, a caching subsystem implemented in software, and a hash table designed for GPUs. Our key contributions include: (i) the first automatic CPU-GPU data management system that improves on the performance of state-of-the-art double-buffering scheme (a scheme that overlaps communication with computation to improve the GPU performance), (ii) a GPU level 1 cache implemented entirely in the software that outperforms hardware L1 when used by Big Data applications and, (iii) a GPU-based hash table (for storing key-value pairs popular in Big Data applications) that can grow beyond the available GPU memory yet retain reasonable performance. These solutions allow many existing Big Data applications to be ported to GPUs in a straightforward way and achieve performance gains of between 1.04X and 7.2X over the fastest CPU-based multi-threaded implementations.Ph.D
AutoVM: Accelerating Convolutional Neural Network Training with Actively Managed GPU Virtual Memory
No full textThe size of neural networks a GPU can train is limited by the GPU’s memory capacity. Although GPU virtual memory enables training arbitrarily large neural networks, such trainings are often accompanied by severe performance penalties. Furthermore, popular frameworks for constructing machine learning applications, like TensorFlow, have disabled using GPU virtual memory by default. We propose AutoVM, a software layer that can better manage GPU virtual memory in neural network training by incorporating our understandings of neural networks. AutoVM schedules data transfers between GPU and CPU memory to relieve the memory pressure on GPU; and in turn optimizes training speed. We have integrated AutoVM into TensorFlow such that existing machine learning applications can benefit from AutoVM with minimal effort. Our tests suggest that training VGG-19 using AutoVM can be at most 2.5× faster compared to using default Nvidia virtual memory.M.A.S
Configuring In-Memory Caches: From TTL-Aware Sizing to Interval-Based Historical Analysis with HistoChron
No full textIn-memory caches such as Memcached and Redis are crucial for enhancing the performance of distributed systems by significantly reducing query response times. Correctly sizing these caches is critical, especially considering that prominent organizations use terabytes to petabytes of Dynamic Random Access Memory (DRAM) for these caches. Configuring these caches to operate efficiently remains a challenging task, considering the dynamic nature of modern workloads where caching requirements can change significantly over time.
Our thesis is that the state-of-the-art for in-memory cache performance analysis does not accommodate modern workloads. This gap is evident in the lack of consideration for Time-to-Live (TTL) attributes and heterogeneous object sizes, as well as the absence of interval-based historical analysis to address the dynamic nature of these workloads. This dissertation introduces a comprehensive reevaluation of in-memory cache performance analysis tools.We propose novel tools that account for TTL attributes and heterogeneous object sizes, and we introduce a new tool that enables efficient interval-based historical analysis of in-memory cache workloads.
In particular, one of our primary contributions is the development of Miss Ratio Curve (MRC) generation and Working Set Size (WSS) estimation algorithms that accommodate TTL attributes and heterogeneous object sizes.
Our analysis of real-world cache workloads demonstrates that including TTLs can lead to an average reduction in cache memory footprint by 69%, and up to 99%.
Additionally, we introduce HistoChron, a novel methodology with a Graphical User Interface (GUI) that enables efficient interval-based historical analysis of caching workloads. Evaluated on over 5,000 cache access traces from six real-world datasets, encompassing more than 300 billion accesses over an 18-year span, HistoChron demonstrates its efficacy by generating exact MRCs over any arbitrary time interval using just 24MiB of storage space weekly. We also present a lower-overhead variant of HistoChron that generates approximate results with a mean error of less than 1%. These contributions advance the field of in-memory cache management, offering a robust framework for optimizing in-memory caches in alignment with the dynamic demands of modern workloads.Ph.D
Operating System Techniques for Reducing Processor State Pollution
No full textApplication performance on modern processors has become increasingly dictated by the use of on-chip structures, such as caches and look-aside buffers. The hierarchical (multi-leveled) design of processor structures, the ubiquity of multicore processor architectures, as well as the increasing
relative cost of accessing memory have all contributed to this condition. Our thesis is that operating systems should provide services and mechanisms for applications to more efficiently utilize on-chip processor structures. As such, this dissertation demonstrates how the operating system can
improve processor efficiency of applications through specific techniques.
Two operating system services are investigated: (1) improving secondary and last-level cache utilization through a run-time cache filtering technique, and (2) improving the processor efficiency of system intensive applications through a new exception-less system call mechanism. With the first mechanism, we introduce the concept of a software pollute buffer and show that it can be used effectively at run-time, with assistance from commodity hardware performance counters, to reduce pollution of secondary on-chip caches.
In the second mechanism, we are able to decouple application and operating system execution, showing the benefits of the reduced interference in various processor components such as the first level instruction and data caches, second level caches and branch predictor. We show that exception-less system calls are particularly effective on modern multicore processors. We explore two ways for applications to use exception-less system calls. The first way, which is completely transparent to the application, uses multi-threading to hide asynchronous communication between the operating system kernel and the application. In the second way, we propose that applications can directly use the exception-less system call interface by designing programs that follow an event-driven architecture.Ph
PR-MRC: MRC Construction using Non-statistical Sampling
No full textMiss ratio curves (MRCs) play an important role for visualizing and deciding on an effective cache size for a given workload. Unfortunately, generating exact MRCs require processing and memory overheads that are not practical for online use in production systems.
Previous approximate algorithms employ statistical sampling where the set of sampled keys is decided based on satisfying a random sampling condition. We introduce a new approximation algorithm that employs non-statistical sampling where the set of sampled keys is decided based on prior knowledge from previously accessed keys. Our algorithm, called PR-MRC (Pattern Recognition MRC), only updates the MRC when the access pattern is changing.
We evaluate PR-MRC using publicly available traces. More than eighty MRCs were generated and compared to the exact MRC. Results show up to 5.5% lower throughput for MRC generation compared to existing approximation algorithms, while achieving improved MRC accuracy.M.A.S
- …
