3 ms·
"MapGraph is up to two orders of magnitude faster than parallel CPU implementations on up 24 CPU cores and has performance comparable to a state-of-the-art manu
by tromp 12y ago
"MapGraph is up to two orders of magnitude faster than parallel CPU implementations on up 24 CPU cores and has performance comparable to a state-of-the-art manually optimized GPU implementation."
That doesn't bode well for my $1000 GPU Speed Parity Bounty
at
https://github.com/tromp/cuckoo https://github.com/tromp/cuckoo
based on my belief that the Cuckoo Cycle graph-theoretic proof-of-work algorithm is more suited to CPUs.
- Bakkot 12y agoI don't know. This is admittedly not something I know much about, but from poking around a bit, it looks like the Gather-Apply-Scatter model - or any other vertex-centric model - is not well suited to finding cycles of specific length. Compare eg GraphChi's triangle-counting code [1], which specifically notes the difficulties arising from having to maintain and work with large adjacency lists. I don't see a way around that for vertex-centric models. That said, I haven't actually read your miner, so I don't know what it's doing or if something similar can be done for GAS-based frameworks. If someone who knows more wants to chime in, I'd be delighted to read more about this. [1] https://github.com/GraphChi/graphchi-cpp/blob/master/example_apps/trianglecounting.cpp https://github.com/GraphChi/graphchi-cpp/blob/master/example...
- tromp 12y agoMost time in the miner is spent identifying which edges have an endpoint of degree 1, and thus cannot be part of any cycle. This degree counting sounds like it should be right up the Gather-Apply-Scatter alley...