DescriptionQ161
Q161ArchASIC interview problem
Look up time-indexed register history
TechniquesTimestampUpper boundLocal memoryBackpressure
DifficultyMedium
TopicMemory Systems
LanguageSystemVerilog
Requirements5 checkpoints
01
Problem
Store timestamped values for four register keys and answer queries with the value whose stored timestamp is the greatest one less than or equal to the requested time.
Example input and output
Use this case to check your interpretationInput
write key=2 (t=10,A), then (t=20,B); query key=2 at t=5,10,17,20Output
MISS, A, A, BExplanation
The backward search returns the newest timestamp less than or equal to the query and treats an exact timestamp as a hit.
02
Requirements (5)
- Support four keys and at most eight writes per key, with strictly increasing timestamps within each key.
- Serialize accepted commands and make every accepted write visible to every later accepted query.
- Return a miss before the first stored timestamp and use inclusive less-than-or-equal behavior for exact matches.
- Model a one-cycle local-memory read rather than comparing an entire history combinationally.
- A query response must remain stable until accepted; writes do not generate responses.