Thinking concurrently

Overview

Recall questions on concurrency and parallelism, identifying tasks that can run at once, parallel image filters and merge sort, Amdahl's law, overheads and contention, race conditions, deadlock, testing concurrent code, and data and task parallelism.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What does thinking concurrently mean, and how does concurrency differ from parallelism?

   Model answer

   Thinking concurrently means identifying the parts of a problem that do not have to wait for each other, so that they can be dealt with in overlapping time rather than strictly one after another. It is a way of analysing the structure of the problem, and it applies whether or not the hardware can actually run two things at the same instant. Concurrency is about structure: several tasks are in progress over the same period, and a single processor can achieve this by switching rapidly between them, so that while one task waits for a disk or a network the processor works on another. Parallelism is about execution: two or more tasks genuinely execute at the same instant, which requires multiple processors or cores. The distinction matters practically. A program can be concurrent and get a large speedup on one core, if its tasks spend most of their time waiting rather than computing, which is why a web browser fetching thirty resources over one connection benefits enormously from concurrency. Equally, a program can be run in parallel and get no benefit if its work is not divisible. Answers that treat the two as synonyms miss the fact that the reason for overlapping work is sometimes to use idle waiting time and sometimes to use idle hardware.

2. 2

   How do you work out which parts of a problem can be tackled at the same time?

   Model answer

   By looking for the absence of dependencies. Two tasks can proceed simultaneously if neither needs a result the other produces, neither needs a state the other establishes, and they do not both write to the same data, or one write and the other read it, in a way where the outcome would depend on which happened first. Practically, the method is to list the tasks, draw an arrow from each task to every task that depends on it, and then look at the resulting diagram: tasks with no arrow between them in either direction are candidates for concurrency, and the longest chain of arrows gives the shortest possible completion time no matter how many workers you have. Then check for shared resources that the dependency list does not show, because two tasks that need the same printer, the same file, the same lock or the same limited network bandwidth are not truly independent even though neither uses the other's output. A useful sanity check is to ask whether the result would be the same if the tasks ran in either order or overlapped in any way; if the answer depends on the timing, they are not independent and will need synchronising.

3. 3

   Applying a blur filter to a large photograph is a standard example of a task that parallelises well. Explain why, and identify the one complication.

   Model answer

   Because the calculation for each output pixel depends only on the input pixel and its neighbours, and not on any other output pixel. The image can therefore be divided into strips or tiles and each region assigned to a different core, with every core reading from the same unchanged input image and writing to a separate region of the output. There is no ordering requirement between regions, no communication needed between the workers while they run, and the work per region is easy to make roughly equal, which is what keeps all the cores busy. This pattern, where the same operation is applied independently to many elements of a dataset, is called data parallelism, and it is why image processing, video encoding and much of machine learning run so well on graphics processors, which have very many simple cores. The complication is at the boundaries: a pixel near the edge of a tile needs neighbours that lie in the adjacent tile, so each worker must be able to read a margin of the input beyond its own region. That is manageable because the input is read-only, but if the filter were applied in place, overwriting the input as it went, workers would read neighbours that had already been modified by another worker and the result would depend on timing. Keeping the input and output separate is what makes the independence real.

4. 4

   Explain how a web server serving thousands of users at once benefits from concurrency, even on a machine with few cores.

   Model answer

   Because most of the time spent handling a request is spent waiting rather than computing. A typical request involves reading from disk, querying a database on another machine, perhaps calling an external service, and then sending bytes back over a network to a client that may be on a slow mobile connection. During all of that waiting the processor has nothing to do for that request. If the server handled requests strictly one at a time, the processor would sit idle for the great majority of every request and throughput would be dreadful. By keeping many requests in progress simultaneously, whether through threads or through an event loop with asynchronous input and output, the server switches to another request whenever one blocks, so the waiting overlaps and the processor stays busy. This is concurrency delivering a large gain with no parallelism at all. Two consequences follow. First, the limiting resource is usually not processor time but memory, connections and file handles, which is why servers cap the number of simultaneous connections. Second, because requests share resources such as a connection pool, a cache and session data, the server still needs the discipline of concurrent programming, and a bug in how two requests share one piece of state is a real fault even on a single core.

5. 5

   How can a merge sort be made to use several processor cores, and what limits the speedup?

   Model answer

   Merge sort divides the list into two halves, sorts each recursively and merges the sorted halves. The two recursive sorts are independent of each other, since neither reads the other's data, so they can be given to separate workers. With two cores the two halves are sorted at the same time; with four, each half is split again and the four quarters sorted simultaneously, and so on. What limits the speedup is the merging. The final merge combines two fully sorted halves into one list, it cannot begin until both halves are complete, and in its simple form it is sequential work proportional to the whole length of the list. So however many cores you add, the last merge still takes the time it takes, and it is preceded by a merge of quarters and so on, all of which are only partly parallel. There is also the cost of creating and coordinating the workers, which is why practical implementations sort small sublists sequentially, often switching to insertion sort below a threshold, rather than spawning a thread for every two elements. This example is the standard illustration of a general truth: the parts that cannot be divided set a floor on the running time, and they become the dominant cost as the parallel parts get faster.

6. 6

   State Amdahl's law and use it to work out a speedup.

   Model answer

   Amdahl's law says that the speedup available from parallelising a task is limited by the fraction of it that must remain sequential. If p is the proportion of the work that can be parallelised and N is the number of processors, the speedup is at most one divided by the quantity one minus p, plus p over N. Take a task of which eighty per cent can be parallelised, leaving twenty per cent sequential. On four processors the speedup is one divided by nought point two plus nought point eight over four, which is one divided by nought point four, or two and a half times. So four processors give two and a half times the performance, not four. Now let N grow without limit: the second term vanishes and the speedup approaches one divided by nought point two, which is five. No number of processors will ever make this task more than five times faster, and going from sixteen processors to a thousand moves the speedup from exactly four to just under five. Two lessons follow. First, adding hardware has sharply diminishing returns, and the money is often better spent reducing the sequential fraction. Second, the law is an upper bound that ignores overheads, so real speedups are lower than it predicts. It also assumes a fixed problem size; where a larger machine is used to solve a proportionately larger problem, the picture is more favourable, which is the point made by Gustafson.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.