15 ms·

It's simple to do what you write, multiple languages already do just that. It's the class of problems that is called "embarrassingly parallel" (https://en.wikip

It's simple to do what you write, multiple languages already do just that. It's the class of problems that is called "embarrassingly parallel" (https://en.wikipedia.org/wiki/Embarrassingly_parallel https://en.wikipedia.org/wiki/Embarrassingly_parallel). However, it turns out that it places some rather serious restrictions on the kind of calculations you can perform this way. In general for two pieces of code to be executed in parallel, they must be independent of each other. I.e for the following 1: tmpA := A(input) 2: tmpB := B(tmpA) 3: tmpC := C(tmpB) 4: result := D(tmpC) it's impossible to calculate a line before the previous line has finished. You cannot do this calculation concurrently. On the other hand if it was like this: 1: resA := A(input) 2: resB := B(input) 3: resC := C(input) 4: resD := D(input) You can calculate all 4 concurrently and achieve a great speed-up if you have resources to do it. Except if B, C, or D somehow access the result of a previous line. For mathematical notation this is simple, but for general programming languages there are plenty of ways to do this. We know that an optimal optimization, i.e. finding the fastest way a program can be executed is known uncomputable. Not difficult, not brute forceable, but impossible to compute with traditional computers. The best we can do is identify _some_ concurrency optimizations, but so far it has not been a fruitful adventure for general programming languages. So what we can do is use patterns and constructs that rely on dividing the problems into concurrent pieces and use proper guarding on shared state. This is however notoriously easy to get wrong.

chmod775 6y ago
> We know that an optimal optimization, i.e. finding the fastest way a program can be executed is known uncomputable. Not difficult, not brute forceable, but impossible to compute with traditional computers. I'm really curious about the proof of this, since there's only a finite number of ways you can re-arrange instructions in a program. Likewise there's only a finite number of ways you could shard them across threads. For this to be true you'd clearly need to phrase the problem in a way that allows you to have an infinite number of possibilities, then prove you can't arrive at the optimal solution through some means that doesn't involve checking an infinite number of them. (Edit: Or prove that it is impossible to decide on which one is the fastest at the time the optimizer runs. When does the optimizer run?). Was the assumption that you'd also be (infinitely) unrolling loops or maybe 'rewriting' the program into something equivalent but faster? What does "finding the fastest way a program can be executed" mean? Just re-ordering instructions and distributing them across threads, or something more?
- Denzel 6y ago
  Finding the optimal execution time of an arbitrary program is equivalent to the halting problem. [1] If you narrow the “arbitrary” constraint to only include well-structured, analyzable, guaranteed-to-terminate programs, then you can at least start to approximate a solution. Finding the true optimal case, even under those conditions, would be computationally expensive. [1]: https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem
  - chmod775 6y ago
    This wasn't about anything related to optimal execution time. That an optimizer needs to know whether the code it optimizes terminates (or how long it runs) would also need proof if you'd want to go that route. The assumptions and optimizations the optimizer is allowed to use and what kinds of programs we're talking about, and what even is considered an "optimal program" is also still unclear (Edit: I'm assuming lowest number of instructions executed serially?). Please do refer me to a paper. Please do not link me vaguely related Wikipedia articles.
    - vidarh 6y ago
      It's equivalent to the halting problem because there exists a set of problems for which for any input that optimiser creates the optimal solution for, there exists another input for which that problem is not optimal. The parallel to the halting problem is that with access to the output of the optimiser, you can always construct a problem where whatever the optimiser produces can be obstructed by producing an input that makes the optimised program non-optimal for the given input. A trivial example of such a program is a function that sorts it input and returns the sorted result, as no sort is optimal for all inputs.
      - chmod775 6y ago
        > It's equivalent to the halting problem because there exists a set of problems for which for any input that optimiser creates the optimal solution for, there exists another input for which that problem is not optimal. You're trying to prove that no optimal solution can exist, not that it's impossible to find one. Which is fine, because it's a stronger claim. But it heavily depends on your definition of optimal. If you define optimal as "lowest average number of instruction across all possible inputs", then there exist optimal sorting algorithms. If you define optimal as: "A solution is optimal only if for every possible input there exists no solution that requires a lower number of instructions.", then yes, there can be no optimal sorting algorithm. I would argue that in practice only the first definition is useful. Further, you're assuming that "optimizations" that replace an existing algorithm with an equivalent one are allowed. Which brings me back to one of my original questions: What optimizations was hvidgaard allowing to be me made when he claimed an optimal solution is incomputable.
oblio 6y ago
I know about "embarrassingly parallel" problems, and the thing is, they're only "embarrassingly parallel" to solve in math. When programming the level of friction is from annoying to high unbearable, depending on the programming language. It should be trivial to implement these solutions, as trivial as the sequential solutions. It's not. Until this is the case in mainstream programming languages, I doubt we'll have CPUs with 1000 cores in our smartphones or laptops. I mean, we'll have them but they'll be useless because 99% of software today is practically single-threaded. The reason multiple cores are good for laptops, for example, is because we're multi-tasking between multiple applications, not because those cores are frequently used by day-to-day apps. I'm talking about random small apps, not compute intensive ones that have to use multi-threading intensively (rendering, compiling, what have you, professional level software).
- rbanffy 6y ago
  > but they'll be useless because 99% of software today is practically single-threaded. I used to joke developers should get workstations with SPARC Niagaras or Xeon Phis for that reason: core count is going up and a CPU with a dozen small cores is much cheaper to build than one with 4 beefy ones. Now some of the low-end chips Intel is pushing have 4 SMT2 cores. HEDT is on the 16 SMT2 core range and, if our software continues to be single threaded, there will be a lot of silicon being used for nothing more than spreading heat.
  - colejohnson66 6y ago
    Isn’t the point of high core counts for workloads that can actually be parallelized? Like compilation or graphics rendering?
    - rbanffy 6y ago
      A lot of tasks can be parallelized if you think hard enough. Your CPU is busy reordering instructions so they keep as many execution ports busy as it can so that it can retire as many instructions per core cycle as possible. SMT was invented to keep those execution units busy by running more than one instruction stream at a time. The incentive to do it when most computers have two SMT2 cores is small, but as the average device starts getting 4 or 8 SMT2 cores, or 8 asymmetric cores, the incentives to make things run faster in parallel get better and better.

chmod775 6y ago

> We know that an optimal optimization, i.e. finding the fastest way a program can be executed is known uncomputable. Not difficult, not brute forceable, but impossible to compute with traditional computers. I'm really curious about the proof of this, since there's only a finite number of ways you can re-arrange instructions in a program. Likewise there's only a finite number of ways you could shard them across threads. For this to be true you'd clearly need to phrase the problem in a way that allows you to have an infinite number of possibilities, then prove you can't arrive at the optimal solution through some means that doesn't involve checking an infinite number of them. (Edit: Or prove that it is impossible to decide on which one is the fastest at the time the optimizer runs. When does the optimizer run?). Was the assumption that you'd also be (infinitely) unrolling loops or maybe 'rewriting' the program into something equivalent but faster? What does "finding the fastest way a program can be executed" mean? Just re-ordering instructions and distributing them across threads, or something more?

Denzel 6y ago
Finding the optimal execution time of an arbitrary program is equivalent to the halting problem. [1] If you narrow the “arbitrary” constraint to only include well-structured, analyzable, guaranteed-to-terminate programs, then you can at least start to approximate a solution. Finding the true optimal case, even under those conditions, would be computationally expensive. [1]: https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem
- chmod775 6y ago
  This wasn't about anything related to optimal execution time. That an optimizer needs to know whether the code it optimizes terminates (or how long it runs) would also need proof if you'd want to go that route. The assumptions and optimizations the optimizer is allowed to use and what kinds of programs we're talking about, and what even is considered an "optimal program" is also still unclear (Edit: I'm assuming lowest number of instructions executed serially?). Please do refer me to a paper. Please do not link me vaguely related Wikipedia articles.
  - vidarh 6y ago
    It's equivalent to the halting problem because there exists a set of problems for which for any input that optimiser creates the optimal solution for, there exists another input for which that problem is not optimal. The parallel to the halting problem is that with access to the output of the optimiser, you can always construct a problem where whatever the optimiser produces can be obstructed by producing an input that makes the optimised program non-optimal for the given input. A trivial example of such a program is a function that sorts it input and returns the sorted result, as no sort is optimal for all inputs.
    - chmod775 6y ago
      > It's equivalent to the halting problem because there exists a set of problems for which for any input that optimiser creates the optimal solution for, there exists another input for which that problem is not optimal. You're trying to prove that no optimal solution can exist, not that it's impossible to find one. Which is fine, because it's a stronger claim. But it heavily depends on your definition of optimal. If you define optimal as "lowest average number of instruction across all possible inputs", then there exist optimal sorting algorithms. If you define optimal as: "A solution is optimal only if for every possible input there exists no solution that requires a lower number of instructions.", then yes, there can be no optimal sorting algorithm. I would argue that in practice only the first definition is useful. Further, you're assuming that "optimizations" that replace an existing algorithm with an equivalent one are allowed. Which brings me back to one of my original questions: What optimizations was hvidgaard allowing to be me made when he claimed an optimal solution is incomputable.

oblio 6y ago

I know about "embarrassingly parallel" problems, and the thing is, they're only "embarrassingly parallel" to solve in math. When programming the level of friction is from annoying to high unbearable, depending on the programming language. It should be trivial to implement these solutions, as trivial as the sequential solutions. It's not. Until this is the case in mainstream programming languages, I doubt we'll have CPUs with 1000 cores in our smartphones or laptops. I mean, we'll have them but they'll be useless because 99% of software today is practically single-threaded. The reason multiple cores are good for laptops, for example, is because we're multi-tasking between multiple applications, not because those cores are frequently used by day-to-day apps. I'm talking about random small apps, not compute intensive ones that have to use multi-threading intensively (rendering, compiling, what have you, professional level software).

rbanffy 6y ago
> but they'll be useless because 99% of software today is practically single-threaded. I used to joke developers should get workstations with SPARC Niagaras or Xeon Phis for that reason: core count is going up and a CPU with a dozen small cores is much cheaper to build than one with 4 beefy ones. Now some of the low-end chips Intel is pushing have 4 SMT2 cores. HEDT is on the 16 SMT2 core range and, if our software continues to be single threaded, there will be a lot of silicon being used for nothing more than spreading heat.
- colejohnson66 6y ago
  Isn’t the point of high core counts for workloads that can actually be parallelized? Like compilation or graphics rendering?
  - rbanffy 6y ago
    A lot of tasks can be parallelized if you think hard enough. Your CPU is busy reordering instructions so they keep as many execution ports busy as it can so that it can retire as many instructions per core cycle as possible. SMT was invented to keep those execution units busy by running more than one instruction stream at a time. The incentive to do it when most computers have two SMT2 cores is small, but as the average device starts getting 4 or 8 SMT2 cores, or 8 asymmetric cores, the incentives to make things run faster in parallel get better and better.