CS-343 Assignment 4

Due Date and Submission

This assignment is due by midnight, April 14. Submit it by sending email to me at the address, vickery@babbage.cs.qc.edu. Be sure to put "CS-343 Assignment 4" in the subject of your email and to put your name/ID in the message body.

This is a programming project, and you may use any programming you like, with the following restrictions: If you use C or C++ your program must compile and run using the gcc/g++ compiler on Forbin, Linux, or Cygwin. If you use Java, your program must compile and run using either Sun's JDK (command line tools), IBM's Jikes compiler, or the Eclipse development environment (www.eclipse.org). If you use some other language, it must run on Linux and without the need for proprietary software; check with me before picking a non-Java/C/C++ language.

The Assignment

Your program is to simulate the ARC processor used in the textbook, essentially replicating the simulator available on the web. (Click here to get a copy of the simulator.) However you do not have to provide a graphical user interface for your simulator. You may do so for extra credit if you wish, but you will get the most benefit out of this assignment by concentrating on the design of the back end.

Your simulator will consist of a program loader, which will load machine language programs into the simulator's memory, the memory, the CPU's datapath, and the CPU's control unit. The machine language program files will be structured just like the .bin files generated by the textbook's ARC assembler: for each word of memory, there will be a line of text consisting of the address of the word, one or more spaces, and the contents of the word. Both the address and the contents will be given in hexadecimal.

Although your program does not need to have a GUI, it does need to run interactively. It will recognize the following commands entered by the user:

Development Steps

Do not try to write all the code at once. You will receive much more credit for the assignment if you develop your code incrementally and submit an incomplete program that works up to a point than if you submit the whole thing, but it doesn't work.

1. Implement the Quit command.

   Write code to read command lines from the user. Ignore everything the user types, except when a command line starts with the letter 'q,' print a message saying how many major and minor cycles were executed (which would be zero at this point), and exit.

2. Implement the Load command.

   Implementing the Load command will require you to recognize the Load command and to pick out the file name from the remainder of the line. (Use strtok() if you are writing in C or C++; use StringTokenizer if you are using Java.) You will also need to implement the simulated memory and to supply the read() and write() accessor methods for it. The main() method is to read the named file, a line at a time, and to use the addresses and values to make the calls to write(). After loading the file, print a message telling how many memory words were loaded into memory, the name of the file, and the lowest and highest memory locations that were loaded.

3. Implement the Memory command.

   Format the output into lines with up to eight words of memory per line. Display the address of the first word of each line at the left. Sample output, in response to a "M 1000 1010" command:

         00001000: 00112233 44556677 8899AABB CCDDEEFF
         00001010: FEDCBA98
       

4. Implement the REgisters command. You will have to implement the registers in much the same way as memory.
5. Implement the PC command.

   Print a message saying what the old value of the PC was, and what the new value is.

6. Implement the Step command.
7. Implement the RUn command.

Initial Code

The following files give you a skeleton version of the simulator. The code is available in two versions, one in C/C++ (C++ code that uses traditional C I/O and no classes, but which compiles without warnings or errors using a C++ compiler), and one in Java.

The C/C++ version was developed and tested in a Linux development environment, and you should be able to build it without modification on other Unix environments, including Cygwin for Windows. I used the free GNU g++ compiler and gmake utility for building and testing the code, with the environment variable CXXFLAGS set to "-g -Wall -Wwrite-strings" which provides good compiler checking for common programming mistakes. You can download it either as a zip file or as a compressed tar file using the following links:

• C/C++ Version in Zip Format
• C/C++ Version in gzipped tar format

The Java version was developed and tested using the Eclipse development environment (eclipse.org). It was built using JDK version 1.4, and aims more to parallel the structure of the C/C++ version than to optimize the use of Java features. It is available as a Jar file that contains all the .java and .class files. (You can execute this version using the command, "java -jar simulator.jar".) You can use either the jar command or a zip program such as WinZip to extract the .java files from the jar file.

• Java Version in a Jar File

Coding Help

First, here is more complete executable jar file for the Java version of the simulator. This version does not implement the RUN command. And the only type of ARC instruction it can execute is addcc. But running it, even if you are doing a C++ implementation, will give you an idea of what your simulator should do when the user enters commands.

This version of the simulator implements some features that are not required, but which make the simulator much more useful as a learning tool, I think. One feature is a new command, IR, which shows the contents of the Instruction Register, including a "disassembly" of the IR (translation from machine language back to assembly language). Also, the REgisters command allows you to assign a value to a register ("reg 5 = 1234a5a5" puts the value 0x1234a5a5 into register 5.) The PC command allows you to specify "+" as the new value, which adds 4 to the current value.

• Executable Jar File

After you download the file, you can run it from a command prompt using the command, "java -jar 2004-04-02_Simulator.jar" (unless you used a different file name when you downloaded it). Note that this jar file, unlike the previous one, does not contain source code. But I think both Java and C++ programmers can benefit by reading the description that follows. I plan to post C++ versions of the code shown below later.

You don't have to implement your simulator exactly the way I did it, of course. But for convenience (my convenience, that is), I'll provide my help in the context of how my code works.

First, because of the nature of Java, I needed a class to hold my do_minor() method. I called the class Processor, and it contains the following fields and methods:

do_minor()

This is the code we went over in class on March 31. The arguments are three register numbers, a 4-bit ALU function code, and a 2-bit memory-operation code. Here is the method declaration and the first few lines of code I used:

  //  do_minor()
  //  ----------------------------------------------------------------
  /**
   *    Implements one clock cycle.
   * 
   *    @param    A_Reg   Register to place on the A-Bus
   *    @param    B_Reg   Register to place on the B-Bus
   *    @param    C_Reg   Register to receive result from the C-Bus
   *    @param    alu_func  4-bit ALU function code from Fig. 6-4
   *    @param    mem_op    2-bit Memory operation (nop, rd, wr)
   */
    private static void do_minor( short A_Reg, short B_Reg,
                            short C_Reg, short alu_func, short mem_op)
                                       throws IllegalArgumentException
    {
      //  Validate Arguments
      if ( (A_Reg < 0) || (A_Reg > 37) )
        throw new IllegalArgumentException( 
                                "Invalid A Register (" + A_Reg + ")"); 
      if ( (B_Reg < 0) || (B_Reg > 37) )
        throw new IllegalArgumentException( 
                                "Invalid B Register (" + B_Reg + ")"); 
      if ( (C_Reg < 0) || (C_Reg > 37) )
        throw new IllegalArgumentException( 
                                "Invalid C Register (" + C_Reg + ")"); 
      if ( (alu_func < 0) || (alu_func > 15) )
        throw new IllegalArgumentException( 
                           "Invalid ALU Function (" + alu_func + ")"); 
      if ( (mem_op < 0) || (mem_op > 3) )
        throw new IllegalArgumentException( 
                         "Invalid Memory Operation (" + mem_op + ")"); 

      //  Compute the ALU result
      int alu_result = 0;
      switch ( alu_func )
      {
        case ALU.ANDCC:
          alu_result = 
                   ALU.do_andcc( registers[A_Reg], registers[B_Reg] );
          break;

do_minor() calls one of sixteen functions provided by class ALU to perform the ALU operation, it then calls Memory.memory_read(), Memory.memory_write(), or neither Memory function depending on the value of the memory-operation code. Finally, it has to change the register specified as the C_Reg operand (if it's not Register 0). In addition, it does some housekeeping, including keeping count of how many times it has been called. I also used some boolean variables that control what messages to print out; you can see how some of them are used in this code from the end of do_minor():

      //  Save result in destination register and display trace
      //  information.
      if ( 0 != C_Reg )
      {      
        registers[C_Reg] = 
                    (mem_op == Memory.read) ? mem_result : alu_result;
        //  Trace register changes
        if ( ( (C_Reg < 32) && Options.doTraceRegisters() ) ||
                                       Options.doTraceAllRegisters() )
        {
          System.out.println( "\tRegister " + C_Reg + " changed to "
                                + Utils.hexize(registers[C_Reg], 8) );
        }
      }
      if ( Options.doTraceRegisters() || 
           Options.doTraceAllRegisters() )
      {
        System.out.println( "\t" + ALU.formatCC() );
      }

      //  Update the count of minor cycles and return.
      numMinor++;
      return;
    }

The function Utils.hexize() in the above code is one I wrote to convert an int to its hexadecimal notation. It's like the %X format specifier in C's printf() library function. I don't know how you're "supposed" to do this in Java; there must be something like it in one of the core libraries, but I haven't found it. Here's my code:

  public class Utils
  {
    private static String hexTable = "0123456789ABCDEF";
    
    //  hexize()
    //  --------------------------------------------------------------
    /**
     *    Convert an int to a String of hex digits.
     * 
     *    @param  val Value to convert.
     *    @param  len Length of result.  Will be zero padded.
     */
      public static String hexize( long val, int len )
      {
        StringBuffer sb = new StringBuffer( "" );
        for (int i = 0; i < len; i++ )
        {
          sb.append( hexTable.charAt( (int)(val & 0x0F )));
          val >>= 4;
        }
        return sb.reverse().toString();
      }
  }

do_major()

Processor.do_major() implements the processor's fetch-execute cycle, and is essentially the same as the code I wrote in class:

  //  do_major()
  //  ----------------------------------------------------------------
  /**
   *    Fetches and executes a single ISA level instruction.
   * 
   *    @return   True if an instruction was executed successfully,
   *              and returns false if the op code was invalid, nop,
   *              or halt. 
   */
    public static boolean do_major()
    {
      try
      {
        fetch();
        decode();
        if ( execute() )
        {
          update_pc();
        }

        //  Update the count of major cycles and return.      
        numMajor++;
        return true;
      }
      catch (UnimplementedOpCodeException e)
      {
        System.out.println( "Unimplemented op code: " + 
                                                      e.getMessage());
        return false;
      }
    }

The step command simply invokes this method once. The run command would call it repeatedly until it returns false. The run command should probably also turn off some of the tracing options so there won't be too much output.

fetch()

This method simply calls do_minor() to read the next instruction from memory into the Instruction Register:

    private static void fetch()
    {
      do_minor( PC, R0, IR, ALU.AND, Memory.read );    
    }

decode()

This is code we worked on in class on March 31 (on the side board). The idea is to copy various fields from the IR into a set of variables that can be used by the various execution functions. I also used these field values in the disassembly code. Here are the fields I defined in class Processor:

    //  Decoded instruction fields
    public static short op       = 0;
    public static short op2      = 0;
    public static short op3      = 0;
    public static short rs1      = 0;
    public static short rs2      = 0;
    public static short rd       = 0;
    public static short i_bit    = 0;
    public static short simm13   = 0;
    public static short imm22    = 0;
    public static short disp22   = 0;
    public static short disp30   = 0;
    public static short cond     = 0;
    public static short op_code  = 0;

Then, decode() fills in their values from the current value of the IR:

      op      = (short)((registers[IR] >> 30) & 0x003);
      op2     = (short)((registers[IR] >> 22) & 0x007);
      op3     = (short)((registers[IR] >> 19) & 0x03F);
      etc.

An issue in the design of the ARC processor is that different instructions have different numbers of bits in their op codes. The call instruction uses just two bits (the op field), the sethi instruction uses 5 bits (the op and op2 fields), branch instructions use 9 bits (op, op2, and cond), and the others use 8 bits (op and op3). The decode() method fills in the "op_code" field with an 8-bit value consisting of the op and op3 fields, but it zeros out unused parts of the value. That is, if op is 01₂ (the call instruction), the rightmost six bits of the op_code field are set to 000000₂ regardless of the contents of bits 19-24 of the IR. Likewise, if op is 00₂, the rightmost three bits of op_code are set to 000₂ regardless of the contents of bits 19-21 of the IR. This way, each ISA instruction has a unique op_code value. What decode() does not do is to incorporate the cond field into the value of op_code. The reason for this is to be compatible with the way that the ARC processor in the textbook finishes decoding the five branch instructions as it executes them. This point is discussed further in the description of the execute() method, below.

update_pc()

The update_pc() method calls do_minor() to add 4 to the PC. It's a one-line method like fetch() was, and for efficiency it could just be replaced by the call to do_minor(). I made these separate functions to make the logic of do_major() clearer.

Looking at the code for do_major() you can see that the call to update_pc() is conditional on a boolean value returned by the execute() method. The reason for this is that the execution of some instructions (call, jumps, branches that are taken) compute the address of the next instruction to be executed themselves, so it would be inappropriate to add anything to the address they left in the PC. These instructions cause execute() to return false; the normal instructions return true so that update_pc() will be called before the next instruction is fetched.

Here's the code for update_pc():

  //  update_pc()
  //  ----------------------------------------------------------------
  /**
   *    Adds 4 to the Program Counter.
   */
    private static void update_pc()
    {
      do_minor( PC, R0, PC, ALU.INCPC, Memory.nop );
    }

execute()

The heart of this assignment is for you to work on the code that executes instructions. I set up a list of symbolic names for all the op codes listed in Figure 6-2:

    public static final short nop     = 0x00; // 00 000 000
    public static final short sethi   = 0x20; // 00 100 xxx
    public static final short branch  = 0x10; // 00 010 xxx
    public static final short call    = 0x40; // 01 xxx xxx
    public static final short addcc   = 0x90; // 10 010 000
    public static final short andcc   = 0x91; // 10 010 001
    public static final short orcc    = 0x92; // 10 010 010
    public static final short orncc   = 0x96; // 10 010 110
    public static final short srl     = 0xA6; // 10 100 110
    public static final short jmpl    = 0xB8; // 10 111 000
    public static final short ld      = 0xC0; // 11 000 000
    public static final short st      = 0xC4; // 11 000 100

Then I started implementing execute() with a big switch statement, as outlined is class. Here's the code for execute() with only the addcc instruction implemented:

  //  execute()
  //  ----------------------------------------------------------------
  /**
   *    Executes a decoded instruction.
   * 
   *    @return   True if PC is to be incremented, or false if not.
   *    @throws   UnimplementedOpCodeException if op code is not
   *              implemented.
   */
    private static boolean execute()
                                   throws UnimplementedOpCodeException
    {
      if ( Options.doTraceInstructions() )
      {
        System.out.println( Disassemble.dasm());
      }

      switch ( op_code )
      {
        case  addcc:
        {
          if ( i_bit == 0 )
          {
            do_minor( rs1, rs2, rd, ALU.ADDCC, Memory.nop );
            return true;
          }
          else
          {
            do_minor( IR, R0, temp0, ALU.SEXT13, Memory.nop );
            do_minor( rs1, temp0, rd, ALU.ADDCC, Memory.nop );
            return true;
          }
        }
        default:
        {
          throw new UnimplementedOpCodeException( op_code );
        }
      }
    }

Your job is to add cases for each of the possible op codes. The rule is that your code must do all its simulated work by making the appropriate calls to do_minor(). It can test the values of any fields in the IR and/or the condition code bits (I made these four public static boolean variables in class ALU), but it must not modify any register except by making the appropriate call(s) to do_minor(). And remember, the first three arguments to do_minor() are register numbers, not register values. And the other two arguments are a 4-bit ALU function code and a 2-bit memory operation code. Like the real processor, your simulator has to use the datapath described in the textbook to do all its work.

Strategy

I suggest you work on executing instructions in the following order:

• First, do the other arithmetic instructions, using addcc as a model. If you are interested, you can try adding a new instruction to your simulator: see the Example on page 212 of the textbook for a discussion of how to implement a subcc instruction. You will need to write some sample ARC programs and get the text's simulator to convert them into binary files for testing your simulator.
• The ld and st are very important for you to understand, so you should work on those even before you implement all the arithmetic instructions. Both of them require you to compute an Effective Address (EA) either by adding two registers together or by adding a register and an immediate operand. The EA is the address used for the memory read or write operation.
• The sethi instruction is used when a program needs to load a register with a value that won't fit into the 13-bit simm13 field. A common case is when a program needs the address of some data that is in a high memory location. When you work on this, you should think about some of those strange ALU function codes, like LSHIFT10.
• The jmpl and call instructions unconditionally change the PC, and would make sense to work on next. They are described on page 119 of the text. Look at the LSHIFT2 ALU function code for converting word offsets to byte offsets.
• I'm putting the branch instructions last because they are the hardest to do, at least using the technique developed in the textbook. But they are critical for writing real programs, so you might want to tackle them early on. (Try writing an ARC assembly language program that uses a loop to add up a list of data values stored in memory and you will see how important they are.) The issue is to use the cond field to determine what condition code bit(s) to test. In the textbook, the RSHIFT5 ALU function is used to shift the leftmost bit of the cond field to bit position 13 of the IR, and then shifts the other bits of the IR into position 13 by adding the IR to itself, which doubles its value, which shifts its bits to the left one place. This is ridiculously tricky code, done in the name of some hardware of the ARC that we haven't looked at yet that can test IR bit 13 but not other bits. The good news is that for your simulator it is perfectly fine just to examine the cond field's bits directly to decide what type of branch to do.