The problem with static data flow schedules

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.

About these ads