DescriptionQ647
Q647ArchASIC interview problem
Validate micro-operation dependencies
TechniquesGraphTopological sortFSMBackpressure
DifficultyMedium
TopicHardware Algorithms
LanguageSystemVerilog
Requirements5 checkpoints
01
Problem
Build a bounded dependency validator for a programmable accelerator. Load directed edges u -> v, where u must issue before v, report whether the graph is acyclic, and emit the legal node order when it is.
Example input and output
Use this case to check your interpretationInput
nodes=4; edges = [0->2, 1->2, 2->3]Output
acyclic=1; emitted order = [0, 1, 2, 3]Explanation
Nodes 0 and 1 are initially eligible, so the lower-index rule emits 0 first; node 2 becomes eligible only after both incoming edges retire.
02
Requirements (5)
- Support 1 to 8 nodes and 0 to 16 nonduplicate directed edges; a self-edge is a cycle.
- Accept the declared edge count before start, and allow a zero-edge graph to start immediately after configuration.
- Always choose the lowest-numbered eligible node and update every affected indegree exactly once.
- Buffer the complete order until acyclicity is known so a cyclic graph emits no order tokens.
- Hold the result and each order token stable under backpressure.