@sanchuah That blue box is an example of false sharing.
Zarathustra
@sanchuah This is an example of artifactual communication (communication that is a result of our communication protocol) as opposed to inherent (or intrinsic) sharing, which refers to the inability to do computation without all of the data (the two dots on both sides of the line). In this case we are assuming that P1 can do all the work it needs to do by working only with its data set (the left side of the line) and P2 can do all the work it needs to do by working with just the data on the right. But, we might have a cache line that contains all four dots (two on either side of the line). This will result in artifactual communication in an invalidation-based cache coherence scheme, because P1 will load data and do some work, and, if it needs to WRITE to this location, it must "own" that cache line. That means we need to tell P2 that the data on its side of the line is invalid because we are writing to that cache line (the data is stale because of P1's write). But, this is FALSE sharing, because P2 is only using a portion of the cache line that the writes by P1 will never touch. So, even though we didn't need to invalidate the cache line and force communication (algorithmically, or intrinsically speaking), our cache coherency protocol requires it, so we have to do it anyway.
afzhang
Inherent communication: communication built-in to the problem; there's nothing you can really do about this as it's just part of the problem statement. (Although you can sometimes switch algorithms to one with less inherent communication!)
Artifactual communication: communication that occurs due to the way real machines are implemented. Example: having to load a cache line worth of bytes even if you're only interested in reading 4 bytes of stuff.
False sharing: In the example above, P1 doesn't care about the half of the blue box on P2's side of the work and vice versa. However, when P1 writes to its portion of the cache line it needs to claim ownership of the cache line. Similar for P2. As a result, the cache line will ping pong in ownership between P1 and P2 (causing a lot of extra communication overhead) even though there's no need for the cache line to stay up to date between the 2 processors. This is entirely due to artifactual communication.
ekr
@Zarathustra You're conflating false sharing with artifactual communication, when the two are separate concepts. This slide is an example of false sharing, where the two processors are invalidating each other's cache lines even though the data hasn't been invalidated, because the cache line straddles the data boundary. There is no communication going on at all.
Artifactual communication would be if P1 needs to send the first two elements in its local data to P2. Because the cache line size is 4 elements, it needs to send two more elements than are actually going to be used by P2.
jazzbass
@ekr I think that @Zarathustra is right. False sharing is a form of artifactual communication, since it involves a communication overhead of cache invalidation that generates cache misses.
Oops! I was under the impression that artificial communication only refers to actual communication between two processors. Good catch.
Zarathustra
To be completely clear: there IS (indirect) communication between the processors in the invalidation based cache coherence scheme. At least, there are messages being passed on the interconnect to cache controllers as a result of two processors editing this line repeatedly.
Curious about what this slide want to talk about?
@sanchuah That blue box is an example of false sharing.
@sanchuah This is an example of artifactual communication (communication that is a result of our communication protocol) as opposed to inherent (or intrinsic) sharing, which refers to the inability to do computation without all of the data (the two dots on both sides of the line). In this case we are assuming that P1 can do all the work it needs to do by working only with its data set (the left side of the line) and P2 can do all the work it needs to do by working with just the data on the right. But, we might have a cache line that contains all four dots (two on either side of the line). This will result in artifactual communication in an invalidation-based cache coherence scheme, because P1 will load data and do some work, and, if it needs to WRITE to this location, it must "own" that cache line. That means we need to tell P2 that the data on its side of the line is invalid because we are writing to that cache line (the data is stale because of P1's write). But, this is FALSE sharing, because P2 is only using a portion of the cache line that the writes by P1 will never touch. So, even though we didn't need to invalidate the cache line and force communication (algorithmically, or intrinsically speaking), our cache coherency protocol requires it, so we have to do it anyway.
Inherent communication: communication built-in to the problem; there's nothing you can really do about this as it's just part of the problem statement. (Although you can sometimes switch algorithms to one with less inherent communication!)
Artifactual communication: communication that occurs due to the way real machines are implemented. Example: having to load a cache line worth of bytes even if you're only interested in reading 4 bytes of stuff.
False sharing: In the example above, P1 doesn't care about the half of the blue box on P2's side of the work and vice versa. However, when P1 writes to its portion of the cache line it needs to claim ownership of the cache line. Similar for P2. As a result, the cache line will ping pong in ownership between P1 and P2 (causing a lot of extra communication overhead) even though there's no need for the cache line to stay up to date between the 2 processors. This is entirely due to artifactual communication.
@Zarathustra You're conflating false sharing with artifactual communication, when the two are separate concepts. This slide is an example of false sharing, where the two processors are invalidating each other's cache lines even though the data hasn't been invalidated, because the cache line straddles the data boundary. There is no communication going on at all.
Artifactual communication would be if P1 needs to send the first two elements in its local data to P2. Because the cache line size is 4 elements, it needs to send two more elements than are actually going to be used by P2.
@ekr I think that @Zarathustra is right. False sharing is a form of artifactual communication, since it involves a communication overhead of cache invalidation that generates cache misses.
See: lecture 10, slide 35
Oops! I was under the impression that artificial communication only refers to actual communication between two processors. Good catch.
To be completely clear: there IS (indirect) communication between the processors in the invalidation based cache coherence scheme. At least, there are messages being passed on the interconnect to cache controllers as a result of two processors editing this line repeatedly.