Lecture 10: Program Optimization

Generally Useful Optimizations

---

Code Motion

루프 내에서 동일한 계산이 반복적으로 수행되는 경우, 해당 계산을 루프 외부로 이동하여 한 번만 수행되도록 최적화한다.

void set_row(double *matrix, double *vector, long r, long width) {
    for (long c = 0; c < width; c++)
        matrix[width * r + c] = vector[c];
}

위 코드를 -O1 옵션과 함께 컴파일해 보자.

set_row:
        testq   %rcx, %rcx
        jle     .L1
        imulq   %rcx, %rdx
        leaq    (%rdi,%rdx,8), %rdx
        movl    $0, %eax
.L3:
        movsd   (%rsi,%rax,8), %xmm0
        movsd   %xmm0, (%rdx,%rax,8)
        addq    $1, %rax
        cmpq    %rax, %rcx
        jne     .L3
.L1:
        ret

이를 다시 C로 표현해 보면 다음과 같다.

void set_row(double *matrix, double *vector, long r, long width) {
    long offset = width * r;
    double *row = matrix + offset;
    for (long c = 0; c < width; c++)
        row[c] = vector[c];
}

Strength Reduction

곱셈/나눗셈을 시프트 연산으로 치환¹하는 것처럼, 가능한 경우 비용이 더 적은 연산으로 변환한다.

for (long r = 0; r < height; r++) {
    long offset = width * r;
    for (long c = 0; c < width; c++)
        matrix[offset + c] = vector[c];
}

컴파일러는 루프 내에서 수행되는 곱셈을 보다 비용이 적은 덧셈으로 변환한다.

long offset = 0;
for (long r = 0; r < height; r++) {
    for (long c = 0; c < width; c++)
        matrix[offset + c] = vector[c];
    offset += width;
}

Optimization Blockers

---

Procedure Calls

lower()은 문자열 s의 모든 문자를 소문자로 변환하는 함수이다.

size_t strlen(const char *s) {
    size_t length = 0;
    while (*s != '\0') {
        s++;
        length++;
    }
    return length;
}

void lower(char *s) {
    for (size_t i = 0; i < strlen(s); i++) {
        if (s[i] >= 'A' && s[i] <= 'Z')
            s[i] -= ('A' - 'a');
    }
}

문자열을 한 번 순회하면 끝이므로, 문자열의 길이 $n$에 대해 $O(n)$의 시간 복잡도를 가질 것처럼 보인다. 그러나 조건식에서 strlen()을 반복적으로 호출하고 있기 때문에, $O(n)$인 strlen()이 총 $n$번 호출되어 결국 $O(n^2)$의 시간이 걸리게 된다. 따라서 strlen()이 한 번만 호출되도록 루프 외부로 이동하는 것이 좋다.

void lower_opt(char *s) {
    size_t len = strlen(s);
    for (size_t i = 0; i < len; i++) {
        if (s[i] >= 'A' && s[i] <= 'Z')
            s[i] -= ('A' - 'a');
    }
}

실제로 50만 자의 문자열에 대해 각 함수를 실행해 보면, 실행 시간이 엄청나게 차이 나는 것을 볼 수 있다.

lower(): 1956.30 ms
lower_opt(): 0.96 ms

위 예시에서는 strlen()의 반환값이 일정하지만, 조건식에서 호출되는 함수의 반환값이 달라지는 경우도 있으므로 컴파일러는 이러한 최적화를 수행하지 않는다.

Memory Aliasing

/* Sum each row of n × n matrix and store in vector */
void sum_each_row(double *matrix, double *vector, long n) {
    for (long r = 0; r < n; r++) {
        vector[r] = 0;
        for (long c = 0; c < n; c++)
            vector[r] += matrix[n * r + c];
    }
}

.L4:
        movsd   (%rsi,%rax,8), %xmm0  ; Load
        addsd   (%rdi), %xmm0         ; Add
        movsd   %xmm0, (%rsi,%rax,8)  ; Store
        addq    $8, %rdi
        cmpq    %rcx, %rdi
        jne     .L4

어셈블리 코드를 보면 내부 루프에서 matrix에 대한 읽기 작업뿐만 아니라 vector에 대한 읽기/쓰기 작업까지 매번 수행하는 것을 확인할 수 있는데, 이는 Aliasing(서로 다른 메모리 참조가 같은 위치를 가리키는 것)의 존재 가능성을 고려하기 때문이다.

double a[9] = {
     0,  1,   2,
     4,  8,  16,
    32, 64, 128
};

double *b = a + 3;  /* Aliasing */

sum_each_row(a, b, 3);

r	c	b[0 ... 2]
-	-	{ 4, 8, 16 }
		⋮
0	2	{ 3, 8, 16 }
1	-	{ 3, 0, 16 }
1	0	{ 3, 3, 16 }
1	1	{ 3, 6, 16 }
1	2	{ 3, 22, 16 }
		⋮
2	2	{ 3, 22, 224 }

Aliasing을 사용하지 않는다면, 지역 변수를 도입하여 읽기 작업을 최소화하고 쓰기 작업을 한 번만 수행하도록 최적화할 수 있다.

void sum_each_row_opt(double *matrix, double *vector, long n) {
    for (long r = 0; r < n; r++) {
        double sum = 0;
        for (long c = 0; c < n; c++)
            sum += matrix[n * r + c];
        vector[r] = sum;
    }
}

.L10:
        addsd   (%rdi), %xmm0         ; Load + Add
        addq    $8, %rdi
        cmpq    %rax, %rdi
        jne     .L10
        movsd   %xmm0, (%rsi,%rcx,8)  ; Store

Exploiting Instruction-Level Parallelism

---

Benchmark Performance

typedef struct {
    size_t len;
    data_t *data;
} vec;

int get_vec_element(vec *v, size_t index, data_t *dest) {
    if (index >= v->len)
        return 0;
    *dest = v->data[index];
    return 1;
}

size_t vec_length(vec *v) {
    return v->len;
}

data_t *get_vec_start(vec *v) {
    return v->data;
}

void combine1(vec *v, data_t *dest) {
    *dest = IDENT;
    for (long i = 0; i < vec_length(v); i++) {
        data_t val;
        get_vec_element(v, i, &val);
        *dest = *dest OP val;
    }
}

Name	Description
data_t	int, long, float, double 중 하나
IDENT	0 또는 1
OP	+ 또는 *

다음은 combine1()의 성능을 요소 당 클럭 사이클(Cycles Per Element, CPE)로 나타낸 것이다.

		정수		FP
	+	×	+	×
Unoptimized	22.68	20.02	19.98	20.18
-O1	10.12	10.12	10.17	11.14

Effect of Basic Optimizations

combine1()을 다음과 같이 최적화한 뒤 성능을 다시 측정해 보자. (이하 -O1 기준)

• 불필요한 경계 검사를 수행하지 않음
• 지역 변수를 도입하여 optimization blockers 제거

void combine2(vec *v, data_t *dest) {
    long length = vec_length(v);
    data_t *d = get_vec_start(v);
    data_t t = IDENT;
    for (long i = 0; i < length; i++)
        t = t OP d[i];
    *dest = t;
}

		정수		FP
	+	×	+	×
combine1()	10.12	10.12	10.17	11.14
combine2()	1.27	3.01	3.01	5.01

Pipelined Functional Units

현대의 프로세서는 여러 개의 파이프라인을 가지고 있어 한 클럭 사이클에 여러 개의 명령어를 병렬적으로 처리할 수 있으며, 이를 슈퍼스칼라(Superscalar) 프로세서라 한다.

파이프라이닝²의 아이디어는 명령어 처리를 여러 단계로 나누어서 수행하는 것이다.

long mult_eg(long a, long b, long c) {
    long p1 = a * b;
    long p2 = a * c;
    long p3 = p1 * p2;
    return p3;
}

Cycle	1	2	3	4	5	6	7
Stage 1	a * b	a * c			p1 * p2
Stage 2		a * b	a * c			p1 * p2
Stage 3			a * b	a * c			p1 * p2

• a * b와 a * c는 서로 의존성이 없으므로, a * b 연산을 수행하는 도중에 a * c 연산을 시작할 수 있다.
• 3단계의 파이프라이닝을 통해, 총 9 클럭 사이클이 필요한 작업을 7 클럭 사이클만에 완료하였다.

Loop Unrolling

Loop unrolling은 루프 내부에서 더 많은 작업을 수행함으로써 루프의 반복 횟수를 줄이는 최적화 기법이다.

void combine3(vec *v, data_t *dest) {
    long length = vec_length(v);
    long limit = length - 1;
    data_t *d = get_vec_start(v);
    data_t x = IDENT;
    long i;
    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i += 2)
        x = (x OP d[i]) OP d[i + 1];
    /* Finish any remaining elements */
    for (; i < length; i++)
        x = x OP d[i];
    *dest = x;
}

루프 내부에서 OP 연산을 2번 수행하여 루프 반복 횟수가 절반으로 감소하였다.

		정수		FP
	+	×	+	×
combine2()	1.27	3.01	3.01	5.01
combine3()	1.01	3.01	3.01	5.01
Latency bound	1.00	3.00	3.00	5.00

루프 반복에 따른 오버헤드가 감소하면서 정수 덧셈이 조금 빨라졌지만 나머지는 그대로인데, 이는 루프에서 반복적으로 수행하는 OP 연산 사이에 순차적 의존성(Sequential dependency)이 존재하기 때문이다.

Order	Computation
1	IDENT * d[0] = res1
2	res1 * d[1] = res2
3	res2 * d[2] = res3
4	res3 * d[3] = res4
5	res4 * d[4] = res5
6	res5 * d[5] = res6
7	res6 * d[6] = res7
8	res7 * d[7] = res8

Reassociation

다음과 같이 괄호를 이동하여 연산 순서를 변경해 보자.

void combine4(vec *v, data_t *dest) {
    long length = vec_length(v);
    long limit = length - 1;
    data_t *d = get_vec_start(v);
    data_t x = IDENT;
    long i;
    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i += 2)
        x = x OP (d[i] OP d[i + 1]);
    /* Finish any remaining elements */
    for (; i < length; i++)
        x = x OP d[i];
    *dest = x;
}

Order	Computation
1	d[0] * d[1] * IDENT = res1
2	d[2] * d[3] * res1 = res2
3	d[4] * d[5] * res2 = res3
4	d[6] * d[7] * res3 = res4

		Integer		Double FP
	+	×	+	×
combine2()	1.27	3.01	3.01	5.01
combine3()	1.01	3.01	3.01	5.01
combine4()	1.01	1.51	1.51	2.51
Latency bound	1.00	3.00	3.00	5.00

의존성 체인의 길이가 절반으로 감소함에 따라, 정수 덧셈을 제외한 나머지 세 연산의 실행 속도가 2배 가까이 빨라졌다.

부동 소수점 연산은 결합 법칙이 성립하지 않는 경우³가 존재하기 때문에, 연산 순서를 변경하는 것에 주의해야 한다. 이러한 이유로 컴파일러는 위와 같은 최적화를 수행하지 않는다.

Multiple Accumulators

void combine5(vec *v, data_t *dest) {
    long length = vec_length(v);
    long limit = length - 1;
    data_t *d = get_vec_start(v);
    data_t x0 = IDENT;
    data_t x1 = IDENT;
    long i;
    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i += 2) {
        x0 = x0 OP d[i];
        x1 = x1 OP d[i + 1];
    }
    /* Finish any remaining elements */
    for (; i < length; i++)
        x0 = x0 OP d[i];
    *dest = x0 OP x1;
}

		정수		FP
	+	×	+	×
combine2()	1.27	3.01	3.01	5.01
combine3()	1.01	3.01	3.01	5.01
combine4()	1.01	1.51	1.51	2.51
combine5()	0.81	1.51	1.51	2.51
Latency bound	1.00	3.00	3.00	5.00

Reassociation과 마찬가지로 연산 순서를 변경하기 때문에, 부동 소수점 연산의 경우 주의해야 한다.

Advanced Vector Extensions

AVX(Advanced Vector Extensions)는 x86의 SIMD 확장 명령어 집합으로, SSE⁴의 후속작이다. AVX의 2번째 버전인 AVX2는 하스웰(Haswell) 프로세서에 처음으로 도입되었다.

%ymm0부터 %ymm15까지 총 16개의 256비트 레지스터가 존재한다. 각 레지스터에는 여러 개의 데이터를 저장할 수 있으며, SIMD 명령어⁵를 통해 병렬 연산을 수행할 수 있다.⁶

• 8비트 정수 32개
• 16비트 정수 16개
• 32비트 정수 8개
• 64비트 정수 4개
• 32비트 부동 소수점 수 8개
• 64비트 부동 소수점 수 4개

AVX-512에는 총 32개의 512비트 레지스터가 존재한다.

Dealing with Conditionals

---

Branch Prediction

명령어 수준 병렬성(Instruction-Level Parallelism, ILP)과 더불어 고려해야 할 또 다른 요소는 분기 예측(Branch prediction)⁷이다. 현대의 프로세서는 95% 이상의 정확도로 분기를 예측할 수 있지만, 예측이 틀리면 파이프라인을 비우고 새로 채워야 하므로 큰 오버헤드가 발생한다. 따라서 예측하기 어려운 분기를 최소화하도록 코드를 작성하는 것이 좋다.

References

---

• Carnegie Mellon University. (2015). Lecture 10: Program Optimization. [Online].

Footnote

1. “Lecture 03: Bits, Bytes, and Integers (cont.).” 고볼. [Online]. ↩︎

2. “Lecture 06: Machine-Level Programming II: Control.” 고볼. [Online]. ↩︎

3. “Lecture 01: Course Overview.” 고볼. [Online]. ↩︎

4. “Lecture 08: Machine-Level Programming IV: Data.” 고볼. [Online]. ↩︎

5. Oracle. x86 Assembly Language Reference Manual. [Online]. ↩︎

6. R. E. Bryant and D. R. O’Hallaron. Achieving Greater Parallelism with SIMD Instructions. 2016. [Online]. ↩︎

7. “Why is processing a sorted array faster than processing an unsorted array?” Stack Overflow. [Online]. ↩︎