Vulkan compute shaders

[chalsall]

Originally Posted by mrh

With a few optimizations, it can test about 420M factors/second, or about 15 ghz-days/day (I think). Pretty good considering the really slow/simple squaring algorithm.

We welcome the empirical around these here parts.

Do you have more to show? Perspiring minds want to know.

[mrh]

Originally Posted by chalsall

We welcome the empirical around these here parts.

Do you have more to show? Perspiring minds want to know.

It is still a little rough, I only wanted to determine what could and could not be done with a compute shader.

https://github.com/mrh42/vtf

[kriesel]

Originally Posted by mrh

With a few optimizations, it can test about 420M factors/second, or about 15 ghz-days/day (I think). Pretty good considering the really slow/simple squaring algorithm.

420 vs 100 is an admirable jump in performance. 15 GHD/d sounds anomalously low to me for 420M factor candidates/sec.
From a recent RTX2080 Super mfaktc run,

Starting trial factoring M299000123 from 2^79 to 2^80 (409.48 GHz-days)
 k_min =  1010807125666800
 k_max =  2021614251333651
Using GPU kernel "barrett87_mul32_gs"
Date    Time | class   Pct |   time     ETA | GHz-d/day    Sieve     Wait
Apr 26 15:48 |    0   0.1% | 12.420   3h18m |   2967.22    82485    n.a.%
...
Apr 26 19:07 | 4617 100.0% | 12.495   0m00s |   2949.41    82485    n.a.%
no factor for M299000123 from 2^79 to 2^80 [mfaktc 0.21 barrett87_mul32_gs]
tf(): total time spent:  3h 19m  6.270s

Let's suppose that on average that is 2958. GHD/d.
Duration was 11946.27 seconds, or 0.138267 days.
Check mean sustained GHD/d; 409.48/0.138267 = 2961.516 GHD/d, 0.1189% higher than estimated above.
k range = k_max-k_min ~ 1.0108E15.
Per the attachment of https://www.mersenneforum.org/showpo...18&postcount=9
the density of primes in that k range 1E15 to 2E15 is ~2.9%.
Optimistically assuming mfaktc is approximating complete sieving, that would mean it is testing ~2.9E13 k values.
~2.9E13 / 11946.27 seconds ~2.4275E9 candidates/sec ~ 2.097E14 candidates/day;
2961.5GHD/day for RTX2080 super, vs. its 3072. rating at https://www.mersenne.ca/mfaktc.php is close, and explainable variation, since this RTX2080 Super is being operated at lower than nominal input power, and effective GHD/d varies by kernel & perhaps other variables.
I tend to operate Radeon VIIs at reduced power too.
The Radeon vii GPU is rated for TF performance at https://www.mersenne.ca/mfaktc.php as 1114. GHD/d.
That's 1114/3072 = 0.3626 of the RTX 2080 Super throughput.

If the 420M/sec figure is surviving candidates, that's 420E6/2.43E9 / 0.3626 ~ 47.7% of mfaktx's performance after adjusting for GPU TF expected speed ratio.
If the 420M/sec figure is raw k values before even the wheel sieve, it's ~2.9% of 47.7%, or ~1.4%.
Achieving even 1% of state of the art GPU software TF performance is more than nearly all GIMPS participants have coded.

You may be able to increase performance by using more of the concepts listed here.
I see you are already using some, and specifically not using others (Montgomery, Barrett) yet.

It was unclear to me how you run the code on a specific exponent and bit level. The latest commit seems to contain exponent and k values inline in the code.
I think it would make sense to repurpose some mfaktc/o code for implementing ini files, worktodo, checkpoint files, etc at some point.

[mrh]

Ah, I think you are correct. I did quick estimate to complete between vtf and mfakto, and vtf is maybe 20x slower. So maybe 140 ghd/d?

The current checked in code can manage about 420M raw k-values/sec when using 512K threads (on M262359187).

I have studied your TF reference manual quite a bit, thank you! I want to write a SqMod() that uses one of the advanced techniques, but I'm not quite there yet. I understand them in principal, but not enough just yet to actually write the code...

Yes, all the params on the cpu side are just hard coded. I can almost convert from bit-level to k-value in my head now. :)
I might add some of the file interface stuff, but I'm not sure where to go with this. Does the world need another TF variant? Probably not. I did this to learn how the Vulkan stuff works, and learning about how trial factoring works was a bonus. (I wrote the TF code in Go first, so much easier to debug).

At some point I want to understand how PRP works. The only way I know how to learn, is trying to implement it myself. But that seems quite a bit more difficult.

Originally Posted by kriesel

420 vs 100 is an admirable jump in performance. 15 GHD/d sounds anomalously low to me for 420M factor candidates/sec.
...

If the 420M/sec figure is surviving candidates, that's 420E6/2.43E9 / 0.3626 ~ 47.7% of mfaktx's performance after adjusting for GPU TF expected speed ratio.
If the 420M/sec figure is raw k values before even the wheel sieve, it's ~2.9% of 47.7%, or ~1.4%.
Achieving even 1% of state of the art GPU software TF performance is more than nearly all GIMPS participants have coded.

You may be able to increase performance by using more of the concepts listed here.
I see you are already using some, and specifically not using others (Montgomery, Barrett) yet.

It was unclear to me how you run the code on a specific exponent and bit level. The latest commit seems to contain exponent and k values inline in the code.
I think it would make sense to repurpose some mfaktc/o code for implementing ini files, worktodo, checkpoint files, etc at some point.

[mrh]

Originally Posted by mrh

It is still a little rough, I only wanted to determine what could and could not be done with a compute shader.

https://github.com/mrh42/vtf

In case folks are interested, here are some things I did or thought about to make it fast:

- Very minimal data movement between the cpu/gpu. R/W to/from gpu memory is really slow from the cpu. So it writes some tables before the first call, but after that the cpu only looks at a couple uint64_t values per call.

- Try to keep all the gpu "threads" doing useful work. I found my gpu likes a lot. Like 512k threads. So be very mindful of branching, etc. You don't want one edge case going while 1000s are waiting for it to catch up.

- To keep everyone working on something, requires a little memory trade-off. So each thread starts with a range of 200ish K values, and builds an array of 30ish to pass to the next sieve stage. Something like 13 stages of list shortening gave good results. I think this can still be improved, the first stage should be broken up.

- This pre-work is done with 32bit P and 64bit K values, but it still does a number of integer mod operations. So I found using around 200 small primes for the sieve() was a good balance for saving work in the next step.

- For the K values that make it through the sieve, we finally create Q from P*2*K+1, start squaring. This will perform 10*log2(Q) * log2(P) - ish simple operations on a 96bit extended uints. These are fast, but that is a lot of operations, 20K maybe? I'll work on this next.

That last step works well across the threads, but there is still some variation in the length of the lists of k-values to test between threads. So there are some threads waiting around, that could be doing work. I don't know what to do about that, maybe threads within a work group could balance out the work lists. There are some mechanisms for that.

It was certainly an interesting exercise, it took me back to my early days of writing SIMD code in lisp for a Connection Machine in 1990 maybe?

[kriesel]

Originally Posted by mrh

Now, if someone had a fft/ntt based Square-mod function I could use... :)

https://github.com/DTolm/VkFFT may be useful, and offers competitive performance.

Re, who would need or want a Vulkan based TF or PRP package for GIMPS, some scenarios:
1) OpenCL or CUDA driver not working, but Vulkan is
2) performance advantage
3) If it supported >32 bit exponent, TF on 4.3G-10G for mersenne.ca, or even higher exponents in special cases:
https://www.mersenneforum.org/showpo...04&postcount=5
https://www.mersenneforum.org/showpo...45&postcount=4
https://www.mersenneforum.org/showpo...4&postcount=11 Double mersennes on CUDA with mmff, but there's no OpenCL software for double mersennes above MM31.

[mrh]

I made a little bit more progress today. The little shader can now process almost 2.5 billion K-values/second. Maybe 100ghz-d/day? I'll have to do some longer runs to be sure.

Not optimized yet, but it seems to work, best I can tell. This is now using 128/256 bit uints. It has a Modulo function that uses floating point to estimate 128-bit values to subtract leaving an accurate remainder.

https://github.com/mrh42/vtf/blob/main/tf.comp

[mrh]

Another vulkan thing I learned. I can point my program at the Radeon VII vulkan device, or an "llvmpipe" device that runs on my CPU.
The unmodified SPIR-V code ran on my CPU, using 16 cores at about 17M factors/sec. (Xeon Gold 6146) Kinda cool for testing I suppose.

[mrh]

The latest version of the TF compute shader code can process about 3.7 billion potential factors per second at 100W on my Radean VII. About 4.5 billion/sec at 250W. The main update was to use DEVICE_LOCAL memory for some data. No where near mfact* performance, but the code is also very simple.

This might be a useful starting starting point if someone wants to write something else for a GPU but doesn't want to start from scratch.

https://github.com/mrh42/vtf/blob/main/tf.comp

[chalsall]

Originally Posted by mrh

The latest version of the TF compute shader code can process about 3.7 billion potential factors per second at 100W on my Radean VII. About 4.5 billion/sec at 250W. ...

This might be a useful starting point if someone wants to write something else for a GPU but doesn't want to start from scratch.

Thank you for doing this. It takes some confidence to publish code, and then take peer review.

The Scientific Method is not everyone's comfort zone...

Is there a simple "make" system avaiabvle to build and run this? If not, any install guide?

I am impressed by this work.

[mrh]

Originally Posted by chalsall

Thank you for doing this. It takes some confidence to publish code, and then take peer review.

The Scientific Method is not everyone's comfort zone...

Is there a simple "make" system avaiabvle to build and run this? If not, any install guide?

I am impressed by this work.

Thanks! I wasn't sure if there was interest. For now I've added some basic instructions to the README. I'll cleanup the CPU side a bit and add a makefile in a while.

https://github.com/mrh42/vtf/blob/main/README.md

edit: I'm working on a version that doesn't require GL_EXT_shader_explicit_arithmetic_types_int64. I don't know if it will be better or worse. Its a bit of work, so it may not show up for a few days.