Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
I do not see how data-passing could use up that much CPU in the libraries/concepts I mentioned above. I do not know RIPPEN, but if the problem is not inherent to it, would you mind elaborating a bit on the reasons for these 20%? –  Frank Apr 17 '12 at 16:50
    
The problem with this approach is that as soon as things get interesting, diagrammatic languages become unwieldy. Basically, you can't refactor diagrams. –  kevin cline Apr 17 '12 at 18:23
    
I don't know why RIPPEN was eating me alive shuffling data around between blocks. I only know what the profiler showed me, that 20% of my CPU time was "unaccounted for" in any of the code I was working on. –  John R. Strohm Apr 17 '12 at 18:34
    
@kevincline, it sure can get unwieldy! However, if you stick with the intent of the LabVIEW language and also keep the scope of the project from sprawling, it can be superb for rapid application development in the domains for which it is well-suited. I consider LabVIEW like a very big DSL. –  Angelo Apr 17 '12 at 18:43
    
My question wasn't about diagrammatic languages really, so I'll wait for some other answers for comparison. –  Frank Apr 18 '12 at 6:00
add comment

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.

share|improve this answer
    
Flight sims run at minimum of 30hz - usually 60hz or higher these days. This is the frame rate and is equivalent to 33.33ms frames. Typically sims run with min 20% spare time so that gives you around 27ms to do all the calculations and be ready. Frame overrun will emergency halt the sim. Digital Controls run at 500hz - analog controls (pre mid 80s) are different again. The rest is run at max rate (i.e. 30hz or higher depending on the era). Not all systems run at max rate - there is usually half and quarter rate for less important systems. –  Richard Harrison May 17 '12 at 12:14
    
All of this was via shared memory when using multiple cpus - which could be global in the era pre reflective memory (mid 80's). No dynamic memory was used on these. Typically the global shared memory would be from 32k to 128k depending on the airframe. All of the schedulers I ever worked on were on a one per CPU basis and executed in specified sequence (not round-robin) because each module had to complete before the next one started. –  Richard Harrison May 17 '12 at 12:19
    
However the dataflow of these old sims isn't well defined in terms of dependencies we all knew what was where so it was well understood. Effectively it's all data driven from the data lookup tables for aero, hyds, engines etc. But a lot of skill was required to get the systems in the right CPU in the right sequence. –  Richard Harrison May 17 '12 at 12:20
    
@RichardHarrison Thanks for the correction and additional info. I updated the frame time to 33ms. At the time I was an IO guy so my knowledge of the host is limited to what I learned from the engineers I worked with. One thing I always wondered. Back then, as the computers scaled to more processors the overhead increased at a rate where eventually no gain was achieved from adding more CPUs. With the re-emergence of multi/many-CPU SMP, how was that overcome? –  Evan Plaice May 17 '12 at 18:24
    
SMP doesn't really apply to most sims as they are more like distributed systems - each with a discrete unit running specialised real time executive (depending on the sim and the vintage). The ones using shared reflective memory are limited by the RM bus to the number of discrete processing units that can be added to the bus - adding extra nodes would upscale the performance fairly linearly - if we ran out of spare time it was common (but expensive) to add another node to the configuration - the overhead would be very small as it is just that of the real time executive so you'd get probably 99% –  Richard Harrison May 18 '12 at 11:48
add comment

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.

share|improve this answer
1  
Your answer is not about dataflow-based programming at all, but about general problems in automation of sensor-actuator-scenarios, which was not my question. –  Frank Apr 18 '12 at 14:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.