4 ms·

I like the branch-predict / branch-verify split. It reminds me strongly of the ldrex/strex strategy in ARM for splitting (for example) a compare-exchange in two

I like the branch-predict / branch-verify split. It reminds me strongly of the ldrex/strex strategy in ARM for splitting (for example) a compare-exchange in two parts, so that in the non-contended case it basically just flows straight through. Having recently done a lot of GPU programming, I'm wondering what your thoughts are on a GPU-like approach, with tons of in-order cores. It's hard to program, but maybe we need to figure that out in order to get performance.

api 7y ago
I lean strongly toward your second paragraph. If we can make many core programming easier I think we can dispense with a ton of complexity and just scale out cores with transistor counts. I think an under researched area is the application of deep learning to compilers. What could be done there for parallelism? We are still kind of stuck in programming models developed back when core frequencies were scaling geometrically. We hit that wall in the early 2000's and still haven't quite assimilated it. We are tackling it at the macro scale of multiple discrete systems via modern devops but the systems (e.g. Kubernetes) are baroque, clunky, and hard to manage.
- deepnotderp 7y ago
  Regarding deep learning for compilers, at Vathys we're using deep learning in compilers for deep learning code and it works well, achieving pretty good results even compared to human implementations. But it's not that much of a gain and it can often get stuck on some code, especially if it's sufficiently new code. Just as surprisingly, genetic algorithms are almost as good but faster and more robust. Finally, I think people point to examples of much faster hardware accelerated workloads and optimized assembly code that share these characteristics: 1. Are relatively embarrassingly parallel 2. Are relatively control flow light 3. Generally tend to exhibit high compute/bandwith ratios. Hence, you see deep learning hardware, bitcoin mining hardware, optimized compression codec assembly, etc. pointed to as examples of acceleration, but this doesn't apply to all workloads, e.g. a web app.
- jcranmer 7y ago
  > I think an under researched area is the application of deep learning to compilers. What could be done there for parallelism? I don't think it's under-researched, because we already know that it's only ever going to do a lousy job. The problem of autoparallelization is mostly stymied by difficulty in computing the legality of transformations, and secondarily by the problem of tuning parameters [1]. We've realized that it's easier to just get the users to tell us about these things, sidestepping the problem for the most part. > We are still kind of stuck in programming models developed back when core frequencies were scaling geometrically. The programming model for parallelism is dataflow. We already know that: the tricky thing of parallelism is communication, so annotating all of the edges of communication makes the scheduling problem much, much easier. [1] Theoretically, machine learning is good at tuning parameters. In practice, you get good results with the dumbest algorithms already, and the available headroom for performance is generally swamped by the fact that small changes such as function size can dramatically alter the performance characteristics of code elsewhere in the application.
deepnotderp 7y ago
The "Branch Vanguard" paper does exactly this.
- Veedrac 7y ago
  Thank you, I've edited the article to cite this.
tntn 7y ago
> with tons of in-order cores It's worth noting that GPUs are only "in order" because the computer architecture community has decided that "out of order" means "some variation of Tomasulo." Every GPU architecture in the last decade has relied extensively on executing (and committing) instructions in a single instruction stream out of order. Doing a bunch of math while waiting for memory operations to complete is fundamental to high performance. Modern GPUs cannot achieve anywhere close to peak performance without extensive ILP - relying on latency hiding via threads is insufficient.
- atq2119 7y ago
  Regardless of Tomasulo, I would expect "out of order" to imply that (at the very least) when you have two independent streams of arithmetic (in the same thread) that depend on different memory loads, the order of execution of the arithmetic depends on which of the loads returns first. I don't think any GPU does that. You could perhaps argue that GPUs issue instructions in order, but memory instructions can retire out of order wrt arithmetic. If there is a GPU that's more out of order than that, I'd appreciate some pointers to evidence :)
Impossible 7y ago
The GPU model is a proven way to get better performance out of traditional CPUs also. You will get the best performance from modern CPUs if you treat each SIMD lane as a parallel execution on homogeneous data and also execute on multiple cores. See ispc, and Burst Compiler as examples. I think there is a view that this style of programming only applies to traditionally high compute areas like games, hpc, rendering, ML, etc but we've recently seen a lot of core building blocks of "normal" web applications like hash tables (https://code.fb.com/developer-tools/f14/ https://code.fb.com/developer-tools/f14/) and json parsers (https://github.com/lemire/simdjson https://github.com/lemire/simdjson) get massive perform gains from SIMD.
- Nyan 7y ago
  Note that SIMD on CPUs is somewhat different to GPU style "SIMD" (particularly for cases where you want fixed width SIMD vs arbitrary vector processing (ala SPMD, ISPC, CUDA etc)). JSON parsing, for example, doesn't scale in the same way as typical graphics applications do with wide vectors, for example. It's just that the traditional model of byte-by-byte parsing is very inefficient - SIMD implementations just exploit some of the unused parallelism available in CPUs. It's still very much a latency bound problem, and has complex control flow problems, which is why it wouldn't run well on a GPU, yet runs well on CPU SIMD.
Veedrac 7y ago
I pretty much agree with you: it's hard to program, but possibly something we just need to do anyway. It's a much more efficient way to build computers, and the relative benefits only look to get bigger... but if I knew how to make it work, I wouldn't be writing about CPUs!
Nyan 7y ago
> It's hard to program, but maybe we need to figure that out in order to get performance. There will always be problems which require latency over throughput. Although the idea has been tried - e.g. Xeon Phi.
deleted 7y ago
[deleted]

api 7y ago

I lean strongly toward your second paragraph. If we can make many core programming easier I think we can dispense with a ton of complexity and just scale out cores with transistor counts. I think an under researched area is the application of deep learning to compilers. What could be done there for parallelism? We are still kind of stuck in programming models developed back when core frequencies were scaling geometrically. We hit that wall in the early 2000's and still haven't quite assimilated it. We are tackling it at the macro scale of multiple discrete systems via modern devops but the systems (e.g. Kubernetes) are baroque, clunky, and hard to manage.

deepnotderp 7y ago
Regarding deep learning for compilers, at Vathys we're using deep learning in compilers for deep learning code and it works well, achieving pretty good results even compared to human implementations. But it's not that much of a gain and it can often get stuck on some code, especially if it's sufficiently new code. Just as surprisingly, genetic algorithms are almost as good but faster and more robust. Finally, I think people point to examples of much faster hardware accelerated workloads and optimized assembly code that share these characteristics: 1. Are relatively embarrassingly parallel 2. Are relatively control flow light 3. Generally tend to exhibit high compute/bandwith ratios. Hence, you see deep learning hardware, bitcoin mining hardware, optimized compression codec assembly, etc. pointed to as examples of acceleration, but this doesn't apply to all workloads, e.g. a web app.
jcranmer 7y ago
> I think an under researched area is the application of deep learning to compilers. What could be done there for parallelism? I don't think it's under-researched, because we already know that it's only ever going to do a lousy job. The problem of autoparallelization is mostly stymied by difficulty in computing the legality of transformations, and secondarily by the problem of tuning parameters [1]. We've realized that it's easier to just get the users to tell us about these things, sidestepping the problem for the most part. > We are still kind of stuck in programming models developed back when core frequencies were scaling geometrically. The programming model for parallelism is dataflow. We already know that: the tricky thing of parallelism is communication, so annotating all of the edges of communication makes the scheduling problem much, much easier. [1] Theoretically, machine learning is good at tuning parameters. In practice, you get good results with the dumbest algorithms already, and the available headroom for performance is generally swamped by the fact that small changes such as function size can dramatically alter the performance characteristics of code elsewhere in the application.

deepnotderp 7y ago

The "Branch Vanguard" paper does exactly this.

Veedrac 7y ago
Thank you, I've edited the article to cite this.

tntn 7y ago

> with tons of in-order cores It's worth noting that GPUs are only "in order" because the computer architecture community has decided that "out of order" means "some variation of Tomasulo." Every GPU architecture in the last decade has relied extensively on executing (and committing) instructions in a single instruction stream out of order. Doing a bunch of math while waiting for memory operations to complete is fundamental to high performance. Modern GPUs cannot achieve anywhere close to peak performance without extensive ILP - relying on latency hiding via threads is insufficient.

atq2119 7y ago
Regardless of Tomasulo, I would expect "out of order" to imply that (at the very least) when you have two independent streams of arithmetic (in the same thread) that depend on different memory loads, the order of execution of the arithmetic depends on which of the loads returns first. I don't think any GPU does that. You could perhaps argue that GPUs issue instructions in order, but memory instructions can retire out of order wrt arithmetic. If there is a GPU that's more out of order than that, I'd appreciate some pointers to evidence :)

Impossible 7y ago

The GPU model is a proven way to get better performance out of traditional CPUs also. You will get the best performance from modern CPUs if you treat each SIMD lane as a parallel execution on homogeneous data and also execute on multiple cores. See ispc, and Burst Compiler as examples. I think there is a view that this style of programming only applies to traditionally high compute areas like games, hpc, rendering, ML, etc but we've recently seen a lot of core building blocks of "normal" web applications like hash tables (https://code.fb.com/developer-tools/f14/ https://code.fb.com/developer-tools/f14/) and json parsers (https://github.com/lemire/simdjson https://github.com/lemire/simdjson) get massive perform gains from SIMD.

Nyan 7y ago
Note that SIMD on CPUs is somewhat different to GPU style "SIMD" (particularly for cases where you want fixed width SIMD vs arbitrary vector processing (ala SPMD, ISPC, CUDA etc)). JSON parsing, for example, doesn't scale in the same way as typical graphics applications do with wide vectors, for example. It's just that the traditional model of byte-by-byte parsing is very inefficient - SIMD implementations just exploit some of the unused parallelism available in CPUs. It's still very much a latency bound problem, and has complex control flow problems, which is why it wouldn't run well on a GPU, yet runs well on CPU SIMD.

Veedrac 7y ago

I pretty much agree with you: it's hard to program, but possibly something we just need to do anyway. It's a much more efficient way to build computers, and the relative benefits only look to get bigger... but if I knew how to make it work, I wouldn't be writing about CPUs!

Nyan 7y ago

> It's hard to program, but maybe we need to figure that out in order to get performance. There will always be problems which require latency over throughput. Although the idea has been tried - e.g. Xeon Phi.

deleted 7y ago

[deleted]