C swap function
void swap(int v[], int k) {
int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}- v in $a0, k in $a1, temp in $t0
MIPS는 Byte address를 사용하므로 각 워드는 실제로 4바이트씩 떨어져 있다.
그러므로 인덱스 k를 주소에 더하기 전에 4를 곱해야 한다.
순차적인 워드 주소가 1이 아니고 4씩 차이가 나는 것을 반드시 기억해야 한다.
따라서 v[k]의 주소를 구하기 위해서 처음 해야 할 일은 k에 4를 곱하는 것이다.
sll $t1, $a1, 2 # reg $t1 = k * 4
add $t1, $a0, $t1 # reg $t1 = v + k * 4
# reg $t1 has the address of v[k]
$t1을 이용해서 v[k]를 load하고, $t1에 4를 더해 v[k + 1]을 load할 수 있다.
lw $t0, 0($t1) # reg $t0 (temp) = v[k]
lw $t2, 4($t1) # reg $t2 = v[k + 1]
# refers to next element of v
$t0와 $t2를 맞바꾼 주소에 저장한다.
sw $t2, 0($t1) # v[k] = reg $t2
sw $t0, 4($t1) # v[k + 1] = reg $t0 (temp)swap: sll $t1, $a1, 2 # reg $t1 = k * 4
add $t1, $a0, $t1 # reg $t1 = v + k * 4
# reg $t1 has the address of v[k]
lw $t0, 0($t1) # reg $t0 (temp) = v[k]
lw $t2, 4($t1) # reg $t2 = v[k + 1]
# refers to next element of v
sw $t2, 0($t1) # v[k] = reg $t2
sw $t0, 4($t1) # v[k + 1] = reg $t0 (temp)
C bubble sort function
void sort (int v[], int n) {
int i, j;
for (i = 0; i<n ; i += 1)
for (j = i - 1; j >= 0 && v[j] > v[j + 1]; j -= 1)
swap(v, j);
}- v in $a0, k in $a1, i in $s0, j in $s1
for (i = 0; i < n; i += 1)위 부분을 assembly로 바꾸면,
move $s0, $zero # i = 0
addi $s0, $s0, 1 # i += 1slt 명령으로 $s0 < $a1이면 $t0을 1로, 아니면 0으로 만들 수 있다.
$s0 >= $a1인가를 검사해야 하므로 $t0가 0일 때 분기하면 된다.
forlist: slt $t0, $s0, $a1 # reg $t0 = 0 if $s0 >= $a1 (i >= n)
beq $t0, $zero, exit1 # go to exit if $s0 >= $a1 (i >= n)
반복문의 맨 끝은 처음의 반복 조건 검사로 되돌아가는 명령이다.
j forlist # jump to test of outer loop
첫 for 반복문의 형태는 다음과 같다.
move $s0, $zero # i = 0
forlist: slt $t0, $s0, $al # reg $t0 = 0 if $s0 >= $a1 (i >= n)
beq $t0, $zero, exit1 # go to exit1 if $s0 >= $a1 (i >= n)
...
(첫 for 문 body)
...
addi $s0, $s0, 1 # i += 1
j forlist # jump to test of outer loop
exit1:
두 번째 for문.
for (j = i - 1; j >=0 && v[j] > v[j + 1]; j -= 1)
초기화
addi $s1, $s0, -1 # j = i -1
addi $s1, $s1, -1 # j -= 1
반복 조건 검사.
첫 번째 조건
for2tst: slti $t0, $s1, 0 # reg $t0 = 1 if $s1 < 0 (j < 0)
bne $t0, $zero, exit2 # go to exit2 if $s1 < 0 (j < 0)두 번째 조건
sll $t1, $s2, 2 # reg $t1 = j * 4
add $t2, $a0, $t1 # reg $t2 = v + (j * 4)
lw $t3, 0($t2) # reg $t3 = v[j]
lw $t4, 4($t2) # reg $t4 = v[j + 1]
slt $t0, $t4, $t3 # reg $t0 = 0 if $t4 >= $t3
beq $t0, $zero, exit2 # go to exit2 if $t4 >= $t3j for2tst # jump to test of inner loop move $s2, $a0 # save $a0 into $s2
move $s3, $a1 # save $a1 into $s3
move $s0, $zero # i = 0
for1tst: slt $t0, $s0, $s3 # t0 = 0 if $s0 >= $s3 (i >= n)
beq $t0, $zero, exit1 # go to exit1 if $s0 >= $s3 (i >= n)
addi $s1, $s0, -1 # j = i - 1
addi $s1, $s0, –1 # j = i – 1
for2tst: slti $t0, $s1, 0 # reg $t0 = 1 if $s1 < 0 (j < 0)
bne $t0, $zero, exit2 # go to exit2 if $s1 < 0 (j < 0)
sll $t1, $s1, 2 # reg $t1 = j * 4
add $t2, $a0, $t1 # reg $t2 = v + (j * 4)
lw $t3, 0($t2) # reg $t3 = v[j]
lw $t4, 4($t2) # reg $t4 = v[j + 1]
slt $t0, $t4, $t3 # reg $t0 = 0 if $t4 ≥ $t3
beq $t0, $zero, exit2 # go to exit2 if $t4 ≥ $t3
move $a0, $s2 # 1st param of swap is v (old $a0)
move $a1, $s1 # 2nd param of swap is j
jal swap
addi $s1, $s1, –1 # j –= 1
j for2tst # jump to test of inner loop
exit2: addi $s0, $s0, 1 # i += 1
j for1tst
Effect of Compiler Optimization
- 명령어의 개수와 CPI는 성능을 측정하는데 좋은 지표가 아니다.
- 컴파일러 최적화는 알고리즘마다 다를 수 있다.
- Java/JIT로 컴파일된 코드는 JVM으로 interpet된 코드보다 훨씬 빠르다.
C언어와 비교해봐도 대체로 빠르다.
-> 알고리즘 CPU 성능을 개선 할 수 없다.
