This file contains bibliographic citations (with abstracts) for selected
papers produced at the University of Rochester. Most citations end
with a link to a PDF or (formerly) compressed postscript file.
These files are also available via anonymous ftp from
ftp.cs.rochester.edu (user anonymous, password your_name), in the
directory pub/.
Copyright on many of these papers may be owned by organizations other
than the University of Rochester, as indicated in the citations below.
For more information or for help obtaining technical
reports not available online, please contact
tr@cs.rochester.edu.
Keywords: software transactional memory; nonblocking progress; performance;WSTM.
The current state of the art seems to favour blocking software transactional memory (STM) implementations over nonblocking ones, and a common belief is that nonblocking STMs fundamentally cannot be made to perform as well as blocking ones. But this belief is based on experience, intuition, and anecdote, not on rigorous analysis.We believe there is still plenty of room for improvement in the performance of nonblocking STMs and that, regardless of performance, blocking is unacceptable in some contexts. It is therefore important to continue improving nonblocking STMs, both as a goal in its own right, as well as to inform research aimed at determining whether a fundamental gap exists between blocking and nonblocking STMs.
We describe a novel nonblocking copyback mechanism for a word-based software transactional memory (STM), which closely follows simple and efficient blocking mechanisms in the common case. Previous nonblocking copyback mechanisms impose significant overhead on the common case. Our performance experiments show that this approach yields significant performance improvement over the previous best nonblocking word-based STM. Our design approach can be applied to some other blocking STMs to achieve nonblocking counterparts that perform similarly in the common case.
Keywords: reuse distance; time distance; random access;.
Reuse distance is a basic metric for program locality. The distribution of reuse distances, called the reuse signature, shows the average locality or the amount of actively used data. Random access is often assumed in analytical models about program behavior. An interesting question is whether the reuse behavior of random data access has a closed-form answer. In this paper we prove that the length of reuse distances of random access is uniformly distributed from 0 to n-1 when n is the size of data. We also test random traces of different lengths to show the effect on the distribution.
Keywords: Decoupled; hardware transactional memory; cache coherence; signatures; programmable data isolation; redo buffer;conflict tables; lazy conflict management; RTM; FlexTM;.
A high-concurrency Transactional memory (TM) implementation needs to track concurrent accesses, buffer speculative updates, and manage conflicts. We propose that the requisite hardware mechanisms be decoupled from one another. Decoupling (a) simplifies hardware development, by allowing mechanisms to be developed independently; (b) enables software to manage these mechanisms and control policy (e.g., conflict management strategy and laziness of conflict detection); and (c) makes it easier to use the hardware for purposes other than TM.We present a system, FlexTM (FLEXible Transactional Memory), that employs three decoupled hardware mechanisms: read and write signatures, which summarize per-thread access sets; per-thread conflict summary tables, which identify the threads with which conflicts have occurred; and a lazy versioning mechanism, which maintains the speculative updates in the local cache and employs a thread-private buffer (in virtual memory) only in the rare event of an overflow. The conflict summary tables allow lazy conflict management to occur locally, with no global arbitration (they also support eager management). All three mechanisms are kept software-accessible, to enable virtualization and to support transactions of arbitrary length. In experiments with a prototype on the Simics/GEMS testbed, FlexTM provides a 5 times speedup over high-quality software TM, with no loss in policy flexibility. Our analysis highlights the importance of lazy conflict detection, which maximizes concurrency and helps to ensure forward progress. Eager detection provides better overall system utilization in a mixed-programming environment. We also present a preliminary case study in which FlexTM components aid in the development of a tool to detect memory-related bugs.
Keywords: Transactional memory; nonblocking synchronization; ASTM; .
This paper addresses interoperability of software transactions and ad hoc nonblocking algorithms. Specifically, we explain how to modify %arbitrary nonblocking methods so that (1) they can be used both inside and outside transactions, (2) external uses serialize with transactions, and (3) internal uses succeed if, only if, and when the surrounding transaction commits. Interoperability has two important benefits. First, it allows nonblocking methods to play the role of fast, closed nested transactions, with potentially significant performance benefits. Second, it allows programmers to safely mix transactions and nonblocking methods, e.g., to update legacy code, call nonblocking libraries, or atomically compose nonblocking methods.We demonstrate our ideas in the context of the Java-based ASTM system on several lock-free datastructures. Our findings are encouraging: Although performance of transaction-safe nonblocking objects does not match that of the original nonblocking objects, the degradation is not unacceptably high (particularly after application of an optimization we call lazy logging). It is, moreover, significantly better than that of analogous transactional objects. We conclude that transaction safe nonblocking objects can be a significant enhancement to software transactional memory.
Keywords: file system; journaling; data consistency;.
A filesystem's sole purpose is to store data so it can be easily accessed at a later time. Part of that entails recovering properly from a system crash. But a difficulty that modern filesystems face is the advent of write caching in a disk. The disk will report that a write operation has completed before the data is actually secure on the magnetic platter. How is a programmer to respond to this outright lie from the hardware?The problem goes even further. Journaled filesystems depend on the order of the write operations they send to the disk. If the real data is written before the journal, then there is not only no point in having the journal, but it actually gives a false sense of security. After a crash, the disk checker will only replay the journal, never bothering to examine the real data on the disk for consistency.
There is a solution to this problem. It is called Tagged Command Queuing (TCQ) in the SCSI-2 specification. And it is optional. Filesystems, Ext3 in particular in this paper, use TCQ exclusively and have no fallback. We present a fallback solution that depends on a required feature of the SCSI-2 specification, Force Unit Access (FUA). Our results showed that write-intensive workloads display a significant slowdown from the FUA-based solution. However, the performance impact is still less than that incurred by using other methods, such as synchronizing the cache after each journal write.
Keywords: bloom filters; optimization; cooperative distributed caching;distributed keyword search;.
Bloom filters are compact set representations that support set membership queries with small, one-sided error probabilities. Standard Bloom filters are oblivious to object popularity in sets and membership queries. However, sets and queries in many distributed applications follow known, stable, highly skewed distributions (e.g., Zipf-like). This paper studies the problem of minimizing the false-positive probability of a Bloom filter by adapting the number of hashes used for each data object to its popularity in sets and membership queries. We model the problem as a constrained nonlinear integer program and propose two polynomial-time solutions with bounded approximation ratios --- one is a 2-approximation algorithm with O(N^c) running time (c>=6 in practice); the other is a (2+e)-approximation algorithm with running time O(N^2/e), e>0. Here N denotes the total number of distinct data objects that appear in sets or queries. We quantitatively evaluate our proposed approach on two distributed applications (cooperative caching and full-text keyword searching) driven by real-life data traces. Compared to standard Bloom filters, our data popularity-conscious Bloom filters achieve up to 24 and 27 times false-positive probability reduction for the two applications respectively. The quantitative evaluation also validates our solution's bounded approximation ratio to the optimal.
Keywords: transactional memory; privatization: RSTM; Obstruction freedom;.
Early implementations of software transactional memory (STM) assumed that sharable data would be accessed only within transactions. Memory may appear inconsistent in programs that violate this assumption, even when program logic would seem to make extra-transactional accesses safe. Designing STM systems that avoid such inconsistency has been dubbed the privatization problem. We argue that privatization comprises a pair of symmetric subproblems: private operations may fail to see updates made by transactions that have committed but not yet completed; conversely, transactions that are doomed but have not yet aborted may see updates made by private code, causing them to perform erroneous, externally visible operations. We explain how these problems arise in different styles of STM, present strategies to address them, and discuss their implementation tradeoffs. We also propose a taxonomy of contracts between the system and the user, analogous to programmer-centric memory con- sistency models, which allow us to classify programs based on their privatization requirements. Finally, we present empirical comparisons of several privatization strategies. Our results suggest that the best strategy may depend on application characteristics
Keywords: cache coherence; alert-on-update; programmable data isolation; RTM; transactional memory.
There has been considerable recent interest in the support of transactional memory (TM) in both hardware and software. We present an intermediate approach, in which hardware is used to accelerate a TM implementation controlled fundamentally by software. Our hardware support reduces the overhead of common TM tasks, namely, conflict detection and data isolation, for bounded transactions. Software control allows policy flexibility for conflict detection, contention management, and data granularity, in addition to enabling transactions unbounded in space and time. Our hardware consists of 1) an alert-on-update mechanism for fast event-based communication, used for software-controlled conflict detection; and 2) support for programmable data isolation, allowing multiple concurrent transactional readers and writers at the software's behest, along with fast data commit and abort support (using only a few cycles of completely local operation).Our results show that for common-case bounded transactions, the proposed hardware mechanisms eliminate data copying and dramatically reduce the overhead of bookkeeping and validation (resulting in a factor of 2 improvement in performance on average). Moreover, RTM shows good scalability as the number of threads is increased and graceful degradation in performance when transactions overflow available hardware support. Detecting conflicts eagerly (on first access) or lazily (at commit time), enabled by the ability to handle multiple concurrent transactional writers and readers, can result in differences in performance in either direction depending on the application access pattern (up to two orders of magnitude at 16 threads for one workload), demonstrating the need for policy flexibility.
Keywords: transactional memory; adaptive scheduling; data locality.
Software transactional memory systems enable a programmer to easily write concurrent data structures such as lists, trees, hashtables, and graphs, where non-conflicting operations proceed in parallel. Many of these structures take the abstract form of a dictionary, in which each transaction is associated with a search key. By regrouping transactions based on their keys, one may improve locality and reduce conflicts among parallel transactions.In this paper, we present an executor that partitions transactions among available processors. Our key-based adaptive partitioning monitors incoming transactions, estimates the probability distribution of their keys, and adaptively determines the (usually nonuniform) partitions. By comparing the adaptive partitioning with uniform partitioning and round-robin keyless partitioning on a 16-processor SunFire 6800 machine, we demonstrate that key-based adaptive partitioning significantly improves the throughput of fine-grained parallel operations on concurrent data structures.
Keywords: memory management; Java; collaborative systems; multi-programming.
Limiting the amount of memory available to a program can hamstring its performance, however in a garbage collected environment allowing too large of a heap size can also be detrimental. Because garbage collection will occasionally access the entire heap, having a significant amount of virtual memory becomes expensive. Determining the appropriate size for a program's heap is not only important, but difficult in light of various virtual machines, operating systems, and levels of multi-programming with which the program may be run.We present a model for program memory usage with which we can show how effective multi-programming is likely to be. In addition, we present an automated system for adding control at the program level that allows runtime adaptation of a program's heap size. The process is fully automatic and requires no extra coding on the part of programmers. We discuss two adaptive schemes: The first acts independently, and while performing competitively, the system behaves politely in a multi-programmed environment. The second scheme explicitly cooperates when multiple instances are running. Both schemes are evaluated in terms of their response time, throughput, and fairness.
Keywords: parallelization; speculation; unsafe optimization.
The use of multi-core, multi-processor machines is opening new opportunities for software speculation, where program code is speculatively executed to improve performance at the additional cost of monitoring and error recovery. In this paper we describe a new system that uses software speculation to support unsafely optimized code. We open a fast, unsafe track of execution but run the correct code on other processors to ensure correctness. We have developed an analytical model to measure the effect of major parameters including the speed of the fast track, its success rate, and its overheads. We have implemented a prototype and verified the correctness and performance using a synthetic benchmark on a 4-CPU machine.
Keywords: program locality; memory hierarchy management; reuse distance; data layout.
The data layout of a program is critical to performance because it determines the spatial locality of the data access. Most quantitative notions of spatial locality are based on the overall miss rate and leave three questions not fully answered: how much can the locality of a given data layout be improved, can a data layout be improved if the miss rate cannot be lowered, and can the overall spatial locality be decomposed into smaller components? This paper describes a new definition of spatial locality that addresses these questions. The model is based on off-line profiling of a sequential execution. It has been used to analyze the spatial locality of 14 SPEC2000 benchmarks.
Keywords: parallelization; partial information; programmable software speculation; program behavior.
Many sequential applications are difficult to parallelize because of problems such as unpredictable data access, input-dependent parallelism, and custom memory management. These difficulties led us to build a system for behavior-oriented parallelization (BOP), which allows a program to be parallelized based on partial information about program behavior, for example, a user reading just part of the source code, or a profiling tool examining merely one or few inputs.The basis of BOP is programmable software speculation, where a user or an analysis tool marks possibly parallel regions in the code, and the run-time system executes these regions speculatively. It is imperative to protect the entire address space during speculation. The main goal of the paper is to demonstrate that the general protection can be made cost effective by three novel techniques: programmable speculation, critical-path minimization, and valuebased correctness checking. On a recently acquired multi-core, multi-processor PC, the BOP system improved the whole-program performance by integer factors for a Lisp interpreter, a data compressor, a language parser, and a scientific library.
Keywords: locality; reuse distance histogram; approximation; trace generator; time distance histogram.
Locality increasingly determines system performance. As a rigorous and precise locality model, reuse distance has been used in program optimizations, performance prediction, memory disambiguation and locality phase prediction. However, the high cost of measurement has been severely impeding its uses in scenarios requiring high ef ciency, e.g. product compilers, performance debugging, and run-time optimizations.This work proposes a statistical model to approximate reuse distance histograms from easily-obtained time distance histograms. The model makes reuse distance measurement as light as measuring data access frequency. Compared to the state-of-the-art technique, this model reduces measurement overhead by 17 times on ten SPEC CPU2000 ref executions and achieves over 99% accuracy for cache reuse approximation. Furthermore, this paper presents a trace generator, which produces data access traces from a given reuse distance histogram. It is bene cial for comprehensive evaluation of the approximation technique and can serve as a general tool for other locality studies.
Keywords: locality; reuse distance; approximation; time distance.
Locality, characterized by data reuses, determines caching performance. Reuse distance (i.e. LRU stack distance) precisely characterizes program locality and has been used in memory-related research since 1970s. However, the high cost of measuring it still urges a breakthrough before its practical uses in performance debugging, locality analysis and optimizations of long-running applications.In this work, we improve the efficiency by exploring the connection between time and locality. We propose a statistical model converting cheap time distance to costly reuse distance. Compared to the state-of-the-art technique, this approach reduces measuring time by 17 times, and approximates cache line reuses with over 99% accuracy. Experiments demonstrate the effective uses of the approximated reuse distance in cache miss rate prediction. This work, for the first time, reveals the strong correlations between time and locality. It makes precise locality as easy to obtain as data access frequency, removes the obstacles to reuse distance's practical uses, and opens new opportunities for program optimizations.
Keywords: nonblocking synchronization; transactional memory; storage management; RSTM.
Recent years have seen the development of several different systems for software transactional memory (STM). Most either employ locks in the underlying implementation or depend on thread-safe general-purpose garbage collection to collect stale data and metadata. We consider the design of low-overhead, obstruction-free software transactional memory for non-garbage-collected languages. Our design eliminates dynamic allocation of transactional metadata and co-locates data that are separate in other systems, thereby reducing the expected number of cache misses on the common-case code path, while preserving nonblocking progress and requiring no atomic instructions other than single-word load, store, and compare-and-swap (or load-linked/store-conditional). We also employ a simple, epoch-based storage management system and introduce a novel conservative mechanism to make reader transactions visible to writers without inducing additional metadata copying or dynamic allocation. Experimental results show throughput significantly higher than that of existing nonblocking STM systems, and highlight significant, application-specific differences among conflict detection and validation strategies.
Keywords: synchronization; transactional memory; policy and mechanism; TMESI; RTM; hardware/software interaction.
Transactional memory (TM) systems seek to increase scalability, reduce programming complexity, and overcome the various semantic problems associated with locks. Software TM proposals run on stock processors and provide substantial flexibility in policy, but incur significant overhead for data versioning and validation in the face of conflicting transactions. Hardware TM proposals have the advantage of speed, but are typically highly ambitious, embed significant amounts of policy in silicon, and provide no clear migration path for software that must also run on legacy machines.We advocate an intermediate approach, in which hardware is used to accelerate a TM implementation controlled fundamentally by software. We present a system, RTM, that embodies this approach. It consists of a novel transactional MESI (TMESI) protocol and accompanying TM software. TMESI eliminates the key overheads of data copying, garbage collection, and validation without introducing any global consensus algorithm in the cache coherence protocol, or any new bus transactions. The only change to the snooping interface is a "threatened" signal analogous to the existing "shared" signal.
By leaving policy to software, RTM allows us to experiment with a wide variety of policies for contention management, deadlock and livelock avoidance, data granularity, nesting, and virtualization.
Keywords: multiple core; active profiling; parallelization; utility programs; automatic parallelization; behavior phase.
With the fast development of multiple core processors, automatic parallelization becomes increasingly important. In this work, we focus on the parallelization of utility programs, a class of commonly used applications including compilers, transcoding utilities, file compressors, and databases. They take a series of requests as inputs and serve them one by one. Their high input dependence poses a challenge to analysis and optimization.We use active profiling to find behavior phase boundaries and then automatically detect dependences through profiling. Using a unified framework, we parallelize the programs at phase boundaries. We show that for two programs, the technique enables parallelization at large grainularity, which may span many loops and subroutines. The parallelized programs show significant speedup on both uniprocessor and multiple-processor machines.
Keywords: reuse signature; temporal locality; cache miss rate.
Since a program may have an infinite number of inputs, it is difficult to measure the exact performance under all possible uses. In this paper, we use the notion of reuse distance and reuse signature to measure the variation of data locality across program inputs. We use two classes of programs. The first is integer programs from SPEC 2000 benchmark set, including Vpr, Mcf, Parser, Perl, Gzip, and Bzip. For this set we test the current version from their open-source web sites instead of (or in addition to) the ones in the benchmark set. The second class is commonly used interactive programs, including Latex, Ghostview, and Gnuplot. We compare the reuse signature of 126 inputs for these 9 programs and show different degrees of locality variation. For most programs, the reuse signature is mostly consistent across inputs, indicating that the reuse pattern can be exploited in system design and optimization.
Keywords: nonblocking synchronization; scalability; obstruction freedom; wait freedom; contention management; design tradeoffs; software transactional memory.
Software Transactional Memory (STM) is a generic synchronization construct that enables automatic conversion of correct sequential objects into correct nonblocking concurrent objects. Recent STM systems, though significantly more practical than their predecessors, display inconsistent performance: differing design decisions cause different systems to perform best in different circumstances, often by dramatic margins. In this paper we consider four dimensions of the STM design space: (i) when concurrent objects are acquired by transactions for modification; (ii) how they are acquired; (iii) what they look like when not acquired; and (iv) the non-blocking semantics for transactions (lock-freedom vs. obstruction-freedom). In this 4-dimensional space we highlight the locations of two leading STM systems: the DSTM of Herlihy et al. and the OSTM of Fraser and Harris. Drawing motivation from the performance of a series of application benchmarks, we then present a new Adaptive STM (ASTM) system that adjusts to the offered workload, allowing it to match the performance of the best known existing system on every tested workload.
Keywords: non-blocking synchronization; timeout; user-level spin locks; scalability; preemption tolerance; published timestamp heuristic; CLH; MCS; abortable spin locks; microbenchmark; scheduler interface.
The proliferation of multiprocessor servers and multithreaded applications has increased the demand for high-performance synchronization. Traditional scheduler-based locks incur the overhead of a full context switch between threads and are thus unacceptably slow for many applications. Spin locks offer low overhead, but they either scale poorly on large-scale SMPs (test-and-set style locks) or behave poorly in the presence of preemption (queue-based locks).Previous work has shown how to build preemption-tolerant locks using an extended kernel interface, but such locks are neither portable to nor even compatible with most operating systems.
In this work, we propose a time-publishing heuristic in which each thread periodically records its current timestamp to a shared memory location. Given the high resolution, roughly synchronized clocks of modern processors, this convention allows threads to guess accurately which peers are active based on the currency of their timestamps. We implement two queue-based locks, MCS-TP and CLH-TP, and evaluate their performance relative to both traditional spin locks and preemption-safe locks on a 32-processor IBM p690 multiprocessor. Experimental results indicate that time-published locks make it feasible, for the first time, to use queue-based spin locks on multiprogrammed systems with a standard kernel interface.
Keywords: multicore architectures; clusters; caches; multithreading; adaptive coherence protocols; shared memory; parallel applications.
The design of the memory hierarchy in a multi-core architecture is a critical component since it must meet the capacity (in terms of bandwidth and low latency) and coordination requirements of multiple threads of control. Most previous designs have assumed either a shared L1 data cache (e.g., simultaneous multithreaded architectures) or L1 caches that are private to each individual processor (e.g., chip multiprocessors (CMPs)) with coherence maintained across the L1s at the L2 level. A shared L1 cache has the benefit of potentially increasing cache capacity for threads with non-uniform working sets but the disadvantage of higher access latency from remote clusters/cores and the potential for conflicts among threads. Private caches have the benefit of lower L1 access latency but the disadvantages of reduced effective cache size and of coherence overhead.In this paper, we focus on the design of the L1 cache as being a critical design component especially for multithreaded/parallel workloads. We identify the factors contributing to reduced performance, and examine ways in which each factor---locality of access, capacity, as well as migratory, multiple-reader, and read-write sharing patterns---can be addressed in a low-overhead fashion. We demonstrate that direct access to remote L1 cache banks provides the flexibility to address thread-specific capacity issues as well as to provide improved sharing support for active read-write sharing. We propose a novel selectively replicating (SR) adaptive protocol to handle locality and capacity issues in addition to recognizing and adapting to migratory, multiple-reader, and read-write sharing access patterns. The SR cache design is able to meet or beat the performance of the coherent cache, improving performance by up to 44% relative to a coherent cache (with an average of 5% across all applications) when using 8 threads.
Keywords: program analysis; garbage collection; phase; leak detection; gated memory control.
In the past, program monitoring often operates at the code level, performing checks at function and loop boundaries. Recent research shows that profiling analysis can identify high-level phases in complex binary code. Examples are time steps in scientific simulations and service cycles in utility programs. Because of their larger size and more predictable behavior, program phases make it possible for more accurate and longer term predictions of program behavior, especially its memory usage. This paper describes a new approach that uses phase boundaries as the gates to monitor and control the memory usage. In particular, it presents three techniques: memory usage monitoring, object lifetime classification, and preventive memory management. They use phase-level patterns to predict the trend of the program's memory demand, identify and control memory leaks, improve the efficiency of garbage collection. The potential of the new techniques is demonstrated on two non-trivial applications---a C compiler and a Lisp interpreter.
Keywords: phase detection; program characterization; frequency-based filtering; service-oriented programs.
The behavior of service-oriented programs depends strongly on the input. A compiler, for example, behaves differently when compiling different functions. Similar input dependences can be seen in interpreters, compression and encoding utilities, databases, and dynamic content servers. Because their behavior is hard to predict, these programs pose a special challenge for dynamic adaptation mechanisms, which attempt to enhance performance by modifying hardware or software to fit application needs.We present a new technique to detect phases---periods of distinctive behavior---in service-oriented programs. We begin by using special inputs to induce a repeating pattern of behavior. We then employ frequency-based filtering on basic block traces to detect both top-level and second-level repetitions, which we mark via binary rewriting. When the instrumented program runs, on arbitrary input, the inserted markers divide execution into phases of varying length. Experiments with service-oriented programs from the Spec95 and Spec2K benchmark suites indicate that program behavior within phases is surprisingly predictable in many (though not all) cases. This in turn suggests that dynamic adaptation, either in hardware or in software, may be applicable to a wider class of programs than previously believed.
Keywords: reference affinity; trace; N-body simulation; search tree; hierarchical data placement.
To fully utilize the hierarchical memory on modern machines, hierarchical data placement reorganizes program data in many layers of data blocks, which exploit data locality at all memory levels. Manually designed methods have been used in at least three important application domains---matrix operations, N-body simulation, and search trees---by different research groups using very different data layouts. This paper presents a new method for hierarchical data placement. The method is based on the reference affinity model, which captures the temporal pattern in program computation and converts it into the spatial relation in program data. The method is applicable to any sequential programs. It is polynomial time. It automatically gives the hierarchical data layout not only for cases reported by previous studies but also for other important problems. The new results reveal strong relations between computation and data and therefore should help to improve the management of data as well as the design of compilers and programming languages.
Keywords: memory management; competitive prefetching; data-intensive online server.
(This technical report also appeared in the First Workshop on Operating System and Architectural Support for the on demand IT InfraStructure (OASIS'04), Boston, MA, October 2004.)In a disk I/O-intensive online server, sequential data accesses of one application instance can be frequently interrupted by other concurrent processes. Although aggressive I/O prefetchiing can improve the granularity of sequential data access, it must control the I/O bandwidth wasted on prefetchiing unneeded data. In this paper, we propose a competitive prefetching strategy that balances the overhead of disk I/O switching and that of unnecessary prefetching. Based on a simple model, we show that the performance of our strategy (in terms of I/O throughput) is at least half that of the optimal offline policy. We have implemented competitive prefetching in the Linux 2.6.3 kernel and conducted experiments based on microbenchmarks and two real applications (an index searching server and the Apache Web server). Our evaluation results demonstrate that competitive prefetching can improve the throughput of real applications by 15%-47%. The improvement is achieved without any application assistance or changes.
Keywords: sequence data mining; reference affinity; sampling method; reuse distance.
Making better use of the cache is of great importance for the modern computer programs and systems. One key step is to understand the data locality. In this article, we investigate one effective and important model of data locality---reference affinity. This model is superior than the previous methods in that it can express the whole-scale locality in a more accurate and more flexible way. Traces collected from different applications are a rich source for the analysis of reference affinity. In this article, we extend the strict reference affinity to weak reference affinity and their properties are proved. We propose a sampling method to find reference affinity groups and present experimental results based on synthetic data showing that the new method is more scalable and accurate than the state-of-the-art method proposed by Zhong et al. (2004).
Keywords: nonblocking synchronization; scalability; obstruction freedom; wait freedom; contention management; design tradeoffs; software transactional memory.
Software Transactional Memory (STM) can be defined as a generic nonblocking synchronization construct that allows correct sequential objects to be converted automatically into correct concurrent objects. In STM, a transaction is defined as a sequence of instructions that atomically modifies a set of concurrent objects. The original STM proposed by Shavit and Touitou worked on static transactions (wherein the concurrent objects being accessed by a transaction were pre-determined). Recent STM research has focused on support for more realistic dynamic transactions.In this paper we present a qualitative survey of modern STM systems that support dynamic transactions. More concretely, we describe the designs of three STM systems---a hash table based STM system (Hash table STM) for shared memory words due to Harris and Fraser, and two purely object-based STM systems, one due to Herlihy et al., the other due to Fraser. We also present a detailed analysis of the Hash table STM and a qualitative comparison between the two object-based STM systems. We identify a scalability drawback (that may be unacceptable in some applications) in the Hash table STM and propose an LL/SC based variant that overcomes this drawback. The qualitative comparison between the two object-based STM systems helps us understand their various design peculiarities and the potential tradeoffs involved. Specifically, we discuss object ownership acquire semantics, levels of indirection to access concurrent objects, space utilization, transaction search overhead during conflict resolution, transaction validation semantics, and contention management versus helping.
Keywords: large-scale storage systems; energy efficiency; power efficient disk arrays.
The disk array of a server-class system can account for a significant portion of the serverUs total power budget. Similar observations for mobile (e.g., laptop) systems have led to the development of power management policies that spin down the hard disk when it is idle, but these policies do not transfer well to server-class disks. On the other hand, state-of-the-art laptop disks have response times and bandwidths within a factor of 2.5 of their server class cousins, and consume less than one sixth the energy. These ratios suggest the possibility of replacing a server-class disk array with a larger array of mirrored laptop disks. By spinning up a subset of the disks proportional to the current workload, we can exploit the latency tolerance and parallelism of typical server workloads to achieve significant energy savings, with equal or better peak bandwidth. Potential savings range from 50% to 80% of the total disk energy consumption.
Keywords: microprocessor architecture; frequency and voltage scaling; complexity adaptive processing (CAP); accounting cache; multiple clock domain (MCD) microarchitecture.
Microprocessors are traditionally designed to provide "best overall" performance across a wide range of applications and operating environments. Several groups have proposed hardware techniques that save energy by "downsizing" hardware resources that are underutilized by the current application. We explore the converse: improving performance by "upsizing" resources for which the application has greater needs. Our proposal depends critically on the ability to change frequencies independently in separate domains of a globally asynchronous, locally synchronous (GALS) microprocessor.We use a variant of a multiple clock domain (MCD) processor, with four independently clocked domains. Each domain is streamlined with modest hardware structures for very high clock frequency. Key structures can then be upsized on demand to exploit more distant parallelism, improve branch prediction, or increase cache capacity. Although doing so requires decreasing the associated domain frequency, other domain frequencies are unaffected. Measuring across a broad suite of application benchmarks, we find that configuring our MCD processor just once per application yields performance 17.6% better, on average, than that of the "best overall" fully synchronous design. By adapting automatically to application phases, we can increase this advantage to more than 20%.
Keywords: overlay networks; distributed hashtable; performance evaluation.
Internet overlay services must adapt to the substrate network topology and link properties to achieve high performance. A common overlay structure management layer is desirable for enhancing the architectural modularity of service design and deployment. Additionally, a shared substrate-aware overlay structure can potentially reduce redundant per-service link-selection probing when overlay nodes participate in multiple services. The concept of building services on a common structure management layer fits well with unstructured services, those that do not place specific requirements on the overlay connectivity structure (e.g., Gnutella).Despite the benefits, it is unclear how the distributed hashtable (DHT) service can take advantage of a service-independent structure management layer, considering recently proposed scalable DHT protocols all employ protocol-specific overlay structures. In this paper, we present the design of a self-organizing DHT protocol based on the Landmark Hierarchy. Coupled with a simple low-latency overlay structure management protocol, this approach can support low-latency DHT lookup without any service-specific requirement on the overlay structure. Compared with Chord, a well-known DHT protocol, simulations and experimentation on 51 PlanetLab sites find that the proposed scheme can deliver better lookup performance (reducing the lookup latency by almost half) under the same link density. This benefit is achieved at the cost of less balanced lookup routing overhead. Our evaluation also demonstrates that the balance of key placement and fault tolerance for the proposed scheme are close to those of Chord. However, our approach produces more key reassignments after overlay membership changes, due to its structure-sensitive DHT mapping scheme.
Keywords: heterogeneity; wide area; transactions; remote procedure calls; shared state.
Most distributed applications require, at least conceptually, some sort of shared state: information that is non-static but mostly read, and needed at more than one site. At the same time, RPC-based systems such as Sun RPC, Java RMI, CORBA, and .NET have become the de facto standards by which distributed applications communicate. As a result, shared state tends to be implemented either through the redundant transmission of deep-copy RPC parameters or through ad-hoc, application-specific caching and coherence protocols. The former option can waste large amounts of bandwidth; the latter significantly complicates program design and maintenance.To overcome these problems, we propose a distributed middleware system that works seamlessly with RPC-based systems, providing them with a global, persistent store that can be accessed using ordinary reads and writes. In an RPC-based program, shared state serves to (1) support genuine reference parameters in RPC calls, eliminating the need to pass large structures repeatedly by value, or to recursively expand pointer-rich data structures using deep-copy parameter modes; (2) eliminate invocations devoted to maintaining the coherence and consistency of cached data; (3) reduce the number of trivial invocations used simply to put or get data. Relaxed coherence models and aggressive protocol optimizations reduce the bandwidth required to maintain shared state. Integrated support for transactions allows a chain of RPC calls to update that state atomically.
We focus in this paper on the implementation challenges involved in combining RPC with shared state, relaxed coherence, and transactions. In particular, we describe a transaction metadata table that allows processes inside a transaction to share data invisible to other processes and to exchange data modifications efficiently. Using microbenchmark and large-scale datamining applications, we demonstrate how the integration of RPC, transactions, and shared state facilitates the rapid development of robust, maintainable code.
Keywords: reuse distance; reuse signature; program analysis; visualization.
Making use of information on cache performance requires a quick way to comprehend how the miss rate for an application changes as cache and input size varies. In 1970, Mattson et al. showed how to measure miss rates for all cache sizes. Recently, Zhong et al. showed how to predict miss rates for all program input data sizes. This paper builds on the previous results and shows the miss rate of a program as a function over the domain with cache and data input size as two orthogonal dimensions. This paper makes three contributions. First, it presents an interactive tool that visualizes the miss rates in three-dimensional plots. It measures the compounded error of prediction for different cache sizes for program inputs that are never ran let along simulated on a cache simulator. Second, it applies predictions to a new set of benchmark programs with dynamic data structures. Finally, it discusses possible uses of the new tool. Experiments show that the compounded prediction error for the hit rate is within 6.5% for caches of all sizes and with a small amount of associativity. The visualization tool can run on any machine with Java 3D. It can be downloaded from http://www.cs.rochester.edu/research/locality.
Keywords: program optimization; program transformation; cache optimization; program locality; reuse distance; reuse signature; reference affinity .
While the memory of most machines is organized as a hierarchy, program data are laid out in a uniform address space. This paper defines a model of reference affinity, which measures how close a group of data are accessed together in a reference trace. It proves that the model gives a hierarchical partition of program data. At the top is the set of all data with the weakest affinity. At the bottom is each data element with the strongest affinity. Based on the theoretical model, the paper presents k-distance analysis, a practical test for the hierarchical affinity of source-level data. When used for array regrouping and structure splitting, k-distance analysis consistently outperforms data organizations given by the programmer, compiler analysis, frequency profiling, statistical clustering, and all other methods we have tried.
Keywords: phase detection; phase prediction; data locality; reuse distance; wavelet; shortest path; hierarchical phase.
Computer memory hierarchy becomes increasingly powerful but also more complex to optimize. Run-time adaptation emerges as a promising strategy. For software, it means adjusting data behavior at different phases of an execution. For hardware, it means reconfiguring the memory system at different times.This paper presents a method that predicts the memory phases of a program when it runs. The analysis first detects memory phases in a profiling run using variable-distance sampling, wavelet filtering, and optimal phase partition. It then identifies the phase hierarchy through grammar compression. Finally, it inserts phase markers into a program through binary rewriting. The technique is a unique combination of locality profiling and phase prediction.
The new method is tested on a wide range of programs against programmer manual analysis and pure hardware monitoring. It predicts program executions that are thousands of times longer than profiling runs. The average length of the predicted phases is over 700 million instructions, and the length is predicted with 99.5% accuracy. When tested for cache adaptation, it reduces the cache size by 40% without increasing the number of cache misses. These results suggest that phase prediction can significantly improve the many adaptation techniques now used for increasing performance, reducing energy, and other improvements to the computer system design.
Keywords: sorting; parallel sorting; data partitioning; adaptive partitioning; probability distribution.
Many computing problems benefit from dynamic data partitioning--- dividing a large amount of data into smaller chunks with better locality. When data can be sorted, two methods are commonly used in partitioning. The first selects pivots, which enable balanced partitioning but cause a large overhead of up to half of the sorting time. The second method uses simple functions, which is fast but requires that the input data confirm to a uniform distribution. In this paper, we propose a new method, which partitions data using the cumulative distribution function. It partitions data of any distribution in linear time, independent of the number of sublists to be partitioned into. Experiments show 10-30% improvement in partitioning balance and 20-70% reduction in partitioning overhead. The new method is more scalable than existing methods. It yields greater benefit when the data set and the number of sub-lists grow larger. By applying this method, our sequential sorting beats Quick-sorting by 20% and parallel sorting exceeds the previous sorting algorithm by 33-50%.
Keywords: program balance; multi-clock domain processor; simulation and performance evaluation; loop fusion.
Loop fusion combines corresponding iterations of different loops. As shown in previous work, it can often decrease program run time by reducing the overhead of loop control and effective address calculations, and in important cases by dramatically increasing cache or register reuse. In this paper we consider corresponding changes in program energy.By merging program phases, fusion tends to increase the uniformity, or balance of demand for system resources. On a conventional superscalar processor, increased balance tends to increase IPC, and thus dynamic power, so that fusion-induced improvements in program energy are slightly smaller than improvements in program run time. If IPC is held constant, however, by reducing frequency and voltage--- particularly on a processor with multiple clock domains---then energy improvements may significantly exceed run time improvements.
We demonstrate the benefits of increased program balance under a theoretical model of processor energy consumption. We then evaluate the benefits of fusion empirically on synthetic and real-world benchmarks, using our existing loop-fusing compiler, and running on a heavily modified version of the SimpleScalar/Wattch simulator. In addition to validating our theoretical model, the simulation results allow us to "tease apart" the various factors that contribute to fusion-induced time and energy savings.
Keywords: high-performance microprocessors; low-power microarchitectures; memory hierarchy bottlenecks; data caches; register files; clustered processors.
Improvements in technology have resulted in steadily improving microprocessor performance. However, the shrinking of process technologies and increasing clock speeds introduce new bottlenecks to performance, viz, long wire delays on the chip and long memory latencies. We observe a number of trade-offs in the design of various microprocessor structures and the gap between the different trade-off points only widens as technologies improve and latencies of wires and memory increase. The emergence of power as a first-order design constraint also introduces trade-offs involving performance and power consumption. Microprocessor designs are optimized to balance these trade-offs in the average case, but are highly sub-optimal for most programs that run on the processor. The dissertation evaluates hardware reconfiguration as a means to providing a program with multiple trade-off points, thereby allowing the hardware to match the program's needs at run-time. In all cases, hardware reconfiguration exploits technology trends and is relatively non-intrusive.We examine a reconfigurable cache layout that varies the L1 data cache size and helps handle the trade-off between cache capacity and access time. We also study a highly clustered and communication-bound processor, where a subset of the total clusters yields optimal performance by balancing the extraction of distant parallelism with the inter-cluster communication costs. In a processor with limited resources, distant parallelism can be mined with the help of a pre-execution thread and the allocation of resources between the primary and pre-execution thread determines the trade-off between nearby and distant parallelism. In all of these cases, the dynamic management of on-chip resources can balance the different trade-offs. We propose and evaluate dynamic adaptation algorithms that detect changes in program behavior and select optimal hardware configurations. Our results demonstrate that the adaptation algorithms are very effective in adapting to changes in program behavior, allowing improved processor efficiency through hardware reconfiguration. Performance is improved and power consumption is reduced when compared with a static hardware design.
Keywords: overlay networks; distributed systems.
(This technical report is superceded by a 2004 NSDI paper titled "Structure Management for Scalable Overlay Service Construction," which can be accessed via the link.)Internet overlay services may exhibit poor performance when their designs ignore the topology and link properties of the underlying Internet substrate. Various service-specific techniques have been proposed to select good overlay links and thus enhance the performance. In this paper, we explore the model of providing a substrate-aware overlay structure management layer to assist the construction of large-scale wide-area Internet services. To this end, we propose Saxons, a distributed software layer that dynamically maintains an efficient mesh structure connecting overlay nodes. Saxons provides connectivity support with three performance goals: low overlay latency, low hop-count distance, and high overlay bandwidth. Services built on top of this layer can utilize the mesh structure while achieving high performance. Furthermore, Saxons targets large-scale self-organizing services which adds scalability and stability requirements into our design. This paper describes the design of Saxons and services that can take advantage of it. Our simulation-based evaluations demonstrate Saxons' effectiveness in terms of structure quality, stability, and overlay connectivity. To illustrate the usage of Saxons, this paper also presents the design of a Saxons-based high-bandwidth overlay route discovery service.
Keywords: wireless communication; sensor networks; middleware; distributed computing.
Current trends in computing include increases in both distribution and wireless connectivity, leading to highly dynamic, complex environments on top of which applications must be built. The task of designing and ensuring the correctness of applications in these environments is similarly becoming more complex. The unified goal of much of the research in distributed wireless systems is to provide higher level abstractions of complex low-level concepts to application programmers, easing the design and implementation of applications. This is also the goal of the proposed Milan middleware platform, but Milan's unique feature is its ability to continuously control the network functionality with respect to the application's changing demands.Applications targeted by Milan are characterized by their ability to adapt to changing sets of available components, and their need to further constrain the active components for application-performance reasons. Physical resources (e.g., transmission distance, bandwidth) and minimum application performance limit the input to certain subsets of available components. It is the job of Milan to identify these feasible sets and determine which set optimizes the tradeoff between application performance and network cost (e.g., energy dissipation). Milan must then configure the network so that components in the selected feasible set are linked to the application. A key feature of Milan is the separation of the policy for managing the network, which is defined by the application, from the mechanisms for implementing the policy, which is effected within Milan. This report describes the initial design of Milan as well as our plans for future research.
Keywords: disk scheduling; spin-down; prefetching; disk update policy; write-back; energy efficiency.
Hard disks for portable devices, and the operating systems that manage them, incorporate spin-down policies that idle the disk after a certain period of inactivity. In essence, these policies use a recent period of inactivity to predict that the disk will remain inactive in the near future. We propose an alternative strategy, in which the operating system deliberately seeks to cluster disk operations in time, to maximize the utilization of the disk when it is spun up and the time that the disk can be spun down. In order to cluster disk operations we postpone the service of non-urgent operations, and use aggressive prefetching and file prediction to reduce the likelihood that synchronous reads will have to go to disk. In addition, we present a novel predictive spin-down/spin-up policy that exploits high level operating system knowledge to decrease disk idle time prior to spin-down, and application wait time due to spin-up. We evaluate our strategy through trace-driven simulation of several different workload scenarios. Our results indicate that the deliberate creation of bursty activity can save up to 55% of the energy consumed by an IBM TravelStar disk, while simultaneously decreasing significantly the negative impact of disk spin-up latency on application performance.
Keywords: parallel algorithm; bayesian phylogenetic inference; Metropolis-coupled Markov Chain Monte Carlo; message passing interface; software distributed shared memory.
Bayesian estimation of phylogeny is based on the posterior probability distribution of trees. Currently, the only numerical method that can effectively approximate posterior probabilities of trees is Markov Chain Monte Carlo (MCMC). Standard implementations of MCMC can be prone to entrapment in local optima. A variant of MCMC, known as Metropolis-Coupled MCMC, allows multiple peaks in the landscape of trees to be more readily explored, but at the cost of increased execution time. This paper presents a parallel algorithm for Metropolis-Coupled MCMC. The proposed parallel algorithm retains the ability to explore multiple peaks in the posterior distribution of trees while maintaining a fast execution time. The algorithm has been implemented using two parallel programming models: the Message Passing Interface (MPI) and the Cashmere software distributed shared memory protocol. Performance results indicate nearly linear speed improvement in both programming models for small and large data sets. (MrBayes v3.0 is available at http://morphbank.ebc.uu.se/mrbayes/.)
Keywords: relaxed coherence; consistency; software-distributed shared memory; heterogeneity; middleware; distributed systems.
InterWeave is a distributed middleware system that supports the sharing of strongly typed, pointer-rich data structures across heterogeneous platforms. Unlike RPC-style systems (including DCOM, CORBA, Java RMI), InterWeave does not require processes to employ a procedural interface: it allows them to access shared data using ordinary reads and writes. To save bandwidth in wide area networks, InterWeave caches data locally, and employs two-way diffing to maintain coherence and consistency, transmitting only the portions of the data that have changed.In this paper, we focus on the aspects of InterWeave specifically designed to accommodate heterogeneous machine architectures and languages. Central to our approach is a strongly typed, platform-independent wire format for diffs, and a set of algorithms and metadata structures that support translation between local and wire formats. Using a combination of microbenchmarks and real applications, we evaluate the performance of our heterogeneity mechanisms, and compare them to comparable mechanisms in RPC-style systems. When transmitting entire segments, InterWeave achieves performance comparable to that of RPC, while providing a more flexible programming model. When only a portion of a segment has changed, InterWeaveUs use of diffs allows it to scale its overhead down, significantly outperforming straightforward use of RPC.
Keywords: pervasive computing; Java virtual machines; garbage collection; distributed system; memory management.
Our everyday life is becoming increasingly filled with computing devices. Among them, mobile and embedded devices usually have far more limited resource specifications than wired and consequently more powerful computing devices. In order to increase available software on mobile devices it is beneficial to reuse existing software platforms or applications. Conventional wisdom has been to trim down current software to fit them into smaller devices. However, we believe that when surrounded by other computer resources there is an alternative solution for certain resource, in which resource limited devices can utilize those resources by dynamically offloading services.In this paper, we examine the use of "memory offloading" as a means of relieving memory constraints in Java environments. Our experiments we have found that using virtual memory to relieve resource constraints from JVMs can lead to very bad performance due to Java's garbage collector. We propose extending the garbage collector of a JVM we allow it to take into account the semantics of Java memory usage to provide efficient and transparent memory offloading. Our results using a modified JVM show that with moderate monitoring overhead, both migration policies investigated can achieve a 85\% reduction in bandwidth requirement and even more in necessary number of messages for most of application benchmarks we used.
Keywords: energy efficient microprocessor; dynamic; cache; reorder buffer; issue queue; register file; Accounting Cache.
Energy efficiency in microarchitectures has become a necessity. Significant dynamic energy savings can be realized for adaptive storage structures such as caches, issue queues, and register files by disabling unnecessary storage resources. Prior studies have analyzed individual structures and their control. A common theme to these studies is exploration of the configuration space and use of system IPC as feedback to guide reconfiguration choices. However, in a system where multiple structures adapt in concert, the number of possible configurations increases dramatically, and assigning causal effects to IPC change becomes problematic. To overcome this issue, we introduce designs for these adaptive structures that make reconfiguration decisions based solely on local behavior. We introduce a novel cache design, the Accounting Cache, that permits direct calculation of optimal configurations. For buffer and queue structures, we demonstrate how limited histogramming permits fast and precise resizing control. When using these designs for all levels of the instruction and data caches, the issue queue, reorder buffer, and register file, we show energy savings of up to 70% on the individual structures, and savings averaging 30% overall for the portion of energy attributed to the adaptive structures with an average of 1.2% performance degradation.
Keywords: non-blocking synchronization; timeout; user-level spin locks; preemption; scalability.
Queue-based spin locks allow programs with busy-wait synchronization to scale to very large multiprocessors, without fear of starvation or performance-destroying contention. Timeout-capable spin locks allow a thread to abandon its attempt to acquire a lock; they are used widely in real-time systems to avoid overshooting a deadline, and in database systems to recover from transaction deadlock and to tolerate preemption of the thread that holds a lock. In previous work we showed how to incorporate timeout in scalable queue-based locks. Technological trends suggest that this combination will be of increasing commercial importance. Our previous solutions, however, require a thread that is timing out to handshake with its neighbors in the queue, a requirement that may lead to indefinite delay in a preemptively multiprogrammed system. In the current paper we present new queue-based locks in which the timeout code is non-blocking. These locks sacrifice the constant worst-case space per thread of our previous algorithms, but allow us to bound the time that a thread may be delayed by preemption of its peers. We present empirical results indicating that space needs are modest in practice, and that performance scales well to large machines. We also argue that constant per-thread space cannot be guaranteed together with non-blocking timeout in a queue-based lock.
Keywords: high performance superscalar processors; clustered microarchitectures; decentralized data cache; on-chip multiprocessor.
Clustered microarchitectures are an attractive alternative to large monolithic superscalar designs due to their potential for higher clock rates in the face of increasingly wire-delay-constrained process technologies. In such a microarchitecture, the distribution of functional units, the register files, and the issue queues across multiple clusters reduces the latency of various cycle time critical paths, thereby enabling a faster clock. However, a penalty in terms of instructions per cycle is incurred if instructions frequently communicate values among clusters because of dependences.In this paper, we propose several novel extensions that significantly improve the performance of clustered designs. First, we explore a word-interleaved clustered cache in which memory instructions are steered to clusters based on addresses, and when the effective address is unknown, directs memory operations to the appropriate cluster via bank prediction. We then study the scalability of the resulting clustered microarchitecture as the number of clusters is increased (resulting in a corresponding increase in inter-cluster communication latency). Our evaluation identifies the key bottlenecks and shows how novel enhancements to the cluster resource allocation mechanisms can significantly improve the scalability of the design. We also show that communication latency in a highly clustered processor can be reduced for certain programs by only using a subset of the clusters. Overall, these enhancements achieve a 30% fill in the correct value improvement over a baseline design with the clustered cache.
Keywords: register file; dynamic superscalar processors; register renaming; register file cache.
Dynamic superscalar processors execute instructions out-of-order by looking for independent operations within a large window. The number of physical registers within the processor has a direct impact on the size of this window as most in-flight instructions are assigned a new physical register. A large register file helps improve the instruction-level parallelism (ILP), but has a detrimental effect on clock speed, especially at future technologies. In this paper, we propose a two-level register file organization, where the first level only contains values that potentially have active consumers in the pipeline. The second level contains those values that are going to be used only in the event of a branch mispredict or an exception, and has minimal port requirements. Adding the second level shows overall speedups of 1.22, 1.06, and 1.19 relative to an architecture without a second-level cache for three different processor models for a varied benchmark set. A small first-level register file supported by a second-level register file can support as much ILP as a much larger single-level register file, thus having favorable implications for clock speed and power.
Keywords: relaxed coherence; consistency; software-distributed shared memory; heterogeneity; loosely-coupled distributed systems.
InterWeave is a distributed middleware system that attempts to do for computer programs what the World Wide Web did for human beings: make it dramatically simpler to share information across the Internet. Specifically, InterWeave allows processes written in multiple languages, running on heterogeneous machines, to share arbitrary typed data structures as if they resided in local memory. In C, operations on shared data, including pointers, take precisely the same form as operations on non-shared data. Sharing at all levels is supported seamlessly---InterWeave can accommodate hardware coherence and consistency within multiprocessors (level-1 sharing), software distributed shared memory (SDSM) within tightly coupled clusters (level-2 sharing), and version-based coherence and consistency across the Internet (level-3 sharing). Application-specific knowledge of minimal coherence requirements is used to minimize communication. Consistency information is maintained in a manner that allows scaling to large amounts of shared data.We discuss the implementation of InterWeave in some detail, with a particular emphasis on memory management; coherence and consistency; and communication and heterogeneity. We then evaluate the performance and usability of the system. Anecdotal evidence suggests that the InterWeave prototype significantly simplifies the construction of important distributed applications. Quantitative evidence demonstrates that it achieves this simplification at acceptably modest cost.
Keywords: pre-execution; prefetch; branch mispredict recovery; instruction reuse; dynamic superscalar procesesors; instruction-level parallelism (ILP).
Modern superscalar processors use wide instruction issue widths and out-of-order execution in order to increase instruction-level parallelism (ILP). Since instructions must be committed in order so as to guarantee precise exceptions, increasing ILP implies increasing the sizes of structures such as the register file, issue queue, and reorder buffer. Simultaneously, cycle time constraints limit the size of these structures, resulting in conflicting design requirements.In this paper, we present a novel microarchitecture designed to overcome the limitations of a register file size dictated by cycle time constraints. Available registers are dynamically allocated between the primary program thread and a future thread. The future thread issues and executes instructions when the primary thread is limited by resource availability. The future thread is not constrained by in-order commit requirements. It is therefore able to examine a much larger instruction window and jump far ahead to execute ready instructions. Results are communicated back to the primary thread by warming up the register file, instruction cache, data cache, and instruction reuse buffer, and by resolving branch mispredicts early. The proposed microarchitecture is able to get an overall speedup of 1.17 over the base processor for our benchmark set, with speedups of up to 1.64.
Queue-based spin locks allow programs with busy-wait synchronization to scale to very large multiprocessors, without fear of starvation or performance-destroying contention. So-called try locks, traditionally based on non-scalable test-and-set locks, allow a process to abandon its attempt to acquire a lock after a given amount of time. The process can then pursue an alternative code path, or yield the processor to some other process.We demonstrate that it is possible to obtain both scalability and bounded waiting, using variants of the queue-based locks of Craig, Landin, and Hagersten, and of Mellor-Crummey and Scott. A process that decides to stop waiting for one of these new locks can "link itself out of line" atomically. Single-processor experiments reveal performance penalties of 50-100% for the CLH and MCS try locks in comparison to their standard versions; this marginal cost decreases with larger numbers of processors.
We have also compared our queue-based locks to a traditional test-and-test_and_set lock with exponential backoff and timeout. At modest (non-zero) levels of contention, the queued locks sacrifice cache locality for fairness, resulting in a worst-case 3X performance penalty. At high levels of contention, however, they display a 1.5-2X performance advantage, with significantly more regular timings and significantly higher rates of acquisition prior to timeout.
Keywords: cache analysis; reuse distance; instrumentation; performance.
Cache is one of the most widely used components in today's computing systems. Its performance is heavily depended on the locality in programs. Till now, the analysis of program locality relies on expensive cache simulation. As machine cache becomes increasingly complex and adaptive, more efficient and accurate methods are needed to find the best cache configuration for each program or even each part of the program. In this report, we measure program locality directly by the distance between the reuses of its data. Data reuse is an inherent program property and does not depend on any cache parameters. Therefore, it allows quantitative measurement of program locality that is not tied to any particular machine. To measure reuse distance, we describe a new method consisting of two components. The first performs fast analysis for full applications accessing large data sets, and the second ascribes the simulation result to source-level data structures at fine granularity. With this tool, we analyze data reuse behavior in a set of benchmark applications and present main findings about their program locality.
Keywords: instruction balance; energy consumption; software-hardware co-optimization.
A computer consists of multiple components such as functional units, cache and main memory. At each moment of execution, a program may have a varied amount of work for each component. Recent development has exploited this imbalance to save energy by slowing the components that have a lower load. Example techniques include dynamic scaling and clock gating used in processors from Transmeta and Intel. Symmetrical to reconfiguring hardware is reorganizing software. We can alter program demand for different components by reordering program instructions. This paper explores the theoretical lower bound of energy consumption assuming that both a program and a machine are fully adjustable. It shows that a program with a balanced load always consumes less energy than the same program with uneven loads under the same execution speed. In addition, the paper examines the relation between energy consumption and program performance. It shows that reducing power is a different problem than that of improving performance. Finally, the paper presents empirical evidence showing that a program may be transformed to have a balanced demand in most parts of its execution.
Keywords: software distributed shared memory; symmetric multiprocessors; system area networks; virtual memory-based coherence.
Cashmere is a software distributed shared memory (SDSM) system designed for today's high-performance cluster architectures. These clusters typically consist of symmetric multiprocessors (SMPs) connected by a low-latency system area network. Cashmere introduces several novel techniques for delegating intra-node sharing to the hardware coherence mechanism available within the SMPs, and also for leveraging advanced network features such as remote memory access. The efficacy of the Cashmere design has been borne out through head-to-head comparisons with other well-known, mature SDSMs and with Cashmere variants that do not take advantage of the various hardware features.In this paper, we describe the implementation of the Cashmere SDSM. Our discussion is organized around the core components that comprise Cashmere. We discuss both component interactions and low-level implementation details. We hope this paper provides researchers with the background needed to modify and extend the Cashmere system.
Emerging system-area networks provide a variety of features that can dramatically reduce network communication overhead. Such features include reduced latency, protected remote memory access, cheap broadcast, and ordering guarantees. In this paper, we evaluate the impact of these features on the implementation of Software Distributed Shared Memory (SDSM), and on the Cashmere system in particular. Cashmere has been implemented on the Compaq Memory Channel network, which supports remote memory writes, inexpensive broadcast, and total ordering of network packets.We evaluate the performance impact of these special network features on the three kinds of SDSM protocol communication: shared data propagation, protocol meta-data maintenance, and synchronization, using an 8-node, 32-processor system. Among other things, we compare our base protocol, which leverages all of Memory Channel's special features, to a protocol based solely on reliable point-to-point messages. We found that the special features improved performance by 18-44% for three of our applications, but less than 12% for our other seven applications. The message-based protocol has the added benefit of allowing shared memory size to grow beyond the addressing limits of the network interface. Moreover, it enables us to implement a home node migration optimization that sometimes more than offsets the advantages of the protocol that fully leverages the Memory Channel features, improving performance by as much as 67%. These results suggest that for systems of modest size, low latency is much more important for SDSM performance than are remote writes, broadcast, or total ordering. At the same time, results on an emulated 32-node system indicate that broadcast based on remote writes of widely-shared data may improve performance by up to 56% for some applications. If hardware broadcast or multicast facilities can be made to scale, they can be beneficial in future system-area networks.
Keywords: cache coherence; clusters; remote-memory-access networks; software distributed shared memory; symmetric multiprocessors.
Clusters of workstations have long provided a cost-effective, large-scale parallel computing platform. A Software Distributed Shared Memory (SDSM) system simplifies programming on these platforms by presenting the illusion of shared memory. SDSM performance has historically been limited by the high cost of inter-processor communication overhead. Recent hardware trends, such as commodity symmetric multiprocessors (SMPs) and system area networks, can be used to potentially lower this overhead.The Cashmere SDSM has been designed for clusters of SMPs connected by a low-latency, remote-memory-access system area network. Cashmere introduces several novel techniques to leverage SMP hardware coherence and also to exploit remote-memory-access and other special features found in today's emerging system area networks. The results of our prototype implementation show that the Cashmere design leads to an average improvement of 25% over a comparable protocol version that does not leverage the SMP hardware coherence. The results also isolate the performance impact of various network features, thereby providing network designers with an informative application study.
In addition, we have investigated the impact of these new hardware trends on the most fundamental aspect of SDSM design: the coherence granularity. Our findings show that recent hardware trends help reduce the performance gap between fine and coarse granularity SDSM. We also provide additional techniques for further reducing the gap.
Keywords: cluster computing; scalable web servers; locality.
In this paper we use analytic modeling and simulation to evaluate network servers implemented on clusters of workstations. More specifically, we model the potential benefits of locality-conscious request distribution within the cluster and evaluate the performance of a cluster-based server (called L2S) we designed in light of our experience with the model. Our most important modeling results show that locality-conscious distribution on a 16-node cluster can increase server throughput with respect to a locality-oblivious server by up to 7-fold, depending on the average size of the files requested and on the size of the server's working set. Our simulation results demonstrate that L2S achieves throughput that is within 22% of the full potential of locality-conscious distribution on 16 nodes, outperforming and significantly outscaling the best-known locality-conscious server. Based on our results and on the fact that the files serviced by network servers are becoming larger and more numerous, we conclude that our locality-conscious network server should prove very useful for its performance, scalability, and availability properties.
Although successive generations of middleware (such as RPC, CORBA, and DCOM) have made it easier to connect distributed programs, the process of distributed application decomposition has changed little: programmers manually divide applications into sub-programs and manually assign those sub-programs to machines. Often the techniques used to choose a distribution are ad hoc and create one-time solutions biased to a specific combination of users, machines, and networks.We assert that system software, not the programmer, should manage the task of distributed decomposition. To validate our assertion we present Coign, an automatic distributed partitioning system that significantly eases the development of distributed applications. Given an application (in binary form) built from distributable COM components, Coign constructs a graph model of the application's inter-component communication through scenario- ased profiling. Later Coign applies a graph-cutting algorithm to partition the application across a network and minimize execution delay due to network communication. Using Coign, even an end user (without access to source code) can transform a non-distributed application into an optimized, distributed application.
Coign has automatically distributed binaries from over 2 million lines of application code, including Microsoft's PhotoDraw 2000 image processor. To our knowledge, Coign is the first system to automatically partition and distribute binary applications.
Keywords: software distributed shared memory; remote-memory-access networks.
Emerging system-area networks provide a variety of features that can dramatically reduce network communication overhead. Such features include reduced latency, protected remote memory access, cheap broadcast, and ordering guarantees. In this paper, we evaluate the impact of these features on the implementation of Software Distributed Shared Memory (SDSM), and on the Cashmere system in particular. Cashmere has been implemented on the Compaq Memory Channel network, which supports remote memory writes, inexpensive broadcast, and total ordering of network packets.We evaluate the performance impact of these special network features on the three kinds of SDSM protocol communication: shared data propagation, protocol meta-data maintenance, and synchronization, using an 8-node, 32-processor system. Among other things, we compare our base protocol, which leverages all of Memory Channel's special features, to a protocol based solely on reliable point-to-point messages. We found that the special features improved performance by 18-44% for three of our applications, but less than 12% for our other seven applications. The message-based protocol has the added benefit of allowing shared memory size to grow beyond the addressing limits of the network interface. Moreover, it enables us to implement a home node migration optimization that sometimes more than offsets the advantages of the protocol that fully leverages the Memory Channel features, improving performance by as much as 67%. These results suggest that for systems of modest size, low latency is much more important for SDSM performance than are remote writes, broadcast, or total ordering. At the same time, results on an emulated 32-node system indicate that broadcast based on remote writes of widely-shared data may improve performance by up to 56% for some applications. If hardware broadcast or multicast facilities can be made to scale, they can be beneficial in future system-area networks.
Component software techniques have been developed to facilitate software reuse. State and functionality are encapsulated inside components with the goal of limiting program errors due to implicit interactions between components. Late binding of components allows implementations to be chosen at run-time, thereby increasing opportunities for reuse. Current component infrastructures also provide version management capabilities to control the evolutionary development of components. In addition to the general goal of reuse, component software has also focused on enabling distributed computing. Current component infrastructures have strong support for distributed applications.By leveraging these strengths of component software, a component-based operating system (OS) application programmer interface (API) can remedy two weaknesses of current monolithic, procedural APIs. Current APIs are typically very rigid; they cannot be modified without jeopardizing legacy applications. This rigidity results in bloat in both API complexity and support code. Also current APIs focus primarily on the single host machine. They lack the ability to name and manipulate OS resources on remote machines. An API constructed entirely of components can leverage version management and distributed computing facilities. Version management can be used to identify legacy APIs, which can then be dynamically loaded. OS resources modeled as components can be instantiated on remote machines and then manipulated with the natural access semantics.
We have developed the COP system as prototype component-based API for Windows NT. The system provides an API with version management capabilities and with a method for naming and manipulating remote OS resources. The advantages are gained with a minimum of overhead and without sacrificing legacy compatibility.
Keywords: software distributed shared memory; cluster computing.
Symmetric multiprocessors (SMPs) connected with low-latency networks provide attractive building blocks for software distributed shared memory systems. Two distinct approaches have been used: the fine-grain approach that instruments application loads and stores to support a small coherence granularity, and the coarse-grain approach based on virtual memory hardware that provides coherence at a page granularity. Fine-grain systems offer a simple migration path for applications developed on hardware multiprocessors by supporting coherence protocols similar to those implemented in hardware. On the other hand, coarse-grain systems can potentially provide higher performance through more optimized protocols and larger transfer granularities, while avoiding instrumentation overheads. Numerous studies have examined each approach individually, but major differences in experimental platforms and applications make comparison of the approaches difficult.This paper presents a detailed comparison of two mature systems, Shasta and Cashmere, representing the fine- and coarse-grain approaches, respectively. Both systems are tuned to run on the same commercially available, state-of-the-art cluster of AlphaServer SMPs connected via a Memory Channel network. As expected, our results show that Shasta provides robust performance for applications tuned for hardware multiprocessors, and can better tolerate fine-grain synchronization. In contrast, Cashmere is highly sensitive to fine-grain synchronization, but provides a performance edge for applications with coarse-grain behavior. Interestingly, we found that the performance gap between the systems can often be bridged by program modifications that address coherence and synchronization granularity. In addition, our study reveals some unexpected results related to the interaction of current compiler technology with application instrumentation, and the ability of SMP-aware protocols to avoid certain performance disadvantages of coarse-grain approaches.
Keywords: parallel data mining; knowledge discovery; association rules; sequence discovery; decision tree classification; shared memory machines; distributed memory machines; network of SMP workstations; high performance parallel computing.
Data mining is the process of automatic extraction of novel, useful, and understandable patterns in very large databases. High-performance scalable and parallel computing is crucial for ensuring system scalability and inter-activity as datasets grow inexorably in size and complexity. This thesis deals with both the algorithmic and systems aspects of scalable and parallel data mining algorithms applied to massive databases. The algorithmic aspects focus on the design of efficient, scalable, disk-based parallel algorithms for three key rule discovery techniques---association rules, sequence discovery, and decision tree classification. The systems aspects deal with the scalable implementation of these methods on both sequential machines and popular parallel hardware ranging from shared-memory systems (SMP) to hybrid hierarchical clusters of networked SMP workstations.The association and sequence mining algorithms use lattice-theoretic combinatorial properties to decompose the original problem into small independent sub-problems that can be solved in main memory. Using efficient search techniques and simple intersection operations all frequent patterns are enumerated in a few database scans. The parallel algorithms are asynchronous, requiring no communication or synchronization after an initial set-up phase. Furthermore, the algorithms are based on a hierarchical parallelization, utilizing both shared-memory and message-passing primitives. In classification rule mining, we present disk-based parallel algorithms on shared-memory multiprocessors, the first such study. Extensive experiments have been conducted for all three problems, showing immense improvement over previous approaches, with linear scalability in database size.
Keywords: automatic distributed partitioning; component object model (COM); automatic distributed partitioning systems (ADPS); distributed systems; client/server systems.
Distributed applications provide access to distributed resources including memory, processor cycles, and I/O devices. It is easy to create distributed applications with poor performance, but difficult to create distributed applications with good performance. High-performance distributed applications are difficult to create in large part because the programmer must manually partition and distribute the application to maximize locality and minimize communication.This dissertation asserts that system software, not the programmer, should shoulder the burden of distribution. We identify the features necessary to automatically partition and distribute applications. These features include structural metadata to identify and isolate application components, support for component location transparency, dynamic metadata to quantify inter-component communication, an algorithm to choose a distribution, mechanisms to realize a chosen distribution, and sufficient component granularity in the application to enable partitioning.
We demonstrate that a large class of applications can be distributed efficiently without access to source code using automatic partitioning tools that minimize distributed communication. This dissertation describes a functional system, Coign, that automatically distributes applications conforming to Microsoft Corporation's Component Object Model (COM). Coign has been applied to several commercial applications, including the Microsoft Picture It! image processor. To our knowledge, Coign is the first system to provide automatic distributed partitioning of binary applications.
This paper presents the PLANMINE sequence mining algorithm to extract patterns of events that predict failures in databases of plan executions. New techniques were needed because previous data mining algorithms were overwhelmed by the staggering number of very frequent, but entirely unpredictive patterns that exist in the plan database. This paper combines several techniques for pruning out unpredictive and redundant patterns which reduce the size of the returned rule set by more than three orders of magnitude. PLANMINE has also been fully integrated into two real-world planning systems. We experimentally evaluate the rules discovered by PLANMINE, and show that they are extremely useful for understanding and improving plans, as well as for building monitors that raise alarms before failures happen.
Many data mining tasks (e.g., Association Rules, Sequential Patterns) use complex pointer-based data structures (e.g., hash trees) that typically suff er from sub-optimal data locality. In the multiprocessor case shared access to these data structures may also result in false sharing. For these tasks it is commonly observed that the recursive data structure is built once and accessed multiple times during each iteration. Furthermore, the access patterns after the build phase are highly ordered. In such cases locality and false sharing sensitive memory placement of these structures can enhance performance significantly. We evaluate a set of placement policies for parallel association discovery, and show that simple placement schemes can improve execution time by more than a factor of two. More complex schemes yield additional gains.
Keywords: non-blocking; lock-free; mutual exclusion; locks; multiprogramming; concurrent queues; concurrent stacks; concurrent heaps; concurrent counters; concurrent data structures; compare-and-swap; load-linked; store-conditional.
Most multiprocessors are multiprogrammed to achieve acceptable response time and to increase their utilization. Unfortunately, inopportune preemption may significantly degrade the performance of synchronized parallel applications. To address this problem, researchers have developed two principal strategies for concurrent, atomic update of shared data structurew: (1) preemption-safe locking and (2) non-blocking (lock-free) algorithms. Preemption-safe locking requires kernel support. Non-blocking algorithms generally require a universal atomic primitive such as compare-and-swap or load-linked/store-conditional, and are widely regarded as inefficient.We evaluate the performance of preemption-safe lock-based and non-blocking implementations of important data structures---queues, stacks, heaps, and counters---including non-blocking and lock-based queue algorithms of our own, in micro-benchmarks and real applications on a 12-processor SGI Challenge multiprocessor. Our results indicate that our non-blocking queue consistently outperforms the best known alternatives, and that data-strucutre-specific non-blocking algorithms, which exist for queues, stacks, and counters, can work extremely well. Not only do they outperform preemption-safe lock-based algorithms on multiprogrammed machines, they also outperform ordinary locks on dedicated machines. At the same time, since general-purpose non-blocking techniques do not yet appear to be practical, preemption-safe locks remain the preferred alternative for complex data structures: they outperform conventional locks by significant margins on multiprogrammed systems.
In this paper we describe a formal framework for the problem of mining association rules. The theoretical foundation is based on the field of formal concept analysis. A concept is composed of closed subsets of attributes (itemsets) and objects (transactions). We show that all frequent itemsets are uniquely determined by the frequent concepts. We further show how this lattice-theoretic framework can be used to find a small rule generating set, from which one can infer all other association rules.
Load balancing involves assigning to each processor, work proportional to its performance, minimizing the execution time of the program. Although static load balancing can solve many problems (e.g., those caused by processor heterogeneity and non-uniform loops) for most regular applications, the transient external load due to multiple-users on a network of workstations necessitates a dynamic approach to load balancing. In this paper we show that different schemes are best for different applications under varying program and system parameters. Therefore, application-driven customized load balancing becomes essential for good performance. We present a hybrid compile-time and run-time modeling and decision process which selects (customizes) the best scheme, along with automatic generation of parallel code with calls to a runtime library for load balancing.
Discovery of association rules is an important data mining task. Several parallel and sequential algorithms have been proposed in the literature to solve this problem. Almost all of these algorithms make repeated passes over the database to determine the set of frequent itemsets (a subset of database items), thus incurring high I/O overhead. In the parallel case, most algorithms perform a sum-reduction at the end of each pass to construct the global counts, also incurring high synchronization cost.In this paper we describe new parallel association mining algorithms. The algorithms use novel itemset clustering techniques to approximate the set of potentially maximal frequent itemsets. Once this set has been identified, the algorithms make use of efficient traversal techniques to generate the frequent itemsets contained in each cluster. We propose two clustering schemes based on equivalence classes and maximal hypergraph cliques, and study two lattice traversal techniques based on bottom-up and hybrid search. We use a vertical database layout to cluster related transactions together. The database is also selectively replicated so that the portion of the database needed for the computation of associations is local to each processor. After the initial set-up phase, the algorithms do not need any further communication or synchronization. The algorithms minimize I/O overheads by scanning the local database portion only twice. Once in the set-up phase, and once when processing the itemset clusters. Unlike previous parallel approaches, the algorithms use simple intersection operations to compute frequent itemsets and do not have to maintain or search complex hash structures.
Our experimental testbed is a 32-processor DEC Alpha cluster inter-connected by the Memory Channel network. We present results on the performance of our algorithms on various databases, and compare it against a well known parallel algorithm. The best new algorithm outperforms it by an order of magnitude.
In this paper, we study the problem of scheduling parallel loops at compile-time for a heterogeneous network of workstations. We consider heterogeneity in various aspects of parallel programming: program, processor, memory and network. A heterogeneous program has parallel loops with different amount of work in each iteration; heterogeneous processors have different speeds; heterogeneous memory refers to the differe