Kahn Process Networks (KPN) with SystemC

[Matthias Jung]

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:

• Page 63: http://www.edaplayground.com/x/6Mfi
• Page 42: http://www.edaplayground.com/x/4jLZ

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

 

[Philipp A Hartmann]

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

[Matthias Jung]

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

[Matthias Jung]

I found a solution: https://github.com/tukl-msd/SCVP.artifacts/tree/master/kpn_artificial_deadlock

Indeed it depends on the way how SystemC schedules the processes.

Note that it may behave differently w.r.t. scheduling and therefore also w.r.t. FIFO sizes If you call wait(SC_ZERO_TIME) in between.

[Markus Damm]

On 11/5/2017 at 9:47 AM, Philipp A Hartmann said:

Hi Matthias,

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

Phil,

maybe you confuse this with SDF.

 

Regards,

Markus