Non-volatile main memory (NVRAM) enables data persistence in memory. However, the existence of transient CPU caches in modern computer architectures brings a serious performance issue. In particular, cache lines have to be flushed frequently to guarantee consistent persistent program states. Hence, persistence and performance cannot be easily obtained simultaneously. In this paper, we optimize data persistence by proposing a software cache. The software cache first buffers lines that need to be flushed, and then flushes them out at an appropriate later time. The software cache aims to maximize the combination of cache line flushes. We designed a new linear-time algorithm to calculate cache miss ratio curve (MRC) so as to adaptively select the best cache capacity at run-time based on program behavior. We evaluated the software cache on a real-world memory-based database benchmark, the SPLASH2 benchmark suite and four micro-benchmarks. Results indicate that the software cache solution reduces cache write backs to persistent memory by 12× and improves performance over the state-of- the-art methods by 2.1× on average, measured on a real system emulator.

Technology trends suggest that byte-addressable nonvolatile memory (NVM) will supplant many uses of DRAM over the coming decade, raising the prospect of inexpensive recovery from power failures and similar faults. Ensuring the consistency of persistent state remains nontrivial, however, in the presence of volatile caches; cached values can "leak" back to persistent memory in arbitrary order. To ensure consistency, existing persistent memory algorithms use expensive, explicit write-back instructions to force each value back to memory before performing a dependent write, thereby incurring significant run-time overhead. To reduce this overhead, we present a new design paradigm that we call periodic persistence. In a periodically persistent data structure, updates are made "in place," but can safely leak back to memory in any order, because only those updates that are known to be valid will be heeded during recovery. To guarantee forward progress, we periodically force a write-back of all dirty data in the cache, ensuring that all "sufficiently old" updates have indeed become persistent, at which point they become semantically visible to the recovery process. As an example of periodic persistence, we present a transactional hash map, Dalí, together with an informal proof of safety (buffered durable linearizability). Experiments with a prototype implementation suggest that periodic persistence can offer substantially better performance than either file-based or incrementally persistent (per-access write-back) alternatives.

It is expected that DRAM memory will be augmented, and perhaps eventually replaced, by one of several up-and-coming memory technologies. These are all non-volatile, in that they retain their contents without power. This allows primary memory to be used as a fast disk replacement. It also enables more aggressive programming models that directly leverage persistence of primary memory. However, it is challenging to maintain consistency of memory in such an environment. There is no consensus on the right programming model for doing so, and subtle differences can have large, and sometimes surprising, effects on the implementation and its performance. The existing literature describes multiple programming systems that provide point solutions to the selective persistence for user data structures. Real progress in this area requires a choice of programming model, which we cannot reasonably make without a real understanding of the design space. Point solutions are insufficient. We systematically explore what we consider to be the most promising part of the space, precisely defining semantics and identifying implementation costs. This allows us to be much more explicit and precise about semantic and implementation trade-offs that were usually glossed over in prior work. It also exposes some promising new design alternatives.

Byte addressable non-volatile memory (NVRAM) is likely to supplement, and perhaps eventually replace, DRAM. Applications can then persist data structures directly in memory instead of serializing them and storing them onto a durable block device. However, failures during execution can leave data structures in NVRAM unreachable or corrupt. In this paper, we present Makalu, a system that addresses non-volatile memory management. Makalu offers an integrated allocator and recovery-time garbage collector that maintains internal consistency, avoids NVRAM memory leaks, and is efficient, all in the face of failures.

Preserving the integrity of application data across updates in the presence of failure is an essential function of computing systems, and byte-addressable non-volatile memory (NVM) broadens the range of fault-tolerance strategies that implement it. NVM invites database systems to manipulate durable data directly via load and store instructions, but overheads due to the widely used mechanisms that ensure consistent recovery from failures impair performance, e.g., the logging overheads of transactions. We introduce the concept of Timely Sucient Persistence (TSP) mechanisms, which is relevant to both conventional and emerging computer architectures. For a broad spectrum of faulttolerance requirements, satisfactory TSP mechanisms typically involve lower overheads during failure-free operation than their non-TSP counterparts; hardware and OS support can facilitate TSP mechanisms. We present TSP variants of programs representing two very di↵erent classes of sharedmemory multi-threaded software that store application data in persistent heaps: The first employs conventional mutexes for isolation, and TSP substantially reduces the overhead of a fault-tolerance mechanism based on fine-grained logging. The second class of software employs lock-free and wait-free algorithms; remarkably, TSP is very easy to retrofit onto a non-resilient design and enjoys zero runtime overhead .E xtensive experiments confirm that TSP yields robust crash resilience with substantially reduced overhead.

Non-volatile main memory, such as memristors or phase change memory, can revolutionize the way programs persist data. In-memory objects can themselves be persistent without the need for a separate persistent data storage format. However, the challenge is to ensure that such data remains consistent if a failure occurs during execution.

A large body of data-flow analyses exists for analyzing and optimizing sequential code. Unfortunately, much of it cannot be directly applied on parallel code, for reasons of correctness. This article presents a technique to automatically, aggressively, yet safely apply sequentially-sound data-flow transformations, without change , on shared-memory programs. The technique is founded on the notion of program references being “siloed” on certain control-flow paths. Intuitively, siloed references are free of interference from other threads within the confines of such paths. Data-flow transformations can, in general, be unblocked on siloed references. The solution has been implemented in a widely used compiler. Results on benchmarks from SPLASH-2 show that performance improvements of up to 41% are possible, with an average improvement of 6% across all the tested programs over all thread counts.

Programming with atomic sections is a promising alternative to locks since it raises the abstraction and removes deadlocks at the programmer level. However, implementations of atomic sections using software transactional memory (STM) support have significant bookkeeping overheads. Additionally, because of the speculative nature of transactions, aborts can be frequent greatly lowering application performance. Thus regardless of the STM implementation, tools need to be available to programmers that provide insights into the runtime characteristics of an application as well as provide means to improve performance. This paper attempts to identify the source of an abort at the granularity of a transactional memory reference. The resulting abort patterns are captured in the form of a runtime abort graph (RAG). We show how to build this graph efficiently using compiler instrumentation. We then describe a technique that works on the RAG and automatically recommends STM policy changes to improve performance. Detailed experimental results are presented showing the tradeoffs in building the RAG and its use in reducing aborts and improving performance.

A large body of data-flow analyses exists for analyzing and optimizing sequential code. Unfortunately, much of it cannot be directly applied on parallel code, for reasons of correctness. This paper presents a technique to automatically, aggressively, yet safely apply sequentially-sound data-flow transformations, without change, on shared-memory programs. The technique is founded on the notion of program references being "siloed" on certain control-flow paths. Intuitively, siloed references are free of interference from other threads within the confines of such paths. Data-flow transformations can, in general, be unblocked on siloed references.

We present the design and implementation of a dynamic conflict graph annotated with fine grain transaction characteristics and show that this is important information for effective performance analysis of a software transactional memory (STM) program. We show how to implement the necessary support in a compiler and an STM with minimal perturbation of the original behavior of the application.

Atomic sections have been recently introduced as a language construct to improve the programmability of concurrent software. They simplify programming by not requiring the explicit specification of locks for shared data. Typically atomic sections are supported in software either through the use of optimistic concurrency by using transactional memory or through the use of pessimistic concurrency using compiler-assigned locks. As a software transactional memory (STM) system does not take advantage of the specific memory access patterns of an application it often suffers from false conflicts and high validation overheads. On the other hand, the compiler usually ends up assigning coarse grain locks as it relies on whole program points-to analysis which is conservative by nature. This adversely affects performance by limiting concurrency. In order to mitigate the disadvantages associated with STM's lock assignment scheme, we propose a hybrid approach which combines STM's lock assignment with a compiler aided selective lock assignment scheme (referred to as SCLA-STM). SCLA-STM overcomes the inefficiencies associated with a purely compile-time lock assignment approach by (i) using the underlying STM for shared variables where only a conservative analysis is possible by the compiler (e.g., in the presence of may-alias points to information) and (ii) being selective about the shared data chosen for the compiler-aided lock assignment. We describe our prototype SCLA-STM scheme implemented in the hp-ux IA-64 C/C++ compiler, using TL2 as our STM implementation. We show that SCLA-STM improves application performance for certain STAMP benchmarks from 1.68% to 37.13%.

Data prefetching has been widely used in the past as a technique for hiding memory access latencies. However, data prefetching in multi-threaded applications running on chip multiprocessors (CMPs) can be problematic when multiple cores compete for a shared on-chip cache (L2 or L3). In this paper, we (i) quantify the impact of conventional data prefetching on shared caches in CMPs. The experimental data collected using multi-threaded applications indicates that, while data prefetching improves performance in small number of cores, its benefits reduce significantly as the number of cores is increased, that is, it is not scalable; (ii) identify harmful prefetches as one of the main contributors for degraded performance with a large number of cores; and (iii) propose and evaluate a compiler-directed data prefetching scheme for shared on-chip cache based CMPs. The proposed scheme first identifies program phases using static compiler analysis, and then divides the threads into groups within each phase and assigns a customized prefetcher thread (helper thread) to each group of threads. This helps to reduce the total number of prefetches issued, prefetch overheads, and negative interactions on the shared cache space due to data prefetches, and more importantly, makes compiler-directed prefetching a scalable optimization for CMPs. Our experiments with the applications from the SPEC OMP benchmark suite indicate that the proposed scheme improves overall parallel execution latency by 18.3% over the no-prefetch case and 6.4% over the conventional data prefetching scheme (where each core prefetches its data independently), on average, when 12 cores are used. The corresponding average performance improvements with 24 cores are 16.4% (over the no-prefetch case) and 11.7% (over the conventional prefetching case). We also demonstrate that the proposed scheme is robust under a wide range of values of our major simulation parameters, and the improvements it achieves come very close to those that can be achieved using an optimal scheme.

Research on procedure inlining has mainly focused on heuristics that decide whether inlining a particular call-site maximizes application performance. However, other equally important aspects of inline analysis such as call-site analysis order, indirect effects of inlining, and selection of the most profitable version of a procedure warrant more attention. This paper evaluates a number of different sequences in which call-sites are examined for inlining and shows that choosing the correct order is crucial to obtaining the best run-time performance. We then present a novel, work-list-based, and updated sequence that achieves the best results. While applying cross-module inline analysis on large applications with thousands of files and millions of lines of code, we separate the analysis from the transformation phase and allow the former to work solely on summary information in order to reduce compile-time and memory consumption. A focus of this paper is to enumerate the summaries that our compiler maintains, present a technique to compute the goodness factor on which the work-list sequence is based, and describe methods to continuously update the summaries as and when a call-site is accepted for inlining. We then introduce inline specialization, a new technique that facilitates inlining into call chains selectively. The power of inline specialization lies in its ability to choose the most profitable version of the called procedure without having to maintain multiple versions at any point of time. We discuss implementation of these techniques in the HPUX Itanium/spl reg/ production compiler and present experimental results showing that a dynamic work-list based analysis order, comprehensive summary updates, and inline specialization significantly improve performance of applications.

With the delta between processor clock frequency and memory latency ever increasing and with the standard locality improving transformations maturing, compilers increasingly seek to modify an application's data layout to improve spatial and temporal locality and to reduce cache miss and page fault penalties. In this paper, we describe a practical implementation of the data layout optimizations structure splitting, structure peeling, structure field reordering and dead field removal, both for profile and non-profile based compilations. We demonstrate significant performance gains, but find that automatic transformations fail for a relatively high number of record types because of legality violations or profitability constraints. Additionally, we find a class of desirable transformations for which the framework cannot provide satisfying results. To address this issue, we complement the automatic transformations with an advisory tool. We reuse the compiler analysis done for automatic transformation and correlate its results with performance data collected during runtime for structure fields, such as data cache misses and latencies. We then use the compiler as a performance analysis and reporting tool and provide insight into how to layout structure types more efficiently.

Performing analysis across module boundaries for an entire program is important for exploiting several runtime performance opportunities. However, due to scalability problems in existing full-program analysis frameworks, such performance opportunities are only realized by paying tremendous compile-time costs. Alternative solutions, such as partial compilations or user assertions, are complicated or unsafe and as a result, not many commercial applications are compiled today with cross-module optimizations. We present SYZYGY, a practical framework for performing efficient, scalable, interprocedural optimizations. The framework is implemented in the HP-UX Itanium/spl reg/ compilers and we have successfully compiled many very large applications consisting of millions of lines of code. We achieved performance improvements of up to 40% over optimization level two and compilation time improvements in the order of 100% and more compared to a previous approach.

This paper presents a novel technique to perform global optimization of communication and preprocessing calls in the presence of array accesses with arbitrary subscripts. Our scheme is presented in the context of automatic parallelization of sequential programs to produce message passing programs for execution on distributed machines. We use the static single assignment (SSA) form for message passing programs as the intermediate representation and then present techniques to perform global optimizations even in the presence of array accesses with arbitrary subscripts. The focus of this paper is in showing that, using a uniform compilation method both at compile-time and at run-time, our framework is able to determine the earliest and the latest legal communication point for a certain distributed array reference even in the presence of arbitrary array addressing functions. Our scheme then heuristically determines the final communication point after considering the interaction between the relevant communication schedules. Owing to combined static and dynamic analysis, a quasi-dynamic method of code generation is implemented. We describe the need for proper interaction between the compiler and the run-time routines for efficient implementation of optimizations as well as for compatible code generation. All of the analyses is initiated at compile-time, static analyses of the program is done as much as possible, and then the run-time routines take over the analyses while building on the data structures initiated at compile time. This scheme has been incorporated in our compiler framework which can use uniform methods to compile, parallelize, and optimize a sequential program irrespective of the subscripts used in array addressing functions. Experimental results for a number of benchmarks on an IBM SP-2 show up to around 10-25% reduction in total run-times in our globally-optimized schemes compared to other state-of-the-art schemes on 16 processors.

This paper starts from a well-known idea, that structure in irregular problems improves sequential performance, and tries to show that the same structure can also be exploited for parallelization of irregular problems on a distributed-memory multicomputer. In particular, we extend a well-known parallelization technique called run-time compilation to use structure information that is explicit on the array subscripts. This paper presents a number of internal representations suited to particular access patterns and shows how various preprocessing structures such as translation tables, trace arrays, and interprocessor communication schedules can be encoded in terms of one or more of these representations. We show how loop and index normalization are important for detection of irregularity in array references, as well as the presence of locality in such references. This paper presents methods for detection of irregularity, feasibility of inspection, and finally, placement of inspectors and interprocessor communication schedules. We show that this process can be automated through extensions to an HPF/Fortran-77 distributed-memory compiler (PARADIGM) and a new runtime support for irregular problems (PILAR) that uses a variety of internal representations of communication patterns. We devise performance measures which consider the relationship between the inspection cost, the execution cost, and the number of times the executor is invoked so that a comparison of the competing schemes can be performed independent of the number of iterations. Finally, we show experimental results on an IBM SP-2 that validate our approach. These results show that dramatic improvements in both memory requirements and execution time can be achieved by using these techniques.

We present a novel framework of a Web-based automated parallel CAD environment. The goal of this project is to make available to the CAD community a growing number of design and test applications that support standard interfaces and execute efficiently in a parallel environment. The design files of a user working on a remote machine are transparently shipped to the local Compute Center, the relevant computation is performed in a parallel environment and then the results are returned back to the user. A job submission and scheduling tool ensures proper load balance and maximal usage of the various parallel machines. The whole process is done efficiently and transparently without the user having to bother about any low-level details. At present, a number of parallel CAD tools including a placement tool, a fault simulator and a VHDL simulator are supported. Results from a preliminary implementation are impressive and show the feasibility of the approach.

Almost all applications containing indirect array addressing (irregular accesses) have a substantial number of direct array accesses (regular accesses) too.A conspicuous percentage of these direct array accesses usually require interprocessor communication for the applications to run on a distributed memory multicomputer.This study highlights how lack of a uniform representation and lack of a uniform scheme to generate communication structures and parallel code for regular and irregular accesses in a mixed regularirregular application prevent sophisticated optimizations.Furthermore, we also show that code generated for regular accesses using compile-time schemes are not alzvays compatible to code generated for irregular accesses using run-time schemes.In our opinion, existing schemes handling mixed regular-irregular applications either incur unnecessary preprocessing costs or fail to perform the best communication optimization.This study presents a uniform scheme to handle both regular and irregular accesses in a mixed regularirregular application.While this allows for sophisticated communication optimizations such as message coalescing, message aggregation to be made across regular and irregular accesses, the preprocessing costs incurred are likely to be minimum.Experimental comparisons for various benchmarks on a 16-processor IBM SP-2 show that our scheme is feasible and better than existing schemes.

An improved hierarchical testing algorithm for combinational circuits with repetitive sub-circuits using the bus fault model has been proposed. This model exploits the regularity of a circuit by grouping together identical gate-level sub-circuits into high-level sub-circuits. Though the existing test generation techniques using this model reduces the required time substantially in many cases, it fails on encountering incompatibility between the inputs and outputs of high-level modules. The algorithm proposed helps in resolving high level incompatibility. The concept of a state transition graph has been used and it has been shown that resolving incompatibility at the high level is equivalent to finding a loop in the state transition graph. The technique is hierarchical in the sense that the original modeled high-level circuit is sub-divided into a number of components as soon as an incompatibility is encountered. The results of implementation of the algorithm for a class of combinational circuits indicate a significant reduction in the test generation time and complete fault coverage thus validating our technique.