Tiny Cuckoo Core
Fast, hardware accelerated dictionary lookups.
The Tiny Cuckoo Core is an implementation of Cuckoo Hashing. It is a data structure of key-value pairs that allows for fast lookup and retrieval of entries based on the key. Cuckoo Hashing guarantees a fixed lookup latency at the cost of a more complex insertion/update procedure.
Tiny Cuckoo Core implements the lookup in logic but saves on logic resources by deferring the update to software. This is ideal for use cases where frequent lookups need to be performed in the logic but updates to the table are infrequent or initiated by a driver in the first place. An implementation of the software counterpart in C is bundled with the IP-core.
Feel free to download and evaluate the core. Contact us if you have questions or want to license it.
At a glance
| Key size | Configurable |
| Value size | Configurable |
| Maximal capacity | Configurable |
| Throughput | One lookup per clock cycle at a fixed latency of two clock cycles. |
| Hash function | Tabulation Hashing |
| Hash table | Cuckoo Hashing with configurable number of tables |
| Storage | On-chip (Block RAM) |
| Input/Output | Avalon Streams with fixed 2-cycle latency |
| Configuration/Update | 32-bit Avalon Memory Mapped interface (software counterpart in C for driver included) |
| Price for evaluation and non-commercial use | Free |
| Price for commercial use | 5000 € |
Features
Dynamically seeded hash function
The hash function is dynamically seeded by the software counterpart making it very hard for an attacker to degrade performance by forcing hash collisions. This allows Tiny Cuckoo Core to be used in exposed locations such as in caches that are referenced for incoming network traffic.
Fixed Latency
The IP-core uses on chip block ram for storage. This in combination with the properties of Cuckoo Hashing allows for a lookup to be performed with a fixed latency. All requests are handled in order with a fixed 2-cycle latency. The throughput is one request per cycle.
Easy Integration
The IP-core uses a single clock and has no special requirements wrt. resets. Input and output is handled through regular Avalon streams.
The provided implementation of the software counterpart to the MM control interface is very easy to integrate into existing drivers. To ensure the code can fulfill any kernel space requirements it is written in pure C. It doesn’t introduce any new dependencies and uses user-supplied callbacks for heap allocations, memory access, etc.
Full Flexibility
The IP-Core is shipped as a generator that allows configuration of all relevant aspects. This allows to adjust the core to your specific needs and, if need be, readjust it if requirements change during the development. The generator exports regular VHDL 2008 code that can be used in common tool chains.
Extensive Documentation
The product is bundled with detailed documentation explaining the involved algorithms, the available configuration parameters and their tradeoffs, as well as how to use the generator. For the specific configuration chosen, the generator also performs tests with an internal cycle-exact simulator that runs the driver and logic in a closed loop to verify design correctness. A specific interface documentation for the chosen configuration is also generated that shows and describes the exact functional blocks, associated signals, waveforms, and MM registers.
