HW3 CS 5330.001 F23

pdf

School

University of Texas, Dallas *

*We aren’t endorsed by this school

Course

5330

Subject

Computer Science

Date

Feb 20, 2024

Type

pdf

Pages

Uploaded by PresidentFreedomWren42

Name: FENGLONG YANG NetID: fxy230000 Date: 10/24/2023 CS 5330.001 Assignment 3 (4%) Due 11:59pm, October 24, 2023 QUESTION 1 (15%) Assume the function declaration for func is “int func (int a, int b);” The code for function f is as follows: Int f (int a, int b, int c, int d) { Return func ( func (a, b), c + d) } a. Translate function f into MIPS assembly language. If you need to use registers $t0 through $t7, use the lower-number registers first. f: addi $sp, $sp, -12 sw $ra, 0($sp) sw $a0, 4($sp) sw $a1, 8($sp) jal func move $a0, $v0 add $a1, $a2, $a3 jal func lw $ra, 0($sp) lw $a0, 4($sp) lw $a1, 8($sp) addi $sp, $sp, 12 jr $ra b. Can we use the tail-call optimization in this function? If no, explain why not. If yes, what is the difference in the number of executed instructions in f with and without the optimization? Because the return value of f is just the return value of func without any additional operation, so theoretically it can be optimized by tail-call optimization to save the extra cost of stack allocation. But since f is not a recursive function, so using tail-call optimization here does not make great sense. c. Right before function f returns, what do we know about contents of registers $t5, $s3, $ra, and $sp? Keep in mind that we know what the entire function f looks like, but for

function func we only know its declaration. $t5: f does not update $t5, it could be any values (it is unsafe across functions, so it can be written by other functions) $s3: f does not update $s3, it will keep being the initial value of $s3 before f executes. $ra: the return address, specifically where the caller of f calls f. $sp: the stack pointer address, in f, when it restores (pop everything corresponding with f), the value of $sp will be the address corresponding with caller of f, QUESTION 2 (15%) Write a program in MIPS assembly language to convert an ASCII number string containing integer decimal strings, to an integer. Your program should expect register $a0 to hold the address of a null-terminated string containing some combination of the digits 0 through 9. Your program should compute the integer value equivalent to this string of digits, then place the number in register $v0. If a non-digit character appears anywhere in the string, your program should stop with the value -1 in register $v0. For example, if register $t9 points to a sequence of three bytes 50 10 , 52 10 , 0 10 (the null- terminated string “24”), then when the program stops, register $v0 should contain the value 24 10 . .main: move $t0, $a0 li $v0, 0 // Initialize $v0 to 0 cal: lb $t1, 0($t0) // load current byte beq $t1, 0, exit // can return if current is 010 blti $t1, 48, illegal // if currently it is out of number’s range, return -1 bgti $t1, 57, illegal li $t2, 10 mul $v0, $v0, $t2 // base * 10 sub $t1, $t1, 48 // Convert ASCII to integer add $v0, $v0, $t1 addi $t0, $t0, 1 // Increment pointer j cal illegal: li $v0, -1 j exit exit: … // syscall to exit the program QUESTION 3 (10%) a. Write the MIPS assembly code that creates the 32-bit constant 0010 0000 0000 0001 0100 1001 0010 0100 2 and stores that value to register $t1. Firstly, we need convert this binary into hex, 0010 0000 0000 0001 0100 1001 0010 0100 2 0X20014924

To store this value to $t1, we need execute: li $t1, 0x20014924 b. If the current value of the PC is 00000000 16 , can you use a single jump instruction to get to the PC address as shown by the 32-bit constant in a.? Explain. It cannot get to the address. The j instruction allows any address within 256M based on current PC. It will be able to get to target address if it has same value with PC in terms of the high 6 bit. Compare 0000 (high 4 bits of PC) with 0010 (high 4 bits of target address), it’s not same .

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

c. If the current value of the PC is 00000600 16 , can you use a single branch instruction to get to the PC address as shown by the 32-bit constant in a.? Explain. It cannot get to the address. The branch instruction allows any address within 32K based on current PC. It will be able to get to target address if it has same value with PC in terms of the high 14 bit. Obviously, they are not same. d. If the current value of the PC is 1FFFF000 16 , can you use a single branch instruction to get to the PC address as shown by the 32-bit constant in a.? Explain. It cannot get to the address. The branch instruction allows any address within 32K based on current PC. It will be able to get to target address if it has same value with PC in terms of the high 14 bit. Obviously, they are not same. QUESTION 4 (6%) a. What is 5ED4 – 07A4 when these values represent unsigned 16-bit hexadecimal numbers? The result should be written in hexadecimal. Show your work. 5ED4 - 07A4 = 5730 b. What is 5ED4 – 07A4 when these values represent signed 16-bit hexadecimal numbers stored in sign-magnitude format? The result should be written in hexadecimal. Show your work. (* sign-magnitude format is NOT the 2’s complement) Because the sign bit of both is 0, means they are both positive, so the result will be same with a) 5ED4 - 07A4 = 5730 QUESTION 5 (9%) a. Assume 185 and 122 are unsigned 8-bit decimal integers. Calculate 185 – 122. Is there overflow, underflow, or neither? Because it represents unsigned number, the range would be [0, 2^8-1]. 185-122 = 63, it is in this range, so neither overflow nor underflow. b. Assume 185 and 122 are signed 8-bit decimal integers stored in sign-magnitude format. Calculate 185 + 122. Is there overflow, underflow, or neither?

In form of sign-magnitude, the range would be [-127, 127], 185 cannot be stored by 8 bits with such form. c. Assume 185 and 122 are signed 8-bit decimal integers stored in sign-magnitude format. Calculate 185 - 122. Is there overflow, underflow, or neither? In form of sign-magnitude, the range would be [-127, 127], 185 cannot be stored by 8 bits with such form. QUESTION 6 (7%) One possible performance enhancement is to do a shift and add instead of an actual multiplication. Since 9 x 6, for example, can be written (2 x 2 x 2 + 1) x 6, we can calculate 9 x 6 by shifting 6 to the left 3 times and then adding 6 to that result. Show the best way to calculate 33 16 x 55 16 using shifts and adds/subtracts. Assume both inputs are 8-bit unsigned integers. First, I need figure out the good point of the performance enhancement method is using less shift operations to replace add operations. Based this idea, we can separate 55 16 (Which is equal to 85 10 ) to be (2 0 + 2 2 + 2 4 + 2 6 ). If so, the multiplication of 33 16 and 55 16 can be optimized to be the following steps: 1) Shift 00110011 2 to left 6 times, add it to the result. 2) Shift 00110011 2 to left 4 times, add it to the result. 3) Shift 00110011 2 to left 2 times, add it to the result. 4) Finally, add 00110011 2 to the result. Overall, it pays 3 times shift operations and 4 times add operations. QUESTION 7 (10%) a. What decimal number does the bit pattern 0C000000 16 represent if it is a floating-point number? Use the IEEE 754 standard. Show your work. 0C000000 16 = 0 000 1100 0 000 0000 0000 0000 0000 0000 Sign bit: 0 Exponent Section: 000 1100 0 2 = 24 10 Fraction Section: 0 000 0000 0000 0000 0000 0000 = (-1)^0 *(1) * 2^( 24 - 127) = 2^(-103) b. Write down the binary representation of the decimal number 63.25 assuming the IEEE 754 single precision format. Show your work.

63.25 = 63 + 0.25 = 111111 2 + .01 2 = 111111.01 = 1.1111101 x 2 5 // normalization = 2 0 * ( 1 + (1 x 2 -1 ) + (1 x 2 -2 ) + (1 x 2 -3 ) + (1 x 2 -4 ) + (1 x 2 -5 ) + (1 x 2 -7 ) ) * 2 (132-127) = 0 10000100 11111010000000000000000 QUESTION 8 (10%) IEEE 754-2008 contains a half precision that is only 16 bits wide. The leftmost bit is still the sign bit, the exponent is 5 bits wide and has a bias of 15, and the fraction is 10 bits long. A hidden 1 is assumed. Write down the bit pattern to represent -1.5625 x 10 -1 assuming a version of this format. Show your work. Comment on how the range and accuracy of this 16-bit floating point format compares to the single precision IEEE 754 standards. -1.5625 x 10 -1 = -1 * 10 / 2 6 = -1 * 1010 2 * 2 -6 = -1 * 1.010 * 2 -3 = (-1) 1 * 1.010 * 2 12-15 = 1 01100 0100000000 Then let us calculate the range and accuracy of the 16-bit float type number under IEEE 754- 2008 standard. Since the exponent part is 5 bits wide, means [00001 2 , 11110 2 ] = [1, 63]. With a bias of 15, and a fraction with [1,2] (00000…0, 11111…1, respectively). The smallest value would be ±1.0 × 2 -14 The largest value would be ±2.0 × 2 -48 Since the fraction is a 10-bit wide, then it will be approx 2 – 10 10 × log 10 2 = 10×0.3010≈3.01 ≈ 3 decimal digits of precision QUESTION 9 (9%) Add the numbers 0.75 10 and -0.6875 10 in binary using the binary floating-point addition algorithm, assuming that we keep 4-bits of precision. Show your work on Align binary points, Add significands, Normalize the result & check for overflow/underflow, and Round and normalize if necessary. 0.75 10 = 3 / 4 = 11 2 / 2 2 = 0.11 // Normalize = 1.1 * 2 -1

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

-0.6875 10 = - 11 / 16 = - 1011 2 / 2 4 = - 0.1011 // Normalize = - 1.011 * 2 -1 Right now both are aligned, then we do addition: 1.1 * 2 -1 + - 1.011 * 2 -1 = 0.001 * 2 -1 // Normalize = 1.0 * 2 -4 QUESTION 10 (9%) Multiply the numbers 0.75 10 and -0.6875 10 in binary using the binary floating-point multiplication algorithm, assuming that we keep 4-bits of precision. Show your work on Add exponents, Multiply significands, Normalize the result & check for overflow/underflow, Round and normalize if necessary, and Determine sign of result from signs of operands 0.75 10 = 3 / 4 = 11 2 / 2 2 = 0.11 // Normalize = 1.1 * 2 -1 -0.6875 10 = - 11 / 16 = - 1011 2 / 2 4 = - 0.1011 // Normalize = - 1.011 * 2 -1 1. Add exponents Unbiased = (-1) + (-1) = -2; Biased: ( – 1 + 127) + ( – 1 + 127) – 127 = – 3 + 127 = 124 2. Multiply significands 1.1 * 1.011 = 10.0001 => 10.0001 * 2 -2 3. Normalize result & check for over/underflow with no over/underflow 10.0001 * 2 -2 = 1.00001 * 2 -1 (underflow) 4. Round and renormalize if necessary (no change) 1.0001 * 2 -1 = 1.0 * 2 -1 5. Determine sign: +ve × – ve ⇒ – ve = – 1.0001 * 2 -1

BONUS (20%) Calculate the time necessary to perform a multiply using the approach described in the class (Figure 3.4 in the textbook) if an integer is 8 bits wide and each step of the operation takes 4 time units. Assume that in step 1a an addition is always performed – either the multiplicand will be added, or a zero will be. Also assume that the registers have already been initialized (you are just counting how long it takes to do the multiplication loop itself). If this is being done in hardware, the shifts of the multiplicand and multiplier can be done simultaneously. If this is being done in software, they will have to be done one after the other. Solve for each case. Show your work. This is the long multiplication flow: For software, since it has to be serializable. We need 8 times left shift on multiplicand, 8 times right shift on multiplier, and 8 times addition on product. Overall, it needs (8 + 8 + 8) * 4 = 96 time units. For hardware, with the optimization of parallel, means within one clock cycle, we can execute left shift, right shift, and addition simultaneously, then overall it needs 8 * 4 = 32 time units. SUBMISSION : 1. Clearly write your answers to the corresponding questions in a WORD or plain text file. 2. Submit your answers, clearly marked with your name, through eLearning by the due date. 3. Plagiarizing homework answers obtained from the internet or AI chatbots is not permitted. 4. No late homework or assignment will be accepted!

HW3 CS 5330.001 F23

Related Documents