Landmarks in the SC literature
A few pointers the book highlights from the vast literature:
- Lamport defined SC. Interestingly, the intuitive result that cores presenting loads and stores in program order to a cache-coherent memory system suffices for SC — the recipe of §3.7 — was believed long before Meixner and Sorin first actually proved it.
- SC vs. database serializability. Both insist that operations from all entities appear to affect shared state in a serial order, but the resemblance ends there:
| Sequential consistency | Serializability | |
|---|---|---|
| Operation | a single memory access | a transaction reading/writing multiple database entities |
| State | volatile memory, assumed not to fail | a database expected to survive failures |
| Guarantees | ordering + values of loads | ACID: Atomic (all-or-nothing under failure), Consistent, Isolated, Durable |
- The conflict-order view (Shasha and Snir). Following Lamport and SPARC, this chapter defined SC via a total order of all memory accesses. That eases intuition but is not necessary: one can constrain only conflicting accesses conflicting accesses Two accesses from different threads to the same location where at least one is a store (or RMW). defined in Chapter 3 — open in glossary and leave non-conflicting accesses unordered. This leaner view pays off for the relaxed models of Chapter 5.
A cautionary tale
Recall §3.8’s second verification scheme: remember the value a load speculatively read, and commit if the location still holds that value at replay. Martin et al. showed this check breaks for cores that also perform value prediction:
This is analogous to the classic ABA problem. Solutions exist — e.g., also replaying all loads dependent on the initially speculated load — but the book’s point is not the corner case itself. It is the closing moral of the whole chapter: prove that your implementation is correct rather than rely on intuition. (Chapter 11 supplies the proof tools.)
Check yourself
1.Shasha and Snir showed that SC needn't be defined via a total order of ALL memory accesses. What is the alternative?
2.How does SC differ from database serializability?
3.The cautionary tale: why does the commit-time replay check (§3.8) break when a core also performs VALUE PREDICTION?
3 questions
Chapter 3 references
- C. Blundell, M. M. K. Martin, and T. F. Wenisch. InvisiFence: Performance-transparent memory ordering in conventional multiprocessors. ISCA, 2009.
- H. W. Cain and M. H. Lipasti. Memory ordering: A value-based approach. ISCA, 2004.
- L. Ceze, J. Tuck, P. Montesinos, and J. Torrellas. BulkSC: Bulk enforcement of sequential consistency. ISCA, 2007.
- D. Gope and M. H. Lipasti. Atomic SC for simple in-order processors. HPCA, 2014.
- A. Singh, S. Narayanasamy, D. Marino, T. Millstein, and M. Musuvathi. End-to-end sequential consistency. ISCA, 2012.
- C. Lin, V. Nagarajan, R. Gupta, and B. Rajaram. Efficient sequential consistency via conflict ordering. ASPLOS, 2012.
- K. Gharachorloo, S. V. Adve, A. Gupta, J. Hennessy, and M. D. Hill. Specifying system requirements for memory consistency models. TR CSL-TR93-594, Stanford, 1993.
- K. Gharachorloo, A. Gupta, and J. Hennessy. Two techniques to enhance the performance of memory consistency models. ICPP, 1991.
- C. Guiady, B. Falsafi, and T. Vijaykumar. Is SC + ILP = RC? ISCA, 1999.
- J. Gray and A. Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, 1993.
- L. Hammond et al. Transactional memory coherence and consistency. ISCA, 2004.
- L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Trans. on Computers, C-28(9), 1979.
- M. H. Lipasti and J. P. Shen. Exceeding the dataflow limit via value prediction. MICRO, 1996.
- M. M. K. Martin, D. J. Sorin, H. W. Cain, M. D. Hill, and M. H. Lipasti. Correctly implementing value prediction in microprocessors that support multithreading or multiprocessing. MICRO, 2001.
- A. Meixner and D. J. Sorin. Dynamic verification of memory consistency in cache-coherent multithreaded computer architectures. DSN, 2006.
- P. Ranganathan, V. S. Pai, and S. V. Adve. Using speculative retirement and larger instruction windows to narrow the performance gap between memory consistency models. SPAA, 1997.
- A. Roth. Store vulnerability window (SVW): Re-execution filtering for enhanced load optimization. ISCA, 2005.
- D. Shasha and M. Snir. Efficient and correct execution of parallel programs that share memory. ACM TOPLAS, 10(2), 1988.
- T. F. Wenisch, A. Ailamaki, A. Moshovos, and B. Falsafi. Mechanisms for store-wait-free multiprocessors. ISCA, 2007.
- D. L. Weaver and T. Germond, Eds. SPARC Architecture Manual (Version 9). PTR Prentice Hall, 1994.
- K. C. Yeager. The MIPS R10000 superscalar microprocessor. IEEE Micro, 16(2), 1996.