1. Introduction
1.1 Background
A Central Processing Unit has a fixed architecture comprised of several basic components. These components interact with program instructions during execution and reflect on the processor’s final speed and efficiency. In general these components cannot be changed once the processor has been manufactured in silicon.
A virtual processor with a user-definable architecture has the potential to allow the user to dry-run software under a specific architecture to see how it performs and operates. By making changes to the architecture of a processor, one may also see how this affects the operation of the software. A configurable processor opens up the possibility of emulating a multitude of real processors within a single package.
There are many parts of a processor, which reflect on its performance, however the UESA will concentrate on three main areas. The processor’s register set, which can be a composition of both data and instructions registers, the main store and the actual instruction set used by the processor.
1.2 Aims
This report describes an application which allows the user to define several aspects of a processor. The target audience of such an application may be those who are interested in testing how processor components affect program performance, those who are interested in the potential of emulating other architectures or those who wish to create their own.
Before working on this project, I had no previous experience with an object-orientated language such as Java, so it was also an opportunity for me to gain experience and knowledge in this area.
The original project specification is attached in Appendix A.
1.3 Overview
The background research for this report involved studying Java and understanding the basic concepts of a CPU. This report describes the product of that research and the work involved from analysis to testing.
Chapter 2 summarises the methodologies that were used in the creation of the software.
Chapter 3 describes the basics of a CPU and introduces the reader to the CPU terminology used throughout the report.
Chapter 4 discusses the suitability of Java as a programming language for this project and provides a brief history of Java and object orientated programming.
Chapter 5 describes the analysis and design of the project including the design of the CPU components, the graphical user interface (GUI) and the design and layout of assembly source code.
Chapter 6 discusses the implementation of the system and the methods used for testing.
Chapter 7 evaluates both the software and project, with the conclusions and recommendations being described in Chapter 8.
2. Methodology
This chapter describes the methodologies used from analysis to implementation. Section 2.1 describes why certain limitations have been imposed and section 2.2 describes the methodologies.
2.1 Imposing Limitations
It was important at the start of the project to lay down which aspects of the UESA should be configurable by the user and what limitations should be imposed. It was necessary to impose certain limitations for practical reasons and time constraints.
A major component of a processor’s architecture is its register set. The limitations on the register set would be based on common processor designs available today. For example, the Motorola 68000 series of processors have both general purpose data registers and address registers available to the programmer [7] whereas the ARM series of processors have no distinction between data and registers [6]. It was decided that it was important for the user to be able to define both Address and Data Registers. The next step was in deciding what the maximum number of registers should be. Again, this was based on real processors in use today. Both the ARM and 68000 series of processors have 16 general-purpose registers whereas PowerPC processors have 32 [9].
The CPU’s instruction set is another important factor, which obviously varies considerably from one architecture to another. The instruction set should be definable by the user, however the difficulty was in deciding how the instructions could be defined. Register Transfer Language (RTL) is a common method for describing data movement between a processor’s registers and memory. Initially it seemed quite appropriate for describing an instruction. The mnemonic would be chosen by the user and an RTL sequence would define its operation. It became clear however that the user would have to be limited to a generic subset of RTL. Specific sequences would lead to some rather obscure assembly.
Java was chosen as a suitable programming language, which I began to explore by means of working through textbooks and attempting example programs and exercises [3], [1].
2.2 Design Approach
The design approach involved three main steps.
- Step One: The Initial Design
- Step Two: Implementation of prototype source code
- Step Three: Integration with the main source code
Step one involved using a technical drawing package called Visio, which allows the user to visually describe software in a choice of notations. Diagrams were constructed in Visio to describe how different aspects of the UESA work and operated. Basic diagrams were drawn to show how registers and memory locations might be represented and flowcharts were constructed to describe the processes involved. This is particularly applicable in describing the routine for parsing an ASCII assembly source code file. The appearance of the graphical user interface was also designed visually with Visio using standard interface components. Although the source code for the GUI could be generated automatically from the designs, this method was not chosen, but instead the GUI was written manually. It was felt that in order to understand the GUI classes of Java correctly, it would be necessary to write the code manually.
Augmented Backus Naur Form (BNF) is a notation used for describing the structure of a programming language. This was deemed suitable for describing how the assembly source code should be written and in turn for describing what the parsing routine would expect. A description of the Augmented BNF notation is attached in Appendix B.
Step two dealt with the translation of the designs into prototype source code. Prototype source code is necessary because it allows the programmer to test the robustness of their designs, without the complications of the entire project and its code clouding the situation. It was also appropriate because of the uncertainties of how to implement the software due to the unfamiliarity of Java. At the same time, errors in the design or limitations within the programming language can be detected and the design re-worked if necessary. Prototype source code was developed on a class-by-class basis, with linking of the classes being done in step three. Samples of some of the prototype source code are attached in Appendix C.
Although Unified Modelling Language (UML) was not used to design the classes of the UESA, it is a useful language for describing the structure of the classes.
Step Three dealt with the final implementation of the prototype source code. Once the prototype class was proven to work satisfactorily, it was integrated into the main source code. Regular backups of the entire source code were made to a fileserver whenever new source code was implemented, or existing source code changed.
3. The Central Processing Unit
3.1 Introduction
The Central Processing Unit (CPU) is a piece of hardware, often incorporated onto a single chip or integrated circuit (IC). The CPU is responsible for executing instructions that form the basis of programs. Instructions are read sequentially from memory, decoded and executed. The CPU is often responsible for communicating with external devices called peripherals. There are technical differences between the terms CPU and processor, however in modern day use they have become almost synonymous.
3.2 Components of a CPU
There are many components of a CPU, all of which function together in order to execute programs and process data. This section will concentrate on those components which the UESA implements.
3.2.1 Main Store Memory
Although in the strictest of terms the main store memory is usually not part of the CPU, it is closely related to its operation. Any CPU would have little practical functionality without it. Main store memory is responsible for storing the instructions and data of programs awaiting processing and execution. Each instruction or item of data is stored in a specific location or across several locations, which are identified by unique addresses. The more memory a processor has at its disposal, the greater the size and number of programs which it can execute.
3.2.2 General Purpose Registers
Registers are simply small units of memory commonly around 32bits in size, integrated within the CPU. Processors often contain different registers designed for specific purposes, some of which may be manipulated by the programmer and others that are designed for the processor's internal use.
The UESA is concerned with two main types of general-purpose registers, both of which can be manipulated by the programmer. These are data registers and address registers. Their primary use is for the fast storage and retrieval of temporary data during program execution to help avoid the need to access the much slower main memory. Address Registers differ slightly in the fact they are designed to hold an address, or in other words a pointer to a memory location containing an item of data.
3.2.3 Instructions and Operands
All processors have an instruction set that forms the basis of programs executed by the processor. They are stored as a series of bits that can be broken down into two main fields.
- The operation code, commonly abbreviated to opcode
- Bits that describe the instruction’s operands.
The operation code is decoded by the processor and signifies the instruction to perform. Some processors have a fixed length operation code, which means all instructions are defined using the same number of bits; others use a variable length definition.
The second component of an instruction describes one or more operands. These are simply items of data, which are operated on by the instruction. It is important however to understand, the processor simply sees a sequence of bits. It is the interpretation of those bits and the context of the instruction, which describes whether that value represents an integer, memory location, or even a register.
Figure 3.1 – Diagram of a sequence of bits representing a theoretical instruction
Although this method of describing instructions and their operands is perfectly suitable for the processor, it is difficult and convoluted for the programmer to use and understand. In modern computer use the programmer rarely deals with the bits directly, but adopts a more abstract notation that is closer to English. This is called assembly language.
Each instruction is identified by a name, called the mnemonic, e.g. MOVE and a sequence of characters that describe the operands (see Table 3.2). Assembly code usually contains special commands called assembler directives. They are not so much concerned with the machine code but instruct the assembler to perform tasks such as attaching symbolic names to variables, constants or even locations within the source code. The assembler, which is itself a program, is responsible for translating the assembly code into the sequence of bits understood by the processor.
Assembly source code is not portable to processors from differing families, because it is simply an “English” representation of the machine code instructions, which vary considerably across different processor families.
Table 3.1 – An example of 68000 assembly source code
Instruction |
Description |
|
MOVE.L D3,D0 |
Moves the 32bit value contained in Data Register 3, to Data Register 0. |
|
NOP |
No Operation. Contains no operands and instructs the processor to do nothing. |
|
AND.L D1,D0 |
Performs a 32bit logical AND operation on Data Register 1 and 0 with the result being stored in D0 |
3.2.4 – Condition Code Register
The condition code register (CCR) sometimes called the program status register (PSR), contains a set of flags that record the outcome of an operation performed by an instruction. The exact flags that form the CCR vary across processors. The following are examples of the flags used by the Motorola 68000 processor [8].
- C – The last operation produced a
carry bit.
- Z – The last operation produced a
zero result.
- N – The last operation produced a
negative result.
- V – The last operation produced an
overflow.
- X – The last arithmetic operation
produced a carry bit
The flags are immediately set after instruction execution, and may be used by other instructions to alter the outcome of their operation. For example, branching instructions can use the Z flag to determine whether the branch should take place or not. This is analogous to an IF statement in a higher level language.
3.2.5 – Program Counter
The program counter is a special register that holds the address in main memory of the next instruction to be fetched. Once the instruction has been fetched, the program counter is incremented and the instruction is executed. Where an instruction turns out to be a branch and the branch is indicated to take place, the program counter is loaded with the address of the instruction to which the branch points.
The UESA does not use a program counter because instructions are not read from main memory. They are executed by directly interpreting the assembly source code, therefore a program counter is considered unnecessary. Instead, branches take place by specifying the absolute line number from where execution should continue.
4. Java
This chapter provides a brief description of Java; its history and the concepts that led to its creation.
4.1 What is Java?
4.1.1 History of Java
Java goes back to 1991 where a group of software engineers working for Sun Microsystems, wanted to design a language for use in consumer electronic devices [4]. Anything from videocassette recorders to cable TV switch boxes. Since these devices have little memory and frequently use a whole host of different processors, a language was required which was portable and produced tight code. They achieved this by designing a language, which compiled source code into byte code for a hypothetical machine. This machine is known as the Java Virtual Machine, or JVM for short. This intermediate code could then be run on any machine that had an appropriate interpreter.
Java exploded onto the scene in 1995 with the production of a web browser, now known as HotJava. Since then, its popularity has increased, especially in the production of glue software known as Middleware and Internet applications.
4.1.2 Overview of Java
Java is a fully object-orientated language, which bares many similarities to C++. However, Java is designed to be far more robust and simpler to use. Almost everything in Java is a class including many of the data types such as strings, which are in fact simply classes wrapped around the character primitive. Every class in Java originates from the super class called Object. Java does not use pointers like more traditional languages such as C, but reference variables are used to refer to structures and objects. Methods, which are synonymous to functions or procedures in other languages, must be contained within a class.
4.1.3 Compilation and Execution
In most languages the source code is compiled directly into a binary file, which can be executed only on the target platform. The binary file contains machine code instructions that are unique to the processor and function calls that are unique to the operating environment. Java differs significantly in this respect.
Java compiles source code into a form known as byte code for a virtual processor, with what could be considered as running a virtual operating system. The byte code is read into memory and interpreted by the Java Runtime Environment. The JRE effectively translates the byte code into a series of instructions understood by the native processor and operating system. In effect, any operating system that has a JRE is able to execute the Java “binaries” and no recompilation is necessary.
Software written in Java can either be designed to run as an application or an applet. An application generally runs on a user’s system, much the same as any other program. An applet is usually received from a remote server and executed, often as part of a web page. Certain restrictions are placed on applets for security reasons. These restrictions are enforced by the JRE and are not a programming convention. For example, applets cannot open files contained on the user’s machine.
5. Analysis and Design
This chapter describes the analysis and design of the final version of the User Extensible System Architecture. The design of the system was closely linked with its implementation as described in Chapter 6.
5.1 CPU Component Classes
This section describes the operation and layout of the classes, which form the CPU components of the UESA.
5.1.1 Data and Address Registers
The specification for the project stated that the size or width of the registers should be user-definable as either 16- or 32bit. In light of this, a register definition was required which could cope with different data sizes depending upon the users choice. The initial register design consisted of using an array of four bytes to represent one register. The number of registers would be set by creating an array whereby each element consisted of an array of four bytes, as mentioned. This effectively creates a two dimensional array, with one dimension holding the number of registers and the other holding the size of the registers. The thinking behind this was that it would allow 8-, 16- and 32bit register operations to be performed. The diagrams showing the original designs for memory and registers is attached in Appendix E.
Prototype source code was written to demonstrate how this method operates, by manipulating the individual bytes of each register. However, it soon became clear that this design had a major flaw. For example, putting a 32bit value into a register would require splitting the value into four bytes, requiring a complex set of calculations. In turn, these calculations would have to be performed multiple times for each instruction. The prototype source code is attached in Appendix C.
At this stage I began to explore object-orientated
programming in earnest and discovered it would be far more effective to
actually create a register class. The UML representation of this class is shown
in figure F.5 of Appendix F. The advantages of treating a register like an
object, as apposed to a primitive data type is that it can be accessed only by
using the specified methods.
This presents a standard interface to the register class in which the
underlying code of the methods can be changed without altering any other
classes. It also means that the internal workings of the register class cannot
be altered by malicious code. Another advantage is that the GUI component for
displaying the contents of a register can be contained within the register
class. This allows the GUI component to be automatically updated, whenever the
value of the register is changed.
Although address and data registers are formed from the same class, it is important to understand the difference between the two. The UESA treats data registers as a simple store, whereby their contents can be set or retrieved. Address registers are treated differently. Their contents are set in much the same way as that used for data registers, but they cannot be retrieved directly. Address registers actually hold a pointer to a memory location, so that any reference made to an address register, actually retrieves the contents of the memory location, pointed at by the register. This is analogous to address register indirect addressing as used on the 68000 [2]. Four public methods control the operation of the register.
- Register(): The constructor method that creates an instance of a register and initialises its value to zero.
- setValue(int n): Sets the value of the register and updates the GUI component to reflect the changes.
- getValue(): Returns the value of the register.
- getField(): Returns a reference to the GUI component, for inclusion in a window’s display.
The third advantage is that an array of register objects can be created to represent the entire number of registers chosen by the user.
The current register class only supports 32bit values due to time constraints, however an additional method could be inserted into this class and similar classes, to deal with 16bit values.
5.1.2 Main Store Memory
The initial design for representing the main store memory was much the same as that chosen for registers and based on the assumption that memory was byte aligned (see Appendix E).
Clearly, this would fall foul of the same problem concerning the conversion of data with differing bit lengths. In light of this, a memory class was constructed so that a single memory location could be treated as an object. The memory location class contains the following three public methods.
- MemoryLocation(): Creates an instance of a memory location and initialises its contents to zero.
- setValue(int v): Sets the contents of a memory location.
- getValue(): Retrieves the contents of a memory location.
An array of memory location objects can be used to represent the entire main store memory available to the CPU. Methods to deal with GUI components are not required for memory locations, because it is physically impossible to display all memory locations within a single window.
5.1.3 Condition Code Register (CCR)
In a real processor such as the 68000, the condition code register contains a series of bits whereby each bit represents one flag. As a side point, the CCR in the 68000 actually refers to a section of bits contained within the status register (SR). A similar approach was adopted for the CCR used by the UESA.
It was not necessary to design a class that represented a single flag, but rather the entire condition code register. The methods of the CCR class are responsible for changing the state of the individual flags. The CCR contains four flags based upon those found in the 68000. These are Carry (C), Zero (Z), Negative (N) and Overflow(V). The CCR class contains 17 methods that are summarised as follows. The “X” in the method names denotes the name of the flag i.e. C, Z, N, V
- CCR(): The constructor method that creates an instance of the class and initialises the all the flags.
- setXOn(): A series of methods that set the flags to the value one (true).
- setXOff(): A series of methods that set the flags to the value zero (false).
- getX(): A series of methods that returns the value of a flag.
- getXField(): A series of methods that return a reference to the flag’s GUI component for inclusion in a window’s display.
As with the registers, the GUI component for each flag is contained within the class. Each time the state of a flag is altered the GUI component is automatically updated to reflect those changes.
While code does exist to alter the state of the Overflow and Carry flags, the routines which would check for these occurrences have not been implemented. They have not been implemented, due to the uncertainty of how to check for the required states.
5.1.3 Instructions and Data
Instructions are instantiated by the instruction class, which contains three important pieces of information. Each instruction is formed from the mnemonic, its functions and its operands. Collectively, they make up an entire instruction definition. The mnemonic is simply held as a string, which is used for comparison against strings from the source code to identify an instruction.
The basic operation of any instruction can be broken down into a sequence of one or more basic functions (see section 5.3.3). For example, an instruction that adds two integers and leaves the result in a register can be represented by an “add” function followed by a “move” function. The instruction class holds an array of these “functions” which are processed in order when the instruction is encountered during the execution phase. The array itself is simply composed of constants. The value of the constant in an array element is a representation of the function to perform. During the execution phase, these constants are read from the instruction class and the relevant functions performed. See figure 5.1.
Figure 5.1 – Diagram to show the function array contained within the instruction class
The third point to consider is the operands associated with the instruction. These are contained within the instruction class in a similar manner to that used for the functions. An operand array also holds a series of constants that represent the data type of each operand (see figure 5.2). The operands are held in reverse order because a stack is used during the execution phase to hold the value of each operand, consequently the first value pulled from the stack is the value of the instruction’s last operand.
Figure 5.2 – Diagram to show the operand array contained within the instruction class
By reading the arrays shown above (figure 5.1 and 5.2) in the execution phase, we can define an instruction that performs addition on operands three and four. Then performs a subtraction with operand two and the result of the addition. Finally, the result is moved into the data register. For information on defining new instructions, please see section 5.3.2.
The instruction class contains six methods for instruction handling, as follows.
- Instruction(String n, int nops, int nfunc, int[] lst, int[] flst ): Creates a new instance of an instruction and initialises it.
- String n: A string representing the mnemonic for the instruction.
- int nops: The number of operands for the instruction.
- int nfunc: The number of functions for the instruction.
- int[] lst: The array of operands for the instruction.
- int[] flst: The array of functions for the instruction.
- getName(): Returns the mnemonic associated with the instruction.
- getNumOps(): Returns the number of operands the instruction has.
- getNumFunc():Returns the number of functions associated with the instruction.
- getOpList(): Returns the array containing the operand types.
- getFuncList(): Returns the array containing the functions.
5.2 Assembly Source Code
5.2.1 Source Code Layout
Source code layout was defined using augmented Backus Naur Form. The original BNF notation was devised by John Backus and Peter Naur and used to specify the language ALGOL 60 [5]. It was necessary to define how the source should be laid out because the parsing routine would need to process the source code based upon a set of rules. Figure 5.3 shows the augmented BNF definition. A description of the BNF notation used is attached in Appendix B.
Comment = “;” *OCTET
Mnemonic = 1*OCTET SP
Operand = *SP (“D”|”A”|”$”|”#”) 1*DIGIT *SP
Label = 1*(OCTET) “:”
Operandset = *(Operands “,”) Operand
Command = Mnemonic Operandset
Line = *SP (comment| Label | Command) EOL
Figure 5.3 – Augmented BNF definition of assembly source code.
This BNF definition can be summarised in English as follows.
- The End of Line (EOL) character can be either a carriage return followed by a line feed (CRLF), or a single line feed (LF).
- Comments must begin with a semi-colon followed by number of characters.
- A mnemonic must be at least one character in length and followed by a space. It cannot begin with a semi-colon.
- An operand can be preceded with zero or more spaces followed by one of the following characters, ‘D, A, $, #’, then a sequence of one or more digits. An operand can be succeeded with zero or more spaces.
- An operand set can begin with zero or more operands, which are each followed by a comma. It must end with one operand, not succeeded by a comma.
- A label must begin with a least one character and be terminated by a colon.
- A command must contain a mnemonic followed by an operand set.
- A line can begin with zero or more spaces and must contain only one of the following, a comment, a command or label, followed by the end of line character.
5.2.2 Parsing Assembly Source Code
The UESA executes programs by reading an ASCII source code file and processing it. A parsing routine was designed, based upon the BNF specification for the source code. The parsing routine sequentially reads lines from the source code and breaks them up into the relevant tokens. The parsing routine could be considered as a filter, whereby the tokens are filtered out at different stages for processing. The flowcharts for the design of the parsing routine are attached at the end of this section and a description of the flow chart notation is attached in Appendix D.
The parsing routine is also responsible for executing the instructions and setting the CPU’s initial state. The ParseSource class contains three public methods and 17 private methods. The private methods are only accessible by the ParseSource class for its own internal use. The main methods are summarised as follows.
- ParseSource(String fname, DefaultListModel model, Register[] al, Register[] dl, CCR concoreg): Constructor class which creates a new instance of the parsing routine.
- String fname: The name of the source code file to open for processing.
- DefaultListModel model: Reference to the list on the “Run Source” window for displaying output.
- Register[] al: The array of address registers.
- Register[] dl: The array of data registers.
- CCR concoreg: The condition code register.
- go(): Executes the source code until completion. (figure 5.4)
- step(): Executes one line of source code.
- parseComment(): Parses a comment and outputs it to the screen. (figure 5.5)
- labelError(): Displays an error for a label that has no name. (figure 5.6)
- ParseDefault(): Determines whether a sequence of characters is a mnemonic or a Label and calls the appropriate method. (figure 5.7)
- parseLabel(): Adds a label, along with the line numbers to a list for future reference. (figure 5.8)
- parseCommand(): Displays the current command being executed and displays an error if the command does not exist. (figure 5.9)
- parseOperandSet(Instruction cmd): Parses the operands associated with an instruction into individual operands. (figure 5.10)
- Instruction cmd: The instruction for which the operands should be parsed.
- parseOperand(): Converts an operand string into an integer and pushes it on the stack ready for execution. For example, an operand such as #15 would have 15 pushed on the stack and D5, would have five pushed on the stack. (figure 5.11)
- execute(Instruction cmd): Retrieves all the operands off the stack and executes the instruction.
- Instruction cmd: The instruction to be executed.
- memorydump(): Displays the contents of main store memory.
Figure 5.4 – Flowchart to show overview of the parsing routine
Figure 5.5 Flowchart to show overview of the parseComment() method.
Figure 5.6 – Flowchart to show overview of the labelError() method.
Figure 5.7 – Flowchart to show overview of the parseDefault() method.
Figure 5.8 – Flowchart to show overview of the parseLabel() method.
Figure 5.9 – Flowchart to show overview of the parseCommand() method.
Figure 5.10 – Flowchart to show overview of the parseOperandset() method
Figure 5.11 – Flowchart to show overview of the parseOperand() method.
Figure 5.12 – Flowchart to show overview of the parseSpace() method.
5.3 Instruction Set
As with any processor an instruction set is required in order to execute programs. The UESA does not have a built in instruction set as such (see the user documentation in Appendix G), but allows the user to define their own. This section describes the methods and notation used, by which instructions are defined and represented
5.3.1 Register Transfer Language
In an ideal situation, the user would be able to define the instructions at the machine code level, however this is considered impractical for several reasons. Not only is machine code difficult to understand, but it is impossible to program in by all, except the most adept of programmers and hardware engineers. The UESA is more concerned with the functionality of those instructions and so it is preferable to allow the definition of assembly instructions.
A suitable notation is needed to describe an instruction, which both the user can understand and the software interpret. Register Transfer Language (RTL) is a common notation for describing the operation of an instruction and the manipulation of data [2]. In light of this, it was deemed a suitable notation to use for instruction definition.
On further analysis it became clear that RTL was not as appropriate as it first seemed. Whilst it is perfectly adequate for describing an instruction, in its current form it is not as useful for instruction definition. For example, an instruction in assembly language that moves a literal integer into a data register, may have the following form, ‘MOVE D0, #20’. The first operand is the destination and the second is the source. This may be described in RTL using the following sequence, ‘[D0]<-20’. If we wanted to do the reverse and create an instruction based upon that RTL sequence, we would have an instruction which took no parameters and simply moved the integer 20 into D0. No parameters would be needed because there would simply be nothing to specify. The operation is inherent within the mnemonic. Clearly, this would allow the user to define some extremely obscure source code, which is entirely unintelligible. A more generic definition was needed. The notation used by the UESA is shown table 5.1, and is based upon an adapted subset of RTL.
Table 5.1 – Adapted subset of RTL as used by the UESA
Construct |
Description |
|
[A] |
An address register |
|
[D] |
A data register |
|
[M] |
The contents of a memory location |
|
[#] |
An integer literal. |
|
dest <- source |
Move the source to the destination |
|
- |
Subtract |
|
+ |
Add |
|
/ |
Divide |
|
* |
Multiply |
5.3.2 Instruction Definition
The user defines an instruction by entering the mnemonic as a string, followed by an RTL sequence. This sequence is then parsed by the UESA and an instruction is defined. The method which handles the RTL sequence is contained within the instruction definition window class and is called parseRTL(). Each construct in a sequence of RTL can be considered as either a functional construct i.e. it describes an action, or an operand construct, for example a memory location or value. An example of a function construct might be ‘+’ which indicates an ‘add’ function whereas ‘[D]’ indicates an operand, in this case a data register. The instruction class requires four groups of information to be able to create a new instruction. These are summarised below.
- The data type of each operand, such as whether it is a literal, data register or memory location. These are stored in an array, which we will refer to as the operand array.
- The functions to apply on those operands. These are also stored in a separate array, which we will refer to as the function array.
- The number of operands.
- The number of functions.
Whilst parsing an RTL sequence, each time an operand or function is encountered the corresponding variable is incremented and an entry made in the corresponding array. The order in which the entries are placed in the arrays is important because it determines the order in which they are executed.
Certain types of instructions cannot be defined by specifying an RTL sequence, for example branching instructions. For cases such as these, the UESA provides a set of internal instructions that may be used to perform branching. Details of these instructions are described in the user documentation attached in Appendix G.
The user is able to define instructions which make use of the four basic arithmetic operators, in conjunction with several addressing modes. The UESA supports three types of addressing modes. These are register indirect addressing, as mentioned in section 5.1.1, literal addressing, and memory direct addressing. Literal addressing simply refers to an absolute value such as the number five and memory direct addressing refers to the contents of a memory location.
When defining the RTL sequence for an instruction, there are certain pitfalls which need to be observed. A definition such as ‘[D]<-[D]<-[#]’ creates an instruction that moves a literal into two data registers. In actual fact it means move an integer into a data register, then move the contents of that register into another data register. However the outcome is the same. Nevertheless, you might be forgiven for thinking that the sequence ‘[A]<-[A]<-[#]’ creates an instruction that moves a literal into two address registers. This is not the case. As mentioned in section 5.1.1 address registers hold pointers. So in this case, the literal would be moved into the first address register, but the second address register would have the contents of the memory location pointed at by the first, inserted instead.
5.3.3 Instruction Execution
During the parsing phase, all operand values associated with an instruction are placed on the stack in preparation for execution. The values on the stack are all integers, it is the responsibility of the execution phase to determine how to treat them.
As mentioned in section 5.1.3, an instruction definition holds two arrays, one contains a list of functions to perform and the other contains a list the operands’ data types. It is important at this stage for the reader to understand the difference between the operand values on the stack and operand data types held in the array. The stack holds the true values of an operand, which have been obtained from the source code. However, the operand array simply describes the data types of those values.
The execution phase determines the first function to perform, by looking at the function array. The next step is pull two values from the stack, for use by the function, however these cannot be used directly. An integer on the stack could be a literal, or be referring to a particular data register. A method called resolveValue() is used which looks at the operand array and determines the data type for that integer. In the case where the integer is found to be a literal, then resolveValue() simply returns it for use by the function however, in the case where the integer refers to a data register, then it is the contents of that data register which is returned. A similar approach is used for all the possible data types. Any result produced from a function is placed back on the stack and may be used by the next function. A boolean variable is used to indicate that a pending result is on the stack for the next function to use.
The functions that are used by the execution phase are summarised below. All instructions used by the UESA are formed from at least one, or more of these functions.
- ADD: Adds two values together and pushes the result onto the stack.
- SUB: Subtracts one value from the other and pushes the result onto the stack
- MUL: Multiplies two values together and pushes the result onto the stack.
- DIV: Divides one value by another and pushes the result onto the stack.
- MOV: Moves a value from one location to another. If the value placed in the destination is a zero then the Z flag is other, if its negative then the N flag is set. Both flags are cleared otherwise.
- JMP: Branches to a specified line in the source code.
- SGT (Set if greater than): Sets the Z flag if the first value is greater than the second.
- SLT (Set if less than): Sets the Z flag if the first value is less than the second.
- BINZ (Branch if not zero): Branches if the last instruction did not produce i.e. if the Z flag is zero.
- BIZ (Branch if zero): Branches if the last instruction produced a zero i.e. if the Z flag is set to one.
- CMP (Compare): Sets the Z flag to zero if the two values are equal, otherwise the Z flag is cleared.
5.4 The Graphical User Interface (GUI)
The user interacts with the system by using separate frames or windows. The windows in their current state are shown in this section, whilst the original designs upon which they were based are in Appendix H.
The main window (see figure 5.5) is the first interface to appear when the UESA is executed. The main window contains information about the current user’s settings. A menu system is available which implements event handling and has the following options.
File Menu
- “Open Source…” displays the window shown in figure 5.5
- “Run Source” displays the window shown in figure 5.6
- “Quit” exits the UESA.
Configuration Menu
- “Define Memory Size” displays the window shown in figure 5.7
- “Define Registers” displays the window shown in figure 5.8
- “Define
Instruction Set” displays the window shown in figure 5.9
Help Menu
- “Help” displays a dialog box, telling the user to look at the HTML documentation.
- “About” displays the window shown in figure 5.10
Figure 5.4 – The main window GUI.
Figure 5.5 – The file requestor used for choosing the source code.
Figure 5.6 – The “Run Source” window.
Figure 5.7 – The “Memory Size Definition” window.
Figure 5.8 – The “Register Definition” window.
Figure 5.9 – The “Instruction Definition” window.
Figure 5.10 – The “About” window.
“Open Source File Requestor” (figure 5.5)
Displays a standard file requestor, which allows the user to select a file for processing by the UESA.
“Run Source Window” (figure
5.6)
All information regarding the execution of source code is displayed in the centre of the window, including the current line of source code being executed and any errors generated. The text fields down the sides of the window show the contents of the data and address registers respectively while the text fields in the lower half show the current status of the processor flags. The buttons on this window have the following functions.
- “Go!” executes the source code in its entirety until the end of the file is reached. All registers and processor flags are automatically updated as necessary.
- “Step Through” executes one line of source code each time the button is pressed. All registers and processor flags are automatically updated as necessary.
- “Show Memory” performs a memory dump by creating a table of all memory locations and their contents.
- “Reset” clears the contents of all register, memory locations and processor flags and resets the current execution position back to the start.
- “Close” simply closes the “Run Source” window.
“Define Memory Size” (figure 5.7)
Shows the current number of memory locations available to the CPU and provides a text field in which the user can enter a new value. Memory is shown in blocks because each location is currently 32bits wide.
“Define Registers” (figure 5.8)
Shows the current number of data and address registers. Text fields are provided for the user to change these values. The radio buttons were intended for the user to be able to change the size of the registers and in turn the size of a memory block, however this has not been implemented and so they are redundant. The “OK” buttons accepts any changes, whilst the close button discards any changes.
“Define Instructions” (figure 5.9)
This window handles the definition of new instructions. The user enters the mnemonic in the first text field and an RTL sequence in the second. The instruction is submitted by pressing the “Add Instruction” button.
“About” (figure 5.10)
Displays a brief description of the program, its current version and the author’s name.
5.5 Comments on the classes
In general, the classes that were used to form the CPU components were well designed with a specific purpose in mind. However, the design of the GUI classes did not use such a clean approach. There were several reasons for this. The code for the interface was written manually and required a certain degree of experimentation, especially with regards to component layout. Secondly the swing classes used for interface creation are complex yet powerful and so certain methods were changed in favour of others.
The class used for the parsing and execution of source code
was by far the most difficult to write and is perhaps far more unwieldy that it
needed to be. This has led to a certain amount of code duplication.
6. Implementation and Testing
Implementation and testing was closely linked with the analysis and design of the software as described in Chapter 5. This chapter describes the implementation process used.
6.1 Implementation
Implementation was done by integrating the prototype source into the main code on an incremental basis. The project was broken into smaller tasks that could generally be completed within a few days. Each task, usually consisted of a single class that performed a specific function. The order in which the tasks were attempted was related to their complexity and grouping. The simpler programming tasks were generally attempted earlier, whilst the more sophisticated tasks were left till later in the project. The grouping relates to whether a specific task was considered a CPU component, a GUI component or some glue code that acts as an interface between the different classes. The CPU component programming tasks were considered the core of the project and attempted first. The GUI tasks were constructed later in order to wrap around the component code effectively. It was felt that had the reverse approach been adopted, then significant alterations in the GUI code would have to be made in order to accommodate the core of the program. Immediately after integration of the prototype source, into the main code, the program was compiled and tested to see how it performed.
Certain risks can be identified with using this approach. Firstly, any alterations that modified existing and previously tested code, could introduce errors into the program. However, this risk was kept to a minimum because new code was usually added in the form of a class and required little, if no modification to the existing code. Any errors which were identified could be tracked down to the new class and amended. Regular backups of the entire project were stored on a fileserver, which ensured that a previous working copy could be retrieved if necessary.
Almost all the requirements laid down in the original specification were implemented. The exceptions were the ability to alter the size of registers to handle values of differing bit lengths and the C and V flags, which whilst partly implemented are redundant in use.
6.2 Testing
Testing took place whenever significant changes were made to the project. Most of the testing was done using the development platform, which was JDK 1.2.2 running under Windows 98. However limited testing was done using JDK 1.2.1 running under Linux to check for consistency across different operating systems.
GUI event handling was tested immediately after implementation by activating all menus and buttons under a variety of circumstances. Additionally, all keyboard shortcuts relating to the menus were tested.
The software’s operation was tested by using the four programs which are shown in Appendix I. The first program datamovement.s, tests the flow of data between the components of the CPU, to ensure that both the components and the move function, work as expected. The program operates by simply moving literals into registers and memory locations as well as moving values between these components. The program also demonstrates address register indirect addressing, absolute address and literal addressing.
The second program called arithmetic.s, tests the four main arithmetic functions used by the UESA. These are addition, subtraction, multiplication and division. The result of each instruction is placed in a consecutive data register, to verify their validity.
The third program called flag.s, was used to test two of the processor flags, Z (Zero) and N (Negative). Arithmetic instructions are used to produce a result which alters the state of these flags. A move instruction will also alter the state of these flags, but is obviously dependant the on the value being moved. This program also tests the three main equality functions, which are CMP (Compare), SGT (Set if Greater Than) and SLT (Set if Less Than). These equality functions alter the state of the Z flag to indicate the truth of the instruction. For example, testing two values for equality will set the Z flag to ‘ON’ if they are indeed equal, otherwise it will cleared.
The fourth program called factorial.s, tests several areas of the instruction set. Firstly, it proves that the UESA can be used to generate useful results, by calculating the factorial of five. Secondly, the factorial is calculated in a functional manner, which means that it exploits branching as part of the calculation. Finally, the movement and arithmetic functions are tested, because they are an integral part of the calculation.
These four programs are supplied with the system so that the user can verify its operation. All four programs make use of the pre-defined instruction set which has been implemented purely for the user’s convenience.
Several user programs have been tested on the system throughout its development, however it is impossible to test every combination of instructions. Nevertheless, programs were written which tested the robustness of error reporting with malformed programs. In general this is quite successful, with most problems generating an error response. For example, warnings are given for references to out of range registers and memory locations, or malformed labels. An error is not issued for every possible problem, however the worst case scenario is that the program being executed simply terminates prematurely. The reason for this early termination is because the cause is not immediately obvious to the system.
The testing phase did in fact pick up one fairly serious bug. The bug was to related to the move function which can be used as part of an instruction definition. The move function worked fine, providing it was used as the last function in an instruction definition. For example, and instruction which uses the move function as its last function may be defined as:
[D]<-[#]+[#]
Add two literals and move the result into a data register.
However, problems were encountered if the move function, was used in the middle of an RTL construct, as shown below.
[D]<-[D]<-[D]<-[#]
Moves a literal into three data registers.
The effect was that the literal would only be moved into one of the data registers, instead of all three. The cause of the problem, was that the move function did not push any result back onto the stack. So consequently, any consecutive functions would be lacking one of their values and therefore would not work correctly. This has now been fixed.
7. Evaluation
This chapter evaluates the software product and the project as a whole.
7.1 The UESA in Operation
The user guide for the UESA is attached in Appendix G, which is actually a printout of the supplied HTML documentation.
The user interacts with the system by using a GUI that exploits the interface components with which most people are familiar. The user is guided through the system by using a series of menus and buttons, which can be activated by the keyboard and mouse, whichever is their preferred choice. Documentation is provided in a standard cross-platform file format (HTML), which describes how to install and use the system.
The simulator successfully executes the supplied example programs shown in Appendix I. During program execution, the user is provided with a view of the CPU which changes dynamically during program execution. A program can be executed in its entirety, to view the final results, or stepped through to monitor the execution of each instruction. The user can choose to display a memory dump, even during program execution, showing the contents of all memory locations.
The user can define new instructions within the program, however there is no facility to save the instruction set. All changes are lost, once the program quits. Instructions are defined using RTL and a list is presented showing all currently available instructions. The user is warned about any attempt to duplicate an instruction mnemonic.
The system has been thoroughly tested and in general seems to be robust. At the time of writing, I do not know of any serious problems with the system. There is a slight problem with the graphic on the main window, it is not always displayed immediately when the window first opens. However, this was considered ephemeral to project and therefore not fixed.
7.2 Evaluation of the project
More time could have been devoted to the design of the system, with the original design of classes being specified in UML before their implementation.
The use of flowcharts for describing the processes involved in the parsing routine are perhaps too abstract from the actual source code, which has led to a certain amount of code duplication. However, it is believed that using a more concrete notation would have had a detrimental effect on the project, due to time constraints. This in turn would lead to less of the project reaching the implementation stage.
I believe I have gained a lot of experience in programming and computer architecture, by working on this project. Before the project I had virtually no experience with an object-orientated programming language, and now feel confident with both the methodology and terminology. In addition, I have learned an entirely new programming language as a by-product of the work.
8. Conclusions and Recommendations
8.1 Conclusions
A CPU simulator with an extensible architecture has been successfully demonstrated and proven to work. The system allows the user to define a complete instruction set as well as several components of the CPU. The system has a functional user interface which can be executed on a variety of platforms.
The system successfully executes source code contained within a text file and displays the results to the user. Source code can be executed on a step-by-step basis with the components of the CPU visible so that the user may monitor its effect. A facility is provided to display a memory dump for the user to view memory contents. The system is supported by an HTML help system, which can be viewed on any platform and is attached in Appendix G.
The system has been implemented as a Java application which has been proven to work under two operating systems and two versions of the JDK. The system is therefore considered to be portable as well as satisfying most of the project objectives.
Java has been found to be a powerful and robust language. However, it does have problems, which are inherent because of its portability. For example, using files can be quite a convoluted process because it has to deal with file system conventions for any computer, as well as a whole host of character sets. Certain constructs are also far too limiting, for example the switch statement, which leads to excessive and sometimes repetitive coding.
8.2 Recommendations
The current implementation has no method for the storage and retrieval of architectures defined by the user. Any architecture defined, including the instruction set, is lost once the program exits. Clearly, a way of saving and loading would need to be implemented for any future version.
Whilst RTL, or at least a notation based on RTL has been proven to work effectively for instruction definition to a certain degree, it has several awkward limitations. Firstly, any instruction that is defined using RTL has a restricted operand set.
That is, all the operands must of be of the data types, expressed in the RTL sequence. If the sequence specifies a literal, then an address cannot be used instead. A far cleaner method would be able to define the basic operation of the instruction, with the operand values and their data types being recognised at run-time. Secondly, certain types of instruction cannot easily be expressed within the scope of RTL. For example, an instruction which tests a pair of values for equality, then sets a processor flag to indicate its truth. For any similar project, it would be far more preferable to create a new notation for instruction definition, which would address these concerns.
The interface used to define instructions lacks two features that would be convenient for instruction definition. Once a new instruction has been created, there is no way to remove it from the instruction set. You are effectively stuck with it, until the system exits. There is also no method by which an instruction’s definition can be edited which means that mistakes cannot be rectified.
The current method of performing a branch, by specifying an absolute line number, is cumbersome an awkward to use. In any program of significant size, it would become entirely impractical. Changing one single line of code, would have the potential of completely destroying the flow of the program. The original intention was to use labels, however this could not be completed in the time available. Even so, a better solution would be to store the program in memory, and implement a real program counter.
A fully-fledged user extensible architecture would have to take into consideration far more factors than have been here. The processor clock frequency could be user-defined, cache memory could be configurable and even the ability to design multiple processors working in tandem.
9. References
|
[1] |
Bishop, Judy |
Java Gently: Programming Principles Explained, Addison-Wesley |
|
[2] |
Clements, Alan |
The Homepage of Alan Clements http://www.clements.flyer.co.uk/ |
|
[3] |
Horstmann, Cay S. & Cornelll, Gary |
Core Java 1.2: Volume 1 – Fundamentals, Prentice Hall, 1999 |
|
[4] |
Horstmann, Cay S. & Cornelll, Gary |
Core Java 1.2: Volume 1 – Fundamentals, Prentice Hall, 1999, Pages 2, 14-15 |
|
[5] |
- |
BNF Description, Manchester
University http://www.cs.man.ac.uk/~pjj/bnf/ebnf_bnfwebclub.html |
|
[6] |
- |
Embedded Electronics Magazine http://www.chipanalyst.com/tech_lib/embedded/esamples_c7.html |
|
[7] |
- |
M68000 8-/16-/32bit Microprocessor User’s Manual, Motorola Corporation, Section 2.1.1 |
|
[8] |
- |
M68000 8-/16-/32bit Microprocessor User’s Manual, Motorola Corporation, Section 2.1.3 |
|
[9] |
- |
PowerPC 604 RISC Microprocessor User’s Manual, Motorola Corporation & IBM Microelectronics, 1994, Page 21. |
(b)
(c)
(b)
(c)
(b)
(b)
(c)
(b)
(b)
(b)
(c)
