50.1K

Verified Solution

Link Copied!

Linear search is the simplest search and can be done in just a few lines of code. The idea is to step through each element of an array, one-by-one, until you find an element in question (which we call the target). If you find it, you save its array index someplace, and can stop searching (or break). If you get all the way to the end of the array without finding the target, we use -1 as the index. For our case, we will be storing this index in the last position in the array. So we budget an array of size one more than the values through which we are searching. This code can be implemented in Java as shown below. Note the size of arr in this case is N+1, not N. The first N elements (indices 0 to N-1) are our values. Element N will be the index of the target (0 to N-1, or -1 if not found).

Task: At the point in IP1.part2.asm marked PUT CODE HERE FOR LINEAR SEARCH, translate the following lines:

int idx = -1;

for (int i = 0; i <= N-1; i++) {

if (arr[i] == target) {

idx = i;

break;

}

}

arr[N] = idx;

to MIPS.

Note: You can assume that the starting address of arr is in $s0 , N is in $s1, and target is in $s2.

For full credit, your solution should be a literal, line-by-line translation of this code to its MIPS equivalent. The goal of this project is not to write a linear search in MIPS. It is to take the above statements in the Java language, and translate them to equivalent statements in the MIPS language. This is therefore more of a translation project, and not a problem solving project. In fact, you could do this project without even knowing the above code does linear search. Registers You will need new $s registers for idx and i. Remember do not use $s0, $s1, or $s2 - or you will overwrite arr, N, and target. This is important, as I outlined in lecture - $t registers (being temporary) can lose their contents if a function is called. Arrays The elements of an array, being arbitrary size, can never use registers (as we only have 32 general purpose registers available in MIPS). Therefore: As a result, any access to an array element must at some point involve either a lw or a sw. And remember the difference: When translating the above three statements, a big key will be whether you are reading or writing the array. For example, the line: if (arr[i] == target) Is reading arr[i] and comparing it to target, signifying a lw. In an instruction like this: arr[N] = idx; arr[N] appears on the left of the equal assign, meaning it is changing (being written, signifying a sw). I covered in lecture how to calculate the address of an array element. You need this for lw and sw. A lw for example will do this (from MIPS Instruction Reference, for any $x, $base and offset): lw $x, offset($base) # $x = RAM[offset+$base] Variables in MIPS should always use $s registers. Array elements in MIPS will always be stored in RAM.

As a result, any access to an array element must at some point involve either a lw or a sw. And remember the difference: A lw reads a value from RAM to a register, and a sw writes a value from a register to RAM. When translating the above three statements, a big key will be whether you are reading or writing the array. For example, the line: if (arr[i] == target) Is reading arr[i] and comparing it to target, signifying a lw. In an instruction like this: arr[N] = idx; arr[N] appears on the left of the equal assign, meaning it is changing (being written, signifying a sw). I covered in lecture how to calculate the address of an array element. You need this for lw and sw. A lw for example will do this (from MIPS Instruction Reference, for any $x, $base and offset): lw $x, offset($base) # $x = RAM[offset+$base]

The if statement above requires you to use a lw to access arr[i]: if (arr[i] == target) When the array index (in this case i) is a variable, I recommend using 0 for offset and focus on getting $base to the address of arr[i]. Remember: This is because RAM is byte-addressed (every address holds one byte) and integers are 4 bytes. Therefore for the example above, if you can get a temporary register equal to the (starting address of arr) + 4i, you are in good shape. You can then make that the $base register of your lw instruction and use a zero offset. Loops The for loop includes an initializer (int i=0), a condition to keep looping (i <= N-1), and an increment (i++).

for (int i = 0; i <= N-1; i++) {

}

for loops are an abstraction used by Java convenient for counter-controlled repetition, but the order of execution of its initializer, condition, increment and body can be challenging. However, fundamentally: The algorithm for this conversion proceeds as shown in the following table, for a for loop with initializer A, condition B, increment C and body D, where each of A-D can be multiple statements long: For Loop Equivalent While Loop for (A; B; C) { D } A while (B) { D C } I strongly suggest converting this for loop to an equivalent while loop on paper first, before attempting to translate to MIPS. The outer loop involves subtraction by a constant (N-1), but MIPS has no subi instruction. Therefore:Subtraction by a constant in MIPS is done using an addi with a negative number.

Finally, we must bear in mind that MIPS will by default run all instructions sequentially unless explicitly told otherwise. Java has many abstractions available that allow us to say if this is true, run the next line(s) and as long as this is true, run the next line(s). Because of its default behavior, we have to tell MIPS explicitly when NOT to run the next line. The only comparator available in MIPS is b a >= b a <= b Language of Less a is less than b b is less than a a is not less than b b is not less than a Thinking contrapositively involves a different thought process when it comes to loops, with a condition B (note the contrapositive produces the equivalent result to the positive): Finally, remember at the close brace to jump back to the top! You can use a j instruction for this. If Statements The internal if statement: if (arr[i] == target) { } This is not a comparator, so there is no need to convert to the language of less. However, we must still think contrapositively. For an if statement with condition B: Break Statements When translating if statements and for loops to MIPS, we adopt two mottos: (1) Use the language of less. (2) Think contrapositively. Positive (Java): Loop while B is true. Contrapositive (MIPS): Loop until B is false. Positive (Java): If B is true, do this. Contrapositive (MIPS): If B is false, dont do this. All comparators can be converted to the language of less, and should be prior to any further translation

In Java, a break statement gets you out of the nearest enclosing for loop (marked HERE below): for (i = 0; i <= N-1; i++) { if (arr[i] == target) { break; } } // HERE Using the MIPS j instruction, coupled with a label at HERE, will be useful for making this happen. III. Selection Sort: Binary We now will translate your MIPS code into binary. I have supplied on Canvas a Java simulator (MIPSSimulator.java). Within this file, I initialized RAM to contain the unsorted array, starting from address zero. I also initialized $s0=0 (the starting address of arr), $s1=12 (the array size), and $s2=44 (the target). Note this means registers and RAM are in the same state as when you began writing your code in MARS. To test, open a Java project for MIPSSimulator.java. Place memfile.dat in the same directory as your Java project (note: this may be different from the directory with MIPSSimulator.java). Run MIPSSimulator.java. The array should display afterwards, with 5 at the end (the index of 44). To experiment with different targets, you can change this value in MIPSSimulator.java (it is marked with a comment). In the end however, you will only turn in memfile.dat. Translating MIPS instructions to binary will largely involve following the Instruction Reference and Register Table, as outlined in lecture and available on Canvas. The trickiest instructions are branches and jumps. The binary immediate value for these instructions works differently: As an example: add $s0, $s1, $s2 loop: beq $s0, $t0, hello # hello is 4 forward, immediate=4-1=3 lw $t1, 4($t0) addi $t0, $t0, 4 The MIPSSimulator expects as input one file memfile.dat. This file should consist solely of 32-bit MIPS instructions, one instruction per line, no spaces within or between instructions. Create this file memfile.dat and provide the binary representation of the MIPS code you added to IP1.part2.asm, one instruction per line (no spaces or empty lines). beq/bne: The immediate value is the amount of instructions away, takeaway one. j: The immediate value is the instruction number, starting from zero.

j loop # loop is instruction #1 (assuming I start from 0), immediate=1 hello: The binary translation of the above beq would be: 000100 10000 01000 0000000000000011 beq $s0 $t0 3 The binary translation of the above j would be: 000010 00000000000000000000000001 j 1

Answer & Explanation Solved by verified expert

See Answer