임베디드시스템 - Optimization!
임베디드 시스템의 경우 general computer에 비해 훨씬 더 harsh 한 environment에서 최소의 resource로 최적의 코드를 짜는게 더욱 중요해진다. 따라서 이번에는 하드웨어 단을 고려하여 최적의 code optimization을 하는 방법을 배워보자.
1. bus 크기를 고려한 코딩!
window 32면 bus크기는 32bit, window 64 면 bus 크기는 64 bit 이다.
여기서 bus의 크기는 다음과 같은 의미를 가지고 있다.
1. address의 크기 -> 다시 말하면, 32bit의 bus를 사용하면, address에 들어갈 elements갯수는 2의 32승이다.
2. 한번에 전송되는 데이터 단위
우리는 보통 메모리를 적게 차지하는 char, short를 리런 타입으로 설정하면 더욱 빠른 퍼포먼스를 보일것이라 착각하기 쉽다. 하지만 bus의 크기는 4byte이므로, 어차피 데이터는 최소 4byte씩 움직이게 된다. 여기서 char, short로 할 경우에는, 비워있는 비트를 0으로 채우는 문제때문에 오히려 어셈블리 코드가 길어진다. 즉, 4bytes인 int로 리턴할때가 가장 빠르다.
2. memory를 고려한 코딩!
일단 언제나 중요하고 알고있어야 하는 memory구조를 좀 집고 넘어가자.
<참고 : http://sfixer.tistory.com/entry/%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%98%81%EC%97%ADcode-data-stack-heap>
그림과 같이 memory영역은 code, data, heap, stack으로 크게 이루어져 있다. (BSS는 초기화 안된 전역변수공간인데, DATA에 포함된다고 하자)
code는 실제 코드가 들어있는 영역이다.
Data는 전역변수, 정적변수(static), 배열(array), 구조체(structure)등이 저장되는 공간이다.
Heap은 runtime시에 동적으로 생성되는 메모리 영역으로, 주소값으로 참조된다. (malloc)
Stack은 프로그램이 자동으로 저장되는 임시 메모리 영역으로, 함수의 리턴값, 지역변수, 매개변수등이 저장되는 공간이다.
여기서 heap 은 위에서 아래로 쌓이고, stack은 아래서 위로 쌓인다.
구조체가 저장될때에는 그림과 같이 pad공간이 생겨 공간낭비가 생긴다. 이렇게 되는 이유는, 데이터에 접근하는 속도를 빠르게 하기 위함이다. 하지만 속도보다 공간이 중요하다면, 밑에처럼 변수를 packing해주면 된다.
-extern variable
extern variable은 내가 아닌 다른 파일에 선언된 global variable을 쓰고 싶을때 사용한다. 이 경우 다음과 같은 단계를 따른다.
1. 해당 global variable의 주소를 read
2. 해당 주소의 데이터값을 read
여기서 위 그림의 경우 총 6번의 참조가 일어날 것이다.
하지만 아래와 같이 structure로 선언을 해버리면, 단 한번만 구조체의 base address를 참조해오면 되기 때문에 총 4번의 참조만 일어난다.
-volatile variable
이부분은 잘 기억해놓자. 실제 네이버 인턴면접에서 나온 문제이다.
compiler은 우리가 코딩을 하면 컴파일할때 자동으로 optimization을 한다. 예를 들어 다음과 같은 코드가 있다고 하자.
1. a=10;
2. b=a;
3. c=a;
이 경우 3번코드에서 우리는 a의 값을 읽어와 c에 넣으라고 명령하였지만, 컴파일러는 실제로 그러지 않는다. 2번코드에서 래지스터에 a값을 받아왔기 때문에 해당 래지스터로부터 바로 c에 넣어버린다. 즉 다시 a를 참조하지 않는다는 것이다. 다음 코드에서도 마찬가지이다.
1. *port = value;
2. value = *port;
이 경우, 컴파일러는 1번코드에서 value를 *port에 넣고 수정을 가하지 않았으니, 2번코드를 실제로 수행하지 않는 방식으로 optimization한다. 하지만 이와 같은 방식은 위험할 수 있다.
컴파일러는 자신의 프로그램 내의 정보를 고려하여 optimization 을 고려하는데, 사실은 여러 프로그램이 동시에 수행하는 flow를 가질 경우가 많기 때문에, 이 optimization이 오류를 초래할 수 있다. 다음 그림을 보자.
var1을 메모리에 write하고 read하라는 명령이 있으면 컴파일러는 자신의 프로그램이 값을 바꾸지 않았으면 read를 굳이 다시 수행하지 않는다. 하지만, 실전에서는 다른 프로그램이 이 값을 바꾸는 경우가 있다. 이 경우 컴파일러는 optimization으로 인해 이 사실을 인지하지 못하고 바꾸기 전 값을 그대로 대입하게 된다.
이를 방지하기 위해선 다음그림과 같이 volatile을 선언해줘야 하는 것이다.
-register 변수
local varible은 stack에 할당되지만, register로 선언하면 stack이 아닌 register에 넣을 수 있다.
-inline 함수
함수 역시 그 자체가 오버헤드가 될 수 있다. branch(jump)가 클락사이클을 상당히 잡아먹기 때문이다.
또, 함수 내 argument는 4개 이하로 선언하면 parameter가 register에 할당되서 좋다. 이를 위해 매개변수가 커지면 구조체로 뭉뚱그려 집어넣는 것도 하나의 방법이다.
inline함수는 macro 함수로 스택에 할당되지 않는다. 다음과 같이 선언한다.
__inline int square(int x){ return x*x;}
-function 팁!
function의 경우 호출시 우선 호출한 위치 다음의 주소를 LR 래지스터에 저장하는데, 함수 내에서 또다시 함수를 호출할 경우 LR에 저장할 수 없으므로 stack에 저장하게 된다. 여기서 cost가 발생하므로, 아래와 같이 함수를 return해주면, 두번째 함수의 호출위치를 저장할 필요가 없어 퍼포먼스가 올라간다.
-Loop unrolling!
for, while문 같은 loop에서 optimization을 위한 몇가지 팁을 소개한다.
1. down-count-loop!
-> 0 -> n 으로 loop 를 돌릴경우, 한번의 루프가 돌때마다 n과 compare(cmp)하고, jump하는 2가지과정을 거쳐야한다. 하지만 n->0으로 돌릴경우, jz(0과비교하고 점프하는 명령어) 한번만 수행되기때문에 코드길이가 줄어든다.
ex) while(i++<10){} 보다 while(i--){} 가 좋다.
2. loop unrolling
-> loop unrolling을 통해서 branch instruction을 줄여준다. 이 경우 코드사이즈는 늘지만 실행시간이 줄어든다.
ARM8 프로세서 기준으로 덧셈, 뺄셈은 1cycle인 반면에 branch 는 3cycle이나 소모된다. branch는 가능한 줄이는게 optimization을 위한 길이다.
(사이클이 궁금하다면 특정 프로세서의 관련자료 http://robotshop.com/letsmakerobots/clock-speeds)
->얼마나 loop unrolling을 해야하는가? --> 여러번 시행해보며 최적의 수행시간을 찾는게 정답!
trade off가 있다. loop unrolling을 통해 branch횟수를 줄일 수 있지만, code size가 늘어나고 cashe miss rate가 늘어나기 때문이다!
bit 연산자!
-> devide operation은 20~140 cycle이나 소모하므로 가능한 비트연산자로 피해라!(shift)
-> 비트연산자는 1cycle밖에 안먹어 매우 빠름.
ex) N&3 : 1cycle, N%4 : 오래걸림.. 모듈라보다 비트연산이 훨 나음!!
1. bus 크기를 고려한 코딩!
window 32면 bus크기는 32bit, window 64 면 bus 크기는 64 bit 이다.
여기서 bus의 크기는 다음과 같은 의미를 가지고 있다.
1. address의 크기 -> 다시 말하면, 32bit의 bus를 사용하면, address에 들어갈 elements갯수는 2의 32승이다.
2. 한번에 전송되는 데이터 단위
그림을 보자. <window-32bit 환경>
2. memory를 고려한 코딩!
일단 언제나 중요하고 알고있어야 하는 memory구조를 좀 집고 넘어가자.
<참고 : http://sfixer.tistory.com/entry/%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%98%81%EC%97%ADcode-data-stack-heap>
code는 실제 코드가 들어있는 영역이다.
Data는 전역변수, 정적변수(static), 배열(array), 구조체(structure)등이 저장되는 공간이다.
Heap은 runtime시에 동적으로 생성되는 메모리 영역으로, 주소값으로 참조된다. (malloc)
Stack은 프로그램이 자동으로 저장되는 임시 메모리 영역으로, 함수의 리턴값, 지역변수, 매개변수등이 저장되는 공간이다.
여기서 heap 은 위에서 아래로 쌓이고, stack은 아래서 위로 쌓인다.
-extern variable
extern variable은 내가 아닌 다른 파일에 선언된 global variable을 쓰고 싶을때 사용한다. 이 경우 다음과 같은 단계를 따른다.
1. 해당 global variable의 주소를 read
2. 해당 주소의 데이터값을 read
여기서 위 그림의 경우 총 6번의 참조가 일어날 것이다.
하지만 아래와 같이 structure로 선언을 해버리면, 단 한번만 구조체의 base address를 참조해오면 되기 때문에 총 4번의 참조만 일어난다.
-volatile variable
이부분은 잘 기억해놓자. 실제 네이버 인턴면접에서 나온 문제이다.
compiler은 우리가 코딩을 하면 컴파일할때 자동으로 optimization을 한다. 예를 들어 다음과 같은 코드가 있다고 하자.
1. a=10;
2. b=a;
3. c=a;
이 경우 3번코드에서 우리는 a의 값을 읽어와 c에 넣으라고 명령하였지만, 컴파일러는 실제로 그러지 않는다. 2번코드에서 래지스터에 a값을 받아왔기 때문에 해당 래지스터로부터 바로 c에 넣어버린다. 즉 다시 a를 참조하지 않는다는 것이다. 다음 코드에서도 마찬가지이다.
1. *port = value;
2. value = *port;
이 경우, 컴파일러는 1번코드에서 value를 *port에 넣고 수정을 가하지 않았으니, 2번코드를 실제로 수행하지 않는 방식으로 optimization한다. 하지만 이와 같은 방식은 위험할 수 있다.
컴파일러는 자신의 프로그램 내의 정보를 고려하여 optimization 을 고려하는데, 사실은 여러 프로그램이 동시에 수행하는 flow를 가질 경우가 많기 때문에, 이 optimization이 오류를 초래할 수 있다. 다음 그림을 보자.
var1을 메모리에 write하고 read하라는 명령이 있으면 컴파일러는 자신의 프로그램이 값을 바꾸지 않았으면 read를 굳이 다시 수행하지 않는다. 하지만, 실전에서는 다른 프로그램이 이 값을 바꾸는 경우가 있다. 이 경우 컴파일러는 optimization으로 인해 이 사실을 인지하지 못하고 바꾸기 전 값을 그대로 대입하게 된다.
이를 방지하기 위해선 다음그림과 같이 volatile을 선언해줘야 하는 것이다.
-register 변수
local varible은 stack에 할당되지만, register로 선언하면 stack이 아닌 register에 넣을 수 있다.
함수 역시 그 자체가 오버헤드가 될 수 있다. branch(jump)가 클락사이클을 상당히 잡아먹기 때문이다.
또, 함수 내 argument는 4개 이하로 선언하면 parameter가 register에 할당되서 좋다. 이를 위해 매개변수가 커지면 구조체로 뭉뚱그려 집어넣는 것도 하나의 방법이다.
inline함수는 macro 함수로 스택에 할당되지 않는다. 다음과 같이 선언한다.
__inline int square(int x){ return x*x;}
-function 팁!
function의 경우 호출시 우선 호출한 위치 다음의 주소를 LR 래지스터에 저장하는데, 함수 내에서 또다시 함수를 호출할 경우 LR에 저장할 수 없으므로 stack에 저장하게 된다. 여기서 cost가 발생하므로, 아래와 같이 함수를 return해주면, 두번째 함수의 호출위치를 저장할 필요가 없어 퍼포먼스가 올라간다.
-Loop unrolling!
for, while문 같은 loop에서 optimization을 위한 몇가지 팁을 소개한다.
1. down-count-loop!
-> 0 -> n 으로 loop 를 돌릴경우, 한번의 루프가 돌때마다 n과 compare(cmp)하고, jump하는 2가지과정을 거쳐야한다. 하지만 n->0으로 돌릴경우, jz(0과비교하고 점프하는 명령어) 한번만 수행되기때문에 코드길이가 줄어든다.
ex) while(i++<10){} 보다 while(i--){} 가 좋다.
2. loop unrolling
-> loop unrolling을 통해서 branch instruction을 줄여준다. 이 경우 코드사이즈는 늘지만 실행시간이 줄어든다.
ARM8 프로세서 기준으로 덧셈, 뺄셈은 1cycle인 반면에 branch 는 3cycle이나 소모된다. branch는 가능한 줄이는게 optimization을 위한 길이다.
(사이클이 궁금하다면 특정 프로세서의 관련자료 http://robotshop.com/letsmakerobots/clock-speeds)
->얼마나 loop unrolling을 해야하는가? --> 여러번 시행해보며 최적의 수행시간을 찾는게 정답!
trade off가 있다. loop unrolling을 통해 branch횟수를 줄일 수 있지만, code size가 늘어나고 cashe miss rate가 늘어나기 때문이다!
bit 연산자!
-> devide operation은 20~140 cycle이나 소모하므로 가능한 비트연산자로 피해라!(shift)
-> 비트연산자는 1cycle밖에 안먹어 매우 빠름.
ex) N&3 : 1cycle, N%4 : 오래걸림.. 모듈라보다 비트연산이 훨 나음!!
댓글
댓글 쓰기