COMP 2421 Computer Organization Midterm
Release date: Feb. 22, 2021
Firm Deadline: 11:59 pm, Mar. 1, 2021. Zero mark for late submission
• Open-book exam. But you are prohibited to communicate with others.
Copyright By PowCoder代写 加微信 powcoder
• If cheating is detected, anyone involved will get 0 for this exam.
• For branch instructions in MIPS, you can safely ignore branch delay slot.
1 FILL IN THE BLANKS [25PTS]
If not specified, each question counts for 2pts.
(1) Assuming 12-bit 2’s complement representation, the hexadecimal number FD2 is equal to the decimal number:
Register $t1 contains the address 0x10000100. Write the instruction (using lw) that loads the four bytes that precede this address into register $t2:
lw $t2, -4($t1)
Given the following data definitions:
X: .word -4, 2, 5
Y: .half 1, 2, 3 #.half means half-word
Z: .byte ’A’, ’B’, ’C’
Suppose the address for X is 0x10010000, the hexadecimal addresses for Z will be:
Address of Y = 0x10010000 + 12 + 6 = 0x10010012
For simplicity, we use x’ to denote the complement of x. Then the complement of F = x(y’z’+yz) in simplified form is:
x’ + (y+z)(y’+z’) = x’+yz’+y’z.
(3pts) Find the decimal value of the following floating point number represented in binary form (8 bits for biased exp and 23 bits for significand):
1 |1000 1001 | 111 1100 1101 0000 0000 0000
Sign bit = 1 (negative)
Biased Exponent = 1000 1001 = 137
Exponent Value = 137 – 127 = 10
Value = -(1.11111001101000000000000)2 × 210
= –(11111100110.1000000000000)2
Decimal Value = –2022.5
Examine the following program fragment:
addiu $t1,$0,-13
addiu $t2,$0,23
the third instruction
What is the third instruction to set $t3 to 1? Requirement: using ’sltu’ and the instruction should contain $t1 and $t2.
sltu $t3,$t2,$t1.
(7) (3pts) Complete the following program to push the two values stored in $s1 and $s2 into stack (note: $s1 is pushed first):
addi $sp, $sp, sw $s1, ($sp) sw $s2, ($sp)
(8) (3pts) In the following circuit shown in Fig. 1 , the flip-flops are all positive-edge triggered. The initial state is 𝑄3𝑄2𝑄1𝑄0 = 0001. After one clock pulse, what does the state 𝑄3𝑄2𝑄1𝑄0 become?
Fig. 1. Question 1-(8)
(9) ThesimplifiedSOPformof𝑋′𝑌′𝑍′ +𝑋′𝑌′𝑍 +𝑋′𝑌𝑍 +𝑋𝑌′𝑍 +𝑋𝑌𝑍 is: 𝑋 ′𝑌 ′ + 𝑍
(10) (4pts)ThecharacteristicequationofaT-Flip-Flopisgivenby𝑄𝑛𝑒𝑥𝑡 =𝑇𝑄′ +𝑇′𝑄.Inthefollowingcirucit shown in Fig. 2, the symbol 𝐴 and 𝐵 each represents a single logic gate (for example, AND, OR, XOR, NOT gate). What should 𝐴 and 𝐵 represent to make the circuit implement a T-Flip-Flop?
Both 𝐴 and 𝐵 are AND gate.
Fig. 2. Question 1-(10)
2 MIPS: TRANSLATE PSEUDO-INSTRUCTIONS [15PTS]
Pseudo-instructions are legal MIPS assembly language instructions that do not have a direct hardware imple- mentation. They are provided as a convenience for the programmer. When you use pseudo-instructions in a MIPS assembly language program, the assembler translates them into equivalent actual MIPS instructions.
The following is an example of Pseudo-instruction with comment, and its equivalent translation using one or a sequence of actual MIPS instructions:
li $t1, big # load an immediate value “big” of 32 bits into $t1
It’s translation into actual MIPS instructions is:
lui $t1, upper-of-big # load the upper 16 bits of big into $t1
ori $t1, $t1, lower-of-big # load the lower 16 bits of big into $t1
For each of the following Pseduo-instruction with comment, translate it into actual MIPS instructions as specified. 3pts for each question.
addiu $t1, $t2, 0x1234abcd
#add a 32-bit constant with $t2, and store the result in $t1
Requirement: use a sequence of three instructions: lui, ori, addu, and another register.
bgt $t1, $t2, Label
#branch greater than: if $t1 > $t2, branch to Label
Requirement: use a sequence of two instructions: slt, bne, and another register.
ror $t1, 7
#rotate right: rotate the bits in $t1 to the right by 7 positions.
#here, “rotate” means that the bits on the right side are filled into
#the vacated bits on the left (see Fig.1)
Requirement: use a sequence of three instructions: srl, sll, or, and another register.
Fig. 3. Question 2-(3): rotate right.
multiply $t1, $t2, 31
#multuply $t2 with a constant 31 and store the result in $t1
#suppose there’s no overflow
Requirement: use a sequence of two instructions: sll, sub.
lw $t4, 0x00010002($t1)
#load the word stored at memery address $t1 + 0x00010002 into register $t4,
#where $t1 stores the base address
Requirement: use a sequence of four instructions: lui, ori, add, lw, and another resigter
(1) lui $t3, 0x1234 # set any register $t3 as 0x12340000
ori $t3, $t3, 0xabcd # set $t3 = 0x1234abcd
addu $t1, $t2, $t3
(2)slt$t3,$t2,$t1 #set$t3=1if$t2<$t1
bne $t3, $0, Label # if $t3 is not equal to 0 (i.e., if $t2 < $t1), branch to Label)
(3) srl $t2, $t1, 7 sll $t1, $t1, 25 or $t1, $t1, $t2
# first, shift $t1 to the right by 7 positions, store the result in $t2 # second, shift $t1 to the left by (32 - 7) = 25 positions
# take or operation between $t1 and $t2
(4) sll $t1, $t2, 5 # $t1 = 32* $t2
sub $t1, $t1, $t2 # $t1 = $t1 - $t2
(5) lui $t2, 0x0001
ori $t2, $t2, 0x0002 # load 0x 00010002 into $t2
add $t2, $t2, $t1 # now, $t2 stores the target address $t1 + 0x00010002
lw $t4, 0($t2)
3 MIPS: TRANSLATE MIPS PROGRAM INTO C PROGRAM [10PTS]
Read the following MIPS code segment and comments. Translate it into C code (the skeleton C code is provided to you).
Specifically, the registers $s0, $s1, $s2, $s3 store signed integers 𝑥,𝑦,𝑧,𝑤, respectively. Complete the C code using expressions of 𝑥,𝑦,𝑧,𝑤. Do not care too much about the grammars of C. You will get full marks as long as the meanings are correct.
Hint: this is a "two-layer" if-else structure (i.e., an inner if-else inside an outer if) as shown in the skeleton C code. The general idea is to consider what the conditions are to enter the if structure. Specifically, the first three instructions specify the condition for the outer if.
MIPS code segment:
bge $s0, $s1, L1 #gotoL1if$s0>=$s1
bgt $s2, $s3, skip # go to skip if $s2 > $s3
bne $s0, $s2, skip # go to skip if $s0 != $s2
# inner if statement
bne $s2, $s3, L3
addu $s0, $s1, $s2
addiu $s2, $s1, -2
#gotoL3if$s2!=$s3
C code you need to complete:
if (some condition 1 [5pts]){
if (some condition 2 [3pts])
some code 1 [1pt]
some code 2 [1pt]
bge $s0, $s1, L1 # branchifx>=y
bgt $s2, $s3, skip # branch if z > w
bne $s0, $s2, skip # branch if x != z
L2: # inner if statement
bne $s2, $s3, L3 # branch if z !=w
addu $s0, $s1, $s2 # execute inner if
j skip #
addiu $s2, $s1, -2 # execute inner else
5 pts “some condition 1”: Consider the condition to enter L2. There are two ways: (1) branch in instruction 1 – do not branch in instruction 3; (2) do not branch in instruction 1 – do not branch in instruction 2 – do not branch in instruction 3.
Thus, the corresponding condition is (𝑥 >= 𝑦&&𝑥 == 𝑧)||(𝑥 < 𝑦&&𝑧 <= 𝑤&&𝑥 == 𝑧) — Equation 1.
It can be simplified to (𝑥 >= 𝑦||𝑥 < 𝑦&&𝑧 <= 𝑤)&&𝑥 == 𝑧 — Equation 2. It can be further simplified to (𝑥 >= 𝑦||𝑧 <= 𝑤)&&𝑥 == 𝑧 — Equation 3.
Rules of marking: 5pts if got Equation 3 correctly. 4 pts if got Equation 2 correctly. 3pts it got Equation 1 correctly.
3 pts "some condition 2": do not branch. So the condition is 𝑧 == 𝑤 1pts "somecode1":x=y+z
1pts "somecode2":w=y-2
4 MIPS: TRANSLATE C PROGRAM INTO MIPS PROGRAM [10PTS]
Let B be an array of integers, where each integer has a size of 4 bytes. The address of B[0] is called the base address of the array. And the address of B[i] is base address added by 4 × 𝑖.
Now, suppose the base address of B is stored in register $s0, and the size of the array 𝑛 is stored in $s1. Complete the MIPS assembly code fragment to implement the following C program (note, some comments are given as hint):
for(i=0; i< n-1;i++)
if(B[i]==B[i+1]){ Num = Num +1}
The MIPS code fragment you need to complete:
addi $s1, $s1, -1
lw $t0, _($s0)
lw $t1, _($s0)
_ $t0,$t1, Skip
addi _, _, _
addi $s0,$s0, _
addi $s1, $s1, _
bne $s1, _, Loop
#if (B[i]== B[i+1])
Answer: 0,0,4,𝑏𝑛𝑒,$𝑠2,$𝑠2,1,4,−1,$0
5 MIPS: UNDERSTAND MIPS CODE [15PTS]
An array of integers S is defined in the following code. Try to understand the code and answer the following questions.
S: .word 14, -29, 18, 30, -12, 12, 106, -7
la $a0, S # load address of S into $a0; suppose $a0 = 0x20060000
addi $a1, $a0, 28
move $v0, $a0 #move the value of $a0 into $v0
lw $v1, 0($v0)
move $t0, $a0
loop: addi $t0, $t0, 4
lw $t1, 0($t0)
ble $t1, $v1, skip # go to skip if $t1 <= $v1
move $v0, $t0
move $v1, $t1
skip: bne $t0, $a1, loop
(1) Multiple choices question: what flow-control statement does ble $t1, $v1 implement? [1pt] A. if; B. for; C. while
(2) To show that you fully understand the function of this program, briefly explain the usage of the following 4 registers in the program. That is, what are these registers used for in the program. For example, for register $a1, it stores the address of the last element of array, indicating the end of array. [4pts]
Registers: $t0, $t1, $v0, $v1
(3) Briefly explain the usage of the two instructions move $v0, $t0; move $v1, $t1. [2pts]
(4) Briefly explain the usage of the instruction bne $t0, $a1, loop. [2pts]
(5) Briefly explain the function of this program, suppose the desired outputs of the program are the contents
of the registers $v0 and $v1. [3pts]
(6) Determine the contents of the registers $v0 and $v1 after executing the code. [3 pts]
S: .word 14, -29, 18, 30, -12, 12, 106, -7
la $a0, S # suppose $a0 = 0x20060000
addi $a1, $a0, 28 # $a1 stores the address of the last element S[7]
move $v0, $a0 # $v0 stores the address of the current maximum element
lw $v1, 0($v0) # $v1 stores the value of the current maximum element
move $t0, $a0 # initialize $t0 to be the address of the first element
loop: addi $t0, $t0, 4 # update $t0 to the address of the current element to be compared lw $t1, 0($t0) # $t1 stores the value of the current element to be compared ble $t1, $v1, skip # go to skip if $t1 <= current maximum
move $v0, $t0 # if $t1 is the current maximum, update $v0 and $v1
move $v1, $t1
skip: bne $t0, $a1, loop # check if reached the end of the array
(2) $t0 stores the address of the current array element to be compared
$t1 stores the value of the current array element to be compared 7
$v0 stores the address of the maximum element
$v1 stores the value of the maximum element
(3) since a larger element is found, update the address and value of the current maximum element
(4) by checking the address, determine if the program has reached the end of the array
(5) find the address and value of the maximum element in the array.
(6) $v0: 0x20060018
$v1: decimal value 106
DIGITAL LOGIC: FLIP-FLOPS [10PTS]
Consider a new type of flip-flop called X-Y flip-flip. It has two inputs X and Y and two outputs Q and 𝑄 ̄. Let 𝑄𝑡 be the current state of this X-Y flip-flop at time 𝑡 and 𝑄𝑡+1 be the next state. Its characteristic table is given as follows:
X Y 𝑄𝑡+1 000 0 1 𝑄𝑡′ 1 0 𝑄𝑡 111
(1) Derive the characteristic function 𝑄𝑡 +1 = 𝑓 (𝑄𝑡 , 𝑋 , 𝑌 ) of this X-Y Flip-Flop in simplified SOP form using Karnaugh map. Show your steps. [3 pts]
(2) Give the excitation table for this X-Y flip-flop. Use ’x’ to denote "don’t care" condition. [3 pts]
(3) Suppose that you are given a J-K flip-flop (the diagram of J-K is shown below), show how you can build the
above X-Y flip-flip using J-K flip-flop and other simple logic gates. Draw a diagram. [4 pts]
Fig. 4. Question 6-(3): J-K Flip-Flop.
DIGITAL LOGIC: FINITE STATE MACHINE [15PTS]
You are given a finite state machine with state diagram shown in Fig. 5. Implement the FSM using two J-K flip-flops. Specifically, the states are encoded as 𝐴 = 00, 𝐵 = 01, 𝐶 = 10, 𝐷 = 11. Denote the inputs of the two flip-flops as 𝐽0𝐾0 and 𝐽1𝐾1, respectively. Denote their output as 𝑄0 and 𝑄1, and use 𝑄1𝑄0 to represent the state (e.g., 𝑄1𝑄0 = 01 represents state 𝐵.). Use 𝑋 and 𝑍 to denote the external input and output, respectively.
Complete the following steps:
• Derive the state table of the FSM. [3pts]
• Derive the excitation table for the circuit. [4pts]
• Derive𝐽0,𝐾0,𝐽1,𝐾1 and𝑍 asfunctionsof𝑄1,𝑄0,𝑋,respectively.Specifically,useK-maptogetthesimplified
SOP forms of the five functions. [5pts] • Draw the circuit. [3pts]
Fig. 5. State diagram for Question 7.
X Y At Clt-11 OOOO
excitation ta b le
GivenJ-K : Qtti= JAE
to Qtti = ✗At -140¥
K=×' - i - - - frpts)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com