CS 3853 Fall 2010, Homework 2

1. Textbook problems: Do problems 1.12, 1.13, and 1.14 from pp. 61--62 in the textbook. Also, do the following problem:

   Consider two machines, machine A and machine B. For both machines, all instructions except for mispredicted branches take one cycle. Mispredicted branches take one cycle plus an additional misprediction latency. Machine A has a clock rate of 1.0 GHz and a misprediction penalty of 5 cycles. Machine B has a clock rate of 2.0 GHz and a misprediction penalty of 20 cycles. Branches are 25% of all instructions.

   1. With static branch prediction, 80% of branches are predicted correctly.

      Which machine is faster, machine A or B? What is the speedup?

   2. With dynamic branch prediction, 95% of branches are predicted correctly.

      Which machine is faster, machine A or B? What is the speedup?

2. RISC processor emulation: Simulation is a very important part of computer architecture research. Architecture concepts are often too high-level to allow for a simple implementation in hardware, so we simulate our ideas in high-level languages like C and Java with varying levels of detail. The most simple level of detail is functional simulation also known as emulation, where we simulate an instruction-set architecture by executing each instruction in a program one by one, updating emulated memory locations and registers.

   For this problem, modify the xocolatl emulator to include several new MIPS-like RISC instructions. For this problem, you will take the following steps:

   1. Download the xocolatl emulator for the MC6809 processor. Unpack it into your home directory on one of the UTCS machines with tar -xvzf xocolatl.tar.gz .
   2. Modify the file xocolatl/src/projects/risc_isa.java to emulate the RISC MIPS-like ISA described below. (The current version of that file reads one instruction at a time, printing its hexadecimal value.) The emulator should fetch and execute instructions through the program counter one by one, incrementing the program counter by 4 after each fetch (and also updating the program counter correctly for branches).
   3. Compile xocolatl with your modifications and run it with two script files: fib.txt and phi.txt. These files will test your emulation of the RISC instructions. The first file computes the Fibonacci numbers using 32-bit integers, then prints them out. The second file computes the Fibonacci numbers and an approximation of the Golden Ratio, then prints them out.
   4. Turn in your code and the output generated by running each script.
   Your code should produce no output; it should only move values around in memory and do computation. If you like to have debug output, please disable it in the code you use to turn in your assignment.

   Compiling and running xocolatl

   To compile xocolatl together with the code you have written in xocolatl/src/projects/risc_isa.java, change to the directory xocolatl/src and type make. The first time through, it will make a number of extra programs and files related to the run-time environment of the emulator.

   You can run the scripts for this assignment by copying them to your xocolatl/src/ directory and typing the following at the command line:

   java -cp .:projects xoco -s fib.txt -heof
   java -cp .:projects xoco -s phi.txt -heof
   

   The -cp option for the java JVM tells it to look for compiled class files in the current directory as well as the projects/ directory, where your code will be compiled.

   Note: If you are running the emulator after having logged in remotely, you might need to set your DISPLAY environment variable to ":0.0" to fool the JVM into believing it has a screen before it can run. See the README file in xocolatl/ for information about using the video display option.

   For this problem, you will be implementing a MIPS-like RISC instruction set architecture.

   Your interface to xocolatl

   xocolatl is a somewhat complex emulator with RAM, ROM, input, output, and the full 6809 instruction set. Nevertheless, for this assignment our interface to the xocolatl emulator is small, since all we need to be able to do is load a byte, store a byte, and know where to begin fetching instructions. When a certain opcode is executed by the emulator, it hands control over to your code. These elements of the emulator are relevant to your assignment:
   • xoco.pc is the program counter, i.e., the address where the currently-executing instruction can be found. You should load bytes from and modify xoco.pcas you go through instructions.
   • xoco.load (int x) is a method that loads a byte from the emulated machine's address x. Use this method to read both instructions and values for emulated "load" operations for your emulator.
   • xoco.store (int x, int y) is a method that stores the value y to the emulated address x as an 8-bit integer. Use this method to store values that your emulated "store" operations generate.
   Once your emulation is finished, make sure the value of xoco.pc is set to one byte beyond the last instruction your emulation executed, so control can return back to the proper address in the emulated 6809 program.

   Instruction Set Architecture

   The MIPS-like RISC ISA has the following properties:
   • Values are represented in big-endian. There are two data types: 32-bit integers and 64-bit floating point numbers.
   • There are two sets of registers: one for 32-bit integer registers and one for 64-bit floating point registers. Each set of registers has 32 registers. When execution begins, all registers start out with the value 0.
   • Instructions are 32 bits. Number these bits from 0 to 31, with 31 being the most significant bit. Each instruction is divided into 5 fields:
     1. Bits 31-24: An 8-bit opcode indicating the type of instruction.
     2. Bits 23-19: A 5-bit register number for a destination register (rd)
     3. Bits 18-14: A 5-bit register number for the first source register (rs)
     4. Bits 13-9: A 5-bit register number for the second source register (rt)
     5. Bits 8-0: A 9-bit two's-complement (i.e. signed) immediate value (imm).
   • The following instructions are defined:

     MIPS-like RISC ISA description

     Mnemonic	Opcode	Meaning
     L.D	0x20	Load 64-bit floating point (FP) rt register from address at (integer) register rs plus imm
     S.D	0x21	Store 64-bit FP register rt to address at (integer register) rs plus imm
     DIV.D	0x24	Divide FP register rs by FP register rt, placing result in FP register rd.
     MUL.D	0x25	Multiply FP register rs by FP register rt, placing result in FP register rd.
     ADD.D	0x26	Add FP register rs to FP register rt, placing result in FP register rd.
     SUB.D	0x27	Subtract FP register rt from FP register rs, placing result in FP register rd.
     ADDI.D	0x28	Add FP register rs to imm, placing result in FP register rd.
     ADDI	0x30	Add integer register rs to imm, placing result into integer register rd.
     ADD	0x31	Add integer register rs to integer register rt, placing result into integer register rd.
     SUB	0x32	Subtract integer register rt from integer register rs, placing result into integer register rd.
     SUBI	0x33	Subtract imm from integer register rs, placing result into integer register rd.
     XOR	0x34	Take the bitwise exclusive-OR of register rs and rt, placing the result into register rd.
     OR	0x35	Take the bitwise OR of register rs and rt, placing the result into register rd.
     AND	0x36	Take the bitwise AND of register rs and rt, placing the result into register rd.
     BACK	0x41	Halt processing RISC instructions, leaving the value of the program counter one instruction beyond this instruction.
     S	0x50	Store 32-bit integer register rt to address at rs plus imm.
     L	0x51	Load integer register rt from address at integer register rs plus imm.
     SHL	0x60	Shift the value in integer register rs left by a number of bits given by integer register rt, placing the result into integer register rd.
     SHLI	0x61	Shift the value in integer register rs left by a number of bits given by imm, placing the result into integer register rd.
     SHR	0x62	Shift the value in integer register rs right by a number of bits given by integer register rt, placing the result into integer register rd.
     SHRI	0x63	Shift the value in integer register rs right by a number of bits given by imm, placing the result into integer register rd.
     BEQ	0x70	If integer register rs is equal to integer register rt, then branch to the instruction whose address is the address of the next instruction plus 4 times imm, i.e., imm instructions past this instruction.
     BNE	0x71	If integer register rs is not equal to integer register rt, then branch to the instruction whose address is the address of the next instruction plus 4 times imm.
     BGE	0x72	If integer register rs is greater than or equal to to integer register rt, then branch to the instruction whose address is the address of the next instruction plus 4 times imm.
     BLE	0x73	If integer register rs is less than or equal to to integer register rt, then branch to the instruction whose address is the address of the next instruction plus 4 times imm.

   Hints

   • The scripts fib.txt and phi.txt both use the emulated BASIC language to place RISC instructions one byte at a time into memory locations starting at address 0x1000. The instructions are on lines that look like the following:

     190 DATA 31,08,86,00 ' 1018
     

     That line, from fib.txt, has four hexadecimal numbers corresponding to the 4 bytes in a single RISC instruction. This particular instruction looks like this in binary:

     bit # 33222222 22221 11111 1111
           10987654 32109 87654 32109 876543210
           -------- ----- ----- ----- ---------
            opcode   rd    rs    rt      imm
     value 00110001 00001 00010 00011 000000000
     

     So the opcode is binary 00110001, i.e. 0x31, so the instruction is an ADD instruction. The rd field is 1, the rs field is binary 00010 i.e. 2, and the rt field is binary 00011 i.e. 3, so this instruction says to add integer register 2 to integer register 3 and put the result back into integer register 1. You will need to be able to write Java code to parse these bit fields; make sure to get this working and see if you can tell what the program is supposed to be doing before you try anything else.
   • Note that a 32-bit load involves 4 calls to xoco.load, since xoco.load loads 8-bit bytes. Similarly, a 64-bit load involves 8 calls to xoco.load. There will also be multiple calls to xoco.store for the instructions that store 32 and 64-bit data.
   • Make sure you pay attention to the fact that this instruction set is big-endian, i.e., if you are storing a 32-bit integer to address 0x1000, the bits 31 through 24 byte goes into address 0x1000, bits 23 through 16 go into address 0x1001, bits 15 through 8 go into address 0x1002, and bits 7 through 0 go into address 0x1003.
   • Make sure to read carefully the descriptions for instructions that do subtraction and addition. They are not commutative, so you need to make sure you are subtracting from and dividing by the right register.
   • The file phi.txt has a number of BASIC statements on lines 90 through 270 that could use some explanation. This code is getting 31 8-byte floating point numbers out of memory where your program has (hopefully) stored them, then converting them from IEEE 754 double-precision format that Java uses to the floating-point format used by BASIC, then printing the numbers.
   • Note that the imm field is signed. You will need to figure out how to sign-extend a 9-bit number into Java's 32-bit int type so that you can e.g. do an ADDI with a negative number or do a backwards branch.
   • Branches are a little tricky. The new value of the program counter (i.e. xoco.pc) is the value of imm plus the address of the instruction that is just one past the branch instruction.
   • This instruction set seems a little thin, doesn't it? For instance, why aren't there any instructions to move values between registers? Try disassembling the programs and seeing their logic for yourself. One way to move data from one register to another is to add 0 to the first register with the destination being the second register. Recall that all registers are initially 0; if we never write to, say, register 0, then we will always have the value 0 available in that register (on MIPS, register 0 is always the value 0).
   • Make sure to implement the BACK opcode correctly so the emulator can continue processing and printing out data, rather than failing after reaching an opcode it doesn't recognize. The risc_isa.java file distributed with the assignment doesn't do that, so you will have to figure out how to do that and whether the emulator is behaving correctly after you have done that. Maybe do that first.
   • This problem in a nutshell; type the following from the Linux command prompt on a UTSA x86 machine:

     wget http://cava.cs.utsa.edu/xocolatl.tar.gz
     tar -xvzf xocolatl.tar.gz
     cd xocolatl
     cd src
     <your-favorite-editor> projects/risc_isa.java
     <insert-here-typing-to-do-the-assignment>
     make
     wget http://www.cs.utsa.edu/~dj/cs3853/hw2/fib.txt
     wget http://www.cs.utsa.edu/~dj/cs3853/hw2/phi.txt
     java -cp .:projects xoco -s fib.txt
     java -cp .:projects xoco -s phi.txt
     <more-commands-to-print-out-stuff>
     

You may not work together on this assignment with other classmates or receive assistance from any person other than your professor.

Turn in your assignment by 11:59pm, February 18, 2010 as a single email to the teaching assistant with the following attachments:

1. Your answers the the problems in the first part as a PDF file (no Word documents).
2. Your Java code for the second part as risc_isa.java.

Late assignments will not be accepted.