FIFO Queues in Hardware
First-in-first-out buffers: the fundamental building block for pipelining, buffering, and order matching.
Problem
How does hardware store a sequence of items and retrieve them in the same order? FIFOs appear everywhere: between pipeline stages, at bus interfaces, in network switches, and in order book matching engines.
How it works
Circular buffer: the most common FIFO implementation uses a fixed-size memory array with two pointers:
• Write pointer (tail): points to the next empty slot. Advances on enqueue.
• Read pointer (head): points to the oldest item. Advances on dequeue.
• Both pointers wrap around when they reach the end of the array.
Full/empty detection: the tricky part. If head = tail, is the FIFO empty or full? Common solutions:
• Extra bit: use (N+1)-bit pointers for an N-slot FIFO. Full when pointers match in low bits but differ in the extra bit. Empty when pointers are exactly equal.
• Counter: track the number of occupied slots separately.
• Waste a slot: never fill the last slot; full = (tail+1) mod size == head.
Synchronous vs asynchronous: when the producer and consumer run on different clocks (e.g., crossing clock domains), an async FIFO uses Gray code pointers so only one bit transitions per cycle, making single-bit synchronization manageable via multi-stage synchronizers. This is one of the most important and subtle structures in digital design.
Depth sizing: FIFO depth is chosen to absorb burst traffic without overflow. Too shallow = data loss under burst. Too deep = wasted area.
• Write pointer (tail): points to the next empty slot. Advances on enqueue.
• Read pointer (head): points to the oldest item. Advances on dequeue.
• Both pointers wrap around when they reach the end of the array.
Full/empty detection: the tricky part. If head = tail, is the FIFO empty or full? Common solutions:
• Extra bit: use (N+1)-bit pointers for an N-slot FIFO. Full when pointers match in low bits but differ in the extra bit. Empty when pointers are exactly equal.
• Counter: track the number of occupied slots separately.
• Waste a slot: never fill the last slot; full = (tail+1) mod size == head.
Synchronous vs asynchronous: when the producer and consumer run on different clocks (e.g., crossing clock domains), an async FIFO uses Gray code pointers so only one bit transitions per cycle, making single-bit synchronization manageable via multi-stage synchronizers. This is one of the most important and subtle structures in digital design.
Depth sizing: FIFO depth is chosen to absorb burst traffic without overflow. Too shallow = data loss under burst. Too deep = wasted area.
Key insightA FIFO decouples a producer from a consumer: they don’t need to run at the same rate or even the same clock. In order book engines, each price level’s order queue is a FIFO: first order in is the first to be matched (price-time priority).