From The Edge

The IEEE 2001 Annual Report notes that 40 of the 60 most-cited technical journals come from their presses. While Transactions on Applied Superconductivity (for just one example) might have a rather narrow focus, you'll find both great breadth and depth in others. In particular, the Proceedings of the IEEE covers the entire range of the technological universe as seen from the electronic end of the biz.

Even if 8 of the 13 papers in the January 2003 Proceedings of the IEEE come from academia, that Special Issue on Modeling and Design of Embedded Software should be of interest to all embedded systems folks. These authors report from the far frontiers of embedded software design, out where algorithms use strange languages and hardware sports bizarre shapes. First, let's see why embedded programming merits a special issue, then examine a few highlights from those 240 pages of dense, ad-free text.

Embedded is Different

Application software development proceeds under a set of fundamental assumptions that are so obvious as to be taken for granted. These assumptions date back to the dawn of electronic computing, back to the days when real mathematicians walked the stage, back when a "computer" sat at a desk with a hand-cranked arithmetic calculator, an algorithm on a sheet of paper, and a pencil.

Software development's basic activity involves converting a problem description into an algorithm, an unambiguous sequence of steps that converts input data into output data. Both inputs and outputs may be any numeric values, with intermediate values being more of the same. The algorithm processes its data regardless of the computer implementing it, because Turing demonstrated that all computers are simply variations on a theme.

We're so used to jacking up software, sliding new hardware underneath, and lowering the code gently on its new carrier that we exhibit surprise when it doesn't work, rather than when it does. Various quirks aside, successive hardware generations tend to run application programs just the same, only faster.

In fact, once upon a time there were more 7090 systems running than IBM ever produced, because IBM System/360 mainframes ran emulators for the company's older 7090s faster than real 7090 hardware. Even in those days, buying (uh, leasing) new hardware posed fewer problems than recoding old applications.

In contrast, embedded systems code depends critically on the hardware. Even if it need not react in real time, it must accept real-world constraints on accuracy and latency while conforming to power and EMI specifications. Software defines the behavior and function of embedded systems to such an extent that the hardware may seem secondary, but hardware defines how the software observes and manipulates the outside world.

As the Proceedings introduction observes, that symbiotic relationship cuts directly across conventional software development methodologies. Where applications development depends on functional decomposition, embedded hardware constraints entwine throughout the design. Modules that seem completely disjoint on a functional basis become closely coupled by a hardware feature that can't be abstracted away.

For example, logically separate serial channels may use control bits located in a single hardware register. The simple act of checking one channel's status may reset bits associated with other channels, so the serial port code must exactly match the hardware's functions. Moving that code unchanged to another system with slightly different serial port hardware will trigger mysterious failures.

A device driver normally handles the hardware and prevents higher level functions from the grisly bit twiddling. Embedded code generally can't afford that level of isolation: Imagine an engine controller for both 12-cylinder diesel locomotives and one-lung gasoline irrigation pumps. The controller must know quite a lot about the specific hardware at the end of its wires.

Current development methods concentrate almost exclusively on abstract algorithm modeling, which captures hardware linkages on a less formal basis. Handling those serial port bits, timing a glow plug's heat, or triggering an ignition pulse may be easy, at least after you realize what's involved; but defining restrictions on this algorithm in order to reduce spurious RF emissions from that circuit under control of those routines, before you even write the code or choose the hardware, requires an entirely new way of specifying and developing programs.

Embedded software's intimate hardware relationship also complicates our ability to verify its function, because the notion of "provably correct" software doesn't scale well. Even short sample programs used to demonstrate a proof methodology have contained undetected errors, and the problem gets worse as projects get larger.

Proving that a program meets specifications implicitly assumes that those specifications are correct, which may be a bad assumption for complex projects. After you toss in a few real-world issues such as timing, accuracy, resolution, latency, and noise, you'll probably find that you cannot specify exactly how the program should work in all situations.

Standard software development attacks that problem by decomposing the problem into smaller units that can be verified to be correct. Unfortunately, that doesn't work well with embedded systems, either, because of those nasty hardware interactions and real-world connections. Worse, we've discovered that lashing a large number of small, seemingly well-specified subsystems together can produce what's euphemistically called "emergent behavior."

Time Is of the Essence

The early years of computer design produced no broad agreement on how to make the things work. One school of thought held that asynchronous, self-timed logic made for faster and simpler circuitry. Others opted for synchronous logic with every register driven from a master clock.

Asynchronous logic, as deployed in the University of Illinois' ILLIAC I, triggers each computational block when its data becomes available, rather than at the next clock tick. Each block must generate a status output to indicate when its results become valid and must also maintain its output until downstream blocks have accepted it. Each block produces its results as rapidly as possible, so the entire system runs at a rate determined by the instantaneous complexity of the operation and its data.

A synchronous logic system latches the outputs of all computational blocks in registers, with the period of the clock defined by the longest delay through any of the blocks. While nominally slower than an asynchronous design, this architecture has the compelling advantage that you can freeze the entire state of the system by simply stopping the clock. The register contents define the current system state, and their inputs show what the circuitry has come up with since the previous tick.

Essentially all contemporary computer systems use synchronous logic, if only because essentially all contemporary hardware design and verification programs don't handle asynchronous logic particularly well. The notion of results rattling around inside a complex system like balls through a Pachinko game sends shivers up the spines of folks who must verify the hardware's functions.

Asynchronous logic is making a comeback because distributing a single global clock across a huge chip poses serious problems. Separating the chip into asynchronous subsystems, then resynchronizing at the boundaries, sidesteps several rather gnarly time-of-flight issues.

Pop Quiz: So, is current software synchronous or asynchronous?

Right. All common languages (that is, ones you've seen advertised) are essentially asynchronous. Each function runs at top speed, reads and updates whatever variables it likes, and returns those results when it's good and ready.

Several Proceedings papers explore synchronous languages, which seem to be much better known in Europe than the U.S. A synchronous language imposes two convenient fictions: All processes run in parallel, and all their outputs change simultaneously at specific instants. Those conventions greatly simplify both analysis and verification of the ensuing code.

These are not general-purpose languages that would find ready acceptance in the payroll department (or wherever they do payroll these days). Synchronous languages help fill the need for deterministic, provably correct programs for hard real-time control systems and simply aren't applicable outside that domain. On the other hand, that domain is growing to encompass systems that might benefit from a different approach.

Synchronous languages define a global software clock that updates the software state at each tick. All functions prepare their outputs based only on the previous state, but the outputs do not change until commanded by the global clock. Asynchronous inputs must be sampled, perhaps lightly processed, and stored as part of the state update, not handled on the fly.

The global clock must be uniform across the entire system, just as in a synchronous hardware design, although a software clock need not tick at subnanosecond rates (yet!). Ensuring accurate software synchronization across multiple processor components in multiple sites remains an area of active research, as does resynchronizing data produced in different domains.

Specifications for such a system can be built in a modeling language that defines a set of states and the valid transitions between them, using both Boolean and arithmetic functions. With state transitions defined by the global clock and all functions acting only on the previous state with perfect concurrency, the resulting code can be either generated or checked (depending on the language) with far greater accuracy than with asynchronous languages.

A similar development describes designs using the Time Triggered Architecture (TTA). Unlike ordinary hardware, TTA incorporates external wall-clock time directly into the system design on a hardware level. Each node of a distributed system can run asynchronously using hardware synchronizers that ensure consistent communication between nodes. As with synchronous languages, a global clock defines an overall timebase that allows a unique timestamp for each external event, but individual nodes do not run their logic from the global clock.

A coherent image of the system state prevents "impossible" situations from producing weird responses. Unique timestamps ensure that each node can impose a strict ordering on all events, eliminating those little quirks we've come to expect every now and again.

Doesn't it seem just slightly odd, though, that at a time when hardware reenters asynchronous waters, software starts heading in the other direction? Maybe this has something to do with the overall symmetry of the universe.

Optimization

Since embedded software and hardware have such intimate relations, hardware constraints directly affect software design and, conversely, the software implementation can affect the hardware. Several Proceedings papers explore the surprising effects.

Embedded systems face severe per-unit cost restrictions that generally make the hardware as cheap as possible. Although special-purpose hardware may cost less than a general-purpose microprocessor and all its support circuitry, the flexibility of a micro generally wins out. That microprocessor must then have as little support circuitry as possible, which means as little memory as possible. Trading off those "as possibles" is what engineering is all about.

In addition to simple code size, memory access patterns can dramatically affect the system's average and peak power consumption. While this may not seem like a big deal, remember that a system's average power directly determines its run time from a given battery, and a high peak-to-average current ratio complicates the power supply. Arranging your code to reduce external memory accesses also reduces power consumption, which means embedded code must be aware of hardware cache behavior.

In fact, one paper explores the power consequences of a program's cache friendliness for various cache control algorithms. Now, frankly, you'd want to study your requirements carefully to see if an on-the-fly reconfigurable cache makes any difference, but it's an example of how something you never considered might save your run-time bacon.

Ordinary application programs can safely assume their underlying hardware will always work. Embedded code doesn't have that luxury, particularly in situations where repair may be impossible. Designing code that can detect and work around hardware failures poses a significant challenge.

One paper uses the Mars Polar Lander failure as an example. It seems that a glitch triggered the ground contact sensors when the lander deployed its legs high up in the Martian atmosphere. The control code started polling those sensors about 40 meters above the surface, instantly saw that they'd been tripped, and shut off the landing engine. Thump!

Several papers describe methods of modeling the external world so that the system can use that model to decide what to do in a given situation. The model can include failure modes with various workarounds to avoid further damage. The software may not be reasoning, but at least it can make reasonable choices.

Perhaps the most encouraging aspect of the Special Issue on Modeling and Design of Embedded Software is the improvement over our current practices. Even though the oddball languages and modeling techniques may not be the right answers, they help show that we can do better if we try something different.

It's almost enough to make me wish for Version 1.0 of their shrink-wrapped code! Nah, nothing can be that good...

Contact Release

I've found IEEE publications to be invaluable resources over the years. Start at http://www.ieee.org/, where you can get to the annual report by entering "2001 Annual Report" (with the quotes) in the search field. Those of you in college towns may prefer reading IEEE journals, either electronic or paper, in university libraries.

Start at http://simh.trailing-edge.com/ to run various emulators. There's no 7090, but I'm sure someone would appreciate your hammering one out.

If you haven't already done so, go to http://catless.ncl.ac.uk/Risks/ and commence reading. You can read more than you probably want to know about Pachinko at http://www.japan-zone.com/modern/pachinko.shtml.

Rudy Rucker described what happens when robots discover how to evade Asimov's Three Laws. His Moldies and Meatbops, although out of print, remains available at reasonable prices from the usual sources.

DDJ