CS计算机代考程序代写 mips assembly assembler algorithm csc258final12f

csc258final12f

UNIVERSITY OF TORONTO

Faculty of Arts and Science

December 2012 Examinations

CSC258H1S: Computer Organization

Duration: 3 hours

No Aids Allowed

Last Name: _______________________________________

First Name: _______________________________________

Student Number: __________________________________

Instructor: Steve Engels

Total: / 155

/ 52

/ 18

/ 21 Part A:

Part B:

Part C:

Mark Breakdown Instructions:

• Write your name on every page of this exam.
• Do not open this exam until you hear the signal

to start.

• Have your student ID on your desk.
• No aids permitted other than writing tools. Keep

all bags and notes far from your desk before the

exam begins.

• There are 6 questions on 18 pages. When you hear
the signal to start, make sure that your exam is

complete before you begin.

• Read over the entire exam before starting.
• If you use any space for rough work or have to

user the overflow page, clearly indicate the

section(s) that you want marked.

/ 14 Part D:

/ 20 Part E:

/ 30 Part F:

2 (continued)

Student Number: __________________

Answer the following questions in the space provided. When providing a written answer, write as

clearly and legibly as possible. Marks will not be awarded to unreadable answers.

Part A: Short Answer (21 marks)

1. How many instructions could fit into a 256 byte memory unit, given a 32-bit architecture?

(2 marks)

2. How many address bits are needed to specify each byte in a 512 byte memory unit? (1 mark)

a) 256 b) 64

c) 32 d) 8

3. How many minterms could you have in a circuit with three inputs and two flip-flops? (1 mark)

4. True or False? MOSFETs act as a switch by creating a conductive channel between the two

n-type sections in a p-type substrate, or vice versa. (1 mark)

5. What are the HI and LO registers used for in the context of integer division? (2 marks)

6. Assume that wires have already been declared for a, b and c. In the space below, show TWO
different statements in Verilog that set c high when a and b are low. (2 marks)

True False

a) 512 b) 8

c) 32 d) 9

3 (continued)

Student Number: __________________

8. In p-type semiconductors, what are “holes”? (1 mark)

9. How many bits do you shift a binary number in order to divide it by 4? (1 mark)

10. Why are the addresses of all MIPS instructions divisible by 4? (1 mark)

11. What do the following output signals from the ALU signify? (4 marks)

C: _______________ V: __________________

N: _______________ Z: __________________

7. Consider the finite state machine shown below. The output of this circuit goes high

whenever it is in State C or State E. In the spaces below, indicate the operation that this finite
state machine performs, and how many flip-flops this will need. (5 marks)

Operation: _____________________

_______________________________

Number of flip-flops: _______________

A

B

C

D

E

0
0

1
1

1 1

0

1 0

0

a) absent electrons b) positive charge carriers

c) protons d) where you plant silicon flowers

4 (continued)

Student Number: __________________

Part B: Design and Analysis (18 marks)

1. In the space below, draw a circuit whose behaviour matches the following waveform. (4 marks)

input1

Clock

output

input2

2. Which of the circuits below have equivalent behaviour? Draw lines that connect any

circuits that match. (6 marks)

Y
B
C

Y
B

B

Y
C
B

A
B

C

Y
A
B

C

Y
B
C

C
A

A
C

Y B
C

A

Student Number: __________________

4. Given the following circuit, show what the output

waveform diagram. Assume that Q

Clock

Q0

Q2

Y

T Q0

Q Clock

1

Q1

3. Draw gates into the following diagram

5 Student Number: __________________

circuit, show what the output value of Q0, Q1, Q2
waveform diagram. Assume that Q0, Q1 and Q2 start with initial values of zero

T Q1

Q

T Q2

Q

Draw gates into the following diagram to implement a subtractor circuit

(continued)

2 and Y will be in the
start with initial values of zero. (6 marks)

Y

to implement a subtractor circuit. (2 marks)

Student Number: __________________

1. In the datapath diagram below, connect the following

affect. (8 marks)

2. For the following write signal diagram, describe what each labeled time segment is called,

and the purpose of each segment during a memory write operation

tSA: _____________________________________________________________

tAW: _____________________________________________________________

tSD: _____________________________________________________________

tHD: _____________________________________________________________

IorD MemRead IRWrite

Part C: Processors (52 marks)

6 Student Number: __________________

below, connect the following signals to the units that they

For the following write signal diagram, describe what each labeled time segment is called,

and the purpose of each segment during a memory write operation. (8

: _____________________________________________________________

: _____________________________________________________________

_____________________________________________________________

: _____________________________________________________________

MemWrite MemToReg PCSource

: Processors (52 marks)

(continued)

the units that they

For the following write signal diagram, describe what each labeled time segment is called,

8 marks)

: _____________________________________________________________

: _____________________________________________________________

_____________________________________________________________

: _____________________________________________________________

PCWrite PCSource RegDst

7 (continued)

Student Number: __________________

3. In the space below, perform Booth’s Algorithm on the binary values A=10110 and B=01101.

Show your steps in the space provided. (6 marks)

4. Verify your answer above by writing the decimal values for A, B and the final product in the

spaces below. (2 marks)

A =

B =

Product =

P =

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:

8 (continued)

Student Number: __________________

5. For the following assembly language instructions, write the equivalent machine code

instruction in the space provided. You might find the reference information in the appendix

helpful for this question. (10 marks)

a) addu $t2, $t0, $t1

b) lw $t0, 20($s0)

c) jal top (where top is at hexadecimal address 0xFF00)

6. For the following machine code instructions, provide the equivalent assembly language

instruction in the space provided. (6 marks)

a) 00111001000000100000000011111111

b) 00000010000001000100000000100011

c) 00100111111000000000000000000000

9 (continued)

Student Number: __________________

7. For each of the processor tasks below, indicate what the values of the following control unit

signals will be by filling in the boxes next to each signal with the signal values. (12 marks)

• If a control signal doesn’t affect the operation, fill in its value with an X.
• For ALUOp, if you don’t know the values, just write what kind of operation is taking place.

Reduce the program counter by the value stored in $t0.

Fetch the next instruction from the address in the program counter.

Add 64 to $s0 and store the result back in $s0.

PCWrite PCWriteCond IorD MemRead MemWrite

MemToReg IRWrite PCSource ALUOp

ALUSrcA ALUSrcB RegWrite

PCWrite PCWriteCond IorD MemRead MemWrite

MemToReg IRWrite PCSource ALUOp

ALUSrcA ALUSrcB RegWrite

PCWrite PCWriteCond IorD MemRead MemWrite

MemToReg IRWrite PCSource ALUOp

ALUSrcA ALUSrcB RegWrite

10 (continued)

Student Number: __________________

Consider the piece of Verilog code on the right.

1. In one sentence, describe what function this

code performs. (4 marks)

2. Given your answer to part 1, what input signal is

missing from this device? (2 marks)

3. In the space below, write a Verilog module called counter that takes in input signals called
clock, reset and enable, and has a 4-bit output signal called value. (3 marks)

• Make the value output increment if enable is on when the clock goes high (3 marks)
• Implement an asynchronous reset that is also positive-edge triggered. (2 marks)

Part D: Verilog (14 marks)
module foo(a, b, s, r);

input [31:0] a, b;
input [2:0] s;
output reg [31:0] r;

always @(*) begin
case(s[2:0])
3’b000: r = a;
3’b001: r = a + b;
3’b010: r = a – b;
3’b011: r = a – 1;
3’b100: r = a & b;
3’b101: r = a | b;
3’b110: r = a ^ b;
3’b111: r = ~a;
endcase

end

endmodule

11 (continued)

Student Number: __________________

1. Consider the following state machine and flip-flop assignments below. Assume that the

input to this state machine is a single input called X.

Fill in the truth table below with the values that correspond to the FSM above. (8 marks)

F1 F0 X F1 F0

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

Part E: Finite State Machines (20 marks)

A

B C

D

0
0

1

1 1

1

0
0

Flip-Flop Assignments

State A � F1 = 0 F0 = 0

State B � F1 = 0 F0 = 1

State C � F1 = 1 F0 = 1

State D � F1 = 1 F0 = 0

12 (continued)

Student Number: __________________

2. Given the truth table values on the previous page, fill in the Karnaugh map shown below,

and circle the largest minterm groupings possible. (6 marks)

3. Given the Karnaugh map groupings from the previous part, write the boolean equations

that express these groupings, and draw the resulting circuit diagram that implements this

behaviour in the space below. (6 marks)

F1·F0 F1·F0 F1·F0 F1·F0

X

X

F1·F0 F1·F0 F1·F0 F1·F0

X

X

F1:

F0:

13 (continued)

Student Number: __________________

1. In the spaces provided below, write the assembly language instruction(s) that corresponds

to each of the tasks provided. (12 marks total)

a) Perform a right arithmetic shift on the value in $t0. The number of bits to shift $t0 by is
stored in $s0. The result will be stored back into $t0. (3 marks)

b) Load half a word from a memory address stored at $a0, and store that value in register
$t0. The upper bits of $t0 should be filled with zeroes. (3 marks)

c) Jump back to the instruction at location top if the value in $t4 is anything other than zero.
(3 marks)

d) Take the value that is already stored in $t0, and set all of its bits to zero except for the last
3 digits, which are kept as their original values. (3 marks)

Part F: Assembly Language (30 marks)

14 (continued)

Student Number: __________________

Consider the assembly language program in the box below.

2. For each line in the code, provide a short descriptive comment on the right (6 marks)

3. In the space below, provide a one-sentence description of the overall task this code is trying

to perform. (2 marks)

4. One of the lines has a bug in it. What would need to be changed in order for this operation

to be correct? (2 marks)

.data

list: .word 3, 0, 1, 2, 6, -2, 4, 7, 3, 7

.text

main: addi $s0, $zero, list #

addi $t9, $zero, 10 #

top: lw $t1, 0($s0) #

lw $t2, 4($s0) #

sub $t3, $t2, $t1 #

bgtz $t3, inc #

sw $t2, 0($s0) #

sw $t1, 4($s0) #

inc: addi, $s0, $s0, 4 #

subi $t9, $t9, 1 #

bgtz $t9, top #

end: jr $ra #

15 (continued)

Student Number: __________________

5. In the space below, write a short assembly language

program that is a translation of the program on the

right. You can assume that i has been placed on the top
of the stack, and should be replaced by the return value

before returning to the calling program. Make sure that

you comment your code so that we understand what

you’re doing. (8 marks)

int make_even (int i) {
if (i % 2 == 1)
return i-1;
else
return i;

16 (continued)

Student Number: __________________

Register values : Processor role

• Register 0 ($zero): value 0.
• Register 1 ($at): reserved for the assembler.
• Registers 2-3 ($v0, $v1): return values
• Registers 4-7 ($a0-$a3): function arguments
• Registers 8-15, 24-25 ($t0-$t9): temporaries
• Registers 16-23 ($s0-$s7): saved temporaries
• Registers 28-31 ($gp, $sp, $fp, $ra)

Reference Information

ALU arithmetic input table:

Select Input Operation

S1 S0 Y Cin=0 Cin=1

0 0 All 0s G=A G=A+1

0 1 B G=A+B G=A+B+1

1 0 B G=A-B-1 G=A-B

1 1 All 1s G=A-1 G=A

Register table:

Instruction Op/Func Syntax
add 100000 $d, $s, $t
addu 100001 $d, $s, $t
addi 001000 $t, $s, i
addiu 001001 $t, $s, i
div 011010 $s, $t
divu 011011 $s, $t
mult 011000 $s, $t
multu 011001 $s, $t
sub 100010 $d, $s, $t
subu 100011 $d, $s, $t
and 100100 $d, $s, $t
andi 001100 $t, $s, i
nor 100111 $d, $s, $t
or 100101 $d, $s, $t
ori 001101 $t, $s, i
xor 100110 $d, $s, $t
xori 001110 $t, $s, i
sll 000000 $d, $t, a
sllv 000100 $d, $t, $s
sra 000011 $d, $t, a
srav 000111 $d, $t, $s
srl 000010 $d, $t, a
srlv 000110 $d, $t, $s
beq 000100 $s, $t, label
bgtz 000111 $s, label
blez 000110 $s, label
bne 000101 $s, $t, label
j 000010 label
jal 000011 label
jalr 001001 $s
jr 001000 $s
lb 100000 $t, i ($s)
lbu 100100 $t, i ($s)
lh 100001 $t, i ($s)
lhu 100101 $t, i ($s)
lw 100011 $t, i ($s)
sb 101000 $t, i ($s)
sh 101001 $t, i ($s)
sw 101011 $t, i ($s)
trap 011010 i
mflo 010010 $d

Instruction table:

17 (continued)

Student Number: __________________

This page is left blank intentionally for answer overflows.

18 (continued)

Student Number: __________________

This page is left blank intentionally for answer overflows.

Total Marks = 155

Total Pages = 18

End of exam