6 ms·

The problem with parallelisation

26 points by 00_NOP 7y ago

darknoon 7y ago
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.
- zozbot234 7y ago
  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.)
  - sdenton4 7y ago
    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.
- vardump 7y ago
  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.
QuadmasterXLII 7y ago
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.
- tombert 7y ago
  That's Gustafson's Law, right? [0] [0] https://en.wikipedia.org/wiki/Gustafson's_law https://en.wikipedia.org/wiki/Gustafson's_law
- TheOtherHobbes 7y ago
  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 https://en.wikipedia.org/wiki/Amdahl%27s_law
  - tombert 7y ago
    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 https://en.wikipedia.org/wiki/Gustafson's_law
- sgt101 7y ago
  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.
  - eesmith 7y ago
    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.
timerol 7y ago
Counterpoint: The NVIDIA Titan RTX has 4608 CUDA cores. We won't see 1024-core CPUs because GPUs cover that use case already.
- tombert 7y ago
  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.
  - pmoriarty 7y ago
    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?
    - Symmetry 7y ago
      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.
    - diabeetusman 7y ago
      To directly answer your question, graphics cards are Turing complete but they are optimized for a highly parallel workload.
    - lalaithion 7y ago
      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.
mattnewport 7y ago
"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.
- theandrewbailey 7y ago
  It's almost as if the author took a conventional quad core CPU and imagined it divided up into 1000 cores instead of 4.
  - 00_NOP 7y ago
    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.
petermcneeley 7y ago
I think Cliff click of Java on 1000 cores might disagree. https://youtu.be/5uljtqyBLxI https://youtu.be/5uljtqyBLxI
- eesmith 7y ago
  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")
jupp0r 7y ago
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.
proc0 7y ago
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-systems/ https://battlepenguin.com/tech/microservices-and-biological-... [2] https://spectrum.ieee.org/semiconductors/processors/cerebrass-giant-chip-will-smash-deep-learnings-speed-barrier https://spectrum.ieee.org/semiconductors/processors/cerebras...
Symmetry 7y ago
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.
Google234 7y ago
See: https://en.wikipedia.org/wiki/Amdahl%27s_law https://en.wikipedia.org/wiki/Amdahl%27s_law Can't sure what this PhD is adding.
gnufx 7y ago
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.
- 00_NOP 7y ago
  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.
deleted 7y ago
[deleted]

26 points by 00_NOP 7y ago

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.

zozbot234 7y ago
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.)
- sdenton4 7y ago
  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.
vardump 7y ago
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.

QuadmasterXLII 7y ago

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.

tombert 7y ago
That's Gustafson's Law, right? [0] [0] https://en.wikipedia.org/wiki/Gustafson's_law https://en.wikipedia.org/wiki/Gustafson's_law
TheOtherHobbes 7y ago
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 https://en.wikipedia.org/wiki/Amdahl%27s_law
- tombert 7y ago
  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 https://en.wikipedia.org/wiki/Gustafson's_law
sgt101 7y ago
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.
- eesmith 7y ago
  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.

timerol 7y ago

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

tombert 7y ago
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.
- pmoriarty 7y ago
  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?
  - Symmetry 7y ago
    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.
  - diabeetusman 7y ago
    To directly answer your question, graphics cards are Turing complete but they are optimized for a highly parallel workload.
  - lalaithion 7y ago
    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.

mattnewport 7y ago

"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.

theandrewbailey 7y ago
It's almost as if the author took a conventional quad core CPU and imagined it divided up into 1000 cores instead of 4.
- 00_NOP 7y ago
  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.

petermcneeley 7y ago

I think Cliff click of Java on 1000 cores might disagree. https://youtu.be/5uljtqyBLxI https://youtu.be/5uljtqyBLxI

eesmith 7y ago
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")

jupp0r 7y ago

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.

proc0 7y ago

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-systems/ https://battlepenguin.com/tech/microservices-and-biological-... [2] https://spectrum.ieee.org/semiconductors/processors/cerebrass-giant-chip-will-smash-deep-learnings-speed-barrier https://spectrum.ieee.org/semiconductors/processors/cerebras...

Symmetry 7y ago

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.

Google234 7y ago

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

gnufx 7y ago

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.

00_NOP 7y ago
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.

deleted 7y ago

[deleted]