CS 230 Winter 2022 Assignment 5 : Subroutines in MIPS, CPU Pipeline and Performance Measures Due Date: Friday, March 25, 11:59 p.m. *** Note the new due date.****
• All submissions are to be completed through MarkUs (https://markus.student.cs.uwaterloo.ca/markus_cs230_w/en/assignments)
• Read the policy described in Learn regarding late submissions (https://www.student.cs.uwaterloo.ca/~cs230/w22/outline.shtml)
• Solutions for assignments will not be posted.
Copyright By PowCoder代写 加微信 powcoder
• Questions are approximately equally weighted.
1. For this question, you will be submitting two separate files. However, you may choose to develop the solution in a single file, and divide the code into separate files before submitting the final versions.
You should test the final versions of your solutions by concatenating the files before assembling them. Here is how you can do that in Linux:
cat a5q1b.asm a5q1a.asm > a5q1.asm
/u/cs230/pub/binasm < a5q1.asm > a5q1.mips
The first command concatenates the two files from part b) and part a) into a single file (note the order of the files). The second command assembles the joint files.
When we test your solution, we will providing our own versions of each part.
In other words, when we test your part a), we will use our own version of part b) and vice versa. This means your solution for each part should not depend on any details of the other part.
It is very important that the solutions for this question follow the register conventions described on Slide 29 of Module 2. The main purpose of this assignment is to test the creation and use of subprograms. The majority of the correctness marks will be connected to properly using the registers according to the conventions.
• Your programs must assemble and run properly with the given MIPS assembler binasm in the student.cs environment.
• The marks for this question will be based on correctness. If your program does not assemble properly, then the correctness marks will be 0. Test your submission thoroughly before submitting.
• Your solution should include comments at the beginning that include your name, your Quest ID, and a brief description of the program.
• You are not required to comment every line of your program. However, you should include inline comments that highlight the logical steps of your solution.
CS 230 Winter 2022 Assignment 5 Graham
(a) Recall the map function from CS115/135. This is an abstract list function that consumes a function and a list and produces a list where each element has been transformed by the function. For example (map sqr ’(1 2 3)) produces the list ’(1 4 9).
For this part, create a subroutine that is labelled map that has three arguments: the address of a function that itself has one parameter, the address of the beginning of an array, and the size of the array. The subroutine will create a copy of the elements of the array, where each element has been transformed by the function that was provided. The copy should appear in the memory addresses immediately following the original array. The subroutine should return the address of the first element of the newly created array. The original array elements should not change. For example, if the map subroutine is given the address of a subroutine that will calculate the square of a number, and the address of an array with values 1, 2, 3 and the size 3, then the values 1, 4, 9 would appear in memory locations immediately following 1, 2, 3.
Note that this subroutine will be calling another subroutine. This means that it is both a callee and a caller. The subroutine it calls has the right to change any registers that are designated as unsaved temporary. So, if this is an issue, you should save the important register values of map on the stack before calling another subroutine.
Submit the file a5q1a.asm.
(b) Write a program that uses the map subroutine from part a) to create a new array of transformed integers. The program will use the array front end, where the address of the beginning of the array is in register $1 and the size of the array is in register $2. Assume that the array is filled with positive integers. The new array will contain integers that are the numbers from the original array where the digits are reversed. So for example, if the original array had the values [31, 218, 4] the new array would have the values [13, 812, 4]. The original array elements should remain as they were. The address of the new array should appear in register $2.
The program must include a subroutine called reversedigits. This subroutine has a single argument that is a positive integer and returns an integer representing the positive integer equal to the number where the digits are reversed. For example, if the subroutine is given the integer 1735, it will return the integer 5371. The code for the subroutine should appear at the end of the file, after the instruction jr $31 of the main program.
CS 230 Winter 2022 Assignment 5 basic structure of this file will be:
;; Set up registers to call map subroutine
;; Call map subroutine
reversedigits:
;; Code for reversedigits subroutine
Note that this program should not work directly with the arrays. There will be a severe loss of correctness marks for solutions of part b) that directly access the elements of the arrays using lw and sw.
Submit the file a5q1b.asm.
CS 230 Winter 2022 Assignment 5 Graham
2. For this question you will be working with the following MIPS assembly program.
add $3, $1, $0 addi $4, $0, 4 mult $4, $2 mflo $4
add $4, $1, $4 addi $4, $4, −4 beq $3, $4, end slt $5, $4, $3 bne $5, $0, end lw $5, 0($3)
lw $6, 0($4)
sw $6, 0($3)
sw $5, 0($4) addi $3, $3, 4 addi $4, $4, −4 beq $0, $0, loop
(a) Write the machine code version of the program. The machine code instructions should be written as hexadecimal values. The file should contain each 8-digit hexadecimal number preceded by 0x (for a total of 10 characters) on a separate line. The alphadigits in the hexadecimal values should all be uppercase. See the solution for Question 3 of the practice problems for Lecture 14 for the expected format.
Submit the file a5q2a.txt.
(b) Assume you have a processor running at 16GHz with the cycles per instruction set
architecture defined as follows:
• Memory accesses: 10 cycles
• Branch/Jump accesses: 2 cycles • Everything else: 5 cycles
Assume that the program is run using the array front end and the user enters 4 for the array size, and the numbers: [5, 6, 7, 8] for the array contents.
What is the CPI of the processor for the program given the input described?
How much time would the processor take to complete the program instructions? Your answer should ignore the user time it takes to enter the data.
Show your work.
Submit the file a5q2b.pdf.
CS 230 Winter 2022 Assignment 5 Graham
3. Consider the following MIPS assembly code. Line numbers have been added to the beginning of each instruction so you can use them a references in subsequent questions.
1 2 3 4 5 6 7 8 9
beq $2, $0, end lw $3, 0($1)
slt $4, $3, $0 beq $4, $0, endif sub $3, $0, $3
sw $3, 0($1)
Assume that this program is run using the array frontend, and that register $1 contains the address of the first element of the array, and $2 contains the size of the array. Assume that the size of the array is 2, and that the numbers [4, -7] have been placed in the array. Assuming that no pipeline optimizations have been implemented (including forwarding) determine the number of cycles it takes to complete the execution of this program.
Justify your answer using a pipeline diagram similar to the diagram in the model solutions for Question 5 of the practice problems for Lecture 15 (albeit without any forwarding connections since you are assuming that forwarding has not been implemented). It may be helpful to use a spreadsheet to draw the diagram.
Suppose forwarding and static branch prediction have been implemented. How many cycles will be saved compared to the answer in part (b)? Identify which lines of stall bubbles from your diagram in part (b) will be eliminated because of forwarding, and which will be eliminated because of static branch prediction.
Suppose you ran the same code with an array that had 100 elements following the pattern, [1, -2, 3, -4, 5, -6, …, 99, -100]. What is the difference between the number of lines of stall bubbles saved using static branch prediction compared to the number of stall bubbles saved using dynamic branch prediction. Briefly justify your answer.
Submit the file a5q3.pdf.
endif: addi $2, $2, −1 addi $1, $1, 4
beq $0, $0, loop jr $31
Identify the pipeline hazards present in this code.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com