In sparse directories, are we not just shifting the storage overhead from directories to the cache? We now require only one pointer in the homenode's directory but additional two (next, prev) pointers in the cache line. Am I missing something here?
ChandlerBing
I guess I am just totally confused about this. Can someone tell me how have we reduced M here (as suggested in Slide 25 )? Doesn't the diagram suggest that each cache line entry in directory stores one pointer now?
kayvonf
@ChandlerBing. Yes, I've confused people a bit here. Your interpretation of what's going on is correct given my slide.
However, in practice, an implementation wouldn't allocate storage for a pointer each memory location, it might allocate pointer storage for exactly as many lines as could be in cache and then a mechanism would be needed to quickly search that table, e.g., via a content addressable memory (CAM).
ChandlerBing
@kayvonf Ahh it's clearer now, that makes sense! Thanks!
sgbowen
I'm still confused about this...
If we're allocating pointer storage, why not just allocate "entry" storage as earlier?I.e., why can't we allocate space for a limited-pointer scheme or a bit vector? What's the need to chain the pointers in a linked list format? Isn't that more of an optimization in the "P" direction than the "M" direction?
zhanpenf
Does it mean that with the sparse directories optimization, the number of entries in each directory equals to the product of the number of lines in one cache and the number of processors?
jcarchi
So I think what @kayvonf is saying is that the table isn't actually M lines long. It's as long as the number of lines the cache can hold, which is usually much smaller than the size of memory. (sum of cache sizes << size of memory)
And @sgbowen, I agree that the linked list format seems like an optimization in the "P" direction in most cases. However, if the number of processors is less than the number of bits required for a pointer, wouldn't this be wider? Or am i overthinking it?
@zhanpenf yes, i think M = num processors * num cache lines
In sparse directories, are we not just shifting the storage overhead from directories to the cache? We now require only one pointer in the homenode's directory but additional two (next, prev) pointers in the cache line. Am I missing something here?
I guess I am just totally confused about this. Can someone tell me how have we reduced M here (as suggested in Slide 25 )? Doesn't the diagram suggest that each cache line entry in directory stores one pointer now?
@ChandlerBing. Yes, I've confused people a bit here. Your interpretation of what's going on is correct given my slide.
However, in practice, an implementation wouldn't allocate storage for a pointer each memory location, it might allocate pointer storage for exactly as many lines as could be in cache and then a mechanism would be needed to quickly search that table, e.g., via a content addressable memory (CAM).
@kayvonf Ahh it's clearer now, that makes sense! Thanks!
I'm still confused about this...
If we're allocating pointer storage, why not just allocate "entry" storage as earlier?I.e., why can't we allocate space for a limited-pointer scheme or a bit vector? What's the need to chain the pointers in a linked list format? Isn't that more of an optimization in the "P" direction than the "M" direction?
Does it mean that with the sparse directories optimization, the number of entries in each directory equals to the product of the number of lines in one cache and the number of processors?
So I think what @kayvonf is saying is that the table isn't actually M lines long. It's as long as the number of lines the cache can hold, which is usually much smaller than the size of memory. (sum of cache sizes << size of memory)
And @sgbowen, I agree that the linked list format seems like an optimization in the "P" direction in most cases. However, if the number of processors is less than the number of bits required for a pointer, wouldn't this be wider? Or am i overthinking it?
@zhanpenf yes, i think M = num processors * num cache lines
If anyone is interested, this paper discusses various space saving directory schemes including the one above. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.6826&rep=rep1&type=pdf