Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- > Is it known whether Momentum and/or Cuckoo are memory-hard? I don't think
- > either are.
- As author of Cuckoo Cycle, let me address your concerns.
- > Both claim to be "memory-hard".
- The Cuckoo Cycle project page at https://github.com/tromp/cuckoo in fact lists a
- "Linear Time-Memory Trade-Off Bounty
- $500 for an open source implementation that uses at most N/k bits
- while running up to 15 k times slower, for any k>=2.
- Both of these bounties require N ranging over {2^28,2^30,2^32} and
- #threads ranging over {1,2,4,8}, and further assume a high-end Intel
- Core i7 or Xeon and recent gcc compiler with regular flags as in my
- Makefile."
- The whitepaper at
- https://github.com/tromp/cuckoo/blob/master/cuckoo.pdf?raw=true
- devotes a Section to Time-Memory Trade-Offs (TMTOs) that further
- details the memory hardness claims.
- Which you seem to conveniently ignore in your own notion of memory-hardness :-(
- Instead, what you're talking about is covered in the later Section
- "Parallelization",
- which show the gains achievable by using multiple threads.
- The algorithm you outline is also detailed in the earlier Section
- "Cuckoo Cyle basic algorithm"
- and is in fact what motivates the its name.
- It's almost as if you've gone out of your way to avoid reading the whitepaper:-)
- > Cuckoo Cycle also claims to be memory-hard, but I don't buy it. They're
- > looking for cycles of length L by building a forest of trees, and detecting
- > when loops form, and measuring the length. If we do a parallel sort as
- > above, we can store entries in a Cuckoo hash table
- > <https://en.wikipedia.org/wiki/Cuckoo_hashing> rapidly in parallel.
- You don't need parallel sort for that; the parallel version of the
- basic algorithm
- already does it. But note that:
- 1) it uses 32 times more memory than the Cuckoo Cycle reference algorithm
- 2) the parallel memory accesses are going to form a latency bottleneck when
- the number of threads runs into the hundreds.
- regards,
- -John
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement