A Primer on Memory Consistency and Cache Coherence

1 Morgan Claypool Publishers& Editor: Mark D. Hill, University of WisconsinMORGAN&CLAYPOOLCM&Morgan Claypool Publishers&About SYNTHESIsThis volume is a printed version of a work that appears in the SynthesisDigital Library of Engineering and Computer Science. Synthesis Lecturesprovide concise, original presentations of important research and developmenttopics, published quickly, in digital and print formats. For more informationvisit LECTURES ONCOMPUTER ARCHITECTUREMark D. Hill, Series EditorISBN: 978-1-60845-564-5978160845564590000 Series ISSN: 1935-3235 SYNTHESIS LECTURES ONCOMPUTER ARCHITECTUREA Primer ON Memory Consistency AND Cache COHERENCESORIN HILL WOODA Primer on Memory Consistencyand Cache CoherenceDaniel J. Sorin, Duke UniversityMark D. Hill and David A. Wood, University of Wisconsin, MadisonMany modern computer systems and most multicore chips (chip multiprocessors) support sharedmemory in hardware.

2 In a shared Memory system, each of the processor cores may read and write toa single shared address space. For a shared Memory machine, the Memory Consistency model definesthe architecturally visible behavior of its Memory system. Consistency definitions provide rules aboutloads and stores (or Memory reads and writes) and how they act upon Memory . As part of supportinga Memory Consistency model, many machines also provide Cache Coherence proto-cols that ensure thatmultiple cached copies of data are kept up-to-date. The goal of this Primer is to provide readers witha basic understanding of Consistency and Coherence . This understanding includes both the issues thatmust be solved as well as a variety of solutions. We present both high-level concepts as well as specific,concrete examples from real-world Primer on MemoryConsistency andCache CoherenceDaniel J. SorinMark D.

3 HillDavid A. WoodA Primer on Memory Consistency and Cache CoherenceiiOne liner Chapter TitleSynthesis Lectures on Computer ArchitectureEditorMark D. Hill, University of WisconsinSynthesis Lectures on Computer Architecture publishes 50- to 100-page publications on topics pertaining to the science and art of designing, analyzing, selecting and interconnecting hardware components to create computers that meet functional, performance and cost goals. The scope will largely follow the purview of premier computer architecture conferences, such as ISCA, HPCA, MICRO, and Primer on Memory Consistency and Cache CoherenceDaniel J. Sorin, Mark D. Hill, and David A. Wood2011 Dynamic Binary Modification: Tools, Techniques, and ApplicationsKim Hazelwood2011 Quantum Computing for Computer Architects, Second EditionTzvetan S. Metodi, Arvin I.

4 Faruque, Frederic T. Chong2011 High Performance Datacenter Networks: Architectures, Algorithms, and OpportunitiesDennis Abts, John Kim2011 Processor Microarchitecture: An Implementation PerspectiveAntonio Gonz lez, Fernando Latorre, and Grigorios Magklis2011 Transactional Memory , 2nd edition Tim Harris, James Larus, and Ravi Rajwar 2010 Computer Architecture Performance Evaluation ModelsLieven Eeckhout2010 Introduction to Reconfigurable Supercomputing Marco Lanzagorta, Stephen Bique, and Robert Rosenberg 2009On-Chip NetworksNatalie Enright Jerger and Li-Shiuan Peh2009 The Memory System: You Can t Avoid It, You Can t Ignore It, You Can t Fake ItBruce Jacob2009 Fault Tolerant Computer ArchitectureDaniel J. Sorin2009 The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale MachinesLuiz Andr Barroso and Urs H lzle2009 Computer Architecture Techniques for Power-EfficiencyStefanos Kaxiras and Margaret Martonosi2008 Chip Multiprocessor Architecture: Techniques to Improve Throughput and LatencyKunle Olukotun, Lance Hammond, and James Laudon2007 Transactional Memory James R.

5 Larus and Ravi Rajwar 2006 Quantum Computing for Computer ArchitectsTzvetan S. Metodi and Frederic T. Chong2006iiiCopyright 2011 by Morgan & ClaypoolAll rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means electronic, mechanical, photocopy, recording, or any other except for brief quotations in printed reviews, without the prior permission of the Primer on Memory Consistency and Cache CoherenceDaniel J. Sorin, Mark D. Hill, and David A. : 9781608455645 paperbackISBN: 9781608455652 ebookDOI: Publication in the Morgan & Claypool Publishers seriesSYNTHESIS LECTURES ON COMPUTER ARCHITECTURE #16 Lecture #16 Series Editor: Mark D. Hill, University of WisconsinSeries ISSNISSN 1935-3235printISSN 1935-3243electronicA Primer on Memory Consistency and Cache CoherenceDaniel J. Sorin, Mark D.

6 Hill, and David A. WoodSYNTHESIS LECTURES ON COMPUTER ARCHITECTURE #16 ABSTRACTMany modern computer systems and most multicore chips (chip multiprocessors) support shared Memory in hardware. In a shared Memory system, each of the processor cores may read and write to a single shared address space. For a shared Memory machine, the Memory Consistency model defines the architecturally visible behavior of its Memory system. Consistency definitions provide rules about loads and stores (or Memory reads and writes) and how they act upon Memory . As part of supporting a Memory Consistency model, many machines also provide Cache Coherence proto-cols that ensure that multiple cached copies of data are kept up-to-date. The goal of this Primer is to provide readers with a basic understanding of Consistency and Coherence . This understanding includes both the issues that must be solved as well as a variety of solutions.

7 We present both high-level concepts as well as specific, concrete examples from real-world architecture, Memory Consistency , Cache Coherence , shared Memory , Memory systems, multicore processor, multiprocessorviiThis Primer is intended for readers who have encountered Memory Consistency and Cache coher-ence informally, but now want to understand what they entail in more detail. This audience includes computing industry professionals as well as junior graduate expect our readers to be familiar with the basics of computer architecture. Remembering the details of Tomasulo s algorithm or similar details is unnecessary, but we do expect readers to understand issues like architectural state, dynamic instruction scheduling (out-of-order execution), and how caches are used to reduce average latencies to access storage structures. The primary goal of this Primer is to provide readers with a basic understanding of consis-tency and Coherence .

8 This understanding includes both the issues that must be solved as well as a variety of solutions. We present both high-level concepts as well as specific, concrete examples from real-world systems. A secondary goal of this Primer is to make readers aware of just how complicated Consistency and Coherence are. If readers simply discover what it is that they do not know without actually learning it that discovery is still a substantial benefit. Furthermore, because these topics are so vast and so complicated, it is beyond the scope of this Primer to cover them exhaustively. It is not a goal of this Primer to cover all topics in depth, but rather to cover the basics and apprise the readers of what topics they may wish to pursue in more owe many thanks for the help and support we have received during the development of this Primer . We thank blake Hechtman for implementing and testing (and debugging!)

9 All of the Coherence protocols in this Primer . As the reader will soon discover, Coherence protocols are com-plicated, and we would not have trusted any protocol that we had not tested, so blake s work was tremendously valuable. blake implemented and tested all of these protocols using the Wisconsin GEMS simulation infrastructure [ ].For reviewing early drafts of this Primer and for helpful discussions regarding various topics within the Primer , we gratefully thank Trey Cain and Milo Martin. For providing additional feed-back on the Primer , we thank Newsha Ardalani, Arkaprava Basu, Brad Beckmann, Bob Cypher, Joe Devietti, Sandip Govind Dhoot, Alex Edelsburg, Jayneel Gandhi, Dan Gibson, Marisabel Gue-vara, Gagan Gupta, blake Hechtman, Derek Hower, Zachary Marzec, Hiran Mayukh, Ralph Na-than, Marc Orr, Vijay Sathish, Abhirami Senthilkumaran, Simha Sethumadhavan, Venkatanathan Prefaceviii A Primer ON Memory Consistency AND Cache COHERENCEV aradarajan, Derek Williams, and Meng Zhang.

10 While our reviewers provided great feedback, they may or may not agree with all of the final contents of this work is supported in part by the National Science Foundation (CNS-0551401, CNS-0720565, CCF-0916725, CCF-0444516, and CCF-0811290), Sandia/DOE (#MSN123960/DOE890426), Semiconductor Research Corporation (contract 2009-HJ-1881), and the University of Wisconsin (Kellett Award to Hill). The views expressed herein are not necessarily those of the NSF, Sandia, DOE, or thanks Deborah, Jason, and Julie for their love and for putting up with him taking the time to work on another synthesis lecture. Dan thanks his Uncle Sol for helping inspire him to be an engineer in the first place. Lastly, Dan dedicates this book to the Memory of Rusty Sneiderman, a treasured friend of thirty years who will be dearly missed by everyone who was lucky enough to have known wishes to thank Sue, Nicole, and Gregory for their love and thanks his coauthors for putting up with his deadline-challenged work style, his par-ents Roger and Ann Wood for inspiring him to be a second-generation Computer Sciences profes-sor, and Jane, Alex, and Zach for helping him remember what life is all.