We present a new limited form of interprocedural analysis called field analysis that can be used by a compiler to reduce the costs of modern language features such as object-oriented programming, automatic memory management, and run-time checks required for type safety. Unlike many previous interprocedural analyses, our analysis is cheap, and does not require access to the entire program. Field analysis exploits the declared access restrictions placed on fields in a modular language (e.g. field access modifiers in Java) in order to determine useful properties of fields of an object. We describe our implementation of field analysis in the Swift optimizing compiler for Java, as well a set of optimizations that exploit the results of field analysis. These optimizations include removal of run-time tests, compile-time resolution of method calls, object inlining, removal of unnecessary synchronization, and stack allocation. Our results demonstrate that field analysis is efficient and effective. Speedups average 7% on a wide range of applications, with some times reduced by up to 27%. Compile time overhead of field analysis is about 10%.

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.

Commercial SMP nodes are an attractive building block for software distributed shared memory systems. The advantages of using SMP nodes include fast communication among processors within the same node and potential gains from clustering where remote data fetched by one processor is used by other processors on the same node. This paper describes a major extension to the Shasta distributed shared memory system to run efficiently on a cluster of SMP nodes. The Shasta system keeps shared data coherent across nodes at a fine granularity by inserting inline code that checks the cache state of shared data before each load or store in an application. However allowing processors to share memory within the same SMP is complicated by race conditions that arise because the inline state check is non-atomic with respect to the actual load or store of shared data. We present a novel protocol that avoids such race conditions without the use of costly synchronization in the inline checking code. To characterize the benefits of using SMP nodes in the context of Shasta, we present detailed performance results for nine SPLASH-2 applications running on a cluster of Alpha multiprocessors.

research relevant to the design and application of high performance scientific computers. We test our ideas by designing, building, and using real systems. The systems we build are research prototypes; they are not intended to become products. There are two other research laboratories located in Palo Alto, the Network Systems

Despite a large research effort, software distributed shared memory systems have not been widely used to run parallel applications across clusters of computers.The higher performance of hardware multiprocessors makes them the preferred platform for developing and executing applications.In addition, most applications are distributed only in binary format for a handful of popular hardware systems.Due to their limited functionality, software systems cannot directly execute the applications developed for hardware platforms.We have developed a system called Shasta that attempts to address the issues of efficiency and transparency that have hindered wider acceptanceof software systems.Shastais adistributedsharedmemory system that supports coherence at a fine granularity in software and can efficiently exploit small-scale SMP nodes by allowing processes on the same node to share data at hardware speeds.This paper focuses on our goal of tapping into large classes of commercially available applications by transparently executing the same binaries thatrun on hardware platforms.We diicussthe issues involved in achieving transparent execution of binaries, which include supporting the full instruction set architecture, implementing an appropriate memory consistency model, and extending OS services across separatenodes.We also describe the techniquesusedin Shastatosolvetheabovepmblems.TheShastasystemisfullyfunctional on a prototype cluster of Alpha multiprocessors connected through Digital's Memory Channel network and can transparently run parallel applications on the cluster that were compiled to run on a single shared-memory multiprocessor.As an example of Shasta's flexibility, it can execute Oracle 7.3, a commercial database engine, across the cluster, including workloads modeled after the TPC-B and TPC-D database benchmarks.To characterize the performance of the system and the cost of providing complete transparency, we present performance results for microbenchmarks and applications running on the cluster, include preliminary results for Oracle runs.

This paper describes Shasta, a system that supports a shared address space in software on clusters of computers with physically distributed memory. A unique aspect of Shasta compared to most other software distributed shared memory systems is that shared data can be kept coherent at a fine granularity. In addition, the system allows the coherence granularity to vary across different shared data structures in a single application. Shasta implements the shared address space by transparently rewriting the application executable to intercept loads and stores. For each shared load or store, the inserted code checks to see if the data is available locally and communicates with other processors if necessary. The system uses numerous techniques to reduce the run-time overhead of these checks. Since Shasta is implemented entirely in software, it also provides tremendous flexibility in supporting different types of cache coherence protocols. We have implemented an efficient cache coherence protocol that incorporates a number of optimizations, including support for multiple communication granularities and use of relaxed memory models. This system is fully functional and runs on a cluster of Alpha workstations.The primary focus of this paper is to describe the techniques used in Shasta to reduce the checking overhead for supporting fine granularity sharing in software. These techniques include careful layout of the shared address space, scheduling the checking code for efficient execution on modern processors, using a simple method that checks loads using only the value loaded, reducing the extra cache misses caused by the checking code, and combining the checks for multiple loads and stores. To characterize the effect of these techniques, we present detailed performance results for the SPLASH-2 applications running on an Alpha processor. Without our optimizations, the checking overheads are excessively high, exceeding 100% for several applications. However, our techniques are effective in reducing these overheads to a range of 5% to 35% for almost all of the applications. We also describe our coherence protocol and present some preliminary results on the parallel performance of several applications running on our workstation cluster. Our experience so far indicates that once the cost of checking memory accesses is reduced using our techniques, the Shasta approach is an attractive software solution for supporting a shared address space with fine-grain access to data.

The authors present Jade, a high-level parallel programming language for managing course-grain concurrency. Jade simplifies programming by providing the programmer with the abstractions of sequential execution and a shared address space. Jade programmers augment sequential, imperative programs with constructs that declare how parts of the program access data; the Jade implementation dynamically interprets this information to execute the program in parallel. This parallel execution preserves the serial semantics of the original program. Jade has been implemented as an extension to C on shared-memory multiprocessors, a message-passing machine, networks of heterogeneous workstations, and systems with special-purpose functional units. Programs written in Jade run on all of these platforms without modification.>