Kpn4free: A generator for random Kahn Process Network applications

The parallel programming model of Kahn Process Networks (KPNs) has been introduced in our previous blog post. In certain situations, a high number of different KPN applications are needed, for example when testing software tools that work with these types of applications. Therefore it would be very useful to have a generator of synthetic KPN applications.

KPN For free graphic.cut-kpn4free-generator-random-kahn-process-network-applications

Random generation of KPN applications that show non-regular communication patterns is not a straightforward process. This is partly due to the blocking of the first-in first-out (FIFO) channels. It is not sufficient to create a set of processes, connect them with some channels and then randomly read and write the connected channels in each process. Reading might lead to structural deadlocks when a channel is empty and never written. Further, writing to a channel without the other side reading will lead to unbounded memory consumption.

In order to solve the problem of generating code for non-regular communication over FIFO channels, kpn4free uses a trick. First, it generates a set of processes and some channels for connecting those in a straight-forward way. The generation of communication does not happen independently for each process. Instead, it is based on channels. For each channel, a pseudo-random number generator (PRNG) determines the points in time when to write tokens to the channel and when to read tokens from it. A copy of the same PRNG can be run in both the writer and the reader process, so the writes and reads will always work out.

Applying this principle to all channels of the synthetic process network ensures that there will never be a deadlock or a channel with unlimited memory consumption.

For more details, please check out the open-source implementation of kpn4free:

https://github.com/Silexica/kpn4free/

Here you can get a “test.sh” script that shows how to generate a random KPN application including the graph and the source code for SLX. It outputs the KPN graph in postscript and PDF format. Further, it creates a Silexica CPN application. In case the Silexica environment is loaded, the application is also executed on the host.

 

For more information on SLX or for a free trial of SLX click here

Ebene 1-440
STEFAN SCHUERMANS
Stefan is a computer scientist who has been working with compilers and embedded systems for almost two decades. Since the introduction of embedded multicore systems, he works to solve complex challenges by leveraging the potential of parallel execution.
He received a computer science diploma from RWTH Aachen University in 2005 and then worked as a software developer and consultant for three years. He then joined the Institute for Communication Technologies and Embedded Systems at RWTH Aachen University as a full-time research assistant and doctoral student. Stefan joined Silexica in January 2016 and is responsible for the architecture of SLX.

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です