PostAddsense


Chapter 2 : Instructions - Language of the Computer Computer Organization


Design Principle 1: Simplicity favors regularity.

Design Principle 2: Smaller is faster.

Design Principle 3: Good design demands good compromises.







Terms


2.3 Operands of the Computer Hardware

word
The natural unit of access in a computer, usually a group of 32 bits; corresponds to the size of a register in the MIPS architecture.

address
A value used to delineate the location of a specific data element within a memory array.

alignment restriction
A requirement that data be aligned in memory on natural boundaries.

big-endian & little-endian


2.5 Representing Instructions in the Computer

opcode
The field that denotes the operation and format of an instruction.


2.7 Instructions for Making Decisions

basic block
A sequence of instructions without branches (except possibly at the end) and without branch targets or branch labels (except possibly at the beginning).


2.8 Supporting Procedures in Computer Hardware

program counter (PC)
The register containing the address of the instruction in the program being executed.

Figure 2.11







Exercises


※ The following solutions are my thoughts so that they may be wrong. If one of the solutions is wrong, please comment on that.

2.1 [5] <§2.2> For the following C statement, what is the corresponding MIPS assembly code? Assume that the variables f, g, h, and i are given and could be considered 32-bit integers as declared in a C program. Use a minimal number of MIPS assembly instructions.
f = g + (h–5);


addi i, h, -5
add f, g, i





2.2 [5] <§2.2> For the following MIPS assembly instructions above, what is a corresponding C statement?
add f, g, h
add f, i, f


f = i + (g + h);





2.3 [5] <§§2.2, 2.3> For the following C statement, what is the corresponding MIPS assembly code? Assume that the variables f, g, h, i, and j are assigned to registers s0, s1, s2, s3, and s4, respectively. Assume that the base address of the arrays A and B are in registers s6 and 7, respectively.
B[8] = A[i–j];


sub $t0, $s3, $s4 # $t0 = i-j
sll $t0, $t0, 2 # $t0 = (i-j) * 4
lw $t1, 0($s6) # $t1 = A[0]
add $t1, $t1, $t0 # $t1 = &A[i-j]
lw $t1, 0($t1) # $t1 = A[i-j]
sw $t1, 32($s7) # B[8] = A[i-j]





2.4 [5] <§§2.2, 2.3> For the MIPS assembly instructions above, what is the corresponding C statement? Assume that the variables f, g, h, i, and j are assigned to registers s0, s1, s2, s3, and s4, respectively. Assume that the base address of the arrays A and B are in registers $s6 and $s7, respectively.



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





2.5 [5] <§§2.2, 2.3> For the MIPS assembly instructions in Exercise 2.4, rewrite the assembly code to minimize the number if MIPS instructions (if possible) needed to carry out the same function.


sll $t0, $s0, 2 # $t0 = f * 4
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
lw $t0, 4($t0) # $t0 = A[f+1]
add $t0, $t0, $s0 # $t0 = A[f+1] + A[f]
sw $t0, 0($t1) # B[g] = $t0





2.6 The table below shows 32-bit values of an array stored in memory.

// in row 2 of the table of the textbook, the "Address" is 28, not 38.

Address Data
24 2
28 4
32 3
36 6
40 1

2.6.1 [5] <§§2.2, 2.3> For the memory locations in the table above, write C code to sort the data from lowest to highest, placing the lowest value in the smallest memory location shown in the figure. Assume that the data shown represents the C variable called Array, which is an array of type int, and that the first number in the array shown is the first element in the array. Assume that this particular machine is a byte-addressable machine and a word consists of four bytes.
2.6.2 [5] <§§2.2, 2.3> For the memory locations in the table above, write MIPS code to sort the data from lowest to highest, placing the lowest value in the smallest memory location. Use a minimum number of MIPS instructions. Assume the base address of Array is stored in register $s6.


C
temp = Array[0];
Array[0] = Array[4];
Array[4] = temp; // Array[4] = 2

temp = Array[1];
Array[1] = Array[4];
Array[4] = temp; // Array[4] = 4

temp = Array[3];
Array[3] = Array[4];
Array[4] = temp; // Array[4] = 6

MIPS
lw $t0, 0($s6)
lw $t1, 16($s6)
sw $t1, 0($s6) # A[0] = 1
sw $t0, 16($s6) # A[4] = 2

lw $t0, 4($s6)
lw $t1, 16($s6)
sw $t1, 4($s6) # A[1] = 2
sw $t0, 16($s6) # A[4] = 4

lw $t0, 12($s6)
lw $t1, 16($s6)
sw $t1, 12($s6) # A[3] = 4
sw $t0, 16($s6) # A[4] = 6





2.7 [5] <§2.3> Show how the value 0xabcdef12 would be arranged in memory of a little-endian and a big-endian machine. Assume the data is stored starting at address 0.


big-endian
(memory)
low ---------------------> high
ab | cd | ef | 12

little-endian
(memory)
low ---------------------> high
12 | ef | cd | ab





2.8 [5] <§2.4> Translate 0xabcdef12 into decimal.


  • 10x167 + 11x166 + … + 2x160 = 2882400018





2.9 [5] <§§2.2, 2.3> Translate the following C code to MIPS. Assume that the variables f, g, h, i, and j are assigned to registers s0, s1, s2, s3, and s4, respectively. Assume that the base address of the arrays A and B are in registers $s6 and s7, respectively. Assume that the elements of the arrays A and B are 4-byte words:
B[8] = A[i] + A[j];


sll $t0, $s3, 2
add $t0, $t0, $s6
lw $t0, 0($t0) # $t0 = A[i]
sll $t1, $s4, 2
add $t1, $t1, $s6
lw $t1, 0($t1) # $t1 = A[j]
add $t2, $t0, $t1
sw $t2, 32($s7) # B[8] = A[i] + A[j]





2.10 [5] <§§2.2, 2.3> Translate the following MIPS code to C. Assume that the variables f, g, h, i, and j are assigned to registers $s0, $s1, $s2, $s3, and $s4, respectively. Assume that the base address of the arrays A and B are in registers $s6 and s7, respectively.
addi $t0, $s6, 4
add $t1, $s6, $0
sw $t1, 0($t0)
lw $t0, 0($t0)
add $s0, $t1, $t0


A[1] = A[0];
f = A[0] + A[1];





2.11 [5] <§§2.3, 2.5> For each MIPS instruction, show the value of the opcode (OP), source register (RS), and target register (RT) fields. For the I-type instructions, show the value of the immediate field, and for the R-type instructions, show the value of the destination register (RD) field.


addi $t0, $s6, 4 # I-type, OP :  8, RS : 22, RT : 8, IM :  4
add $t1, $s6, $0 # R-type, OP : 32, RS : 22, RT : 0, RD :  9
sw $t1, 0($t0) # I-type, OP : 43, RS :  8, RT : 9, IM :  0
lw $t0, 0($t0) # I-type, OP : 35, RS :  8, RT : 8, IM :  0
add $s0, $t1, $t0 # R-type, OP : 32, RS :  9, RT : 8, RD : 16





2.12 Assume that registers $s0 and s1 hold the values 0x80000000 and 0xD0000000, respectively.

2.12.1 [5] <§2.4> What is the value of t0 for the following assembly code?
add t0, s0, s1
2.12.2 [5] <§2.4> Is the result in t0 the desired result, or has there been overflow?
2.12.3 [5] <§2.4> For the contents of registers s0 and s1 as specified above, what is the value of t0 for the following assembly code?
sub t0, s0, s1
2.12.4 [5] <§2.4> Is the result in t0 the desired result, or has there been overflow?
2.12.5 [5] <§2.4> For the contents of registers s0 and s1 as specified above, what is the value of t0 for the following assembly code?
add t0, s0, s1
add t0, t0, s0
2.12.6 [5] <§2.4> Is the result in t0 the desired result, or has there been overflow?

  1. t0 = s0 + s1 = 0x80000000 + 0xD0000000 = 0x150000000

  2. There has been overflow.

  3. t0 = s0 - s1 = 0x80000000 - 0xD0000000 = -0x50000000 (2's complement : 1011 0000 0000 0000 0000 0000 0000 0000)

  4. Yes, it is.

  5. t0 = s0 + s1 = 0x80000000 + 0xD0000000 = 0x150000000
    t0 = t0 + s0 = 0x150000000 + 0x80000000 = 0x1D0000000

  6. There has been overflow.




2.13 Assume that s0 holds the value 128ten.
2.13.1 [5] <§2.4> For the instruction add t0, s0, s1, what is the range(s) of values for s1 that would result in overflow?
2.13.2 [5] <§2.4> For the instruction sub t0, s0, s1, what is the range(s) of values for s1 that would result in overflow?
2.13.3 [5] <§2.4> For the instruction sub t0, s1, s0, what is the range(s) of values for s1 that would result in overflow?


  1. The range of values for$s1 is from 2147483520 to 2147483647. (binary : from 01111111111111111111111110000000) to 01111111111111111111111111111111)

    128ten = 0000 0000 0000 0000 0000 0000 1000 0000two

  2. The range of values for$s1 is from -2147483648 to -2147483520. (binary : from 10000000000000000000000000000000 to 10000000000000000000000001111111)

  3. The range of values for$s1 is from -2147483648 to -2147483521. (binary : from 10000000000000000000000000000000 to 10000000000000000000000001111111)

    -128ten = 11111111111111111111111110000000two




2.14 [5] <§§2.4, 2.5> Provide the type and assembly language instruction for the following binary value: 0000 0010 0001 0000 1000 0000 0010 0000two


R-type, add  s0, s0, $s0

opcodersrtrdshamtfunct
00000010000100001000000000100000





2.15 [5] <§§2.4, 2.5> Provide the type and hexadecimal representation of following instruction: sw $t1, 32(t2)


I-type, 0xAD490020 (binary : 1010 1101 0100 1001 0000 0000 0010 0000)

opcodersrtimmediate
10101101010010010000 0000 0010 0000





2.16 [5] <§2.5> Provide the type, assembly language instruction, and binary representation of instruction described by the following MIPS fields:
op=0, rs=3, rt=2, rd=3, shamt=0, funct=34


R-type, sub  $v1, $v1, $v0

opcodersrtrdshamtfunct
00000000011000100001100000100010





2.17 [5] <§2.5> Provide the type, assembly language instruction, and binary representation of instruction described by the following MIPS fields:
op=0x23, rs=1, rt=2, const=0x4


I-type, lw  $v0, 4($at)

opcodersrtimmediate
10001100001000100000 0000 0000 0100





2.18 [5] <§2.5> Assume that we would like to expand the MIPS register file to 128 registers and expand the instruction set to contain four times as many instructions.
2.18.1 [5] <§2.5> How would this affect the size of each of the bit fields in the R-type instructions?
2.18.2 [5] <§2.5> How would this affect the size of each of the bit fields in the I-type instructions?
2.18.3 [5] <§§2.5, 2.10> How could each of two propose changes decrease the size of an MIPS assembly program? On the other hand, how could the proposed change increase the size of an MIPS assembly program?

  1. All bit fields ends up with 2 addtional bits. There are 6 bit fields for R-type so the size of a word is 44.

  2. As the word size of R-type above is 44, the word size of I-type is equally 44.

  3. // I am sorry to say I don't know a solution for this problem. T_T





2.19 Assume the following register contents:
$t0 = 0xAAAAAAAA, $t1 = 0x12345678

2.19.1 [5] <§2.6> For the register values shown above, what is the value of $t2 for the following sequence of instructions?
sll $t2, $t0, 4
or $t2, $t2, $t1
2.19.2 [5] <§2.6> For the register values shown above, what is the value of $t2 for the following sequence of instructions?
sll $t2, $t0, 4
andi $t2, $t2, –1
2.19.3 [5] <§2.6> For the register values shown above, what is the value of $t2 for the following sequence of instructions?
srl $t2, $t0, 3
andi $t2, $t2, 0xFFEF

  1. $t2 = 0xBABEFEF8

  2. $t2 = 0xAAAAAAA0

  3. $t2 = 0x5545




2.20 [5] <§2.6> Find the shortest sequence of MIPS instructions that extracts bits 16 down to 11 from register $t0 and uses the value of this field to replace bits 31 down to 26 in register t1 without changing the other 26 bits of register t1.

solution 1
srl $t2, $t0, 11
sll $t2, $t2, 26
srl $t1, $t1,  6
add $t2, $t2, $t1

solution 2
andi $t2, $t0, 0x1F800
sll $t2, $t2, 15
srl $t1, $t1,  6
add $t2, $t2, $t1





2.21 [5] <§2.6> Provide a minimal set of MIPS instructions that may be used to implement the following pseudoinstruction:
not $t1, $t2 // bit-wise invert


nor $t1, $t2, $zero





2.22 [5] <§2.6> For the following C statement, write a minimal sequence of MIPS assembly instructions that does the identical operation. Assume $t1 = A, t2 = B, and s1 is the base address of C.
A = C[0] << 4;


lw $t1, 0($s1)
sll $t1, $t1, 4

// I don't know why B is displayed.





2.23 [5] <§2.7> Assume $t0 holds the value 0x00101000. What is the value of t2 after the following instructions?
slt $t2, 0, t0
bne t2, 0, ELSE
j  DONE
ELSE:  addi  t2, t2, 2
DONE:


  • the value of $t2 is 3.




2.24 [5] <§2.7> Suppose the program counter (PC) is set to 0x2000 0000. Is it possible to use the jump (j) MIPS assembly instruction to set the PC to the address as 0x4000 0000? Is it possible to use the branch-on-equal (beq) MIPS assembly instruction to set the PC to this same address?


  1. Though jump can locate to full 32bits address, it's not possible to jump to a address greater than 28bits with one single jump instruction.

  2. It's not possible to branch, since branch is I-type instruction, which can only use 18bits address.

Reference





2.25 The follow instruction is not included in the MIPS instruction set:
rpt $t2, loop # if(R[rs]>0) R[rs]=R[rs]–1, PC=PC+4+BranchAddr

2.25.1 [5] <§2.7> If this instruction were to be implemented in the MIPS instruction set, what is the most appropriate instruction format?
2.25.2 [5] <§2.7> What is the shortest sequence of MIPS instructions that performs the same operation?

  1. I-type

  2. Loop: slt $t3, $0, $t2
    beq $t3, $0, Exit
    sub $t2, $t2, 1
    j Loop
    Exit:




2.26 Consider the following MIPS loop:
LOOP: slt $t2, $0, $t1
beq $t2, $0, DONE
subi $t1, $t1, 1
addi $s2, $s2, 2
j LOOP
DONE:

2.26.1 [5] <§2.7> Assume that the register $t1 is initialized to the value 10. What is the value in register s2 assuming the s2 is initially zero?
2.26.2 [5] <§2.7> For each of the loops above, write the equivalent C code routine. Assume that the registers s1, $s2, t1, and t2 are integers A, B, i, and temp, respectively.
2.26.3 [5] <§2.7> For the loops written in MIPS assembly above, assume that the register t1 is initialized to the value N. How many MIPS instructions are executed?

  1. $s2 = 20

  2. while(i>0)
        i = i-1;
       B = B+2;

  3. the loop is executed N*5+2 times




2.27 [5] <§2.7> Translate the following C code to MIPS assembly code. Use a minimum number of instructions. Assume that the values of a, b, i, and j are in registers $s0, s1, t0, and t1, respectively. Also, assume that register s2 holds the base address of the array D.
for(i=0; i<a; i++)
for(j=0; j<b; j++)
D[4*j] = i + j;


add $t0, $0, $0 # i = 0
L1: slt $t2, $t0, $s0 # i < a
beq $t2, $0, Exit # $t2 == 0, go to Exit
add $t1, $0, $0 # j = 0
L2: slt $t2, $t1, $s1 # j < b
beq $t2, $0, L3 # if $t2 == 0, go to L3
add $t2, $t0, $t1 # i+j
sll $t4, $t1, 4 # $t4 = 4*j (sll was written instead of mul.)
add $t3, $t4, $s2 # $t3 = &D[4*j]
sw $t2, 0($t3) # D[4*j] = i+j
addi $t1, $t1, 1 # j = j+1
j L2
L3: addi $t0, $t0, 1
# i = i+1
j L1
Exit:





2.28 [5] <§2.7> How many MIPS instructions does it take to implement the C code from exercise 27? If the variables a and b are initialized to 10 and 1 and all elements of D are initially 0, what is the total number of MIPS instructions that is executed to complete the loop?

  1. formula = 3 + a*(4 + (3 + b*8))
    (Inner) 3 + b*4 + b*4
    (Outer) 3 + a*4 + a*(Inner)


  2. the total number of MIPS instrucitons = 3 + 10*(4 + (3 + 1*8)) = 153



// 문제에는 bne $t2, $s0, LOOP 라고 나와있는데 오타라고 생각하여 $s0 -> $0로 수정합니다.
2.29 [5] <§2.7> Translate the following loop into C. Assume that the C-level integer i is held in register $t1, $s2 holds the C-level integer called result, and $s0 holds the base address of the integer MemArray.
addi $t1, $0, $0
LOOP: lw $s1, 0($s0)
add $s2, $s2, $s1
addi $s0, $s0, 4
addi $t1, $t1, 1
slti $t2, $t1, 100
bne $t2, $0, LOOP


i = 0;
do {
  result += MemArray[i];
  i++;
} while(i<100);





2.30 [5] <§2.7> Rewrite the loop from Exercise 2.29 reduce the number of MIPS instructions executed.


addi $t1, $s0, 400
LOOP: lw $s1, 0($s0)
add $s2, $s2, $s1
addi $s0, $s0, 4
slti $t2, $s0, $t1
bne $t2, $0, LOOP





2.31 [5] <§2.8> Implement the following C code in MIPS assembly. What is the total number of MIPS instructions needed to execute the function?
int fib(int n) {
   if (n==0)
      return 0;
   else if (n==1)
      return 1;
   else
      return fib(n-1) + fib(n-2);
}

  • We assume $a0 is non-negative.
fib:
addi $sp, $sp, -12 # allocate stack frame of 12 bytes
sw $a0, 8($sp)
save n
sw $ra, 4($sp) #
save return address
sw $s0, 0($sp) #
save $s0

slti $t0, $a0, 2
fib(i) = i for i = 0, 1
beq $t0, $0, else
add $v0, $a0, $0 # $v0 = 0 or 1
j exit # go to exit
else:
addi $a0, $a0, -1 # fib(n-1)
jal fib
# recursive call
add $s0, $v0, $0
addi $a0, $a0, -1 # fib(n-2)
jal fib
# recursive call
add $v0, $v0, $s0
exit:
lw $a0, 8($sp)
# restore $a0
lw $ra, 4($sp) # restore return address
lw $s0, 0($sp) # restore $s0
addi $sp, $sp, 12 # free stack frame

jr $ra # return to caller





2.32 [5] <§2.8> Functions can often be implemented by compilers “in-line.” An in-line function is when the body of the function is copied into the program space, allowing the overhead of the function call to be eliminated. Implement an “in-line” version of the the C code in the table in MIPS assembly. What is the reduction in the total number of MIPS assembly instructions needed to complete the function? Assume that the C variable n is initialized to 5.

  • Due to recursive nature of the code, not possible for the compiler to in-line the function call.





2.33 [5] <§2.8> For each function call, show the contents of the stack after the function call is made. Assume the stack pointer is originally at address 0x7ffffffc, and follow the register conventions as specified in Figure 2.11.

  • Assume that the C variable n is initialized to 3.

    0x7ffffff0 $a0 address
    0x7fffffe4 save return address of caller (n=3)
    0x7fffffd8 $s0 address

    0x7fffffcc $a0 address
    0x7fffffc0 save return address of 1st recursive call (n=2)
    0x7fffffb4
    $s0 address

    0x7fffffa8 $a0 address
    0x7fffff9c save return address of 2nd recursive call (n=1)
    0x7fffff90 $s0 address

    0x7fffffa8 restore stack pointer of 2nd recursive call

    0x7fffffa8 $a0 address
    0x7fffff9c save return address of 3rd recursive call (n=0)
    0x7fffff90 $s0 address

    0x7fffffa8 restore stack pointer of 3rd recursive call

    0x7fffffcc restore stack pointer of 1st recursive call

    0x7fffffcc
    $a0 address
    0x7fffffc0 save return address of 4th recursive call (n=1)
    0x7fffffb4 $s0 address

    0x7fffffcc restore stack pointer of 4th recursive call

    0x7ffffff0 restore stack pointer of caller




2.34 Translate function f into MIPS assembly language. If you need to use registers $t0 through $t7, use the lower-numbered registers first. Assume the function declaration for func is “int func(int a, int b);”. The code for function f is as follows:
int f(int a, int b, int c, int d){
return func(func(a,b),c+d);
}


f: addi $sp, $sp, -4 # allocate stack frame of 4 bytes
sw $ra, 0($sp) # save return address
jal func # call func(a,b)
add $a0, $v0, $0 # $a0 = result of func(a,b)
add $a1, $a2, $a3 # $a1 = c+d
jal func # call func(func(a,b), c+d)
lw $ra, 0($sp) # restore return address
addi $sp, $sp, 4 # free stack frame
jr $ra # return to caller





2.35 [5] <§2.8> Can we use the tail-call optimization in this function? If no, explain why not. If yes, what is the difference in the number of executed instructions in f with and without the optimization?


※ What Is Tail Call Optimization? : http://stackoverflow.com/questions/310974/what-is-tail-call-optimization
  • Yes, we can.Tail-call optimization is where you are able to avoid allocating a new stack frame for a function because the calling function will simply return the value that it gets from the called function.




2.36 [5] <§2.8> Right before your function f from Exercise 2.34 returns, what do we know about contents of registers $t5, $s3, $ra, and $sp? Keep in mind that we know what the entire function f looks like, but for function func we only know its declaration.


  • Register $ra is equal to the return address in the caller function, registers sp and s3 have the same values they had when function f was called, and register t5 can have an arbitrary value. For t5, note that although function f does not modify it, function func is allowed to modify it so we cannot assume anything about $t5 after function func has been called.




2.37 [5] <§2.9> Write a program in MIPS assembly language to convert an ASCII number string containing positive and negative integer decimal strings, to an integer. Your program should expect register $a0 to hold the address of a null-terminated string containing some combination of the digits 0 through 9. Your program should compute the integer value equivalent to this string of digits, then place the number in register v0. If a non-digit character appears anywhere in the string, your program should stop with the value −1 in register v0. For example, if register a0 points to a sequence of three bytes 50ten, 52ten, 0ten (the null-terminated string “24”), then when the program stops, register v0 should contain the value 24ten.


str2int: # convert string to integer
li $t5, 0x2B # $t5 = '+'
li $t6, 0x30 # $t6 = '0'
li $t7, 0x39 # $t7 = '9'
li $v0, 0 # initialize $v0 = 0
add $t0, $0, $a0 # $t0 = pointer to string
lbu $t1, 0($t0) # load $t1 = sign character
add $t3, $t1, $0 # $t3 = sign character
addiu $t0, $t0, 1 # point to next char
lbu $t1, 0($t0) # load $t1 = digit character
LOOP:
slt $t2, $t1, $t6 # char < '0'
bne $t2, $0, NoDigit
slt $t2, $t1, $t7 # char > '9'
beq $t2, $0, NoDigit
subu $t1, $t1, $t6 # convert char to integer
mul $v0, $v0, 10 # multiply by 10
add $v0, $v0, $t1 # $v0 = $v0 * 10 + digit
addiu $t0, $t0, 1 # point to next char
lbu $t1, 0($t0) # load $t1 = next digit
bne $t1, $0, LOOP # branch if not end of string
bne $t3, $t5, negative # if $t3 != '+', go to negative
jr $ra # return integer value
negative:
sub $v0, $0, $v0 # -$v0
jr $ra # return integer value
NoDigit:
li $v0, -1 # return -1 in $v0
jr $ra





2.38 [5] <§2.9> For the following code:
lbu $t0, 0($t1)
sw $t0, 0($t2)

Assume that the register t1 contains the address 0x1000 0000 and the register t2 contains the address 0x1000 0010. Note the MIPS architecture utilizes big-endian addressing. Assume that the data (in hexadecimal) at address 0x1000 0000 is: 0x11223344. What value is stored at the address pointed to by register t2?

  • $t2value = 0x0000 0011 (=17ten)

    big-endian format in memory
    (high)
    44
    33
    22
    11
    (low)




2.39 [5] <§2.10> Write the MIPS assembly code that creates the 32-bit constant 0010 0000 0000 0001 0100 1001 0010 0100two and stores that value to register $t1.


lui $t0, 0x2001 # $t0 = 0010 0000 0000 0001 0000 0000 0000 0000two
ori $t0, 0x4924 # $t0 = 0010 0000 0000 0001 0100 1001 0010 0100two 
add $t1, $t0, $0 # save $t0 in $t1 ( $t0 = 0x20014924)





2.40 [5] <§§2.6, 2.10> If the current value of the PC is 0x00000000, can you use a single jump instruction to get to the PC address as shown in Exercise 2.39?

  • We can't use a single jump instruction, since the jump address range is 0xF8000004 ~ 0x08000003.

    PC + 4 + 0x07FF FFFF = 0x0800 0003
    PC + 4 - 0x0800 0000  = 0xF800 0004




2.41 [5] <§§2.6, 2.10> If the current value of the PC is 0x00000600, can you use a single branch instruction to get to the PC address as shown in Exercise 2.39?

  • we can't use a single branch instruction, since the branch address range is 0xFFFFE604 ~ 0x00020600, 

    PC + 4 + 0x1FFFC = 0x0002 0600
    PC + 4 - 0x20000   = 0xFFFE 0604




2.42 [5] <§§2.6, 2.10> If the current value of the PC is 0x1FFFf000, can you use a single branch instruction to get to the PC address as shown in Exercise 2.39?

  • we can use a single branch instruction, since the branch address range is 0x1FFDF004 ~ 0x2001F000

    PC + 4 + 0x1FFFC = 0x2001 F000
    PC + 4 - 0x20000   = 0x1FFD F004




2.43 [5] <§2.11> Write the MIPS assembly code to implement the following C code:
lock(lk);
shvar=max(shvar,x);
unlock(lk);

Assume that the address of the lk variable is in $a0, the address of the shvar variable is in a1, and the value of variable x is in $a2. Your critical section should not contain any function calls. Use ll/sc instructions to implement the lock() operation, and the unlock() operation is simply an ordinary store instruction.


again: addi $a0, $0, 1 # lock(lk)
ll $t0, 0($s0)
sc $a0, 0($s0)
beq $a0, $0, again # branch if store fails
slt $t1, $a1, $a2 shvar = max(shvar,x)
beq $t1, $0, shvar # if shvar > x, go to shvar
add $a1, $a2, $0
j ul
shvar: add $a1, $a1, $0
ul: addi $a0, $0, $0 # unlock(lk)
sw $a0, 0($s0)







2.44 [5] <§2.11> Repeat Exercise 2.43, but this time use ll/sc to perform an atomic update of the shvar variable directly, without using lock() and unlock(). Note that in this problem there is no variable lk.


// I didn't understand this exercise.





2.45 [5] <§2.11> Using your code from Exercise 2.43 as an example, explain what happens when two processors begin to execute this critical section at the same time, assuming that each processor executes exactly one instruction per cycle.


// I didn't understand this exercise.





2.46 Assume for a given processor the CPI of arithmetic instructions is 1, the CPI of load/store instructions is 10, and the CPI of branch instructions is 3. Assume a program has the following instruction breakdowns: 500 million arithmetic instructions, 300 million load/store instructions, 100 million branch instructions.
2.46.1 [5] <§2.19> Suppose that new, more powerful arithmetic instructions are added to the instruction set. On average, through the use of these more powerful arithmetic instructions, we can reduce the number of arithmetic instructions needed to execute a program by 25%, and the cost of increasing the clock cycle time by only 10%. Is this a good design choice? Why?
2.46.2 [5] <§2.19> Suppose that we find a way to double the performance of arithmetic instructions. What is the overall speedup of our machine? What if we find a way to improve the performance of arithmetic instructions by 10 times?


// I wouldn't like to solve 2.46 ~ 2.47 since in this chapter I think performance is not a important portion.





2.47 Assume that for a given program 70% of the executed instructions are arithmetic, 10% are load/store, and 20% are branch.
2.47.1 [5] <§2.19> Given the instruction mix and the assumption that an arithmetic instruction requires 2 cycles, a load/store instruction takes 6 cycles, and a branch instruction takes 3 cycles, find the average CPI.
2.47.2 [5] <§2.19> For a 25% improvement in performance, how many cycles, on average, may an arithmetic instruction take if load/store and branch instructions are not improved at all?
2.47.3 [5] <§2.19> For a 50% improvement in performance, how many cycles, on average, may an arithmetic instruction take if load/store and branch instructions are not improved at all?







References



2.27

2.32, 2.33, 2.34, 2.36, 2.37

2.41




덧글

  • asd 2015/04/10 20:54 # 삭제

    야 빨리 3단원 풀어
  • 불타는 아이스크림 2015/04/10 21:56 #

    네 ㅠㅠ
  • asd 2015/10/11 18:50 # 삭제

    2.3번에서 곱하기 할때
    sll$t0, $t0, 4 가 아니라
    sll$t0, $t0, 2 이네요^^.
  • 불타는 아이스크림 2015/10/18 16:17 #

    감사합니다. 수정했습니다.
  • 2015/10/21 07:46 # 삭제 비공개

    비공개 덧글입니다.
  • 불타는 아이스크림 2015/10/21 18:14 #

    http://www.mrc.uidaho.edu/mrc/people/jff/digital/MIPSir.html

    위에 사이트 가보셔서 slt 검색하시면 상세히 나오구요.

    slt를 해석하면 set on less than 의 약자예요. 예를 들면, "a가 b보다 작으면 어떤 값을 설정해라" 이런 거예요. 같다는 조건은 없어요.

    LOOP:slt t2,0, t1
    beq t2, 0,DONE
    subi t1, t1,1
    addi s2, s2,2
    j LOOP
    DONE:

    맨처음 slt문에서 t1보다 0이 작으면 true니 t2=1이고,t1보다 0이 크면 false니 t2=0이겠죠?

    만약0이 t1보다 작으면(즉, t1이0보다크면)t2가 1이 되죠. 그 다음 beq에서 $t2이 0과 같으면 DONE으로 가라고 하니까 반복문을 빠져나가라는 소리죠.

    이해되셨는지 모르겠네요.
  • 씹샘블리 2016/02/21 16:24 # 삭제

    2.40 자세한 설명좀 부탁드려도 될까요,,?
    PC 어드레스에 +4를 왜 붙이는거고,

    2.39의 0x20014924 hexa가
    어떻게 0x07FF FFFF 로 변했는지도 도저히 감이 안잡히네요ㅠㅠ

    고수님의 도움 부탁드려요,,
  • 불타는 아이스크림 2016/03/02 02:30 #

    1. 점프할 때에 PC+4 된 주소부터 시작합니다. (기존 PC 주소를 쓴다면 점프를 할 수 있는 공간이 1개 줄어들게 되니깐요. 똑똑하신 설계자분들임.) 그래서 점프 명령어의 26bit 부분이 0이면 자동적으로 그 다음 명령어로 점프하게 되는 거죠.

    2. 답은 점프 "명령어를 사용할 수 없다" 입니다. 단순히 점프할 수 있는 범위 ((PC + 26bit) or (PC - 26bit)) 만 표시했습니다. 범위를 벗어나니까 문제에 대한 답은 없는거죠.
  • rt 2016/03/22 12:45 # 삭제

    2.13.3 문제에서 s1의 범위가 -2147483648 이상 -2147483520 미만이 되야하는거 아닌가요? s1 = -2147483520 이면 t0이 -2147483648이니까 오버플로우가 아니지 않나요?
  • 불타는 아이스크림 2016/04/01 02:48 #

    네. 맞습니다. 음수 범위이므로 -2147483521 이네요. 수정했습니다.
  • 꼬질꼬질한 둘리 2016/03/22 13:01 #

    2.19.1 문제에서 sll $t2, $t0, 44를 하면 $t2에 0x00000000, 이 저장되서 or을 하더라도 그대로 $t1의 값이 $t2로 가는게 아닌가요?
    문제 풀이좀 부탁드립니다
  • 불타는 아이스크림 2016/04/01 03:00 #

    sll $t2, $t0, 4
    // $t2 에 $t0을 left shift 4번 한 것을 저장. $t2 = 0xAAAAAAA0
  • 우로포 2016/04/12 08:02 # 삭제

    2.34 문제에서, $sp에 -4만 한 이유가 return address때문은거같은데요
    이런 문제에서 보통 $sp에 얼마나 - 하는지는 보통 어떻게 알수있나요??
  • 불타는 아이스크림 2016/04/16 19:37 #

    컴퓨터 주소 체계가 4bytes 이므로 -4를 사용합니다. 주소 저장 공간이 x개 필요하다면 x * (-4) 만큼 선언해줘야겠죠.
  • 우로포 2016/04/13 01:43 # 삭제

    2.27에서 L2 에서 D[4*j] = i + j; 를 실행하는데, i를 L1에서 너무 일찍 증가시키는거 아닌가요?
    i 를 L2 오기전 L1에서 증가시키면
    L2 에서 D[4*j] = i + j;를 할때 i는 이미 1이 되버리는데, 시작값은 0이 되야하지 않을까요?
  • 불타는 아이스크림 2016/04/16 19:58 #

    맞습니다. 코드 재수정 했습니다. 알려주셔서 감사합니다.
  • 우로포 2016/04/16 01:01 # 삭제

    2.30
    addi$t1, $0, 400 에서 "$0" 대신 "$s0"가 되어야할거같은데요
    여기서 $s0가 0부터 시작한다는 조건이 성립이되어야는데,
    문제에서는 그러한 조건이 명시되어있지 않아서, $0을 사용하면 무한반복문이 되지않을까요
    예를들어 $s0 가 398에서 시작한다고 가정하면 무한반복문에 빠지겠죠.
  • 불타는 아이스크림 2016/04/16 20:40 #

    네. 오타로 인해 빠졌었네요. 그리고 문장 하나 더 추가해서 올바르게 작동하도록 했습니다.
  • 감사합니다 2016/09/30 05:45 # 삭제

    2.28 에서 저 식은 어떻게 세우신 건가요??? 저는 세려보니까 153개 나오는데...
  • 불타는 아이스크림 2016/10/19 07:38 #

    식을 잘못 세워서 수정했습니다. 153개가 맞아요.
  • 2016/10/12 14:05 # 비공개

    비공개 덧글입니다.
  • 2016/10/19 07:49 # 비공개

    비공개 답글입니다.
  • elrlemrm 2016/10/15 18:19 # 삭제

    2.30에
    bne$t1, $s0, LOOP
    에서
    $t1이 아니라 $t2아닌가요??
  • 불타는 아이스크림 2016/10/19 15:12 #

    네. 맞습니다. 수정했습니다.
  • 궁금자 2016/10/19 23:21 # 삭제

    2.29 에서 bne $t2,$s0,LOOP 문장에서 $s0 대신 $0 이어야 하는거 아닌가요?
    문제가 틀린건지? 아님 제가 잘못 이해 하는건지 모르겠네요ㅠㅜ
  • 궁금자 2016/10/19 23:36 # 삭제

    while문에서 i<100 이라는 근거가 생기려면 $s0 대신 $0 이 아닌가 하는 궁금증입니다
  • 불타는 아이스크림 2016/10/20 05:17 #

    네. 저도 그게 잘못됐다고 생각하는데요. $s0는 오타가 아닐까 생각하네요. 0이어야 조건식이 부합하는지 안하는지 알 수 있으니깐요. 그렇게 수정해야겠네요. 감사합니다.
  • 호잉 2016/10/31 23:02 # 삭제

    4장도 풀어주시면 안될까요 ㅠ.ㅜ
  • 손오공 2016/11/27 17:12 # 삭제

    여기선 MIPS 라고 써있는데 제 2016 책에선 LEGv8 로 써있는데 똑같나요?

  • 불타는 아이스크림 2016/11/27 20:36 #

    잘 모르겠습니다. 직접 찾아보시는 게 좋을 듯 하네요.
  • 저팔계 2016/12/07 00:33 # 삭제

    4장에 연습문제 4.3하고 4.9만 풀어 주시면 안되나요? ㅠㅜ
※ 로그인 사용자만 덧글을 남길 수 있습니다.