Maximum points: 70
A. 3.12 in the book (4 points)
Branches use PC-relative addressing and can only branch to addresses within 2^15 of the current PC. Thus, if here is far enough from there (specifically, more than 2^15 instructions away), then beq will not have enough address bits to jump. The solution could be something like this:
here: bne $t1, $t2, temp
j there
temp:...
there: add $t1, $t1, $t1
The jump can take a 26-bit (almost) absolute address and thus jump to longer distances.
B. 3.14 in the book (6 points)
a. Take a typical 100 instructions. How many of these access memory? Well, each instruction needs to be actually read from memory giving 100 reads, and then 33 of instructions also need to load or store data. That's total 133 accesses, of which 33 are actually for data in memory.
% all memory accesses for data = (memory data accesses) / (all memory accesses) = 33 / 133 = 25%
Note that you can get the same results for any number of instructions, or if you do the same calculations with only percentages. It's just easier to understand with a concrete number of instructions.
b. Again, take 100 instructions. As in a, this gives 133 total memory accesses. Of the 33 data accesses, 2/3 are loads, and 1/3 are stores. That's 22 reads and 11 writes. Also, don't forget that there are 100 more reads, since we must read in each instruction from memory before executing it. Thus,
% all memory accesses that are reads = (100+22) / 133 = 91.7%
C. 3.16 in the book (5 points)
Averaging the instruction percentages for gcc and spice gives:
Arithmetic | 49% |
Data transfer | 37% |
Conditional branch | 12.5% |
Jump | 1.5% |
Now, using this we get the CPI as follows:
CPI = (0.49)(1) + (0.37)(1.4) + (0.125)(1.7) + (0.015)(1.2) = 1.2385
D.
1 At roughly 400 kilobytes, gcc has one of the largest manpages you can find. (1 point)
2 and 3. (20 points)
There are many ways to do this. Here is a sample solution:
#include <stdio.h> int upcase(char c) { return (c >= 'a' && c <= 'z') ? (c - 'a' + 'A') : c; } int is_pal(char *str) { // begin and end point to characters being checked at both ends of // the string char *begin = str, *end = str; while(*end) end++; end--; for(;;) { // "infinite" loop while(upcase(*begin) < 'A' || upcase(*begin) > 'Z') begin++; while(upcase(*end) < 'A' || upcase(*end) > 'Z') end--; if(begin > end) return 1; // we are done and string is a palindrome if(upcase(*begin++) != upcase(*end--)) return 0; // found a discrepancy in current character } } int main(int argc, char **argv) { if(argc < 2) return 1; printf("%s %s a palindrome\n", argv[1], is_pal(argv[1]) ? "is" : "is not"); return 0; }
4. (2 points) Put the main() into main.c and everything else into ispal.c. Then compile as:
gcc -c main.c -o main.o
gcc -c ispal.c -o ispal.o
gcc ispal.o main.o -o ispal
This will build an executable ispal. Useful optional flags to gcc include -g to save debugging info, -O6 to turn on optimization, -Wall to turn on all warnings. See man page for more options.
E.
1. (2 points)
The integer format is basically either 0, or an optional minus sign, followed any digit 1-9, followed by any number of arbitrary digits 0-9. Since it wasn't specified whether it's ok to have leading 0's in a number (e.g. number 0000014), we didn't test these cases and you could do whatever you wanted with them.
2. (20 points)
Sample solution coming soon...
F. (10 points)
a. (3 points) Why is the idea worthwhile on the surface.
b. (4 points) Consequences
c. (3 points) Conclusion
In general, any reasonable account was fine. Here are a few of ideas you could have for both options:
64 registers
Pros
|
Cons
|
Memory operands in instructions
Pros
|
Cons
|