CSE 378 Practice problems for exam 1 (v1.02) ------------------------------------------------------------------------ 1. (Tim's comment - I think this is harder than you'd see on the exam.) Show how you'd make an inverter using only nand gates. Now, show how you'd make an and gate using only nand gates (you can use the inverter from part 1) Now, show how you'd make an or gate using only nand gates (you can use the and gate and inverter from parts 1 and 2) Now, make an xor gate using only nand gates (you can use any of the units from part 1, 2 or 3) ------------------------------------------------------------------------ 2. Add a "bgezal" instruction to the MIPS datapath. The bgezal instruction takes one register as an argument and branches if it is greater than or equal to zero. It also stores the address of the next PC in $ra. ------------------------------------------------------------------------ 3. Write a "printf" function in MIPS assembly language. This printf function, unlike the one in C, will only have the "%d" and "%s" conversion specifications. In C, a call to printf would be something like this: char* s = "Tim"; int x = 5, y = 7; printf("The value of x is %d. The value of y is %d.\n", x, y); printf("The author of this program's name is %s.\n", s); The output would look like this: The value of x is 5. The value of y is 7. The author of this program's name is Tim. When writing this function, you need to realize that it can take an unlimited number of arguments. If you have over 4, you should put remaining arguments on the stack. The first argument will be the formatted string and subsequent arguments will be the values to be printed as strings. If you like, you can assume there is an itoa function already written which takes an integer in $a0 and the address of a buffer in $a1 and, upon returning, the converted integer will be a string in the buffer you specified. Be sure to use the proper MIPS calling conventions, saving registers before function calls, saving registers upon entry into a function, and restoring registers upon exit out of a function. System calls: print_int 1 print_float 2 print_double 3 print_string 4 sbrk 9 exit 10 ------------------------------------------------------------------------ 4. (Note, if this is very similar to another problem below, but on a different machine.) You think the way memory operations are done in MIPS is silly in cases where you want a base and a dynamically changing offset, so you decide to add R-type load instructions. These instructions work as follows: lw rd, rs(rt) sw rd, rs(rt) The purpose of these instructions is to keep the base of the array in rt and to increment rs as you loop. Ignoring other instructions (like lb, sb, etc) how would you change the MIPS datapath to implement these instructions? What effect would it have on the instruction set? (Note, this shouldn't take more than a few brief sentences to explain.) ------------------------------------------------------------------------ 5. Explain why using any of these metrics alone would be a false indication of performance: MIPS, clock rate, MFLOPS. ------------------------------------------------------------------------ 6. You are the lead designer of a new processor. The processor design and compiler are complete, and now you must decide whether to produce the current design as it stands or spend additional time to improve it. You discuss this problem with your hardware engineering team and arrive at the following options: a. Lave the design as it stands. Call this base machine Mbase. It has a clock rate of 500 MHz, and the following measurements have been made using a simulator: --------------------------------------- | Instruction class | CPI | Frequency | --------------------------------------- | A | 2 | 40% | | B | 3 | 25% | | C | 3 | 25% | | D | 5 | 10% | --------------------------------------- b. Optimize the hardware. The hardware team claims that it can improve the processor design to give it a clock rate of 600 MHz. Call this machine Mopt. The following measurements were made using a simulator for Mopt: --------------------------------------- | Instruction class | CPI | Frequency | --------------------------------------- | A | 2 | 40% | | B | 2 | 25% | | C | 3 | 25% | | D | 4 | 10% | --------------------------------------- What is the CPI for each machine? Using the CPI, on average how much faster does an instruction execute in Mopt than in Mbase? If your program was 100 billion (100 x 10^9) instructions, how much time would you save? ------------------------------------------------------------------------ 7. What is one advantage and one disadvantage each of stack, accumulator and general purpose register architectures? ------------------------------------------------------------------------ 8. (This is probably too hard for an exam problem, but good practice anyway.) Recall the accumulator architecture in the text. The three instructions that it mentioned were add, load, and store. add Address # Acc = Acc + Memory[Address] load Address # Acc = Memory[Address] store Address # Memory[Address] = Acc This is not a very complete instruction set as you can only run sequential programs using this technique. Add 2 instructions of your choice, describe how they would work, and then use them to write a factorial program that assumes the argument is present in the accumulator when called. ------------------------------------------------------------------------ 9. If the program reaches the "next" label, what will the value of $t1 be (in hex) and why? If it doesn't reach the "next" label, why didn't it? Assume all registers are 0 upon entry to the code shown here. Also assume stores to the code section are allowed. True Assembler SPIM Assembler [0x00400000] lui $1, 64 __start: la $s0, loop [0x00400004] ori $16, $1, 12 [0x00400008] lui $8, 1 addiu $t0, $0, 0x10000 [0x0040000c] bne $0, $11, 20 loop: bne $0, $t3, next [0x00400010] lw $10, 0($16) lw $t2, 0($s0) [0x00400014] addu $10, $10, $8 addu $t2, $t2, $t0 [0x00400018] sw $10, 0($16) sw $t2, 0($s0) [0x0040001c] addu $9, $9, $8 addu $t1, $t1, $t0 [0x00400020] jr $16 jr $s0 [0x00400024] ori $2, $0, 10 next: done [0x00400028] syscall ------------------------------------------------------------------------ 10. The following pattern of numbers is called Pascal's triangle. row column 1 1 2 11 3 121 4 1331 5 14641 The numbers along the two edges of the triangle are all 1 (one), and each number in the interior of the triangle is the sum of the number above it and the number above and to the left of it. Write a RECURSIVE MIPS procedure that calculates a specific element of Pascal's triangle. Your procedure should be named "pascal" and should take two arguments: the first being the (integer) row number of the element to calculate and the second being the (integer) column number. It should return the calculated element also an integer, as the return value. You must follow register conventions as well as standard procedure calling conventions for full credit on this question (in other words, make no assumptions about the calling procedure). You may assume the inputs are each greater than or equal to 1. Here is a C function which accomplishes the desired task. You are advised to stay as close to this function as possible in order to simplify your own life (and ours). int pascal (int row, int column) { if (column == 1) return 1; else if (row == column) return 1; else { return (pascal (row-1, column) + pascal (row-1, column-1)); } } ------------------------------------------------------------------------ 11. A = 0x20C89000 (a) Give the binary equivalent of A: For the following 2 questions (b, c) you may leave parts of your answers as signed sums of powers of two [e.g. -(2^2+...2^19)]. Do not leave any part of your answers in hex. No hex! (b) Give the decimal equivalent of A if A is interpreted as an integer in 2's-complement notation: (c) Give MIPS instruction equivalent of A if A is interpreted as an instruction in machine language format ------------------------------------------------------------------------ 12. Convert the binary value 110000001111111111101110 into a) hexadecimal (base 16) b) octal (base 8) ------------------------------------------------------------------------ 13. Assuming a five-bit word length, convert the binary value 11100 to decimal, supposing the representation is a) unsigned b) two's complement ------------------------------------------------------------------------ 14. Write a sequence of MIPS instruction that extracts bits 17:11 of register $s0 and inserts them into bits 8:2 of register $s1, leaving all the remaining bits of $s1 unchanged. You may use t-registers as temporaries. ------------------------------------------------------------------------ 15. Translate the following C procedure to MIPS. Use the convention in which arguments are passed in registers. int garply(int a, int *b) { int c; c = subt(a >> 6); //this is a function call *b = a + *b; if (a < 0 || c < 0) return c; else return c | a; } ------------------------------------------------------------------------ 16. Add a jal (jump and link) instruction to the datapath designed in Friday's class. Jal's opcode is 111: ------------------------------------ | 1 | 1 | 1 | | | | | | | ------------------------------------ target address -- lower 6 bits of the instruction. Jal stores the incremented PC into register 3, and jumps to the target address. (If you'd like, you may use http://www.cs.washington.edu/homes/dportnov/378/datapath.pdf as a starting point.) ------------------------------------------------------------------------ 17. You decided that two bits aren't enough for load/store offsets. So you changed the format of these two instructions as follows: Load: $target = MEM[$source1 + $source2] Store: MEM[$source1 + source2] = $target Modify the datapath from Friday's class to support these instructions (opcode for load is 101; opcode for store is 110)