nkanderson
commented
2 weeks ago What you've laid out in the PDF seems good, makes sense to me, anyways.
I think regarding the Python implementation, in my opinion, we are going to want at least one structure with access via named keys (dictionary or instances of a class we create), for the individual entries / cache lines.
Within each set, I'm not sure I see a benefit to a dictionary over a list, since we need to check each item for our matching tag bits either way. ~I don't think we could have a dictionary keyed by the tag bits only without risking collisions.~ I think we could use a dictionary and key by tag, which could make sense for quickly retrieving or removing an entry. Since it's only 16 items in each set, going for a binary search tree or something seems like it might be overkill (though hard to say given the scale we'll be operating on in terms of number of transactions). I think this might depend on how our PLRU is implemented. Maybe something like a priority queue with the PLRU bits to have quick access to eviction, and linear search for the matching tag?
For the sets, I was initially thinking a dictionary, since Mark led us down the path of hashmaps. But @mdhardenburgh got a good clarification there, that he didn't necessarily intend to send us in that direction, I think it was mainly a part of his analogy. I think we could have a list at that level as well, since each index could just be used directly as the index for the list item. If we did a dictionary at that level instead, it could just be keyed by the index - I'm not sure I see any major pros or cons to either option. Might need to dig deeper into the underlying Python implementation if we want to differentiate on things like overall memory usage or speed.
So I guess to provide a visual, this is a very simplified version of what I was thinking:
# Each cache line could be a dictionary or instance of a class we create, with fields we can access by name
cache_line_0 = { "tag": 0b<add the tag bits here>, "data": None, "MESI": 0b00, "valid": 0, "dirty": 0 }
# main cache data structure is a list, where each index points to a list of all the ways in the set
cache = []
# example index 256 is another list representing the ways in the set
# I think this could instead be a dictionary keyed by tag as an alternative
cache[0b100000000] = [cache_line_0, cache_line_1,...,cache_line_15];
# retrieve a cache line:
for way in cache[0b100000000]:
if way["tag"] == target_tag:
cache_hit(way) # do something with the cache line
else:
cache_miss() # handle the missI'm curious to know what @mdhardenburgh and @reecewayt had in mind though, and if you've generated any more ideas after looking at Python data structures more @d-engler.
d-engler
reecewayt
Here is a draft sketch of the data structure. This is just the sketch, not the code. I think this might change once we know more about implementing MESI. That may mean another bit field. As for implementing it, it seems the python way would be nested dictionaries, but I'm gonna do a little python data structures review first.