Real-time Dataflow Programming

Question

Background

Recently, I have been fascinated about the possibilities of dataflow-based programming approaches - in particular, signal/event-based concepts as realized by functional reactive programming, Boost::Dataflow::Signals, and the like.

Sample scenario:

Consider a car that has four speed sensors, one at each of its tires. Let's simplify things and say that these sensors are analog sensors providing the measured speed at that tire. The car further has individual brakes on the four tires (the actuators) that one can program to break more or less strongly.

There is no concrete task, but imagine having to realize things like detecting tires not turning due to aqua-planing, or ABS-support, or or or... In short: you have to evaluate the speed sensor data and control the actuators according to some logic.

From a programming point of view, one could think of realizing this via a signal-network of the following sort:

timer ------------\
sensor1/2/3/4 -> logic -> brakes1/2/3/4

(That is, the timer triggers the logic, which takes the latest analog values of the sensors)

Like this, the timer can be programmed to trigger in fixed intervals (especially important to ensure the real-time constraints).

The advantage of the dataflow-approach here is that the above diagram is directly realized in the code, i.e. you have a logical wiring of signals and just need to provide an implementation that turns your actual hardward sensor's data into a signal (of the corresponding library you are using).

When it comes to real-time requirements, the maximal signal path length can also be computed (or at least more easily derived from the source).

The question

Of course, all of this is just an application idea and I am sure several brilliant people have come up with this before. What I am looking for is the follow-up. Are there any hard problems with this scenario which make it unrealizable in practice? Are there experiences from real-world projects on following such a line of thought? Is there even existing literature on this?

To make things clearer and more objective, I am looking for an answer that either shows an inherent fault in my line of thinking or provides reference to existing work/literature along with evaluations. Bonus points if real-time constraints are taken into account.

Answer 1

This is an old idea, that has popped up an unbelievable number of times over the last several decades. LabView (I think that's the name) is the best-known current version.

I worked with one such system, called RIPPEN, from Orincon (as I recall), around 1998-1999. (Orincon was bought by Lockheed-Martin in 2003. The product appears to be dead and gone now.) The biggest drawback I noticed was that about 20% of my CPU time went to moving data around between processing blocks. Considering that I was doing significant numbercrunching (coordinate transformations, from az/el/range to X/Y/Z and then applying a coordinate system rotation: BUNCHES of trig and matrix/vector multiplication, 20% is a LOT of CPU time.

Around this time, I went to a function at my old university, and mentioned the product to an old friend, who was a grad student when I was there and is now a full professor. His answer was that he'd done a similar thing quite a number of years earlier.

Answer 2

I've seen this type of thing in Flight Simulation

I used to do hardware (specialty being electrical wiring and IO) but I have a basic understand of how the software architecture worked.

In such a system, there are a lot of complex components. For sensors, there are IO computers that handle all the hardware, calibration, networking components necessary to convert analog/digital signals to scalar values.

Basically, every input/output in the whole system can be described as a variable and the table of all possible values in the system lives in a global address space. In fact, on the really old simulators (80s) there's no such thing as dynamic memory allocation. Every time a new variable was assigned the whole system's software needed to be re-compiled.

To avoid that, the developers had built in a ton of spare variables that could simply be re-named, re-purposed if necessary.

The other major software component was the scheduler. The host computer was extremely slow by today's terms. To keep stimulus response latency numbers within standard limits (ie 33.3ms or 30hz max per frame on older gen hardware) they need to set prioritization levels for certain systems. If the latency for any of the sub-systems fell outside of the FAA specified minimum requirements, the simulator would lose its certification until it was fixed.

If I remember right the priorities were setup as:

1. Controls - Highest because control inputs need to be acted on as soon as possible
2. Visual - People respond quickest to visual feedback, if the delay is too long people notice
3. Instrumentation - Pilots spend a lot of time staring at instruments, they need to respond relatively fast
4. Motion - Motion is more subtle and slower to respond in real life so it has a lower priority

Believe it or not, you could fly a sim off of motion and it would still feel like your moving. When you're starting at a 150-180 degree projection on a curved mylar mirror, the visual will trick your mind into thinking that you're moving when you're sitting completely stationary. I have done wiring in the mirror compartment before; it's very important that you pause and gain your bearing while standing directly in front of one of those mirrors or it can throw you off balance sending you falling into the mirror (at the cost of 30K+ to fix). FYI, if you don't know what mylar is, it's the reflective material they make helium balloons with.

For the task scheduler, like I stated, each step is given priority and an iteration is based on a timed interval. The amount of processing that is done in an iteration depends on the inputs/outputs of that interval.

The subsystems each had their hardware. Visual Image Generator, Motion Control, Control Loading, I/O (had it's own network sub-system), the Host, and maybe an IOS (Instructor Operating System) which comprised of a touch screen interface to control the sim.

The way we'd measure input response on the different subsystems was based on hooking up a chart recorder and physically mapping the output response on the different signals. Nowadays, most of that stuff has been replaced by digital charts but (being only 27 now) it was fascinating to see the way things were done in the old days.

---

Like I said, my knowledge is limited to what I witnessed but as far as I can tell the system had a few important details.

1. All of the higher level memory abstractions (ex virtual memory, dynamic allocation) didn't exist on the real-time system.
2. Communications to/from the host were kept to the bare minimum possible. It was actually possible to upgrade the sub-systems as long as they were talking the same networking protocol.
3. A traditional Round Robin scheduler doesn't work because you need to be able to give priority to specific subsystems based on a fixed time-scale.

The concept of a fixed time-scale itself is the core of what real-time programming is. In fact, most of these old systems were built on multi-processor architectures with shared memory. SMP is a lot older than people think, it's just new to the desktop market.

With all that said, I think the solution to your problem is to break it into two systems. One for real-time processing that is capable of doing all its work in a fixed time schedule. One for foreground processing that can deal with processing tasks that exist longer than an iteration.

For something like breaking you need a very low latency controls input system. The specialty for controls is very specialized but there should be decades of material on how it's done out there. For foreground processing something that is fast enough to handle the processing part but stay within limits. If you want to do more comprehensive number crunching you'll probably also want a background processing unit that can process very long running tasks.

I'm not sure if I answered the question you were asking effectively but I hope it was a good read anyway. It's rare that I'm afforded an excuse to talk about this stuff in context.

Aside:

I have survived a couple of FAA baseline certifications and I don't use the term 'survive' lightly. On those old systems, a baseline certification could mean that a small team of highly skilled individuals is guaranteed to spend a full 2-3 day cycling through shifts 24 hours a day to bring everything up to spec as closely as possible. If it misses, the delay before another check can take place will most likely be months.

Answer 3

Are there any hard problems with this scenario which make it unrealizable in practice?

Inattention and sensor failure. The Metro subway system in Washington DC, USA, was computer controlled in the past. While this made for an efficient system from the point of view of the riders, two major problems developed.

1) The train operators had almost nothing to do. Since the computer controlled everything, the train operators became inattentive. In an emergency, the operators could not respond. This problem was mitigated (not solved) by requiring the operators to assume manual control for an hour of their shift, to keep their skills up.

2) There were two catastrophic accidents in the last 7 years due to sensor failure. Imagine the poor train operator moving towards a stopped train at 55 miles per hour, unable to stop the train in time because the computer did not sense the stopped train.

At Least 6 Killed in Red Line Crash

I don't know that these problems make data flow based programming unrealizable. I do know that these and other problems make data flow based programming hard.