Adaptive consistency protocols for local and wide area networks

While Distributed Shared Memory (DSM) systems provide runtime speedup for compute-intensive applications, performance is often limited by use of a suboptimal consistency protocol. DSM systems traditionally either provide only one consistency protocol, and the application must accept the performance even if it is suboptimal, or require the application programmer to select the protocol, burdening the programmer to analyze details about the algorithm and performance effects of sharing data. To address these problems, recent research proposes that DSM adaptively chooses the consistency protocol. However, these approaches—based on data access patterns—may choose a suboptimal protocol and actually degrade performance. Furthermore, factors unknown until runtime may affect consistency protocol performance, so for the same application, a protocol chosen by access pattern may be optimal in one environment but suboptimal in another environment.; This dissertation describes a new approach for DSM to choose the best consistency protocol based on measured protocol performance. Because this measurement-based approach considers protocol performance in the given runtime environment, the DSM can more intelligently select the consistency protocol. Our measurement-based approach chooses among traditional on-demand and update-based protocols, as well as a new demand-update protocol. A prototype implementation demonstrates our measurement-based approach chooses the optimal consistency protocols and provides application runtime speedup, even in cases where access pattern-based approaches fail to do so. Our approach guarantees application performance to be at least at good as a system that provides the most optimal single protocol for the application. Our approach further improves performance by choosing the optimal protocol on a per-data segment basis. We also demonstrate how measured protocol performance can identify and handle situations when a segment's optimal protocol must be reevaluated because of changes in the application algorithm, runtime environment, or work reassignments.