Topic: Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo - page 6. (Read 7214 times)

I wish you good luck! in general, yes, it is convenient that after passing a certain period of values, the program completes its work.

In this case, the program stores dp in RAM and you don't have enough for your entire range. if you add the completion of the process by iterating over a certain area (which RAM allows), you can exclude it in further searches.

If by pure chance Puzzle 135 is in the range I chose, it will end with the foundkey, otherwise it will end with nothing found

so that the program ends after a complete search.

  Speed: 2310 MKeys/s - 3070
Well done! Can I ask you a question about kangaroos? in private messages.

NVIDIA GeForce RTX 3060, 11.76 GB, 28 CUs, cap 8.6, PCI 40, L2 size: 2304 KB
Speed: 1.5 GKeys/s

NVIDIA GeForce GTX 1660 SUPER, 5.80 GB, 22 CUs, cap 7.5, PCI 39, L2 size: 1536 KB
Speed: 1.1 GKeys/s

2x GTX 1660 SUPER + 1x RTX 3060 (-gpu "012")
Speed: 3.7 GKeys/s

22m to solve key 85bit 

Thanks man! 

I request that CPU support be added. We are doing some studies and research, using only GPU is not enough. Sometimes we need to use only CPU. Please add CPU support.

Thank you so much for your incredible contribution to this tool!

I believe it’s already fantastic, but there’s just one feature that could make it truly perfect: the addition of an --end parameter.

Here’s an example to illustrate what I mean:

Puzzle 135: 40000000000000000000000000000000000000:7fffffffffffffffffffffffffffffff

I’d like to try my luck and search within a specific range, such as:
--start 52000000000000000000000000000000000000
--end 5affffffffffffffffffffffffffffff

The inclusion of an --end parameter would be a game-changer for scenarios like this.

Thanks in advance for your consideration

NVIDIA GeForce GTX 1660 Ti "Laptop" 975 MKeys/s

Thanks!
1660Super 930-948Mkey/s

v2.0 (Windows/Linux):
https://github.com/RetiredC/RCKangaroo

- added support for 30xx, 20xx and 1xxx cards.
- some minor changes.

Speed:
4090 - 7.9GKeys/s.
3090 - 4.1GKeys/s.
2080Ti - 2.9GKeys/s.

Please report speed for other cards, for old cards speedup is up to 40%.

If X1, Y1, X2, Y2, Z, and the jump distance are all in registers, you get maximum speed. You can never get faster than that. But you can only do it with a very small number of kangaroos, like up to 6 or 7 kangaroos, depending on how well you use the registers.

Next wall is when L1 + shared memory gets used. This is the next maximum possible speed, but lower speed per kangaroo then above. You can add maybe 1 kangaroo more this way, because this cache is really small (128 KB per SM).

Third wall is using L2 cache. So, much lower speed / kangaroo, even though the overall throughput is greater. This scales up better only if L2 is really big.

This is why: when L2 cache is small, then loading and storing X1 Y1 in/out of L2 before and after each jump is much too slow, because they will actually pass into deice global memory. So, if L2 is small, the only logical (and faster) option is to only load and store X1 Y1 before all the jumps, and store them back after all the jumps.

Adding cycle handling in this case reduces the number of allowed X1 Y1 = less kangaroos = lower speed.

I have like seven different kernel versions that test these different strategies for when and how data is being loaded into/to different memory levels, so I'm pretty sure about the differences in each strategy.

You are wrong, it's not related to L2, loop handling slowdown for new and old cards is similar. But I won't argue.
I will release new version with 20-35% speedup for old cards soon. Not much optimized, but anyway faster than now.

The comparison between SOTA and 3-kangaroo you made is only relevant if the jumping device (RTX 4090 in your case) allows the tradeoffs you mention, in order for the tradeoffs to end up with a more efficient solver.

Let me give you an example.

RTX 3050 or other cards that have a low amount of L2 memory.

Your RCKangaroo is much slower than a non-cycling jumper, like 50% slower, because the overhead of handling the cycles is clearly visible (no L2 memory to hide computing bounds). It is even worse when the kangaroos are stored in global memory (since L2 is too small to cache them).

So the winner in these cases is a normal (optimized) 3-kangaroo algorithm.

But because RTX 4090 has around 75 MB of L2 cache, the lower speed is hidden because it is offset by the fast L2 cache. In other words, the raw speed becomes irrelevant, because now the speed bound is limited by the memory latency of L2, not by the raw computing cores.

In this case you can do pretty much whatever you want in the kernel and go crazy with whatever algorithm you want to use, like your SOTA method. Because it won't affect the speed too much.

What I want to say is: in the future you can't really know if new GPUs will have the same tradeoff benefit, so there is no guarantee that the computing size of a CUDA device won't have a greater influence on speed when compared to the cache latency and size of L2 memory.

1. Maybe.
2. No, it's bad idea.


Yes, 10G for 4090 is ok.
And then one day you will understand that the only way to improve it further - use symmetry and get sqrt(2) boost. Yes you will lose some speed but total improvement worth it.
From RCKangaroo readme:

Fastest ECDLP solvers will always use SOTA method, as it's 1.39 times faster and requires less memory for DPs compared to the best 3-way kangaroos with K=1.6. Even if you already have a faster implementation of kangaroo jumps, incorporating SOTA method will improve it further. While adding the necessary loop-handling code will cause you to lose about 5–15% of your current speed, the SOTA method itself will provide a 39% performance increase. Overall, this translates to roughly a 25% net improvement, which should not be ignored if your goal is to build a truly fast solver.

I must admit you used some really clever tricks to make maximum usage of shared memory (L1) and L2 caches. I'm still trying to figure out the way you keep track of the jump distances using the shared memory instead of updating them using L2.

After adapting my own kernel to load/store stuff using L2 (instead of only once, before and after all the jumps) I reached 9.7 GK/s on RTX 4090 (64 jump points, DP 32), which was an increase of 75% in speed, and I haven't even tried to do micro-optimizations on it, like before. So I guess this was the missing lack of knowledge to be able go beyond the advertised 8+ GK/s stated by others around here, after trying every possible advanced optimizations I could think of to speed things up.

So did you start work on solving 135?

Hi! pretty cool tool :-)
Do you plan to implement if possible to have
 - a "continue" option in case the gpu stop and you want to continue from where is stopped ?
 - a "multiple pubkey" option like an input file with a list of pubkey ?

thanks and have a good one

Yes, new version will support these cards and will be faster by at least 20-30% for these cards.

It would actually be great if 20xx GPUs could be supported!  And if in addition a speed optimization for these 20xx and 30xx series is made great . Thank you  

I'm not going to create serious ready-to-use open-source solution for cracking really high ranges. You should do it by yourself if you want to crack #135 and get a lot of money
But I'm going to update RCKangaroo to support old cards better (+higher speed) when I have time.

@RetiredCoder Maybe you can share networking and dp load/save options. Do you have any plan on it?