Computer Science 230
Computer Architecture and Assembly Language Spring 2022
Assignment 1
Due: Tuesday, February 8, 11:55 pm by Brightspace submission (Late submissions not accepted)
Copyright By PowCoder代写 加微信 powcoder
Programming environment
For this assignment you must ensure your work executes correctly on the MIPS Assembler and Runtime Simulator (MARS) as was installed during Lab #1. Assignment submissions prepared with the use of other MIPS assemblers or simulators will not be accepted. Solutions which prompt the user for input will not be accepted.
Individual work
This assignment is to be completed by each individual student (i.e., no group work). Naturally you will want to discuss aspects of the problem with fellow students, and such discussion is encouraged. However, sharing of code fragments is strictly forbidden without the express written permission of the course instructor (Zastre). If you are still unsure regarding what is permitted or have other questions about what constitutes appropriate collaboration, please contact me as soon as possible. (Code-similarity analysis tools will be used to examine submitted work.) The URLs of significant code fragments you have found and used in your solution must be cited in comments just before where such code has been used.
Objectives of this assignment
• Understand short problem descriptions for which an assembly-language solution is required.
• Use MIPS32 assembly language to write solutions to three such small problem.
• Use MARS to implement, simulate and test your solution.
• Hand draw a flowchart corresponding to your solution to the first problem.
Page 1 of 5
A few requirements for all of the code in Assignment #1
As these may be your first assembly-language programs, I want you to focus on only those aspects of the MIPS architecture that you need to get started. Therefore your submissions must obey the following:
• Please keep your code within the area indicated for student work in the provided files. Code outside of this area (these areas) will be modified during evaluation of student work (i.e., for different test cases).
• You must refer to registers by number, not by name. Register names will make more sense once we start to use procedures. For example, in your solutions you can use register $6, but you must not refer to this register as $a2.
• You must not use $0, $1, $2, and $31. You may otherwise use any other general-purpose register (i.e., registers $3 to $30 are available for your use). You are not, of course, required to use all of them!
• The only branching or branching-support instructions you may use are b, beq, bne, bgtz, blez, bgez, bltz, and slt. You are not, of course, required to use all of them!
• You are encouraged to use “basic” instructions for this first assignment. There also exist “pseudo” instructions which the MARS assembler converts into one or more basic instructions, and it can be a little difficult to understand what this is at first (i.e. harder to debug). However, you are not forbidden from using pseudo-instructions.
• You must not use functions/procedures for this assignment. Part (a): Computing the number of right-most zero/unset bits
A common task in assembly-language programming is counting the number of bits of a certain value within a word stored in a register. A closely-related problem is determining the number of trailing zeros or ones in a binary value. (And, of course, it is possible to also determine the number of leading zeros or ones in a binary value.)
Your task in this part of the assignment is to count the number of leading zeros in a 32-bit register value. For example, if the following is stored in $12:
0x00200020
and since we know that the binary representation of this number is:
0000 0000 0010 0000 0000 0000 0010 0000
then the right-most zeros are shown in bold, i.e. there are five right-most zero bits. Similarly if the following is stored in $12:
Page 2 of 5
0xdabbad00
and since we know that the binary representation of this number is:
1101 1010 1011 1011 1010 1101 0000 0000
then the trailing zeros are shown in bold, i.e. there are eight right-most zero bits.
Your task for part (a) is to complete the code in rightmost-zeros.asm that has been provided for you. Please read this file for more details on what is required. Some test cases are provided to you in this MIPS32 assembly-language file. The value for which you will find the rightmost bits will be register $12, and the result must be stored in register $15.
You must also draw by hand the flowchart of your solution and submit a scan or smartphone photo of the diagram as part of your assignment submission; please ensure this is a JPEG or PDF named “rightmost-zeros-flowchart.jpg” or “rightmost-zeros-flowchart.pdf” depending on the file format you have chosen.
Part (b): Edit distance
One specialization in computer science and mathematics is information theory, invented in the 1940s when the possibilities for the digital representation of data and signals were first deeply investigated. An example of a concept in information theory is edit distance, which describes much one data string differs from another data string. If we examine binary numbers instead of data strings, we can see such edit distance more clearly. For example, consider the 8-bit binary equivalents of 198 and 81:
The numbers are clearly different, and one measure of this is found by determining the number of bit positions in which the two binary numbers differ. Shown below are these two numbers again but with the different bits noted in bold:
11000110 01010001
That is, if we denote bit 7 as the left-most bit of each number, then bits 7, 4, 2, 1 and 0 (i.e. five bits) are different between each number. The edit distance of these two binary numbers is therefore five (5).
Your task for part (b) is to complete the code in edit-distance.asm that has been provided for you. Please read this file for more details on what is required. The values for which you will find the edit distance will be registers $12 and $13, with the stored in register $20.
Some test cases are provided to you in the provided assembly file.
Page 3 of 5
Part (c): An implementation of modulus
You are already familiar with modulus operations from first-year programming courses. Usually these are presented as the “%” binary operation and explained to you as the equivalent of finding the remainder from integer division operations.
It can also be explained as the result of successive subtractions. For example, consider the expression S % T where S = 219 and T = 61. If we repeatedly subtract until we have a value less than N, then that value must be S % T.
• 219–61=>158(subtraction#1) • 158–61=>97(subtraction#2) • 97–61=>36(subtraction#3)
The value of 36 obtained from the last subtraction is therefore 219 % 61.
Your task for part (a) is to complete the code in modulus-operation.asm that has been provided for you. In that file there are some comments giving several simplifying assumptions. For example, the value S will always be a positive two’s- complement number; the value T will always be a two’s complement positive number less than 128. If the values of S or T violate this requirements, a specific result is to be returned. One challenge you might face, however, is how to determine when to stop subtractions. You’ll want to think through how you check for this, even if it means doing one subtraction too many and therefore adding back a value. In your solution, S will be in $12, T in $13, and the result is to be in $19.
Some test cases are provided to you.
You are forbidden from using any MIPS32 multiply and divisions instructions as part of your solution.
What you must submit
• Your completed work in the three source code files (rightmost-zeros.asm, edit-distance.asm, modulus-operation.asm). Do not change the names of these files!
• Your work must use the provided skeleton files. Any other kinds of solutions will not be accepted.
• The scan / smartphone photo of your hand-drawn flowchart with the name of “rightmost-zeros-flowchart.jpg” or “rightmost-zeros- flowchart.pdf” depending on the format you have chosen.
Page 4 of 5
Evaluation
• 2 marks: rightmost zeros is correct for different word values (part a).
• 1 mark: Hand-drawn flowchart for the rightmost-zeros solution is correctly
prepared (part a).
• 3 marks: Edit distance is correct for different word values (part b).
• 5 marks: Modulus solution is correct for different integer values (part c).
• 1 mark: All submitted code properly formatted (i.e., indenting and comments
are correctly used), and files are correctly named. The meaning and purpose of registers in your code is clearly indicated (one comment per register).
Total marks: 12
Page 5 of 5