1/1/2024 0 Comments Memory barrier cache coherence![]() Sequential consistency: an intuitive model of parallelismĪrchitects and programming language designers believe the rules we just explored to be intuitive to programmers. But those rules lead to a contradiction (event (1) happening before itself). Then all the ordering rules we just showed must hold. Think of it as a proof by contradiction: suppose this program could print 00. Since this execution would require time-warping, we can conclude that this program can’t print 00. So if we start at (1), and end up back at (1) again, the graph is saying that (1) must happen before itself! Barring a very concerning advance in physics, this is unlikely to be possible. If we start at (1), and follow the edges-to (2), then (3), then (4), then… (1) again! Remember that the edges are saying which events must happen before other events. So let’s add those edges too:īut now we have a problem. Similarly, for line (4) to print 0, that print must happen before line (1) writes a 1 to A, so let’s add that to the graph:Īnd finally, of course, each thread’s events should happen in order-(1) before (2), and (3) before (4)-because that’s what we expect from an imperative program. We can represent this graphically with an edge:Īn edge from operation x to operation y says that x must happen before y to get the behavior we’re interested in. For line (2) to print 0, we have to print B before line (3) writes a 1 to it. Intuitively, it shouldn’t be possible for this program to print 00. ![]() and a few others that have the same effect.(1) → (3) → (4) → (2): The first instruction from the first thread runs, then both instructions from the second thread, then the second instruction from the first thread.(1) → (3) → (2) → (4): The first instruction in each thread runs before the second instruction in either thread, printing 11.There are also some less obvious orders, where the instructions are interleaved with each other: (3) → (4) → (1) → (2): The second thread runs both its events before the first thread.(1) → (2) → (3) → (4): The first thread runs both its events before the second thread, and so the program prints 01.Intuitively, there are two obvious orders in which this program could run: We should think about the order in which its events can happen. To understand what this program can output, How multiple threads (or workers, or nodes, or replicas, etc.) ![]() There are many resources on memory consistency,Īnd motivate why memory consistency is an issue for multicore systems.įor the details, you should certainly consult these other excellent sources. Which is the problem of defining how parallel threads Seeing things in order is a challenge for the ages. Lurking amongst the tall weeds of computer science: Only two hard things in computer science:Ĭache invalidation, naming things, and off-by-one errors. The cause of, and solution to, all your multicore performance problems. Memory Consistency Models: A Tutorial 17 February 2016 If anyone is aware of a case where the hierarchical thread cache model makes a prediction different from the reordering-based model, I would love to hear about it. I think that you would have to construct a somewhat of a clever case in order for the cache hierarchy to make a difference, though. To be even more accurate, you should assume that the thread caches can form an arbitrary large hierarchy, and so you cannot assume that a read is served only from two possible places – main memory or the thread’s cache. The thread cache model is also accurate for most intents and purposes. I find the explanation based on imaginary thread caches more intuitive than the more commonly used explanation based on operation reordering. NET memory model, and is based purely on publicly available information. This blog post reflects my personal understanding of the. Is the entire imaginary thread cache flushed to main memory after the operation?. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |