시작하기 전
이 글은 필자가 수업시간에 들은 내용과 강의록을 토대로 정리한 글입니다.
수업 필기이다 보니, 오류가 있거나 설명이 부족한 부분이 있을 수 있습니다.
궁금하신 점이나 지적하실 점이 있다면 댓글로 달아주세요! 확인 후 내용을 추가하거나 답변해드리도록 하겠습니다 :)
C 스왑 예제(C Swap Example)
- 스왑 프로시저(leaf) C 코드
void swap (int v[], int k)
{
int temp;
temp = v[k];
v[k] = v[k + 1];
v[k + 1] = temp;
}-
v는
$a0에 저장되고, k는$a1, temp는$t0에 저장된다. -
MIPS 코드
swap: sll $t1, $a1, 2 # $t1 = k * 4
add $t1, $a0, $t1 # $t1 = v + (k * 4) = &v[k]
lw $t0, 0($t1) # $t0 (temp) = v[k]
lw $t2, 4($t1) # $t2 = v[k + 1] = *(&v[k] + 4)
sw $t2, 0($t1) # v[k] = $t2 (v[k + 1])
sw $t0, 4($t1) # v[k + 1] = $t0 (temp)
jr $ra # return to calling routine그닥 특별할 점이라고는 없는 편이다.
C 정렬 프로시저(The Sort Procedure in C)
- 버블 정렬을 어셈블리 명령으로 표현해보자.
C 코드
- Non-Leaf 코드(swap을 호출한다)
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는
$a0에 저장되고, n은$a1, i는$s0, j는$s1에 저장된다.
프로시저 바디(The Procedure Body)
move $s2, $a0 # save $a0 into $s2 (v)
move $s3, $a1 # save $a1 into $s3 (n)
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
for2tst: slti $t0, $s1, 0 # $t0 = 1 if $s1 < 0 (j < 0)
bne $t0, $zero, exit2 # go to exit2 if $s1 < 0 (j < 0)
sll $t1 ,$s1, 2 # $t1 = j * 4
add $t2, $s2, $t1 # $t2 = v + (j * 4) = &v[j]
lw $t3, 0($t2) # $t3 = v[j]
lw $t4, 4($t2) # $t4 = v[j + 1] = *(&v[j] + 4)
slt $t0, $t4, $t3 # $t0 = 0 if $t4 >= $t3
beq $t0, $zero, exit2 # if $t0 = 0, then go to exit2
move $a0, $s2 # 1st param of swap is v (old $a0)
move $a1, $s1 # 2nd param of sqap is j
jal swap # call swap procedure // v[j] <-> v[j + 1]
addi $s1, $s1, -1 # j -= 1
j for2tst # jump to test of inner loop
exit2: addi $s0, $s0, 1 # i += 1
j for1tst # jump to test of outer loop
exit1:- 대부분의 코드는 2중 반복문을 구현하고, 배열의 값을 불러오는 코드이다.
- 차근차근 코드를 이해해서 직접 구현하는 연습을 해보도록 하자.
전체 프로시저(The Full Procedure)
sort: addi $sp, $sp, -20 # make room on stack for 5 registers
sw $ra, 16($sp) # save $ra on stack
sw $s3, 12($sp) # save $s3 on stack
sw $s2, 8($sp) # save $s2 on stack
sw $s1, 4($sp) # save $s1 on stack
sw $s0, 0($sp) # save $s0 on stack
... # procedure body part
exit1: lw $s0, 0($sp) # restore $s0 from stack
lw $s1, 4($sp) # restore $s1 from stack
lw $s2, 8($sp) # restore $s2 from stack
lw $s3, 12($sp) # restore $s3 from stack
lw $ra, 16($sp) # restore $ra from stack
addi $sp, $sp, 20 # restore stack pointer
jr $ra # return to calling routine- procedure body part에는 위의 프로시저 바디의 코드가 들어간다.
- 참고로, 프로시저 바디에서 사용하는 스왑은 스택을 쓰지 않는다. 이 점 유의하도록 하자.
- 정리하자면, 전체 프로시저는 스택 푸시(push) 프로시저 바디 스택 팝(pop)으로 이루어져 있다고 보면 된다.
컴파일러 최적화의 영향(Effect of Compiler Optimization)
- 컴파일러를 적절히 최적화 하면
- 명령 수(Instruction Count)
- 클럭 사이클 수(Clock Cycles)
- CPI
- 위 3가지가 변하기 때문에, 상대적인 성능에도 차이가 생긴다.
언어와 알고리즘의 영향(Effect of Language and Algorithm)
- 보통 C와 Java를 비교하면, C가 빠르다.
- 또한, 퀵 정렬과 버블 정렬을 비교하면, 퀵 정렬이 훨씬 빠른데, 이는 최악의 시간복잡도 O가 퀵 정렬은 인 반면에, 버블 정렬은 이기 때문이다. 즉, 알고리즘 자체도 성능에 큰 영향을 미친다.
ARM과 MIPS의 유사성(ARM vs MIPS Similarities)
- ARM : CPU 아키텍쳐이다. 가장 유명한 임베디드 코어(embedded core)이기도 하다.
- 둘 다 RISC 아키텍쳐이기 때문에, 비슷한 명령어 셋을 가지고 있다.
| ARM | MIPS | |
|---|---|---|
| 발표 년도 | 1985 | 1985 |
| 명령 크기(Instruction size) | 32 비트 | 32 비트 |
| 주소 공간(Address space) | 32 비트 평면(32 bits flat) | 32 비트 평면(32 bits flat) |
| 데이터 정렬(Data alignment) | 정렬됨(Aligned) | 정렬됨(Aligned) |
| 데이터 주소 모드(Data addressing modes) | 9 | 3 |
| 레지스터 | 32 비트 15 | 32 비트 31 |
| 입출력 | 메모리 매핑(Memory mapped) | 메모리 매핑(Memory mapped) |
- 비교, 분기, 조건 명령에 약간 차이가 있다.
- 다른 명령 인코딩 도식(encoding scheme)을 사용한다.
인텔 x86 ISA(The Intel x86 ISA)
옛 기기와의 호환성을 신경 쓴 진화(Evolution with backward compatibility)
- 8086 프로세서(1978)
- 16 비트 프로세서
- CISC를 사용하기 시작했다
- 80386 프로세서(1985)
- 8086에서 32 비트로 확장됐다.
그 후
- AMD64(2003)
- 아키텍쳐가 64 비트로 확장되었다.
- AMD가 개발했다.
- AMD64(2007 버전) : SSE5 명령어를 사용
- 인텔보고 같은거 쓰자고 했다.
- 인텔이 엿이나 까잡수시라고 했다. 대신 …
- Advanced Vector Extension(2008)
- 인텔은 이걸 만들었다.
- 더 긴 SSE 레지스터와 더 많은 명령어를 갖추었다.
x86 명령 인코딩(x86 Instruction Encoding)
- 복잡하다.
- 크기가 지멋대로이다. 8비트부터 40비트까지 아~주 다양하다.
- 즉, 복잡하다.
오해(Fallacies)
- 강력한 명령어가 더 높은 성능을 가져올 것이다.
- 이렇게 주장하는 사람들은 적은 명령어수가 성능 향상을 가져올 것이라고 말한다.
- 하지만, 강력한 명령어는 복잡하기 마련이고, 하드웨어에서 수행하기가 어렵다. 일전에 설명했듯, 이는 모든 명령어에 패널티를 주게 된다.
- 즉, 느려진다.
- 또한, 컴파일러는 충분히 간단한 명령어로 빠른 코드를 만드는 것에 능하다. (컴파일러 개발자들은 지금도 갈려나가고 있다.)
- 즉, 쓰잘떼기 없다.
- 더 높은 성능을 위해서 어셈블리 코드를 쓰자.
- 옛날에는, 맞는 말이기도 했다. 그 당시엔, 컴파일러가 빠른 코드를 만들어낸다는 보장이 없었기 때문이다.
- 하지만 현대의 컴파일러들은 현대의 프로세서들을 위해서 어떤 코드를 만들어내야하는지 잘 알고있다.
- 또한, 어셈블리 코드를 작성하려면, 다른 고수준 프로그래밍 언어보다 더 많은 줄을 작성해야한다. 10, 20줄이면 모르지만 1만줄, 2만줄짜리 고수준 언어 코드가 있다고 생각해보자. 똑같은 기능을 하는 어셈블리 코드를 짜려고 하면 (…) 말해 뭐해다.
- 이는 더 많은 에러를 불러올 것이고, 생산성을 떨어뜨릴 것이다.
- 역호환성(Backward compatibility)
- 일단, 역호환성이란, 최신의 프로그램들도 옛날 기기에서 돌아갈 수 있도록 하는 것을 의미한다.
- 이를 보장하기 위해 명령어 셋이 변하지 않아야 한다.
- 하지만, 계속 새로운 명령어가 서서히 생겨가고 있다. 즉, x86 명령 셋은 점점 더 거대해지고 있다. 이거 어쩔거야 이거?
요약 정리(Concluding Remark)
- 요약 정리라고 이거만 보면 패가망신한다. 꼭 전체적으로 다 공부하도록 하자.
디자인 원칙(Design principles)
- 간결함이 규칙성에 유리하다.(Simplicity favors regularity)
- 작을수록 빠르다.(Smaller is faster)
- 공통적인 것들을 빠르게 만들어라.(Make the common case fast)
- 좋은 디자인은 적절한 타협을 필요로 한다.(Good design demands good compromises)
벤치마크 프로그램에서 MIPS 명령 실행을 측정한 결과
- 공통적인 것들을 빠르게 만드는 것을 고려하라.
- 적절히 타협하라.
| 명령 분류(Instruction class) | MIPS 예시 | SPEC2006 정수 | SPEC2006 부동소수점 |
|---|---|---|---|
| Arithmetic | add , sub , addi | 16% | 48% |
| Data transfer | lw , lb , lui 등 | 35% | 36% |
| Logical | and , nor , sll 등 | 12% | 4% |
| Cond. Branch | beq , slt , slti 등 | 34% | 8% |
| Jump | j , jr , jal | 2% | 0% |
