SIMD와 4x4 Matrix 데이터 처리

 안녕하세요. 평생개발자 입니다.

SIMD와 4x4 Matrix 데이터 처리에 대한 주관적인 의견입니다.

단일명령어 SISD(Single Instruction Single Data)로 구현된 알고리듬을 처리 속도를 높이기 위해 SIMD(Single Instruction Multiple Data) 자료구조를 변경하게 되었는데, 현재 구조는 Linked-list 구조로 자료형이 링크되어 있다 보니 데이터를 읽고 쓰려면 PC(Program count) 가 다시 찾아가는 문제가 있습니다.

수정 포인트!!

1단계 : Linked-list -> Array-list로 변경하는 구조로 수정작업이 필요 했고

2단계 : 3차원(X,Y,Z) 어떠한 자료구조를 가질것 인가?

 - 첫번째 구조

X0

Y0

Z0

X1

Y1

Z1

X2

Y2

Z2

...

첫 번째 구조는 그래픽스(openGL, SDL,etc)하시는 분이라면 익숙하실 것 입니다. 3차원(3D)을 다루기 위해서는 [X, Y, Z]구조로 메모리에 담아두었다가 필요하면 Copy를 하기도 하고, 

openGL에 버퍼로 옮길 수 있는 구조 입니다.

여기서 요점은, [X, Y, Z]가 데이터를 처리 시간(Processing Time)을 단축할 수 있는 구조인가? 입니다.    

그래픽스에서는 3차원 데이터를 변형하기 위해서 4x4 Matrix 를 사용 합니다. 

여기서부터 최적의 연산(Computing)을 하기 앞어서 , CPU 종류를 결정되게 됩니다.

 

 저가 CPU는 SIMD 명령어(instruction set)이 존재하지 않습니다.  대표적으로 Intel 아톰, 셀러론 시리즈가 되겠습니다. 얘네들은 암호화 변복조에 필요한 AES(Advanced Encryption Standard) 정보만 포함되고, 연산에 필요한 레지스터는 없습니다. 즉,   SISD 연산만 가능하기 때문에 속도향상을 기대하기 어렵습니다. (동영상 플레이 하면 CPU 점유 상승)

SIMD 명령어가 포함된 Intel i3,i5,i7, 제온 등이 있습니다.  AMD는 애슬론, 비쉐라, 라이젠 등이 있는데,  저가 CPU에서도 SIMD 명령어 셋이 포함되어 있었습니다. 그래서 사람들이 인코딩 작업에는 AMD를 쓰라고 하는지? 느낌이었는지 궁금하군요.

 SISD 명령어는 [1] + [1] = [2] 하나씩 명령어를 처리하는 단일 연산자라고 생각하면 됩니다. 메모리에서부터 명령어 파이프라인 속도, CPU 병목현상에 따라서 속도가 결정되고, 일반적인 자료형으로 계산을 하였다면 SISD를 사용하고 있을 것입니다. 어쩌면 컴파일러가 지능적이라면 자동으로 수정할 지 의문!

 SIMD는 [1,2,3,4] + [1,2,3,4] = [2,4,6,8]  []묶음으로 한 번의 명령어로 데이터를 처리 할 수 있다.  

즉, SIMD는 묶음으로 한 번에 명령어를 처리함으로서 전체 명령어 수행 횟수를 줄일 수 있게 되어 속도 향상 효과를 가져다준다.  

SIMD 기대 효과에 대해서 이야기 드리겠습니다. 

 CPU 명령어 셋에는 크게 MMX, SSE, AVX, FMA 등 있습니다. (자세한 설명은 다음 포스팅에..)

각각의 레지스터들은  MMX = 64bit, SSE = 128bit, AVX = 256, AVX512 = 512bit 

데이터를 []묶을 수 있는 크기를 가지고 있습니다. 방금 언급한것 처럼 한 번에 데이터를 크게 묶을 수록 PC 수행 횟수가 줄어들기 때문에 속도 향상 효과를 가져다줍니다.

지금까지 서론 이였다면....    이제 본론으로 들어가겠습니다.

4x4 매트릭스가 어떠한 구조로 계산이 되는가? 이게 핵심 포인트 입니다.

SIMD 레지스터는 최대 512bit = flaot[16]를 묶을 수 있는데 어떻게 matrix에 담을 것인가? 

이 의문점에서는 두번째 구조를 확인하면 이해될 것이다. 

첫번째 구조에서 최적의 속도로 연산하는 방법은 SSE = float[4]  와 FMA 사용 할 것이다. 

Matrix SISD로 계산을 풀면

W' = (X*0 + Y*0 + Z*0 + 1 * 1 )               -> 8

 X' = (X*1 + Y*0 + Z*0 + 0 * 1 ) / W'         -> 9

 Y' = (X*0 + Y*1 + Z*0 + 0 * 1 ) / W'         -> 9

 Z' = (X*0 + Y*0 + Z*1 + 0 * 1 ) / W'         -> 9

Operand = 35

Matrix SIMD (SSE, FMA) (포스팅 예정)

E = A[X*0, Y*0, Z*0, 1 * 1 ] + B[X*1, Y*0, Z*0, 0 * 1 ] +

C[X*0, Y*1, Z*0, 0 * 1 ] + D[X*0, Y*0, Z*1, 0 * 1 ]       -> 6

X' = E[0] / E[3]    -> 2

Y' = E[1] / E[3]    -> 2

Z' = E[2] / E[3]    -> 2

Operand = 12

SIMD 를 사용하여 연산 수를 줄여 알고리듬 수행 속도를 높일 수 있게됩니다.

보통 openCV, Eigen, alglib 등등 matrix 관련된 라이브러리에서 SIMD 연산을 하고 있지만, Matrix 구조에 맞도록 넣어 주어야 합니다.

- 두번째 구조

X0

X1

X2

X3

X4

X5

X6

X7

X8

...

Y0

Y1

Y2

Y3

Y4

Y5

Y6

Y7

Y8

...

Z0

Z1

Z2

Z3

Z4

Z5

Z6

Z7

Z8

...

첫번째 구조 SSE = float[4] 만 고려하였다면, 두 번째 구조에서는 avx512 = float[16]을 처리 할 수 있는 자료구조를 만들어서 데이터 처리 수행 시간을 크게 단축 할 수 있게 됩니다.

W' = (X*0 + Y*0 + Z*0 + 1 * 1 )               -> 8

 X' = (X*1 + Y*0 + Z*0 + 0 * 1 ) / W'         -> 9

 Y' = (X*0 + Y*1 + Z*0 + 0 * 1 ) / W'         -> 9

 Z' = (X*0 + Y*0 + Z*1 + 0 * 1 ) / W'         -> 9

기존의 SISD 형대의 자료형을 한 번에 16개를 처리한다고 생각하면 이해가 빠를것이라 생각 한다. 

즉, float[16] 를 한 번에 가지고 올 수 있는 구조 

x[x0, x1, ..., x15]

y[y0, y1, ..., y15]

z[z0, z1, ..., z15]

4x4 매트릭스도 16개가 있다고 생각하면 됩니다.

W[]' = (X[]*0[] + Y[]*0[] + Z[]*0[] + 1[] * 1[] )               -> 8

 X[]' = (X[]*1[] + Y[]*0[] + Z[]*0[] + 0[] * 1[] ) / W[]'         -> 9

 Y[]' = (X[]*0[] + Y[]*1[] + Z[]*0[] + 0[] * 1[]) / W[]'         -> 9

 Z[]' = (X[]*0[] + Y[]*0[] + Z[]*1[] + 0[] * 1[] ) / W[]'         -> 9

Array List인 이러한 구조를 통해서 명령어 처리 량이 16배 줄어든 것이다.  이러한 구조가 16배 속도 향상을 나타내는것은 아니며, 메모리 대역폭과 CPU레지스터의 성능에 따라서 좌우될것이라 생각 하고 있습니다. 

3단계 : SIMD 명령어를 지원하지 않을경우 예외처리.

다음 포스팅에서 좀 더 구체적이고 발전된 모습으로 정리하겠습니다. 

궁금한 사항은 문의 주세요. ^^