Programming Multicore and Many-core Computing Systems (Wiley Series on Parallel and Distributed Computing) by Sabri Pllana & Fatos Xhafa

Author:Sabri Pllana & Fatos Xhafa
Language: eng
Format: mobi, azw3, pdf
ISBN: 9781119332008
Publisher: Wiley
Published: 2017-01-22T23:00:00+00:00

11.3 CONCURRENT CODE

The keyword for further parallelization, in particular of common work tasks that do not adhere to the typical parallel patterns mentioned earlier, is therefore ‘concurrency’. It also determines whether a loop or a pattern can be effectively executed in parallel in the first instance.

Concurrency in this specific context reflects the dependencies of a given code segment or function on other functions or parts of the code. The higher the degree of concurrency, that is, the less dependencies exist, the more effective is its parallel execution and the less likely delays occur due to synchronization overhead. In the ideal case, such as in embarrassingly parallel tasks, the concurrency reaches a maximum that implies that there are virtually no dependencies between the processes.

Obviously, a high degree of concurrency does not necessarily imply that the according segment can be executed in full parallel. A single shared variable can stall the full execution, if the seemingly concurrent code has to wait for the first thread to finish its calculation before the variable is free for access. At the same time, this obviously depends on the read–write order of the respective segments. Accordingly, and as discussed in more detail later, it is difficult to automatically identify concurrency in a given code efficiently. More realistic approaches, such as the Star Superscalar programming model, [7] therefore require the developer to explicitly annotate data dependencies across their code and functions. This information can then be exploited by the compiler to generate a dependency graph which provides implicit information about the execution order and potential points for parallelization and task distribution.

Star Superscalar is thereby still very coarse granular and expects specific function calls to exhibit concurrency rather than, for example, direct workload in a loop. It furthermore does not assess the execution speed of individual function blocks so that resources may not be used to their full optimum – nonetheless the model provides an easy method to increase the overall execution performance.

Essentially, even classical parallelization measurements base on the principle of maximizing concurrency between threads, so as to minimize dependencies and thus communication and synchronization overhead. Concurrency identification can therefore be regarded as the key factor in (semi-)automated parallelization and in addressing the requirements for future programming models. As indicated, however, concurrency cannot be reliably identified automatically.

11.3.1 Concurrency Analysis and Exploitation

There is an extensive literature on automated parallelization which deals with multiple aspects of concurrency analysis in order to identify dependencies. In general, the stronger such a dependency, the less parallelizable the according function. However this furthermore depends on the sequence of read–write statements in the code and on frequency of such occurrences. As a rule of thumb, the gain achieved through the concurrent execution must be higher than the loss introduced this way. While this may sound trivial, it has multiple implications.

The major performance loss occurs by latency introduced through any delays – the most obvious are (i) waiting for data to become available and (ii) passing it to the respective thread and returning results. Similarly, additional delay arises through access to shared-memory spaces.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.