Jump to content
Matthias Jung

Kahn Process Networks (KPN) with SystemC

Recommended Posts

Hey,

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
Matthias

 

Share this post


Link to post
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,
  Philipp

Share this post


Link to post
Share on other sites

Dear Philipp,

Quote

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.

 

Regards
Matthias

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×