mpreda

There's also a different way of "getting water from food": methabolizing (burning) carbohidrates with oxygen produces CO2 (carbon dioxyde) and.. water. I think that desert mouse eats very dry grain (which does not contain much water), but does not need to drink water because of that by-product of metabolism.

I don't think it's the engine exhaust, neither the engine air intake.

I think the exaust has possitive pressure when the engine is running which would prevent water from entering. OTOH water entering the engine air intake.. would be quite bad for the engine I guess, so there'd be protection against that. Also both of these (exhaust & intake) are not free to the inside of the vessel, but form a closed circuit with the engine, so there's no way to flood the vessel through those.

So probably we're talking about the engine room *ventilation* openings that would let water in.

Really, "oxygen to fire" is a bad metaphor for sugar for anybody remotely aquinted with chemistry. Why not "gas to fire" or "hay to fire" or even.. "sugar to fire", instead?

Thank you all for the questions! This was basically my first submission on HN, I'm still learning how to do things around here, but the overall tone was gentle and encouraging. And my main take-away was that I need to make the software more user-friendly in order to help potential new users try it out -- I'll work on that.

Yes I expect there may be some micro-optimizations that are available on CUDA, such as using bits of PTX in places.

And if the GPU provides some sort of matrix-multiplication on FP64, that we're not currently making use of -- clearly that would be a big opportunity.

But somebody needs to implement it, profile, test.. on some HW.

No, you don't have to understand the algorithms in order to use the software.

But I understand your feedback. I put it on my list to make it really easy to see the software running once you have the executable.

There is one little complication though -- you do need a working OpenCL install in order to use GpuOwl. For example, for AMD GPUs, you'd need to install ROCm. On Nvidia GPUs you'd need a working install of CUDA.

> Are you aware of any other computational maths problems where a sufficiently motivated amateur could make an improvement on the state of the art?

Unfortunatelly no, there's nothing I can think of, but that's clearly because I don't know what's out there.

If there's something you'd like to do, focus on something small/simple at first, get it done, and iterate from there.

Sorry, I don't know, and I don't even have an oppinion on the paper yet.

PRP is a pretty efficient test though, I would consider it a breakthrough for anything to improve on the efficiency of PRP for mersenne candidates.

3. Answered in point 1., we use IBDWT and get modular reduction for free through the circular convolution. This works nicely for Mersenne modulus.

4. GCD is not used in PRP, but it is used in P-1 (Pollard's P-1 algo). We use GMP GCD on the CPU (as it's a very rare operation, and GMP/CPU is fast enough). I understand the complexity of the GCD as implemented in GMP is logarithmic which is good.

5. For our dimension it does not make sense to use a quadratic algo instead of a NlogN one; We absolutely need the NlogN provided by convolution/FFT.

2. This was discussed to some length over the years on mersenneforum.org [1]. There is a lot of wisdom stored there but hard to find, and many smart & helpful guys, so feel free to ask there. This is an operation of interest because it's:

   - involved in TF (Trial Factoring), including on GPUs
   - involved in NTT transforms ("integer FFTs")

[1] http://mersenneforum.org/

1. Yes, the core of the algorithm is the modular squaring. The squaring is similar to a multiplication, of course. In general, the fast multiplication is implemented via convolution, via FFTs which results in a N x log(N) time complexity of the multiplication.

What we do is modular squaring iterations:

x := x^2 mod M,

where M== 2^p - 1, i.e. M is the Mersenne number that we test.

Realize that working modulo 2^p - 1 means that 2^p == 1, which corresponds to a circular convolution of size p bits. We use the "Irrational Base Discrete Weighted Transform", IBDWT [1] introduced by Crandall/Fagin to turn this into a convolution of a convenient size N "words", where each word contains about 18bits, so Words ~= p/18. For example our prime of interest M52 was tested with a FFT of size 7.5M == 1024 * 15 * 512.

The FFT is a double precision (FP64) floating point FFT. Depending on the FFT size we can make use of about 18bits per FFT "word", where a "word" corresponds to one FP64 value.

Some tricks involved up to this point are: one FFT size halving and the modular reduction for free because of IBDWT. Another FFT size halving because turning the real input/output values into complex numbers in the FFT.

The FFT implementation that we found appropriate for GPUs is the "matrix FFT", which splits the FFT of size N=A*B into sub-FFTs of size A, one matrix multiplication with about A*B twiddle factors, and sub-FFTs of size B. In practice we split the FFT into three dimensions, e.g. for M52 we used: 7.5M == 1024 * 15 * 512.

We implement in a workgroup one FFT of size 1024 or 512. These are usually base-4 FFTs, with transpositions using LDS (Local Data Share, local per-workgroup memory in OpenCL).

The convolution is formed of:

   - forward FFT
   - element-wise multiplication
   - inverse FFT

After the inverse FFT, we also need to do Carry propagation which properly turns the convolution into a multi-word multiplication.

For performance we merge a few logical kernels that are invoked in succession into a single big kernel, where possible. The main advantage of doing so is that the data does not need to transit through "global memory" (VRAM) anymore but stays local to the workgroup, which is a large gain.

So, to recap:

   - multiplication via convolution
   - convolution via FP64 FFT, achieving about 18bits per FP64 word
   - modular reduction for free through IBDWT

[1] https://en.wikipedia.org/wiki/Irrational_base_discrete_weigh...*

What's nuts is how fast you can square such a number on a GPU!

A number of 136M bits (136 Mega bits), using a 7'500'000-points FFT, can be squared and mod-reduced (modular reduction) in less than 1ms (one milli-second) on consumer-priced (less than $500) GPUs.

"primecurious", who you are and what is the purpose of such statements? how would you know who is or isn't sponsoring my work?

But just to set it straight, GpuOwl received exactly $0 contributions or sponsoring from exactly nobody. It's a pleasure work from my side, and it's open sourced for the easy access of curious minds to the algorithms and techniques implemented. I did receive great help, in the form of source-code contributions, most importantly from George Woltman.

IF ROCm stops supporting Radeon Pro VII, the first solution is to stay on the most recent ROCm that still supports them.

Second, "does not support anymore" does not necessarily mean that it stops working on the old HW, but it could mean that new features/extension aren't implemented for the old HW anymore, and we may not care about those.

Third, AMD does contribute and integrates changes with upstream LLVM. This open-source work could be used by third parties (with significant effort I assume) to continue support.

The HW setup for finding the prime was Nvidia and AMD GPUs with good FP64 in the cloud, using "spot" instances for better price. This allowed scaling up quickly to many GPUs, and it did have a significant cost.

My personal setup is 8x Radeon Pro VII which also provide heating during the cold season. During summer the effort is in removing the excess heat, and the GPUs run in a reduced-power mode (slower & more efficient).

Point taken. I need to improve the documentation and make it easier to start with.

There is a lot of documentation and HowTos on the Mersenne Forums [1] where experienced users help newcomers, and that relieves effort from myself.

[1] http://mersenneforum.org/

Yes. In fact the transition from LL to PRP took place in two steps, at different moments in time.

We used to use the LL test because the LL result is a bit stronger than the PRP result, LL stating that the number is prime, while PRP saying only that it is likely prime. This is the reason LL is still used as an after-test following any successful PRP discovery, as it happened for the most recent M52 as well.

The first transition from LL to PRP happened because a very strong and cheap error-checking algorithm, that we call "the Gerbicz error check", was discovered by Robert Gerbicz. This error-check in its most efficient form only works for PRP not for LL. This error-check allows to verify the correctitude of the computation, as it progresses on the GPU, with high confidence and low overhead. It does protect against a lot of HW errors originating from e.g. the GPU VRAM overheating, the GPU having been under-volted too aggressively, bad VRAM; but also from SW bugs and from FFT precision issues.

As the test of a single exponent takes a long time (let's say 24h on a fast GPU), having confidence that this long computation is proceeding along correctly instead of wasting cycles is a great benefit from the error-check.

The second step of the transition from LL to PRP happened when the PRP proof was introduced, following on the ideas from the VDF (Verifiable Delay Function) article, which allowed to verify cheaply that a PRP test was indeed executed correcty. This eliminated the need for the Double Check (DC) which was standard procedure with the LL test; practically speeding the process up with 100%.

My above answer was typed on a mobile phone while travelling, so it was maybe exceedingly brief. But now, on a real keyboard, I can go into more detail on any point if there's interest.

Indeed CUDA is nice due to the way it uses C++, integrates host and GPU code in a single file, and in the convenience of compilation. Basically I think CUDA is a bit easier to start with than OpenCL.

OTOH CUDA only works on Nvidia, and that's a major limitation.

GpuOwl uses heavily FP64 ("double" floating point), and FP64 is more readily available at consumer prices on AMD GPUs. We (the GIMPS project) use a lot of Radeon VII and Radeon Pro VII GPUs, which have great FP64 at a cheap price (I am personally running 8x Radeon Pro VII that I bought new for about $300 a piece).

So you see, for us AMD GPUs are the first citizen. Of course I want to support Nvidia GPUs as well, and OpenCL allows that. Luke Durant did run GpuOwl on a lot of Nvidia GPUs in the cloud, and I'm happy GpuOwl did work well for him on Nvidia.

What! This is absolutely not true. My open source work was not sponsored by anyone. And IMC is not my employer. But really, how did you get this idea?

I don't know, I haven't eplored OpenMP myself.. maybe some day.

OpenCL works on both AMD and Nvidia GPUs with mostly the same source code. By supporting at-runtime compilation it allows a lot of code particularization/instantiation before compilation, which reduces the power (cost) of the generated code. In general OpenCL is close enough to the HW and the generated code is improving over time (LLVM).

Motivation: a long time ago I had an AMD GPU and no way to run an LL test on it, so I decided to write my own. And I was hooked by the power of the GPU and the quest for ever more efficient, faster implem.

1. My profiling is rudimentary but effective. I measure per-kernel execution time with OpenCL events (which register with high accuracy start/end times w. practically no overhead), and also I continously measure per-iteration time by dividing wall-time for blocks of 20'000 iterations by that nb. These measuremens are consistent and sensitive.

2. I'm not aware of good learning resources. Explore existing such code, e.g. opencl miners tend to use asm. Read in amdgpu/ in LLVM. Disassemble code from OpenCL and read the ISA. Explore and experiment, but it's tedious. I would not recommend to jump into ISA initially. BTW AMD does have good GCN ISA docs available online, that is useful!

3. Yes I often read the compiled ISA, and over time I discover bugs and also better understand the ISA.

4. OpenCL is SIMD, and yes it matches the GPU HW.

5. most important is to reduce the number of registers used (#VGPRs), as that influences heavilly the occupancy of the kernel. Use fewer costly instructions such as FP64 mul/FMA. Sequential memory access, and in general reduce global memory access as it's very slow. Merge small kernels into one (keep the data in the kernel). Never spill VGPRs.

Some topic ideas:

  - Why use OpenCL when implementing GPU software
  - Does it run on AMD or on Nvidia GPUs?
  - How does the primality test implemented in GpuOwl work?
  - How fast is it to test a Mersenne candidate?
  - Why use FFTs? how large are the FFTs?
  - What do you use for sin/cos?

Is there an equivalent of Tidal Heating [1] taking place between the two black holes? It would extract kinetic energy and put it into.. heating the black holes.. whatever that may mean. Assuming there is movement and friction in the core of a black hole.

[1] https://en.wikipedia.org/wiki/Tidal_heating

> discovered [...] on an NVidia A100

Running an OpenCL (not CUDA) program [1], that runs just as well on AMD as on Nvidia GPUs.

[1] https://github.com/preda/gpuowl

> “$50k/year in AWS costs would equal current GIMPS search throughput”

I think you may be wrong by at least 3 orders of magnitude.

I'm right handed; when I experimented with writing with my left hand, I discovered that it's much easier to write "in mirror", right to left, using mirrored cursive characters. (also slanted in mirror)

Solves the problem with the hand overlapping the fresh writing and produces some funky-looking text.

Not so inherently IMO.

What I mean is: where did you take that from? I program FFTs on GPUs, and I see no reason for the "inherently can't reach 100% utilization by any metric".

While still abroad, interview and get a job in a big company in a developed country. Afterwards the company will help with relocation, visa, and other paperwork.