Alexander Jaffe
ABSTRACT
The memory consistency model is a fundamental system property characterizing a multiprocessor. The relative merits of strict versus relaxed memory models have been widely debated in terms of their impact on performance, hardware complexity and programmability. This paper adds a new dimension to this discussion: the impact of memory models on software reliability. By allowing some instructions to reorder, weak memory models may expand the window between critical memory operations. This can increase the chance of an undesirable thread-interleaving, thus allowing an otherwise-unlikely concurrency bug to manifest. To explore this phenomenon, we define and study a probabilistic model of shared-memory parallel programs that takes into account such reordering. We use this model to formally derive bounds on the vulnerability to concurrency bugs of different memory models. Our results show that for 2 concurrent threads, weaker memory models do indeed have a higher likelihood of allowing bugs. On the other hand, we show that as the number of parallel, buggy threads increases, the gap between the different memory models becomes proportionally insignificant, and thus the importance of using a strict memory model diminishes.
- S. V. Adve and K. Gharachorloo. Shared memory consistency models: A tutorial. IEEE Computer, 29(12):66--76, December 1996. Google Scholar
Digital Library
- S. V. Adve and M. D. Hill. Weak ordering--a new definition. In ACM IEEE International Symposium on Computer Architecture, 1990. Google ScholarDigital Library
- AMD Corp. AMD64 Architecture Programmer's Manual - Volume 2: System Programming, July 2007.Google Scholar
- C. Artho, K. Havelund, and A. Biere. High-level data races. Journal on Software Testing, Verification & Reliability, 13(4):220--227, 2003.Google ScholarCross Ref
- Arvind and J.-W. Maessen. Memory model = instruction reordering + store atomicity. In ACM IEEE International Symposium on Computer Architecture, 2006. Google ScholarDigital Library
- H.-J. Boehm and S. V. Adve. Foundations of the C++ concurrency memory model. In ACM SIGPLAN conference on Programming Language Design and Implementation, 2008. Google ScholarDigital Library
- L. Ceze, J. Tuck, P. Montesinos, and J. Torrellas. BulkSC: Bulk enforcement of sequential consistency. In ACM IEEE International Symposium on Computer Architecture, 2007. Google ScholarDigital Library
- M. Dubois, C. Scheurich, and F. A. Briggs. Memory access buffering in multiprocessors. In ACM IEEE International Symposium on Computer Architecture, 1986. Google ScholarDigital Library
- C. Flanagan and S. Qadeer. A type and effect system for atomicity. In ACM SIGPLAN Conference on Programming Language Design and Implementation, 2003. Google ScholarDigital Library
- K. Gharachorloo, A. Gupta, and J. Hennessy. Two techniques to enhance the performance of memory consistency models. In International Conference on Parallel Processing, 1991.Google Scholar
- K. Gharachorloo, D. Lenoski, J. Laudon, P. Gibbons, A. Gupta, and J. Hennessy. Memory consistency and event ordering in scalable shared-memory multiprocessors. In ACM IEEE International Symposium on Computer Architecture, 1990. Google ScholarDigital Library
- C. Gniady, B. Falsafi, and T. N. Vijaykumar. Is SC + ILP = RC? In ACM IEEE International Symposium on Computer Architecture, 1999. Google ScholarDigital Library
- J. R. Goodman. Cache consistency and sequential consistency. Technical Report 1006, University of Wisconsin-Madison, 1989.Google Scholar
- Intel Corp. Intel 64 and IA-32 Architectures Software Developer's Manual--Volume 3A: System Programming Guide, Part 1, December 2009.Google Scholar
- L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, 28(9):690--691, September 1979. Google ScholarDigital Library
- J. Lee and D. Padua. Hiding relaxed memory consistency with compilers. In International Conference on Parallel Architectures and Compilation Techniques, 2000. Google ScholarDigital Library
- S. Lu, S. Park, E. Seo, and Y. Zhou. Learning from mistakes--a comprehensive study on real world concurrency bug characteristics. In 13th International Conference on Architectural Support for Programming Languages and Operating Systems, 2008. Google ScholarDigital Library
- J. Manson, W. Pugh, and S. V. Adve. The Java memory model. In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2005. Google ScholarDigital Library
- SPARC International, Inc. The SPARC Architecture Manual--Version 8, 1992. Google ScholarDigital Library
Index Terms
- The impact of memory models on software reliability in multiprocessors
Recommendations
On Thin Air Reads Towards an Event Structures Model of Relaxed Memory
LICS '16: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer ScienceThis is the first paper to propose a pure event structures model of relaxed memory. We propose confusion-free event structures over an alphabet with a justification relation as a model. Executions are modeled by justified configurations, where every ...
Impact of Instruction Re-Ordering on the Correctness of Shared-Memory Programs
ISPAN '05: Proceedings of the 8th International Symposium on Parallel Architectures,Algorithms and NetworksSequential consistency is an intuitive consistency model that simplifies reasoning about concurrent multiprocessor programs. Most implementations of high-performance multiprocessors, however, utilize mechanisms that allow instructions to execute out of ...
A Unified Formalization of Four Shared-Memory Models
The authors present a data-race-free-1, shared-memory model that unifies four earliermodels: weak ordering, release consistency (with sequentially consistent specialoperations), the VAX memory model, and data-race-free-0. Data-race-free-1 unifies ...
Comments