The problem with static data flow schedules

June 6, 2007

This post is just a quick note. I’ll extend on it later.

Imagine you have a data flow graph with nodes A, B, C, D, G. Of these nodes, A and B are a source of stream and G is a sink. Now, say, the static scheduler gives you this iterative list of firings: B, A, C, B, A, G, B, D, D, G, D, A, G, C, B, G

Now, your application is real-time and, as usually, it is call-back based (the hardware awakes a process in a regular basis providing and consuming data).

Data flow scheduling is very interesting so far, but a question arises: In practice how can you use this scheduling from the call-back process?

Actually the obvious solution I can think is not good at all: you can do call-back adaptation of a blocking interface. That implies leaving the call-back process to just do buffering, and have another thread that executes the data-flow. Where source and sink nodes (A, B and G) can be blocking if data is not available. But in most cases minimize buffers on the inputs and ouputs is desired. So you want the scheduler that collects input as regularly as possible. This is an admitted (SDF scheduling paper, section V.C) limitation of the model.

I haven’t found yet any research focusing on that problem (though I admit I still have a bunch of related papers to read). So any feedback on this will be greatly appreciated. However, I have some ideas on how the solution could be, I’ll post about it later.

Advertisements

3 Responses to “The problem with static data flow schedules”

  1. xamat Says:

    I think the trick here is to realize that when you are in a callback situation you no longer have an SDF. You should have a look at the more general model of KPN’s (Kahn Process Networks).

    A fairly recent article I’d recommend (actually Eric Lee recommeded it to me):

    http://citeseer.ist.psu.edu/geilen03requirements.html

  2. parumi Says:

    Exactly from a callback point of view you don’t have a SDF. However, at the long term, the activation list needs to be balanced and iterative, so the mathematical constructs they do to obtain the static scheduling gave me an idea of how to reuse it to obtain a series of callback activation list. I’ll write it down in short.

    Thanks for the link :-) Will read it today.

  3. Idetrorce Says:

    very interesting, but I don’t agree with you
    Idetrorce


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: