행렬 곱셈 최적화 1편

안녕하세요 조엘입니다! 프로젝트로 진행한 행렬곱셈 최적화에 대한 포스팅을 진행하도록 하겠습니다. 

소스코드는 https://github.com/joelonsw/Matrix-Multiplication-Multithreading에서 확인하실 수 있습니다!

 

저는 총 4가지 단계를 거쳐 최적화를 진행했습니다.

1.인덱싱 순서를 바꾸어 캐시 hit ratio을 증가시켰습니다.

2.멀티 쓰레딩을 통해 병렬처리를 진행하였습니다.

3.타일링 기법을 통해 캐시 hit ratio를 증가시켰습니다.

4.SIMD를 통해 한번에 많은 데이터를 처리할 수 있게 하였습니다. 

실험은 다음과 같은 환경에서 진행했습니다.

모든 소스코드는 C++로 작성을 했고, g++ version 7.5.0을 사용했습니다.

 

컴파일 옵션은 최적화 옵션을 빼고 진행했습니다. Simd사용을 위해 mavx flag를, 쓰레드 생성을 위해 –pthread flag를 사용했습니다. Simd avx512를 사용할때는 –mavx 대신 –mavx512f를 사용하였습니다.

 

성능 측정을 위해서 Perf 4.15.18버전을 사용했습니다. 특정한 코드 부분에서의 퍼포먼스를 측정하는게 정확하지만, 프로그램의 처음부터 끝까지의 성능을 측정했습니다. 최대한 알맞은 결과를 위해 개선이 된 부분 의외의 모든 코드는 똑같이 작성하였습니다. 

 

모든 실험은 4096매트릭스 사이즈로 진행했습니다. 4096으로 선정한 이유는 실행시간의 차이가 잘 보였고, 4096*4096 매트릭스 3개는 총 약 200메비바이트의 메모리를 차지하기에 Cache의 사용량 파악이 가시적으로 가능하겠다 판단했습니다.

사용한 CPU의 cache 정보 입니다. Wikichip 이라는 사이트에서 가져온 수치입니다.

L1 cache hit의 경우 4 cycle, L2 cache hit의 경우 14 cycle, L3 cache hit의 경우 50-70 cycle이 걸린다고 합니다.

만약 L3 cache miss로 인해 main memory에 접근하는 경우 100~300 cycle이 걸린다고 합니다. 

첫번째 최적화로 indexing을 바꿨습니다. 기존의 unoptimized matrix multiplicatio은 첫행렬은 row-wise, 두번째 행렬은 column-wise로 곱셈을 진행했습니다.

배열의 요소들은 연속된 주소로 저장되기 때문에, column-wise 방식의 메모리접근은 지양해야 한다고 판단했습니다.

따라서 기존 IJK방식을 KIJ방식으로 교체하였습니다.

결과는 다음과 같았습니다.

우선 unoptimized 버전은 1629초, 약 27분이 소요되었습니다. 반면에 KIJ으로 인덱싱을 바꾼 버전에서는 219초가 소요되었습니다. 약 7.41배의 성능향상이 이루어졌습니다.

Unoptimized 버전에서 제가 눈여겨본 수치는 Instruction per cycle IPC 였습니다. 이 수치가 1보다 작게 나왔다는 것은, CPU가 메모리를 기다리느라 instruction 수행을 하지 못했다는 의미입니다.

보시다시피 unoptimized 버전에서는 LLC의 miss rate은 83.3프로에 달합니다. 이는 column-wise하게 접근한 배열의 모든 원소가 cache miss를 일으켰기 때문입니다.

하지만 KIJ역시 LLC에서 miss rate이 50프로에 달했습니다. 이는 KIJ 방식에서 result매트릭스는 K가 1이 증가할때 마다 모든 원소에 접근하기 때문에 입니다. 배열의 크기가 LLC의 크기를 넘어서기 때문에,

K가 하나씩 증가할때 마다 처음부터 다시 요소에 접근하는 result 배열은 Cache 재사용이 불가능합니다.

두번째 단계로 멀티쓰레딩을 진행하였습니다.

책의 Cannon과 DNS알고리즘을 보고 착안하였습니다.

제가 행렬곱셈을 진행한 알고리즘은 다음과 같습니다.

A와 B를 16등분을 합니다.

Result array는 A의 행, B의 열의 곱으로 원소들을 구하게 됩니다.

예시로 Result행렬의 첫 칸은 A의 1행과 B의 1열의 곱으로 표현됩니다.

 

다른 Result의 16칸 모두 이와 같이 표현이 가능합니다.

여기에서 병렬화가 이루어 집니다. 16개의 쓰레드를 생성하여, 각 쓰레드0~ 15까지 Result0~15칸에 알맞은 연산이 이루어질 수 있게 합니다.

첫단계에서는 제가 그린 그림의 왼쪽 상단의 16등분 된 A와 B의 행렬중 하나씩이 곱해집니다.

16쓰레드들이 각자의 연산을 완료하면, thread들이 join합니다.

두번째 단계에서는 그림의 오른쪽 상단에 위치한 것들을 16쓰레드를 생성해 수행하고 완료 시 join합니다.

세번째, 네번째 단계도 비슷한 과정으로 진행한 뒤, 함수를 종료합니다.

이 알고리즘의 가장 아쉬운 부분은 한 단계별로 16개의 쓰레드의 연산이 모두 종료되어야 그다음 단계로 넘어간다는 것이었습니다.

가장 늦게 끝나는 쓰레드가 해당 단계의 실행시간이 되어, 해당 단계에서 일찍 끝난 Core는 idle상태가 됩니다.

어떻게 곱해지는지에 대한 코드입니다.

우선 MultipleArg라는 구조체를 생성했습니다.

Matrix_multiply_optimized 함수에서는, 이 구조체를 동적할당해 , A행렬, B행렬, Result행렬의 시작 인덱스와 A행렬, B행렬, Result행렬의 주소를 저장합니다.

이 구조체를 매개변수로 multi라는 함수에 전달하며, 쓰레드를 생성합니다.

Multi함수에서는 KIJ 인덱싱 방법으로 16등분된 A행렬, B행렬, Result행렬의 연산을 진행하게 됩니다.

 

캐논알고리즘보다 위의 알고리즘이 더 성능이 좋다고 생각하는 이유는 다음과 같습니다.

캐논 알고리즘은 매 shift별 A행렬과 B행렬의 모든 원소에 접근합니다

제 알고리즘은 각 단계별로 접근하는 A행렬과 B행렬이 16등분된 행렬 중 4부분만 접근합니다.

이를 통해 캐논 알고리즘 비해 공유 캐시인 L3 cache의 miss rate을 줄일 수 있다고 생각했습니다.

4*4 행렬에서 각각 어떤 인덱스에 접근하는지를 나타내 보았습니다.

각 레벨별로 제가 짠 코드는, A와 B는 4가지의 index만을 계산하지만, Cannon에서는 A,B,Result 전체가 모든단계에서 계산되는 것을 볼 수 있습니다.

사실 처음 구현할때는 DNS알고리즘을 구현하고 싶었습니다. 하지만 문제가 있었습니다.

64개의 쓰레드를 생성하여 모두 실행하면, 16개의 core를 쓰는 앞선 알고리즘보다 많은 20개의 코어를 모두 활용할 수 있기 때문에 더 성능이 좋아질 수 있었지만, Race condition이 발생했습니다.

16등분된 result배열에 4단계의 AB배열 연산들이 동시에 수행되어 결과값을 항상 보장할 수 없었습니다.

Mutex를 써보았지만, 16개의 쓰레드 fork and join이 더 빠르다고 판단되어 이를 통해 멀티쓰레딩을 구현하였습니다.

DNS알고리즘과 약간 다르지만, 명칭은 dns라고 붙이고 남은 발표 진행하도록 하겠습니다.

처음 예상으로는, 4096*4096을 16등분한 1024*1024 연산을 4번 수행하는 시간이면 완료되겠다고 생각했습니다.

KIJ방식으로 1024*1024를 수행하면 약 4초 정도 소요되는데, 16초면 되겠다고 생각했습니다.

하지만 27초가 소요되었습니다.

원인으로는, clock rate의 감소입니다. 1개의 core만 사용할때는 3.184 GHz였던 clock rate가 16개의 core 연산에 사용하자, 2.824GHz로 줄었습니다.

또한 멀티 쓰레딩과 관련한 코드를 추가 작성해주어 instruction의 개수도 증가하였습니다.

 

 

DNS와 캐논 알고리즘을 테스트 해보았습니다. 예상대로 LLC의 miss rate이 캐논알고리즘에서 높게 나왔습니다.

 

너무 길어져서... 여기까지만 포스팅하고 2부에 더 올리도록 하겠습니다!