Previous | Next --- Slide 32 of 49
Back to Lecture Thumbnails
apadwekar

The linked list strategy isn't really used as it is more of a software engineering solution to the problem. As mentioned in the slide, this solution is inefficient for writes as invalidation of sharers becomes linear.

axiao

It seems like we are conflating two ideas into one in this slide:

Sparse directories: only store directory entries for lines stored in cache, not the whole main memory.

Linked list: for each directory entry, we use a chain of cache lines to represent which caches have stored the cache line.

There is no reason for these two ideas to be always combined. We could also have a sparse directory + bit vector scheme, or a non-sparse + linked list scheme.

srb

Why is higher implementation complexity an important factor here?

ykt

The implementation of the sparse directory itself might also affect the performance. If you think about a naive implementation then, you will have to traverse the entire sparse directory to check whether there is an entry for the address that you want. Found some relevant discussion here link