The problem with parallelisation | Hacker News Reader

The problem with parallelisation

cartesianproduct.wordpress.com

26 points00_NOP50 comments

This guy really misses the point. You don't put 1024 x86 cores on a chip because the programming model of individual threads being scheduled ad-hoc doesn't scale that well (and imposes a lot of overhead on the control apparatus).

But on a GPU, it is typical to have well over 1000 cores using a different programming model that accounts for memory access and grouping threads together to accomplish shared work and shared memory accesses.

So, the same work is now being done with slightly different algorithms that exploit this programming model.

CUDA/SPIR-V "cores" are not true cores - they're the equivalent of CPU execution units (ALU's). You don't really "group threads together" on a GPU, so much as use a single real "thread" to execute a whole bunch of computations in lockstep, using a lightly-extended SIMD model. That's the only way you can make such a huge amount of execution units/ALU's useful, and not all domains are well-suited to this approach. (Which is one reason why a lot of code still runs on plain multicore CPU's.)

Yah, though I think there is more to be gained than often realized. Many algorithms can be rewritten to run much faster on gpus, though it takes some effort (and a different perspective, as a designer and programmer).

I rewrote a toeplitz matrix solver not so long ago; it was pretty fun! Treat conditional statements as plagues, and don't worry as much about early stopping... Every example takes the worst case time to handle, but you can do thousands of them at the same time. Ended up getting about a 1000x speed up against the baseline.

I think it's you who missed the point.

If your algorithm requires any serial coordination between execution units, you're hosed, whether you're using CPU, GPU or really anything that can be used for computation.

There are a set of algorithms that are "embarrassingly parallel", and that's where for example many graphics tasks fall. Same is not true in general.

Counterpoint: The NVIDIA Titan RTX has 4608 CUDA cores. We won't see 1024-core CPUs because GPUs cover that use case already.

I was going to say that too; GPUs aren't exactly general-purpose CPUs like an Intel/AMD/ARM chip would be, but they clearly prove that having thousands of cores can help specialized cases.

Please forgive my ignorance, but are GPUs not suitable for general purpose computing because they don't have enough types of logic gates to allow turing complete computation on them, or are they capable of such computation but just aren't optimized for it or what?

Is it something software can do anything about?

A big GPU might have 50 units capable of independently issuing instructions and each of those might have 50 execution units that will execute that instruction if its program counter matches their own. So it's hard to make a good comparison in thread/core count between modern GPUs and CPUs. But each of those 50 blocks can certainly emulate a CPU core on its own perfectly well. But that would be pretty inefficient compared to just using a CPU core.

To directly answer your question, graphics cards are Turing complete but they are optimized for a highly parallel workload.

GPUs are turing complete. They and CPUs are turing-equivalent, but they're optimized for different tasks. Specifically, GPUs are great at doing the same task on different data all at once.

This gets back to the example in the blog post. GPUs can run anything, but if the code spends any appreciable time communicating between threads the performance of a GPU will tank because the individual "cores" are quite slow.

I don't think it's that simple - you could easily communicate across "threads" in a warp, since these are just SIMD execution units. And you could use GPU main memory to communicate across true "streaming" processors, with some minimum latency. The troubling case is when communication latency limits performance, and the communication is not tightly-coupled within something like a warp. That's when CPU's (or even more exotic models, like systolic arrays etc.) might be preferable.

I think the most important part is not communication, but control flow dependencies on data.

GPUs are SIMD

Which means given a wave of 64 that gpu has only 72 cores(cus)

yes and no. they're a bunch of distinct simt cores. so what works badly on a few x8s SIMD cores can work great on GPUs.

ex: df.groupby('x').agg(my_weird_symbolic_func) can do well in rapids.ai and badly on AVX.

To be fair, the original title used here on HN was neither the title of the linked-to essay nor a quote from the essay, but likely a user-submitted title. It has since been changed to match the actual title.

Note the first line of the text specifically references "general computing."

Exactly.

If you're looking for advancement in computing power in the same programming paradigms and hardware styles you've always used, you will eventually be disappointed.

We've had GPUs for ages. Programming for GPUs is common, though I would suspect has significant innovation remaining.

If you're treating that number as accurate, then I'm running on a 896-core x86 computer.

As a comparison between GPUs and CPUs, each "CUDA core" is approximately equal to a SIMD lane on an x86 core. So 56 cores, times 16 lanes (AVX-512) per core, is 896 cores.

> each "CUDA core" is approximately equal to a SIMD lane on an x86 core

It's not really, that's why Larrabee failed.

Could you ELI the difference.

Bingo.

It has bothered me a long time how the whole industry has fallen to GPU manufacturer marketing speak.

That Nvidia Titan RTX thingie is a monster, but it has only 72 SMs (Streaming Multiprocessor), the closest equivalent to a CPU core. That is, SM is the smallest unit that can individually execute a true branch. Just like a CPU core.

Not counting hyperthreads here, GPUs have a metric ton of them, because they have to do useful work while waiting for very high latency memory. CPUs need much less of them to cover "bubbles in the pipeline".

The Turing architecture is a bit more sophisticated than that:

"Like Volta, the Turing SM is partitioned into 4 sub-cores (or processing blocks) with each sub-core having a single warp scheduler and dispatch unit"

"Like we saw in Volta, these changes go hand-in-hand with the new scheduling/execution model with independent thread scheduling that Turing also has, though differences were not disclosed at this time. Rather than per-warp like Pascal, Volta and Turing have per-thread scheduling resources, with a program counter and stack per-thread to track thread state, as well as a convergence optimizer to intelligently group active same-warp threads together into SIMT units. So all threads are equally concurrent, regardless of warp, and can yield and reconverge."

GPU 'cores' are still not as general as a full CPU core but they are a fair bit more flexible and sophisticated than a SIMD lane.

https://www.anandtech.com/show/13282/nvidia-turing-architect...

Interesting.

So what are the sub-core limitations execution flow wise? Or is it truly generic?

Can there be execution level conflicts? Like execution flow could be taken, but execution resources constraining (stalling) it somehow?

I'm only talking about "per clock" view, not about hardware threading. Sometimes these terms are mixed in a bit hard to decipher fashion.

It's hard to get detailed information on a lot of this as much of it is considered proprietary by NVIDIA. My understanding is that threads are not truly independent as they would be on full CPUs but that the hardware is able to dynamically detect thread divergence (when different lanes / threads of the SIMDish hardware take different branches) and intelligently regroup the threads to minimize divergence. I'm not sure how they then deal with instructions that operate across a warp, it's possible those interfere with the regrouping but they're not commonly used in many typical pixel shader workloads so it may be an overall win.

I suspect some of these changes were to make raytracing more efficient (and the Anandtech article suggests as much too). A common problem trying to implement a GPU raytracer on older architectures is performance tanking when rays diverge too much. NVIDIA's Optix did some complicated magic to try and regroup divergent threads but having direct hardware support for it probably makes the raytracing GPU code both simpler and more efficient.

The description is unclear, but these look more like hyperthreads/SMT units than true CPU cores. It's talking about "scheduling resources" implemented in hardware, which suggests a SMT model.

GPUs are already SMT processors, since that's how they handle main memory latency. Instead, I suspect it's essentially dynamic warp formation to handle cases where there's still enough threads to keep all the lanes busy, but they're spread out over several static 16-thread chunks instead of being right next to each other.

> GPUs are already SMT processors, since that's how they handle main memory latency.

I thought they used a simpler barrel-processor model to handle that. SMT seems a bit more sophisticated.

(initial comment deleted since one part addressed integer 'lanes' instead of the 32-bit FP that's more directly relevant in a comparison with a GPU, and the other part was incorrect.)

> They have 16 SIMD registers.

AVX-512 has 32 SIMD registers.

I'm counting the number of single-precision FP units. Although, strictly speaking, AVX-512 hardware actually has two FMA units per core.

I thought AVX-512 ALU resources varied between models?

This is Skylake server part (which should be implied by the high core count), which is using this block diagram: https://www.researchgate.net/figure/Skylake-Microarchitectur...

"For code that is 99.9% parallel then using 1000 processors (each of which is about 250 times slower than the one faster chip they collectively replace) we can double the speed, more or less."

Where does that 250x slower come from? That doesn't seem a very reasonable assumption.

It's almost as if the author took a conventional quad core CPU and imagined it divided up into 1000 cores instead of 4.

If you read the paper referenced in the article you will see it comes from the formula used there to define the Pareto frontier of CPU performance.

It's true that you can't do the same work 1000 times faster with 1000 cores, but what analysis like this misses is that often you can do 1000 times more work, work that you wouldn't even attempt with a single core system.

That's Gustafson's Law, right? [0]

[0] https://en.wikipedia.org/wiki/Gustafson's_law

See also Amdahl's Law for the trade-off between speed and parallelism in massive multicore architectures.

https://en.wikipedia.org/wiki/Amdahl%27s_law

I think the OP knows about Amdahl's Law, but even Ahmdahl's law only talks about fixed-sized problem spaces. The solution to that is to increase the size of the problem space, which is covered by Gustafson's Law. [0]

So, basically, any particular problem will only go n-times faster thanks to Ahmdahl's law, but with the advent of more CPUs, we feel less restricted in our problems, and as a result work on bigger data sets.

[0] https://en.wikipedia.org/wiki/Gustafson's_law

Yes - so if you put 1000 cores with 1000 caches on a chip you could run 1000 vm's - more or less, perhaps 10000 in fact? Why aren't there chips like this... I think because it would blow apart the server manufacturers business models, and Intel's business model as well.

Those caches take up space. Or rather, if you could have 1000 cores each with 16 MiB L3 on-die cache, then why don't we see machines now with 10 cores and 1.6 GiB on-die L3 cache?

After all, there already exists plenty of software (including some I wrote) which is limited by memory bandwidth, or by latency.

Also, all of those 1000 cores would compete for the same main-memory bandwidth, so are much more likely to be bandwidth starved.

OP does not talk about data parallelism vs task parallelism at all.

SIMD instructions and GPGPU has come a long way and while clock rates have somewhat stagnated, we can solve many problems on consumer hardware today that were impossible in Pentium 3 days (big ML models, augmented reality, live ray tracing, ...). It was a painful transition from existing computation models, but it has been a gigantic success imho.

This is interesting and would enjoy reading more about it in the white paper when it's shared. Could it be the next paradigm shift in computing is really the mastery of parallelization techniques baked into the hardware? I'm seeing a similar theme to recent posts about microservices as biological systems[1] and that Cerebras chip[2], which could mean that instead of improving monolothic performance, multiple monoliths converge into a new, higher level processing paradigm that is able to go above and beyond the performance of the individual architecture improvements.

[1] https://battlepenguin.com/tech/microservices-and-biological-...

[2] https://spectrum.ieee.org/semiconductors/processors/cerebras...

I wonder, have people done research on the parallelizability of different tasks? This is hard in that there obviously different algorithms with different characteristics regarding the same problem where you might tradeoff paralizability for computational difficulty. But there seem to be some domains, like graphics, where million way parallelism aren't uncommon.

We tend to think that replacing a O(n) algorithm with an O(n ln(n)) algorithm is a bad idea. But if it lets you spread out your problem over multiple threads it might very well be worth it. Within a certain range the power and silicon required to execute sequentially at a certain speed is, to simplify hugely, a bit more than the square of that speed so there's a lot of potential for improvement.

Certainly anything a human brain can do can be done in an embarrassingly parallel way which ought to be of some comfort.

I think Cliff click of Java on 1000 cores might disagree.

https://youtu.be/5uljtqyBLxI

That was 54 cores per die, 864 cores max.

This essay concerns 1024-core chips. ("When I started the PhD as a part-time student in 2012 the firm expectation in industry was that we would by now be well into the era of 1024-core chips. That simply hasn’t happened because, at least in part, there is no firm commercial reason for it")

I'm not sure what the cores actually are, but the PEZY chips have 1024 and 2048 cores, end Epiphany V taped out at 1024. There are others, at least Kalray and Sunway (Taihulight), with 256 cores. They may not be sufficiently general-purpose -- Taihulight is imbalanced against memory bandwidth -- but can clearly do well on the right sort of problem.

Epiphany did indeed tape out at 1024 - which is why there is the acknowledgement that large scale manufacture of such chips is probably perfectly possible. But Epiphany never went to manufacture, which is sort of the point here.

See: https://en.wikipedia.org/wiki/Amdahl%27s_law Can't sure what this PhD is adding.

Reply on news.ycombinator.com