7 ms·

I think we would just have run into Amdahl's Law earlier. http://en.wikipedia.org/wiki/Amdahl%27s_law http://en.wikipedia.org/wiki/Amdahl%27s_law . Basically

by tezza 15y ago

I think we would just have run into Amdahl's Law earlier. http://en.wikipedia.org/wiki/Amdahl%27s_law http://en.wikipedia.org/wiki/Amdahl%27s_law . Basically you don't get a free pass for parallelising things. . If 90% of a task is parallelizable then the maximum speedup you can get with infinite cores is 10x

larsberg 15y ago
Indeed, we see this today with our compiler (Manticore). On our 48-core AMD and 30-core Intel boxes, we now routinely have flattening speedup curves due to the small sequential portions of even our supposedly "embarrasingly parallel" benchmarks. Compilers, even icc, are still shockingly bad at making good use of the x86_64 instruction set for sequential code. Part of that, of course, is due to C. But part of it is also our (my) fault as compiler writers because even with fantastic type information and unambiguous language semantics we emit shockingly dumb code.
- jules 15y ago
  Can you elaborate on x86_64 code generation? (are you referring specifically to the vector instructions?) What do you think are the most promising directions to improve in this area?
  - larsberg 15y ago
    Yes, certainly the vector instructions. There are a few keys issues many C compilers seem to run into today: - Loop unroll identification is really bad. For example, ICC will unroll and turn a single-level loop with a very obvious body into streaming stores if the increment is "i++" but not if it is the constant "i+=1". - The register allocation problem has some subtelties. Many of the SSE registers overlap the name of the multiple packed-value register with those of the individual ones (e.g. "AX = lower 16 of EAX"), so knowing that you want four numbers to be in the right place without additional moves means a little bit more thinking. But, there's also very little control-flow analysis done or global program analysis done except for some basic link-time code generation and profile-guided optimization. There's a lot you can do (e.g. cross-module inlining; monomorphizing to remove uniform representation; dramatic representation changes of datatypes), though admittedly some of it requires a more static language with some additional semantic guarantees.
jacquesm 15y ago
You're right, there is no free pass. Let me give you one example of how the wrong habits have become embedded in how we think about programming because of the serial nature of former (and most current) architectures: One of the most elementary constructs that we use is the loop. Add four numbers: set some variable to 0, add in the first, the second, the third and finally the fourth. Return the value to the caller. The example is short because otherwise it would be large, repetitive text. But you can imagine easily what it would look like if you had to add 100 numbers in this way, and 'adding numbers' is just a very dumb stand-in for a more complicated reduce operation. That 'section' could be called critical and you'd be stuck at not being able to optimize that any further. But on a parallel architecture that worked seamlessly with some programming language what could be happening under the hood is (first+second) added to (third+fourth). You can expand that to any length list and the time taken would be less than what you'd expect based on the trivial sequential example. Right now you'd have to code that up manually, and you'd have to start two 'threads' or some other high level parallel construct in order to get the work done. As far as I know there is no hardware, compiler, operating system or other architectural component that you could use to parallelize at this level. The bottle-neck is the overhead of setting things up , which should be negligible with respect to the work done. So parallelism would have to be built in to the fabric of the underlying hardware with extremely low overhead from the language/programmers point of view in order to be able to use it in situations like the one sketched above. Those non-parallelizable(sp?) segments might end up a lot shorter once you're able to invoke parallel constructs at that lower level.
- tezza 15y ago
  I'm not poo-pooing improving the ability get 10x speedups... that'd be awesome in many contexts. Rather I think a lot of even "embarrassingly parallel" problems have lots of micro-sequential code within. With your example there are mico-sequential portions for allocating the processors for the split addition to run on, and then the sequential bit of adding the resultants back together again.
  - jacquesm 15y ago
    Those micro-sequential portions are right now lumped into one huge 'can't fix', to be able to exploit parallism at that level would make huge speedups possible. After all, Amdahl's law is 'bad' when you're looking at a 20% segment that you can't improve, but as you get closer to 100% the pay-offs of even small optimizations becomes larger and larger.
tomjen3 15y ago
Well that law is a good theoretical instrument. But aside from some computations which have been deliberately designed to be impossible to parallize, it seems to me that Amdahls assumes that there is some constant part of the program that just can't be parallized. I disagree with that, and I think Erlang offers the best counterargument-- just because some part has to be done on one node (or thread) doesn't mean that the computer can't do other work at the same time. Sure if your mental model of computation is do this, then that, and then do these two things in parrallel and then do these other things in parallel then gather all the results, this would suggest you have a problem under Amdahls law. If your mental model is a set of independent nodes sending messages to each other then when you run into a bottleneck, you spawn a few more of the most commonly used nodes. Suddenly there is no part of the program which has to be run sequentially while the rest of the world waits.
- anamax 15y ago
  No, this isn't a counter-argument. You're not speeding up a given instance, you're "merely" running more instances or running larger problems. (In some problems, the sequential portion is roughly constant, independent of the amount of data. So, you can reduce the effect of the sequential portion by increasing the amount of data.) More throughput and larger data are both good things but they're not the same as running a given problem faster.
comicjk 15y ago
Yes, but "90% of a task" is very different from "90% of the code." The parallel parts tend to be the tight loops, etc where the program spends most of its time, which means for some tasks a number quite close to 100% of the runtime is parallelizable.

by tezza 15y ago

larsberg 15y ago

Indeed, we see this today with our compiler (Manticore). On our 48-core AMD and 30-core Intel boxes, we now routinely have flattening speedup curves due to the small sequential portions of even our supposedly "embarrasingly parallel" benchmarks. Compilers, even icc, are still shockingly bad at making good use of the x86_64 instruction set for sequential code. Part of that, of course, is due to C. But part of it is also our (my) fault as compiler writers because even with fantastic type information and unambiguous language semantics we emit shockingly dumb code.

jules 15y ago
Can you elaborate on x86_64 code generation? (are you referring specifically to the vector instructions?) What do you think are the most promising directions to improve in this area?
- larsberg 15y ago
  Yes, certainly the vector instructions. There are a few keys issues many C compilers seem to run into today: - Loop unroll identification is really bad. For example, ICC will unroll and turn a single-level loop with a very obvious body into streaming stores if the increment is "i++" but not if it is the constant "i+=1". - The register allocation problem has some subtelties. Many of the SSE registers overlap the name of the multiple packed-value register with those of the individual ones (e.g. "AX = lower 16 of EAX"), so knowing that you want four numbers to be in the right place without additional moves means a little bit more thinking. But, there's also very little control-flow analysis done or global program analysis done except for some basic link-time code generation and profile-guided optimization. There's a lot you can do (e.g. cross-module inlining; monomorphizing to remove uniform representation; dramatic representation changes of datatypes), though admittedly some of it requires a more static language with some additional semantic guarantees.

jacquesm 15y ago

You're right, there is no free pass. Let me give you one example of how the wrong habits have become embedded in how we think about programming because of the serial nature of former (and most current) architectures: One of the most elementary constructs that we use is the loop. Add four numbers: set some variable to 0, add in the first, the second, the third and finally the fourth. Return the value to the caller. The example is short because otherwise it would be large, repetitive text. But you can imagine easily what it would look like if you had to add 100 numbers in this way, and 'adding numbers' is just a very dumb stand-in for a more complicated reduce operation. That 'section' could be called critical and you'd be stuck at not being able to optimize that any further. But on a parallel architecture that worked seamlessly with some programming language what could be happening under the hood is (first+second) added to (third+fourth). You can expand that to any length list and the time taken would be less than what you'd expect based on the trivial sequential example. Right now you'd have to code that up manually, and you'd have to start two 'threads' or some other high level parallel construct in order to get the work done. As far as I know there is no hardware, compiler, operating system or other architectural component that you could use to parallelize at this level. The bottle-neck is the overhead of setting things up , which should be negligible with respect to the work done. So parallelism would have to be built in to the fabric of the underlying hardware with extremely low overhead from the language/programmers point of view in order to be able to use it in situations like the one sketched above. Those non-parallelizable(sp?) segments might end up a lot shorter once you're able to invoke parallel constructs at that lower level.

tezza 15y ago
I'm not poo-pooing improving the ability get 10x speedups... that'd be awesome in many contexts. Rather I think a lot of even "embarrassingly parallel" problems have lots of micro-sequential code within. With your example there are mico-sequential portions for allocating the processors for the split addition to run on, and then the sequential bit of adding the resultants back together again.
- jacquesm 15y ago
  Those micro-sequential portions are right now lumped into one huge 'can't fix', to be able to exploit parallism at that level would make huge speedups possible. After all, Amdahl's law is 'bad' when you're looking at a 20% segment that you can't improve, but as you get closer to 100% the pay-offs of even small optimizations becomes larger and larger.

tomjen3 15y ago

Well that law is a good theoretical instrument. But aside from some computations which have been deliberately designed to be impossible to parallize, it seems to me that Amdahls assumes that there is some constant part of the program that just can't be parallized. I disagree with that, and I think Erlang offers the best counterargument-- just because some part has to be done on one node (or thread) doesn't mean that the computer can't do other work at the same time. Sure if your mental model of computation is do this, then that, and then do these two things in parrallel and then do these other things in parallel then gather all the results, this would suggest you have a problem under Amdahls law. If your mental model is a set of independent nodes sending messages to each other then when you run into a bottleneck, you spawn a few more of the most commonly used nodes. Suddenly there is no part of the program which has to be run sequentially while the rest of the world waits.

anamax 15y ago
No, this isn't a counter-argument. You're not speeding up a given instance, you're "merely" running more instances or running larger problems. (In some problems, the sequential portion is roughly constant, independent of the amount of data. So, you can reduce the effect of the sequential portion by increasing the amount of data.) More throughput and larger data are both good things but they're not the same as running a given problem faster.

comicjk 15y ago

Yes, but "90% of a task" is very different from "90% of the code." The parallel parts tend to be the tight loops, etc where the program spends most of its time, which means for some tasks a number quite close to 100% of the runtime is parallelizable.