[SOLVED] algorithm Scheme html MIPS assembly computer architecture graph TCSS372 Computer Architecture Assignment 3

TCSS372 Computer Architecture Assignment 3
30 Points
This homework will test your understanding of concepts that we covered in lecture and Chapters 4 and 5 of your textbook. Submit your homework on Canvas before the due date and time as uwnetid1uwnetid2hw3 (if working in pairs) or uwnetidhw3.doc or docx or pdf, Crypt.asm. Submit all files at the same time.
You may scan your handwritten homework and upload as a single pdf document but it must be legible. No email submissions will be accepted. You must show your work wherever it is applicable to get full credit. Points will be taken off for incorrect submissions that dont follow the guidelines above.
1. (Datapath and Pipeline 10 Points)
Use the following sequence of instructions, to answer the following questions. Assume that they are executed on a 5-stage pipelined datapath:
add $t1, $t2, $t3 lw $t4, 4($t1) lw $t2, 0($t2)
or $t4, $t1, $t4 sw $t4, 0($t1)
a. Write down the order of the execution of the above instructions. Assume there is no forwarding or hazard detection and use nops to ensure correct execution. The first row is filled out as an example. Use the table below to fill in the values and feel free to add more rows and columns as necessary.
b. Repeat the same exercise as (a) this time using nops only when changing or rearranging these instructions cannot avoid a hazard.
c. Repeat the same exercise as (a) with forwarding, but without a hazard detection unit.
Instruction
C1
C2
C3
C4
C5
C6
C7
C8

add $t1, $t2, $t3
IF
ID
EX
MEM
WB

2. (MIPS Programming 10 Points)
a. Background: Cryptography, from the Greek word kryptos, meaning hidden, deals
with the science of hiding a message from eyes you do not want to understand the contents of the message. The desire to do this has existed ever since humankind was first able to write. There are many ways to keep something secret. One way is to physically hide the document. Another way is to encrypt the text you wish to remain secret. Some people use this to keep others from understanding the contents of the files in their computer. Encrypting a file requires an input message, called the plain text, and an encryption algorithm. An encryption algorithm transforms plain text into cipher text. Just like a door needs a key to lock and unlock it, an encryption algorithm often requires a key to encrypt and decrypt a message. Just like a homeowner can selectively give the key to the front door to only those they want to allow unaccompanied access, the author of a message can selectively give the encryption key to only those they want to be able to read the message. In order for someone to read the encrypted message, they have to decrypt the cipher text, which usually requires the key.
For example, suppose the plain text message is HELLO. An encryption algorithm consisting of nothing more than replacing each letter with the next letter in the alphabet would produce the cipher text IFMMP. If someone saw IFMMP, they would have no idea what it meant (unless, of course, they could figure it out, or had the key to decrypt it.) The key to encrypt in this case is pick the next letter in the alphabet, and the decryption key is pick the previous letter in the alphabet. The decryption algorithm simply replaces each letter with the one before it, and presto: the plain text HELLO is produced.
Implement, in MIPS assembly language, an encryption/decryption program that meets the following requirements:
Input: Your program should prompt the user for three separate inputs from the keyboard, as follows:
1. The prompt: Type (E)ncrypt/(D)ecrypt :
a. The user will type E or D. We will assume in this assignment that the user can type an E or D correctly. No validation is necessary.
b. Your program will accept that character, must store it in memory, and use it, as we shall see momentarily.
2. The prompt: Enter encryption key (1-9):
a. The user will type a single digit, from 1 to 9. We will assume in this assignment that the user can hit digit keys on the keyboard correctly. No validation is necessary. b. Your program will accept this digit, must store it, and use it to encrypt or decrypt the message.
3. The prompt: Enter message:
a. The user will input a character string from the keyboard, terminating the message with the key. We will assume in this assignment that the user can hit digit

keys on the keyboard correctly and enter the correct number of characters. No validation is necessary.
b. Your program will store the message in memory. You must reserve locations to store the message. In other words, the starting address of where it must be stored so that it doesnt interfere with other data stored.
The encryption algorithm is as follows:
1. The low order bit of the code will be toggled. That is, if it is a 1, it will be replaced by a 0; if it is a 0, it will be replaced by a 1.
2. The key will be added to the result of step 1 above.
For example, if the input (plain text) is A and the encryption key is 6, the program should take the ASCII value of A, 01000001, toggle bit [0:0], producing 01000000 and then add the encryption key, 6. The final output character would be 01000110, which is the ASCII value F.
The decryption algorithm is the reverse:
1. Subtract the encryption key from the ASCII code. 2. Toggle the low order bit of the result of step 1.
For example, if the input (cipher text) is F, and the encryption key is 6, we first subtract the encryption key (i.e., we add -6) from the ASCII value of F, 01000110 + 11111010, yielding 01000000. We then toggle bit [0:0], producing 01000001, which is the ASCII value for A.
Here are three different sample runs of the MIPS assembly program. The inputs are underlined.
Sample output 1:
Type (E)ncrypt/(D)ecrypt: E Enter encryption key (1-9): 6 Enter message: HELLO OJSST
program is finished running
Sample output 2:
Type (E)ncrypt/(D)ecrypt: D Enter encryption key (1-9): 6 Enter message: OJSST HELLO
program is finished running
Sample output 3:
Type (E)ncrypt/(D)ecrypt: E Enter encryption key (1-9): 6 Enter message: H
O
program is finished running

1. This program requires that you use syscalls. Use the reference at
https://courses.missouristate.edu/KenVollmar/mars/Help/SyscallHelp.html
2. It will be helpful to understand the conversion ASCII values into decimal or hex for alphabets and digits at http://www.asciitable.com/
3. Newline in ascii is decimal 10. Useful to check for end of input when user hits enter
4. Your program must use subroutines for encryption and decryption and for others that are
common across (toggle?)
5. All data or addresses must be defined in the. data section separated by the .text section
6. The input message and the output message must be stored in memory although the
program can be done without storing them. For Example: Look at the data segment below where the input and output are stored. This particular program is storing E (69) at x10010000, 6 at x10010004,
HELLO at x100100a0.
OJSST at x100100c0
7. Use inline comments to explain the logic or your program wont get full credit
8. Code must be formatted into three or four columns
label: opcode operands inline comment
If label doesnt fit, separate into two different lines. Heres a sample:

(a)
3. (Caches 6 Points) Here is a series of address references given as word addresses:
7, 13, 1, 28, 25, 17, 48, 49, 3, 13, 1, 9, 4, 27, 28, and 25.
a. Assuming a Direct-mapped cache with 16 one-word blocks that is initially empty,
label each reference in the list as a hit or a miss.
b. Now assume that the cache is a 2-way set associative, one-word blocks, total 16-
word capacity.
For each of your answers to both parts a & b fill in the table shown below. Show the final contents of the cache in each case. Assume a Least Recently Used replacement policy where applicable.
(b)
Address
Hit/Miss
7
13
1
28
25
17
48
49
3
13
1
9
4
27
28
25
Address
Hit/Miss
7
13
1
28
25
17
48
49
3
13
1
9
4
27
28
25

4. (Virtual memory 4 Points)
Page tables require fairly large amounts of memory, even if most of the entries are invalid. One solution is to use a hierarchy of page tables.
The virtual page number can be broken up into two pieces, a page table number and a page table offset, which is described in the figure below.
FIGURE 5.26 Mapping from a virtual to a physical address. The page size is 4 KiB. The number of physical pages allowed in memory is 218, since the physical page number has 18 bits in it. Thus, main memory can have at most 1 GiB, while the virtual address space is 4 GiB. (From your textbook)
The page table number can be used to index a first-level page table that provides a physical address for a second-level page table. The page table offset is used to index into the second-level page table to retrieve the physical page number. One way to arrange such a scheme is to have the second-level page tables occupy exactly one page of memory.
Assuming a 32-bit virtual address space with 4KB pages and 4 bytes per page table entry, how many bytes will each program need to use to store the first-level page table (which must always be in memory)? Provide information on how to decode the address (i.e. what bits for the page table number, page table offset and physical page offset). Explain your solution.