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: locality; footprint; reuse distance; memory hierarchy; cachesharing; theory; locality sampling.
The locality of a program may be quantified by the data footprint over a time period or by the miss ratio in a particular cache. The relation between data usage and miss frequency has not been precisely established. Neither is it known whether one metric contains more information than the other.This paper presents a theory with two constituents. The first is a set of complete derivations between five commonly used locality metrics including the footprint and miss ratio curve. The second is a condition for the footprint-to-miss-ratio conversion to be correct. The derivations use statistics on variable-length windows and different-size caches. The calculation is similar to differentiation and integration used to convert between high- degree polynomials.
As an application, the paper gives a new sampling technique, which predicts the miss ratio for all cache sizes in near real time without special hardware support and without the exclusive use of the machine cache. The paper evaluates the technique for sequential and parallel programs as well as for a parallel mix of sequential programs.
Keywords: multi-core; server system; power throttling; energy optimization.
Energy efficiency and power capping remain growing concerns in server systems. Online applications continue to evolve with new features and dynamic client-directed processing, resulting in varying power profiles. New computing platforms with multicore resource sharing and heterogeneity further obfuscate the system behaviors, presenting challenges for request/client-based energy accounting, identification and control of power viruses, as well as energy-efficient load management. This paper presents a new operating system facility we call "power and energy containers" that accounts for and controls the power/energy usage of individual fine-grained requests in multicore servers. Our power and energy containers are enabled by three techniques--- 1) online attribution of multicore power (including shared maintenance power) to individual tasks running concurrently on the multicore, 2) alignment of actual power measurements and model estimates to enable online model recalibration, and 3) on-the-fly request tracking in multi-stage servers to isolate the power/energy contributions and customize control of individual requests. We evaluate our request-level power/energy containers on three different multicore processors (Intel Woodcrest, Nehalem, and Westmere) using a number of open-source application workloads including a high stress benchmark that can mimic a power virus. Our power containers can be used to cap server power consumption in a fair manner by penalizing only power-hungry requests. The container energy profiles can also identify request affinity and guide request distribution between heterogeneous servers. Our case study shows up to 18% energy saving compared to an alternative approach that recognizes machine heterogeneity but not per-request affinity.
Keywords: safe parallel programming; software speculative parallelization;race checking.
The safety of speculative parallelization depends on monitoring all program access to shared data. Automatic solutions use either program instrumentation, which can be costly, or hardware-based triggering, which incurs false sharing. In addition, not all access requires monitoring. It is worth considering a manual approach in which programmers insert access annotations to reduce the cost and increase the precision of program monitoring.This report first presents an execution model and its interface for access annotation. The semantics of an annotated program is defined by the output of a (sequential) canonical execution. The report then describes a quadratic-time checker that can verify the safety of annotations, that is, whether a speculative execution always produces the canonical output. The report demonstrates the usability of the annotation interface by safely parallelizing a number of code fragments that have uncertain parallelism.
Keywords: cache replacement algorithm; bipartite cache; LRU-MRU stackdistance; program assisted cache management.
The goal of cache management is to maximize data reuse. Collaborative caching provides an interface for software to communicate access information to hardware. In theory, it can obtain optimal cache performance.In this paper, we study a collaborative caching system that allows a program to choose different caching methods for its data. As an interface, it may be used in arbitrary ways, sometimes optimal but probably suboptimal most times and even counter productive. We develop a theoretical foundation for collaborative cache to show the inclusion principle and the existence of a distance metric we call LRU-MRU stack distance. The new stack distance is important for program analysis and transformation to target a hierarchical collaborative cache system rather than a single cache configuration. We use 10 benchmark programs to show that optimal caching may reduce the average miss ratio by 24%, and a simple feedback-driven compilation technique can utilize collaborative cache to realize 38% of the optimal improvement.
Keywords: locks; transactional memory; memory models; synchronization; consistency; serializbility; data-race freedom.
We argue for transactions as the synchronization primitive of an ordering-based memory consistency model. Rather than define transactions in terms of locks, our model defines locks, conditions, and atomic/volatile variables in terms of transactions. A traditional critical section, in particular, is a region of code, bracketed by transactions, in which certain data have been privatized. Our memory model, originally published at OPODIS'08, is based on the database notion of strict serializability (SS). In an explicit analogy to the DRF0 of Adve and Hill, we demonstrated that SS provides the appearance of transactional sequential consistency (TSC) for programs that are transactional data-race free (TDRF). We argue against relaxation of the total order on transactions, but show that selective relaxation of the relationship between program order and transaction order (selective strict serializability - SSS) can allow the implementation of transaction-based locks to be as efficient as conventional locks. We also show that condition synchronoication (in the form of the transaction retry primitive) can be accommodated in our model without explicit mention of speculation, opacity, or aborted transactions. Finally, we compare SS and SSS to the notion of strong isolation (SI), arguing the SI is neither sufficient for TSC nor necessary in programs that are TDRF.
Keywords: MPI; communication-computation overlapping; dynamic pipelining.
The paper presents delta send-recv, an MPI extension for overlapping coarse-grained computation and communication. It provides an interface for marking the data computation and its communication. It automatically blocks computation and divides communication into increments. Delta sends and recvs are dynamically chained to effect sender-receiver pipelining, which is superior to pipelining only at the sender or the receiver side. The evaluation uses kernel tests to find the best increment size for different MPI implementations and types of machines and networks. It shows 2 to 3 times performance improvement for large-volume data reduce involving 16 or 32 processors. In addition, the new interface enables computation and communication pipelining in an interpreted programming language, Rmpi.
Keywords: parallel and distributed programming; parallelization language;suggestion language; software speculation; program dependence;run-time transformation.
Most computing users today have access to clusters of multi-core computers. To fully utilize a cluster, one must combine two levels of parallelism: shared-memory parallelism within a machine and distributed memory parallelism across machines. Such programming is difficult. Either a user has to mix two programming languages in a single program and use fixed computation and data partitioning between the two, or the user has to rewrite a program from scratch. Even after careful programming, a program may still have hidden concurrency bugs. Users who are accustomed to sequential programming do not find the same level of debugging and performance analysis support especially for a distributed environment. The paper presents a language of suggestions for distributive parallelization. The suggestion language is designed for a user or a profiling-based tool to annotate possible parallelism in C/C++ programs by inserting hints. The hints are safe against any type of misuse and expressive enough to specify independent, pipelined, and speculative parallel execution on a cluster of multi-core computers.
Keywords: memory management; garbage collection; resource-based; multi-core.
While a conventional program uses exactly as much memory as it needs, the memory use of a garbage-collected program can be adjusted by changing the size of the heap used by the garbage collector. This difference can allow applications to adapt their memory demands in response to the changing amount of available memory in a shared environment, which is increasingly important for today’s multicore, multiprocessor machines. We present a memory performance model that better addresses issues that occur with the more changeable memory demands of garbage-collected applications. Traditional locality models are not directly applicable because the application demand may change based on the available memory size. We describe time-memory curves, which can be used to derive optimal static memory allocation a shared environment. For dynamic environments, however, more will be needed. In this work, we describe Poor Richard’s Memory Manager, a lightweight system to reduce paging costs that can be incorporated into existing runtime systems. We describe the design of the memory manager and show how it can be added to most existing garbage collectors with little to no effort. Using an ex- perimental evaluation of both homogeneous and heterogeneous Java workloads on a dual processor machine, we show that Poor Richard’s Memory Manager improves average performance by a factor of 3 or more when paging, while adding almost no overhead when there is no memory pressure. We further show that this system is not specific to any single algorithm, but improves every garbage collector on which it is tested. We finally demonstrate the versatility of our memory manager by using it to improve the performance of a range of .Net workloads.
Keywords: reliability; memory hardware errors; software/hardware interaction.
Memory hardware reliability is an indispensable part of whole-system dependability. Its importance is evidenced by a plethora of prior research work studying the impact of memory errors on software systems. However, the absence of solid understanding of the error characteristics prevents software system researchers from making well reasoned assumptions, and it also hinders the careful evaluations over different choices of fault tolerance design. In this paper, we present our realistic memory hardware error traces collected from production computer systems with more than 800GB memory for around nine months. Based on the traces (including detailed information on the error addresses and patterns), we explore the implications of different hardware ECC protection schemes so as to identify the most common error causes and approximate error rates exposed to the software level. Lastly, we investigate the software system susceptibility to some major error causes, with the particular goal to validate, question, and augment results of prior system studies.
Keywords: program parallelization; dynamic and speculative parallelism; parallel language; task scheduling.
Coarse-grained task parallelism exists in sequential code and can be leveraged to boost the use of chip multi-processors. However, large tasks may execute thousands of lines of code and are often too complex to analyze and manage statically. This report describes a programming system called \emph{suggestible parallelization}. It consists of a programming interface and a support system. The interface is a small language with three primitives for marking possibly parallel tasks and their possible dependences. The support system is implemented in software and ensures correct parallel execution through speculative parallelization, speculative communication and speculative memory allocation. It manages parallelism dynamically to tolerate unevenness in task size, inter-task delay and hardware speed. When evaluated using four full-size benchmark applications, suggestible parallelization obtains up to a 6 times speedup over 10 processors for sequential legacy applications up to 35 thousand lines in size. The overhead of software speculation is not excessively high compared to unprotected parallel execution.
Keywords: progoram optimization; run-time system; memory safety checking;parallel execution.
Fast track is a software speculation system that enables unsafe optimization of sequential code. It speculatively runs optimized code to improve performance and then checks the correctness of the speculative code by running the original program on multiple processors.We present the interface design and system implementation for Fast Track. It lets a programmer or a profiling tool mark fast-track code regions and uses a run-time system to manage the parallel execution of the speculative process and its checking processes and ensures the correct display of program outputs. The core of the run-time system is a novel concurrent algorithm that balances exploitable parallelism and available processors when the fast track is too slow or too fast. The programming interface closely affects the run-time support. Our system permits both explicit and implicit end markers for speculatively optimized code regions as well as extensions that allow the use of multiple tracks and user defined correctness checking. We discuss the possible uses of speculative optimization and demonstrate the effectiveness of our prototype system by examples of unsafe semantic optimization and a general system for fast memory-safety checking, which is able to reduce the checking time by factors between 2 and 7 for large sequential code on a 8-CPU system.
Keywords: hardware transactional memory; FlexTM; Contention management;conflict detection.
In the search for high performance, most transactional memory (TM) systems execute atomic blocks concurrently and must thus be prepared for data conflicts. These conflicts must be detected and the system must choose a policy in terms of when and how to manage the resulting contention. Conflict detection essentially determines when the conflict manager is invoked, which can be dealt with eagerly (when the transaction reads/writes the location), lazily at commit time, or somewhere in between.In this paper, we analyze the interaction between conflict detection and contention manager heuristics. We show that this has a significant impact on exploitation of available parallelism and overall throughput. First, our analysis across a wide range of applications reveals that simply stalling before arbitrating helps side-step conflicts and avoid making the wrong decision. HTM systems that don't support stalling after detecting a conflict seem to be prone to cascaded aborts and livelock. Second, we show that the time at which the contention manager is invoked is an important policy decision: lazy systems are inherently more robust while eager systems seem prone to pathologies, sometimes introduced by the contention manager itself. Finally, we evaluate a \textit{mixed} conflict detection mode that combines the best of eager and lazy. It resolves write-write conflicts early, saving wasted work, and read-write conflicts lazily, allowing the reader to commit/serialize prior to the writer while executing concurrently.
Keywords: software transactional memroy; serializability; atomicity;semantics.
It has been widely suggested that memory transactions should behave as if they acquired and released a single global lock. Unfortunately, this behavior can be expensive to achieve, particularly when---as in the natural publication/privatization idiom---the same data are accessed both transactionally and nontransactionally. To avoid overhead, we propose selective strict serializability (SSS) semantics, in which transactions have a global total order, but nontransactional accesses are globally ordered only with respect to explicitly marked transactions. Our definition of SSS formally characterizes the permissible behaviors of an STM system without recourse to locks. If all transactions are marked, then SSS, single- lock semantics, and database-style strict serializability are equivalent.We evaluate several SSS implementations in the context of a TL2-like STM system. We also evaluate a weaker model, selective flow serializability (SFS), which is similar in motivation to the asymmetric lock atomicity of Menon et al. We argue that ordering-based semantics are conceptually preferable to lock-based semantics, and just as efficient.
Keywords: Transactional memory; condition synchronization; bloom filters.
Software Transactional Memory (STM) systems, if they support condition synchronization, typically do so through a retry mechanism. Using retry, a transaction explicitly self aborts and deschedules itself when it discovers that a precondition for its operation does not hold. The underlying implementation may then track the set of locations read by the retrying transaction, and refrain from scheduling the transaction for re-execution until at least one location in the set has been modified by another transaction.While retry is elegant and simple, the conventional implementation has several potential drawbacks that may limit both its efficiency and its generality. In this note, we present a retry mechanism based on Bloom filters that is entirely orthogonal to TM implementation. Our retry is compatible with hardware, software, and hybrid TM implementations, and has no impact on memory management or on the cache behavior of shared locations. It does, however, serialize writer transactions after their commit point when there are retrying transactions. We describe our mechanism and compare it to an optimized version of the conventional implementation.
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 different amount of user-available memory on the machines; and a heterogeneous network has different cost of communication between processors. We propose a simple yet comprehensive model for use in compiling for a network of processors, and develop compiler algorithms for generating optimal and near-optimal schedules of loops for load balancing, communication optimizations, network contention and memory heterogeneity. Experiments show that a significant improvement of performance is achieved using our techniques.
This paper presents fast scalable decision-tree-based classification algorithms targeting shared-memory systems. The algorithms are based on the sequential SPRINT classifier and span the gamut of data and task parallelism. The data parallelism is based on attribute scheduling among processors. This is extended with task pipelining and dynamic load balancing to yield more complex schemes. The task parallel approach uses dynamic subtree partitioning among processors. These schemes are disk based and achieve excellent scalability, making them ideally suited for data mining in very large databases.
Keywords: sequence mining; predicting plan failures; plan monitoring.
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.
Keywords: compilers; memory locality; array and loop transformations.
This dissertation presents new techniques designed to speed up the execution of computer programs by improving their memory locality. Locality is an important property for today's machines, because it hides the relatively high latency of computer memories.Our techniques change the layout of multidimensional arrays by applying data transformations. We unify data transformations with code transformations which change the order of execution of loop nests. We solve related problems which would have been obstacles to the practical use of our techniques: we show how to detect and reduce array overlapping and how to recover structure from linearized arrays. Our optimizations reduce the execution times of sequential, scientific benchmarks by up to 50% over what is possible with previous techniques. Parallel programs are improved by as much as a factor of four.
In addition to implementing our techniques in a standard, off-line, compiler, we adapt our optimizations to Just-In-Time (JIT) compilation. The JIT translation becomes very important with the increasing popularity of mobile technologies such as Java. We argue that new, faster algorithms are needed in that context. We propose a collection of fast, approximate compiler techniques for data transformations and show that they are effective for Java programs.
Keywords: knowledge discovery; data mining; sequential patterns; sequence discovery; temporal association rules.
In this paper we present a new algorithm for fast discovery of Sequential Patterns. Given a collection of items, a set of records over those items, and records belonging to a customer, the task is to identify all the commonly occurring sequences of items bought by the customers. An example of a sequential pattern could be that 30% of the people buying Douglas Adam's "The Hitchhiker's Guide to the Galaxy" bought "The Restaurant at the End of the Universe" within a month.The existing solutions to this problem make repeated database scans, and use complex hash structures which have poor locality. Our new SPADE algorithm uses only simple join operations, and finds all frequent sequences in usually only three database scans. With the help of extensive experiments, we show that SPADE outperforms the best previous algorithm by more than a factor of 2, and by more than an order of magnitude in the incremental case. It also has excellent scale-up properties with respect to the number of customers, the number of transactions per customer, the transaction size, and the size of potential maximal frequent sequences.
Discovery of association rules is an important problem in database mining. In this paper we present new algorithms for fast association mining, which scan the database only once, addressing the open question whether all the rules can be efficiently extracted in a single database pass. The algorithms use novel itemset clustering techniques to approximate the set of potentially maximal frequent itemsets. The algorithms then make use of efficient lattice 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 traversal techniques based on bottom-up and hybrid search. We also use a vertical database layout to cluster related transactions together. Experimental results show improvements of over an order of magnitude compared to previous algorithms.
Keywords: parallel processing; performance analysis; performance tuning; performance modeling.
There is a constant need throughout the life cycle of a parallel program for analyzing, tuning, and predicting its performance. These tasks all require that the programmer understand the performance exhibited by a program, and the performance implications of alternative implementations. Achieving such an understanding is extremely difficult, however, since a program's performance depends on characteristics of the application, the underlying hardware, the software environment, and interactions among all three. In this dissertation, we show how to automatically generate explanations for performance behavior and thereby facilitate performance analysis, tuning, and prediction.We propose an integrated framework for performance understanding called Carnival, which supports the acquisition and manipulation of large amounts of performance data, automates the process of generating models, and provides visualizations of performance behavior. The novelty of this framework is cause-effect analysis, which is a general approach for generating explanations for the costs associated with parallel overheads automatically.
We illustrate our approach by describing explanation techniques for three classes of overheads in parallel programs: contention in parallel file systems, synchronization in message-passing and shared-memory programs, and communication in distributed shared memory systems. Using the explanations produced by these techniques, we are able to understand and minimize common performance problems in real applications including load imbalance, false sharing, poor lock granularity, contention, and performance degradation due to multiprogramming.
Keywords: knowledge discovery; data mining; association rules; memory placement; memory allocation; improving locality; reducing false sharing; dynamic data structures; hash tree.
A lot of data mining tasks, such as Associations, Sequences, and Classification, use complex pointer-based data structures that typically suffer from sub-optimal locality. In the multi-processor case shared access to these data structures may also result in false-sharing. Most of the optimization techniques for enhancing locality and reducing false sharing have been proposed in the context of numeric applications involving array-based data structures, and are not applicable for dynamic data structures due to dynamic memory allocation from the heap with arbitrary addresses.Within the context of data mining it is commonly observed that the building phase of these large recursive data structures, such as hash trees and decision trees, is random and independent from the access phase which is usually ordered and typically dominates the computation time. In such cases locality and false sharing sensitive memory placement of these structures can enhance performance significantly. We evaluate a set of placement policies over a representive data mining application (association rule discovery) and show that simple placement schemes can improve execution time by more than a factor of two. More complex schemes yield an additional 5-20% gain.
Low-latency remote-write networks, such as DEC's Memory Channel, provide the possibility of transparent, inexpensive, large-scale shared-memory parallel computing on clusters of shared memory multiprocessors (SMPs). The challenge is to take advantage of hardware shared memory for sharing within an SMP, and to ensure that software overhead is incurred only when actively sharing data across SMPs in the cluster. In this paper, we describe a ``two-level'' software coherent shared memory system---Cashmere-2L---that meets this challenge. Cashmere-2L uses hardware to share memory within a node, while exploiting the Memory Channel's remote-write capabilities to implement ``moderately lazy'' release consistency with multiple concurrent writers, directories, home nodes, and page-size coherence blocks across nodes. Cashmere-2L employs a novel coherence protocol that allows a high level of asynchrony by eliminating global directory locks and the need for TLB shootdown. Remote interrupts are minimized by exploiting the remote-write capabilities of the Memory Channel network.Cashmere-2L currently runs on an 8-node, 32-processor DEC AlphaServer system. Speedups range from 8 to 31 on 32 processors for our benchmark suite, depending on the application's characteristics. We quantify the importance of our protocol optimizations by comparing performance to that of several alternative protocols that do not share memory in hardware within an SMP, and require more synchronization. In comparison to a one-level protocol that does not share memory in hardware within an SMP, Cashmere-2L improves performance by up to 46%.
Keywords: frequent itemsets; association rules; knowledge discovery and data mining; parallel algorithms; maximal hypergraph cliques; lattice traversals.
Association rule discovery has emerged as an important problem in knowledge discovery and data mining. The association mining task consists of identifying the frequent itemsets, and then forming conditional implication rules among them. In this paper we present efficient algorithms for the discovery of frequent itemsets, which forms the compute intensive phase of the task. The algorithms utilize the structural properties of frequent itemsets to facilitate fast discovery. The related database items are grouped together into clusters representing the potential maximal frequent itemsets in the database. Each cluster induces a sub-lattice of the itemset lattice. Efficient lattice traversal techniques are presented, which quickly identify all the true maximal frequent itemsets, and all their subsets if desired. We also present the effect of using different database layout schemes combined with the proposed clustering and traversal techniques. The proposed algorithms scan a (pre-processed) database only once, addressing the open question in association mining, whether all the rules can be efficiently extracted in a single database pass. We experimentally compare the new algorithms against the previous approaches, obtaining improvements of more than an order of magnitude for our test databases.
Discovery of association rules is an important database mining problem. Mining for association rules involves extracting patterns from large databases and inferring useful rules from them. 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 commonly occurring patterns or {\em itemsets} (set of items), thus incurring high I/O overhead. In the parallel case, these algorithms do a reduction at the end of each pass to construct the global patterns, thus incurring high synchronization cost.In this paper we describe a new parallel association mining algorithm. Our algorithm is a result of detailed study of the available parallelism and the properties of associations. The algorithm uses a scheme to cluster related frequent itemsets together, and to partition them among the processors. At the same time it also uses a different database layout which clusters related transactions together, and selectively replicates the database 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 algorithm eliminates the need for further communication or synchronization. The algorithm further scans the local database partition only three times, thus minimizing I/O overheads. Unlike previous approaches, the algorithms uses simple intersection operations to compute frequent itemsets and doesn't 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 algorithm on various databases, and compare it against a well known parallel algorithm. Our algorithm outperforms it by an more than an order of magnitude.
Discovery of association rules is a prototypical problem in data mining. The current algorithms proposed for data mining of association rules make repeated passes over the database to determine the commonly occurring itemsets (or set of items). For large databases, the I/O overhead in scanning the database can be extremely high. In this paper we show that random sampling of transactions in the database is an effective method for finding association rules. Sampling can speed up the mining process by more than an order of magnitude by reducing I/O costs and drastically shrinking the number of transactions to be considered. We may also be able to make the sampled database resident in main-memory. Furthermore, we show that sampling can accurately represent the data patterns in the database with high confidence. We experimentally evaluate the effectiveness of sampling on different databases, and study the relationship between the performance, and the accuracy and confidence of the chosen sample.
Most multiprocessors are multiprogrammed to achieve acceptable response time. 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 structures: (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, and are widely regarded as inefficient.We present a comparison of the two alternative strategies, focusing on four simple but important concurrent data structures---stacks, FIFO queues, priority queues and counters---in micro-benchmarks and real applications on a 12-processor SGI Challenge multiprocessor. Our results indicate that data-structure-specific non-blocking algorithms, which exist for stacks, FIFO queues 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.
Recent technological advances have produced network interfaces that provide users with very low-latency access to the memory of remote machines. We examine the impact of such networks on the implementation and performance of software DSM. Specifically, we compare two DSM systems---Cashmere and TreadMarks---on a 32-processor DEC Alpha cluster connected by a Memory Channel network.Both Cashmere and TreadMarks use virtual memory to maintain coherence on pages, and both use lazy, multi-writer release consistency. The systems differ dramatically, however, in the mechanisms used to track sharing information and to collect and merge concurrent updates to a page, with the result that Cashmere communicates much more frequently, and at a much finer grain.
Our principal conclusion is that low-latency networks make DSM based on fine-grain communication competitive with more coarse-grain approaches, but that further hardware improvements will be needed before such systems can provide consistently superior performance. In our experiments, Cashmere scales slightly better than TreadMarks for applications with false sharing. At the same time, it is severely constrained by limitations of the current Memory Channel hardware. In general, performance is better for TreadMarks.
Scalable distributed shared-memory architectures rely on coherence controllers on each processing node to synthesize cache-coherent shared memory across the entire machine. The coherence controllers execute coherence protocol handlers that may be hardwired in custom hardware or programmed in a protocol processor within each coherence controller. Although custom hardware runs faster, a protocol processor allows the coherence protocol to be tailored to specific application needs and may shorten hardware development time. Previous research show that the increase in application execution time due to protocol processors over custom hardware is minimal.With the advent of SMP nodes and faster processors and networks, the tradeoff between custom hardware and protocol processors needs to be reexamined. This paper studies the performance of custom-hardware and protocol-processor-based coherence controllers in SMP-node-based CC-NUMA systems on applications from the SPLASH-2 suite. Using realistic parameters and detailed models of existing state-of-the-art system components, it shows that the occupancy of coherence controllers can limit the performance of applications with high communication requirements, where the execution time using protocol processors can be twice as long as using custom hardware.
To gain a deeper understanding of the tradeoff, we investigate the effect of varying several architectural parameters that influence the communication characteristics of the applications and the underlying system on coherence controller performance. We identify measures of applications' communication requirements and their impact on the performance penalty of protocol processors, which can help system designers predict performance penalties for other applications. We also study the potential of mproving the performance of hardware-based and protocol-processor-based coherence controllers by separating or duplicating critical components.
Memory-mapped network interfaces provide users with fast and cheap access to remote memory on clusters of workstations. Software distributed shared memory (DSM) protocols built on top of these networks can take advantage of fast messaging to improve performance. The low latencies and remote memory access capabilities of these networks suggest the need to re-evaluate the assumptions underlying the design of DSM protocols. This paper describes some of the approaches currently being used to support shared memory efficiently on such networks. We discuss other possible design options for DSM systems on a memory-mapped network interface and propose methods by which the interface can best be used to implement coherent shared memotry in software.
Keywords: mobile computing; location management; dynamic hashing; tries; quorum systems.
Location management is a fundamental problem in mobile computing systems. Existing industry standards employ centralized location management schemes. Centralized schemes are not highly scalable. This paper presents a new, distributed location management strategy for mobile systems. Its salient features are fast location update and query, load balancing among location servers, and scalability. The strategy employs dynamic hashing techniques and quorums to manage location update and query operations. Location information of a mobile host is replicated at a subset of location servers. The set of location servers associated with a mobile host changes with time, depending on the location of mobile hosts and load on the servers. This dynamism prevents situations of heavy load (location update and query messages) on some location servers when the mobile hosts are not uniformly distributed in space, or when some mobile hosts have their location updated or queried more often than others. New location servers can be added to the system as the number of mobile hosts and/or location update and query rates increase. Also, if the load diminishes, the number of location servers in the system can be reduced. Tries and quorum systems are used to expand and shrink the number of location servers. Unlike several existing schemes that progressively expand their region of search and may require multiple rounds of messages to locate a mobile host, the proposed scheme requires a single round of message multicasting for location update and query operations. The size of the multicast set is proportional to the square root of the number of location servers and each message has a small size. All multicast messages are resetricted to the high bandwidth wired part of the mobile network. Hence, communication overhead and latency are low. The storage overheads imposed on the location servers are nominal.
Keywords: component software; distributed applications; groupware; Coign; component placement; inter-component communication analysis (ICCA).
Object systems, such as COM, promise to greatly simplify application development through the reuse of ``black-box'' components. Unfortunately, opaque components create new challenges to understanding application performance, behavior and structure. We propose a conceptual framework, inter-component communication analysis (ICCA), for understanding and exploring the structure of component applications. ICCA models an application as a graph with vertices representing components and edges representing communication links and instantiation relationships between components . Communication edges are labeled with the amount of communication that would cross the interface if the connected components were located in separate address spaces. We describe the Coign runtime system for gathering the data necessary to create the ICCA graph. Coign is distinctive in that it creates the entire ICCA graph using only application binaries. It can in fact be used on components lacking source code. Quantifying inter-component communication is vital to understanding and exploiting the architecture of component applications. We demonstrate the use of ICCA and Coign to determine an optimal distribution of a component application across a network. ICCA helps programmers by providing important information about the application at exactly the level needed: the level of component composition.
Keywords: barriers; busy-waiting; locks; mutual exclusion; preemption; scalability.
Efficient synchronization is important for achieving good performance in parallel programs, especially on large-scale multiprocessors. Most synchronization algorithms have been designed to run on a dedicated machine, with one application process per processor, and can suffer serious performance degradation in the presence of multiprogramming. Problems arise when running processes block, or worse, busy-wait for action on the part of a process that the scheduler has chosen not to run. We show that these problems are particularly severe for scalable synchronization algorithms based on distributed data structures. We then describe and evaluate a set of algorithms that perform well in the presence of multiprogrammintg while maintaining good performance on dedicated machines. We consider both large and small machines, with a particular focus on scalability, and examine mutual-exclusion locks, reader-writer locks, and barriers.Our algorithms vary in the degree of support required from the kernel scheduler. We find that while it is possible to avoid pathological performance problems using previously proposed kernel mechanisms, a modest additional widening of the kerner/user interface can make scheduler-conscious synchronization algorithms significantly simpler and faster, with performance on dedicated machines comparable to that of scheduler-oblivious algorithms.
Keywords: distributed shared memory; memory-mapped network interface; Cashmere; TreadMarks.
Recent technological advances have produced network interfaces that provide users with very low-latency access to the memory of remote machines. We examine the impact of such networks on the implementation and performance of software DSM. Specifically, we compare two DSM systems---Cashmere and TreadMarks---on a 32-processor DEC Alpha cluster connected by a Memory Channel network.Both Cashmere and TreadMarks use virtual memory to maintain coherence on pages, and both use lazy, multi-writer release consistency. The systems differ dramatically, however, in the mechanisms used to track sharing information and to collect and merge concurrent updates to a page, with the result that Cashmere communicates much more frequently, and at a much finer grain.
Our principal conclusion is that low-latency networks make DSM based on fine-grain communication competitive with more coarse-grain approaches, but that further hardware improvements will be needed before such systems can provide consistently superior performance. In our experiments, Cashmere scales slightly better than TreadMarks for applications with fine-grain interleaving of accesses to shared data. At the same time, it is severely constrained by limitations of the current Memory Channel hardware. On average, performance is better for TreadMarks. Because most of its messages require remote processing, TreadMarks depends critically on the latency of interrupts: performance improves greatly when processors poll for messages.
Keywords: interprocedural array remapping; array and code structure recovery; procedure cloning.
Programming languages like Fortran or C define exactly the layout of array elements in memory. Programmers often use that definition to access the same memory via variables declared as arrays of different types. This is done, for instance, to access a slice of larger array or to access data as a linear array, so that subscript computation is simpler giving performance improvements on some architectures and allowing the use of single procedure to perform some operation (e.g., copying) on variables of different types. For many real programs this practice makes changing the layout of an array impossible without violating the semantics of the program since the same memory block may be accessed via a variable of a different type---such an access will now receive wrong array elements.On the other hand, changing array layout is often necessary to obtain good parallel performance or even to improve sequential performance by providing better cache locality. The techniques that achieve that range from manually inserted array distribution directives to automatic compiler transformations.
Our paper demonstrates that the problem of changing array layouts in the presence of multiple variables of different types accessing the same memory can be solved with our algorithms for 1) detecting overlapping arrays, 2) using procedure cloning to reduce overlapping, 3) array type coercion, and 4) code structure recovery. We describe the algorithms used in our compiler and present experimental results showing speedups which are not possible with other techniques.
Most parallel databases exploit two types of parallelism: intra-query parallelism and inter-transaction concurrency. Between these two cases lies another type of parallelism: inter-query parallelism within a transaction or application. Exploiting inter-query parallelism requires either compiler support to automatically parallelize the existing embedded query programs, or programming support to write explicitly parallel query programs. In this paper, we present compiler analysis to automatically detect parallelism in the embedded query programs. We present compiler algorithms for detecting dependences in such programs. We show that the properties of some aggregate functions such as MIN and MAX can help reduce statically computed dependences.
Keywords: message ordering; reliable communication; unreliable communication; FIFO-transmission; communication slots.
Communication protocols designed for database applications are not necessarily suitable for other applications, like multimedia communication, due to the former's requirement of reliable and ordered communication, and the latter's ability to withstand occasional losses and misordering of messages as long as real-time communication can be supported. This paper presents the slotted-FIFO communication protocol that supports communication primitives for the entire spectrum of reliability and ordering requirements of distributed applications: FIFO as well as non-FIFO, and reliable as well as unreliable communication. Hence, the slotted-FIFO protocol is suitable for multimedia applications like MPEG video transmission and video telephony, as well as non real-time distributed applications. The protocol is simple and has low overheads. As FIFO ordering is not required for all messages, message buffering requirements are considerably reduced. Also, message latencies are lower.
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 examine the behavior of global vs local, and centralized vs distributed, load balancing strategies. We show that different schemes are best for different applications under varying program and system parameters. Therefore, customized load balancing schemes become 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.
Keywords: distributed shared memory; fault tolerance; peer logging.
We present a peer logging system for reducing performance overhead in fault-tolerant distributed shared memory systems. Our system provides fault-tolerant shared memory using individual checkpointing and rollback. Peer logging logs DSM modification messages to remote nodes instead of to local disks. We present results for implementations of our fault-tolerant technique using simulations of both TreadMarks, a software-only DSM, and Cashmere, a DSM using memory mapped hardware. We compare simulations with no fault tolerance to simulations with local disk logging and peer logging. We present results showing that fault-tolerant Treadmarks can be achieved with an average of 17% overhead for peer logging. We also present results showing that while almost any DSM protocol can be made fault tolerant, systems with localized DSM page meta-data have much lower overheads.
Keywords: Java; bytecode; profiling; visualization; client-server; World Wide Web; Internet.
In this paper we present a system for network based visualization of profile information generated by Java applets/bytecode. The system, called NetProf, is composed of several components each of which is interesting in their own right. The components are a bytecode to Java source code translator, a profiler that includes a static pass to insert profiler code, a dynamic runtime library that records relevant events, and finally a visualization mechanism that highlights the profile information in an easy-to-use manner. All of this can be done over the Internet using a client-server approach and is independent of the underlying architecture/machine and human intervention.
Keywords: Java; compiler; optimizations; Briki; JavaIR; bytecode.
We present a Java compiler architecture which uses a unique combination of front- and back-ends to deliver great flexibility. Our compiler is designed to use the same optimization passes no matter which pair of front- and back-end is used.The compiler can be configured as a traditional stand-alone compiler (which compiles Java source into Java bytecodes). Another configuration can be used as an on-the-fly optimizer (which optimizes applets as they are loaded from the network). We can also compile Java directly to native code, thus using Java as a replacement for one of the traditional programming languages. Other interesting setups are also possible.
This flexibility is achieved by using a common intermediate representation, JavaIR (Java Intermediate Representation). Multiple front-ends convert various input formats (Java source, bytecode) into JavaIR. Once represented as JavaIR an application can be transformed with any of the existing passes. The modified JavaIR form of an application can be written out in one of the supported output formats.
Although compilers with multiple front- and back-ends have already existed, our approach is unique in supporting high-level code transformations even on applications which are distributed without the source program. Since Briki is written in Java it can be easily integrated into any Java application (e.g., a WWW browser) which dynamically loads applets from the network to provide capabilities of on-the-fly optimization.
Keywords: data mining; association rules; load balancing; hash tree balancing; hashing; shared-memory multiprocessor.
Data mining is an emerging research area, whose goal is to extract significant patterns or interesting rules from large databases. High-level inference from large volumes of routine business data can provide valuable information to businesses, such as customer buying patterns, shelving criterion in supermarkets, and stock trends. Many algorithms have been proposed for data mining of association rules. However, research so far has mainly focused on sequential algorithms.In this paper we present parallel algorithms for data mining of association rules, and study the degree of parallelism, synchronization, and data locality issues on the SGI Power Challenge shared-memory multi-processor. We further present a set of optimizations for the sequential and parallel algorithms. Experiments show that a significant improvement of performance is achieved using our proposed optimizations. We also achieved good speed-up for the parallel algorithm, but we observe a need for parallel I/O techniques for further performance gains.
Keywords: data mining; association rules; random sampling; Chernoff bounds.
Data mining is an emerging research area, whose goal is to extract significant patterns or interesting rules from large databases. High-level inference from large volumes of routine business data can provide valuable information to businesses, such as customer buying patterns, shelving criterion in supermarkets, and stock trends. However, many algorithms proposed for data mining of association rules make repeated passes over the database to determine the commonly occurring {\em itemsets} (or set of items). For large databases, the I/O overhead in scanning the database can be extremely high.In this paper we show that random sampling of transactions in the database is an effective method for finding association rules. Sampling can speed up the mining process by more than an order of magnitude by reducing I/O costs and drastically shrinking the number of transactions to be considered. We may also be able to make the sampled database resident in main-memory. Furthermore, we show that sampling can accurately represent the data patterns in the database with high confidence. We experimentally evaluate the effectiveness of sampling on three databases.
Keywords: real-time; multiprogramming; synchronization; scalable synchronization; adaptive runtime environment; Ephor; SPARTA.
Designing high performance parallel applications is a challenging task. The task becomes more difficult when these applications are on a multiprogrammed multiprocessor or function in the real world and need to meet real-time constraints. From the application's perspective these environments are unpredictable: under multiprogramming it is possible to be switched out at any time, and in the real world unexpected events can occur. Our thesis is that by sharing information across the traditional system-application interface we can achieve high performance in parallel applications both in the presence of multiprogramming and when meeting real-time constraints. The implemented techniques we describe not only perform better, but are simpler than those that would be required without such interaction. The contributions of this thesis, which are stated explicitly later, lie both in the mechanisms and techniques themselves and in the paradigm and implementation of the runtime environment that allows the mechanisms to exist.The mechanisms and techniques described throughout this thesis respond and adapt to unpredictable environments, whether caused by an unanticipated real-world event or an unexpected context switch. Synchronization is needed in almost all parallel programs, and, if oblivious to scheduler decisions, can have deleterious effects on application performance. We describe a set of {\em scheduler-conscious} and {\em preemption-safe} synchronization techniques that address the possibility of preemption on multiprogrammed multiprocessor machines. Mechanisms used in responding to the real world need to be flexible and adaptive. We describe a set of such mechanisms that allow real-time programs to adapt effectively to a changing and unpredictable world. We also describe a model for structuring the entire system (application, runtime, and kernel) in real-world environments.
Keywords: non-blocking; lock-free; mutual exclusion; locks; multiprogramming; concurrent queues; concurrent stacks; concurrent heaps; compare_and_swap; load_linked; store_conditional.
Most multiprocessors are multiprogrammed in order to achieve acceptable response time and to increase 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 structures: {\em preemption-safe locking} and {\em non-blocking} (lock-free) {\em 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.We focus in our study on four simple but important concurrent data structures---stacks, FIFO queues, priority queues and counters---in synthetic kernels and real applications on a 12-processor SGI Challenge multiprocessor. Our results indicate that efficient, data-structure-specific non-blocking algorithms, which exist for stacks, FIFO queues and counters, outperform both preemption-safe and ordinary locks by 20--40\% in real applications and 40--55\% in synthetic kernels on both multiprogrammed and dedicated systems (general-purpose non-blocking techniques do not yet appear to be practical). At the same time, preemption-safe locks outperform conventional locks by significant margins on multiprogrammed systems. The clear conclusion is that data-structure-specific non-blocking algorithms should be used whenever possible. For data structures for which such algorithms are not known, operating systems for multiprogrammed parallel machines should provide preemption-safe locks.
Drawing ideas from previous authors, we present a new non-blocking concurrent queue algorithm and a new two-lock queue algorithm in which one enqueue and one dequeue can proceed concurrently. Both algorithms are simple, fast, and practical; we were surprised not to find them in the literature. Experiments on a 12-node SGI Challenge multiprocessor indicate that the new non-blocking queue consistently outperforms the best known alternatives; it is the clear algorithm of choice for machines that provide a universal atomic primitive (e.g., compare_and_swap or load_linked/store_conditional). The two-lock concurrent queue outperforms a single lock when several processes are competing simultaneously for access; it appears to be the algorithm of choice for busy queues on machines with non-universal atomic primitives (e.g., test_and_set). Since much of the motivation for non-blocking algorithms is rooted in their immunity to large, unpredictable delays in process execution, we report experimental results both for systems with dedicated processors and for systems with several processes multiprogrammed on each processor.
Shared memory is widely believed to provide an easier programming model than message passing for expressing parallel algorithms. Distributed Shared Memory (DSM) systems provide the illusion of shared memory on top of standard message passing hardware at very low implementation cost, but provide acceptable performance for only a limited class of applications. We argue that the principal sources of overhead in DSM systems can be dramatically reduced with modest amounts of hardware support (substantially less than is required for hardware cache coherence). Specifically, we present and evaluate a family of protocols designed to exploit hardware support for a global, but non-coherent, physical address space. We consider systems both with and without remote cache fills, fine-grain access faults, "doubled" writes to local and remote memory, and merging write buffers. We also consider varying levels of latency and bandwidth. We evaluate our protocols using execution driven simulation, comparing them to each other and to a state-of-the-art protocol for traditional message-based networks. For the programs in our application suite, protocols taking advantage of the global address space improve performance by a minimum of 50% and sometimes by as much as an order of magnitude.
Keywords: barriers; synchronization; abstraction; communication topology.
Barriers are a simple, widely-used technique for synchronization in parallel applications. In regularly-structured programs, however, barriers can overly-constrain execution by forcing synchronization among processes that do not really share data. The topological barrier preserves the simplicity of traditional barriers while performing the minimum amount of synchronization actually required by the application. Topological barriers can easily be retro-fitted into existing programs. The only new burden on the programmer is the construction of a pair of functions to count and enumerate the neighbors of a given process. We describe the topological barrier in pseudo-code and pictures, and illustrate its performance on a pair of applications.
Keywords: adaptive real-time scheduling; SPARTAs; Ephor.
Scheduling involves deciding when to run a given task, how much time to allocate to it, and in a multiprocessing enironment where to run it. In this paper we focus on scheduling mechanisms for Soft PArallel Real-Time Applications (SPARTAs). The key element in the mechanisms we propose is their ability to adapt to a changing set of constraints allowing the application to adapt to a dynamic environment. These mechanisms take advantage of the fact that the real world can be modeled via continuous functions and that the derivative of a task's execution time is small. We present three mechanisms, one intended to provide guarantees similar to worst case scheduling, and two others designed to provided nearer to average case performance with analyzable deadline miss rates. We analyze the proposed scheduling policies and provide experimental results comparing their performance.
Keywords: customized dynamic load balancing; network of workstations; performance modeling; compile/run-time system.
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 examine the behavior of {\em global} vs {\em local}, and {\em centralized} vs {\em distributed}, load balancing strategies. We show that different schemes are best for different applications under varying program and system parameters. Therefore, customized load balancing schemes become 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.
Keywords: concurrent queue; lock-free; non-blocking; compare_and_swap; multiprogramming.
Drawing ideas from previous authors, we present a new non-blocking concurrent queue algorithm and a new two-lock queue algorithm in which one enqueue and one dequeue can proceed concurrently. Both algorithms are simple, fast, and practical; we were surprised not to find them in the literature. Experiments on a 12-node SGI Challenge multiprocessor indicate that the new non-blocking queue consistently outperforms the best known alternatives; it is the clear algorithm of choice for machines that provide a universal atomic primitive (e.g., compare_and_swap or load_linked/store_conditional). The two-lock concurrent queue outperforms a single lock when several processes are competing simultaneously for access; it appears to be the algorithm of choice for busy queues on machines with non-universal atomic primitives (e.g., test_and_set). Since much of the motivation for non-blocking algorithms is rooted in their immunity to large, unpredictable delays in process execution, we report experimental results both for systems with dedicated processors and for systems with several processes multiprogrammed on each processor.
Keywords: concurrency; lock-free; non-blocking; memory management; compare_and_swap.
Memory reuse in link-based lock-free data structures requires special care. Many lock-free algorithms require deleted nodes not to be reused until no active pointers point to them. Also, most lock-free algorithms use the compare_and_swap atomic primitive, which can suffer from the ``ABA problem'' associated with memory reuse. Valois ~\cite{Valois-thesis-1995} proposed a memory management method for link-based data structures that addresses these problems. The method associates a reference count with each node of reusable memory. A node is reused only when no processes or data structures point to it. The method solves the ABA problem for acyclic link-based data structures, and allows lock-free algorithms more flexibility as nodes are not required to be freed immediately after a delete operation (e.g.\ dequeue, pop, delete min, etc.). However, there are race conditions that may corrupt data structure that use this method. In this report we correct these race conditions and present a corrected version of Valois's method.
Keywords: inter-query parallelism; embedded SQL; dependence analysis.
Most parallel databases exploit two types of parallelism: intra-query parallelism and inter-transaction concurrency. Between these two cases lies another type of parallelism: inter-query parallelism within a transaction or application. Exploiting inter-query parallelism requires either compiler support to automatically parallelize the existing embedded query programs, or programming support to write explicitly parallel query programs.In this paper, we present compiler analysis to automatically detect parallelism in the embedded query programs. We present compiler dependence test algorithms for detecting both internal and external dependences. We show that the properties of some special functions such as MIN and MAX can help reduce dependences. Finally, we discuss the potential use of dependences to improve the performance of embedded query application programs.
Shared memory is widely regarded as a more intuitive model than message passing for the development of parallel programs. A shared memory model can be provided by hardware, software, or some combination of both. One of the most important problems to be solved in shared memory environments is that of cache coherence. Experience indicates, unsurprisingly, that hardware-coherent multiprocessors greatly outperform distributed shared-memory (DSM) emulations on message-passing hardware. Intermediate options, however, have received considerably less attention. We argue in this position paper that one such option---a multiprocessor or network that provides a global physical address space in which processors can make non-coherent accesses to remote mejory without trapping into the kernel or interrupting remote processors---can provide most of the performance of hardware cache coherence at little more monetary or design cost than traditional DSM systems. To support this claim we have developed the Cashmere family of software coherence protocols for NCC-NUMA (Non-Cache-Coherent, Non-Uniform_Memory-Access) systems, and have used execution-driven simulation to compare the performance of these protocols to that of full hardware coherence and distributed shared memory emulation. We have found that for a large class of applications the performance of NCC-NUMA multiprocessors rivals that of fully hardware-coherent designs, and significantly surpasses the performance realized on more traditional DSM systems.
Keywords: compiler optimizations; linearized array references.
Many powerful parallelizing compiler techniques rely on the structures of data and code. Unfortunately, in many real applications, arrays do not have syntactic structures. In this paper, we show that logical data structures can be automatically recovered from the flat, one-dimensional arrays and accesses. We present a framework and algorithms for recovering the logical multi-dimensional data structures.
Many powerful parallelizing compiler techniques rely on the structures of data and code. Unfortunately, in many real applications, arrays do not have syntactic structures. In this paper, we show that logical data structures can be automatically recovered from the flat, one-dimensional arrays and accesses. We present a framework and algorithms for recovering the logical multi-dimensional data structures.
In this paper, we study the problem of scheduling parallel loops at compile-time for a heterogeneous network of machines. We consider {\em heterogeneity} in three aspects of parallel programming: program, processor and network. A heterogeneous program has parallel loops with different amount of work in each iteration; heterogeneous processors have different speeds; and a heterogeneous network has different cost of communication between processors.We propose a simple yet comprehensive model for use in compiling for a network of processors, and develop compiler algorithms for generating {\em optimal} and {\em sub-optimal} schedules of loops for load balancing, communication optimizations and network contention. Experiments show that a significant improvement of performance is achieved using our techniques.
Almost every modern processor is designed with a memory hierarchy organized into several levels, each of which is smaller, faster, and more expensive than the level below. High performance requires the effective use of the cached data, i.e., cache locality. Smart compiler transformations can relieve the programmer from hand-optimizing for the specific machine architectures.Most of the existing compiler optimizations are developed for dense matrix programs. Irregular problems, on the other hand, have to rely on runtime optimizations, since the data access patterns are unknown at the compile-time. However, many scientific computing problems result in solving linear systems where the matrix of coefficients is {\em banded}, a structure known at the compile-time, but more complicated than the dense matrices. Banded matrix problems are interesting since substantial savings can be made by exploiting the mathematical properties of the bandedness. The complicated memory access patterns in the banded matrix programs make the existing compile-time optimizations impossible to use.
In this paper, we present a new compile-time technique for optimizing banded-matrix programs. We first develop a new data reuse model and an algorithm called {\em height reduction} to improve cache locality. Then with the height reduction algorithm, we extend loop tiling to exploit not only intra-tile data locality but also inter-tile data locality. We call the new tiling {\em affinity tiling}. We show that the algorithms also help to eliminate or reduce {\em false sharing} in multiprocessor systems. With the height reduction algorithm and affinity tiling, significant performance improvement (speedups from 2.5 to 10) has been observed on HP workstations (over the original sequential code) and KSR1 multiprocessors (over the original parallel code).
We present a unified approach to locality optimization that employs both data and control transformations. Data transformations include changing the array layout in memory. Control transformations involve changing the execution order of programs. We have developed new techniques for compiler optimizations for distributed shared-memory machines, although the same techniques can be used for sequential machines with a memory hierarchy.Our compiler optimizations are based on an algebraic representation of data mappings and a new data locality model. We present a pure data transformation algorithm and an algorithm unifying data and control transformations. While there has been much work on control transformations, opportunities for data transformations have been largely neglected. In fact, data transformations have the advantage of being applicable to programs that cannot be optimized with control transformations. The unified algorithm, which performs data and control transformations simultaneously, offers improvement over optimizations obtained by applying data and control transformations separately.
The experimental results using a set of applications on a parallel machine show that the new optimizations improve performance significantly. These results are further analyzed using locality metrics with instrumentation and simulation.
In this paper we present a summary of the issues that need to be dealt with to effectively use a heterogeneous network of machines. We specifically point out the impact of processor and memory heterogeneity on the performance of parallel programs. Our results indicate that processor speeds are application dependent and we show how to use this information along with memory constraints for efficient scheduling.
Keywords: parallel performance modeling; analysis; prediction.
The actual performance of parallel programs is often disappointing, especially in comparison to the peak performance offered by the underlying hardware. There are many sources of performance degradation and understanding these sources is necessary to improve application performance. In this paper we discuss performance modeling, an approach to understanding the performance of parallel systems. We present a survey of current approaches to modeling (both analytical modeling based on system parameters, and structural modeling based on the structure of the program), and propose a combination of these two approaches as a promising direction for new work. This combination is explored by evaluating and proposing improvements to lost cycles analysis, which already contains features from both approaches, and also combines measurement and modeling.
Scalable busy-wait synchronization algorithms are essential for achieving good parallel program performance on large scale multiprocessors. Such algorithms include mutual exclusion locks, reader-writer locks, and barrier synchronization. Unfortunately, scalable synchronization algorithms are particularly sensitive to the effects of multiprogramming: their performance degrades sharply when processors are shared among different applications, or even among processes of the same application. In this paper we describe the design and evaluation of scalable scheduler-conscious mutual exclusion locks, reader-writer locks, and barriers, and show that by sharing information across the kernel/application interface we can improve the performance of scheduler-oblivious implementations by more than an order of magnitude.
Keywords: communication bandwidth; communication latency; scalable multiprocessors; network and memory contention; latency tolerance.
The overhead of remote memory accesses is a major impediment to achieving good application performance on scalable shared-memory multiprocessors. This dissertation explores ways in which to exploit network and memory bandwidth in order to reduce the average cost of memory accesses. We consider scenarios in which (1) the remote access cost is dominated by contention, and (2) the hardware provides abundant bandwidth and the remote access time is dominated by the unsaturated request/access/reply sequence of operations. We introduce and evaluate two techniques for increasing the effective bandwidth available to processors, software interleaving and eager combining. We also evaluate strategies for hiding the high cost of remote accesses, including several forms of prefetching and update-based coherence protocols. We use both analytic models and detailed simulations of multiprocessor systems to quantify the effectiveness of these techniques, and to provide insight into the potential and limitations of exploiting bandwidth to reduce average memory access cost.
Keywords: parallel performance modeling; analysis; prediction.
Although there are many situations in which a model of application performance is valuable, performance modeling of parallel programs is not commonplace, largely because of the difficulty of developing accurate models of real applications executing on real multiprocessors. This paper describes a toolkit for performance tuning and prediction based on {\em lost cycles analysis}. Lost cycles analysis decomposes parallel overheads into meaningful categories that are amenable to modeling, and uses {\em a priori} knowledge of the sources and characteristics of overhead in parallel systems to guide and constrain the modeling process. The Lost Cycles Toolkit automates the process of constructing a performance model for a parallel application by integrating empirical model-building techniques from statistics with measurement and modeling techniques for parallel programs. We present several examples to show how the toolkit facilitates the construction of performance models, and to illustrate the use of the toolkit in solving practical performance problems.
The cost of a cache miss depends heavily on the location of the main memory that backs the missing line. For certain applications, this cost is a major factor in overall peformance. We report on the utility of OS-based page placement as a mechanism to increase the frequency with which cache fills access local memory in distributed shared memory multiprocessors. Even with the very simple policy of first-use placement, we find significant improvements over round-robin placement for many applications on both hardware- and software-coherent systems. For most of our applications, first-use placement allows 35 to 75 percent of cache fills to be performed locally, resulting in performance improvements of up to 40 percent with respect to round-robin placement. We were surprised to find no performance advantage in more sophisticated policies, including page migration and page replication. In fact, in many cases the performance of our applicauons suffered under these policies.
Keywords: Cashmere; software coherence; Net-NUMA; memory-mapped network interface, DSM.
Shared memory is widely believed to provide an easier programming model than message passing for expressing parallel algorithms. Distributed Shared Memory (DSM) systems provide the illusion of shared memory on top of standard message passing hardware at very low implementation cost, but provide acceptable performance on only a limited class of applications. In this paper we study the main sources of overhead found in software-coherent, distributed shared-memory systems and argue that recent revolutionary changes in network technology now allow us to design protocols that minimize such overheads and that approach the performance of full hardware coherence. Specifically, we claim that memory-mapped network interfaces that support a global physical address space can greatly improve the performance of DSM systems. To support this claim we study a variety of coherence protocols that can take advantage of the global physical address space and compare their performance with the best known protocol for pure message passing hardware. For the programs in our application suite, protocols taking advantage of the new hardware features improve performance by at least 50\% and by as much as an order of magnitude.
Keywords: parallel soft real time; real-time monitoring.
As real-time applications become more complex it is increasingly important to provide both a clean model for their development and the ability to verify that their execution matches the development model. In addition to becoming more complex, soft real-time programs are becoming more mainstream and are being run on platforms running some variant of Unix. It is even more important in these environments to be able to monitor a program and understand its behavior. We describe our frame scheduler, which provides a simple model to the real-time programmer while maintaining considerable flexibility. We motivate and describe the implementation of FrameView, a set of tools closely coupled with the frame scheduler. Since FrameView and the frame scheduler were developed in conjunction with each other, and are tightly coupled, they provide a powerful and efficient means for programmers to implement, analyze, and modify soft parallel real-time applications. The frame scheduler is fully implemented in IRIX 5.3, and FrameView is in beta release. In this paper we describe our experiences building and using the frame scheduler and FrameView.
Keywords: heterogeneous network of machines; PVM; processor heterogeneity---normalized processor speed; memory heterogeneity---resident memory size.
In this paper we present a summary of the issues that need to be dealt with to effectively use a heterogeneous network of machines. We specifically point out the impact of processor and memory heterogeneity on the performance of parallel programs. Our results indicate that processor speeds are application dependent and we show how to use this information along with memory constraints for efficient scheduling.
Keywords: parallel performance measurement; analysis; prediction; lost cycles.
Parallel programs often behave in unexpected ways due to the complex relationship between the structure of a parallel program, the machine on which it is run, the number of processors used, the program's input, and the measured running time of the program. As a result, performance tuning of parallel programs is an error-prone, time-consuming process.This dissertation describes a set of tools and methods for assisting the programmer in finding the best-performing implementation for a parallel program, and in answering common questions that arise during the performance tuning process. Our approach is based on three contributions: 1) new metrics for the measurement of parallel applications; 2) a new approach to the analysis of parallel program performance; and 3) a new modelling method that allows the programmer to predict the performance of a program in advance of a complete implementation. The metrics, which we call performance predicates, provide measurements that are amenable to analysis, and yet completely capture parallel overheads. The analysis method, lost cycles analysis, applies algorithmic analysis to parallel overheads, assisted by an on-line tool. The modelling method allows lost cycles analysis to be applied to program fragments, and provides rules for aggregating analytic results into a model for the execution time of a (possibly not-yet-implemented) parallel application. We use implementations of subgraph isomorphism and 2D FFT on the SGI Challenge Series and KSR1 multiprocessors to illustrate our methods and tools, and show how our approach can be used to explain surprising performance results and predict the performance of alternative implementations of an application in advance of implementation, while avoiding large numbers of measurements for performance tuning.
In this paper we consider several hardware implementations of the general-purpose atomic primitives fetch_and_Phi, compare_and_swap, load_linked, and store_conditional on large-scale shared-memory multiprocessors. These primitives have proven popular on small-scale bus-based machines, but have yet to become widely available on large-scale, distributed shared memory machines. We propose several alternative hardware implementations of these primitives, and then analyze the performance of these implementations for various data sharing patterns. Our results indicate that good overall performance can be obtained by implementing compare_and_swap in the cache controllers, and by providing an additional instruction to load an exclusive copy of a cache line.
Keywords: cache coherence; scalability; cost-effectiveness; lazy release consistency; NCC-NUMA machines.
Shared memory is an appealing abstraction for parallel programming. It must be implemented with caches in order to perform well, however, and caches require a coherence mechanism to ensure that processors reference current data. Hardware coherence mechanisms for large-scale machines are complex and costly, but existing software mechanisms for message-passing machines have not provided a performance-competitive solution. We claim that an intermediate hardware option---memory-mapped network interfaces that support a global physical address space---can provide most of the performance benefits of hardware cache coherence. We present a software coherence protocol that runs on this class of machines and greatly narrows the performance gap between hardware and software coherence. We compare the performance of the protocol to that of existing software and hardware alternatives and evaluate the tradeoffs among various cache-write policies. We also observe that simple program changes can greatly improve performance. For the programs in our test suite and with the changes in place, software coherence is often faster and never more than 55% slower than hardware coherence.
Traditional supercomputers use a flat multi-bank SRAM memory organization to supply high bandwidth at low latency. Most other computers use a hierarchical organization with a small SRAM cache and slower, cheaper DRAM for main memory. Such systems rely heavily on data locality for achieving optimum performance. This paper evaluates cache-based memory systems for vector supercomputers. We develop a simulation model for a cache-based version of the Cray Research C90 and use the NAS parallel benchmarks to provide a large scale workload. We show that while caches reduce memory traffic and improve the performance of plain DRAM memory, they still lag behind cacheless SRAM. We identify the performance bottlenecks in DRAM-based memory systems and quantify their contribution to program performance degradation. We find the data fetch strategy to be a significant parameter affecting performance, evaluate the performance of several fetch policies, and show that small fetch sizes improve performance by maximizing the use of available memory bandwidth.
Keywords: concurrency; concurrent priority queue; heap; bit-reverse.
We present a new algorithm for concurrent access to array-based priority queue heaps. Deletions proceed top-down as they do in a previous algorithm due to Rao and Kumar [1988 (IEEE Trans. Computers 37(12))], but insertions proceed bottom-up, and consecutive insertions use a bit-reversal technique to scatter accesses across the fringe of the tree, to reduce contention. Because insertions do not have to traverse the entire height of the tree (as they do in previous work), as many as O(M) operations can proceed in parallel, rather than O(log M) on a heap of size M. Experimental results on a Silicon Graphics Challenge multiprocessor demonstrate good overall performance for the new algorithm on small heaps, and significant performance improvements over known alternatives on large heaps with mixed insertion/deletion workloads.
Keywords: synchronization; scheduler-conscious synchronization; preemption-safe synchronization.
Efficient synchronization is important for achieving good performance in parallel programs, especially on large-scale multiprocessors. Most synchronization algorithms have been designed to run on a dedicated machine, with one application process per processor, and can suffer serious performance degradation in the presence of multiprogramming. Problems arise when running processes block or, worse, busy-wait for action on the part of a process that the scheduler has chosen not to run.In this paper we describe and evaluate a set of scheduler-conscious synchronization algorithms that perform well in the presence of multiprogramming while maintaining good performance on dedicated machines. We consider both large and small machines, with a particular focus on scalability, and examine mutual-exclusion locks, reader-writer locks, and barriers. The algorithms we study fall into two classes: those that heuristically determine appropriate behavior and those that use scheduler information to guide their behavior. We show that while in some cases either method is sufficient, in general sharing information across the kernel-user interface both eases the design of synchronization algorithms and improves their performance.
Scalable busy-wait synchronization algorithms are essential for achieving good parallel program performance on large scale multiprocessors. Such algorithms include mutual exclusion locks, reader-writer locks, and barrier synchronization. Unfortunately, scalable synchronization algorithms are particularly sensitive to the effects of multiprogramming: their performance degrades sharply when processors are shared among different applications, or even among processes of the same application. In this paper we describe the design and evaluation of scalable scheduler-conscious mutual exclusion locks, reader-writer locks, and barriers, and show that by sharing information across the kernel/application interface we can improve the performance of scheduler-oblivious implementations by more than an order of magnitude.
Keywords: cache coherence; lazy release consistency; scalable shared memory; programmable protocol processors; false sharing.
Release consistency is a widely accepted memory model for distributed shared memory systems. It provides significant opportunities for a coherence protocol to improve performance by delaying and buffering coherence operations. Different protocol implementations exploit these opportunities to different extents. Eager release consistency represents the state of the art for hardware-coherent multiprocessors, while lazy release consistency has been shown to provide better performance for software distributed shared memory (DSM). Several of the optimizations performed by lazy protocols have the potential to improve the performance of hardware-coherent multiprocessors, but their complexity has precluded a hardware implementation. With the advent of programmable protocol processors it may become possible to use them after all.We present and evaluate a lazy release-consistent protocol suitable for machines with dedicated protocol processors. This protocol admits multiple concurrent writers, sends write notices concurrently with computation, and delays invalidations until acquire operations. We also consider a lazier protocol that delays sending write notices until release operations. Our results indicate that the first protocol outperforms eager release consistency by as much as 20\% across a variety of applications. The lazier protocol, on the other hand, is unable to recoup its high synchronization overhead. This represents a qualitative shift from the DSM world, where lazier protocols always yield performance improvements. We also study protocol performance under a variety of architectural settings and show that the performance gap between lazy and eager implementations of release consistency will increase on future machines. Based on our results, we conclude that machines with flexible hardware support for coherence should use protocols based on lazy release consistency, but in a less ``aggressively lazy'' form than is appropriate for DSM.
We argue that OS-provided data coherence on non-cache-coherent NUMA multiprocessors (machines with a single, global physical address space) can perform substantially better than distributed shared memory emulations on message-passing hardware, and almost as well as fully cache-coherent multiprocessors.
Keywords: unified data and control transformation; locality optimization; distributed shared memory machines; data mapping; mapping vector; locality model; stride vector.
We present a unified approach to locality optimization that employs both data and control transformations. Data transformations include changing the array layout in memory. Control transformations involve changing the execution order of programs. We have developed new techniques for compiler optimizations for distributed shared-memory machines, although the same techniques can be used for sequential machines with a memory hierarchy.Our compiler optimizations are based on an algebraic representation of data mappings and a new data locality model. We present a pure data transformation algorithm and an algorithm unifying data and control transformations. While there has been much work on control transformations, the opportunities for data transformations have been largely neglected. In fact, data transformations have the advantage of being applicable to programs that cannot be optimized with control transformations. The unified algorithm, which performs data and control transformations simultaneously, offers improvement over optimizations obtained by applying data and control transformations separately.
The experimental results using a set of applications on a parallel machine show that the new optimizations improve performance significantly. These results are further analyzed using locality metrics with instrumentation and simulation.
Keywords: compiling for network of workstations; machine model; static scheduling; bitonic scheduling; heterogeneous computing; contention avoidance.
In this paper, we study the problem of scheduling parallel loops at compile-time for a heterogeneous network of machines. We consider heterogeneity in three aspects of parallel programming: program, processor and network. A heterogeneous program has parallel loops with different amount of work in each iteration; heterogeneous processors have different speeds; and a heterogeneous network has different cost of communication between processors.We propose a simple yet comprehensive model for use in compiling for a network of processors, and develop compiler algorithms for generating optimal and sub-optimal schedules of loops for load balancing, communication optimizations and network contention. Experiments show that significant improvement of performance is achieved using our techniques.
Keywords: invalidations; updates; scalable multiprocessors; coherence protocols.
Cache coherence protocols for shared-memory multiprocessors use invalidations or updates to maintain coherence across processors. Although invalidation protocols usually produce higher miss rates, update protocols typically perform worse. Detailed simulations of these two classes of protocol show that the excessive network traffic caused by update protocols significantly degrades performance, even with infinite bandwidth. Motivated by this observation, we categorize the coherence traffic in update-based protocols and show that, for most applications, more than 90\% of all updates generated by the protocol are unnecessary. We identify application characteristics that generate useless update traffic, and compare the isolated and combined effects of several software and hardware techniques for eliminating useless updates. These techniques include dynamic and static hybrid protocols, false sharing elimination strategies, and coalescing write buffers. Our simulations show that software caching (where coherence is managed under programmer or compiler control) and the dynamic hybrid protocol reduce useless updates the most, but coalescing write buffers produce fewer, albeit larger, coherence messages. As a result, coalescing write buffers usually produce the best running time, except when the block size is large or the bandwidth is limited. Finally, based on the observation that the techniques we consider are unable to eliminate a large number of useless updates, we suggest directions for further reducing the useless traffic in update-based protocols.
Shared memory provides an attractive and intuitive programming model for large-scale parallel computing, but requires a coherence mechanism to allow caching for performance while ensuring that processors do not use stale data in their computation. Implementation options range from distributed shared memory emulations on networks of workstations to tightly-coupled fully cache-coherent distributed shared memory multiprocessors. Previous work indicates that performance varies dramatically from one end of this spectrum to the other. Hardware cache coherence is fast, but also costly and time-consuming to design and implement, while DSM systems provide acceptable performance on only a limited class of applications. We claim that an intermediate hardware option---memory-mapped network interfaces that support a global physical address space, without cache coherence---can provide most of the performance benefits of fully cache-coherent hardware, at a fraction of the cost. To support this claim we present a software coherence protocol that runs on this class of machines, and use simulation to conduct a performance study. We look at both programming and architectural issues in the context of software and hardware coherence protocols. Our results suggest that software coherence on NCC-NUMA machines is a more cost-effective approach to large-scale shared-memory multiprocessing than either pure distributed shared memory or hardware cache coherence.
Keywords: locality; migration; replication; placement.
The cost of a cache miss depends heavily on the location of the main memory that backs the missing line. For certain applications, this cost is a major factor in overall performance. We report on the utility of OS-based page placement as a mechanism to increase the frequency with which cache fills access local memory in a distributed shared memory multiprocessor. Even with the very simple policy of first-use placement, we find significant improvements over round-robin placement for many applications on both hardware and software-coherent systems. For most of our applications, dynamic placement allows 35 to 75 percent of cache fills to be performed locally, resulting in performance improvements of 20 to 40 percent.We have also investigated the performance impact of more sophisticated policies including hardware support for page placement, dynamic page migration, and page replication. We were surprised to find no performance advantage for the more sophisticated policies; in fact in most cases performance of our applications suffered.
Keywords: multiprocessor communication; cache coherence protocols; write invalidate; write update; scalable multiprocessors.
In this paper we present simulation algorithms that characterize the main sources of communication generated by parallel applications under both invalidate and update-based cache coherence protocols. The algorithms provide insight into the reference and sharing patterns of parallel programs and into the amount of useless traffic entailed by each coherence protocol. Under an invalidate-based protocol, our algorithms classify the data traffic caused by the different types of cache misses. Under an update-based protocol, our algorithms not only categorize the data traffic, but also classify update transactions with respect to the sharing patterns that caused them. Although our algorithms deal with numerous hardware features, our categorization is widely applicable and can be easily simplified for use in less detailed simulators.
In a previous article, Gupta and Hill introduced an adaptive combining tree algorithm for busy-wait barrier synchronization on shared-memory multiprocessors. The intent of the algorithm was to achieve a barrier in logarithmic time when processes arrive simultaneously, and in constant time after the last arrival when arrival times are skewed. A fuzzy version of the algorithm allows a process to perform useful work between the point at which it notifies other processes of its arrival and the point at which it waits for all other processes to arrive.Unfortunately, adaptive combining tree barriers as originally devised perform a large amount of work at each node of the tree, including the acquisition and release of locks. They also perform an unbounded number of accesses to non-local locations, inducing large amounts of memory and interconnect contention. We present new adaptive combining tree barriers that eliminate these problems. We compare the performance of the new algorithms to that of other fast barriers on a 64-node BBN Butterfly 1 multiprocessor, a 35-node BBN TC2000, and a 126-node KSR 1. The results reveal scenarios in which our algorithms outperform all known alternatives, and suggest that both adaptation and the combination of fuzziness with tree-style synchronization will be of increasing importance on future generations of shared-memory multiprocessors.
Keywords: synchronization; scalability; fetch-and-\Phi; compare-and-swap; load-linked; store-conditional; cache coherence.
Many hardware primitives have been proposed for synchronization and atomic memory update on shared-memory multiprocessors. In this paper, we focus on general-purpose primitives that have proven popular on small-scale bus-based machines, but have yet to become widely available on large-scale, distributed-memory machines. Specifically, we propose several alternative implementations of fetch_and_\Phi, compare_and_swap, and load_linked/store_conditional. We then analyze the performance of these implementations for various data sharing patterns, in both real and synthetic applications. Our results indicate that good overall performance can be obtained by implementing compare_and_swap in a multiprocessor's cache controllers, and by providing an additional instruction to load an exclusive copy of a line.
Scalable busy-wait synchronization algorithms are essential for achieving good parallel program performance on large scale multiprocessors. Such algorithms include mutual exclusion locks, reader-writer locks, and barrier synchronization. Unfortunately, scalable synchronization algorithms are particularly sensitive to the effects of multiprogramming: their performance degrades sharply when processors are shared among different applications, or even among processes of the same application. In this paper we describe the design and evaluation of scalable scheduler-conscious mutual exclusion locks, reader-writer locks, and barriers, and show that by sharing information across the kernel-application interface we can achieve good performance in the presence of multiprogramming.
Mercury is a system designed to explore methods for improving the performance of "natural grain" parallel object-oriented programs on shared memory multiprocessors with hardware-coherent caches. The novel aspects of Mercury are a locality-conscious implementation of user-level threads, new scheduling techniques based on object affinity, and a lightweight task management mechanism that uses coarse-grain dataflow techniques to reduce the costs of scheduling, synchronizing, and dispatching units of work. By using this combination of techniques to control the overhead of parallelism and to increase locality of reference, Mercury can run relatively fine-grain programs with levels of performance approaching those obtained by hand-tuned coarse-grain programs. We describe the implementation of Mercury and present experimental results on its performance.
MINT is a software package designed to ease the process of constructing event-driven memory hierarchy simulators for multiprocessors. It provides a set of simulated processors that run standard Unix executable files compiled for a MIPS R3000 based multiprocessor. These generate multiple streams of memory reference events that drive a user-provided memory system simulator. MINT uses a novel hybrid technique that exploits the best aspects of native execution and software interpretation to minimize the overhead of processor simulation. Combined with related techniques to improve performance, this approach makes simulation on uniprocessor hosts extremely efficient.MINT runs on MIPS-based machines including those from Silicon Graphics and Digital Equipment Corporation. The source code for MINT is available by anonymous ftp from cs.rochester.edu and includes a tutorial and user manual.
Keywords: remote access latency; cache-coherent multiprocessors; spatial locality; stride-directed prefetching; software prefetching; execution-driven simulation.
Prefetching is an important technique for reducing the average latency of memory accesses in scalable cache-coherent multiprocessors. Aggressive prefetching can significantly reduce the number of cache misses, but may introduce bursty network and memory traffic, and increase data sharing and cache pollution. Given that we anticipate enormous increases in both network bandwidth and latency, we examine whether aggressive prefetching triggered by a miss (cache-miss-initiated prefetching) can substantially improve the running time of parallel programs.Using execution-driven simulation of parallel programs on a scalable cache-coherent machine, we study the performance of three cache-miss-initiated prefetching techniques: large cache blocks, sequential prefetching, and hybrid prefetching. Large cache blocks (which fetch multiple words within a single block) and sequential prefetching (which fetches multiple consecutive blocks) are well-known prefetching strategies. Hybrid prefetching is a novel technique combining hardware and software support for stride-directed prefetching.
Our simulation results show that large cache blocks rarely provide significant performance improvements; the improvement in the miss rate is often too small (or nonexistent) to offset a corresponding increase in the miss penalty. Our results also show that sequential and hybrid prefetching perform better than prefetching via large cache blocks, and that hybrid prefetching performs at least as well as sequential prefetching. In fact, given sufficiently high bandwidth and regular memory addressing, hybrid prefetching can perform as well as software prefetching (which does not require a miss to initiate prefetching). We conclude that among the cache-miss-initiated prefetching techniques we consider, hybrid prefetching is the only technique that offers significant performance improvements for scalable multiprocessors.
Large scale multiprocessors can provide the computational power needed to solve some of the larger problems of science and engineering today. Shared memory provides an attractive and intuitive programming model that makes good use of programmer time and effort. Shared memory, however, requires a coherence mechanism to allow caching for performance and to ensure that processors do not use stale data in their computation. Directory-based coherence, which is the hardware mechanism of choice for large scale multiprocesssors, can be expensive both in terms of hardware cost and in terms of the intellectual effort needed to design a correct, efficient protocol. For scalable multiprocessor designs with network-based interconnects, software-based coherence schemes provide an attractive alternative. In this paper we evaluate a new adaptive software coherence protocol, and demonstrate that smart software coherence protocols can be competitive with hardware-based coherence for a large variety of programs. We then discuss issues that affect the performance of software coherence protocols and proceed to suggest algorithmic and architectural enhancements that can help improve software coherence performance.
Our research addresses the general topic of atomic update of shared data structures on large-scale shared-memory multiprocessors. In this paper we consider alternative implementations of the general-purpose single-address atomic primitives fetch_and_Phi, compare_and_swap, 1oad_linked, and store_conditiona1. These primitives have proven popular on small-scale bus-based machines, but have yet to become widely available on large-scale, distributed shared memory machines. We propose several alternative hardware implementations of these primitives, and then analyze the performance of these implementations for various data sharing patterns. Our results indicate that good overall performance can be obtained by implementing compare_and_swap in the cache controllers, and by providing an additional instruction to load an exclusive copy of a cache line.
Keywords: cache coherence; scalability; cost-effectiveness; lazy release consistency; NCC-NUMA machines.
Shared memory provides an attractive and intuitive programming model that makes good use of programmer time and effort. Shared memory, however, requires a coherence mechanism to allow caching for performance and to ensure that processors do not use stale data in their caches. We evaluate several algorithmic and architectural alternatives in the design space of NCC-NUMA (non cache coherent, non uniform memory access) machines with a globally-accessible physical address space. We present a new adaptive algorithm for software cache coherence that reduces interprocessor communication and scales to large numbers of processors; we compare it to existing software and hardware coherence schemes. We also evaluate (1) the tradeoffs among various write policies (write-through, write-back, write-through with a write-collect buffer) and (2) the effect on performance of using remote memory access. Finally, we observe that certain simple program changes can greatly improve performance. For example, we find that the use of reader-writer locks, synchronization variable relocation, and data structure padding and alignment can allow a protocol to avoid significant amounts of coherence overhead. (A later version of this paper appeared in HPCA, January 1995.)
Keywords: parallel programming; parallelizing compilers; loop transformations; linear transformations; nonsingular transformation.
Loop transformations are becoming critical to exploiting parallelism and data locality in parallelizing and optimizing compilers. This document describes the Lambda loop transformation toolkit, an implementation of the non-singular matrix transformation theory, which can represent any linear one-to-one transformation.Lambda has a simple interface, and is independent of any compiler intermediate representation. It has been used in parallelizing compilers for multiprocessor machines as well as optimizing compilers for uniprocessor machines.
Keywords: memory hierarchy; distributed shared memory architectures; data locality; cache coherence; false sharing; compiler optimizations; loop transformations; non-singular transformations; loop tiling; banded matrix problems.
Almost every modern processor is designed with a memory hierarchy organized into several levels, each of which is smaller, faster, and more expensive than the level below. High performance requires the effective use of the cached data, i.e., cache locality. Smart compiler transformations can relieve the programmer from hand-optimizing for the specific machine architectures.In a multiprocessor system, data inconsistency may occur between memory and caches. For example, the memory and multiple caches may have inconsistent copies of the same cache block. This introduces the problem of cache coherence. Several cache coherence protocols have been developed to maintain data coherence for multiple processors. Since multiple variables are located in the same block, it may cause the problem of false sharing, which has been identified by many researchers as a major obstacle to high performance. Therefore, in a multiprocessor system, we need to avoid false sharing as well as exploit cache locality.
In this paper, we first develop a new data reuse model and an algorithm called height reduction to improve cache locality. The advantage of this algorithm is that it can improve band matrix programs as well as dense matrix programs. It is more accurate and general than the existing techniques on improving cache locality, which were developed to optimize dense matrix programs. Then with the height reduction algorithm, we extend loop tiling to exploit not only intra-tile data locality but also inter-tile data locality. We call the new tiling affinity tiling. Our experiments show that affinity tiling is less sensitive to the choice of the tile size. Finally, we show that the algorithm also helps to eliminate or reduce false sharing in multiprocessor systems. With the height reduction algorithm and affinity tiling, significant performance improvement (speedups from 2.5 to 10) has been observed on HP workstations and KSR1 multiprocessors.
Keywords: coherency; protocol; multiprocessor; Alpha microprocessor; performance.
Since data access patterns vary from application to application, neither write-invalidate nor write-update is the better strategy for maintaining cache coherence in all cases. Thus, it may be advantageous to use a hybrid cache coherency protocol that combines the best aspects of each. Although write-invalidate is the dominant approach in commercial multiprocessors, the recent introduction of coalescing write buffers combined with relaxed models of memory consistency can be expected to improve the performance of protocols based on updating. This motivates our re-examination of the relative performance of write-invalidate, write-update, and on-line dynamic hybrid protocols. Using a detailed program-driven simulation of a high-performance bus-based multiprocessor with release-consistent caching, we compare the performance of several variations on the hybrid protocol used in DEC AXP multiprocessors with the performance of several more conventional protocols. The variations on the hybrid protocol are introduced to correct weaknesses that appeared during the study. Though coalescing write buffers offer large performance improvements to the protocols that use update, conventional write-invalidate protocols also benefit. It appears that, although hybrid protocols do not offer any significant advantage over the best choice of pure protocol for a particular program, they may offer good performance over a wider range of applications than any single pure protocol.
Keywords: cache block size; network bandwidth and latency; locality enhancement; memory bandwidth and latency; scalable multiprocessors.
An important architectural design decision affecting the performance of coherent caches in shared-memory multiprocessors is the choice of block size. There are two primary factors that influence this choice: the reference behavior of application programs and the remote access bandwidth and latency of the machine. Several studies have shown that increasing the block size can lower the miss rate and reduce the number of invalidations. However, increasing the block size can also increase the miss rate by, for example, increasing false sharing or the number of cache evictions. Large cache blocks can also generate network contention. Given that we anticipate enormous increases in both network bandwidth and latency in large-scale, shared-memory multiprocessors, the question arises as to what effect these increases will have on the choice of block size.We use analytical modeling and execution-driven simulation of parallel programs on a large-scale shared-memory machine to examine the relationship between cache block size and application performance as a function of remote access bandwidth and latency. We show that even under assumptions of high remote access bandwidth, the best application performance usually results from using cache blocks between 32 and 128 bytes in size. Using even larger blocks tends to increase the mean cost per reference, either because the miss rate increases or because the improvement in the miss rate is not enough to offset the increase in the miss penalty associated with larger blocks. We also show that modifying the program to remove the dominant source of misses may not help; the modified program could have a lower overall miss rate, but perform best with even smaller cache blocks. Since there are many factors that limit improvements in the miss rate with an increase in block size, and since the remote access bandwidth and latency limit the extent to which an improvement in the miss rate results in a lower mean cost per reference, we conclude that large cache blocks cannot be justified in most realistic scenarios.
Keywords: non-uniform distribution of accesses; memory and network bandwidth; contention; scalable multiprocessors; coherency protocols.
One common cause of poor performance in large-scale shared-memory multiprocessors is limited memory or interconnection network bandwidth. Even well-designed machines can exhibit bandwidth limitations when a program issues an excessive number of remote memory accesses or when remote accesses are distributed non-uniformly. While techniques for improving locality of reference are often successful at reducing the number of remote references, a non-uniform distribution of references may still result, which can cause contention both in the interconnection network and at remote memories.Producer/consumer data, where one processor (the producer) writes data that many other processors (the consumers) must read, is a common sharing pattern in parallel programs that generates a non-uniform distribution of references. In this paper we quantify the performance impact of producer/consumer sharing as a function of memory and network bandwidth, and argue that the contention caused by this form of sharing can severely impact performance on large-scale machines. We then propose a new coherency protocol, called eager combining, which is designed to alleviate this contention. The protocol replicates the producer's data among multiple memory modules, thereby effectively increasing both the memory and network bandwidth of the producer, and dramatically decreasing the remote access latency of consumers. We compare eager combining to other techniques for reducing or eliminating contention, and use execution-driven simulation of parallel programs on a large-scale multiprocessor to show that eager combining can improve performance by a factor of 4 or more when used for programs with producer/consumer data on machines with hundreds of processors.
Synchronization primitives for large shared-memory multiprocessors need to minimize latency and contention. Software queue-based locks address these goals, but suffer if a process near the end of the queue waits for a preempted process ahead of it. To solve this problem, we present two queue-based locks that recover from in-queue preemption. The simpler, faster lock employs an extended kernel interface that shares information in both directions across the user-kernel boundary. Results from experiments with real and synthetic applications on SGI and KSR multiprocessors demonstrate that high-performance software spin locks are compatible with multiprogramming on both large-scale and bus-based machines.
Keywords: parallel performance prediction; performance evaluation; performance predicates; lost cycles.
Traditional performance debugging and tuning of parallel programs is based on the "measure-modify" approach, in which detailed measurements of program executions are used to guide incremental changes to the program that result in better performance. Unfortunately, the performance of a parallel algorithm is often related to its implementation, input data, and machine characteristics in surprising ways, and the "measure-modify" approach is unsuited to exploring these relationships fully: it is too heavily dependent on experimentation and measurement, which is impractical for studying the large number of variables that can affect parallel program performance. In this paper we argue that the problem of selecting the best implementation of a parallel algorithm requires a new approach to parallel program performance evaluation, one with a greater balance between measurement and modeling. We first present examples that demonstrate that different parallelizations of a program may be necessary to achieve the best possible performance as one varies the input data, machine architecture, or number of processors used. We then present an approach to performance evaluation based on lost cycles analysis, which involves measurement and modeling of all sources of overhead in a parallel program. We describe a measurement tool for lost cycles analysis that we have incorporated into the runtime environment for Fortran programs on the Kendall Square KSR1, and use this tool to analyze the performance tradeoffs among implementations of 2D FFT and parallel subgraph isomorphism. Using these examples, we show how lost cycles analysis can be used to solve the problems associated with selecting the best implementation in a variable environment. In addition, we show that this approach can capture large amounts of performance data using only a small number of measurements, and that it is flexible enough to allow conclusions to be drawn from empirical data in some cases, and analytic results in other cases.
Keywords: NSF CDA-8822724; DARPA MDA972-92-J-1012.
Integrated, flexible, surviving, autonomous AI systems are on the horizon, raising new issues in systems support. These systems typically embody hard real-time constraints (for servoing) and soft real-time constraints (solving problems to some level of effectiveness within some time constraints). We assume an adequate hard real-time control substrate, and are concerned here with resource allocation for high-level decision-making in Soft PArallel Real-Time ApplicationS (SPARTAS). Such applications only need to respond to their environment quicker than their environment can dramatically change on them. SPARTAS often generate behavior by running high-level algorithms based on a model of the world and on information from the environment. Designing an executive for SPARTAS is challenging, since in its full generality it calls for dynamic decision-making about resource allocation, scheduling, choice of methods, and handling reflexive or reactive behavior smoothly within a context of planned or intended actions, and a host of other issues not typically encountered either in off-line or hard real-time applications. An important aspect of the environment for a SPARTA is its own state; what resources are being used for what purposes, and which are available. Modern SPARTAS are written on parallel computers, further complicating matters. We are designing Ephor, a run-time envirobnment for parallel machines to alleviate some of the difficulties faced by a SPARTA programmer. In this paper we briefly describe Ephor, show how it allows simpler application code, and demonstrate that Ephor improves problem-solving performance in the presence of varying internal system state by dynamically choosing between different planners.
Keywords: DARPA MDA972-92-J-1012; DARPA N00014-92-J-1801; NSF CDA-8822724.
Parallel programs frequently use barriers to synchronize successive steps in an algorithm. In the presence of multiprogramming the choice of spinning versus blocking barriers can have a significant impact on performance. We demonstrate how competitive spinning techniques previously designed for locks can be extended to barriers, and we evaluate their performance. We design an additional competitive spinning technique that adapts more quickly in a dynamic environment. We then propose and evaluate a new method that obtains better performance than previous techniques by using scheduler information to decide between spinning and blocking. The scheduler information technique makes optimal choices incurring little overhead.
Keywords: NSF IIP CDA-8822724; ONR/DARPA N00014-92-J-1801; NSF Psyche CCR-9005633.
Keywords: Mercury; Presto; NUMA; C++; parallel programming library; lightweight threads; object-affinity scheduling.
It is common for parallel applications to require a large number of threads of control, often much larger than the number of processors provided by the underlying hardware. Using heavyweight (Unix style) processes to implement those threads of control is prohibitively expensive. Mercury is an environment for writing object-oriented parallel programs in C++ that provides the user with simple primitives for inexpensive thread creation and blocking and spinning synchronization. If required, Mercury primitives allow the user to control scheduling decisions in order to achieve good locality of reference in non uniform memory access (NUMA) multiprocessors. This paper describes the basic Mercury primitives and provides examples of their use.
Loops are the single largest source of parallelism in many applications. One way to exploit this parallelism is to execute loop iterations in parallel on different processors. Previous approaches to loop scheduling attempt to achieve the minimum completion time by distributing the workload as evenly as possible, while minimizing the number of synchronization operations required. In this paper we consider a third dimension to the problem of loop scheduling on shared-memory multiprocessors: communication overhead caused by accesses to non-local data. We show that traditional algorithms for loop scheduling, which ignore the location of data when assigning iterations to processors, incur a significant performance penalty on modern shared-memory multiprocessors. We propose a new loop scheduling algorithm that attempts to simultaneously balance the workload, minimize synchronization, and co-locate loop iterations with the necessary data. We compare the performance of this new algorithm to other known algorithms using five representative kernel programs on a Silicon Graphics multiprocessor workstation, a BBN Butterfly, a Sequent Symmetry, and a KSR-1, and show that the new algorithm offers substantial performance improvements, up to a factor of 4 in some cases. We conclude that loop scheduling algorithms for shared-memory multiprocessors cannot afford to ignore the location of data, particularly in light of the increasing disparity between processor and memory speeds.
False sharing occurs when processors in a shared-memory parallel system make references to different data objects within the same coherence block (cache line or page), thereby inducing "unnecessary" coherence operations. False sharing is widely believed to be a serious problem for parallel program performance, but a precise definition and quantification of the problem has proven to be elusive. We explain why. In the process, we present a variety of possible definitions for false sharing, and discuss the merits and drawbacks of each. Our discussion is based on experience gained during a four-year study of multiprocessor memory architecture and its effect on the behavior of applications in a sixteen-program suite.Using trace-based simulation, we present experimental evidence to support the claim that false sharing is a serious problem. Unfortunately, we find that the various computationally tractable approaches to quantifying the problem are either heuristic in nature, or fail to agree with intuition.
Programmers want shared memory. They can get it on special-purpose multiprocessor architectures, but the speed of technological improvements makes it difficult for these architectures to compete with systems built from commodity parts. Shared-memory parallel programming on distributed systems is therefore an appealing idea, but it isn't practical yet. Practicality will hinge on a prudent mix of compiler technology, dynamic data placement with relaxed consistency, and simple hardware support.
Keywords: parallel programming; shared memory; cache organization; scalable multiprocessors.
Several studies have shown that the performance of coherent caches depends on the relationship between the cache block size and the granularity of sharing and locality exhibited by the program. Large cache blocks exploit processor and spatial locality, but may cause unnecessary cache invalidations due to false sharing. Small cache blocks can reduce the number of cache invalidations, but increase the number of bus or network transactions required to load data into the cache. In this dissertation we use reference traces from a variety of parallel programs and detailed simulation of a scalable shared-memory multiprocessor to examine the effects of cache block size on the performance of coherent caches and quantify this impact with respect to the network bandwidth and latency.Our results suggest that, regardless of the available bandwidth or latency, applications with good spatial locality favor long cache lines, and for these applications the relative benefits of longer cache lines increase with the bandwidth and latency. For those applications with poor spatial locality, the best choice of cache line size is determined by the product of the network bandwidth and latency, and for these applications, the performance penalty induced by long cache lines increases as this product decreases. We also found that the performance penalty of a mismatch between the cache block size and the sharing patterns exhibited by applications increases with an increase in latency, and decreases with an increase in bandwidth, and can be substantial even on machines with infinite bandwidth.
To reduce this penalty we propose a new cache organization that adjusts the size of data blocks dynamically according to recent reference patterns. In this new cache organization, blocks are split in two when false sharing occurs, and merged back together to exploit spatial locality. Results of simulations in which we varied both the network bandwidth and latency indicate that, for the suite of applications we consider, the adjustable block size cache organization performs better than every fixed block size alternative (including caches that prefetch multiple lines). In addition, the performance benefits of adjustable block size caches increase with an increase in the ratio of network latency to bandwidth. We conclude that adjusting the block size in response to reference behavior can significantly improve the performance of coherent caches, especially when there is variability in the granularity of sharing exhibited by applications.
Keywords: synchronization; mutual exclusion; backoff; Lamport's fast mutual exclusion algorithm; multiprocessing; algorithms.
We present a mutual exclusion algorithm that performs well both with and without contention, on machines with no atomic instructions other than read and write. The algorithm capitalizes on the ability of memory systems to read and write at both full- and half-word granularities. It depends on predictable processor execution rates, but requires no bound on the length of critical sections, performs only O(n) total references to shared memory when arbitrating among conflicting requests (rather than O(n^2) in the general version of Lamport's fast mutual exclusion algorithm), and performs only 2 reads and 4 writes (a new lower bound) in the absence of contention. We provide a correctness proof.We also investigate the utility of exponential backoff in fast mutual exclusion, with experimental results on the Silicon Graphics Iris multiprocessor and on a larger, simulated machine. With backoff in place, we find that Lamport's algorithm, our new algorithm, and a recent algorithm due to Alur and Taubenfeld all work extremely well, outperforming the native hardware locks of the Silicon Graphics machine, even with heavy contention.
Keywords: shared-memory multiprocessors; multiprogramming; architecture trends; loop scheduling; lightweight thread scheduling.
The last decade has produced enormous improvements in processor speed without a corresponding improvement in bus or interconnection network speeds. As a result, the relative costs of communication and computation in shared-memory multiprocessors have changed dramatically. An important consequence of this trend is that many parallel applications, whose performance depends on a delicate balance between the cost of communication and computation, do not execute efficiently on today's shared-memory multiprocessors.In this dissertation we quantify the effect of this trend in multiprocessor architecture on parallel program performance, explain the implications of this trend on popular parallel programming models, and propose system software to efficiently map parallel programs and programming models to modern shared-memory multiprocessors. Our experiments with application programs on bus-based, cache-coherent machines like the Sequent Symmetry, and large-scale distributed-memory machines like the BBN Butterfly, confirm that applications scale much better on previous-generation machines than on current machines due to the rising cost of communication. Our experiments also suggest that shared-memory programming models, which can be implemented efficiently on the machines of yesterday, do not readily port to state-of-the-art machines. As a solution, we propose new decomposition and scheduling algorithms that significantly reduce communication overhead. Our scheduling algorithms, which apply equally well to run-time libraries and parallelizing compilers, attempt to co-locate processes and data, assigning processes to processors based on the location of the date they will access. Our experiments over a wide variety of shared-memory multiprocessors demonstrate that the performance benefits of these scheduling-for-locality algorithms are significant, improving performance by up to 60\% for some applications on modern machines. We conclude that communication overhead need not dominate performance on present or future multiprocessors, given an appropriate programming model, multiprogramming scheduling policy, and user-level decomposition and scheduling algorithms.
Keywords: software coherence; multiprocessor memory systems; NUMA; tracing; optimal analysis.
Processors are becoming faster and multiprocessor memory interconnection systems are not keeping up. Therefore, it is necessary to have threads and the memory they access as near one another as possible. Typically, this involves putting memory or caches with the processors, which gives rise to the problem of coherence: if one processor writes an address, any other processor reading that address must see the new value. This coherence can be maintained by the hardware or with software intervention. Systems of both types have been built in the past; the hardware-based systems tended to outperform the software ones. However, the ratio of processor to interconnect speed is now so high that the extra overhead of the software systems may no longer be significant. This dissertation explores this issue both by implementing a software-maintained system and by introducing and using the technique of offline optimal analysis of memory reference traces. It finds that in properly built systems, software-maintained coherence can perform comparably to or even better than hardware-maintained coherence. The architectural features necessary for efficient software coherence to be profitable include a small page size, a fast trap mechanism, and the ability to execute instructions while remote memory references are outstanding.
Keywords: performance evaluation; performance predicates; predicate profiling.
Parallel programs incur overhead in many different ways, such as synchronization, load imbalance, communication, and insufficient parallelism. We have found that all of these categories are important in understanding the performance of parallel programs, and that a rapid assessment of how processing time is spent in each of these categories is extremely helpful in the performance tuning of parallel programs. As a result we have developed the notion of performance predicates, which are expressions that define these categories and can be used to recognize and classify inefficient states during a program's execution. Formal definition allows us to discuss the categories quantitatively; we present a method for measuring time spent in each category, based on the common metric of lost cycles. The method we describe, called predicate profiling, is shown to be quite useful for both application-level and program-level performance tuning. We show that predicate profiling is relatively easy to implement, and has very low run-time cost. We also show that the lost cycles metric is applicable to programs for which other metrics, like speedup, aren't well defined.
Keywords: scalable spin locks; multiprogramming; synchronization.
Synchronization primitives for large scale multiprocessors need to provide low latency and low contention to achieve good performance. Queue-based locks (implemented in software with fetch_and_\Phi instructions) can greatly reduce contention and improve overall performance by arranging for processors to spin only on local locations. Unfortunately, queued locks exhibit poor behavior in the presence of multiprogramming: a process near the end of the queue, in addition to waiting for any process that is preempted during its critical section, must also wait for any preempted processes ahead of it in the queue.To solve this problem, we present two queue-based locks that recover from in-queue preemption. The first lock employs the kernel interface of the NYU Symunix project. The second employs an extended interface that shares information in both directions across the user-kernel boundary, resulting in simpler code and better performance. Experiments with these locks in both real and synthetic applications on SGI and KSR multiprocessors confirm the feasibility of high-performance software locks on systems that are both very large and multiprogrammed.
Keywords: MIPS R3000 interpreter; multiprocessor simulation; memory trace; parallel; execution-driven.
This document describes Mint, a MIPS code interpreter for parallel programs. Mint generates memory reference traces that can be used to drive simulations of multiprocessor systems. Mint executes in a single address space and interprets MIPS R3000 object code programs. For faster interpretation, blocks of straight-line code in the object program are executed natively by creating functions at run-time. Unlike other memory tracers that compile the memory tracing calls into the simulated program, Mint does not require recompiling the simulated program. Interpreting the object program has the advantage that no source is needed, the simulator is independent of the object program, and a total program trace, including library references, is easily generated. Mint is a fast interpreter. When generating events for every memory reference, the overhead of Mint typically slows down a simulated program by a factor of 20 to 70 compared to its native execution time.
Keywords: subgraph isomorphism; data parallelism; Natasha; parallel search.
Two popular myths concerning parallel programming are: (1) there is a ``best'' parallelization for a given application on a given class of machine and (2) loop-based data parallelism captures all useful parallelizations. We challenge these myths by considering alternative parallelizations of combinatorial search, examining the factors that determine the best-performing option for this important class of problems. Using subgraph isomorphism as a representative search problem, we show how the density of the solution space, the number of solutions desired, the number of available processors, and the underlying architecture affect the choice of an efficient parallelization. Our experiments, which span seven different shared-memory machines and a wide range of input graphs, indicate that relative performance depends on each of these factors. On some machines and for some inputs, a sequential depth-first search of the solution space, applying data parallelism at each node in the search tree, performs best. On other machines or other inputs, parallel tree search, with no data parallelism, performs best. In still other cases, a hybrid solution, containing both parallel tree search and data parallelism, works best. From these experiences we conclude that there is no one ``best'' parallelization that suffices over a range of machines, inputs, and precise problem specifications. As a corollary, we argue that programming environments should not focus exclusively on data parallelism, since parallel tree search or hybrid forms of parallelism may perform better for some applications.
Memory contention can be a major source of overhead in large-scale shared-memory multiprocessors. Although there are many hardware solutions to the problem of memory contention, these solutions are often complex and expensive, so software solutions are an attractive alternative. This paper evaluates one particular software solution, called block-column allocation, which is very effective at reducing memory contention for a large class of SPMD (Single-Program-Multiple-Data) programs, and can be implemented easily by the compiler. We first quantify the impact of memory contention on performance by simulating the execution of several application kernels on a large-scale multiprocessor. Our simulation results confirm that memory contention is widespread on large-scale machines; our applications suggest that contention is usually caused by synchronized access to a range of addresses (rather than to a single address). We show that block-column allocation, where each range of addresses is divided into cache lines, and each cache line is allocated to a separate memory module, can nearly eliminate this source of memory contention. As our main contribution, we compare block-column allocation to row-major allocation (a common data allocation scheme) and logarithmic broadcasting (the standard software technique for alleviating memory contention). Our analysis demonstrates the clear superiority of block-column allocation over row-major allocation in the presence of memory contention. Our analysis also indicates that the choice between block-column allocation and logarithmic broadcasting is less clear, as it depends both on the type of synchronization used and the number of processors. We can conclude, however, that on large-scale machines with hundreds of processors, block-column allocation and lock-based synchronization is the most effective combination for reducing memory contention in SPMD matrix computations.
Keywords: memory contention; hot spots; eager combining; coherency protocols.
Effective use of large-scale multiprocessors requires the elimination of all bottlenecks that reduce processor utilization. One such bottleneck is memory contention. In this paper we show that memory contention occurs in many parallel applications, when those applications are run on large-scale shared-memory multiprocessors. In our simulations of several parallel applications on a large-scale machine, we observed that some applications exhibit near-perfect speedup on hundreds of processors when the effect of memory contention is ignored, and exhibit no speedup at all when memory contention is considered. As the number of processors is increased, many applications exhibit an increase in both the number of hot spots and in the degree of contention for each hot spot. In addition, we observed that hot spots are spread throughout memory for some applications, and that eliminating hot spots on an individual basis can cause other hot spots to worsen. These observations suggest that modern multiprocessors require some mechanism to alleviate hot-spot contention.We evaluate the effectiveness of two different mechanisms for dealing with hot-spot contention in direct-connected, distributed-shared-memory multiprocessors: queueing requests at the memory module, which allows a memory module to be more highly utilized during periods of contention, and increasing the effective bandwidth to memory by having the coherency protocol distribute the hot data to multiple memory modules. We show that queueing requires long queues at each memory module, and does not perform as well as our proposed coherency protocol, which essentially eliminates memory contention in the applications we consider.
As an alternative to communication via messages or files, shared memory has the potential to be simpler, faster, and less wasteful of space. Unfortunately, the mechanisms available for sharing in Unix are not very easy to use. As a result, shared memory tends to appear primarily in self-contained parallel applications, where library or compiler support can take care of the messy details. We have developed a system, called Hemlock, for transparent sharing of variables and/or subroutines across application boundaries. Our system is backward compatible with existing versions of Unix. It employs dynamic linking in conjunction with the Unix mmap facility and a kernel-maintained correspondence between virtual addresses and files. It introduces the notion of scoped linking to avoid naming conflicts in the face of extensive sharing.
Keywords: parallel genetic algorithms; integer linear programming; transputers; distributed-memory systems.
The implementation of parallel genetic algorithms raises many important issues. These issues can be divided into two main classes: genetic search quality and execution performance. In the context of parallel genetic algorithms on distributed-memory computers, performance considerations have always driven the design of implementations. Thus, centralized implementations have almost always been excluded from any consideration for distributed-memory architectures.The work we present here defines a set of genetic algorithm implementation alternatives for distributed-memory computers, in which strategies with some centralization are included. Each of our implementation alternatives uses a different level of distribution of the population, from the single logically centralized population to a totally distributed set of subpopulations.
The design alternatives we define can be applied to the implementation of any parallel genetic algorithm. As an example of such an implementation, we study the quality of the search and the execution performance of our strategies on the 0-1 Integer Linear Programming problem, on a Transputer network. Our results show that implementations incurring higher overheads can produce as good or better solutions faster than than very "efficient" implementations, depending on the characteristics of the problem at hand. More specifically, in some cases, utilizing more centralized parallel genetic search strategies results in the fastest convergence towards the optimal solution, therefore reducing the number of generations needed by the algorithm.
Keywords: shared memory multiprocessor; software coherence; optimal analysis.
There are three major classes of MIMD multiprocessors: cache-coherent machines, NUMA (non-uniform memory reference) machines without cache coherence, and distributed-memory multicomputers. All three classes can be used to run shared-memory applications, though the third requires software support in order to do so, and the second requires software support in order to do so well. We use trace-driven simulation to compare the performance of these classes, in an attempt to determine the effect of various architectural features and parameters on overall program performance. For those systems whose hardware or software supports both coherent caching (migration, replication) and remote reference, we use optimal off-line analysis to make the correct decision in all cases. This technique allows us to evaluate architectural alternatives without worrying that the results may be biased by a poor data placement policy. We find that the size of the unit of coherence (page or cache line) is the dominant factor in performance; that NUMA systems can have performance comparable to that of cache coherent machines; and that even relatively expensive, software-implemented remote reference is beneficial in distributed shared memory machines.
Keywords: synchronization; adaptive combining tree; fuzzy barriers; multiprogramming; contention; scalability; local-only spinning; fetch-and-store.
Counter-based algorithms for busy-wait barrier synchronization execute in time linear in the number of synchronizing processes. This time can be made logarithmic in the number of processes by adopting algorithms based on trees or FFT-like synchronization patterns. As an additional improvement, Gupta and Hill have proposed an adaptive combining tree barrier that exploits non-uniformity in inter- barrier computation times: processes begin to leave the barrier in time logarithmic in the number of processes when all processes arrive at once, but in constant time after the arrival of the last process when arrival times are skewed.Building on earlier work, Gupta and Hill present both regular and fuzzy versions of their barrier. The fuzzy version allows a process to perform useful work between the point at which it notifies other processes of its arrival at the barrier and the point at which it waits for all other processes to arrive.Unfortunately, like many forms of busy-wait synchronization, adaptive combining tree barriers as originally devised can induce large amounts of memory and interconnect contention in shared-memory multiprocessors, seriously degrading performance. They also perform a comparatively large amount of work at every tree node, raising the possibility that the constant factors in their execution time may be unacceptably high on machines of reasonable size. To address these problems, we present a new adaptive combining tree barrier, with fuzzy variant, that achieves significant speed improvements by spinning only on locally-accessible locations, and by using atomic fetch_and_store operations to avoid explicit locking of tree nodes. We also present a version of this barrier (again with fuzzy variant) that employs breadth-first wakeup of processes to reduce context switching when processors are multiprogrammed. We compare the performance of these new algorithms to that of other fast barriers on a 64-node BBN Butterfly 1 multiprocessor and on a 35-node BBN TC2000. Results suggest that adaptation is of little benefit, but that the combination of fuzziness with tree-style synchronization is of significant practical importance: fuzzy combining tree barriers with local-only spinning outperform all known alternatives on the TC2000 when the amount of fuzzy computation exceeds about 10% of the time between barriers.
Keywords: coherent caches; block size; scalable multiprocessors; sharing; spatial locality.
Several studies have shown that the performance of coherent caches depends on the relationship between the cache block size and the granularity of sharing and locality exhibited by the program. Large cache blocks exploit processor and spatial locality, but may cause unnecessary cache invalidations due to false sharing. Small cache blocks can reduce the number of cache invalidations, but increase the number of bus or network transactions required to load data into the cache. To reduce the performance impact of a mismatch between the cache block size and the sharing pattern exhibited by a given application, we propose to adjust the amount of data stored in a cache line dynamically according to recent reference patterns. In this scheme, cache blocks are split across cache lines when false sharing occurs, and merged back into a single cache line to exploit spatial locality. Results of simulations of a scalable multiprocessor indicate that, over a range of applications, an adjustable block size cache performs better than every fixed block size alternative. Moreover, for a given program, the adjustable block size cache is comparable in performance to the best fixed block size cache for that program. We conclude that adjusting the block size in response to reference behavior can significantly improve performance, especially when there is variability in the granularity of sharing exhibited by applications.
Keywords: object affinity; scheduling; templates; continuation passing; Mercury.
On recent high-performance multiprocessors, there is a potential conflict between the goals of achieving the full performance potential of the hardware and providing a parallel programming environment that makes effective use of programmer effort. On one hand, an explicit coarse-grain programming style may appear to be necessary, both to achieve good cache performance and to limit the amount of overhead due to context switching and synchronization. On the other hand, it may be more expedient to use more natural and finer-grain programming styles based on abstractions such as task heaps, light-weight threads, parallel loops, or object-oriented parallelism. Unfortunately, using these styles can cause a loss of performance due to poor locality and high overhead. We claim that the locality issue in fine-grain parallel programs can be addressed effectively by using object-affinity scheduling and that the overhead can be reduced substantially by representing tasks as templates that are managed using continuation-passing style mechanisms. We present supporting evidence for these claims in the form of experimental measurements of programs running on Mercury, an object-oriented system implemented on an SGI 4D/480 multiprocessor.
Keywords: multi-model parallel programming; operating systems; multiprocessors; programming model; parallel programming.
Multi-model parallel programming is the simultaneous use of different programming models, either within a single program or in separate programs. A variety of programming models is best implemented in runtime libraries, yet current operating systems are not designed to support user-level implementations of processes and communication. Even if an efficient implementation of a programming model can be constructed in user space, interaction with other programming models is complicated by the lack of a common communication mechanism.The thesis of this dissertation is that in order to support multi-model parallel programming, an operating system must provide first-class user-level processes and model-independent communication. First-class user-level processes support the construction of multiple models by allowing flexibility and efficiency of user-level implementations to be combined with the control over resource allocation traditionally enjoyed only by kernel-level implementations. Model-independent communication supports the integration of multiple models into a single application by eliminating model dependencies from the data transfer and concurrency control mechanisms used for communication. Together, these concepts facilitate multi-model programming, making possible a wide variety of high-quality implementations that are easily combined within a single application.
To support the thesis, we designed and implemented a prototype kernel, called Psyche, ported the implementations of different parallel programming models, and built several multi-model programs. Our experiences with the various programming models demonstrate the feasibility of according first-class status to processes implemented in user space. Our experiences with multi-model applications demonstrate how model-independent communication facilitates the construction of multi-model programs. Through these experiences, this dissertation demonstrates the feasibility and utility of multi-model parallel programming.
Keywords: write-invalidate, write-update, hybrid protocols, trace-driven simulation, performance evaluation.
The caches within a multiprocessor typically use either a write-invalidate protocol or a write-update protocol to maintain consistency. The recently introduced MIPS R4000 processor allows operating system software to select, on a per-page basis, which multiprocessor cache coherence protocol (write-invalidate versus write-update) the hardware will use. The availability of the R4000 and the prospect of even more flexible hardware motivated us to examine the potential performance advantages of allowing user-level control over the choice of coherence protocol on a per-page basis and to ask whether more powerful hybrid protocols provide substantially more benefit. We examine the potential benefits of three classes of hybrid protocols: (1) hybrid protocols that choose statically, at the beginning of the program, between write-invalidate (WI) or write-update (WU) on a per-page basis, (2) hybrid protocols that choose statically between WI or WU for each cache block, and (3) dynamic hybrid protocols that can choose between WI or WU at each write. In order to determine how much potential benefit could be obtained by each of these protocol classes, we used trace-driven simulations to evaluate the optimal off-line protocol for each class. We found that the use of a hybrid protocol can substantially reduce the cost of memory references for most of the programs studied. A few programs can also realize large additional benefits from a per-block static hybrid protocol compared to a per-page static hybrid protocol. None of the programs, however, receive a significant additional benefit from using a dynamic hybrid protocol compared to the per-block static hybrid protocol, unless cache block sizes are larger than 16 words (64 bytes).
Keywords: locality management, load balancing, shared-memory, message-passing.
Shared-memory multiprocessors can support a model of parallel computation based on either shared memory or message passing. Since the programming model dictates so many aspects of the implementation of an application, including process decomposition and scheduling, the choice of programming model is a dominant factor in application performance. In this paper we argue that the choice between the shared-memory and message-passing models depends on two factors: the relative cost of communication and computation as implemented by the hardware, and the degree of load imbalance inherent in the application. We use two representative applications to illustrate the performance advantages of each programming model on several different shared-memory machines, including the BBN Butterfly, Sequent Symmetry, Encore Multimax, and Silicon Graphics Iris multiprocessors. We show that applications implemented in the shared-memory model perform better on the previous generation of multiprocessors, while applications implemented in the message-passing model perform better on modern multiprocessors. We argue that both models have performance advantages, and that the factors that influence the choice of model may not be known at compile-time. As a compromise solution, we propose an alternative programming model, which has the load balancing properties of the shared-memory model and the locality properties of the message-passing model, and show that this new model performs better than the other two alternatives.
As an alternative to communication via messages or files, shared memory has the potential to be simpler, faster, and less wasteful of space. Unfortunately, the mechanisms available for sharing in most multi-user operating systems are difficult to use. As a result, shared memory tends to appear primarily in self-contained parallel applications, where library or compiler support can take care of the messy details.We see a tremendous opportunity to extend the advantages of sharing across application boundaries. We believe that these advantages can be realized without introducing major changes to the Unix programming model. In particular, we believe that it is both possible and desirable to incorporate shared memory segments into the hierarchical file system name space.
Our approach has two components: First, we use dynamic linking to allow programs to access shared data and code in the same way they access ordinary (private) variables and functions. Second, we unify memory and files into a single-level store that facilitates the sharing of pointers. This second component is made feasible by the 64-bit addresses of emerging microprocessors.
A parallel application executes most efficiently when its workload is evenly distributed among the available processors, and tasks are located close to their data. There is often a conflict between the goals of load balancing and locality management policies however, which many existing systems resolve in favor of load balancing. In this paper we use both experimentation and simulation to investigate the relationship between load balancing and locality management in shared-memory multiprocessors. Our experiments with applications on a Silicon Graphics Iris multiprocessor workstation and a BBN Butterfly multiprocessor show that both techniques can improve application performance, but locality considerations should take precedence when assigning tasks to processors. Our simulations show that even in cases where there is a significant variation in the completion time of tasks, or where the remote-to-local access time ratio is small, the best performance results from assigning tasks to processors so as to maximize locality, and reassigning tasks when and if imbalance occurs. We conclude that the scheduler should not be oblivious to the location of data, as is the case with the popular central work queue model; instead, the location of data should be the primary factor influencing the initial assignment of tasks to processors.
The last decade has produced enormous improvements in processor speeds without a corresponding improvement in bus or interconnection network speeds. As a result, the relative costs of communication and computation in shared-memory multiprocessors have changed dramatically. An important consequence of this trend is that many parallel applications, which depend on a delicate balance between the cost of communication and computation, do not execute efficiently on today's shared-memory multiprocessors.In this paper we quantify the effect of this trend in multiprocessor architecture on parallel program performance. Our experiments on bus-based, cache-coherent machines like the Sequent Symmetry, and large-scale distributed-memory machines like the BBN Butterfly, demonstrate that applications scale much better on previous-generation machines than on current machines. In addition, we show that some scalable machines support fine-grain, shared-memory programs better than some bus-based, cache-coherent machines, without significantly greater programming effort. From our experiments we conclude that communication has become a dominant source of inefficiency in shared-memory multiprocessors, with serious consequences for system software involved in scheduling and decomposition decisions. In particular, we argue that shared-memory programming models that could be implemented efficiently on the machines of yesterday do not readily port to state-of-the-art machines, and that current software trends in support of fine-grain parallel programming are at odds with hardware trends.
Shared memory as a programming abstraction is widely used within parallel applications. It is not widely used between applications, but we argue that it should be. Specifically, we suggest that shared memory is both faster and more intuitive than the principal alternatives in many cases, and that the general disuse of shared memory facilities in systems such as Unix is due in large part to a lack of appropriate tools.We are pursuing a series of measures to make shared memory more convenient. We use dynamic linking to allow programs to access shared or persistent data the same way they access ordinary variables and functions. We also unify memory and files into a single-level store that facilitates the sharing of pointers and capitalizes on emerging 64-bit architectures. We exploit existing interfaces and tools wherever possible, to remain backward-compatible with Unix.
Several studies have shown that the performance of coherent caches depends on the relationship between the granularity of sharing and locality exhibited by the program and the cache block size. Large cache blocks exploit processor and spatial locality, but may cause unnecessary cache invalidations due to false sharing. Small cache blocks can reduce the number of cache invalidations, but increase the number of bus or network transactions required to load data into the cache. In this paper we describe a cache organization that dynamically adjusts the cache block size according to recently observed reference behavior. Cache blocks are split across cache lines when false sharing occurs, and merged back into a single cache line to exploit spatial locality. To evaluate this cache organization, we simulate a scalable multiprocessor with coherent caches, using a suite of memory reference traces to model program behavior. We show that for every fixed block size, some program suffers a 33\% increase in the average waiting time per reference, and a factor of 2 increase in the average number of words transferred per reference, when compared against the performance of an adjustable block size cache. In the few cases where adjusting the block size does not provide superior performance, it comes within 7\% of the best fixed block size alternative. We conclude that an adjustable block size cache offers significantly better performance than every fixed block size cache, especially when there is variability in the granularity of sharing exhibited by applications.
Keywords: exception handling, debugging, lightweight threads, upcalls.
We describe the facilities provided by \PL{}, a multiprocessor micro-kernel, to support user-level exception handling. The principal design goal for these facilities is to provide a very simple mechanism with sufficient flexibility and efficiency to experiment with the implementation of a wide variety of exception-driven, user-level services in a parallel system. These services provide conventional exception handling, an interface between parallel programs and debugging or performance monitoring tools, user-level paging and I/O services, and support for user-level lightweight process packages. The exception handling facility is based on fast message passing using a reconfigurable hierarchy of mailboxes. The mechanisms we describe have performance comparable to their uniprocessor signal handling under Unix, and retain that performance when used on a multiprocessor to support the kind of exception-driven services demanded by a parallel programming environment.
Keywords: loop scheduling, locality management, load balancing, central workqueues.
Loops are the single largest source of parallelism in many applications. One way to exploit this parallelism, and thereby minimize program execution time, is to execute loop iterations in parallel on different processors. Traditional approaches to loop scheduling attempt to achieve the minimum completion time by distributing the workload as evenly as possible, while minimizing the number of synchronization operations required. In this paper we consider a third dimension to the problem of loop scheduling on shared-memory multiprocessors: communication overhead caused by accesses to non-local data. We show that traditional algorithms for loop scheduling, which ignore the location of data when assigning iterations to processors, incur a significant performance penalty on modern shared-memory multiprocessors. We propose a new loop scheduling algorithm that attempts to simultaneously balance the workload, minimize synchronization, and co-locate loop iterations with the necessary data. We compare the performance of this new algorithm to other known algorithms using five representative applications on a Silicon Graphics multiprocessor workstation, a BBN Butterfly, and a Sequent Symmetry, and show that the new algorithm offers substantial performance improvements, up to a factor of 3 in some cases. We conclude that loop scheduling algorithms for shared-memory multiprocessors cannot afford to ignore the location of data, particularly in light of the increasing disparity between processor and memory speeds.
Keywords: locality management, load balancing, thread scheduling, user-level scheduling.
Many parallel applications are implemented using lightweight thread packages. The low overhead associated with user-level thread management encourages programmers to use threads to exploit fine-grain parallelism in an application. Although the overhead of explicit thread management can be very small, there is other overhead associated with lightweight threads: the time required to load data into the local memory (or cache) where the thread executes. In many cases this overhead is a significant percentage of the execution time of a thread, so much so that fine-grain parallel programs typically perform much worse than coarse-grain implementations of the same application, even when the cost of thread management is negligible. In this paper we propose a technique for thread scheduling, called \mcs, that reduces this overhead by executing a thread close to some of the data it will access. We illustrate the use of this scheduling technique on two different architectures: a bus-based, cache-coherent multiprocessor, and a distributed-memory machine without caches. Our experimental results show that this technique significantly improves the performance of fine-grain parallel applications on both machines. In fact, fine-grain parallel applications using \mcs\ are often comparable in performance to coarse-grain parallel applications. Using simulation, we quantify the benefits of \mcs\ under varying distributions of data and load, and changes in the remote-to-local memory access time ratio. We conclude that \mcs\ offers substantial performance benefits on current multiprocessors, and has even greater potential on
Keywords: locality management, load balancing, thread scheduling, user-level scheduling.
A parallel application executes most efficiently when its workload is evenly distributed among the available processors, and processes are located close to their data. There is often a conflict between the goals of load balancing and locality management policies however, which many existing systems resolve in favor of load balancing. In this paper we use both experimentation and simulation to investigate the relationship between load balancing and locality management in shared-memory multiprocessors. Our experiments with applications on the BBN Butterfly multiprocessor show that although both techniques can improve application performance, locality management should be done before load balancing in many cases. Our simulations show that even in cases where there is a significant variation in the completion time of processes, or where the remote-to-local access time ratio is small, maximizing locality first and balancing load second usually results in the best performance. We conclude that the scheduler should not be oblivious to the location of data, as is the case with the popular central work queue model; instead, the location of data should be the primary factor influencing the initial assignment of processes to processors.
Keywords: tr374 checkers psyche.
Animate vision systems couple computer vision and robotics to achieve robust and accurate vision, as well as other complex behavior. These systems combine low-level sensory processing and effector output with high-level cognitive planning---all computationally intensive tasks that can benefit from parallel processing. A typical animate vision application will likely consist of many tasks, each of which may require a different parallel programming model, and all of which must cooperate to achieve the desired behavior. These multi-model programs require an underlying software system that not only supports several different models of parallel computation simultaneously, but which also allows tasks implemented in different models to interact.This paper describes the Psyche multiprocessor operating system, which was designed to support multi-model programming, and the Rochester Checkers Player, a multi-model robotics program that plays checkers against a human opponent. Psyche supports a variety of parallel programming models within a single operating system by according first-class status to processes implemented in user space. It also supports interactions between programming models using model-independent communication, wherein different types of processes communicate and synchronize without relying on the semantics or implementation of a particular programming model. The implementation of the Checkers Player, in which different parallel programming models are used for vision, robot motion planning, and strategy, illustrates the use of the Psyche mechanisms in an application program, and demonstrates many of the advantages of multi-model programming for animate vision systems.
The postscript in this directory is missing a black-and-white photo.
Keywords: checkers psyche.
Animate vision systems couple computer vision, robotics, and cognition. These activities need cooperative parallel processing at several granularities. The Psyche system provides this multi-model capability.The postscript in this directory is missing a black-and-white photo. There will be minor editorial changes in the final Computer version.
Keywords: psyche.
It is often desirable, for reasons of clarity, portability, and efficiency, to write parallel programs in which the number of processes is independent of the number of available processors. Several modern operating systems support more than one process in an address space, but the overhead of creating and synchronizing kernel processes can be high. Many runtime environments implement lightweight processes (threads) in user space, but this approach usually results in second-class status for threads, making it difficult or impossible to perform scheduling operations at appropriate times (e.g. when the current thread blocks in the kernel). In addition, a lack of common assumptions may also make it difficult for parallel programs or library routines that use dissimilar thread packages to communicate with each other, or to synchronize access to shared data.We describe a set of kernel mechanisms and conventions designed to accord "first-class status" to user-level threads, allowing them to be used in any reasonable way that traditional kernel-provided processes can be used, while leaving the details of their implementation to user-level code. The key features of our approach are (1) shared memory for asynchronous communication between the kernel and the user, (2) software interrupts for events that might require action on the part of a user-level scheduler, and (3) a scheduler interface convention that facilitates interactions in user space between dissimilar kinds of threads. We have incorporated these mechanisms in the Psyche parallel operating system, and have used them to implement several different kinds of user-level threads. We argue for our approach in terms of both flexibility and performance.
Keywords: algorithm tracing trace based analysis.
In recent years, much effort has been devoted to analyzing the performance of distributed memory systems for multiprocessors. Such systems usually consist of a set of memories or caches, some device such as a bus or switch to connect the memories and processors, and a policy for determining when to put which addressable objects in which memories. In attempting to evaluate such systems, it has generally proven difficult to separate the performance implications of the hardware architecture from those of the policy that controls the hardware (whether implemented in software or hardware). In this paper we describe the use of off-line optimal analysis to achieve this separation. Using a trace-driven dynamic programming algorithm, we compute the policy decisions that would maximize overall memory system performance for a given program execution. The result allows us to eliminate the artifacts of any arbitrarily chosen policy when evaluating hardware performance, and provides a baseline against which to compare the performance of particular, realizable, policies. We illustrate this technique in the context of software-controlled page migration and replication, and argue for its applicability to other forms of multiprocessor memory management. (A revised version of this paper appeared in JPDC (Special Issue, Multiproessor Memory Systems), August 1992.)
Keywords: psyche tr368.
In the standard kernel organization on a bus-based multiprocessor, all processors share the code and data of the operating system; explicit synchronization is used to control access to kernel data structures. Distributed-memory multicomputers use an alternative approach, in which each instance of the kernel performs local operations directly and uses remote invocation to perform remote operations. Either approach to inter-kernel communication can be used in a large-scale shared-memory multiprocessor.In this paper we discuss the issues and architectural features that must be considered when choosing between remote memory access and remote invocation. We focus in particular on experience with the Psyche multiprocessor operating system on the BBN Butterfly Plus. We find that the Butterfly architecture is biased towards the use of remote invocation for kernel operations that perform a significant number of memory references, and that current architectural trends are likely to increase this bias in future machines. This conclusion suggests that straightforward parallelization of existing kernels (e.g., by using semaphores to protect shared data) is unlikely in the future to yield acceptable performance. We note, however, that remote memory access is useful for small, frequently-executed operations, and is likely to remain so.
Low-level multiprocessor synchronization primitives, such as spinlocks, are usually designed with little or no consideration about timing constraints, which makes them inappropriate for real-time systems. In this paper, we propose a new synchronization mechanism, the priority spinlock, that takes into account the priorities of the processes that want to acquire it, and favors high priority processes. We define what a priority spinlock is and propose two algorithms to implement priority spinlocks with local spinning. Priority spinlocks can be used to provide prioritized mutually exclusive access to shared resources in real-time multiprocessor systems. They can also be used as building blocks for higher level priority synchronization primitives, such as priority semaphores.
Keywords: tree barriers.
One of the most common ways to share a multiprocessor among several applications is to give each application a set of dedicated processors. To ensure fairness, an application may receive fewer processors than it has processes. Unless an application can easily adjust the number of processes it employs during execution, several processes from the same application may have to share a processor. In this paper we quantify the performance penalty that arises when more than one process from the same application runs on a single processor of a NUMA (NonUniform Memory Access) multiprocessor. We consider programs that use coarse-grain parallelism and barrier synchronization because they are particularly sensitive to multiprogramming. We quantify the impact on the performance of an application of quantum size, frequency of synchronization, and the type of barrier used. We conclude that dedicating processors to an application, even without migration or dynamic adjustment of the number of processes, is an effective scheduling policy even for programs that synchronize frequently using barriers. (A shortened version of this paper appeared in Proc., 3rd IEEE Symposium on Parallel and Distributed Processing, 662--669, December 1991.)
Keywords: architectural independence; closure; Matroshka; Natasha.
To create a parallel program, programmers must decide what parallelism to exploit, and choose the associated data distribution and communication. Since a typical algorithm has much more potential parallelism than any single architecture can effectively exploit, programmers usually express only the exploitation of parallelism appropriate to a single machine. Unfortunately, parallel architectures vary widely. A program that executes efficiently on one architecture may execute badly, if at all, on another architecture. To port such a program to a new architecture, we must rewrite the program to remove any ineffective parallelism, to introduce any parallelism appropriate for the new machine, to re-distribute data and processing, and to alter the form of communication.Architectural adaptability is the ease with which programmers can tune or port a program to a different architecture. The thesis of this dissertation is that control abstraction is fundamental to architectural adaptability for parallel programs. With control abstraction, we can define and use a rich variety of control constructs to represent an algorithm's potential parallelism. Since control abstraction separates the definition of a construct from its implementation, a construct may have several different implementations, each providing different exploitations of parallelism. By selecting an implementation for each use of a control construct with annotations, we can vary the parallelism we choose to exploit without otherwise changing the source code.
We present Matroshka, a programming model that supports architectural adaptability in parallel programs through object-based data abstraction and closure-based control abstraction. Using the model, we develop several working example programs, and show that the example programs adapt well to different architectures. We also outline a programming method based on abstraction. To show the implementation feasibility of our approach, we describe a prototype language based on Matroshka, describe its implementation, and compare the performance of the prototype with existing programs.
Reader-writer synchronization relaxes the constraints of mutual exclusion to permit more than one process to inspect a shared object concurrently, as long as none of them changes its value. On uniprocessors, mutual exclusion and reader-writer locks are typically designed to de-schedule blocked processes; however, on shared-memory multiprocessors it is often advantageous to have processes busy wait. Unfortunately, implementations of busy-wait locks on shared-memory multiprocessors typically cause memory and network contention that degrades performance. Several researchers have shown how to implement scalable mutual exclusion locks that exploit locality in the memory hierarchies of shared-memory multiprocessors to eliminate contention for memory and for the processor-memory interconnect. In this paper we present reader-writer locks that similarly exploit locality to achieve scalability, with variants for reader preference, writer preference, and reader-writer fairness. Performance results on a BBN TC2000 multiprocessor demonstrate that our algorithms provide low latency and excellent scalability.
Multiprocessor memory reference traces provide a wealth of information on the behavior of parallel programs. We have used this information to explore the relationship between kernel-based NUMA management policies and multiprocessor memory architecture. Our trace analysis techniques employ an off-line, optimal cost policy as a baseline against which to compare on-line policies, and as a policy-insensitive tool for evaluating architectural design alternatives. We compare the performance of our optimal policy with that of three implementable policies (two of which appear in previous work), on a variety of applications, with varying relative speeds for page moves and local, global, and remote memory references. Our results indicate that a good NUMA policy must be chosen to match its machine, and confirm that such policies can be both simple and effective. They also indicate that programs for NUMA machines must be written with care to obtain the best performance.
Conventional wisdom holds that contention due to busy-wait synchronization is a major obstacle to scalability and acceptable performance in large shared-memory multiprocessors. We argue the contrary, and present fast, simple algorithms for contention-free mutual exclusion, reader-writer control, and barrier synchronization. These algorithms, based on widely available fetch_and_\Phi instructions, exploit local access to shared memory to avoid contention. We compare our algorithms to previous approaches in both qualitative and quantitative terms, presenting their performance on the Sequent Symmetry and BBN Butterfly multiprocessors. Our results highlight the importance of local access to shared memory, provide a case against the construction of so-called ``dance hall'' machines, and suggest that special-purpose hardware support for synchronization is unlikely to be cost effective on machines with sequentially consistent memory.This file is a little ugly; the version for the conference proceedings was formatted for oversize mats. This reconstruction was made with the scaling facility of dvi2ps. Its references were regenerated in the reconstruction, and may not match the proceedings exactly.
Keywords: scheduling coscheduling time-slicing hardware partitions.
Several studies have shown that applications may suffer significant performance degradation unless the scheduling policy minimizes the overhead due to multiprogramming. This overhead includes context switching among applications, waiting time incurred by one process due to the preemption of another, and various migration costs associated with moving a process from one processor to another. Many different multiprogramming solutions have been proposed, but each has limited applicability or fails to address an important source of overhead. In addition, there has been little experimental comparison of the various solutions in the presence of applications with varying degrees of parallelism and synchronization. In this paper we explore the tradeoffs between different approaches to multiprogramming a multiprocessor. We modified an existing operating system to implement three different multiprogramming options: time-slicing, coscheduling, and dynamic hardware partitions. Using these three options, we implemented applications that vary in the degree of parallelism, and the frequency and type of synchronization. We show that in most cases coscheduling is preferable to time-slicing. We also show that although there are cases where coscheduling is beneficial, dynamic hardware partitions do no worse, and will often do better. We conclude that under most circumstances, hardware partitioning is the best strategy for multiprogramming a multiprocessor, no matter how much parallelism applications employ or how frequently synchronization occurs. (A shortened version of this paper appeared in Proc., 3rd IEEE Symposium on Parallel and Distributed Computing, 590--597, Dec. 1991.)
Keywords: mcs lock MellorCrummeyScott90.
Busy-wait techniques are heavily used for mutual exclusion and barrier synchronization in shared-memory parallel programs. Unfortunately, typical implementations of busy-waiting tend to produce large amounts of memory and interconnect contention, introducing performance bottlenecks that become markedly more pronounced as applications scale. We argue that this problem is not fundamental, and that one can in fact construct busy-wait synchronization algorithms that induce no memory or interconnect contention. The key to these algorithms is for every processor to spin on separate locally-accessible flag variables, and for some other processor to terminate the spin with a single remote write operation at an appropriate time. Flag variables may be locally-accessible as a result of coherent caching, or by virtue of allocation in the local portion of physically distributed shared memory.We present a new scalable algorithm for spin locks that generates O(1) remote references per lock acquisition, independent of the number of processors attempting to acquire the lock. Our algorithm provides reasonable latency in the absence of contention, requires only a constant amount of space per lock, and requires no hardware support other than a swap-with-memory instruction. We also present a new scalable barrier algorithm that generates O(1) remote references per processor reaching the barrier, and observe that two previously-known barriers can likewise be cast in a form that spins only on locally-accessible flag variables. None of these barrier algorithms requires hardware support beyond the usual atomicity of memory reads and writes.
We compare the performance of our scalable algorithms with other software approaches to busy-wait synchronization on both a Sequent Symmetry and a BBN Butterfly. Our principal conclusion is that contention due to synchronization need not be a problem in large-scale shared-memory multiprocessors. The existence of scalable algorithms greatly weakens the case for costly special-purpose hardware support for synchronization, and provides a case against so-called ``dance hall'' architectures, in which shared memory locations are equally far from all processors.
The postscript here is the version from which the galleys were prepared.
Keywords: architectural independence; closure; Matroshka.
Parallel programming involves finding the potential parallelism in an application, choosing an algorithm, and mapping it to the architecture at hand. Since a typical algorithm has much more potential parallelism than any single architecture can effectively exploit, we usually program the parallelism that the available control constructs easily express and that the given architecture efficiently exploits. This approach produces programs that exhibit much less parallelism than the original algorithm and whose performance depends entirely on the underlying architecture. To port such a program to a new architecture, we must rewrite the program to remove any ineffective parallelism and to recover any lost parallelism appropriate for the new machine.In this paper we show how to adapt a parallel program to different architectures using control abstraction. With control abstraction we can define and use a rich variety of control constructs to represent an algorithm's potential parallelism. Since control abstraction separates the definition of a construct from its implementation, a construct may have several different implementations, each exploiting a different subset of the parallelism admitted by the construct. By selecting an implementation for each control construct using annotations, we can vary the parallelism we choose to exploit without otherwise changing the source code. This approach produces programs that exhibit most of, if not all, the potential parallelism in an algorithm, and whose performance can be tuned for a specific architecture simply by choosing among the various implementations for the control constructs in use.
On a distributed shared memory machine, the problem of minimizing accesses to remote memory modules is crucial for obtaining high performance. We describe an object-based, parallel programming system called OSMIUM to support experiments with mechanisms for performing invocations on remote objects. The mechanisms we have studied include: non-cached access to remote memory, data migration, and function-shipping using an interprocessor invocation protocol (IIP). Our analyses and experiments indicate that IIP competes well with the alternatives, especially when the structure of user programs requires synchronized access to data structures. While these results are obtained on a NUMA multiprocessor, they are also applicable to systems that use hardware cache coherency techniques.
Keywords: parallelization; compilers; parallelism; procedural languages.
This dissertation discusses a general model for compilers that take imperative code written for sequential machines (ordinary code) and detect in that code the parallelism that is compatible with the semantics of the underlying programming language. This model is based on the idea of separating the concerns of parallelism detection and parallelism exploitation.This separation is made possible by having the detection component provide an explicit representation of the parallelism available in the original code. This explicitly parallel representation is based on a mathematical formalization of the notion of permissible execution sequences for a given mass of code.
Having made that separation, one can discuss an organization for the parallelism detection component. This organization depends on (1) recognizing a hierarchical structure on a graph representation of the program; and (2) separately encoding parallelization conditions and effects.
Opportunities for parallelization can then be discovered by traversing the hierarchical structure from the bottom up. During this traversal, progressively larger parts of the program are compared against the independently encoded conditions, and transformed when the conditions for a parallelizing transformation are satisfied.
Keywords: tr308.
A programming language has clear advantages over a library package for communication between processes in a distributed environment. Unfortunately, most existing distributed languages are better suited to communication between the processes of a single application than they are to communication between processes that are developed independently. Such independent development is characteristic both of the systems software for multicomputers and of the applications software for geographically-distributed networks. Lynx is a message-based language designed to support both application and system software in a single conceptual framework. It extends the advantages of high-level communication to processes designed in isolation, and compiled and placed in operation without knowledge of their peers. A virtual-circuit abstraction called the link supports changes in communication topology at run time, under user control. A lightweight thread mechanism is integrated with message passing in a way that makes it easy for server processes to maintain context for interleaved conversations with an arbitrary number of clients. Experience with Lynx under two very different implementations has yielded important insights into the interface between a language run-time package and the underlying operating system, and has helped to identify the inherent costs of message-passing systems.This is the place to start if you're interested in Lynx. It cites, and summarizes, most of the other papers. The postscript here is the version from which the galleys were prepared.
Keywords: bridge.
Parallel computers with non-parallel file systems are limited by the performance of the processor running the file system. We have designed and implemented a parallel file system called Bridge that eliminates this problem by spreading both data and file system computation over a large number of processors and disks. To assess the effectiveness of Bridge we have used it to implement several data-intensive applications, including a parallel external merge sort. The merge sort is a particularly demanding application; it requires significant amounts of interprocessor communication and data movement. A detailed analysis of this application indicates that Bridge can profitably be used on configurations in which disks are attached to more than 150 processors. Empirical results on a 32-processor implementation agree with the analysis, providing us with a high degree of confidence in this prediction. Based on our experience, we argue that file systems such as Bridge will satisfy the I/O needs of a wide range of parallel architectures and applications.This paper went through one round of reviewing for IEEE TPDS, but was subsequently dropped. The postscript in this directory is the version submitted to the journal in May of 1990.
Keywords: multi-model real-time satisfice user-level scheduling.
This paper outlines our plans for a real-time systems research program to support the long-term goal of developing intelligent robots. The distinguishing characteristic of our approach to real-time systems is an emphasis on system adaptability in a dynamic real-world environment. We achieve adaptability by allowing multiple real-time process models, with different known properties and timing constraints, to coexist within a single system and application. Using a hardware architecture in which a large-scale multiprocessor controls a behavioral system with vision and manipulation capabilities, we are constructing a prototype software environment that provides a predictable schedule for reflexive robot tasks and a flexible environment for implementing adaptive cognitive robot tasks. We will exploit multiple processors, user-level scheduling, and user-defined process and communication models in the construction of real-time robotics applications.
Many different parallel programming models, including lightweight processes that communicate with shared memory and heavyweight processes that communicate with messages, have been used to implement parallel applications. Unfortunately, operating systems and languages designed for parallel programming typically support only one model. Multi-model parallel programming is the simultaneous use of several different models, both across programs and within a single program. This paper describes multi-model parallel programming in the Psyche multiprocessor operating system. We explain why multi-model programming is desirable and present an operating system interface designed to support it. Through a series of three examples, we illustrate how the Psyche operating system supports different models of parallelism and how the different models are able to interact.The postscript in this directory has been reconstructed from old troff source, and may not match the conference proceedings precisely; the references have been re-built from a newer database, and may not be exactly right.
Keywords: psyche WEBDMS.
Psyche is a parallel operating system under development at the University of Rochester. The Psyche user interface is designed to allow programs with widely differing concepts of process, sharing, protection, and communication to run efficiently on the same machine, and to interact productively. In addition, the Psyche development effort is addressing a host of implementation issues for large-scale shared-memory multiprocessors, including the organization of kernel functions, data structures, and address maps for machines with non-uniform memory; the migration and replication of pages to maximize locality; the introduction of user-level device drivers, memory management, and scheduling; and remote source-level kernel debugging. We focus in this paper on our implementation of Psyche for the BBN Butterfly Plus multiprocessor, though many of the issues we consider apply to any operating system kernel on a large-scale shared-memory machine. We describe our major design decisions, the results of our initial experience with the implementation, and our plans for continued evaluation and experimentation with kernel implementation techniques.The postscript in this directory has been reconstructed from old troff source; the references have been re-built from a newer database, and may not be exactly right.
Multiprocessors with non-uniform memory access times introduce the problem of placing data near the processes that use them, in order to improve performance. We have implemented an automatic page placement strategy in the Mach operating system on the IBM ACE multiprocessor workstation. Our experience indicates that even very simple automatic strategies can produce nearly optimal page placement. It also suggests that the greatest leverage for further performance improvement lies in reducing false sharing, which occurs when the same page contains objects that would best be placed in different memories.
High-performance parallel computers require high-performance file systems. Exotic I/O hardware will be of little use if file system software runs on a single processor of a many-processor machine. We believe that cost-effective I/O for large multiprocessors can best be obtained by spreading both data and file system computation over a large number of processors and disks. To assess the effectiveness of this approach, we have implemented a prototype system called Bridge, and have studied its performance on several data intensive applications, among them external sorting. A detailed analysis of our sorting algorithm indicates that Bridge can profitably be used on configurations in excess of one hundred processors with disks. Empirical results on a 32-processor implementation agree with the analysis, providing us with a high degree of confidence in this prediction. Based on our experience, we argue that file systems such as Bridge will satisfy the I/O needs of a wide range of parallel architectures and applications.
Keywords: Psyche.
An open operating system provides a high degree of programming flexibility and efficiency. At the same time, it generally requires that all programs be written in a single language, and provides no protection other than that which is available from the compiler. These limitations may be tolerated by the user of a personal computer, but they become unacceptable on a workstation that must run untrusted software written in many different languages. Psyche is an operating system designed to make the most effective possible use of shared-memory multiprocessors and uniprocessor machines. It combines the flexibility of an open operating system with the ability to write in multiple languages and to establish solid protection boundaries. It also provides the efficiency of an open operating system for programs that do not require protection.A 5-page position paper.
Keywords: psyche tr311.
Large-scale shared-memory multiprocessors such as the BBN Butterfly and IBM RP3 introduce a new level in the memory hierarchy: multiple physical memories with different memory access times. An operating system for these NUMA (NonUniform Memory Access) multiprocessors should provide traditional virtual memory management, facilitate dynamic and widespread memory sharing, and minimize the apparent disparity between local and nonlocal memory. In addition, the implementation must be scalable to configurations with hundreds or thousands of processors.This paper describes memory management in the Psyche multiprocessor operating system, under development at the University of Rochester. The Psyche kernel manages a multi-level memory hierarchy consisting of local memory, nonlocal memory, and backing store. Local memory stores private data and serves as a cache for shared data; nonlocal memory stores shared data and serves as a disk cache. The system structure isolates the policies and mechanisms that manage different layers in the memory hierarchy, so that customized data structures and policies can be constructed for each layer. Local memory management policies are implemented using mechanisms that are independent of the architectural configuration; global policies are implemented using multiple processes that increase in number as the architecture scales. Psyche currently runs on the BBN Butterfly Plus multiprocessor.
This paper describes an ambitious early design for a VM system for Psyche. Our plans for VM were scaled back substantially after implementation was about half completed, due to changing interests of graduate students. Further discussion can be found in the WEBDMS paper.
Keywords: psyche tr309.
Scalable shared-memory multiprocessors (those with non-uniform memory access times) are among the most flexible architectures for high-performance parallel computing, admitting efficient implementations of a wide range of process models, communication mechanisms, and granularities of parallelism. Such machines present opportunities for general-purpose parallel computing that cannot be exploited by existing operating systems, because the traditional approach to operating system design presents a virtual machine in which the definition of processes, communication, and grain size are outside the control of the user. Psyche is an operating system designed to enable the most effective use possible of large-scale shared memory multiprocessors. The Psyche project is characterized by (1) a design that permits the implementation of multiple models of parallelism, both within and among applications, (2) the ability to trade protection for performance, with information sharings as the default, rather than the exception, (3) explicit, user-level control of process structure and scheduling, and (4) a kernel implementation that uses shared memory itself, and that provides users with the illusion of uniform memory access times.The postscript here was reconstructed from old troff source, and does not match the formatting of the hard-copy TR. In particular, the bibliography has re-built from a newer database, and in several cases cites newer versions of papers -- versions that postdate the TR.
The Psyche project at the University of Rochester aims to develop a high-performance operating system to support a wide variety of models for parallel programming. It is predicated on the conviction that no one model of process state or style of communication will prove appropriate for all applications, but that shared-memory multiprocessors (particularly the scalable ``NUMA'' variety) can and should support all models. Conventional approaches, such as shared memory or message passing, can be regarded as points on a continuum that reflects the degree of sharing between processes. Psyche facilitates dynamic sharing by providing a user interface based on passive data abstractions in a uniform virtual address space. It ensures that users pay for protection only when it is required by permitting lazy evaluation of protection policies implemented with keys and access lists. The data abstractions define conventions for sharing the uniform address space; the tradeoff between protection and performance determines the degree to which those conventions are enforced. In the absence of protection boundaries, access to a shared abstraction can be as efficient as a procedure call or a pointer dereference.The postscript in this directory has been reconstructed from old troff source, and doesn't precisely match the formatting of the version in the conference proceedings. The references have also been re-built from a newer database, and may not be exactly the same.
For three years, members of the Computer Science Department at the University of Rochester have used a collection of BBN Butterfly\*[TM\*] Parallel Processors to conduct research in parallel systems and applications. For most of that time, Rochester's 128-node machine has had the distinction of being the largest shared-memory multiprocessor in the world. In the course of our work with the Butterfly we have ported three compilers, developed five major and several minor library packages, built two different operating systems, and implemented dozens of applications. Our experience clearly demonstrates the practicality of large-scale shared-memory multiprocessors, with non-uniform memory access times. It also demonstrates that the problems inherent in programming such machines are far from adequately solved. Both locality and Amdahl's law become increasingly important with a very large number of nodes. The availability of multiple programming models is also a concern; truly general-purpose parallel computing will require the development of environments that allow programs written under different models to coexist and interact. Most important, there is a continuing need for high-quality programming tools; widespread acceptance of parallel machines will require the development of programming environments comparable to those available on sequential computers.This paper contains several cut-and-paste figures, and is not easily placed in ftp-able form; it doesn't appear in this directory.
Keywords: dcs.
Faster storage devices cannot solve the I/O bottleneck problem for large multiprocessor systems if data passes through a file system on a single processor. Implementing the file system as a parallel program can significantly improve performance. Selectively revealing this parallel structure to utility programs can produce additional improvements, particularly on machines in which interprocessor communication is slow compared to aggregate I/O bandwidth.We have designed and prototyped a parallel file system that distributes each file across multiple storage devices and processors. Naive programs are able to access files just as they would with a conventional file system, while more sophisticated programs may export pieces of their code to the processors managing the data, for optimum performance. Theoretical and early empirical data indicate nearly linear speedup on critical operations for up to several dozen devices.
The Psyche project at the University of Rochester aims to develop a high-performance operating system to support a wide variety of models for parallel programming on a shared-memory multiprocessor. It is predicated on the assumption that no one model of process state or style of communication will prove appropriate for all applications, but that a shared-memory machine can and should support all models. Through a system of keys and access lists, incremental changes to address spaces, and direct execution of remote operations, Psyche will allow individual applications to balance the conflicting goals of efficiency, flexibility, and security. A pilot implementation is under construction on the BBN Butterfly Parallel Processor. (This paper is superceded by the 1988 ICPP paper, and does not appear in this directory.)
Last Change: 10 Aug 2012 / marty@cs.rochester.edu