System-Level Design
WHITEPAPERS

Kahn Process Network: Parallel Programming Without Races And Non-Determinism

How a 1974 parallel programming model may solve problems with the threading approach, including racing and non-determinism.

popularity

Modern personal computing devices feature multiple cores. This is not only true for desktops, laptops, tablets and smartphones, but also for small embedded devices like the Raspberry Pi. In order to exploit the computational power of those platforms, application programmers are forced to write their code in a parallel way. Most often, they use the threading approach. This means multiple parts of the code execute at the same time and have access to same set of shared data. However, parallel programming using threads is complicated and hard to debug. When a thread modifies data that might be read by other threads, the programer has to insert proper synchronization. Almost every programmer who has used threads has experienced data races and/or non-deterministic behavior. In such situations, the application might shows a bug or crashes, but once loaded into the debugger, it completes without problems. The reason for such effects is that the timing of thread execution can affect the computational behavior inside the threads. This means that if the timing changes, e.g. due to the OS scheduling the threads in a slightly different way, the threads might behave slightly differently — or in the worst case do something completely different.

The approach of Kahn Process Networks (KPNs) is a parallel programming method that also allows to harness the potential of multi-core systems. It has been invented by Gilles Kahn in 1974. (His original paper can be accessed at: http://www1.cs.columbia.edu/~sedwards/papers/kahn1974semantics.pdf) This programming model avoids the issues of data-races and non-determinism.

Click here to read more.



Leave a Reply


(Note: This name will be displayed publicly)