Experiences in modeling and simulation of computer architectures in DEVS.
The use of traditional approaches to teach computer organization usually generates misconceptions in the students. The simulated computer ALFA-1 was designed to fill this gap. DEVS was used to attack this complex design of the chosen architecture, allowing for the definition and integration of individual components. DEVS also provided a formal specification framework, which allowed reduction of testing time and improvement of the development process. Using ALFA-1, the students acquired some practice in the design and implementation of hardware components, which is not usually achievable in computer organization courses.
Figure

1. Organization of the Integer Unit.
This RISC processor is provided with 520 integer registers. Eight of them are global (RegGlob, shared by
every procedure), and the remaining 512 are divided in windows of 24 registers each (RegBlock).
Each window includes input, output and local registers for every procedure that has been executed recently.
When a routine begins, new registers are reserved (8 local and 8 output), and the 8 output records of the
calling procedure are used as inputs. A specialized 5-bit register, called CWP (Circular Window Pointer)
marks the active window. Every time a new procedure starts, CWP is decremented.

Figure

2. Organization of the processor's registers.
Besides these general purpose registers, the architecture includes:
PCs: the processor has two program counters. The PC contains the address of the next instruction. The
stores the address of the PC after the execution of the present instruction. Each instruction
cycle finishes by copying the nPC to the PC, and adding 4 bytes (one word) to the nPC. If the instruction is
a conditional branch, nPC is assigned to PC, and nPC is updated with the jump address (if the jump condition
is valid).
Y: is used by the product and division operations;
BASE and SIZE: The memory is considered flat (that is, neither segmentation nor pagination mechanisms
are included). Likewise, multiprogramming is not supported. The BASE register points to the lowest
address a program can access. The SIZE stores the maximum size available for the program.
PSR (Processor Status Register): stores the current status for the program. It is interpreted as follows.
Bits Content Description
Reserved
Negative 1 when the result of the last operation is negative
22 Z - Zero 1 when the result of the last operation is zero
when the result of the last operation is overflow
when the result of the last operation carried one bit
19.12 Reserved
Lowest interrupt number to be serviced.
6 PS - Previous State Last mode.
Enable Trap 1=Traps enabled; 0=Traps disabled.
Current Window Pointer Points to the current register window.

Table

1. Contents of the Process Status Register
WIM (Window Invalid Mask): this 32-bit register (one bit per window) is used to avoid overwriting a
window in use by another procedure. When CWP is decremented, these circuits verify if the WIMbit is active
for the new window. In that case, an interrupt is raised and the interrupt service routine stores the content
of the window in memory. Usually, WIMonly has one bit in 1 marking the oldest window.
TBR (Trap Base Register): it points to the memory address storing the position of a trap routine.
Bits Content Description
base address Base address of the Trap table
11.4 Trap Type Trap to be serviced
3.0 Constant (0000)

Table

2. Contents of the Trap Base Register
The first 20 bits (Trap Base Address) store the base address of the trap table. When an interrupt request is
received, the number of the trap to be serviced is stored in the bits 11.4. Therefore, the TBR points to the
table position containing the address of the service routine. The last 4 bits in 0 guarantees at least 16 bytes
to store each routine.
When the instruction set level of the SPARC architecture is analyzed, we see that each instruction has a
fixed size of 32 bits. Memory operands may be 8, 16 or 32 bits. There are basic Load/Store operations,
classified according to the size and sign of their operands.
Arithmetic and Boolean operations include add, and, or, div, mul, xor, xnor, and shift. These are able to
change the PSR, according to the operation code used. Several jump instructions are available, including
relative jumps, absolute jumps, traps, calls, and return from traps. Other instructions include the movement
of the register window, NOPs, and read/write operations on the PSR.
Multiplication uses 32-bit operands, producing 64-bit results. The most significant 32 bits are stored in the
Y register, and the remaining in the ALU-RES register. Integer division operations take a 64-bit dividend
and a 32-bit divisor, producing a 32-bit result. The Y register stores the most significant bits of the divi-
dend. One ALU input register stores the least significant bits of the dividend, and the other, the divisor. The
integer result is stored in the ALU-RES register, and the remainder in the Y register. Most instructions are
carried out by the ALU, whose structure is depicted in the following figure. It includes two multiplexers
connected to the ALU, Multiplier/Divider unit and shifter.

Figure

3. Organization of the ALU.
There are two execution modes: User and Kernel. Certain instructions can only be executed in Kernel
mode. Also, the Base and Size registers are used only when the program is running in User mode.
The CPU executes under the supervision of the Control Unit . It receives signals from the rest of the processor
using 64 input bits (organized in 5 groups: the Instruction Register, the PSR, BUS_BUSY_IN,
BUS_DACK_IN, and BUS_ERR). Its outputs are sent using 70 lines organized in 59 groups. Some of them
include reading/writing internal registers, activating lines for the ALU or multiplexers. Also, connections
with the PC, nPC, Trap controller and PSR registers are included. Finally, the Data, Address and Control
buses can be accessed.
The memory is organized using byte addressing and Little-Endian to store words. The processor issues a
memory access operation by writing an address (and data, if needed) in the bus. Then, it turns on the AS
(Address Strobe) signal, interpreted by the memory as an order to start the operation. The memory uses the
address available and analyzes the RD_WR line to see which operation was asked. If a read was issued, one
word (4 bytes) is taken from the specified address and sent through the data lines. In a write operation the
address stored in the Byte Select register (lines BSEL0.3) defines the byte to be accessed in the word
pointed to by the Address register. If an address is wrong, the ERR line is turned on. A Data Acknowledge
(DTACK) is sent when the operation finished.
The system components are interconnected using a Bus (see Figure 4). The bus Masters use the BGRANT
(Bus Grant) and IACK (IRQ Acknowledgment) lines to be connected to the two devices with the following
lower and upper priorities. The device with the highest priority is connected to a constant "1" signal in the
BGRANT line. The BGRANT signal is sent to the lower priority devices up to the arrival to a device that
requested the bus. When the device finishes the transfer, a IACK is transmitted. Input/output operations are
memory mapped. Each device have a fixed set of addresses. Data written in those addresses are interpreted
as an instructions for a device. Fifteen IRQ lines (IRQ1.IRQ15) are provided, and devices are connected to
these lines. Higher priority devices are connected to lower IRQs.

Figure

4. Organization of the Bus.
Finally, an external cache memory was defined. The generic structure for the cache controller is defined in
figure 5. The design and implementation of these modules were not included in the original version of Alfa-
1. They were defined as an assignment done by undergraduate students, following the procedures that will
be presented in the following sections. In a first stage, the circuits were tested separately, different algorithms
were implemented, and finally the device was integrated into the architecture. Each model was developed
as a DEVS model that was integrated into a coupled model. This extension to the original architecture
(which not will be explained in detail) shows some of the capabilities for extensibility and modifiability
of Alfa-1.

Figure

5. Organization of the Cache memory.
3. IMPLEMENTING THE ARCHITECTURE AS DEVS MODELS
The architecture presented in the previous section was completely implemented using CD++. First, the behavior
of each component was carefully specified, analyzing inputs, outputs and timing for each element.
The specification also provided test cases. Then, each component was defined as a DEVS following the
specification. After, each model was implemented in CD++, including an experimental framework following
the test cases defined in the specification. Finally, the main model was built as a coupled model connecting
all the submodels previously defined. This model follows the design presented in the figure 1, and
its detailed definition can be found in [49].
Two implementations were considered. First, we reproduced the basic behavior of each circuit, coded as
transition functions. Then, some of them were implemented in detail using Boolean logic. The basic building
blocks were developed as atomic models, coupling them using digital logic concepts. In this way, two
different abstraction levels were provided. Depending on the interest, each of them can be used. Once thoroughly
tested, the basic models were integrated into higher level modules up to completing the definition of
the architecture. The following sections will be devoted to present some of the components implemented as
assignments done by our students. We show how different abstraction levels can be modeled, and present
examples of modifiability of Alfa-1.
3.1. Inc/Dec
As explained earlier, we use 520 general purpose registers organized as overlapped windows. In a given
time, only one window can be active. The Inc/Dec model is the component that chooses the active window
using a 5-bit CWP register. The models that are part of the CWP logic are shown in the figure 2. The CWP
is incremented or decremented, and its value (stored in a d-latch represented as another DEVS) is received
through the lines OP0-OP4. The outputs are transmitted through the lines RES0-RES4. This atomic model
can be defined as:
The behavior for the transition functions can be informally defined as follows:
{
When (x is received in the port y)
If increment
else decrement
dint() { passivate; }
{
If (RES0.4 is different to the last output) send RESP0.4 through the ports OP0.4;

Figure

6. Behavior of the transition functions for the INC/DEC model [50].
The FCOD value is used to tell if the value must be incremented or decremented. The ALU model is used
to do this operation. Here we can see that, when an external event arrives, the hold_in function is activated.
This macro represents the behavior of the DEVS time advance function (D), and it is in charge of manipulating
the sigma variable. This is a state variable predefined for every DEVS model, which represents the
remaining time up to the next scheduled internal event. The model will remain in the current state during
this time, after which an output and internal transition functions are activated. The hold_in macro makes
this timing definition easier. Passivate is another macro, which uses an infinite sigma and puts the model in
passive phase (hold_in(passive, infinite)).
The following figure shows the implementation of these functions using CD++. As we can see, the external
transition function (dext) receives five operands as inputs, together with a function code. According to this
code, the parameter is incremented or decremented. After, the model keeps the present value during a delay
related with the circuit operation. The output function (l) is activated, and if the circuit changed its state the
present value is transmitted. Then, the internal transition function (dint) passivates the model (that is, an
internal event with infinite delay is scheduled, waiting for the next input). The constructor allows to specify
the model's name, input/output ports, and parameters.
As we can see, the definition of a DEVS atomic model is simpler than the use of any standard programming
language. We have explained some of the advantages of using DEVS in section 1, but in this case, we can
see how to apply it to build our models. DEVS provides a interface, consisting of only four functions to be
programmed. This modular definition is independent of the simulator, and it is repeated for every model.
Therefore, one can focus in the model development. The user only concentrate in the behavior under external
events, the outputs that must be sent to other submodels, and the occurrence of internal events. Behavior
for every model is encapsulated in these functions, together with the elapsed time definition. Testing patterns
can be easily created, as the model can only activate these functions.
IncDec::IncDec( const string &name
string time( MainSimulator::Instance().getParameter(
Model &IncDec::externalFunction( const ExternalMessage &msg ) {
// Check the input ports, assigning the input values.
if (_FCOD == 1) {
for (int i=0;
Increment
Increment the va value useing the ALU
for (int
else
{ // Decrement
for (int i=0; i<=4; i++)
Decrement the v value useing the ALU
for (int
this->holdIn(active, preparationTime); // Schedule a delay for the circuit
return *this;
Model &IncDec::internalFunction( const InternalMessage & ) {
When the delay is consumed, activate the output
return *this ;
Model &IncDec::outputFunction( const InternalMessage &msg ) {
if (_RES[0]!=_OLD[0] || _RES[1]!=_OLD[1] || _RES[2]!=_OLD[2] ||
{
sendOutput(msg.time(), RES0, _RES[0] );
sendOutput(msg.time(), RES1, _RES[1] );
sendOutput(msg.time(), RES2, _RES[2] );
sendOutput(msg.time(), RES3, _RES[3] );
sendOutput(msg.time(), RES4, _RES[4] );
return *this ;

Figure

7. INC/DEC model definition: transition functions[50].
Once we have defined the atomic model, we can test it by injecting input values and inspecting the outputs.
An experimental frame can be built, including pairs of input/output values to test the model automatically.
In any case, we have to build a coupled model including the model to be tested. This is defined as follows:
preparation

Figure

8. INC/DEC coupled model definition [50].
These definitions follow the DEVS specifications. They are defined by its components (in this case, I_D, an
instance of the IncDec model) and external parameters. Then, the links define the influencees and translation
functions including the input/output ports for the model. In this case, the I_D model is related with the
Top model, using the input/output ports defined earlier.
3.2. RegGlob
This model defines the behavior of the global registers. It keeps the contents of the 8 global registers, allowing
read/write operations on them. Two auxiliary state variables, olda and oldb, store the last outputs,
and output signals are transmitted only for the bits that changed. This model is defined by:
{0,1}  CIN  {0,., 232-1 };
A sketch of this model was shown in the figure 2. As we can see, it uses three select lines (asel, bsel, and
csel) to choose two output registers and a register to be modified. An array of 32 integers (IN) keeps the
present values of the registers. The Boolean line cen (C enable line) is used to allow write operations. The
external transition function models the reception of an input. The function stores the desired operation according
to the signal received. Also, we store an input value in the number of register to be activated. A
new internal event is scheduled with a predefined delay, which models the circuit delay. If an external event
arrives before the end of the delay, the operation is cancelled.
Model &Regglob::externalFunction( const ExternalMessage &msg ) {
switch (msg.port()) {
case cen: line turned on
case reset: breset = (int)msg.value(); // Reset
Store the input lines
this->holdIn ( active, delay );
return *this;
Model &Regglob::internalFunction( const
if (breset) //
for (int i=0; i<255; i++) in[i]=0;
if (bcen)
for (int i=0; i<32; i++)
return *this ;
The i-eth line of the A input was enabled
Store the register number received
The i-eth line of the B input was enabled
Store the register number received
The i-eth line of the C input was enabled
Store the register number received
A reset signal was issued
// The 8 register (32 bit each) are deleted
// The write line was enabled
// Update the desired register
// Wait the next internal event
Model &Regglob::outputFunction( const InternalMessage &msg ) {
if (olda[i] != in[selecta*32+i]) {
this->sendOutput(msg.time(), aout,
if (oldb[i] != in[selectb*32+i]) {
this->sendOutput(msg.time(), bout,
return *this ;
// The register has changed
// Transmit it through the output line
// The register has changed
// Transmit it through the output line

Figure

9. RegGlob model definition: transition functions [50] .
The output function decides if the register has changed, querying olda and oldb which stores the previous
status of the A and B lines. When the register changes, its value is sent through the chosen output or B).
This model shows a more interesting use of the internal transition function. In this case, we are considering
the internal state to decide how the model must react. The internal transition function sees if the reset line is
activated. In that case, it clears the contents of every register. Then, if the cen line was activated, the value
of the chosen register is updated with the new input.
3.3. Other basic components
The architectural description is completed with other several DEVS models. We include generic aspects,
making a brief description of their behavior. We do not include the definition of the model's transition func-
tions, built as in the previous examples. Details of these models can be found in [49].
This circuit checks if the next window to be used will be overwritten. The component consists of a Window
Invalid Mask register. It returns the value of the CWP-eth bit of the WIM register.
{0,., 24-1}  RD_WR  {0,1}  RESET  {0, 1};
The memory is provided with three basic operations: read, write and reset. When a reset is issued, the
memory initial image is loaded. The processor writes an address in the bus, and signals the memory using
the AS signal when the address is ready. Then, a read/write signal is issued. The memory reacts according
with this signal, using an output after a time related with the memory latency.
The adder receives two inputs. Depending on the result, the Carry bit can be turned on.
These models are used to align data read/written during the Load/Store operations.
This model represents the behavior of the integer Arithmetic-Logic Unit. It is capable of executing the following
operations: add, sub, addx, subx (add/sub with carry), and, or, xor, andn, orn, xnor (negated and, or,
xor).
This group of models were included to provide the behavior of the most used Boolean gates: AND, OR,
NOT and XOR. They receive binary inputs, producing a result according to the desired operation.
AS, RD/WR, DTACK, ERR, RESET, BUSY  {0,1};
The bus interprets each of the input signals, providing outputs related with them. If a device which received
a 1 in the BGRANTin port needs to write data in the Memory, it writes a 0 in the BGRANTout port (no
smaller priority device is able to use the bus). Then, the device starts a bus cycle turning on the BUSYsig-
nal. The device writes the address to be accessed in the ADDRESSlines, and the data to be written in
DATA. After, the Byte Select Mask BSELto define which byte in the word is used. Finally, it turns on the
RD/WRout and AS lines to tell a Write operation was issued. When the memory receives the AS signal, it
executes a memory cycle that finishes when the DTACKout line is turned on. The device that issued the
operation receives this signal in its DTACKin line. When the cycle has finished, if BGRANTin is still
in 1, the device is able to transfer new data. Otherwise, it turns off the BUSYline, allowing a new bus operation
by other device.
This model is used in conditional jumps to decide if a branch must be executed.
It represents the CPU clock, which period can be configured.
This model is used to decide if access to the global registers or the register window is required. It returns the
kind of register (Register window/Global) and its number.
This model updates the nPC.
This model manages the actions that take place when an interrupt is received. The PIL (Processor Interrupt
lines mask the interrupts. If one or more IRQs whose numbers are greater than the PIL are received,
the interrupt must be serviced. Then, we see which one has the higher priority, and the TF (Trap Found) bit
is turned on. The TT (Trap Type) register is loaded according to the highest level interrupt.
This model represents a processor register, implemented as a d-latch. The EIN line enable inputs, and the
CLEAR line resets the register to zero.
This model is in charge of making multiplication and divisions, turning on the condition bits.
These models represent 2 or 4 input multiplexers. To choose them, we receive the 4-bit select signal whose
bit turned on marks which input will be sent through the output.
This model is in charge of managing the Register Window.
This model is in charge of implementing a shifter.
These models extend the sign of an operand of 13 or 22 bits to 32 bits.
This component defines which trap must be serviced, based on a priority system. One of the input lines defines
a non-masked trap. Other 7 bits are used to receive the number of a trap that can be masked. The
model returns a bit telling if the trap must be serviced, and 8 bits telling the trap type. The following table
shows the kind and priorities for each trap available:
Line Description Priority Trap Type
INST_ACC_EXCEP Instruction access exception 5 0x01
ILLEG_INST Illegal instruction 7 0x02
PRIV_INST Privileged instruction 6 0x03
WIN_OVER Window overflow 9 0x05
WIN_UNDER Window underflow 9 0x06
ADDR_NOT_ALIGN Address not aligned 10 0x07
DATA_ACC_EXCEP Data access exception 13 0x09
INST_ACC_ERR Instruction access error 3 0x21
DATA_ACC_ERR Data access error 12 0x29
DIV_ZERO Division by zero 15 0x2A
DATA_ST_ERR Data store error 2 0x2B

Table

3. Available traps
According with this table, the model analyzes which is the higher priority trap to be serviced. After a delay,
it sends the corresponding index through the output ports.
3.4. Control Unit
The Control Unit is in charge of driving the execution flow of the processor. As explained earlier, this
model uses several input/output lines. According with the input received, it issues different outputs, activating
the different circuits that were defined previously. Here we show part of its behavior. The specification
of the input/output sets is not included, because of its size (details can be found in [49]).
Model &UC::externalFunction( const ExternalMessage &msg ) {
else this->passivate();
} else if( msg.port() == DTACK ) {
} else if( msg.port() == CCLOGIC ) {
else
{ string portName;
int portNum;
nameNum( msg.port().name(), portName, portNum );
portName == "ir"
else
return *this;
Model &UC::internalFunction( const InternalMessage & ) {
return *this;
Model &UC::outputFunction( const InternalMessage &msg ) {
.
// See if the c_en line must be activated
// Read the Instruction Register and decode the instruction
} else {
else
// See branches
else
// Transmit the outputs
return *this;

Figure

10. Control Unit: transition functions .
As we can see, this model is activated by the occurrence of a clock tick. In this case, we check if the Control
Unit is waiting a result coming from the memory (waitfmc). In that case, we have nothing to do and the
model passivates. Otherwise, we register that a clock tick has finished. Other external inputs correspond to
the signal DTACK coming from the memory or the CCLOGIC (that is, an input arriving from a register).
We also recognize inputs for the Instruction Register (to store a new instruction to execute) or to the PSR
(to update the condition codes). The internal transition function records that when the Address Strobe is
up, we are waiting the end of a memory transfer. The main tasks of the control unit are executed by the output
function. As we can see in the description, the present input values are queried. Depending on the number
of clock tick in the instruction cycle, different output lines are activated.
4. THE DIGITAL LOGIC LEVEL
The abstraction level of several models was further detailed, letting the students to analyze the digital logic
level of the circuits. In the previous stage, the behavior of these circuits was defined by using atomic mod-
els. In this case, some of these models were built using atomic models representing the basic Boolean gates
(AND, OR, NOT, XOR). These models (described in the previous section) were used as components that
were integrated using digital logic. A coupled model representing the complete circuit replaced the old
atomic ones. These modifications, also done in course assignments, show the extensibility and modifiability
of Alfa-1. Two of the models implemented this way will be explained following.
4.1. CMP model
The CMP is a part of the Address Unit that detects addresses falling out of the program boundaries. The
model receives two inputs (through the lines OPA and OPB that are connected to the BASE and LIMIT
registers). As a result it returns the signal EQ if both values are equal, or LWif A is lower than B.

Figure

11. Sketch of the Address Unit.
The model is composed of several one-bit comparators, and coupling n of them generates n-bit compara-
tors. The following figure shows the basic components of this building block:

Figure

12. One-bit comparator [50].
This model is formally described by:
select >
where each is an atomic defining the corresponding
building block, presented previously in section 3.3.;
I { AND_n_1 }; I
I { Self }; I { Self };
I { AND_n_2 }; I { Self, NOT_n_1, AND_n_1, XOR_n}; and
Zij is built using I, as described earlier, and
The definition of this coupled model using CD++ is presented in the following figure:
in : OPAn OPBn

Figure

13. CMP coupled model [50].
First, we define the components of the coupled model (corresponding to the D set). Then, the input/output
ports are included (which are related with the X/Y sets defined earlier). Finally, the links show the model
influencees (which define the translation function). The select function is implicitly defined by the order of
definition for the model components.
4.2. Chip Selector
The Chip Selector (CS) circuit is devoted to determine if an address is between two others. The model receives
a 32-bit address, an Address Strobe (AS), and it returns a Boolean value telling if the address is between
the boundaries.
The MASK models provide two 32-bit sets (MAX Mask, MIN Mask) containing the boundaries of the address
to be compared. These models, defined originally as latches, were redefined using Boolean gates. The
input address for the chip selector is checked using two comparators, instances of the model defined in the
previous section.

Figure

14. Sketch of the Chip Selector [50].
The result obtained is transmitted through the ports LW and EQ for each of the comparators. Both outputs
are ORed for the first register (as we are interested to see if CMP A  MAX). After, the LW output of the
second register is inverted (as we are interested to see if CMP B  MIN). If the circuit is enabled, the result
obtained is transmitted.
components: MASMAX@MAS MASMIN@MAS CMPA@CMP CMPB@CMP and1@AND and2@AND or@OR not@NOT
Link: A31@top OPA31@CMPA A31@top OPA31@CMPB Link: A30@top OPA30@CMPA A30@top OPA30@CMPB
Link: out31@MASMAX OPB31@CMPA out31@MASMIN OPB31@CMPB
Link: out30@MASMAX OPB30@CMPA out30@MASMIN OPB30@CMPB
Link: out0@MASMAX OPB0@CMPA out0@MASMIN OPB0@CMPB
Link: AS ina@and2
Link: eq@CMPA ina@or lw@CMPA inb@or
Link: out@or ina@and1 out@not inb@and1
Link: out@and1 inb@and2
Link: out@and2 CS@top

Figure

15. CS coupled model [50].
5. SIMULATION RESULTS
The present section shows the results obtained when some of the models previously presented are simu-
lated. In the first case, we show the results of a value of 20 incremented by the INC/DEC model. The figure
shows the model inputs with their timestamps and the output values obtained.
The first step consists of giving an initial value to the circuit (in zero by default). The first event
generates an output only when the model phase changes. As the preparation time for the circuit
is 5 time units, this occurs at 00:00:05:000. The second input does not generate changes in the model
and no output is issued. In simulated time 10, a new input is inserted through the port OP2. As this value
changed, an output is generated at simulated time 15. The following 2 inputs are not registered because the
circuit keeps its present state. The last one increments the value in the register by inserting the value
through the FCOD port. The incremented value can be seen 5 time units after.
INPUT OUTPUT

Figure

16. Inputs and Outputs for the INC/DEC model.
The following example shows the execution of the RegGlob model under different inputs. At the instant 0,
the C enable line is activated, allowing write operations in the register. In this case, the register 4 is selected
(csel2=1, csel1=0 and csel0=0), and the number 0xFFFFFFFF is used as input
ter, in 00:00:01:00, the register 2 is selected (csel2=0 and csel1=1 ), and the number 0x55555555 is input
(cin0=cin2=cin4.=cin30=1, and cin1= The first value is stored in the register
4, and the second in the register 2.
INPUT OUTPUT
reset 1

Figure

17. Inputs/Outputs of RegGlob [50].
At 00:00:02:00, C Enable is deactivated. Therefore, the following operations are devoted to read registers.
We see that the value in the register 4 is sent through the A output (asel=2) and the register 2 is sent
through B (bsel=1). As a result, the values previously loaded are transmitted (that is, 0xFFFFFFFF in A,
and 0x55555555 in B). After, Reset is activated. Now, we try to read the register 4 at 00:00:05:00, and we
obtain the value 0x00000000.
The next test corresponds to the TrapLogic model. Here we can see the result obtained after turning on all
the trap bits. Due to this, we expect obtaining the index of the highest priority trap that is pending. The result
obtained after the delay time corresponds to the highest one of section 3.4: Data Store Error (whose
code is the result we obtained). Also, the Trap Found flag is turned on.
inst_acc_excep / 1.000
illeg_inst / 1.000
priv_inst / 1.000
win_over / 1.000
win_under / 1.000
addr_not_align / 1.000
data_acc_excep / 1.000
inst_acc_err / 1.000
data_acc_err / 1.000
div_zero / 1.000
data_st_err / 1.000
trap_inst / 1.000

Figure

18. Execution results for the TrapLogic model [50] .
Finally, we show two execution examples that are part of a complete program. All the examples were executed
in a Pentium processor (133 MHz), using the Linux version of CD++. The average performance for
this model was one instruction per second. The source code was translated to binary using the GNU MASM
assembler Linker. The executable is used as the initial memory image for the simulator. The first part of the
following figure shows part of a program written in assembly language. The second part presents the binary
code generated, together with the addresses for each instruction or data (one word each).
set 0x12345678, %r1
st %r1, [dest]
sth %r1, [dest+4]
sth %r1, [dest+10]
stb %r1, [dest+12]
stb %r1, [dest+17]
stb %r1, [dest+22]
stb %r1, [dest+27]
unimp
Initial Image
Addr. Memory Image
Final image
Addr. Memory Image
Load the register 1 with 0x12345678
Store it in the "dest" variable
Store the high half-word
Store the last byte
Interpretation
01001000 Store the register 1 in the address 72
01001100 Store the high part of reg. 1 in address 76
01010010 Store the high part of reg. 1 in address 82
01010100 Store the high byte of reg. 1 in address 84
01011001 Store the high byte of reg. 1 in address 89
01011110 Store the high byte of reg. 1 in address 94
01100011 Store the high byte of reg. 1 in address 99
00000000 unimp
00100000 "dest" variable (20: space character)Values

Figure

19. Storing a value in memory .
As we can see, this piece of code copies parts of the number 0x12345678 to certain memory addresses. We
show the translation of the binary codes based on the specification of the instruction set of the SPARC
processor. Finally, we show the memory image after the program execution. As we can see, the values
stored in memory follow the instructions defined by the executable code.
The following example shows the execution of part of another program. As we can see, the goal is to place
a 1 in a given address, and then shift this value to the left, storing the result in the following address. The
cycle is repeated 12 times.
set 1, %r1
cycle: sll %r1, %r2, %r3
stb %r3, [%r2+dest]
subcc %r2, 12, %r0
bne cycle
inc 1, %r2 !Delay slot
unimp
Initial Image
Addr. Memory Image
036 10000111 00101000 01000000 00000010
Final image
Load the register 1
Shift the value the
Store the result in
Repeat the cycle 12
Interpretation
with the value 1
number of times in r2
the variable dest
times
set <1>, 1
Take the register 1, shift and store in R3
Store in address
substract 12 to R0
Relative jump to address -2 words (40)
increment 1
unimp
Destination variable
A value 0x01 shifted 12 times

Figure

20. Shifting and storing results in memory .
Once the basic behavior of the simulated computer was verified, a thorough integration test was attacked.
As explained earlier, each circuit was defined together with a set of input/output values that were encapsulated
in an experimental framework. Once each of the models was tested, each operation in the instruction
set was checked. The procedure was developed using the verification facilities of DEVS, defining 17100
test cases. The mechanism consisted in creating an experimental framework, which executed an instruction
in the instruction set. The execution result was stored in memory, and a memory dump was executed, obtaining
the memory state after the execution. This value is checked against the value obtained when the
same program is executed in the real architecture, which is included in the testing experimental framework.
This procedure allowed us to find some errors derived of the coupled model. For instance, we could see that
the division instruction was not working properly. The generated test included the following sentences:
set 274543375, %r24 ! stores a value in register 24
set 13908050 , %r22 ! a second value is stored in the register 22
both values are divided and stored in r10
st %r10 , [dest] ! The result is stored in memory
unimp
value: .ascii "VALUE:"
dest: .word FFFFFFFF ! Result of Test 100

Figure

21. Testing routine for the UDIV instruction.
When this example was executed, the testing coupled model found an error:
Field Type Expected Found DIF
In this case, the destination should have stored the value 19 (274543375 divided by 13908050). Instead, we
have found the value 1, allowing us to see that one of the instructions had an unexpected behavior. In this
way we could find errors in some of the instructions that could be fixed. We also found errors in some addition
instructions, and in conditional jumps with prediction.
Finally, we show part of the execution of the simulator for the example presented in Figure 20. We show a
log file including the messages interchanged between modules. As in other DEVS frameworks, there are
four kinds of messages: * (used to signal a state change due to an internal event), X (used when an external
event arrives), Y (the model's output) and done (indicating that a model has finished with its task). The I
messages initialize the corresponding models. For each message we show its type, timestamp, value, ori-
gin/destination, and the port used for the transmission.
Message I / 00:00:00:000 /
Message I / 00:00:00:000 /
Message I / 00:00:00:000 /
Message I / 00:00:00:000 /
Message I / 00:00:00:000 /
Message I / 00:00:00:000 /
Message I / 00:00:00:000 /
Message D / 00:00:00:000 /
Message D / 00:00:00:000 /
Message D / 00:00:00:000 /
Message I / 00:00:00:000 /
Message I / 00:00:00:000 /
Message I / 00:00:00:000 /
Message * / 00:00:00:000 /
Message * / 00:00:00:000 /
Message * / 00:00:00:000 /
Message Y / 00:00:00:000 /
Message Y / 00:00:00:000 /
Message D / 00:00:00:000 /
Message X / 00:00:00:000 /
Message X / 00:00:00:000 /
Message X / 00:00:00:000 /
Message X / 00:00:00:000 /
Message D / 00:00:00:000 /
Message D / 00:00:00:000 /
Message D / 00:00:00:000 /
Message D / 00:00:00:000 /
Message D / 00:00:00:000 /
Message D / 00:00:00:000 /
Message * / 00:00:00:000 /
Message * / 00:00:00:000 /
Message * / 00:00:00:000 /
Message Y / 00:00:00:000 /
Message D / 00:00:00:000 /
Message * / 00:00:00:000 /
Message * / 00:00:00:000 /
Message * / 00:00:00:000 /
Message Y / 00:00:00:000 /
Message D / 00:00:00:000 /
Message X / 00:00:00:000 /
Message D / 00:00:00:000 /
Message D / 00:00:00:000 /
Message D / 00:00:00:000 /
Message * / 00:00:00:000 /
Message * / 00:00:00:000 /
Message * / 00:00:00:000 /
Message Y / 00:00:00:000 /
Message Y / 00:00:00:000 /
Message Y / 00:00:00:000 /
Message Y / 00:00:00:000 /
Message Y / 00:00:00:000 /
Message Y / 00:00:00:000 /
Message Y / 00:00:00:000 /
Root(00) to top(01) //
top(01) to mem(02) //
top(01) to bus(03)
top(01) to csmem(04)
top(01) to cpu(05)
top(01) to c1(64)
top(01) to dpc(65)
mem(02) / . to top(01) //
bus(03) / . to top(01) //
. to top(01)
cpu(05) to ir(06) //
cpu(05) to pc_add(07)
cpu(05) to pc_mux(08)
Initialize the higher level
components: memory, bus, CS, etc.
The models reply the next
scheduled event
The CPU initializes the components
Root(00) to top(01)
top(01) to cpu(05)
cpu(05) to npc(10) // Take the nPC
. to cpu(05)
1.000 to pc_latch(11) // Send to pc-inc
to pc_inc(13) // to increment
to pc_latch(11) // the value
Schedule the
activation of the
to cpu(05) // pc-inc model
Root(00) to top(01)
top(01) to cpu(05)
cpu(05) to pc(12)
to cpu(05) // Initial address
pc(12) / . to cpu(05) //
Root(00) to top(01)
top(01) to cpu(05)
cpu(05) to clock(45) // Clock tick
clock(45) / clck / 1.000 to cpu(05)
clock(45) / 00:01:00:000 to cpu(05)
clck / 1.000 to cu(43)
Root(00) to top(01)
top(01) to cpu(05) // Arrival to the CU
cpu(05) to cu(43) // And activation of the components
cu(43) / as / 1.000 to cpu(05)
Message Y / 00:00:00:000 /
Message Y / 00:00:00:000 /
Message Y / 00:00:00:000 /
Message D / 00:00:00:000 /
Message * / 00:00:10:000 /
Message * / 00:00:10:000 /
Message * / 00:00:10:000 /
Message D / 00:00:10:000 /
Message D / 00:00:10:000 /
Message D / 00:00:10:000 /
Message * / 00:00:10:000 /
Message * / 00:00:10:000 /
Message * / 00:00:10:000 /
Message Y / 00:00:10:000 /
Message Y / 00:00:10:000 /
Message D / 00:00:10:000 /
Message * / 00:00:20:001 /
Message * / 00:00:20:001 /
Message Y / 00:00:20:001 /
Message Y / 00:00:20:001 /
Message Y / 00:00:20:001 /
Message Y / 00:00:20:001 /
Message Y / 00:00:20:001 /
Message Y / 00:00:20:001 /
Message D / 00:00:20:001 /
Message X / 00:00:20:001 /
Message X / 00:00:20:001 /
Message X / 00:00:20:001 /
Message X / 00:00:20:001 /
Message X / 00:00:20:001 /
Message X / 00:00:20:001 /
Message D / 00:00:20:001 /
cu(43) / . to cpu(05)
Root(00) to top(01)
top(01) to cpu(05)
cpu(05) to pc_latch(11)
. to cpu(05)
Root(00) to top(01)
top(01) to cpu(05)
cpu(05) to pc_inc(13) // Update the nPC
. to cpu(05)
Root(00) to top(01)
top(01) to mem(02) // Memory returns the first instr.
mem(02) / dtack / 1.000 to top(01)
mem(02) / . to top(01)

Figure

22. Log file of a simple routine .
The execution cycle starts by initializing the higher level models (memory, CPU, etc. The message arrived
to the CPU model is sent to its lower level components: Instruction Register, PC Adder, PC multiplexer,
Control Unit, etc.
When the initialization cycle finishes, the imminent model is executed. In this case, the nPC model is acti-
vated, transmitting the address of the next instruction. As we can see, the 2nd and 5th bits are returned with a
value. That means that the nPC value is (as we see in figure 20, the program starts in the
address 32). The value is sent to the pc-inc model, in charge of adding 4 to this register. The update is finished
in 10:000, as the activation time of this model was scheduled using the circuit delay. At that moment,
a 4 value is added to the nPC, and we obtain the 3rd and 5th bits in 1 (res3 and res5), that is,
the next PC. After, the PC is activated and the value 010000 (that is, 32) is obtained. This is the initial address
of the program. The following event is the arrival of a clock tick, sent to the processor. The CPU
schedules the next tick (in 1:00:000 time units) and transmits the signal to the Control Unit, which activates
several components: a-mux, ALU, Addr-mux, IR,etc.
We finally see, in the simulated time 20:000, that the memory has returned the first instruction (compare the
results with the bit configuration in the address 32). The instruction is sent to the CPU to be stored in the
Instruction Register and to follow with the execution. The rest of the instruction cycle is completed in the
same way.
We are able to follow the execution flow of any program by analyzing this log file. To simplify the analysis
of results, we built a set of scripts using Tk, that lets the students to choose which components should be
considered. In this way, behavior of each of the subcomponents can be followed more easily, and the students
can analyze the behavior of the desired subsystem in detail.
6. CONCLUSION
We have presented the use of DEVS to simulate a simple computer. The models were based on the architecture
of the SPARC processor, which includes features not existing in simpler CPUs. The tools can be
used in Computer Organization courses to analyze and understand the basic behavior of the different levels
of a computer system. The interaction between levels can be studied, and experimental evaluation of the
system can be done.
The use of DEVS allowed us to have reusable models (in this case, Boolean gates, comparators, multiplex-
ers, latches, etc. DEVS also allowed us to provide reusable code for different configurations. We provided
different machines, one running the digital logic level and the other the instruction set, with different performance
in each case, depending on the educational needs. The concept of internal transition functions can
be used to improve the definition of the timing properties of each component, letting to define complex
synchronization mechanisms. Nevertheless, in this case, most timing delays were represented as simple in-
put/output relations.
We have met all the goals proposed. Alfa-1 is public domain, and has been developed using CD++ (which
is also public domain, and it was built using GNU C++). Therefore, the toolkit is available for its use in
most existing Computer Organization courses. We described several levels of the architecture (from the
Digital Logic level up to the Instruction Set). The assembly language level was also attacked using public
domain assemblers that generated executable code that could run in Alfa-1. We have easily extended the
components (for instance, including a cache memory that was not included in the first versions). We also
have modified existing components (implementing, for instance, Digital Logic versions of some of the cir-
cuits). Thorough testing could be done using an approach based on the construction of experimental frameworks
associated with testing functions. An experimental framework was also built for the final integrated
model.
The most important achievements were related with our educational goals. The whole project was designed
with detail as an assignment in a 3rd year Discrete Event Simulation course. The models were formally
specified, and the specifications were used by students in a Computer Organization course to build the final
version of the architecture. These students had only taken previous prerequisite courses in programming.
With only this knowledge the students were able to build all the components here presented. Final integration
was planned by a group of undergraduate Teaching Assistants (which also developed the Control Unit
and a coupled model representing the whole architecture showed in the Figure 1). Individual and integration
testing was also done by 2nd year students. Several of the modifications showed here were developed as
course assignments. These facts show the feasibility of the approach from a pedagogical point of view. Upper
level courses reported higher success rates and detailed knowledge of the subjects after using Alfa-1.
The tools can be obtained at "http://www.sce.carleton.ca/wainer/usenix". Different experiences can be attacked
using this toolkit. In the assembly language level, the students can use existing assemblers to build
executables that run in the simulator. A complete analysis of the execution flow at the instruction level can
be achieved by tracing the execution in the log file. The students can study the flow of a program and each
instruction with detail, starting from the memory image of an executable. The instruction cycle and signal
flow in the datapath can be easily inspected. Going deeper, we can see the behavior of those circuits implemented
in the digital logic level.
By extending or changing the existing instructions, and implementing the changes in the Control Unit, the
students can experience the design of instruction sets. This allows them to have practice in instruction en-
coding, and to relate instruction definition with the underlying architecture. The students also can include
new components (as it was showed with the cache memory example), change existing ones, or implement
them using digital logic.
The hierarchical nature of DEVS provides means to go deeper in the hierarchy. For instance, the logical
gates could be implemented defining the transistor level (which has not been implemented in this version).
We planned to build an Assembler and Linker, but the code generated by those provided by GNU for
SPARC plattforms executed straightforward. Nevertheless, the implementation of an assembler and linker
are interesting assignments that can be faced to complete the layered view applied in these courses. Also, a
debugger for the Alfa-1 architecture could be built, making easier to study the assembly language level.
At present, Alfa-1 is being extended by defining components of the input/output subsystem. Several in-
put/output devices, interfaces and DMA controllers will be simulated. Different transference techniques
(polling, interrupts, DMA) will be considered. Likewise, the implementation of different cache management
algorithms is being finished. Other tasks faced at present include the definition of a graphical interface to
enhance the use of the toolkit. The set of scripts mentioned in section 5 will be used to gather the results of
the simulations, and will be used as inputs to be displayed in graphical way. In this way, the study and
analysis of the different subsystems will be improved.
7.

ACKNOWLEDGEMENTS

I want to thank to the anonymous referees the detailed comments they made to this article. I also thank Prof.
Trevor Pearce at SCE, Carleton University, for his help with the final version. Sergio Zlotnik collaborated
in the early stage of this project, presented earlier in [51]. The research was partially funded by the Usenix
foundation and UBACYT Project JW10. It was developed while Gabriel Wainer was an Assistant Professor
at the Computer Sciences Dept. of the Universidad de Buenos Aires in Argentina.


--R

"Computer Architecture: a quantitative approach"
"Computer Organization and Design: the Hardware/Software Interface"
"Computer Organization and Architecture"
"Computer Systems Design and Architecture"
"Structured Computer Organization"
"The SimpleScalar Tool Set. Version 2.0"
"An interactive environment for the teaching of computer architecture"

"Notes on p86 Assembly Language and Assembling"
"An extensible simulator for the Intel 80x86 processor family"
"The MPS Computer System Simulator"


"The PROVIR Virtual Processor"

"Performance simulation of an ALPHA microprocessor"



"Talisman: fast and accurate multicomputer simulation"
"A Block-Oriented Network Simulator (BONeS)"

"Improved parallel architectural simulations on shared-memory multiprocessors"




"Experiences in simulating a declarative multiprocessor"
"Microprocessor Architecture Design with ATLAS."

"Designing Efficient Simulations Using Maisie"
HARMAN, T. "Mastering Simulink 4"
"ACSL Reference Manual"
COMPANY. "MODSIM II, The Language for Object-Oriented Programming"
"SIMSCRIPT: A Simulation Programming Language"
"Simulation Model Design and Execution"
"Hardware Description Languages: Concepts and Principles"
"The Verilog Hardware Description Language"
"Systems Engineering with SDL"

"ALFA-0: a simulated computer as an educational tool for Computer Organization"
"CRAPS: an emulator for the SPARC processor"
"An emulator of the Atari processor"

"Object-oriented simulation with hierarchical modular models"

"DEVS Theory of Quantization"
"New Extensions to the CD++ tool"



--TR
Object-oriented simulation with hierarchical, modular models: intelligent agents and endomorphic systems
Structured computer organization (3rd ed.)
Introduction to simulation with GPSS
Improved parallel architectural simulations on shared-memory multiprocessors
Execution-driven simulation of multiprocessors
Talisman
SM-prof
Computer organization and architecture (4th ed.)
An interactive environment for the teaching of computer architecture
Using the SimOS machine simulator to study complex computer systems
The SimpleScalar tool set, version 2.0
Performance and dependability evaluation of scalable massively parallel computer systems with conjoint simulation
Iterative design of efficient simulations using Maisie
GDEVS
Hardware Description Languages
Computer Systems Design and Architecture
Simulation Model Design and Execution
Mastering SIMULINK 4
Computer Architecture; A Quantitative Approach
The VERILOG Hardware Description Language
Theory of Modeling and Simulation
Performance Simulation of an Alpha Microprocessor
Microprocessor Architecture Design with ATLAS
The Augmint multiprocessor simulation toolkit for Intel x86 architectures
Experiences in simulating a declarative multiprocessor
Using the DEVS Paradigm to Implement a Simulated Processor
Documentation for the CHIP Computer System (Version 1.1)
PROTEUS: A HIGH-PERFORMANCE PARALLEL-ARCHITECTURE SIMULATOR
The MPS Computer System Simulator
simulation in education;computer organization;applications of DEVS methodology;DEVS models