Jump to content

Kahn Process Networks (KPN) with SystemC

Matthias Jung

Recommended Posts


Kahn Process Networks are defined by the usage of unbounded FIFOs with blocking reads and non-blocking writes.
I read on several sources that KPN with bounded FIFO size (i.e. blocking read and blocking write) can be implemented with SystemC (e.g. Grötker et al).

It seams that the event based scheduler in SystemC behaves different like data-driven scheduler or a demand-driven for KPNs.
I simulated the networks of Park's Dissertation shown on page 36 and 42 which should end up in an artificial deadlock (deadlock which occurs because of blocking write).

A global artificial deadlock in SystemC would result in no scheduled events, and therefore, the simulation should be stopped.

However, even with buffer size 1 for all FIFOs both examples from Park are continuing with execution:

Note that edaplayground exits because of to much output. If you want to test it you better download it and run it on your PC.

Apparently, the SystemC scheduler finds automatically a schedule for the KPN such that no artificial deadlocks occur.
My question: is there an example where I could also see an artificial deadlock in SystemC?

Thanks and Regards


Link to comment
Share on other sites

Hi Matthias,

IIRC, KPNs require that inputs are available on all incoming connections for an actor to fire.  In your model, you already consume tokens from some inputs while being then blocked at others.  This can be the reason that you don't see the deadlock in your model.  But of course, you can also have deadlocks under this approach.  Maybe you can trigger it by just switching the order of some of the read statements in your multi-input actors.

As a general solution, you need to use a similar pattern as recently discussed in the following thread:


Here's an example for one of your processes:

void kpn::p7() // merge
  static const int f7_n = 1; // number of tokens needed from each input
  static const int f8_n = 1;
  while( true )
    while( f7.num_available() < f7_n || f8.num_available() < f8_n ) {
      // at least one side is blocking, wait for activity on either side
      wait( f7.data_written_event() | f8.data_read_event() );
    // forwarding possible, process tokens - will not block on inputs
    unsigned int u = f7.read();
    unsigned int v = f8.read();
    // ...
    // may still block out outputs


Greetings from Duisburg,

Link to comment
Share on other sites

Dear Philipp,


IIRC, KPNs require that inputs are available on all incoming connections for an actor to fire. 

That is unfortunately not the case :( . When a process reads from a queue, the read is blocking. If the queue is empty, then the process will suspend until there is enough data in the queue. This allows even data dependent control flow or control flow depending on internal variables:

process f(in int u, in int v, out int w) {
    int i; bool b = true;
    while (true) {
        i = b ? wait(u) : wait(w);
        printf("%i\n", i);
        send(i, w);
        b = !b;

This is an example form Kahn's original paper in a C syntax. Alternately u and v is read. So it is not necessary that all incoming connections are required to fire the process.

When a process blocks, the scheduler will not unblock the process until enough data becomes available on the blocking input port. Writes to the queues are non-blocking because the queue size is infinite. 

For the example that you show, you peek into the FIFOs which is not allowed for KPNs actually.



Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Create New...