Shared memory is a fundamentally important abstraction in parallel systems. Providing a shared memory abstraction across distributed hardware may prove equally important because it allows processes to access local and remote information uniformly. However, implementing consistent shared memory in a distributed environment is not only costly but also has fundamental problems of latency and scale. The results of recent research suggest that the principled weakening of memory consistency can reduce the cost of consistency maintenance while maintaining a viable model for programming. This project will investigate both theoretical and practical issues arising from the study of weakly consistent memories. The theoretical work will include a formal characterization of both existing and new memories and an investigation of properties of programs that execute correctly when memory consistency is weakened. The results of this research will enhance our fundamental understanding of weak memories. To demonstrate that weak memories can be easily programmed and lead to improved performance, the practical work will investigate programming and implementation of weakly consistent memories. Programmers of weakly consistent memories may write programs "directly" for the weekly consistent model, or programs written for traditional consistent memory may be transformed to run more efficiently on a weakly consistent memory. The project will identify application domains suitable for weak memories, develop idioms that simplify the programming of these memories, and develop efficient distributed implementations of weakly consistent memories. Since an application may be programmed differently on consistent and weak memories, overall performance depends both on the algorithmic efficiency of the application and the performance of the underlying weak memory implementation. Therefore, the work includes experimental research to study the overall performance of a prototype system using measures such as execution speedup and message overhead. Comprehensive investigation of the theory and practice of weakly consistent memories will yield substantial benefits applicable to both distributed systems and large scale multiprocessors.
