Read an Excerpt
Chapter 3
Models of Computation
3.1 Introduction
SystemC allows design teams to build models of systems that utilize one or a mixture of various models of computation.
The notion of a "model of computation" (MOC) is fundamental to system level design; yet it has not been formalized completely. One attempt at a formal definition is found in [10], where the authors state: "How the abstract machine in an operational semantics [. . . of a language . . . ] can
behave is a feature of what we call the model of computation underlying the language." The authors further discuss features of the model of computation, including the kinds of relations that are possible in a denotational semantics, the communication style, how individual behaviors are aggregated to make complex compositions, how concurrency is handled, and how such compositions are hierarchically abstracted.
For our purposes a less formal definition will suffice. We define the model of computation provided by a modeling language as follows:
1. The model of time employed (realvalued, integervalued, untimed) and the event ordering constraints within the system (globally ordered, partially ordered, etc.).
2. The supported method(s) of communication between concurrent processes.
3. The rules for process activation.
Most "traditional" design languages such as VHDL, Verilog, and SDL can be seen as having a single fixed model of computation, and provide little or no way for users to customize the given model of computation. In a sense, SystemC also has a single fixed model of computation, but it is different from other traditional design languages in several key ways:
1. The "base" model of computation is designed to be extremely general.
2. The SystemC language as a whole is designed so that customized models of computation can be cleanly and eYciently layered on top of the base capabilities provided by the SystemC core language.
Briefly, the SystemC core language features that allow customized models of computation to be constructed include:
- Events, the notify() call, and the wait() call. These simple, flexible synchronization capabilities allow a broad range of diVerent channel types to be implemented without having to change the underlying simulation engine. All the required functionality is already present in the simulation kernel. While the global model of time is fixed to an integer model, designers can construct specific channels to achieve their precise rules for communication between processes, process activation, and systemwide event ordering. It is important to realize that events are the fundamental synchronization mechanism within SystemC, and all channels that provide communication and synchronization (even ones as basic as sc_signal) are built up from events and other core language features.
- The user's ability to create specialized channels, interfaces, ports, and modules. SystemC allows users to create channels and interfaces to model specific communication capabilities in the same way that specific communication capabilities are provided by the sc_signal and sc_fifo channels introduced in chapter 2. SystemC also allows users to create specialized ports and modules that make using such user-defined channels more natural and less errorprone. As a simple example of this, a user could create a specialized module named sc_rtl_module that checks to make sure that all of its ports connect to signal channels. Users might then create their RTL modules by deriving from sc_rtl_module rather than the more general sc_module.
In this way, SystemC cleanly supports the emulation of a large number of different MOCs. Although continuous time models as used, for example, in analog modeling, cannot yet be constructed in SystemC, virtually any discrete time system can be modeled in SystemC. Some wellknown models of computation which can be quite naturally modeled in SystemC include:
- Static multirate dataflow
- Dynamic multirate dataflow
- Kahn process networks
- Discrete event as used for
- RTL hardware modeling
- network modeling (e.g., stochastic or ìwaiting roomî models)
- transactionbased SoC platform modeling
Note that the above list of MOCs that can be modeled within SystemC is in no way exhaustive.
Since SystemC can support multiple MOCs, it is important to know how two or more different MOCs will interact when used in the same system. Here again SystemC's generalpurpose, flexible core language features provides many benefits. In the same way that users can create specialized channels to precisely control communication within a single MOC, they also
can create specialized channels to precisely control communication and synchronization between two or more MOCs. As a simple example, when a dataflow module sends tokens to an RTL module, it might be desirable to have the dataflow tokens be spread in time in some fashion (e.g., one token per clock edge). Users can construct MOC "conversion" channels that allow different MOCs to be interfaced according to their precise rules. We will see an example of such an MOC conversion block in chapter 10, example 10.2.3.
Why is it necessary for SystemC to support many different models of computation? One primary reason is that many systems are not homogeneous, and thus they are best described using a combination of models or notations which are natural to various subsystems.
For example, in figure 3.1, we depict a CDMA transmitter/receiver system. It consists of several key subsystems, which would be implemented in the realworld in many different design forms: Radiofrequency (RF) processing, mixedsignal blocks (D/A and A/D), digital hardware implementing DSPstyle functions (e.g., channel coding, Viterbi decoding), possibly software implemented on a digital signal processor (DSP), and finally control software implemented on a standard microprocessor or microcontroller.
The "natural" notation or model of computation for these various subsystems differs. The DSPstyle dataflow functions might best be modeled initially as static or dynamic multirate dataflow. RF and mixedsignal blocks might be modeled using special continuoustime, differential equation based modeling representations. Control software could be modeled in a discrete event form, perhaps using transactionlevel models. An underlying instructionset simulator (ISS) for the control processor or a DSP might use an RTL MOC. In other words, the "natural" way to model this entire system is not to choose one particular model of computation and force every subsystem into it: rather, it is to build an overall system model composed from a series of heterogeneous subsystem models. This requires a modeling environment such as SystemC that allows the definition of models using particular models of computation, and a methodology for composition which allows one to make sense of the overall combination.
Another primary reason that it is important to support multiple MOCs within SystemC is that a particular subsystem might be most naturally expressed with different MOCs at different parts of the design refinement process. For example, a block that is most naturally expressed using static multirate dataflow at the functional level might be remodeled using an RTL MOC as it is refined to hardware.
The rest of this chapter briefly discusses several important models of computation that are commonly used in system design. Our intent is to provide the reader with a basic understanding of these models of computation and some idea of how they can be modeled within SystemC. Keep in mind that many other MOCs can also be modeled in SystemC, and that a given MOC may be modeled in many different ways in SystemC. The approaches outlined below for modeling MOCs in SystemC are for illustrative purposes only. Other more sophisticated approaches might be preferred in some cases for higher performance or greater flexibility.
It is also important to note that there currently are several working groups within the Open SystemC Initiative focused on developing standards for expressing various models of computation in SystemC, including a working group focused on analog and mixed signal modeling within SystemC.
3.2 The "RTL"Model of Computation
The register-transfer level (RTL) MOC is an informal term for a modeling style that corresponds to digital hardware synchronized by clock signals. This modeling style is widely used within languages such as Verilog and VHDL, and it is widely supported by commercial hardware synthesis tools. This modeling style will be described in detail in chapter 4.
In the RTL style, all communication between processes occurs through signals (sc_signal, sc_signal_rv, etc.). (The inner workings of SystemC signals will be described in detail in chapter 7.) Processes may either represent sequential logic, in which case they are sensitive to a clock edge, or they may represent combinational logic, in which case they will be sensitive to all of their inputs. RTL modules are pinaccurate. This means that the ports of an RTL module directly correspond to wires in the realworld implementation of the module. RTL modules are also cycleaccurate.
SystemC signals closely mirror the behavior of VHDL signals, and also the behavior of Verilog signals in which the Verilog deferred assignment operator (<=) is used. The signal channels provided within the SystemC release do not allow time delays to be specified when signal assignments are performed, although it would be easy to create a customized signal channel that provides this feature. (In general, when performing RTL modeling, time delays for signal assignments are not needed because combinational logic delays are not being modeled.)
Because combinational or gate delays are generally not modeled in SystemC at the RTL level, some people might mistakenly believe that SystemC is an RTL "cycle simulator". In true cycle simulators, the order of evaluation of processes is determined before simulation starts using either explicit manual coding or automatic techniques. In SystemC, the order of process evaluation is dynamically (and automatically) determined as the simulation proceeds.
3.3 Kahn Process Networks
A Kahn process network (KPN) is an effective model of computation for building algorithmic models of signalprocessing applications. Such applications are common in the multimedia and communications product domains. The KPN model has been used for multimedia applications by Philips with its YAPI approach [8]. Also see [14] for more information.
In the KPN model, computing blocks or processes execute concurrently, and are connected by channels that carry sequences of data tokens. These channels are infinite length FIFO channels. The concurrent processes that model system functionality read and write to these FIFO channels with blocking read and nonblocking write operations. Systems modeled exclusively using KPN are deterministic: the process execution order (i.e., the scheduling order) will not affect the token values seen on the FIFO channels.
In chapter 5 we will see how sc_fifo channels and SC_THREAD processes can be used to easily model KPN designs within SystemC. As discussed in chapter 5, practical implementations of KPN systems cannot have infinite length FIFOs. Either specific upper bounds for FIFOs must be specified by the designer (thus making write operations potentially blocking), and/or a KPN scheduler must be provided that attempts to keep the network executing without letting any of the FIFOs grow to infinite length.
In its purest form KPN systems have no concept of time. However, as we will see in chapter 5, after initial functional modeling is completed it is often useful to annotate time delays (using wait(sc_time) statements) into KPN models. The resulting model is called a timed functional model, or also a performance model.
3.4 Static Dataflow
Static dataflow (SDF) networks are a special case of Kahn process networks in which:
1. The functionality within each process is clearly separated into three stages: reading of all input tokens, execution of the computation within the process, and writing of all output tokens.
2. The number of tokens that a process will read and write each time it is executed is fixed and known at compiletime.
Because the activation rules for each process are known at compiletime, tools can analyze the network and build static execution schedules for processes and compute bounds for all FIFOs at compiletime rather than at execution time. The resulting models will execute far more quickly than KPN or discrete event models due to the avoidance of dynamic scheduling. Although the scope and expressiveness of SDF is more limited than KPN or other discrete event MOCs, many algorithms have successfully been modeled using SDF. See [19] for further information on SDF. A good summary of methods for determining valid schedules for SDF networks that are consistent and deadlockfree can be found in [3].
One way to express SDF models within SystemC is to use the dataflow modeling style presented in chapter 5, "Functional Modeling." Keep in mind that the data flow modeling style presented in chapter 5 is really the more general KPN MOC, since the token production and consumption rates for blocks are not explicitly declared by the designer, and dynamic scheduling is still used when the system is simulated rather than more efficient static scheduling.
3.5 TransactionLevelModels
Transactionlevel models represent one specific type of the discreteevent MOC. In transactionlevel modeling (TLM), we model communication between modules using function calls that represent the transactions, typically supported by a target platform. Transactions can be viewed as having a specfic start time, end time, and payload data.
Within TLM designs, sc_signal channels are usually avoided entirely instead data is exchanged between different processes by reading and writing shared data variables. In the absence of a wellplanned overall synchronization scheme, having multiple concurrent processes reading and
writing to a common set of shared data variables can lead to unpredictable system execution. In chapter 8 we will present a detailed example of a TLM design and see how a twophase synchronization scheme is used to insure predictable and deterministic system execution.
TLM designs are usually more concise and simulate much faster than corresponding RTL designs.
3.6 Summary
Models of computation are fundamental constructs for the modeling of complex heterogeneous systems at various levels of abstraction. SystemC has been defined and developed to support the flexible modeling capabilities required to model a wide variety of models of computation. Future
chapters indicate how this flexibility can be used by designers.
