Compilers and More: Is Amdahl's Law Still Relevant? | Hacker News Reader

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

hpcwire.com

26 pointsmatt_d17 comments

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.

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.

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/

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

A review of concurrency vs parallelism[1] maybe useful when reviewing this link.

[1] http://joearms.github.io/2013/04/05/concurrent-and-parallel-...

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.

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.

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.

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.

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

Hmm, that's a fair point. Thinking about it a bit more, I think my definitions fit closer with the idea of concurrent or parallel programs rather than the abstract ideas of concurrency or parallelism themselves.

In any case, I completely disagree with your idea that parallel systems must be concurrent. Concurrency arises completely due to the interactions between separate threads of execution, whether they be executing at the same time on separate processors, or scheduled one after the other on a single processor. This is why we have various process calculii (csp, pi-calculus etc), and things such as session types, in order to try and reason about it and manage it. Parallelism assumes nothing about the interactions between processes, only that they are assumed to be running on separate hardware.

As another poster mentioned, this fits fairly well with what the Haskell, Go, and general programming language research community considers to be the definitions of concurrency and parallelism. Look at any paper that focusses on concurrency, and you'll see it's about managing and making safe communication between separate processes. Look at a paper on parallelism, and it'll be on accelerating a parallelisable program on multicore or distributed hardware.

As someone who works in parallel and distributed systems (which means I write and read papers on parallelism), I find your distinction an empty one. Actually getting good performance from parallelism requires careful consideration of the synchronization between the parallel parts - and in my work, the "careful consideration" is usually done by me. My goal is often to make abstractions so that users don't have to implement or even reason about such synchronization themselves, but it's still a central part of the work.

I also disagree with your assertion that the programming language research community disagrees with my definitions - I'm more of a systems person, but I do end up in their playground sometimes.

The Go and Haskell language communities have been pushing those definitions. For the most part they seem to be winning as those definitions are trotted out every time the subject comes up.

https://www.haskell.org/haskellwiki/Parallelism_vs._Concurre...

http://blog.golang.org/concurrency-is-not-parallelism

Any attempts to hijack common words for specific meaning in programming will abound with problems. I find it hardly surprising that many people view parrallelism as concurrently executing similar operations. The key being "similar operations." That actually fits with common uses of the words everywhere else.

Consider, what does it mean to run parallel with something else? Means you are running a similar path. Not even necessarily at the same time. What does it mean to run concurrently with something else? Simply that you are running when it is.

I agree it is odd to say that something is running concurrently but with out concurrency. The problem is threads and locks and what not are well known as concurrency primitives, programming with them known as concurrent programming, etc. So what do we call concurrent programming that doesn't make use of any of the concurrency primitives, concurrent programming techniques? We want to call it something but we don't want to co-opt current nomenclature. Parallel isn't "taken" and does an OK job of expressing what they are doing.

I would have thought something like "independent" or "n-agent" would have caught on. Though, I'm fine with some ambiguity, to be honest. And I am not at all "in the field."

My point is really that it is a lost cause to try and use such an outside common word to have a specific meaning.

I consider it parallelism without concurrency, if tasks are executed at the same time, but do not interact / synchronize. A parallel map operation (without reduce) would an example.

The important thing is: Concurrency introduces indeterminism, while parallelism does not.

Even a parallel map operation must have some synchronization in the beginning and end. The code you write may not, but the parallel framework that you rely on does.

Reply on news.ycombinator.com