[CSAPP] 5.8 Loop Unrolling(루프 풀기)

5.8 Loop Unrolling(루프 언롤링)

• Loop Unrolling(루프 언롤링)이란 각 반복에서 계산되는 요소의 수를 늘려 루프틔 반복 횟수를 줄이는 프로그램 변환법이다. 
• 5.2에서 나온 psum2가 대표적인 예시이다. 아래 코드가 루프 언롤링을 적용한 것.  psum1 -> psum2

/* Compute prefix sum of vector a */
2 void psum1(float a[], float p[], long n)
{
	long i;
	p[0] = a[0];
	for (i = 1; i < n; i++)
		p[i] = p[i-1] + a[i];
}

void psum2(float a[], float p[], long n)
{
	long i;
	p[0] = a[0];
	for (i = 1; i < n-1; i+=2) {
		float mid_val = p[i-1] + a[i];
		p[i] = mid_val;
		p[i+1] = mid_val + a[i+1];
}
/* For even n, finish remaining element */
	if (i < n)
		p[i] = p[i-1] + a[i];
}

 

• Loop Unrolling(루프 언롤링)은 두 가지 방법으로 성능을 향상시킬 수 있다.
  • 1. 루프 indexing 및 조건 분기(conditional branch)와 같이 프로그램 결과에 '직접적'으로 관여하지 않는 작업의 수를 줄이는 방법.
  • 2. 전체 계산의 criticial path에서 작업 수를 줄이기 위해 코드를 추가로 변환할 수 있는 방법.
• 아래는 2 * 1 루프 언롤링이라고 불리는 것을 사용하는 결합 코드를 보여준다.

/* 2 x 1 loop unrolling */
void combine5(vec_ptr v, data_t *dest)
{
	long i;
	long length = vec_length(v);
	long limit = length-1;
	data_t *data = get_vec_start(v);
	data_t acc = IDENT;

/* Combine 2 elements at a time */
	for (i = 0; i < limit; i+=2) {
		acc = (acc OP data[i]) OP data[i+1];
	}

/* Finish any remaining elements */
	for (; i < length; i++) {
		acc = acc OP data[i];
	}
	*dest = acc;
}

• 우리는 우리의 코드가 임의의 벡터 길이에 대해 올바르게 작동하는 것을 원한다.
• 이를 위한 두 가지 방법이 존재.
  • 1. 첫번째 루프가 array 경계를 초과하지 않는 확인하는 것. ex) 길이가 n인 벡터의 경우 루프 한계를 n-1로 설정. 그런 다음에 루프의 인덱스 i가 i < n-1를 만족할 때만 루프가 실행될 것. 따라서 최대 array 인덱스는 i + 1 < (n - 1) + 1 = n 즉 i + 1 < n 을 만족할 것을 보장. 
  • 이를 일반화하여 k * 1 루프 언롤링을 초래하는 요인 k에 의해 루프를 언롤링할 수 있다.
  • 우리의 상한을 n - k + 1로 설정하고 루프 내에서 combining operation를 i ~ i + k -1에 적용한다. 루프 인덱스 i는 각 반복에서 k씩 증가하면 최대 array 인덱스 i + k - 1이 n 보다 작아진다. 
  • 2. 우리는 벡터의 마지막 몇 가지 요소를 한 번에 하나씩 통과하는 두 번째 루프를 포함시킨다. 이 루프는 0 ~ k-1회 사이에 실행된다. k =2일 때, psum2 같이 간단한 조건문만을 이용 가능하다.  k > 2인 경우 루프로 더 표현하기 쉽다.
  • 우리는 k배만큼 풀지만 단일 변수 acc에 값을 축적하기 때문에 이 변환을 k  * 1 언롤링이라 부른다.
• 언롤링 요소 k = 2, k = 3일 때 측정된 평가 값은 다음과 같다.

• integer 덧셈에 대한 CPE가 개선 되어 Latency bound가 약 1.00을 달성했다.
• 이 결과는 루프의 오버헤드 작업을 줄이는 이점 때문일 수 도 있다.
• 벡터 합을 계산하는데 필요한 추가 수에 비해 오버헤드 작업 수를 줄임으로써 정수 추가의 1 cycle latency이 성능 제한 요소가 되는 지점에 도달할 수 있다.
• 반면, 다른 사례들은 개선되지 않았다. 이미 latency bounds에 도달했기 때문이다.

 

• 아래 그림은 루프를 최대 10배(k = 10)까지 풀 때의 CPE 측정값을 보여준다.

• 2와 3의 언롤링에 대해 관찰한 추세가 동일하고 latency bound를 밑도는 것은 없다.
• k * 1 언롤링이 latency bound 이상의 성능을 향상시킬 수 없는 이유를 이해하기 위해, k = 2인 combine5의 내부 루프에 대한 기계어 코드를 보자.
• data_t 타입이 double이고 연산이 곱셉이면 다음 코드가 된다.

// Inner loop of combine5. data_t = double, OP = *
//in %rdx, data %rax, limit in %rbx, acc in %xmm0
.L35: //loop:
vmulsd (%rax,%rdx,8), %xmm0, %xmm0 //Multiply acc by data[i]
vmulsd 8(%rax,%rdx,8), %xmm0, %xmm0 //Multiply acc by data[i+1]
addq $2, %rdx //Increment i by 2
cmpq %rdx, %rbp //Compare to limit:i
jg .L35 //If >, goto loop

• 루프 인덱스 i는 레지스터 %rdx에 저장되고 데이터의 주소는 레지스터 %rax에 저장된다.
• 누적 값 acc는 벡터 레지스터 %xmm0에 저장된다.
• 루프 언롤링은 두 가지 vmulsd 명령으로 수행된다. 
  • 하나는 acc에 데이터 [i]를 추가하고
  • 다른 하나는 acc에 데이터 [i + 1]를 추가한다. 
• 아래 그림은 이 코드를 그래픽으로 표현한 것이다.

• vmulsd 명령은 각각 메모리에서 array 요소를 load하는 작업과 이 값에 누적 값을 곱하는 작업의 두 가지 작업으로 변환된다. 
• 여기서는 각 루프 실행에서 레지스터 %xmm0이 두 번 읽고 쓰는 것을 볼 수 있다.
• 아래 그림 (a)에 표시된 프로세스에 따라 이 그래프를 재정렬, 단순화, 추상화해서 (b)로 표시된 템플릿을 얻을 수 있다.

• 그런 다음 이 템플릿을 n/2회 복제하여 길이 n의 벡터에 대한 계산을 보여주며, 아래 그림에 표시된 data flow 표현을 얻을 수 있다.

• 위 그림에서 우리는 이 그래프에서 n개의 mul operation의 critical path가 여전히 존재한다는 것을 알 수 있다.
• 반복 횟수는 절반이지만 각 반복에는 두 개의 multiplication operation이 순차적으로 있다. 
• critical path는 루프 언롤링이 없는 코드 성능에 대한 제한 요소였기 때문에, k * 1에서도 마찬가지로 적용되는 제한 요소이다.