ABOUT THE AUTHOR Stephen A. Edwards graduated in 1997 with a Ph.D. from Berkeley and is currently working in Synopsys' Advanced Technology Group. He is the author of the book Languages for Digital Embedded Systems, and has published several technical papers on design languages and compilers for system design.

An embedded system is a computer masquerading as a non-computer that must perform a small set of tasks cheaply and efficiently. A typical system might need to do communication, signal processing, and user-interface tasks. Because the tasks must solve diverse problems, a general-purpose language to solve all embedded applications would be difficult to write, analyze, and compile. Instead, developers have introduced a variety of languages, each best suited to a particular problem domain.

This article briefly describes several popular hardware, software, dataflow, and hybrid languages, each of which excels in dealing with certain types of problems. For example, dataflow languages are good for signal processing problems. Hybrid languages combine ideas from the other three language classes. The author also presents examples for each design language.

Verilog provides more primitives geared specifically toward hardware simulation. On the other hand, VHDL's primitives are assignments such as a = b + c or procedural code. Verilog adds transistor and logic-gate primitives, and lets you define new primitives with truth tables.

Both languages allow concurrent processes to be described procedurally. Such processes sleep until awakened by an event that causes them to run, read and write variables, and suspend. Processes may wait for a period of time (for example, #10 in Verilog, wait for 10ns in VHDL), a value change (@(a or b), wait on a,b), or an event (@(posedge clk), wait on clk until clk='1'). VHDL communication is more disciplined and flexible. Verilog communicates through wires or regs: shared memory locations that can cause race conditions. VHDL's signals behave like wires, but the resolution function may be user-defined. VHDL's variables are local to a single process unless declared as shared variables.

	Verilog	VHDL			Verilog	VHDL
Structure				Type System
Hierarchy				Interface/Implementation
Concurrency				Local Variables
Switch-Level Modeling				Shared Memory
Gate-Level Modeling				Wires
Dataflow Modeling				Resolution Functions
Procedural Modeling				Event Access

Table 1:  This summary of Verilog and VHDL language features indicates how each supports various features and tasks ( full support, partial support)

Figure 1:  (a) This Verilog model for a full adder uses primitive gates, continuous assignment, and procedural code. (b) A similar full-adder VHDL model that does not include the test bench (Word document containing this code).

Verilog's type system models hardware with four-valued bit vectors and arrays for modeling memory. VHDL does not include four-valued vectors, but its type system lets a user add them. Furthermore, you can define composite types such as C structs.

Overall, Verilog is the leaner language, more directly geared toward simulating digital integrated circuits. VHDL is a much larger, more verbose language capable of handing a wider class of simulation and modeling tasks.

Each machine instruction typically does little more than, for example, add two numbers, so high-level languages aim to specify many instructions concisely and intuitively. Arithmetic expressions are typical—coding an expression such as a² + bx + c in machine code is straightforward, tedious, and best done by a compiler. The C language provides such expressions, control-flow constructs such as loops and conditionals, and recursive functions. In addition, the C++ language provides classes as a way to build new data types, templates for polymorphic code, exceptions for error handling, and a standard library of common data structures. Java is a still higher-level language that provides automatic garbage collection, threads, and monitors to synchronize the threads.

Assembly Languages
An assembly language program (Figure 2a) is a list of processor instructions written in a symbolic, human-readable form. Each instruction consists of an operation, such as addition, along with some operands. For example, add r5,r2,r4 might add the contents of registers r2 and r4 and then write the result to r5. An assembly language executes these types of arithmetic instructions in order, but branch instructions can perform conditionals and loops by changing the processor's program counter—the address of the instruction being executed.

A processor's assembly language is defined by its opcodes, addressing modes, registers, and memories. The opcode distinguishes, for example, addition from a conditional branch, and an addressing mode defines how and where data is gathered and stored (such as, from a register or from a particular memory location). Registers can be thought of as small, fast, and easy-to-access pieces of memory.

The C Language
A C program (Figure 2b) contains functions built from arithmetic expressions structured with loops and conditionals. Instructions in a C program run sequentially, but control flow constructs such as loops of conditionals can affect the order in which instructions execute. When control reaches a function call in an expression, the program passes control to the called function. This function runs until it produces a result, and control returns to continue evaluating the expression that called the function.

C derives its types from those a processor manipulates directly: signed and un-signed integers ranging from bytes to words, floating point numbers, and pointers. These can be further aggregated into arrays and structures—groups of named fields.

	C	C++	Java			C++	Java	RTOS
Expressions					Templates
Control-Flow					Namespaces
Recursive Functions					Multiple Inheritance
Exceptions					Threads and Locks
Classes and Inheritance					Garbage Collection

Table 2:  A comparison of language features between C, C++, and Java ( full support, partial support)

Figure 2:  (a) Euclid's algorithm written in i386 assembly language. Symbols like %ebx represent registers. movl means "move long value." divl %ebx divides %eax by %ebx and puts the remainder in %edx. (b) An example of a C program that prints its arguments backwards. The outermost while loop iterates through the arguments (count in argc, array of strings in argv), while the inner loop starts a pointer at the end of the current argument and walks it backwards, printing each character along the way. The ++ and -- prefixes increment the variable to which they are attached before returning the value of the variable (Word document containing this code).

C programs use three types of memory. The program allocates space for global data upon program compilation. The stack stores automatic variables the program allocates and releases the variables when the program calls the function and returns a value. The heap supplies arbitrarily sized regions of memory that the program can de-allocate in any order. Although the C language is an ISO standard, many people consult the book by Kernighan and Ritchie , since Ritchie designed the language.

C++
C++ (Figure 3a) extends C with structuring mechanisms for big programs. These mechanisms include user-defined data types, a way to reuse code with different types, namespaces to group objects and avoid accidental name collisions when program pieces are assembled, and exceptions to handle errors. The C++ standard library includes a collection of efficient polymorphic data types such as arrays, trees, and strings for which the compiler generates custom implementations.

A class defines a new data type by specifying its representation and the operations that may access and modify it. Classes may be defined by inheritance, which extends and modifies existing classes. For example, a rectangle class might add length and width fields and an area method to a shape class.

A template is a function or class that can work with multiple types. The compiler generates custom code for each different use of the template. For example, a program could use the same min template for both integers and floating-point numbers.

Java
Sun's Java language resembles, but is incompatible with, C++. Like C++, Java is object-oriented, providing classes and inheritance. It is a higher-level language than C++, since it uses object references, arrays, and strings instead of pointers. Java's automatic garbage collection frees the programmer from memory management.

Java provides concurrent threads (Figure 3b). Creating a thread involves extending the Thread class, creating instances of these objects, and calling their start methods to start a new thread of control that executes the objects' run methods.

Figure 3:  (a) A C++ fragment illustrating a partial complex number type—the C++ standard library has a complete version. (b) A contrived Java program that spawns a counting thread to print all numbers divisible by 5 (Word document containing this code).

Synchronizing a method or block uses a per-object lock to resolve contention when two or more threads attempt to access the same object simultaneously. A thread that attempts to gain a lock owned by another thread will block until the lock is released—you can use this feature grant a thread exclusive access to a particular object.

RTOS
Many embedded systems use a real-time operating system (RTOS) to simulate con-currency on a single processor. An RTOS manages multiple running processes, each written in a sequential language such as C. The processes perform the system's computations and the RTOS schedules them. The scheduling attempts to meet deadlines by deciding which processes run at what times and in what order. Labrosse describes the implementation of a particular RTOS.

Most real-time operating systems use fixed-priority preemptive scheduling in which each process is given a particular priority (a small integer) when the system is designed (Figure 4). At any time, the RTOS runs the highest-priority running process, which is expected to run for a short period of time before suspending itself to wait for more data. Priorities are usually assigned using rate-monotonic analysis (described in Liu and Layland), which assigns higher priorities to processes that must meet deadlines that are more frequent).

Figure 4:  The behavior of an RTOS with fixed-priority preemptive scheduling. Rate-monotonic analysis gives process P1 the highest priority since it has the shortest period; P3 has the lowest. Event A would have missed its deadline, indicated by the tick mark, if it had not preempted Event B.

Kahn Process Networks
Kahn Process Networks form a formal basis for dataflow computation (Figure 5). Kahn systems consist of processes that communicate exclusively through unbounded point- to-point first-in, first-out queues. Reading from a port makes a process wait until data is available, so the behavior of a Kahn network does not depend on execution speed. Balancing the relative execution rates of processes to avoid an unbounded accumulation of tokens is the challenge in scheduling a Kahn network. One general approach, proposed in Parks' thesis, places artificial limits on the size of each buffer. Any process that writes to a full buffer blocks until space is available, but if the system deadlocks because all buffers are full, the scheduler increases the capacity of the smallest buffer.

Figure 5:  Example of a Kahn Process Network. The f process alternately copies from its u and v ports to its w port. The g process does the opposite, copying its u port to alternately v and w. h simply copies its input to its output (Word document containing this code).

Synchronous Dataflow
Lee and Messerschmitt's Synchronous Dataflow fixes the communication patterns of the blocks in a Kahn network (Figure 6). Each time a block runs, it consumes and produces a fixed number of data tokens on each of its ports. This predictability allows the program to completely schedule the SDF at compile-time, producing very efficient code.

Figure 6:  Example of a modem in SDF (from Bhattacharyya et al.)

Scheduling operates in two steps. First, the program establishes the rate at which each block fires by considering the production and consumption rates of each block at the source and sink of each queue. For example, one of the arcs in Figure 6 implies 2C = 4D.

Once the program has established the rates, any algorithm that simulates the execution of the network without buffer underflow will produce a correct schedule if such a schedule exists. However, more sophisticated techniques reduce generated code and buffer sizes by better ordering the execution of the blocks (see Bhattacharyya et al.).

	Esterel	Polis	SDL	SystemC	CCSS
Concurrent
Hierarchy
Preemption
Deterministic
Synchronous Communication
Buffered Communication
FIFO Communication
Procedural
Finite-State Machines
Dataflow
Multi-Rate Dataflow
Software Implementation
Hardware Implementation

Table 3:  A comparison of hybrid language features ( full support, partial support).

Esterel
Intended for specifying control-dominated reactive systems, Esterel combines the control constructs of an imperative software language with concurrency, preemption, and a synchronous model of time such as the time model synchronous digital circuits use (Figure 7a). In each clock cycle, the program awakens, reads its inputs, produces outputs, and suspends.

An Esterel program communicates through signals that are either present or absent during each cycle. In each cycle, each signal is absent unless an emit statement for the signal runs and makes the signal present for that cycle only. Esterel guarantees determinism by requiring each emitter of a signal to run before any statement that tests the signal.

Polis
The Polis hardware-software co-design system uses a concurrent formalism geared to hardware and software implementation. A system is a collection of co-designed finite-state machines (CFSMs) connected through broadcast communication channels. Each CFSM has single-place buffers for each of its inputs, and a CFSM takes a step when it receives at least one event on its inputs, whose types may be events or values. A CFSM transition is atomic, but takes an arbitrary, non-zero time. Each CFSM becomes a process running under an RTOS (buffers are in shared memory) or a state machine that takes a single clock cycle per transition.

SDL
SDL is a graphical specification language developed for describing telecommunication protocols defined by the ITU. Ellsberger presents a more readable description of SDL than does ITU. A system consists of concurrently running FSMs, each with a single input queue, connected by channels defining which messages they carry. Each FSM consumes the most recent message in its queue, reacts to it by changing an internal state or sending messages to other FSMs, changes to its next state, and repeats the process. Each FSM is deterministic, but because messages from other FSMs may arrive in any order because of varying execution speed and communication delays, an SDL system may behave non-deterministically.

SystemC
The SystemC language is a C++ subset for specifying and simulating synchronous digital Hardware (Figure 7b). You can simulate a SystemC specification by compiling it with a standard C++ compiler and linking in freely distributed class libraries (from www.systemc.org). The program generates hardware by working with a commercially available compiler, CoCentric's SystemC.

Figure 7:  (a) An Esterel program modeling a shared resource. (b) A SystemC model for a complex multiplier (Word document containing this code).

The SystemC language builds systems from Verilog- and VHDL-like modules. Each module has a collection of I/O ports and may contain instances of other modules or processes, either synchronous or asynchronous. SystemC's simulation semantics are synchronous—when a clock arrives, each synchronous process sensitive to that clock runs, asynchronous processes sensitive to changes on the outputs of those processes run until they stabilize, and then the process repeats.

CoCentric System Studio
CoCentric System Studio uses a hierarchical formalism that combines Kahn-like dataflow and hierarchical, concurrent FSMs. The FSMs resemble Harel's State-charts, but use Esterel's synchronous semantics to ensure determinism.

A CoCentric System Studio model is built hierarchically from Dataflow, AND, OR, and Gated models. Dataflow models are Kahn Process networks. The blocks may be dataflow primitives written in a C++ subset or other hierarchical models. AND models run concurrently and communicate with Esterel-like synchronous semantics. OR models are finite-state machines that may manipulate data and whose states may contain other models. Gated models contain sub-models whose execution you can temporarily suspended under external control.