18-12-2012, 04:33 PM
A Deterministic Model for Heterogeneous Embedded Systems
A Deterministic Model for Heterogeneous.pdf (Size: 587.11 KB / Downloads: 22)
INTRODUCTION
UNLIKE single-threaded software programs or synchronous
digital logic circuits, real-world embedded systems
contain many computational styles. Most are amalgams
of hardware and software; the hardware is often implemented
as one or more islands of synchronous logic, while the software
may be single-threaded, concurrent, parallel, distributed, or
event-driven.
We propose the SHIM (Software/Hardware Integration
Medium) model, a concurrent, asynchronous, deterministic
model for specifying, validating, and synthesizing such heterogeneous
embedded systems, and discuss its simulation and
synthesis. The need for concurrency is clear: at the minimum,
hardware peripherals operate in parallel with software.
The need for an asynchronous model is more subtle: although
embedded hardware-software systems are typically
implemented using synchronous digital logic, software timing
is difficult to predict. At the lowest level, the number of cycles
required to execute each machine instruction on a modern processor
is unpredictable because of complex interactions among
instructions in the pipeline, the cache, superscalar instruction
scheduling, and branch predictors. While such behavior can be
modeled, it is costly to simulate. Similarly, at a higher level, the
behavior of complex algorithms can be very difficult to predict.
An asynchronous model of software allows such details to be
safely ignored.
TINY-SHIM AND ITS SEMANTICS
the syntax for Tiny-SHIM, a language embodying
our model. Each process is a statement (or group thereof) with
its own set of variables, and each channel is READ and written
by exactly one process, although each such process may contain,
for example, multiple READ operations for a specific channel.
Tiny-SHIM is a simple language with no syntactic sugar. Meant
as an easy-to-understand and analyze intermediate language, we
plan to create the larger SHIM language that will include many
more constructs. This will be dismantled into Tiny-SHIM.
We express the semantics of Tiny-SHIM in Plotkin’s [6] structural
operational style. The state of a process is represented as a
pair of the form , where represents the state of the local
store for each process, i.e., a mapping from a process’s variables
to values, and is the statement the process has become; or of the
form , which represents the process terminated in state .
The state of a system is a multiset of such process states:
an unordered list of potentially repeated process states, since
several processes may be in identical states.
MOTIVATING EXAMPLE
Our choice of model comes from the observation of many embedded
hardware/software systems. Here, we describe one commercial
embedded system that is representative of many microprocessor-
based real-time systems and how to model it in SHIM.
In 1981, Bally/Midway produced the Robby Roto video arcade
game.1 Although primitive by today’s standards, it is representative
of many early arcade games and illustrates a realistic,
commercial embedded system.
Robby is a bus-based microprocessor system with support for
video, sound, and some simple input devices. Built around a Z80
running at about 1.8 MHz, it contains the usual RAMs (both
static and dynamic), ROMs, and memory-mapped input-output
(I/O) devices, including a video controller with bit-mapped
graphics, a hardware blitter, and a pair of sound synthesizers.
Robby employs the usual mechanisms for communicating between
hardware and software: memory mapped I/O for software-
initiated communication and interrupts for hardware-initiated.
The video display is the only source of interrupts in the
system. It can generate two types: a light pen interrupt that goes
unused in the Robby game (an artifact of its home arcade system
origins), and a scan-line interrupt that can be triggered at any
scan line under program control.
Synchronous Processes
The synchronous model, such as that in the Esterel [7] and
Lustre [8], has proven itself useful in modeling a large class of
systems. In it, synchronous processes march to a common clock
and communicate in a broadcast style. Representing such systems
in SHIM can be useful, either as a mechanism for importing
code from existing system, or as a design pattern (e.g., certain
systems might be best modeled as synchronous islands communicating
asynchronously).
In SHIM, synchronous systems can be expressed by introducing
“redundant” communication. A synchronous process in
our model must periodically communicate with all of its peers
(i.e., every process with which it ever communicates). The
one-to-many channels typical in synchronous models can be
emulated with “fanout” processes that repeatedly READ from an
input channel and replicate the data on every output channel.
Berry and Sentovich [9] propose a low-level way to implement
a synchronous formalism in an asynchronous model of
computation.