Solution to Problem 5.7

Solution to Problem 5.7

The following code directly follows the rules we have stated for unrolling a loop by some factor k:

다음 코드는 우리가 앞에서 설명한 '루프를 어떤 계수 k만큼 언롤링(unrolling)하는 규칙'을 그대로 따른 것이다.

 

언롤링(Unrolling) : 프로그래밍에서 성능 최적화를 위해 반복문(Loop)의 횟수를 줄이고, 루프 내의 코드들을 직접 나열하여 실행 속도를 높이는 기술

 

정의 : for문이나 while문 같은 반복문의 본문(body)을 여러 번 복제하여 펼쳐놓고, 루프 제어 코드(카운터 증가, 조건 검사)를 줄이거나 없애는 기법이다.

 

목적 : 루프 오버헤드(비교 및 분기 명령)를 제거하여 실행 속도를 최적화한다.

 

트레이드오프 : 실행 시간(속도)을 단축시키는 대신, 바이너리 코드의 크기가 늘어나는 공간-시간 트레이드오프(Space-Time Tradeoff)방식이다.

 

작동 원리 : 예를 들어, 100번 반복하는 루프를 4번 언롤링하면, 루프 본문을 한 번 실행할 때 4개의 요소를 처리하고 루프 제어부는 25번만 동작하게 된다.

 

<원래 코드(언롤링 전)>

int sum = 0;
for(int i = 0; i < 100; i++) {
	sum += arr[i];
}

 

<4번 언롤링한 코드 (k = 4)>

int sum = 0;
for(int i = 0; i < 100; i+=4) {
	sum += arr[i];
    sum += arr[i + 1];
    sum += arr[i + 2];
    sum += arr[i + 3];
}

---

항목	언롤링 전	언롤링 후
루프 반복 횟수	100	25
루프 제어 실행	100	25
실제 데이터 처리	100	100

 

---

 

unroll5 : 언롤링된 버전의 함수

vec_ptr v : 벡터 구조체를 가리키는 포인터

data_t *dest : 최종 결과를 저장할 주소

 

length : 벡터 전체 길이

limit = length - 4 : i, i+1, i+2, i+3, i+4까지 안전하게 접근 가능한 마지막 시작 지점 -> 5개를 한 번에 처리하기 위한 경계값

*data : 실제 배열 시작 주소

acc = IDENT : 누적 결과 저장용 변수(덧셈이면 0, 곱셈이면 1)

// 가정
v = [10, 20, 30, 40, 50, 60, 70]
length = 7
OP = +
IDENT = 0

long length = vec_length(v);       // 배열의 길이 = 7
long limit = length - 4;           // limit = 7 - 4 = 3

// 4를 뺀 이유 : 
// data[i], data[i+1], data[i+2], data[i+3], data[i+4]
// 를 사용하기 위해서는 i가 3이상이 되어서는 안됨.
// 만약 i가 3 이상이라면 i + 4 = 7이 되므로, 현재 배열의 길이를 초과한다.
// 이를 방지하기 위해 4를 빼서 limit의 값을 length - 4로 설정했다.

data_t *data = get_vec_start(v);
// 이제 data[0] = 10, data[1] = 20 이런 식으로 접근이 가능하다

data_t acc =IDENT;
// acc = 0
// 결과를 계속 누적할 변수

/* Combine 5 elements at a time */
for (i = 0; i < limit; i += 5) {
    acc = acc OP data[i]   OP data[i+1];
    acc = acc OP data[i+2] OP data[i+3];
    acc = acc OP data[i+4];
}
// 원소 5개를 한꺼번에 처리

/* Finish any remaining elements */
for (; i < length; i++) {
    acc = acc OP data[i];
}
// 남은 원소 처리
// 예시 : length = 12
// 첫 번째 for문에서 10개 처리
// 여기서 2개 남음. 이를 처리해 주는 코드

*dest = acc;
// 누적된 결과를 호출한 쪽에서 넘겨준 주소에 저장