DescriptionQ039
Q039DesignArchASIC interview problem
Stably sort records in a local cache-line buffer
TechniquesStable sortSingle-port memoryMulticycle FSM
DifficultyMedium
TopicRTL Design
LanguageSystemVerilog
Requirements4 checkpoints
01
Problem
Load up to 16 key/payload records into one local synchronous storage array, stably sort them by nondecreasing key, and stream the sorted records with backpressure.
Example input and output
Use this case to check your interpretationInput
records in arrival order=[(key2,A),(key1,B),(key2,C),(key1,D)]Output
streamed order=[(1,B),(1,D),(2,A),(2,C)]Explanation
Stable sorting retains B before D and A before C for equal keys while each payload stays attached to its record.
02
Requirements (4)
- Preserve each payload with its key and retain arrival order among equal keys.
- Use a single read-or-write memory operation per cycle and honor one-cycle read latency.
- Handle one record, duplicate keys, sorted input, and reverse-sorted input.
- Hold the output record and out_last stable until accepted, and finish within a bounded number of internal cycles.