3 ms·

Very cool. I have been wondering about using high-level languages to program FPGAs recently. Also, I hadn’t heard of cuckoo hashing before, it sounds neat. I b

Very cool. I have been wondering about using high-level languages to program FPGAs recently. Also, I hadn’t heard of cuckoo hashing before, it sounds neat. I briefly looked at the Wikipedia page about cuckoo hashing that the OP linked to, but didn’t find an answer, so I’ll ask this here: What happens when the load factor of a set of tables gets “too high”, can you just create a new table and prepend it to the list of tables and call it a day, or do you still need to rehash the existing tables?

pjc50 3y ago
> I have been wondering about using high-level languages to program FPGAs recently. In general this is a bad idea. It's a very tempting idea, but it leans heavily on "sufficiently smart compiler" that's inevitably not that smart and also not well supported since it's one guy's research project. Even the vendor supported ones aren't that great. You'd be better off with a higher-level or more modern HDL that compiles to Verilog/VHDL. "Chisel" is one such. The need to control state vs time and manage pipelining makes most higher level software languages unhelpful when trying to get efficient FPGA performance. Not only that, higher level software languages tend to encourage recursion, which maps really badly to FPGA architecture.
- adam_walker 3y ago
  > You'd be better off with a higher-level or more modern HDL that compiles to Verilog/VHDL. "Chisel" is one such. As is Clash, the language this project was written in :) https://clash-lang.org/ https://clash-lang.org/
j-pb 3y ago
This paper is a great intro to cuckoo hash tables: http://www.ru.is/faculty/ulfar/CuckooHash.pdf http://www.ru.is/faculty/ulfar/CuckooHash.pdf Since you have multiple hash functions in use at the same time you can simply increase the number of hash functions when you grow a table to include ones that also cover the new table space. You can then lazily hash keys with the new functions whenever they are cuckooed out of the current position, and perform lookup with all of them. If you keep track of how many elements are using each function, you can then start deprecating the old ones once all of their keys have been hashed with the new range.

pjc50 3y ago

> I have been wondering about using high-level languages to program FPGAs recently. In general this is a bad idea. It's a very tempting idea, but it leans heavily on "sufficiently smart compiler" that's inevitably not that smart and also not well supported since it's one guy's research project. Even the vendor supported ones aren't that great. You'd be better off with a higher-level or more modern HDL that compiles to Verilog/VHDL. "Chisel" is one such. The need to control state vs time and manage pipelining makes most higher level software languages unhelpful when trying to get efficient FPGA performance. Not only that, higher level software languages tend to encourage recursion, which maps really badly to FPGA architecture.

adam_walker 3y ago
> You'd be better off with a higher-level or more modern HDL that compiles to Verilog/VHDL. "Chisel" is one such. As is Clash, the language this project was written in :) https://clash-lang.org/ https://clash-lang.org/

j-pb 3y ago

This paper is a great intro to cuckoo hash tables: http://www.ru.is/faculty/ulfar/CuckooHash.pdf http://www.ru.is/faculty/ulfar/CuckooHash.pdf Since you have multiple hash functions in use at the same time you can simply increase the number of hash functions when you grow a table to include ones that also cover the new table space. You can then lazily hash keys with the new functions whenever they are cuckooed out of the current position, and perform lookup with all of them. If you keep track of how many elements are using each function, you can then start deprecating the old ones once all of their keys have been hashed with the new range.