Hacker News Reader

Note that the article is specifically talking about testing accelerated code. This is usually using machine-specific features, meaning it won't run on a graphic card.

I am also not sure about how fast you are if you need to transfer data out of the GPU, or to add conditional branching to the shader code (it used to be that branches were super slow in GPUs, not sure where they are now).

I could see it working for some other problems though.

> meaning it won't run on a graphic card.

GPUs implement the ceil and round functions.

Heck, GPUs implement popcount, bit-reverse, and a whole slew of instructions that CPUs don't. (Mainly bitreverse and bpermute. Intel x86 only has permute (aka pshufb), but not the backwards version. BSwap can't emulate bitreverse)

> (it used to be that branches were super slow in GPUs, not sure where they are now).

Branches are fine. Its divergent branches (in both CPUs and GPUs) that are slow. A uniform branch will be branch-predicted on a CPU, while a uniform branch on a GPU will have all 64-threads (AMD GCN) or 32-threads (NVidia or RDNA) follow the instruction pointer.

There's no slowdown with uniform branches, either on CPUs or GPUs. Both CPUs and GPUs do poorly on divergent branches, but GPUs do MUCH worse than CPUs.

The article was about testing a specific implementation of floor, ceil, and round using CPU instructions. You can run floor, ceil, and round on the GPU, but that won't tell you whether your new implementation using CPU instructions is correct.

I thought the post was about how the 32-bit space could be exhausted in minutes with common hardware in the year 2014. Which means that any problem I have which is in the 32-bit space is a candidate for brute force.

Given the advances in computers over the past few years: exhausting the 64-bit (or 2x 32-bit) space is "reasonable" for the year 2020. At least, reasonable for people who are willing to wait a month (on one GPU), or willing to buy a cluster of GPUs.

No, the article is that if you have some code that operates on a 32 bit value, it's reasonable on most modern hardware to try all 2^32 values to ensure quality.

There may be some GPU code that is reasonable to test on all 2^64 values, but it doesn't help us verify the implementation of SSE (Intel architecture) ceil/round/etc against reference implementations at all, because trying all double precision values would not complete in a practical amount of time and offloading it to a GPU means we are not testing the SSE implementation that we're trying to verify anymore.

> trying all double precision values would not complete in a practical amount of time

Actually we're getting close-ish: AVX512(=8x64) at 4GHz (or two dependency chains at 2GHz) times 64 CPU cores (which TFA's author has mentioned having) is 2 teraops. Double-precision space of 2^64 / 2Tops is 3 months/instruction on a single computer. So you could brute-force verify a simple function in a year or two, and at least the SIMD width and number of cores is likely to continue increasing.

Keep in mind you need to run the non-SIMD baseline function, too, to perform the actual comparison/verification... So, not yet.

Also, AVX512 throttles down, so you're not going to running it on all cores full tilt at 4GHz today.

I think it's much more reasonable for 64 bit space to have a reasonable set of human-chosen test cases + a large randomized test sequence.

The post was about exhausting the space to test code. The example they used of code that should have been tested this way was CPU code. If you're testing CPU code, exhausting the space quickly on a GPU isn't helpful.

> I thought the post was about how the 32-bit space could be exhausted in minutes with common hardware in the year 2014. Which means that any problem I have which is in the 32-bit space is a candidate for brute force.

No, the post is about exhaustive testing, and that it's completely reasonable on 32 bit values because it only takes a few minutes.

> Given the advances in computers over the past few years: exhausting the 64-bit (or 2x 32-bit) space is "reasonable" for the year 2020.

That's not actually reasonable, it's feasible for very specific contexts.

> At least, reasonable for people who are willing to wait a month (on one GPU), or willing to buy a cluster of GPUs.

And whose code specifically can run on GPU. TFA is about CPU-optimised code, the entire point was to exhaustively test an SSE3 implementations. How do you do that on a GPU?

> That's not actually reasonable, it's feasible for very specific contexts.

I was inventing a new hash function for myself, just for giggles a few weeks ago.

I needed a constant: I started by choosing an arbitrary constant (I started with 0x31415926...), but then I realized that the 32-bit space, and even 50+ bit spaces were feasible on my GPU.

I ended up rewriting the random-number generator on the GPU, and searched for the number which caused the largest number of "avalanche" bit-flips across the entire 32-bit seed space of the RNG.

Where an "avalanche" bit flip is 16 bits flipped, and 16-bits remaining the same, after the RNG was applied to the seed.

For example: seed = 1 * K, where K == 0xAAAAAAAA will cause 16-bit flips, and 16-bits to remain the same.

Repeat for all 32-bit values of seed, searching for the optimal K. 0xAAAAAAAA wasn't the best number (aka: 1010101010101010 binary), but you can see where my thought process was.

My RNG was more complicated than just a single multiply, but I think you can see where the general thought process was with my above example.

--------

There was a time when constants were arbitrarily chosen for these kinds of functions. But today, we can literally test ALL numbers and just pick the best.

If K is constrained by some other requirements (in my case: it must be odd, and a few other tidbits to work with my RNG), then you shrink the search space from 64-bits down to something that can be accomplished in just a few days of search.

-------------

As far as I'm concerned, the blog post is talking about how modern computers have conquered the 32-bit space.

My current post is how the 64-bit space could be feasibly explored. It wasn't even that long ago when 64-bit space was considered cryptographic-secure (see DES crypto algorithm or WEP).

> Note that the article is specifically talking about testing accelerated code. This is usually using machine-specific features, meaning it won't run on a graphic card.

I think there are a lot of computing algorithms you might run on a GPU where you might want to verify the correctness over the range of 32-bit or 64-bit numbers (integers or floating point).

You could also use this to verify 32-bit functions with two arguments.

Sounds like a small and relatively cheap farm could do it in hours or minutes even.

Hmmm... assuming 4-GPUs per node, and 1200W per node, you'll need 216kW to generate the result in a day.

But that also assumes that the operation you're testing is 1-clock tick, which is only true for the most trivial of calculations. Still, 216kWs per day per "test-case clock ticks" shows us that the 2^64 exhaustive bitspace is within a reasonable organization's grasp.

I think your units are wrong. You want 216kW days, not 216kW per day. 216kW days is 18.6Gj.

Hmm, "216kW days per test-case clock ticks" does sound more correct from a unit perspective.