Computer Architecture: October 2013

Assign 2 - Exercise 2.13 ASM

Link to source file
https://docs.google.com/file/d/0B3pg-UsmVkpFT2RGcUFVUkVYRVE/edit?usp=sharing

.data

space: .asciiz "\n" # Print New Line

.text
__start:
#2.13.1
#a
li $t0, 0xAAAAAAAA
li $t1, 0x12345678
sll $t2, $t0, 30
sll $t2, $t2, 14
or $t2, $t2, $t1
move $a0, $t2
jal printint
#b
li $t0, 0xF00DD00D
li $t1, 0x11111111
sll $t2, $t0, 30
sll $t2, $t2, 14
or $t2, $t2, $t1
move $a0, $t2
jal printint
#output
#305419896
#286331153

#2.13.2
#a
li $t0, 0xAAAAAAAA
li $t1, 0x12345678
sll $t2, $t0, 4
andi $t2, $t2, -1
move $a0, $t2
jal printint
#b
li $t0, 0xF00DD00D
li $t1, 0x11111111
sll $t2, $t0, 4
andi $t2, $t2, -1
move $a0, $t2
jal printint
#output
#-1431655776
#14483664

#2.13.3
#a
li $t0, 0xAAAAAAAA
li $t1, 0x12345678
srl $t2, $t0, 3 #shift right t0 by 3 store in t2
andi $t2, $t2, 0xFFEF #t2 += 0xFFEF
move $a0, $t2
jal printint
#b
li $t0, 0xF00DD00D
li $t1, 0x11111111
srl $t2, $t0, 3 #shift right t0 by 3 store in t2
andi $t2, $t2, 0xFFEF #t2 += 0xFFEF
move $a0, $t2
jal printint
#output
#21829
#47617

#2.13.4
li $t0, 0x0000A5A5
li $t1, 0x00005A5A
sll $t2, $t0, 1 #t2 = t0*2
andi $t2, $t2, -1 #t2 = t2 & -1
move $a0, $t2
jal printint

andi $t2, $t1, 0x00F0 #t2 = t1 & 0x00F0
srl $t2, $t2, 2 #t2 = t2 >> 2 # t2/4
move $a0, $t2
jal printint

#output
#84810
#20

#2.13.5
xor $t2, $t2, $t2 #clear register

li $t0, 0xA5A50000
li $t1, 0xA5A50000
sll $t2, $t0, 1 #t2 = t0*2
andi $t2, $t2,-1 #t2 = t2 & -1
move $a0, $t2
jal printint

andi $t2, $t1, 0x00F0 #t2 = t1 & 0x00F0
srl $t2, $t2, 2 #t2 = t2 >> 2 # t2/4
move $a0, $t2
jal printint
#output
#1263140864
#0

#2.13.6
xor $t2, $t2, $t2 #clear register

li $t0, 0xA5A5FFFF
li $t1, 0xA5A5FFFF
sll $t2, $t0, 1 #t2 = t0*2
andi $t2, $t2,-1 #t2 = t2 & -1
move $a0, $t2
jal printint

andi $t2, $t1, 0x00F0 #t2 = t1 & 0x00F0
srl $t2, $t2, 2 #t2 = t2 >> 2 # t2/4
move $a0, $t2
jal printint

#output
#1263271934
#60

j done

printint:
addi $v0, $zero, 1 # load appropriate system call code into register $v0;
# code for printing integer is 1
syscall # call operating system to perform operation

addi $v0, $zero, 4 # load appropriate system call code into register $v0;
# code for printing string is 4
la $a0, space # load address of the string
syscall

jr $ra

done:

Assign 2 - Exercise 2.13

Jumping ahead a little into something that was meant to be programmed.

In the following problems, the data table contains the values for registers $t0 and

$t1. You w be asked to perform several MIPS logical operations on these registers.

a. $t0 = 0xAAAAAAAA, $t1 = 0x12345678

b. $t0 = 0xF00DD00D, $t1 = 0x11111111

2.13.1 For the lines above, what is the value of $t2 for the following sequence of instructions?

sll $t2, $t0, 44 #left shift by t0 44 store in t2

or $t2, $t2, $t1 #t2 = t2 | t1

pseudo

t2 = (t0 << 44) || t1

= (0xAAAAAAAA << 44) || 0x12345678

= (0xF00DD00D << 44) || 0x11111111

This shift left operation is actually illegal, as we use 32 bit registers, so we can only shift left by 31 as a max. However, if we adjust this to shift 30, then shift 14, we get:

= (0xAAAAAAAA << 44) || 0x12345678

-0x45412988

= (0xF00DD00D << 44) || 0x11111111

0x75135111

we are shifting left the entire register and then doing an or, which copies t1

2.13.2 For the values in the table above, what is the value of $t2 for the following sequence of instructions?

sll $t2, $t0, 4 #shift left t0 by 4 store in t2

andi $t2, $t2, -1 #t2 += -1

pseudo

t2 = (t0 << 4) -1

= (0xAAAAAAAA << 4) -1

=0xAAAAAAA0

= (0xF00DD00D << 4) -1

=0x00DD00D0

This exercise is playing with bits. Visually we are dropping the left most hex digit and sweeping in a zero, in binary, its a bit different, no pun intended.

0b10101010101010101010101010101010 to

0b10101010101010101010101010100000

0b11110000000011011101000000001101 to

0b00000000110111010000000011010000

2.13.3 For the lines above, what is the value of $t2 for the following sequence of instructions?

srl $t2, $t0, 3 #shift right t0 by 3 store in t2

andi $t2, $t2, 0xFFEF #t2 += 0xFFEF

pseudo

t2 = (t0 >> 3) + 0xFFEF

= (0xAAAAAAAA >> 3) + 0xFFEF

=0x5545

= (0xF00DD00D >> 3) + 0xFFEF

=0xBA01

In the following exercise, the data table contains various MIPS logical operations.

You will be asked to find the result of these operations given values or registers

$t0 and $t1.

sll $t2, $t0, 1 #t2 = t0*2

andi $t2, $t2, –1 #t2 = t2 & -1

andi $t2, $t1, 0x00F0 #t2 = t1 & 0x00F0

srl $t2, 2 #illegal

srl $t2, 2 is an illegal instruction as srl takes in 2 registers and an arg. I am assuming this is a typo and am changing it.

andi $t2, $t1, 0x00F0 #t2 = t1 & 0x00F0

srl $t2, $t2, 2 #t2 = t2 >> 2 # t2/4

pseudo

a. $t2 = $t0 << 1

$t2 = $t2 & -1

$t2 = ($t0 << 1) & -1

b. $t2 = $t1 & 0x00F0

$t2 = $t2 >> 2

$t2 = ($t1 & 0x00F0) >> 2

Any why we need t0 and t1 is beyond me, since they are the same value and we don’t modify it, however, I copied what was in the book anyway.

2.13.4 Assume that $t0 = 0x0000A5A5 and $t1 = 0x00005A5A. What is

the value of $t2 after the two instructions in the table?

a) = (0x0000A5A5 << 1) & -1

=0x00014b4a

b) = (0x0000A5A5 & 0x00F0) >> 2

=(0x00000050) >> 2

=0x00000014

2.13.5 Assume that $t0 = 0xA5A50000 and $t1 = 0xA5A50000.What is

the value of $t2 after the two instructions in the table?

a) = (0xA5A50000 << 1) & -1

=0x4b4a0000

b) = (0xA5A50000 & 0x00F0) >> 2

=(0x0) >> 2

2.13.6 Assume that $t0 = 0xA5A5FFFF and $t1 = 0xA5A5FFFF. What is

the value of $t2 after the two instructions in the table?

a) = (0xA5A5FFFF << 1) & -1

= (0x4b4bfffe)

b) = (0xA5A5FFFF & 0x00F0) >> 2

= (0x000000f0) >> 2

=0x0000003c

In the statements above; for a) -1 is FFFFFFFF so, it will just mime the results of the first operation, where-as b actually required calculation, in most cases.

As stated in the mini intro, these problems were all about logical operations. I am not sure if they used hex to play visual games with the results, or force students to look at what is happening at the binary level, they are called bitwise operators after all.

As stated at the very beginning, I did up a MIPS program for this exercise. The only operands I have performed thus far was a shift left and some adds, so it was nice to touch each one of these.

Assign 2 - Exercise 2.4

Moving ahead one more jump in our C to ASM exercises. This time we are bringing in the handling of arrays and shifting. Since this is not the same as the previous 3 exercises, I am bringing load/store instructions back into the writeup. I am going to keep up with the ARM conversions even though a MIPS asm program is looking tempting again. However, I know there are later exercises where I will be writing programs.

Per Exercise Instructions:

f,g,h,i,j assigned to $s0…$s4

address A in $s6

address B in $s7

ARM Assumptions:

f,g,h,i,j assigned to r4,r5,r6,r7,r8

address of A in r11

address of B in r12

a) f = -g - A[4];

b)B[8] = A[i-j];

2.4.1 For the C statements above, what is the corresponding MIPS assembly code?

f = -g - A[4];

MIPS	Comment	ARM
lw $t0, 16($s6) add $t0, $t0, $s1 sub $s0, $zero, $t0	#load 4x4 into temp 0 #16($s6) is 4th address in A #add A[4], g = A[4] + g #f = 0 - $t0 = 0-(g + A[4])	ldr r0, [r11, #16] add r1, r0, r5 sub r4, #0, r1

B[8] = A[i-j];

MIPS	Comment	ARM
sub $t0, $s3, $s4 sll $t0, $t0, 2 add $t0, $t0, $s6 lw $t0, 0[$t0] sw $t0, 32[$s7]	#load i - j into t0 #shift left 2 to *4 #to adjust to register location #add t0 to &A #load value A[i-j] - into t0 #store t0 into B[8]	sub r0, r7, r8, lsl#2 add r0, r0, r11 ldr r0, [r0, #0] str r0, [r12, #32]

2.4.2 For the C statements above, how many MIPS assembly instructions are needed to perform the C statement?

a) 3

b) 5 (4 for ARM because ARM can combine an operand with an instruction - sub(s) Rd,Rn,<Operand2>)

2.4.3 For the C statements above, how many different registers are needed to carry out the C statement?

a) 1 temp, 2 saved
b) 1 temp, 4 saved

ARM Assumptions:

f,g,h,i,j assigned to r4,r5,r6,r7,r8

address of A in r11

address of B in r12

Since theres not too much writing of my own code in the rest of this, I am going to translate the given MIPS code into ARM.

MIPS	Comment	ARM
sll $s2, $s4, 1 add $s0, $s2, $s3 add $s0, $s0, $s1	#s2 = s4*2 #s0 = s2 + s3 #s0 = s0 + s1	lsl r6, r8, #1 add r4, r6, r7 add r4, r4, r5

MIPS	Comment	ARM
sll $t0, $s0, 2 add $t0, $s6, $t0 sll $t1, $s1, 2 add $t1, $s7, $t1 lw $s0, 0($t0) addi $t2, $t0, 4 lw $t0, 0($t2) add $t0, $t0, $s0 sw $t0, 0($t1)	# t0 = f * 4 # t0 = &A[f] # t1 = g * 4 # t1 = &B[g] # f = A[f] # t2 = &A[f+1] # t0 = A[f+1] # t0 = t0 + A[f] # B[g] = t0	lsl r0, r4, #2 add r0, r11, r0 lsl r1, r5, #2 add r1, r12, r1 ldr r4, [r0, #0] add r2, r0, #4 ldr r0, [r2, #0] add r0, r0, r4 str r0, [r1, #0]

2.4.4 For the MIPS assembly instructions above, what’s the corresponding C statement?

h = (j << 1) //j*2

f = h + i

f = f + g

compacts to

f = (j<<1)+i + g

sll $t0, $s0, 2 # $t0 = f * 4 --- integers 4 bytes

add $t0, $s6, $t0 # $t0 = &A[f]

sll $t1, $s1, 2 # $t1 = g * 4

add $t1, $s7, $t1 # $t1 = &B[g]

lw $s0, 0($t0) # f = A[f]

addi $t2, $t0, 4 #$t2 = &A[f+1]

lw $t0, 0($t2) #$t0 = A[f+1]

add $t0, $t0, $s0 #$t0 = $t0 + f

sw $t0, 0($t1) #B[g] = $t0

f = A[f]

f = A[f+1] + f

B[g] = f

compacts to

f = A[f] + A[f+1]

B[g] = f

B[g] = A[f] + A[f+1]

2.4.5 For the MIPS assembly instructions above, rewrite the assembly code to minimize the number MIPS instructions (if possible) needed to carry out the same function.

a) I believe a has the fewest instructions it can possibly have, as there are three instructions preformed 1 multiply, 2 add.

sll $t0, $s0, 2 # $t0 = f * 4 --- integers 4 bytes

add $t0, $s6, $t0 # $t0 = &A[f]

sll $t1, $s1, 2 # $t1 = g * 4

add $t1, $s7, $t1 # $t1 = &B[g]

lw $s0, 0($t0) # f = A[f]

addi $t2, $t0, 4 #$t2 = A[f+1]

lw $t0, 4($t0) #$t0 = A[f+1]

add $t0, $t0, $s0 #$t0 = $t0 + f

sw $t0, 0($t1) #B[g] = $t0

While this result was reached in the following problem, I found it to be applicable to this one as well. In ARM however, I believe we can reduce the number of instructions performed more-so.

mov r3, #4 #r3 = 4 so we can use mla

mla r0, r4, r3, r11 #r0 = r4 * 4 + r11

mla r1, r5, r3, r12 #r1 = r5 * 4 +r12

add r1, r12, r1

ldr r4, [r0, #0]

ldr r0, [r0, #4]

add r0, r0, r4

str r0, [r1, #0]

2.4.6

In both code examples we can remove one register by changing to the following:

sll $s0, $s4, 1

add $s0, $s0, $s3

add $s0, $s0, $s1

sll $t0, $s0, 2 # $t0 = f * 4 --- integers 4 bytes

add $t0, $s6, $t0 # $t0 = &A[f]

sll $t1, $s1, 2 # $t1 = g * 4

add $t1, $s7, $t1 # $t1 = &B[g]

lw $s0, 0($t0) # f = A[f]

addi $t2, $t0, 4 #$t2 = A[f+1]

lw $t0, 4($t0) #$t0 = A[f+1]

add $t0, $t0, $s0 #$t0 = $t0 + f

sw $t0, 0($t1) #B[g] = $t0

This whole exercise is one we went through thoroughly on the board, that being said, in the first instruction set, we forgot to add in the bit shift to adjust the address. I added it into this write up. Also, finding an opportunity to use the ARM’s optional operand was interesting. Haven’t had a chance to exploit that feature yet. In addition, this was the first application of mla in a instruction set for me. I had originally had an incorrect notation of using an arg instead of a register, this has since been corrected.

Sunday, October 13, 2013

Assign 2 - Exercise 2.13 ASM

Assign 2 - Exercise 2.13

Assign 2 - Exercise 2.4