3 ms·

Compilers and More: Is Amdahl's Law Still Relevant?

26 points by matt_d 12y ago

scott_s 12y ago
I find the author's insistence on his thesis - that we must retire Ahmdal's Law - very strange. I don't even think of Ahmdal's Law as being necessarily about parallelism; it's also useful when reasoning about improving the performance of a sequential program. The reason I find his insistence strange is that the rest of the article is a good explanation of what has changed in the decades since Ahmdal published his paper. But I disagree that all of those matters change the fundamental lesson: your ability to improve overall performance will be limited by the parts that you are unable to improve.
- taeric 12y ago
  Agreed, this feels like arguing for the abolishment of Big-O notation, because it doesn't address constant factors. This is, of course, true. But largely not the point of the notation or the law? If anything, it seems that the lessons need further underlining so that their actual uses are understood.
marktangotango 12y ago
A review of concurrency vs parallelism[1] maybe useful when reviewing this link. [1] http://joearms.github.io/2013/04/05/concurrent-and-parallel-programming.html http://joearms.github.io/2013/04/05/concurrent-and-parallel-...
- scott_s 12y ago
  That's good, but does not quite capture the relationship in how I define it. From what I have said several times on HN now: Concurrency is a statement about a duration of time. Parallelism is a statement about a moment in time. During a one second window, did both of the tasks execute? If yes, then they are concurrent. If no, then they are not concurrent in that window. Was there any moment in time when both tasks were executing simultaneously? If yes, then they executed in parallel. If no, then they did not execute in parallel. From this, it's easy to see that if something is parallel, it must also be concurrent - in order for two tasks to execute during the same moment in time, they must also both have executed during a window of time. Concurrency without parallelism happens on machines with a single core. Processes and threads must time-share the only core. Frequently, some of these processes will have multiple threads, so the threads need to synchronize with each other, even though they don't execute at the same time.
  - 14113 12y ago
    I don't think either definition really defines what concurrency and parallelism are really. Concurrency is the study of how processes interact (i.e. communication, locking etc) while parallelism is studying how to physically perform more things at once. In this way, concurrency and parallelism (almost) form two axes within which you can judge programs: You can have highly concurrent, but serial program (e.g. a browser, with different threads for networking, UI, etc), and highly parallel, but non-concurrent (or with little concurrency), like image processing, or other "embarrassingly parallel" problems.
    - scott_s 12y ago
      What you call concurrency, I call concurrency control. But more often, I just call it synchronization. I am unaware of any widespread acceptance of your definition.
      - 14113 12y ago
        I hate doing this, but both the wikipedia articles for concurrency and parallelism agree with me: Concurrency > In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other. Parallelism > Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently ("in parallel"). In my opinion there's really not that much more to concurrency that's hard, apart from safely organising the communication between concurrent processes/threads. It's then the opposite problem with parallelism; the difficulty is finding and implementing the physically separate execution of different threads of execution in a program, while (generally) the communication is seen as a concurrency problem.
        scott_s 12y ago
        I don't think that definition of concurrency agrees with either of us. You defined concurrency as interaction itself, while Wikipedia defines it in terms of time and execution. I would agree with the Wikipedia definition if it changed "simultaneously" with "concurrently".
varelse 12y ago
Pretty much any GPU workload will quickly collide with Amdahl's Law w/r to spreading the work across multiple GPUs in short order. That's because 13 GB/s interconnect (P2P transfers) can only take one so far w/r to a problem that is O(n log n) or less unless the constant factor is huge. And that's why NVIDIA itself is now developing its own internal networking protocol: http://blogs.nvidia.com/blog/2014/11/14/what-is-nvlink/ http://blogs.nvidia.com/blog/2014/11/14/what-is-nvlink/ As a concrete example, it's why in his NIPS 2014 talk, Jeffrey Dean goes on and on and on about the different ways to parallelize the different sorts of layers of a deep neural network across multiple processors because the convolution layers are O(n^2)ish* (a convolution across ~n examples and ~n feature detectors) and and the fully connected layers are O(n^3)ish* (a matrix matrix product)... And that's just one problem domain. There are many more... *Totally abusing the terminology

26 points by matt_d 12y ago

I find the author's insistence on his thesis - that we must retire Ahmdal's Law - very strange. I don't even think of Ahmdal's Law as being necessarily about parallelism; it's also useful when reasoning about improving the performance of a sequential program. The reason I find his insistence strange is that the rest of the article is a good explanation of what has changed in the decades since Ahmdal published his paper. But I disagree that all of those matters change the fundamental lesson: your ability to improve overall performance will be limited by the parts that you are unable to improve.

taeric 12y ago
Agreed, this feels like arguing for the abolishment of Big-O notation, because it doesn't address constant factors. This is, of course, true. But largely not the point of the notation or the law? If anything, it seems that the lessons need further underlining so that their actual uses are understood.

marktangotango 12y ago

A review of concurrency vs parallelism[1] maybe useful when reviewing this link. [1] http://joearms.github.io/2013/04/05/concurrent-and-parallel-programming.html http://joearms.github.io/2013/04/05/concurrent-and-parallel-...

scott_s 12y ago
That's good, but does not quite capture the relationship in how I define it. From what I have said several times on HN now: Concurrency is a statement about a duration of time. Parallelism is a statement about a moment in time. During a one second window, did both of the tasks execute? If yes, then they are concurrent. If no, then they are not concurrent in that window. Was there any moment in time when both tasks were executing simultaneously? If yes, then they executed in parallel. If no, then they did not execute in parallel. From this, it's easy to see that if something is parallel, it must also be concurrent - in order for two tasks to execute during the same moment in time, they must also both have executed during a window of time. Concurrency without parallelism happens on machines with a single core. Processes and threads must time-share the only core. Frequently, some of these processes will have multiple threads, so the threads need to synchronize with each other, even though they don't execute at the same time.
- 14113 12y ago
  I don't think either definition really defines what concurrency and parallelism are really. Concurrency is the study of how processes interact (i.e. communication, locking etc) while parallelism is studying how to physically perform more things at once. In this way, concurrency and parallelism (almost) form two axes within which you can judge programs: You can have highly concurrent, but serial program (e.g. a browser, with different threads for networking, UI, etc), and highly parallel, but non-concurrent (or with little concurrency), like image processing, or other "embarrassingly parallel" problems.
  - scott_s 12y ago
    What you call concurrency, I call concurrency control. But more often, I just call it synchronization. I am unaware of any widespread acceptance of your definition.
    - 14113 12y ago
      I hate doing this, but both the wikipedia articles for concurrency and parallelism agree with me: Concurrency > In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other. Parallelism > Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently ("in parallel"). In my opinion there's really not that much more to concurrency that's hard, apart from safely organising the communication between concurrent processes/threads. It's then the opposite problem with parallelism; the difficulty is finding and implementing the physically separate execution of different threads of execution in a program, while (generally) the communication is seen as a concurrency problem.
      - scott_s 12y ago
        I don't think that definition of concurrency agrees with either of us. You defined concurrency as interaction itself, while Wikipedia defines it in terms of time and execution. I would agree with the Wikipedia definition if it changed "simultaneously" with "concurrently".

varelse 12y ago

Pretty much any GPU workload will quickly collide with Amdahl's Law w/r to spreading the work across multiple GPUs in short order. That's because 13 GB/s interconnect (P2P transfers) can only take one so far w/r to a problem that is O(n log n) or less unless the constant factor is huge. And that's why NVIDIA itself is now developing its own internal networking protocol: http://blogs.nvidia.com/blog/2014/11/14/what-is-nvlink/ http://blogs.nvidia.com/blog/2014/11/14/what-is-nvlink/ As a concrete example, it's why in his NIPS 2014 talk, Jeffrey Dean goes on and on and on about the different ways to parallelize the different sorts of layers of a deep neural network across multiple processors because the convolution layers are O(n^2)ish* (a convolution across ~n examples and ~n feature detectors) and and the fully connected layers are O(n^3)ish* (a matrix matrix product)... And that's just one problem domain. There are many more... *Totally abusing the terminology