DescriptionQ397
Q397ArchGoogleASIC interview problem
Check coherent transactions under reordering
TechniquesArchCache coherenceScoreboardInterconnect
DifficultyHard
TopicComputer Architecture
LanguagePython
Requirements4 checkpoints
01
Problem
Two masters access two cache lines. Accepted operations to each line serialize in acceptance order; responses for different lines may reorder. Design an executable reference model that checks retry handling, snoop acknowledgements, coherent data, completion uniqueness, and end-of-test drainage.
Starting declarationPython
request: master, id, op, line, data
snoop: target, line, invalidate, ack
response: master, id, status, data
IDs unique while outstanding; retry means not accepted; reset line value=0Example input and output
Use this case to check your interpretationInput
M0 and M1 share line L; M0's write is accepted, but completion arrives before M1's invalidate acknowledgementOutput
AssertionError naming missing acknowledgement from master 1Explanation
The write cannot become the coherent line owner or update expected data until every other current sharer acknowledges invalidation.
02
Requirements (4)
- Track only accepted requests by ID and update no state for a retry; the same ID may later be accepted.
- Maintain owner, sharers, and data per line; reads observe serialized line state and writes commit only after all required invalidation acknowledgements.
- Permit response reordering across lines but require acceptance order within each line and exactly one completion per accepted ID.
- Detect unknown or duplicate completion, stale read data, missing snoop acknowledgement, and nonempty outstanding state at test end.