3 ms·

> Most consumer problems are latency-bound. Is that even true? I'd argue a lot of what happens on consumer devices can (or could) be done in parallel. There's

> Most consumer problems are latency-bound. Is that even true? I'd argue a lot of what happens on consumer devices can (or could) be done in parallel. There's some need for a fast response, but things like, responding to a button click and updating some internal state, take a trivial amount of computation to implement. Updating your UI in response to that button click, that's again something that can be parallelized.

dragontamer 6y ago
Think of the following line of code: blah = blah->next A simple linked-list traversal: 50-nanoseconds on a typical consumer CPU. This could represent a DOM-tree traversal. Or it could be a Javascript object being allocated. Or it could be the text getting added to the end of your rope-data structure. Or it could be a binary-search (finding a new address to check next). Or a malloc() (which traverses a linked-list to find memory). This dereference happens very often. 50-nanoseconds to hit main-RAM, 10-nanoseconds if L3 cache, 4-nanoseconds if in L2 cache, 1-nanosecond if in L1 cache. This sort of operation is very fast on CPUs, especially if you're cached. Heck, your CPU won't even wait on the result: its going to branch-predict the answer and start executing the next bit of code before it even knows its correct. ---------- That same memory-dereference is 300-nanoseconds from GPU VRAM, and maybe 100-nanoseconds if you're in GPU L1 cache. If you got a tree, its probably going to be far faster to traverse on a CPU. Where the GPU wins is Raytracing: you can have millions of individual tasks traversing the same tree, in parallel, at larger overall bandwidths than a CPU ever could. IE: GPUs can perform 1000 binary searches faster than a CPU can perform 1000 binary searches. But how many applications need 1000 binary searches? Usually, you need 1 binary search, and once you get the result, you need to do something else. (And that result can be branch predicted for even further accelerations to speed).
- jedbrown 6y ago
  I agree in general, but I'm not confident of this: > GPUs can perform 1000 binary searches faster than a CPU can perform 1000 binary searches. With several vector lanes and ILP on a 64+ core node, the 1000 parallel searches on the CPU may well beat the GPU. It'd have to be tested in any case.
  - dragontamer 6y ago
    Hmmmm... 1000 is still a "small" number when we're talking about GPU cores. I probably should have said 100,000 binary searches, or 1,000,000 binary searches. You're right, 1000 is a small enough number where the CPU might still win. If its a large-enough data-structure to hit VRAM (ie: a binary search across a 8GB vector), that's what'd be best for the GPU. Raytracing is millions rays per scene. 4k is 8,294,400 rays at 1-sample per pixel, and each one of those rays has to traverse a BVH tree (similar to a binary tree). Each of those rays MIGHT set off a 2nd or 3rd ray, depending on what its bouncing against. The big BVH tree that organizes all of the video game triangles / objects is shared for all rays. That's the "1000s of binary tree searches in parallel" I was trying to reference. But I guess its closer to 10s of millions.
fulafel 6y ago
"Could be done in parallel" is a very different space. As is painfully evident, sw inertia/ path dependency is huge and we get widespread big changes on timescale of decades.

dragontamer 6y ago

Think of the following line of code: blah = blah->next A simple linked-list traversal: 50-nanoseconds on a typical consumer CPU. This could represent a DOM-tree traversal. Or it could be a Javascript object being allocated. Or it could be the text getting added to the end of your rope-data structure. Or it could be a binary-search (finding a new address to check next). Or a malloc() (which traverses a linked-list to find memory). This dereference happens very often. 50-nanoseconds to hit main-RAM, 10-nanoseconds if L3 cache, 4-nanoseconds if in L2 cache, 1-nanosecond if in L1 cache. This sort of operation is very fast on CPUs, especially if you're cached. Heck, your CPU won't even wait on the result: its going to branch-predict the answer and start executing the next bit of code before it even knows its correct. ---------- That same memory-dereference is 300-nanoseconds from GPU VRAM, and maybe 100-nanoseconds if you're in GPU L1 cache. If you got a tree, its probably going to be far faster to traverse on a CPU. Where the GPU wins is Raytracing: you can have millions of individual tasks traversing the same tree, in parallel, at larger overall bandwidths than a CPU ever could. IE: GPUs can perform 1000 binary searches faster than a CPU can perform 1000 binary searches. But how many applications need 1000 binary searches? Usually, you need 1 binary search, and once you get the result, you need to do something else. (And that result can be branch predicted for even further accelerations to speed).

jedbrown 6y ago
I agree in general, but I'm not confident of this: > GPUs can perform 1000 binary searches faster than a CPU can perform 1000 binary searches. With several vector lanes and ILP on a 64+ core node, the 1000 parallel searches on the CPU may well beat the GPU. It'd have to be tested in any case.
- dragontamer 6y ago
  Hmmmm... 1000 is still a "small" number when we're talking about GPU cores. I probably should have said 100,000 binary searches, or 1,000,000 binary searches. You're right, 1000 is a small enough number where the CPU might still win. If its a large-enough data-structure to hit VRAM (ie: a binary search across a 8GB vector), that's what'd be best for the GPU. Raytracing is millions rays per scene. 4k is 8,294,400 rays at 1-sample per pixel, and each one of those rays has to traverse a BVH tree (similar to a binary tree). Each of those rays MIGHT set off a 2nd or 3rd ray, depending on what its bouncing against. The big BVH tree that organizes all of the video game triangles / objects is shared for all rays. That's the "1000s of binary tree searches in parallel" I was trying to reference. But I guess its closer to 10s of millions.

fulafel 6y ago

"Could be done in parallel" is a very different space. As is painfully evident, sw inertia/ path dependency is huge and we get widespread big changes on timescale of decades.