University of Michigan EECS 370
Winter 2002

EXAM 1

Instructions

1. This is an open books/notes exam.

2. It comprises a total of 27 multiple-choice questions, broken down as follows:

a. 4 2-point questions

b. 23 4-point questions

3. Each question has only one correct answer.

4. For each question, indicate your answer on the answer sheet provided.

5. You have 80 minutes to complete the exam.

6. Please make sure you enter your name in the space below AND on the answer sheet.

7. By signing below, you certify that your conduct throughout the exam has been in accordance with the College of Engineering Honor Code.

8. At the end of the exam, please turn in this exam booklet AND your answer sheet.

Name ______________________________________________

Signature ______________________________________________

Program Conventions [4 Questions @ 2 points each]

Complete statements 1—4 correctly.

1. _____________ requires that locally used registers are saved before first use.

a. Caller-save

b. Callee-save

c. Dynamic linkage

d. An Activation record

e. A linker

2. The __________ provides local dynamic storage used by a function.

a. Compiler

b. Assembler

c. Activation record

d. Program heap

e. Linker

3. The __________ provides dynamic storage that can be used by all functions within a program, provided references are available.

a. Assembler

b. Calling convention

c. Static global data

d. Program heap

e. Linker

4. A(n) ______________ statically resolves storage location references in an object module in preparation for program execution.

a. Loader

b. Linker

c. Assembler

d. Compiler

e. SPIM

Procedures [2 Questions @ 4 points each]

5. Consider the following program

int x;

void main()

{

int b;

int c = 0xffff;

func( b );

}

void func( int y )

{

static int z;

return;

}

Where will the variables b,c,x,z be placed in memory? The heap, stack, or global static data?

a. x, z in global, b, c on heap

b. x, z in global, b in stack, c on heap

c. x, c in global, b, z on stack

d. z on heap, x, c, b in global data

e. None of the above

6. The Fibonnaci function is defined as follows:

int fib( int n )

{

if (n <= 1)
return 1;

else

return fib(n-2) + fib(n-1);

}

If each activation frame requires 32 bytes of storage, and the maximum stack size possible for the machine is 700 bytes, what is the largest of the calls below which can execute correctly? (Ignore the stack of the caller of fib.)

a. fib(15)

b. fib(16)

c. fib(17)

d. fib(32)

e. None of the above

Assembly programming [5 Questions @ 4 point each]

7. Assume a 32-bit word-addressable RISC machine with 32 registers and 8-bit opcode. Its branch instruction compares two registers and uses the offset field (in 2’s complement) to compute the PC-relative target. What is the largest possible number of target addresses?

a. 2¹³

b. 2¹⁴

c. 2¹⁵

d. 2¹⁶

e. 2²²

8. Consider the following sequence of LC-2K2 instructions. Assume all registers have been initialized to zero.

nand 0 0 3

lw 0 2 three

three .fill 3

halt

What are the final values in registers r2 and r3?

a. 2 and -2

b. 3 and 0

c. 3 and -1

d. 2 and 3

e. None of the above.

9. Consider the following sequence of LC-2K2 instructions. Assume that the final values of registers r1, r2, and r3 are 2, 2, and 3, respectively.

lw 0 5 target

add 1 2 1

jalr 5 6

add 1 2 1

halt

sub add 6 3 6

add 3 2 3

jalr 6 5

target .fill sub

What would be the initial values of registers r1, r2, and r3? (Assume the initial value of r0 is zero.)

a. 0, 2, 0

b. 0, 2, 1

c. -2, 2, 1

d. -4, 2, 1

e. None of the above

10. Assume r1 is 0. Consider the following LC-2K2 program.

PC Instruction

0 beq 0 1 0

1 jalr 5 5

2 beq 0 0 0

3 halt

Which of the following statements is true?

a. r1 has the value 2 after program halts

b. r1 has the value 0 after program halts

c. Program executes an infinite loop (i.e. never halts)

d. r1 is undefined after program halts

e. None of the above

11. Consider the following instruction sequence

lw 0 1 target

lw 1 5 –1

lw 1 6 1

lw 1 1 0

XXXXXXXXXXXXXXX

halt

.fill 17

data .fill 16

.fill 15

target .fill data

If the initial values of registers r2 and r3 are –2 and 47, and the final values of r2 and r3 are 15 and 15, what sequence of LC-2K2 instructions would need to be inserted into XXXXXXXX?

a. lw 1 2 1
lw 1 3 1

b. add 2 6 2
nand 3 1 3
nand 3 6 3

c. add 2 5 2
nand 3 6 3
nand 3 3 3

d. add 2 5 3
lw 1 3 2

e. None of the above sequences is correct

Addressing modes [4 Questions @ 4 points each]

For Questions 12 and 13, assume the following addressing modes and initial machine configuration.

Direct: lwd r3, 0x108 r3=Mem[0x108]

Indirect: lwi r3, 0x108 r3=Mem[Mem[0x108]]

Base/Disp: lw r3, 8(r1) r3=Mem[r1 + 8]

Registers: r1=0x1000 r2=0x2000 r3=r4=0x0

Location	Value	Location	Value
0x1000	0x2000	0x2000	0x1000
0x1004	0x1008	0x2004	0x200c
0x1008	0x1004	0x2008	0x1004
0x100c	0x8	0x200c	0x4

Consider the following program.

lw r3,0(r2)

lw r1,8(r3)

lw r2,0(r1)

sw r2,0(r3)

sw r2,4(r1)

12. What is the value in r1 after completion?

a. 0x1000

b. 0x1004

c. 0x1008

d. 0x2000

e. None of the above

13. What is the value of memory location 0x1008 after completion?

a. 0x1000

b. 0x1004

c. 0x1008

d. 0x2000

e. None of the above

For Questions 14 and 15, assume the following addressing and initial machine configuration (same as in previous page, just repeated here).

Direct: lwd r3, 0x108 r3=Mem[0x108]

Indirect: lwi r3, 0x108 r3=Mem[Mem[0x108]]

Base/Disp: lw r3, 8(r1) r3=Mem[r1 + 8]

Registers: r1=0x1000 r2=0x2000 r3=r4=0x0

Location	Value	Location	Value
0x1000	0x2000	0x2000	0x1000
0x1004	0x1008	0x2004	0x200c
0x1008	0x1004	0x2008	0x1004
0x100c	0x8	0x200c	0x4

Consider the following program

lwd r3, 0x2000

lwi r2, 0x1004

swd r2, 0x1004

swi r2, 0x2008

14. What are the contents of r2 after the program is executed?

a. 0x4

b. 0x8

c. 0x1004

d. 0x1008

e. None of the above

15. What are the contents of memory location 0x1004 after execution?

a. 0x4

b. 0x1000

c. 0x1004

d. 0x1008

e. None of the above

Single-Cycle Datapath [2 Questions @ 4 points each]

Questions 16 and 17 refer to the following single-cycle datapath implementation of LC-2K2 that was covered in lecture.

16. Assume the following delays for the datapath components

Memories 2 ns

Register file 1 ns

ALU 2 ns (fast carry-lookahead add design)

Adders 5 ns (slow ripple-carry add designs)

All other components have 0 delays. What is the minimum clock period possible for this datapath?

a. 2 ns

b. 5 ns

c. 7 ns

d. 8 ns

e. 10 ns

17. Which of the following instructions require the control signal D to select the lower MUX input (i.e. the one coming from the register file)?

I. add

II. nand

III. beq

IV. lw

V. sw

a. I and II

b. I, II, and III

c. III and IV

d. I, II, and V

e. III, IV, and V

Multi-Cycle Datapath [7 Questions @ 4 points each]

Questions 18—24 refer to the following multicycle datapath implementation of LC-2K2 that was covered in lecture. Recall that on this datapath, BEQ always completes in 3 cycles.

18. Suppose that the wire indicated by the X is disconnected. Which instructions are affected by this defect?

a. jalr only

b. jalr and store

c. jalr and load

d. load and store

e. load only

19. Suppose the sign extension unit is defective. Which one of the following lists contains instructions that are all affected by this defect?

a. add, load, store

b. add, load, beq

c. load, store, beq

d. nand, load

e. nand, load, beq

20. During the execution of a BEQ instruction, how many times and when is the PC updated?

a. Once during Fetch (cycle #1)

b. Once during Decode (cycle #2)

c. Twice: during Fetch (cycle #1) and Decode (cycle #2)

d. Once (during Fetch) or twice (during Fetch and Decode.

e. Once (during Fetch) or twice (during Fetch and ALU operation).

21. During the execution of an ADD instruction, how many times and when is the PC updated?

a. Once during Fetch (cycle #1)

b. Once during Decode (cycle #2)

c. Twice: during Instruction Fetch (cycle #1) and Decode (cycle #2)

d. Twice: during Instruction Fetch (cycle #2) and ALU operation (cycle #3)

e. Once (during Fetch) or twice (during Fetch and ALU operation).

22. Which control signals may be set to “don’t care” throughout the execution of a BEQ instruction?

a. A and B

b. B

c. C and D

d. E and F

e. Every control signal must be set to 0 or 1 at some cycle during BEQ execution

23. Which control signals may be set to “don’t care” throughout the execution of an ADD instruction?

a. A and B

b. B

c. C and D

d. E and F

e. Every control signal must be set to 0 or 1 at some cycle during ADD execution

24. Consider the execution of a program on this multi-cycle datapath. The program has 1,000 instructions with the following mix.

50% ADD

25% BEQ

15% LW

10% SW

If the clock period is 4 ns, what is the total execution time of this program?

a. 3,900 ns

b. 4,000 ns

c. 15,600 ns

d. 16,600 ns

e. None of the above

Floating Point Numbers [3 Questions @ 4 points each]

25. What is the IEEE 754 representation of 0.21875 ?

a. 0 01111110 10000000000000000000000

b. 0 01111100 11000000000000000000000

c. 1 01111110 10000000000000000000000

d. 1 01111100 11000000000000000000000

e. 1 11111100 11000000000000000000000

26. The largest finite floating point number that can be represented in the IEEE 754 format is about

a. 2⁸

b. 2²³

c. 2³²

d. 2¹²⁸

e. 2²⁵⁶

27. The number of floating point numbers that can be represented in the IEEE 754 format is about

a. 2⁸

b. 2²³

c. 2³²

d. 2¹²⁸

e. 2²⁵⁶