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