Computing platforms that package multiple types of memory, each with their own performance characteristics, are quickly becoming mainstream. To operate efficiently, heterogeneous memory architectures require new data management solutions that are able to match the needs of each application with an appropriate type of memory. As the primary generators of memory usage, applications create a great deal of information that can be useful for guiding memory management, but the community still lacks tools to collect, organize, and leverage this information effectively. To address this gap, this work introduces a novel software framework that collects and analyzes object-level information to guide memory tiering. The framework includes tools to monitor the capacity and usage of individual data objects, routines that aggregate and convert this information into tier recommendations for the host platform, and mechanisms to enforce these recommendations according to user-selected policies. Moreover, the developed tools and techniques are fully automatic, work on standard Linux systems, and do not require modification or recompilation of existing software. Using this framework, this study evaluates and compares the impact of a variety of design choices for memory tiering, including different policies for prioritizing objects for the fast memory tier as well as the frequency and timing of migration events. The results, collected on a modern Intel platform with conventional DDR4 SDRAM as well as Intel Optane NVRAM, show that guiding data tiering with object-level information can enable significant performance and efficiency benefits compared with standard hardware- and software-directed data-tiering strategies for a diverse set of memory-intensive workloads.

Computing platforms that package multiple types of memory, each with their own performance characteristics, are quickly becoming mainstream. To operate efficiently, heterogeneous memory architectures require new data management solutions that are able to match the needs of each application with an appropriate type of memory. As the primary generators of memory usage, applications create a great deal of information that can be useful for guiding memory tiering, but the community still lacks tools to collect, organize, and leverage this information effectively. To address this gap, this work introduces a novel software framework that collects and analyzes object-level information to guide memory tiering. Using this framework, this study evaluates and compares the impact of a variety of data tiering choices, including how the system prioritizes objects for faster memory as well as the frequency and timing of migration events. The results, collected on a modern Intel platform with conventional DRAM as well as non-volatile RAM, show that guiding data tiering with object-level information can enable significant performance and efficiency benefits compared to standard hardware- and software-directed data tiering strategies.

As scaling of conventional memory devices has stalled, many high-end computing systems have begun to incorporate alternative memory technologies to meet performance goals. Since these technologies present distinct advantages and tradeoffs compared to conventional DDR* SDRAM, such as higher bandwidth with lower capacity or vice versa, they are typically packaged alongside conventional SDRAM in a heterogeneous memory architecture. To utilize the different types of memory efficiently, new data management strategies are needed to match application usage to the best available memory technology. However, current proposals for managing heterogeneous memories are limited, because they either (1) do not consider high-level application behavior when assigning data to different types of memory or (2) require separate program execution (with a representative input) to collect information about how the application uses memory resources. This work presents a new data management toolset to address the limitations of existing approaches for managing complex memories. It extends the application runtime layer with automated monitoring and management routines that assign application data to the best tier of memory based on previous usage, without any need for source code modification or a separate profiling run. It evaluates this approach on a state-of-the-art server platform with both conventional DDR4 SDRAM and non-volatile Intel Optane DC memory, using both memory-intensive high-performance computing (HPC) applications as well as standard benchmarks. Overall, the results show that this approach improves program performance significantly compared to a standard unguided approach across a variety of workloads and system configurations. The HPC applications exhibit the largest benefits, with speedups ranging from 1.4× to 7× in the best cases. Additionally, we show that this approach achieves similar performance as a comparable offline profiling-based approach after a short startup period, without requiring separate program execution or offline analysis steps.

Intel's 3D-Xpoint NVDIMM product1 is now in general availability. This technology, herein termed Optane-PM, is a first-in-breed persistent memory technology, designed for the enterprise storage domain. Optane-PM is attached to the memory-bus and is load-store addressable. It provides higher capacity and density than DRAM, while also enabling non-volatility - data is persistent and durable across power-cycles. This paper presents a detailed evaluation of adopting Optane-PM in key-value stores. To achieve this goal, we designed and implemented a high-performance, memory-centric key-value store (MCKVS), that directly leverages persistent memory for data and meta-data storage. Multiple storage back-ends, with different software stacks, are used to provide a comparative analysis and help us understand how Optane-PM is positioned on the performance landscape. We also conducted comparisons against popular in-memory KV stores based on DRAM.

Many applications, including program optimizations, debugging tools, and event loggers, rely on calling context to gain additional insight about how a program behaves during execution. One common strategy for determining calling contexts is to use compiler instrumentation at each function call site and return sites to encode the call paths and store them in a designated area of memory. While recent works have shown that this approach can generate precise calling context encodings with low overhead, the encodings can grow to hundreds or even thousands of bytes to encode a long call path, for some applications. Such lengthy encodings increase the costs associated with storing, detecting, and decoding call path contexts, and can limit the effectiveness of this approach for many usage scenarios.

Computer systems with multiple tiers of memory devices with different latency, bandwidth, and capacity char­acteristics are quickly becoming mainstream. Due to cost and physical limitations, device tiers that enable better performance typically include less capacity. Such heterogeneous memory systems require alternative data management strategies to utilize the capacity-constrained resources efficiently. However, current techniques are often limited because they rely on inflexible hardware caching or manual modifications to source code. This paper introduces MemBrain, a new memory management framework that automates the production and use of data-tiering guidance for applications on hybrid memory systems. MemBrain employs program profiling and source code analysis to enable transparent and efficient data placement across different types of memory. It automatically clusters data with similar expected usage patterns into page-aligned regions of virtual addresses (arenas), and uses offline profile feedback to direct low-level tier assignments for each region. We evaluate MemBrain on an Intel Knights Landing server machine with an upper tier of limited capacity (but higher bandwidth) MCDRAM and a lower tier of conventional DDR4 using a selection of high-bandwidth benchmarks from SPEC CPU 2017 as well as two proxy apps (Lulesh and AMG), and one full scale scientific application (QMCPACK). Our evaluation shows that MemBrain can achieve significant performance and efficiency improvements compared to current guided and unguided management strategies.

This paper addresses the problem of creating durable transactions in byte-addressable Non-Volatile Memory or Persistent Memory (PM) when using Hardware Transactional Memory (HTM)-based concurrency control. It shows how HTM transactions can be ordered correctly and atomically into PM by the use of a novel software protocol combined with a Persistent Memory Controller, without requiring changes to processor cache hardware or HTM protocols. In contrast, previous approaches require significant changes to existing processor microarchitectures. Our approach, evaluated using both micro-benchmarks and the STAMP suite compares well with standard (volatile) HTM transactions. It also yields significant gains in throughput and latency in comparison with persistent transactional locking.

Controlling the distribution and usage of memory power is often difficult, because these effects typically depend on activity across multiple layers of the vertical execution stack. To address this challenge, we construct a novel and collaborative framework that employs object placement, cross-layer communication, and page-level management to effectively distribute application objects in the DRAM hardware to achieve desired power/performance goals. This work describes the design and implementation of our framework, which is the first to integrate automatic object profiling and analysis at the application layer with fine-grained management of memory hardware resources in the operating system. We demonstrate the utility of this framework by employing it to control memory power consumption more effectively. First, we design a custom memory-intensive workload to show the potential of this approach to reduce DRAM energy consumption. Next, we develop sampling and profiling-based analyses and modify the code generator in the HotSpot VM to understand object usage patterns and automatically control the placement of hot and cold objects in a partitioned VM heap. This information is communicated to the operating system, which uses it to map the logical application pages to the appropriate DRAM modules according to user-defined provisioning goals. The evaluation shows that our Java VM-based framework achieves our goal of significant DRAM energy savings across a variety of workloads, without any source code modifications or recompilations.

Executing and optimizing SQL analytics on Data Lakes and Enterprise Data Warehouses (EDW) are areas of significant and growing interest. Achieving high performance for SQL analytics on large-scale data repositories remains a key challenge for data practitioners. The SQL-on-Hadoop Analytics solution described in this paper is very well suited for implementing the infrastructure to support these modern analytics initiatives while meeting requirements such as higher performance, lower cost, more efficient data center footprint, lower power consumption, appropriate storage needs and increased reliability. By using a TPC-DS derived workload applied to 100 TB of data, the work demonstrates for the first time the feasibility of designing such an extremely high-performance cluster. Furthermore, it enables investigation of large-scale SQL-on-Hadoop systems as the Spark SQL framework matures and enables similar investigations into machine learning and related Spark capabilities.

This paper addresses the challenges of coupling byte addressable non-volatile memory (NVM) and hardware transaction memory (HTM) in high-performance transaction processing. We first show that HTM transactions can be ordered using existing processor instructions without any hardware changes. In contrast, existing solutions posit changes to HTM mechanisms in the form of special instructions or modified functionality. We exploit the ordering mechanism to design a novel persistence method that decouples HTM concurrency from back-end NVM operations. Failure atomicity is achieved using redo logging coupled with aliasing to guard against mistimed cache evictions. Our algorithm uses efficient lock-free mechanisms with bounded static memory requirements. We evaluated our approach using both micro-benchmarks, and, benchmarks in the STAMP suite, and showed that it compares well with standard (volatile) HTM transactions. We also showed that it yields significant gains in throughput and latency in comparison with persistent transactional locking.

Emerging persistent memory technologies (generically referred to as Storage Class Memory or SCM) hold tremendous promise for accelerating popular data-management applications like in-memory databases. However, programmers now need to deal with ensuring the atomicity of transactions on SCM-resident data and maintaining consistency between the persistent and in-memory execution orders of concurrent transactions. The problem is specially challenging when high-performance isolation mechanisms like Hardware Transaction Memory (HTM) are used for concurrency control.

Big Data applications need to be able to access large amounts of variable data as fast as possible. Emerging Storage Class Memory (SCM) fit this need by making memory available in large capacity while making changes endure as a seamless continuation of load-store accesses through processor caches. However, when writing values into a persistent memory tier, programmers are faced with the dual problems of controlling untimely cache evictions that might commit changes prematurely, and of grouping changes and making them durable as a unit so that consistency can be guaranteed in the event of sudden failure. In this paper, we present various methods to achieve high-performance byte-addressable persistence for an in-memory data store. We chose Redis, a popular high-performance memory oriented key value database. We modified its source code to use SCM such that updates to data and structures are performed in a failure resilient manner. We evaluated the changes using both internal benchmarks and the Yahoo! Cloud Servicing Benchmark (YCSB). We found that even though Redis uses many SCM read operations, it can benefit from highly optimized persistent SCM write based approaches, especially when SCM write times are longer than DRAM write times. The paper presents an innovative Local Alias Table Batched (LATB) method, and shows that it outperforms the alternatives.

In-memory database management systems (DBMSs) outperform disk-oriented systems for on-line transaction processing (OLTP) workloads. But this improved performance is only achievable when the database is smaller than the amount of physical memory available in the system. To overcome this limitation, some in-memory DBMSs can move cold data out of volatile DRAM to secondary storage. Such data appears as if it resides in memory with the rest of the database even though it does not.

Non-volatile byte-addressable memory has the potential to revolutionize system architecture by providing instruction-grained direct access to vast amounts of persistent data. We describe a non-intrusive memory controller that uses backend operations for achieving lightweight failure atomicity. By moving synchronous persistent memory operations to the background, the performance overheads are minimized. Our solution avoids costly software intervention by decoupling isolation and concurrency-driven atomicity from failure atomicity and durability, and does not require changes to the front-end cache hierarchy. Two implementation alternatives - one using a hardware structure, and the other extending the memory controller with a firmware managed volatile space - are described. Our results show the performance is significantly better than traditional approaches.

This paper introduces a software policy for memory management in heterogeneous memory systems in order to improve the trade-offs between performance and power consumption, while attempting to make the best use of different characteristics of the underlying memory technologies. In this policy, the operating system and the application co-schedule page management in order to make informed decisions about page allocation and migration. Software-Controlled 2- Level Memory (Soft2LM) is a hardware-agnostic approach for efficient usage of heterogeneous memory that allows for region-based allocations, migrations, and application advice. We include analysis of the access characteristics of the PARSEC 3.0 suite of benchmarks, both as motivation for software-guided intelligent page placement as well as for understanding where application advice can make a difference. Our evaluation running PARSEC on our Soft2LM Linux kernel shows an average 4.7x improvement over comparable RAMDISK- based swapping. Even when migrating 100 and 1000 pages per second between regions, Soft2LM performs comparably to a stock system with twice the available DRAM, showing a 1.8\% and 0.7\% improvement, respectively.

In-memory computing is gaining popularity as a means of sidestepping the performance bottlenecks of block storage operations. However, the volatile nature of DRAM makes these systems vulnerable to system crashes, while the need to continuously refresh massive amounts of passive memoryresident data increases power consumption. Emerging storage-class memory (SCM) technologies combine fast DRAM-like cache-line access granularity with the persistence of storage devices like disks or SSDs, resulting in potential 10x-100x performance gains, and low passive power consumption. This unification of storage and memory into a single directly-accessible persistent tier raises significant reliability and pro-grammability challenges. In this paper, we present SoftWrAP, an open-source framework for Software based Write-Aside Persistence. SoftWrAP provides lightweight atomicity and durability for SCM storage transactions, while ensuring fast paths to data in processor caches, DRAM, and persistent memory tiers. We use our framework to evaluate both handcrafted SCM-based microbenchmarks as well as existing applications, specifically the STX B+Tree library and SQLite database, backed by emulated SCM. Our results show significant benefits of SoftWrAP over existing methods such as undo logging and shadow copying, and can match non-atomic durable writes to SCM, thereby gaining atomic consistency almost for free.

This paper describes a lightweight software library to solve the challenges [6], [3], [1], [5], [2] of programming storage class memory (SCM). It provides primitives to demarcate failure-atomic code regions. SCM loads and stores within each demarcated code region (called a “wrap”) are routed through the library, which buffers updates and transmits them to SCM locations asynchronously while allowing their speedy propagation from writers to readers through CPU caches.

Performance and energy efficiency in memory have become critically important for a wide range of computing domains. However, it is difficult to control and optimize memory power and performance because these effects depend upon activity across multiple layers of the vertical execution stack. To address this challenge, we construct a novel and collaborative framework that employs object placement, cross-layer communication, and page-level management to effectively distribute application objects in the DRAM hardware to achieve desired power/performance goals. In this work, we describe the design and implementation of our framework, which is the first to integrate automatic object profiling and analysis at the application layer with fine-grained management of memory hardware resources in the operating system. We demonstrate the utility of our framework by employing it to more effectively control memory power consumption. We design a custom memory-intensive workload to show the potential of our approach. Next, we develop sampling and profiling-based analyses and modify the code generator in the HotSpot VM to understand object usage patterns and automatically determine and control the placement of hot and cold objects in a partitioned VM heap. This information is communicated to the operating system, which uses it to map the logical application pages to the appropriate DRAM ranks according to user-defined provisioning goals. We evaluate our framework and find that it achieves our test goal of significant DRAM energy savings across a variety of workloads, without any source code modifications or recompilations.

With the flourishing of IoV(Internet of Vehicles) technology, location based services need to handle the positional coordinates streaming in continuously from large numbers of vehicles. Across the hundreds of thousands of kilometers of roads, with tens of millions of vehicles on them, it is a significant performance challenge to determine in real time where vehicles are; how quickly and where they are headed; and when, where, and how much congestion can be expected to build as a result. The high volume of data and the rate at which the mappings must be performed require high computational efficiency and avoidance of storage accesses where possible. This paper introduces a Hadoop based approach for handling such large volumes of information. The paper describes a couple of simple adjustments to methods available in JTS and Java AWT that provide efficient mapping between vehicle positions and road segments, shows the importance of secondary sort in achieving the needed computational throughput, and establishes the significant performance benefit to be achieved from in-memory processing. An evaluation using RAF, a lightweight in-memory computing framework, shows the mapping is 20X+ faster than Hadoop approach to achieve results for real-time operation.

Up-to-date business intelligence has become a critical differentiator for the modern data-driven highly engaged enterprise. It requires rapid integration of new information on a continuous basis for subsequent analyses. ETL-based and traditionally batch-processing oriented methods of absorbing changes into a relational database schema take time, and are therefore incompatible with very low-latency demands of realtime analytics. Instead, in-memory clustered stores that employ tunable consistency mechanisms are becoming attractive since they dispense with the need to transform and transit data between storage layouts and tiers. When data is updated infrequently, in-memory approaches such as RDD transformations in Spark can suffice, but as updates become frequent, such in-memory approaches need to be extended to support dynamic datasets. This paper describes a few key additional requirements that result from having to support in-memory processing of data while updates proceed concurrently. The paper describes Real-time Analytics Foundation (RAF), an architecture to meet the new requirements. Performance of an early implementation of RAF is also described: for an unaudited TPC-H derived workload, RAF shows a node-to-node scaling ratio of 88% at 8 nodes, and for a query equivalent to Q6 in the TPC-H set, RAF is able to show 9x improvement over that of Hive-Hadoop. The paper also describes two RAF based solutions that are being put together by two independent software vendors in China.

This paper proposes a collaborative approach in which applications can provide guidance to the operating system regarding allocation and recycling of physical memory. The operating system incorporates this guidance to decide which physical page should be used to back a particular virtual page. The key intuition behind this approach is that application software, as a generator of memory accesses, is best equipped to inform the operating system about the relative access rates and overlapping patterns of usage of its own address space. It is also capable of steering its own algorithms in order to keep its dynamic memory footprint under check when there is a need to reduce power or to contain the spillover effects from bursts in demand. Application software, working cooperatively with the operating system, can therefore help the latter schedule memory more effectively and efficiently than when the operating system is forced to act alone without such guidance. It is particularly difficult to achieve power efficiency without application guidance since power expended in memory is a function not merely of the intensity with which memory is accessed in time but also how many physical ranks are affected by an application's memory usage.

Current hardware and operating system power management mechanisms use heuristics of a general nature that are largely application software independent, thus treating the application as a black box. The resulting communication disconnect between OS power management policies and application-level quality of service goals can either cause breaches in service level agreements (SLA) when the policies are too aggressive, or reduce energy savings when they are too conservative. In this work, we engage enterprise software in the management of its own performance and power by introducing a middleware that we call SLA Governor. The SLA Governor receives periodic updates on application level performance and the applicable SLA. Based on the available leeway and recent history, the SLA Governor makes, and puts into effect, decisions to raise or lower CPU speeds. Compared to state of the art OS based power management, the SLA Governor provides 8.3% better energy savings for an online transaction processing workload (TPoX) using a latest generation machine employing Intel E5-5600 (“Westmere”) series processors.

The growing popularity of hosted storage services and shared storage infrastructure in data centers is driving the recent interest in resource management and QoS in storage systems. The bursty nature of storage workloads raises significant performance and provisioning challenges, leading to increased resource requirements, management costs, and energy consumption. We present a novel workload shaping framework to handle bursty workloads, where the arrival stream is dynamically decomposed to isolate its bursts, and then rescheduled to exploit available slack. We show how decomposition reduces the server capacity requirements and power consumption significantly, while affecting QoS guarantees minimally. We present an optimal decomposition algorithm RTT and a recombination algorithm Miser, and show the benefits of the approach by evaluating the performance of several storage workloads using both simulation and Linux implementation.

The growing popularity of hosted storage services and shared storage infrastructure in data centers is driving the recent interest in resource management and QoS in storage systems. The bursty nature of storage workloads raises significant performance and provisioning challenges, leading to increased infrastructure, management, and energy costs. We present a novel dynamic workload shaping framework to handle bursty workloads, where the arrival stream is dynamically decomposed to isolate its bursts, and then rescheduled to exploit available slack. We show how decomposition reduces the server capacity requirements dramatically while affecting QoS guarantees minimally. We present an optimal decomposition algorithm RTT and a recombination algorithm Miser, and show the benefits of the approach by performance evaluation using several storage traces.

Analysis of workload execution and identification of software and hardware performance barriers provide critical engineering benefits; these include guidance on software optimization, hardware design tradeoffs, configuration tuning, and comparative assessments for platform selection. This paper uses Model trees to build statistical regression models for the SPEC1 CPU2006 and the SPEC OMP2001 suites. These models link performance to key microarchitectural events. The models provide detailed recipes for identifying the key performance factors for each suite and for determining the contribution of each factor to performance. The paper discusses how the models can be used to understand the behaviors of the two suites on a modern processor. These models are applied to obtain a detailed performance characterization of each benchmark suite and its member workloads and to identify the commonalities and distinctions among the performance factors that affect each of the member workloads within the two suites. This paper also addresses the issue of model transferability. It explores the question: How useful is an existing performance model (built on a given suite of workloads) to study the performance of different workloads or suites of workloads? A performance model built using data from workload suite P is considered transferable to workload suite Q if it can be used to accurately study the performance of workload suite Q. Statistical methodologies to assess model transferability are discussed. In particular, the paper explores the use of two-sample hypothesis tests and prediction accuracy analysis techniques to assess model transferability. It is found that a model trained using only 10% of the SPEC CPU2006 data is transferable to the remaining data. This finding holds also for SPEC OMP2001. In contrast, it is found that the SPEC CPU2006 model is not transferable to SPEC OMP2001 and vice versa.

The identification of performance issues on specific computer architectures has a variety of important benefits such as tuning software to improve performance, comparing the performance of various platforms and assisting in the design of new platforms. In order to enable this analysis, most modern micro-processors provide access to hardware-based event counters. Unfortunately, features such as out-of-order execution, pre-fetching and speculation complicate the interpretation of the raw data. Thus, the traditional approach of assigning a uniform estimated penalty to each event does not accurately identify and quantify performance limiters. This paper presents a novel method employing a statistical regression-modeling approach to better achieve this goal. Specifically, a model-tree based approach based on the M5' algorithm is implemented and validated that accounts for event interactions and workload characteristics. Data from a subset of the SPEC CPU2006 suite is used by the algorithm to automatically build a performance-model tree, identifying the unique performance classes (phases) found in the suite and associating with each class a unique, explanatory linear model of performance events. These models can be used to identify performance problems for a given workload and estimate the potential gain from addressing each problem. This information can help orient the performance optimization efforts to focus available time and resources on techniques most likely to impact performance problems with highest potential gain. The model tree exhibits high correlation (more than 0.98) and low relative absolute error (less than 8 %) between predicted and measured performance, attesting it as a sound approach for performance analysis of modern superscalar machines

The authors formally define a distributed-memory parallel architecture called the pipelined hypercube. A coarse-grained parallel sorting algorithm that can be mapped efficiently on such an architecture is also presented. The pipelined hypercube has a more powerful communication mechanism than the traditional binary code architecture, in that it permits communication of blocks of data between processing elements (PEs) to be performed in a pipelined manner. Certain data communication problems which would probably be serialized on the binary code architecture, can be performed optimally on the pipelined hypercube. The sorting algorithm can be mapped efficiently onto a pipelined hypercube of P PEs. It sorts N data items, initially distributed among the PEs, in time O((N log N/P)+log/sup 2/ P), thereby achieving linear speedup when P is O(N/log N).>

This paper describes a modular, systolic design for two-dimensional convolution which is a frequent and computationally intensive operation in low-level image processing. The design consists of a one-dimensional array of homogeneous cells, each with a fixed amount of storage. The paper also presents schema by which the design consisting of a limited number of cells can be used to implement convolutions of varying kernel sizes, with optimal throughput. The design is simple and hence a good candidate for VLSI integration. Its one-dimensional organization and unidirectional data flow characteristics result in good fault-tolerance for the array.

Parallel algorithms for computing the minimum spanning tree of a weighted undirected graph, and the bridges and articulation points of an undirected graphs on a fixed-size linear array of processors are presented. For a graph of n vertices, the algorithms operate on a linear array of p processors and require O(n2/p) time for all p, 1 ≤ p ≤ n. In particular, using n processors the algorithms require O(n) time which is optimal on this model. The paper describes two approaches to limit the communication requirements for solving the problems. The first is a divide-and-conquer strategy applied to Sollin's algorithm for finding the minimum spanning tree of a graph. The second uses a novel data-reduction technique that constructs an auxiliary graph with no more than 2n − 2 edges, whose bridges and articulation points are the bridges and articulation points of the original graph.