There is risk when doing experiments on real world systems and making real world measurements. In a theoretical system, a simulation, or a test bed, we can make assumptions about real world behaviors and gloss over potential problems. In a real world system, however, we have to solve those problems to get science done. Sometimes these are technical problems, like making sure a tool chain is consistent across many hosts. Sometimes these are policy problems, such as obtaining permission and access. The other users of a system have a reasonable expectation that their work will not be disrupted, so researchers studying those systems must be careful accommodate that expectation. Sometimes, systems researchers encounter these problems and a study must be changed or canceled, though the problem may have nothing to do with the study itself. Our goal was to make a high-quality all-to-all network latency map that captures features not present in existing latency data sets. We solved most of the technical problems needed to make the required measurements. We solved most policy problems too, often with complex technical solutions to get around a policy obstacle without creating disruptions. However, we eventually ran out of technical solutions: we ran afoul of a policy obstacle to a technical solution to a technical problem. There is no one to blame, and no one has done anything obviously wrong: the policy decision was a conservative one designed to protect the data of the regular users of the system. Although our resulting latency data set is not complete, we believe it still has value for various network applications. Our goal was to make a high-quality all-to-all network latency map that captures features not present in existing latency data sets. We solved most of the technical problems needed to make the required measurements. We solved most policy problems too, often with complex technical solutions to get around a policy obstacle without creating disruptions. However, we eventually ran out of technical solutions: we ran afoul of a policy obstacle to a technical solution to a technical problem. There is no one to blame, and no one has done anything obviously wrong: the policy decision was a conservative one designed to protect the data of the regular users of the system. Although our resulting latency data set is not complete, we believe it still has value for various network applications.

We present a completely decentralized algorithm for parallel job scheduling and load balancing in distributed peer-to-peer environments. This algorithm is useful for meta-scheduling across known clusters and scheduling on desktop grids. To accomplish this, we build on previous work to route jobs to appropriate resources then use the new algorithm to start parallel jobs and balance load across the grid. We also discuss what constitutes useful clustering's for this algorithm as well as inherent scaling limitations. Ultimately, we show that our algorithm performs comparably to one using centralized load balancing with global up-to-date information. The principal contribution of this work is that the parallel job scheduling is completely decentralized, which is not featured in previous work, and enables reliable ad hoc sharing of distributed resources to run parallel computations.

We propose resource discovery and load balancing techniques to accommodate computing nodes with many types of computing elements, such as multi-core CPUs and GPUs, in a peer-to-peer desktop grid architecture. Heterogeneous nodes can have multiple types of computing elements, and the performance and characteristics of each computing element can be very different. Our scheme takes into account these diverse aspects of heterogeneous nodes to maximize overall system throughput. However, straightforward methods of handling diverse computing elements that differ on many axes can result in high overheads, both in local state and in communication volume. We describe approaches that minimize messaging costs without sacrificing the failure resilience provided by an underlying peer-to-peer overlay network. Simulation results show that our scheme's load balancing performance is comparable to that of a centralized approach, that communication costs are reduced significantly compared to the existing system, and that failure resilience is not compromised.

Data-intensive distributed applications can increase their performance by running on a cluster of hosts connected via high-bandwidth interconnections. However, there is no effective method to find such a bandwidth-constrained cluster in a decentralized fashion. Our work is inspired by prior work that treats Internet bandwidth as an approximate tree metric space. This paper presents a decentralized, accurate, and efficient method to find a cluster of Internet hosts, given the desired cluster size and minimum interconnection bandwidth. We describe a centralized polynomial time algorithm for a tree metric space, along with a proof of correctness. We then provide a decentralized version of the algorithm. Simulation experiments with two real-world datasets confirm that our clustering approach achieves high accuracy and scalability. We also discuss the costs of decentralization and how the treeness of the dataset affects clustering accuracy.

The distributed nature of modern computing makes end-to-end prediction of network bandwidth increasingly important. Our work is inspired by prior work that treats the Internet and bandwidth as an approximate tree metric space. This paper presents a decentralized, accurate, and low cost system that predicts pairwise bandwidth between hosts. We describe an algorithm to construct a distributed tree that embeds bandwidth measurements. The correctness of the algorithm is provable when driven by precise measurements. We then describe three novel heuristics that achieve high accuracy for predicting bandwidth even with imprecise input data. Simulation experiments with a real-world dataset confirm that our approach shows high accuracy with low cost.

The majority of CPUs now sold contain multiple computing cores. However, current desktop grid computing systems either ignore the multiplicity of cores, or treat them as distinct, independent machines. The latter approach ignores the resource contention present between cores in a single CPU, while the former approach fails to take advantage of significant computing power. We propose a decentralized resource management framework for exploiting multi-core nodes in peer-to-peer grids. We present two new load-balancing schemes that explicitly account for the resource sharing and contention of multiple cores, and propose a simple simulation model that can represent a continuum of resource sharing among cores of a CPU. We use simulation to confirm that our two algorithms match jobs w ith computing nodes efficiently, and balance load during the lifetime of the computing jobs.

We present some recent and ongoing work in our decentralized desktop computing grid project. Specifically, we discuss matching jobs with compute nodes in a peer-to-peer grid of heterogeneous platforms, and the implementation of our algorithms in a concrete system.

Desktop grids have evolved to combine Peer-to-Peer and Grid computing techniques to improve the robustness, reliability and scalability of job execution infrastructures. However, efficiently matching incoming jobs to available system resources and achieving good load balance in a fully decentralized and heterogeneous computing environment is a challenging problem. In this paper, we extend our prior work with a new decentralized algorithm for maintaining approximate global load information, and a job pushing mechanism that uses the global information to push jobs towards underutilized portions of the system. The resulting system more effectively balances load and improves overall system throughput. Through a comparative analysis of experimental results across different system configurations and job profiles, performed via simulation, we show that our system can reliably execute Grid applications on a distributed set of resources both with low cost and with good load balance.

The goal of the work described in this paper is to design and build a scalable infrastructure for executing grid applications on a widely distributed set of resources. Such grid infrastructure must be decentralized, robust, highly available, and scalable, while efficiently mapping application instances to available resources in the system. However, current desktop grid computing platforms are typically based on a client-server architecture, which has inherent shortcomings with respect to robustness, reliability and scalability. Fortunately, these problems can be addressed through the capabilities promised by new techniques and approaches in peer-to-peer (P2P) systems. By employing P2P services, our system allows users to submit jobs to be run in the system and to run jobs submitted by other users on any resources available in the system, essentially allowing a group of users to form an ad-hoc set of shared resources. The initial target application areas for the desktop grid system are in astronomy and space science simulation and data analysis.

We describe the design, implementation, and performance of MFS, a new file system designed to support efficient widearea collaboration. MFS is structured around the twin abstractions of lightweight sessions and snapshots, along with a highly configurable capability-based security architecture. Sessions simplify and clarify collaborative semantics. Snapshots allow atomic access to arbitrary collections of files, and allow sharing to be defined in a simple and expressive fashion. MFS’s security architecture is a layered system that allows diverse usage scenarios. Pure capability-based access allows clients to access data without needing expensive public key or authentication servers, or complicated administration. However, MFS’s capabilities can also be watermarked, allowing a range of services to be added on a per-mount basis, up to and including traditional user authentication based on passwords or public keys. Basing the system around the use of immutable snapshots enables the underlying system to use several performance optimizations aggressively. Performance results from our MFS prototype show that, far from adding overhead, the use of snapshots allows the system to perform comparably to NFS in the local-area case and significantly outperform existing systems in wide-area environments.

We describe d-spaces, a replica control protocol defined in terms of quorum sets on multi-dimensional logical structures. Our work is motivated by asymmetrical access patterns, where the number of read accesses to data are dominant relative to update accesses, i.e. where the protocols should be read-few write-many. D-spaces are optimal with respect to quorum group sizes. The quality of the tradeoff between read efficiency and update availability is not matched by existing quorum protocols. We also propose a novel scheme for implementing d-spaces that combines caching and local information to provide a best-effort form of global views. This allows quorum reconfiguration to be lightweight without impacting access latencies, even when the rate of membership changes is very high.

Peer-to-peer systems can be used to form a low-latency decentralized data delivery system. Structured peer-to-peer systems provide both low latency and excellent load balance with uniform query and data distributions. Under the more common skewed access distributions, however, individual nodes are easily overloaded, resulting in poor global performance and lost messages. This paper describes a lightweight, adaptive, and system-neutral replication protocol, called LAR, that maintains low access latencies and good load balance even under highly skewed demand. We apply LAR to Chord and show that it has lower overhead and better performance than existing replication strategies.

We describe a method for performing trust-preserving set operations by untrusted parties. Our motivation for this is the problem of securely reusing content-based search results in peer-to-peer networks. We model search results and indexes as data sets. Such sets have value for answering a new query only if they are trusted. In the absence of any system-wide security mechanism, a data set is trusted by a node a only if it was generated by some node which is trusted by a. Our main contributions are a formal definition of the problem as well as an efficient scheme that solves this problem by allowing untrusted peers to perform set operations on trusted data sets while also producing unforgeable proofs of correctness. This is accomplished by requiring trusted nodes to sign appropriately-defined digests of generated sets; each such digest consists of an RSA accumulator and a Bloom filter. The scheme is general, and has other applications as well. We give an analysis demonstrating the low overhead of the scheme, and we include experimental data which confirm the analysis.

Summary form only given. Recent work on peer-to-peer systems has demonstrated the ability to deliver low latencies and good load balance when demand for data is relatively uniform. We describe an adaptive replication protocol that delivers low latencies, good load balance even when demand is heavily skewed. The protocol can withstand arbitrary and instantaneous changes in demand distribution. Our approach also addresses classical concerns related to topological constraints of asymmetrical namespaces, such as hierarchical bottlenecks in the context of hierarchical namespaces. The protocol replicates routing state in an ad-hoc manner based on profiled information, is lightweight, scalable, and requires no replica consistency guarantees.

This paper presents the design, implementation, and evaluation of the replication framework of Deno, a decentralized, peer-to-peer object-replication system targeted for weakly connected environments. Deno uses weighted voting for availability and pair-wise, epidemic information flow for flexibility. This combination allows the protocols to operate with less than full connectivity, to easily adapt to changes in group membership, and to make few assumptions about the underlying network topology. We present two versions of Deno's protocol that differ in the consistency levels they support. We also propose security extensions to handle a class of malicious actions that involve misrepresentation of protocol information. Deno has been implemented and runs on top of Linux and Win32 platforms. We use the Deno prototype to characterize the performance of the Deno protocols and extensions. Our study reveals several interesting results that provide fundamental insight into the benefits of decentralization and the mechanics of epidemic protocols.

No abstract available.

Maintaining strict consistency of replicated data can be prohibitively expensive for many distributed applications and environments. In order to alleviate this problem, some systems allow applications to access stale, imprecise data. Due to relaxed correctness requirements, many applications can tolerate stale data but require that the imprecision be properly bounded. This paper describes ReBound, a system that provides an adaptive framework for supporting and exploiting data precision vs. efficiency tradeoffs in symmetric replication environments via distributed precision control. Previous work proposed efficient precision control algorithms that support continuous read requests tagged with custom numerical precision ranges. ReBound generalizes and extends previous work with a new algorithm for continuous reads, support for ad-hoc reads, and light-weight adaptation mechanisms for coping with dynamically changing update patterns. This paper also presents preliminary experimental results, based on a prototype implementation, that demonstrate the performance advantages of exploiting precision vs. efficiency tradeoffs.

This paper presents the replication framework of Deno, an object replication system specifically designed for mobile and weakly-connected environments. Deno uses weighted voting for availability and pair-wise, epidemic information flow for flexibility. This combination allows the protocols to operate with less than full connectivity, to easily adapt to changes in group membership, and to make few assumptions about the underlying network topology. Deno has been implemented and runs on top of Linux and Win32 platforms. We use the Deno prototype to characterize the performance of two versions of Deno's protocol. The first version enables globally serializable execution of update transactions. The second supports a weaker consistency level that still guarantees transactionally-consistent access to replicated data. We demonstrate that the incremental cost of providing global serializability is low, and that speculative dissemination of updates can significantly improve commit performance.

We investigate the problem of distributing communicating objects across wide-area environments. Our goals are to balance load, minimize network communication, and use resources efficiently. However, applications running in such environments are often dynamic and highly unpredictable. Furthermore, synchronous communication is usually too expensive to be used in disseminating load information. We therefore investigate policies that use local information to approximate desired global behaviors. Our results with Java applications show that simple, local approaches are surprisingly effective in capturing load information and object relationships, and in making migration and clustering decisions based on profiled information.

This paper proposes and evaluates a new mechanism, rate windows, for I/O and network rate policing. The goal of the proposed system is to provide a simple, yet effective way to enforce resource limits on target classes of jobs in a system. This work was motivated by our Linger Longer infrastructure, which harvests idle cycles in networks of workstations. Network and I/O throttling is crucial because Linger Longer can leave guest jobs on non-idle nodes and machine owners should not be adversely affected. Our approach is quite simple. We use a sliding window of recent events to compute the average rate for a target resource. The assigned limit is enforced by the simple expedient of putting application processes to sleep when they issue requests that would bring their resource utilization out of the allowable profile. Our I/O system call intercept model makes the rate windows mechanism light-weight and highly portable. Our experimental results show that we are able to limit resource usage to within a few percent of target usages.

This paper presents a theoretical framework based on Bayesian decision theory for analyzing recently reported results on implicit coscheduling of parallel applications on clusters of workstations. Using probabilistic modeling, We show that the approach presented can be applied for processes with arbitrary communication mixes. We also note that our approach can be used for deciding the additional spin times in the case of spin-yield. Finally, we present arguments for the use of a different notion of fairness than assumed by prior work.

Networks of workstations are fast becoming the standard environment for parallel applications. However, the use of "found" resources as a platform for tightly-coupled runtime environments has at least three obstacles: contention for resources, differing processor speeds, and processor heterogeneity. All three obstacles result in load imbalance, leading to poor performance for scientific applications. This paper describes the use of thread migration in transparently addressing this load imbalance in the context of the CVM software distributed shared memory system. We describe the implementation and performance of mechanisms and policies that accommodate both resource contention, and heterogeneity in clock speed and processor type. Our results show that these cycles can indeed be effectively exploited, and that the runtime cost of processor heterogeneity can be quite manageable. Along the way, however, we identify a number of problems that need to be addressed before such systems can enjoy widespread use.

This paper proposes extensions to the backfilling job-scheduling algorithm that significantly improve its performance. We introduce variations that sort the "backfilling order" in priority-based and randomized fashions. We examine the effectiveness of guarantees present in conservative backfilling and find that initial guarantees have limited practical value, while the performance of a "no-guarantee" algorithm can be significantly better when combined with extensions that we introduce. Our study differs from many similar studies in using traces that contain user estimates. We find that actual overestimates are large and significantly different from simple models. We propose the use of speculative backfilling and speculative test runs to counteract these large overestimations. Finally, we explore the impact of dynamic, system-directed adaptation of application parallelism. The cumulative improvements of these techniques decrease the bounded slowdown, our primary metric, to less then 15% of conservative backfilling.

Discusses the implementation and performance of bounded voting, which is a new object replication protocol designed for use in mobile and weakly-connected environments. We show that the protocol eliminates several restrictions of previous work, such as the need for (1) strong or complete connectivity, (2) complete knowledge of system membership, and (3) low update rates. The protocol implements an asynchronous, weighted-voting scheme via epidemic information flow, and commits updates in an entirely decentralized fashion. A proxy mechanism is used to enable transparent handling of planned disconnections. We use a detailed simulation study to characterize the performance of bounded voting under a variety of loads and environments, and to compare it to another decentralized epidemic protocol. We further investigate the performance impact of the proxy mechanism.

We describe the design and use of thetapemechanism, a new high-level abstraction of accesses to shared data for software DSMs. Tapes consolidate and generalize a number of recent protocol optimizations, including update-based locks and recorded-replay barriers. Tapes are usually created by “recording” shared accesses. The resulting recordings can be used to anticipate future accesses by tailoring data movement to application semantics. Tapes-based mechanisms are layered on top of existing shared-memory protocols, and are largely independent of the underlying memory model. Tapes can also be used to emulate the data-movement semantics of several update-based protocol implementations, without altering the underlying protocol implementation. We have used tapes to create the Tapeworm synchronization library. Tapeworm implements sophisticated record-replay mechanisms across barriers, augments locks with data-movement semantics, and allows the use of producer-consumer segments, which move entire modified segments when any portion of the segment is accessed. We show that Tapeworm eliminates 85% of remote misses, reduces message traffic by 63%, and improves performance by an average of 29% for our application suite.

We present the design and evaluation of a new data-race-detection technique. Our technique executes at runtime rather than post-mortem, and handles unmodified shared-memory applications that run on top of CVM, a software distributed shared memory system. We do not assume explicit associations between synchronization and shared data, and require neither compiler support nor program source. Instead, we use a binary code re-writer to instrument instructions that may access shared memory. The most novel aspect of our system is that we are able to use information from the underlying memory system implementation in order to reduce the number of comparisons made at runtime. We present an experimental evaluation of our techniques by using our system to look for data races in five common shared-memory programs. We quantify the effect of several optimizations to the basic technique: data flow analysis, instrumentation batching, runtime code modification, and instrumentation inlining. Our system correctly found races in three of the five programs, including two from a standard benchmark suite. The slowdown of this debugging technique averages less than 2.5 for our applications.

Backfilling is a simple and effective way of improving the utilization of space-sharing schedulers. Simple first-come-first-served approaches are ineffective because large jobs can fragment the available resources. Backfilling schedulers address this problem by allowing jobs to move ahead in the queue, provided that they will not delay subsequent jobs. Previous research has shown that inaccurate estimates of execution times can lead to better backfilling schedules. We characterize this effect on several workloads, and show that average slowdowns can be effectively reduced by systematically lengthening estimated execution times. Further, we show that the average job slowdown metric can be addressed directly by sorting jobs by increasing execution time. Finally, we modify our sorting scheduler to ensure that incoming jobs can be given hard guarantees. The resulting scheduler guarantees to avoid starvation, and performs significantly better than previous backfilling schedulers.

We present the design of an interface to allow applications to export tuning alternatives to a higher-level system. By exposing different parameters that can be changed at runtime, applications can be made to adapt to changes in their execution environment due to other programs, or the addition or deletion of nodes, communication links, etc. An integral part of this interface is that an application not only exposes its options, but also the resource utilization of each option and the effect that the option will have on the application's performance. We discuss how these options can be evaluated to tune the overall performance of a collection of applications in the system. Finally, we show preliminary results from a database application that is automatically reconfigured by the system from query shipping to data shipping based on the number of active clients.

We describe methods of identifying and exploiting sharing patterns in multi-threaded DSM applications. Active correlation tracking is used to determine the affinity, or amount of sharing, in pairs of threads. Thread affinities are combined to create correlation maps, which summarize sharing between all pairs of threads in the application. Correlation maps can be used in two ways. First, they can be used as an aid for performance tuning, Second, they can be used to estimate the impact on communication requirements of reconfiguring running applications through thread migration. Thread migration provides a way of tuning applications for which sharing information is not known a priori, and a means of adapting to dynamic algorithms or environments. We show that i) accurate thread affinities can be obtained without multiple rounds of migration, ii) thread affinities lead to good approximations of application communication requirements, iii) simple heuristics can use thread affinities to efficiently approximate optimal mappings of threads to nodes, and iv) good placement is essential for high performance.

A consistency protocol can be termed symmetric if all processors are treated identically when they access common resources. By contrast, asymmetric protocols usually assign a home or manager to each resource. Use of the resource by the home incurs less overhead than use by other processors. The key to good performance in such systems is to ensure that the asymmetry of the underlying protocol is skewed in the same way as that of the application. This paper presents a comparative evaluation of a symmetric and an asymmetric DSM protocol. We pay particular attention to those performance differences caused by symmetric and asymmetric features of the protocols. We then present the design and evaluation of an improved asymmetric writer protocol that dynamically migrates ownership according to access patterns. We show that the new protocol outperforms and is more stable than the non-migrating asymmetric protocol, and has much less memory overhead than the symmetric protocol. 1.

this paper is a characterization of the delays actually observed in a suite of applications. We show that the majority of notification delays result from a small number of large delays. These delays can dominate any gains achieved through use of new network technologies. The impact of these delays can be considerable. Our applications averaged more than 31% slower without interrupts than with them. This result argues that the problem is serious, and needs to be addressed either by including interrupts in emerging standards, or through use of the techniques discussed below

This paper presents an investigation into local mechanisms and scheduling policies that allow guest processes to efficiently exploit otherwissidle workstation resources.Unlike traditional policies that harvest cycles only from unused machines, we target policies that exploit resources even from machines that have active users.We present a set of kernel extensions that allow these policies to operate without significantly impacting host processes: 1) a new guesf process priority that prevents processes from stealing any processor time from host processes, 2) a new page replacement policy that imposes hard bounds on the number of physical pages that can be obtained by guest processes when host processes are active, and 3) a new page-out strategy that adaptively increases the pageout rate of guest processes when new host processes are started.We evaluate both the individual impacts of each mechanism, and their utility in supporting Linger-Longer, an aggressive cycleharvesting policy.

We describe a new replicated-object protocol designed for use in mobile and weakly-connected environments. The protocol differs from previous protocols in combining epidemic information propagation with voting, and in using fixed per-object currencies for voting. The advantage of epidemic protocols is that data movement only requires pairwise communication. Hence, there is no need for a majority quorum to be available and simultaneously connected at any single time. The protocols increase availability by using voting, rather than primary copy or primary commit schemes. Finally, the use of per-object voting currencies allows votes to take place in an entirely decentralized fashion, without any server having complete knowledge of group membership. We show that currency allocation can be used to implement diverse policies. For example, uniform currency distributions emulate traditional dynamic voting schemes, while allocating all currency to a single server emulates a primary-copy scheme. We present simulation results showing both schemes, as well as the performance advantages of using currency proxies to temporarily reallocate currency during planned disconnections.

Networks of workstations are characterized by dynamic resource capacities. Such environments can only be efficiently exploited by applications that are dynamically reconfigurable. The paper explores mechanisms and policies that enable online reconfiguration of shared memory applications through thread migration. We describe the design and preliminary performance of a distributed shared memory (DSM) system that performs online remappings of threads to nodes based on sharing behavior. Our system obtains complete sharing information through a novel correlation tracking phase that avoids the thread thrashing that characterizes previous approaches. This information is used to evaluate the communication required by a given thread mapping and to predict the resulting performance.

We describe the design and early functionality of the Active Harmony global resource management system. Harmony is an infrastructure designed to efficiently execute parallel applications in large scale, dynamic environments. Harmony differs from other projects with similar goals in that the system automatically adapts ongoing computations to changing conditions through online reconfiguration. This reconfiguration can consist of system directed migration of work at several different levels, or automatic application adaptation through the use of tuning options exported by Harmony aware applications. We describe early experience with work migration at the level of procedures, processes and lightweight threads.

This work presents a new I/O system design and implementation targeted at applications that perform data streaming. The approach yields true zero-copy transfers between I/O devices in many instances. We give a general characterization of I/O elements and provide a framework that allows analysis of the potential for zero-copy transfers. Finally, we describe the design, implementation, and performance of a prototype I/O system in a real time, embeddable, 32-bit operating system whose design is based on the presented analysis to minimize data copying.

This paper evaluates the use of per-node multithreading to hide remote memory and synchronization latencies in software DSMs. As with hardware systems, multithreading in software systems can be used to reduce the costs of remote requests by running other threads when the current thread blocks. We added multithreading to the CVM software DSM and evaluated its impact on the performance of a suite of common shared memory programs. Multithreading resulted in speed improvements of at least 20 percent in two of the applications, and better than 15 percent for several other applications. However, we also found that good performance cannot always be achieved transparently for nontrivial applications. Also, the characteristics of the underlying DSM protocol can have a large effect on multithreading's utility.

This paper evaluates the use of per-node multi-threading to hide remote memory and synchronization latencies in a software DSM. As with hardware systems, multi-threading in software systems can be used to reduce the costs of remote requests by switching threads when the current thread blocks. We added multi-threading to the CVM software DSM and evaluated its impact on performance for a suite of common shared memory programs. Multi-threading resulted in speed improvements of at least 17% in three of the seven applications in our suite, and lesser improvements in the other applications. However, we found that: good performance is not always achievable transparently for non-trivial applications; multi-threading can negatively interact with DSM operations; multi-threading decreases cache and TLB locality; and any multi-threading speedup is dependent on available work.

This paper presents a detailed comparison of the relative importance of allowing concurrent writers versus the choice of the underlying consistency model. Our comparison is based on single- and multiple-writer versions of a lazy release consistent (LRC) protocol, and a single-writer sequentially consistent protocol, all implemented in the CVM software distributed shared memory system. We find that in our environment, which we believe to be representative of distributed systems today and in the near future, the consistency model has a much higher impact on overall performance than the choice of whether to allow concurrent writers. The multiple writer LRC protocol performs an average of 9% better than the single writer LRC protocol, but 34% better than the single-writer sequentially consistent protocol. Set against this, MW-LRC required an average of 72% memory overhead, compared to 10% overhead for the single-writer protocoIs.

No abstract available.

Compares the performance of software-supported shared memory on a general-purpose network to hardware-supported shared memory on a dedicated interconnect. Up to eight processors, the results are based on the execution of a set of application programs on a SGI 4D/480 multiprocessor and on TreadMarks, a distributed shared memory system that runs on a Fore ATM LAN of DECstation-5000/240s. Since the DECstation and the 4D/480 use the same processor, primary cache, and compiler, the shared-memory implementation is the principal difference between the systems. Beyond eight processors, the results are based on execution-driven simulation. Specifically, the authors compare a software implementation on a general-purpose network of uniprocessor nodes, a hardware implementation using a directory-based protocol on a dedicated interconnect, and a combined implementation using software to provide shared memory between multiprocessor nodes with hardware implementing shared memory within a node.>

We evaluate the effect of processor speed, network characteristics, and software overhead on the performance of release-consistent software distributed shared memory. We examine five different protocols for implementing release consistency: eager update, eager invalidate, lazy update, lazy invalidate, and a new protocol called lazy hybrid. This lazy hybrid protocol combines the benefits of both lazy update and lazy invalidate.

Relaxed memory consistency models, such as release consistency, were introduced in order to reduce the impact of remote memory access latency in both software and hardware distributed shared memory (DSM). However, in a software DSM, it is also important to reduce the number of messages and the amount of data exchanged for remote memory access. Lazy release consistency is a new algorithm for implementing release consistency that lazily pulls modifications across the interconnect only when necessary. Trace-driven simulation using the SPLASH benchmarks indicates that lazy release consistency reduces both the number of messages and the amount of data transferred between processors. These reductions are especially significant for programs that exhibit false sharing and make extensive use of locks.