[CS] 루프 풀기 및 병렬성 높이기 (Loop unrolling)

루프 풀기

루프 풀기는 루프의 매 반복 실행마다 계산되는 원소의 수를 증가시켜서 루프의 총 반복 횟수를 줄이는 프로그램 변환이다.

개선되는 점

1. 루프 인덱스 계산과 조건부 분기와 같이 프로그램의 결과와는 직접적으로 관련이 없는 연산들의 수를 줄인다.
2. 추가적인 최적화를 적용할 수 있게 된다.

 

2 x 1 루프 풀기

루프 한 번 마다 배열의 두 원소를 처리한다. 루프의 인덱스는 반복마다 2씩 증가한다.

벡터의 길이가 2의 배수가 아닐 가능성이 있으므로 임의의 벡터 길이에 대해서도 정확하게 동작해야 한다.

해결법은 루프의 한계를 n-1로 설정한다.

 

k x 1 루프 풀기

위와 같이 임의의 인자 k에 대해 일반화할 수 있다.

n-k+1를 한계로 설정한다.

 

 

2 x 1 루프 풀기에서 루프 오버헤드 연산을 줄여 정수 덧셈에 대한 CPE가 개선되었다.

다른 경우들에 대해서는 개선 사항이 없는데 그 이유를 알기 위해 기계 수준 코드를 조사해보자.

 

 

아래의 코드는 위의 combine5 내부 루프에 대한 코드이며, double 자료형의 곱셈을 나타낸다.

 

(좌) combine4 / (우) combine5

 

combine4는 i 변수를 안 쓰고 데이터의 주소를 직접 8(바이트)씩 올리고,

combine5는 i를 저장하는 rdx를 2씩 올려 %rax + (8 * i)로 연산하여 역참조 한다.

 

combine5를 그림으로 표현한 것

 

vmulsd 인스트럭션은 배열 원소를 메모리에 적재하고, 이 값을 누적된 값과 곱한다.

%xmm0 가 매번 루프가 실행될 때 두 번씩 읽히고 쓰이는 것을 알 수 있다.

 

combine5 연산들을 데이터 흐름 그래프로 추상화

(좌) combine4 / (우) combine5

 

위의 우측 combine5 그림에서 여전히 n개의 mul 연산을 갖는 critical path를 가지고 있는 것을 볼 수 있다.

반복 실행 횟수는 절반으로 줄었으나, 매 실행마다 연속된 두 번의 곱셈 연산을 갖는다.

 

이 critical path가 루프 풀기를 사용하지 않은 코드의 성능에 대해서 제한 요소이기 때문에

k x 1 루프 풀기가 있는 경우에도 여전히 같은 상태를 가진다.

 

gcc -03 이상일 때 컴파일러는 일련의 루프 풀기를 수행한다.

 

 

 

병렬성 높이기

덧셈과 곱셈을 수행하는 기능 유닛들은 모두 완전히 파이프라인화 되어 있으며,

이것은 이들이 매 클럭 사이클마다 새로운 연산을 시작할 수 있으며,

일부 연산들은 복수의 함수 유닛글에 의해 수행될 수 있다는 것을 의미한다.

 

하드웨어는 곱셈과 덧셈을 훨씬 빠른 속도로 실행할 수 있는 잠재력을 가졌지만,

값들을 한 개의 변수 acc로 누적하고 있었기 때문에 루프 풀기를 사용하더라도 이 능력을 활용할 수 없었다.

이전의 계산이 완료될 때까지는 acc의 새로운 값을 계산할 수 없으며,

새 연산을 시작할 수 있는 경우에도 매 L (연결연산의 지연시간) 사이클마다 한 번만 시작하게 된다.

 

이제 우리는 이 순차적 의존성을 깰 수 있으며,

지연시간 경계값보다 더 좋은 성능을 얻을 수 있는 방법들을 조사해보자.

 

다수의 누산기 사용 / 2 x 2 루프 풀기

정수 덧셈이나 곱셈과 같이 교환성과 결합성이 있는 연결연산에 대해서

연결연산의 집합을 여러 부분으로 나누고,

결과를 마지막에 합치는 방법을 사용해서 성능을 개선할 수 있다.

예를 들어 Pn이 원소 a0, a1, … an-1의 곱을 나타낸다고 하자.

 

 

n이 짝수라고 가정하면 Pn = PEn x POn이라고 쓸 수 있으며,

PEn은 짝수 인덱스 원소들의 곱이고, POn은 홀수 인덱스를 갖는 원소들의 곱이다.

 

 

그리고 아래는 이 방법을 사용하는 코드다.

 

 

반복 실행마다 보다 많은 원소를 연결하기 위한 이중 루프 풀기와

짝수 인덱스를 갖는 원소들과 홀수 인덱스를 갖는 원소들을 각각 acc0, acc1에 누적하는

이중 병렬성을 모두 사용한다.

이를 2 x 2 루프 풀기라고 부른다.

 

모든 경우에 대해서 성능이 개선된 것을 볼 수 있다.

가장 중요한 것은 지연시간 경계로 내포된 장벽을 깨뜨렸다는 것이다.

이 프로세서는 더 이상 연산의 시작을 이전 값이 완료되기까지 지연할 필요가 없어졌다.

 

5.22 combine6에 대한 내부 루프의 그래픽 표시 / 5.23 combine6의 데이터 흐름 그래프

 

combine5에서처럼 내부 루프는 두 개의 vmulsd 연산을 포함하고 있지만,

이 인스트럭션들은 이들 사이에 데이터 의존성 없이 별도의 레지스터들에 읽고 쓰는 mul 연산들로 번역된다.

 

combine6 내부 루프 그래픽 표시

 

이 템플릿을 n=2번 복사해서 이 함수의 실행을 길이 n의 벡터에 대해 모델링한다.

이제 두 개(짝수, 홀수)의 critical path를 갖는다는 것을 알 수 있다.

이들은 각각 n=2 연산만을 포함하며, CPE 값 5.00/2 = 2.50을 얻는다.

 

비슷한 해석을 통해서 여러 가지 조합의 데이터 타입과

연결연산에 대해서 지연시간 L을 같는 연산들에 대해 CPE가 L/2라는 것을 알 수 있다.

 

유일한 예외는 정수 덧셈에 대한 경우다.

CPE를 1.0 이하로 줄였지만, 여전히 이론적 한계인 0.50을 얻기에는

너무 많은 루프 오버헤드가 존재한다.

 

k x k 루프 풀기

 

k=10 까지의 값들에 대해 이 변환을 적용했을 때의 효과를 보여준다.

충분히 큰 k 값에 대해 이 프로그램이 모든 경우에 대해 처리량 한계값을 얻었다.

1. 정수 덧셈 k=7로 CPE 0.54를 얻었으며,
2. 이는 두 개의 적재 유닛들로 인한 처리량 한계 0.50에 근접했다.
3. 정수 곱셈과 부동소수점 덧셈은 k≥3일 때 CPE 1.01을 얻었으며,
4. 함수 유닛에 의한 처리량 한계 1.00에 근접했다.
5. 부동소수점 곱셈은 k≥10에 대해 CPE 0.51을 얻었으며,
6. 두 새의 부동소수점 곱셈기와 두 개의 적재 유닛에 의한 처리량 한계 0.50에 근접했다.

부동소수점 곱셈에서 거의 두 배의 처리량을 얻을 수 있는 것에 주목할 필요가 있다.

덧셈보다 더 복잡한 연삼이에도 불구하고 덧셈과 동일하다.

 

해당 연산을 수행할 수 있는 모든 함수 유닛들에 대해

파이프라인을 지속적으로 채울 수 있을 때에만 처리량 한계를 얻을 수 있다.

 

시간 지연 L, 용량 C를 갖는 연산에 대해, k ≥ C * L을 요구한다.

(부동소수점 곱셈은 C=2, L=5를 가지며, 루프 풀기 인자 k≥10을 필요로 한다.

부동소수점 덧셈은 C=1, L=3을 가지며, k≥3으로 최대 처리량을 얻는다.)

 

k x k 루프 풀기를 수행할 때, 원래 함수의 기능성을 보존하는지도 고려해야한다.

2장에서 오버플로우 발생시 2의 보수 산술연산이 교환, 결합법칙이 성립한다는 것 때문에

combine6의 계산 결과는 combine5와 동일한 것이다.

그래서 최적화 컴파일러는 combine4 → combine5 → combine6으로 변환한다.

 

반면에, 부동소수점 곱셈과 덧셈은 결합법칙이 성립하지 않으므로

combine5와 combine6이 근사나 오버플로우로 인해 다른 결과를 만들 수 있다.

고로 컴파일러는 부동소수점으로는 이러한 변환을 시도하지 않는다.

 

재결합 변환  / 2 x 1a 루프 풀기

이제는 순차적 의존성을 끊을 수 있는 방법을 조사해보고, 지연시간 경계값을 넘어서 성능을 개선해보자.

 

 

 combine5와 비교해서 아래의 연산만 바뀌었다.

 

 

단지 두 괄호가 어떻게 위치하는지만 다르다.

이것을 재결합 변환(reassociation transform)이라고 부르는데,

이 괄호들이 누적된 값 acc와 연결된 벡터 원소들에서의 순서를 이동시켜

2 x 1a 라고 부르는 일종의 루프 풀기를 만들기 때문이다.

 

 

같은 연산처럼 보이지만 CPE를 측정해보면 combine6 버전의 성능과 거의 일치한다.

이 경우들은 지연시간 한계로 주어진 장벽을 깨뜨린 것이다.

 

 

 

우측 그림을 보면 하나의 mul 연산만이 데이터 의존성 체인을 형성한다.

매 반복 실행 내에 첫 번째 곱셈은 이전 반복 실행으로부터 누적된 값을 기다리지 않고 수행할 수 있어서 CPE 값을 약 2배로 줄일 수 있다.

 

 

k=10까지의 k x 1a 루프 풀기의 효과를 보면

k x k 루프 풀기와 유사한 성능을 생성한다는 것을 알 수 있다.

 

정수 연산의 경우 벡터 원소들의 재배치가 결과에 아무 영향을 주지 않지만,

부동소수점 연산에서는 그 여부를 더 검사해야한다.

 

재결합 변환은 계산하는 데 핵심 경로를 따라가며 연산의 수를 축소할 수 있으며,

다수의 함수 유닛들과 이들의 파이프라이닝 능력을 더 잘 활용해서 좋은 성능을 얻게된다.

대부분의 컴파일러들은 연산들이 결합성을 갖는 것이 보장되지 않기 때문에

부동소수점 연산의 재결합은 시도하지 않을 것이다.

정수의 경우에도 언제나 좋은 효과를 얻는 것은 아니다.

 

 

SIMD 인스트럭션으로 보다 높은 병렬성 달성하기

인텔은 1999년에 SSE (Streaming SIMD Extension) 인스트럭션들을 도입했고,

최근 버전의 SSE는 AVX (Advanced Vector Extension)로 명명되었다.

단일 인스트럭션 내에서 전체 데이터의 벡터에 대해 동작에 관련된다.

 

이 벡터들은 %ymm0 ~ %ymm15 라는 특별 벡터 레지스터 집합에 보관되며,

32바이트 길이를 가지고, 각각 8개의 32-비트 / 4개의 64-0비트 수를 보관할 수 있다.

 

AVX 인스트럭션들은 4 또는 8개의 집합의 값들을 병렬로 더하거나 곱하는 것과 같은

벡터 연산을 이 레지스터들에 대해서 수행할 수 있다.

 

예를 들어, %ymm0이 8개의 단일정밀도 부동소수점을 포함하고,

%rcx가 연속된 8개의 단일 정밀도 부동소수점 수의 메모리 주소를 가지고 있다면,

 

 

8개의 값을 메모리에서 읽어들여서 0 ≤ i ≤ 7에 대한 ai ← ai * bi를 병렬로 8번의 곱셈을 수행하고,

결과 값 8개의 곱을 벡터 레지스터 %ymm1에 저장할 것이다.

 

이는 즉 한 개의 인스트럭션이 다수의 데이터 값들에 대해 계산을 생성할 수 있다는 것이고

이것이 SIMD (Single-Instruction, Multiple-Data)를 의미한다.

 

gcc는 c언어에 확장을 제공해서 AVX의 벡터 인스트럭션들로 컴파일될 수 있는

벡터 연산을 사용해서 프로그래머가 표현할 수 있게 해준다.

이는 어셈블리어로 직접 코드를 작성하는 것보다 바람직한데,

gcc가 다른 프로세서에서 사용하는 벡터 인스트럭션들을 위한 코드도 생성할 수 있기 때문이다.

 

 

SIMD 인스트럭션들을 활용하면 4배~8배의 성능을 추가로 얻을 수 있다.

 

『Computer Systems: A Programmer's Perspective』 책을 읽고 정리한 글입니다.
검색을 허용하지 않고, 수익을 창출하지 않습니다.