Computer Architecture Jacobs University Bremen Dr.

Heinrich Stamerjohanns

Course: 320241 December 19th, 2009

Final Exam Your name:

Problem E.1 Twos complement
(3 points) For simplicity we use 16-bit integers in this exercise. Please write down the number 1 and -1 as binary numbers using twos complement representation. Also write down the smallest possible number in decimal notation.

Problem E.2 Programming languages

(3 points)

In brief words, what is the difference between a higher language, assembly language and machine code?

Problem E.3 Performance

(6 points) Consider two different implementations P1 and P2, of the same instruction set. There are ve classes of instructions (A - E) in the instruction set.

Class A B C D E

CPI on P1 1 2 3 4 3

CPI on P2 2 2 2 4 4

P1 has a clock rate of 4 GHz, P2 has a clock rate of 6 GHz. The average number of cycles for each instruction class for P1 and P2 is as in the table above. If the number of instructions executed in a certain program is divided equally among the classes of instructions as above except for class A, which occurs twice as often as each of the others, how much faster is P2 than P1?

Problem E.4 MIPS assembler

(6 points) In the MIPS assembly language, there are different instruction categories. Please name three of them and give for each an example by lling out the following table: (Into Category you can either write down the X-Format or supply longer explanatory names, which have been used in lecture)

Problem E.5 MIPS instruction

Consider the following code: while (value[i] == k) i += 1;

(6 points)

Assume that i and k correspond to registers $s0 and $s1 and the base of the array value is in $s6. What is the MIPS assembly code corresponding to this C segment?

Problem E.6 MIPS assembler

(3 points) In the snippet of MIPS assembler code below, how many times is instruction memory accessed? How many times is data memory accessed? (Count only accesses to memory, not registers.) lw $v1, 0($a0) addi $v0, $v0, 1 sw $v1, 0($a1) addi $a0, $a0, 1

Problem E.7 MIPS instruction set

(4 points)

The bne instruction has only space for a 16-bit address that can be jumped to, although generally addressable memory space is typically 32 bits wide. a) What code can the compiler emit to circumvent this limit?

b) Will this happen often? Why or why not?

Problem E.8 Stack

Please describe briey the term stack. What is it used for in MIPS assembler?

(4 points)

Problem E.9 MIPS instruction set

(3 points) In MIPS assembly language, registers $s0 to $s7 map onto register 16 to 23, and registers $t0 to $t7 map onto register 8 to 15. The opcode for addition and subtraction is 0. The function code is 32 for addition and 34 for subtraction. Given all this, please translate the following binary word into a MIPS instruction: 000000 10010 10100 01010 00000 100010

Problem E.10 MIPS assembler

(6 points) In the following code segment, f,g,h,i and j are variables. If the ve variables f through j correspond to the ve registers $s0 through $s4, what is the compiled MIPS code for this C if statement ? Consider the following fragment of C code: if (i > j) f = g + h; else f = g - 2;

Problem E.11 Floating point

a) Convert 14.5 into a normalized form of base 2.

(3+3+2 = 8 points)

b) IEEE 754 oating point single precision standard has 1 bit for the sign, 8 bits for the exponent and 23 bits for the fraction. Remember that there is a bias of 127 for the exponent. Write down the binary representation of 14.5 as a IEEE 754 oating point single precision number. c) Why is there such a bias for the exponent and why is the bias 127 and not e.g. 227?

Problem E.12 single-cycle datapath

(6 + 5 + 1 + 1 = 13 points)

0
Add 4 ALUOp Instr[31-26] Control Unit ALUSrc RegDst Instruction Memory PC Read Address Instr[31-0] RegWrite Branch Shift left 2 Add

1
PCSrc MemRead MemtoReg MemWrite

ovf zero 0 1
ALU control ALU Address Data Memory Read Data Write Data

Instr[25-21] Read Addr 1

Read Register Instr[20-16] Read Addr 2 Data 1 File 0 Write Addr Read 1 Data 2 Instr[15 Write Data -11] Sign Extend

1 0

Instr[15-0] 16

32

Instr[5-0]

a) By marking (by e.g. a thicker line) the active lines and circling the active selectors in the gure above, show the single-cycle datapath for the sw instruction. Then with your ndings write down the values of the control lines for that instruction into the table below. Use a symbolic arithmetic command (like add, subtract, divide, multiply or shift for ALUOp. Memto Reg Reg Write Mem Read Mem Write

Instruction sw

RegDst

ALUSrc

Branch

ALUOp

0
Add 4 ALUOp Instr[31-26] Control Unit ALUSrc RegDst Instruction Memory PC Read Address Instr[31-0] RegWrite Branch Shift left 2 Add

1
PCSrc MemRead MemtoReg MemWrite

ovf zero 0 1
ALU control ALU Address Data Memory Read Data Write Data

Instr[25-21] Read Addr 1

Read Register Instr[20-16] Read Addr 2 Data 1 File 0 Write Addr Read 1 Data 2 Instr[15 Write Data -11] Sign Extend

1 0

Instr[15-0] 16

32

Instr[5-0]

b) The shown datapath misses the jump instruction. Please add support for the jump instruction by adding hardware and control as needed. Please also mark the active lines and circle the selectors in the gure above. c) What operation does the ALU do when the instruction beq is used?

d) What is the purpose of the MemtoReg control?

Problem E.13 Single-cycle

(2 points) The single-cycle datapath is quite easy to build. However most modern processors do not implement it, why? Give a (short) example.

Problem E.14 Datapath and control (12 points) When silicon chips are fabricated, defects in material (e.g. silicon) and manufacturing errors can result in defective circuits. A very common defect is for one wire to affect the signal in another. This is called a cross-talk fault. A special class of cross-talk faults is when a signal is connected to a wire that has a constant logical value. In this case we have a stuck-at-0 or a stuck-at-1 fault and the affected signal always has a logical value of 0 or 1, respectively.
Signal Instruction memory, output instruction, bit 7 Control unit, output MemtoReg

a. b.

Let us assume that the processor testing is done by lling the PC, registers, and data and instruction memories with some values (you can choose which values), letting a single instruction execute, then reading the PC, memories, and registers. These values are then examined to determine if a particular fault is present. Can you design a test (values for PC, memories, and registers) that would determine if there is a stuck-at-0 fault on the given signals above?

Problem E.15 Pipelining I

(2 points) When one instruction is executed in a pipelined datapath, it still needs the same amount of time as in the single-cycle datapath. So where is actually the benet, or is this statement wrong?

Problem E.16 Pipelining II

(7 points)

a) Sketch a gure of a single cycle datapath with pipelining. It should contain the main hardware but no control lines. b) What are the different stages for executing an instruction in a single cycle datapath with pipelining? Name each step and provide some description.

Problem E.17 Pipelining III (6 points) With pipelining there are special situations when the next instruction cannot be executed in the next clock cycle. Name the three types that might exist, give a brief description and give an example in MIPS assembler for one of them.

Problem E.18 Memory hierarchy

a) Why do many computers use caches? (Please give only brief description.)

(6 points)

b) To improve performance caches transfer multiple words in one block. What kind of principle is taken advantage of? (Please name it and give a short description (max. 3 sentences))

c) However, the block size should not be increased beyond certain limits. Please name and describe briey two of the most important points that lead to decreased performance if the block size is too large.

Points: 100 Bonus: 0