Read these instructions carefully. There is a considerable amount of information for you to read before the part about what you're supposed to do. For this assignment you will optimize code that simulates a simple CPU with memory and output. Our simulated CPU fetches instructions from the memory (which may be thought of as part of the CPU) and executes them. A special instruction, HALT, tells the CPU to stop executing altogether.

Our simulated CPU stores its instructions in an array of C structs. It can hold up to 2000 instructions. It represents memory as another array of 10000 ints called memory[]. Our CPU has special integer variable in it called the Program Counter. This is the index into the instruction array where the currently executing instruction is found. Our CPU simulator uses the following algorithm to execute programs:

1. Read the file named on the command line into the array of instructions.
2. Set the Program Counter (PC) equal to 0.
3. Continue with steps 4 and 5 until "halt" is encountered.
4. Fetch the instruction at the PC element of the array, then add one to the PC.
5. Execute the instruction, possibly changing the PC again. If the instruction is the "halt" instruction, break out of the fetch/execute loop and exit the program, otherwise continue at step 3.

Program Files

• sim.c. This file contains code to read in a simulated program file into the program[] array, then continues to call the simulate() function until simulation is finished.
• simulate.c. This file contains the simulate() function, that executes one instruction from program[pc]. The function returns 1 if simulation is finished, 0 otherwise.
• opcodes.h. This file contains declarations for the struct instruction type and #defines for each instruction, giving mnemonic names to the values for the instruction types.

gcc -O3 -o sim sim.c simulate.c

Instruction Format

struct instruction {
        int     type,		/* type of instruction */
                addr1,		/* first address */
                addr2,		/* second address */
                data;		/* data for the instruction */
};

struct instruction program[2000];

• The integer representing it.
• A short mnemonic name (like "ADD") to make the program easier to read.
• A description of what the instruction does.

Sample Programs for the Simulator

• hello.bin - This program simply prints "Hello, World!" and a newline. It uses only the STORE_CONST, OUTPUT, and HALT instructions.
• test.bin - This program tests some of the instructions. If they seem to be working correctly, it will print:

  testing instructions...
  jump seems to work;
  nop seems to work;
  move and cond_jump seem to work;
  add_const seems to work;
  mul seems to work; assuming add, div, and mod work, too;
  storepc seems to work;
  loadpc seems to work; done.
  

  Otherwise it will fail at one of those instructions and halt with a message.
• primes.bin - This program prints the prime numbers between 1 and 10000.
• bubble.bin - This program illustrates a bubble sort on the numbers from 1 through 200; the numbers are initially in reverse order, and the program shows what a bubble sort does to get them into ascending order.

wget http://www.cs.utsa.edu/~dj/cs2733/hw5/hello.bin
wget http://www.cs.utsa.edu/~dj/cs2733/hw5/test.bin
wget http://www.cs.utsa.edu/~dj/cs2733/hw5/primes.bin
wget http://www.cs.utsa.edu/~dj/cs2733/hw5/bubble.bin

Compiler Implementation of Switch Statement

What You're Supposed To Do

First Optimiztion: Linear Search Instead of Jump Table

	switch (type) {
	case 0: a;
	case 1: b;
	case 2: c;
	...
	}

	if (type == 0) a;
	else if (type == 1) b;
	else if (type == 2) c;
	...

gcc -O3 -o sim-1 sim.c simulate-1.c

time ./sim primes.bin > /dev/null
time ./sim-1 primes.bin > /dev/null

Second Optimization: Ordered Linear Search

Make a new program file called simulate-2.c that will contain another new version of the simulate() function. Temporarily modify the simulator program to count, for each instruction type, how often that type of instruction is executed, and print the instruction counts at the end of simulation. Run the modified simulator on the primes.bin program to collect the frequencies of the instruction types. Then reorder the if statements in the simulate() function to check the type fields in decreasing order of frequency, so that the most common instruction is checked first, etc.

Compile the new program with the following command:

gcc -O3 -o sim-2 sim.c simulate-2.c

time ./sim primes.bin > /dev/null
time ./sim-2 primes.bin > /dev/null

Note that you are not required to change the assembly language, but that your choice of C statements has a large impact on the generated assembly language. Also, this assignment sort-of shows you how a microprocessor works, so you get a little extra computer architecture learning at no extra charge.

What To Turn In

1. Your version of simulate-1.c.
2. Your version of simulate-2.c.
3. A short writeup explaining your results. Address the following questions:
   • How much faster was each new function than the original function for primes.bin?
   • How much faster was each new function than the original function for bubble.bin?
   • Does optimizing the function with respect to the instruction counts in primes.bin also help with bubble.bin? Why or why not?
   • For each simulated instruction, how often was it executed in primes.bin?

Due Date