SIMD 프로그래밍

SIMD 란 ?

SIMD란 Single Instrument Mutliple Data 라는 뜻으로 하나의 명령어로 여려개의 데이터를 처리할 수 있는 인텔의 기술을 말한다. 물론 현재에는 인텔과 amd가 기술제휴를 해서 같이 개발하는 듯 하다.
이 기술은 SSE 명령어가 지원되면 사용가능하며, x86_64 명령어를 처리가능한 CPU의 경우에는 사용가능하다.
이 SIMD 명령어를 사용하게 되면, 엄청난 속도향상을 보인다. 최소 20%에서 극단적으로는 12배까지도 속도의 향상을 얻을 수 있는 것. 일단 기본적으로는 벡터연산에 대해서 효율적인 명령어셋이라서 3D 프로그램에서 주로 사용된다. 물론 극단적인 병렬화가 필요하다면 GPGPU를 쓰는 것이 좋긴 한데, 저 부분은 상당히 어려운 것으로 알고 있다.

SIMD 명령어 계보

MMX, SSE~SSE4, AVX 명령어로 계보가 이어지며, 이중 MMX는 더이상 사용되지 않는다.
AVX는 256bit 연산이 지원되고 3피연산자가 지원된다는 점에서 SSE와 큰 차이점이 존재한다.
혹시나 내 컴퓨터가 어떤 명령어가 지원되지는지 보고싶으면 cpu-z 라는 프로그램을 통해 볼 수 있다. 나는 AVX2 까지 지원이 된다.

특징

일단 기본적인 특징은 우리의 CPU는 연산기를 여러개 가지고 있기 때문에, 이걸 여러개 쓰자는 것이다. 아래 그림과 같이, A0+B0, A1+B1, A2+B2, A3+B3 연산을 4번 할 것을 병렬로 한방에 더해버리자는 것이다.
(이미지 출처 :https://stonzeteam.github.io/SIMD-%EB%B3%91%EB%A0%AC-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D/)

벡터연산에 효율적이라는 것이 무슨 소리인지 이해가 되는가? 백터는 (x,y,z) 꼴로 보통 표시돼있는데 연산 3번 할것을 한번으로 줄일 수 있다는 것이다. 본 포스팅에서는 SSE 에 대해서 다룰 것인데, SSE 시리즈는 기본적으로 128bit 까지 한번에 연산이 가능하고, 이를 풀어서 쓰자면

byte 16 개 or word 8개 or dword 4 개 or qword 2 개로 이루어진 배열 또는 단정밀도 부동소수점 4개 or 배정밀도 부동소수점 2개를 한번에 연산할 수 있다는 것이다. 한마디로 128bit 크기의 이어진 자료형 끼리는 한번에 연산할 수 있다는 것!

하지만 이 막강한 기술을 사용하기 위해서는 메모리 정렬이라는 것이 필요하다. 우리는 128bit 레지스터를 사용하기 때문에 메모리 끝 주소가 00 으로 끝나면 된다. 이 이유는 CPU에서 메모리에 접근할 때 해당 레지스터의 크기 단위로 접근하기 때문인데, 다행히도 SSE 명령어셋은 5% 정도의 속도 저하가 있지만 메모리 정렬을 하지 않아도 되는 명령어를 제공한다. 이 과정에서 CPU는 페이지 단위에 맞게 알아서 쉬프트 연산등을 이용해 메모리에 접근하여 레지스터로 가져오는 연산을 추가적으로 진행할 것이다.

기본적인 메모리 정렬을 하는 방법은 다음과 같다.

1. 스택에 배열을 선언하는 경우
   __declspec(align(16)) short v1[8]
   align(16)은 16byte 단위로 정렬하겠다는 것이다.

2. 힙에서 할당받아오는 경우
   short *arr=_aligned_malloc(sizeof(short) * 8,16);
   동일하게 뒤에 16은 16byte 단위로 정렬하겠다는 것이다.

기본적으로 GCC의 경우에는 malloc_align 이 16byte 단위이기 때문에 필요가 없다.

만약 메모리 정렬이 필요한 명령어에 메모리 정렬이 안된 주소를 넣어줬다면, 환경에 따라 다르지만 Segmentation Fault 가 뜨거나, 추가연산을 통해서 정렬해서 계산한다.

메모리 정렬에 대한 자세한 사항은 앞으로 올라올 시리즈들을 참고해주길 바란다.

실습코드 및 설명

백문이불여일견. 아래 코드는 memcpy 함수를 직접 구현한 것이다. 하나는 for loop를 통해서 구현을 했고, 나머지 하나는 sse2 명령어를 이용해서 구현했다. 편의성을 위해서 count는 16의 배수라고 가정했다. 약 500mb 크기의 배열을 복사하여 속도를 측정한다. check_memcpy는 memcpy가 잘 작동했나를 검사하는 함수이다. 이 또한 SIMD를 이용해서 속도향상 시킬 수 있다.

#include <stdio.h>
#include <emmintrin.h>
#include <time.h>
void for_memcpy(char* dest, char* source, size_t count);
int check_memcpy(char* dest, char* source, size_t count);
void simd_memcpy(char* dest, char* source, size_t count);
const size_t TEST_SIZE = 500000000;
int main()
{
	char* original = (char*)malloc(TEST_SIZE);
	char* temp= (char*)malloc(TEST_SIZE);
	for (size_t i = 0; i < TEST_SIZE; i++)
		original[i] = i;
	clock_t start = clock();
	for_memcpy(temp, original, TEST_SIZE);
	clock_t end = clock();
	printf("SISD : %.3fs\n", (float)(end - start)/CLOCKS_PER_SEC);
	check_memcpy(temp, original, TEST_SIZE);
	for (size_t i = 0; i < TEST_SIZE; i++)
		temp[i] = 0;
	start = clock();
	simd_memcpy(temp, original, TEST_SIZE);
	end = clock();
	printf("SIMD : %.3fs\n", (float)(end - start)/CLOCKS_PER_SEC);
	check_memcpy(temp, original, TEST_SIZE);
	free(original);
	free(temp);
}

void for_memcpy(char* dest, char* source, size_t count)
{
	count/=8;
	for (size_t i = 0; i < count; i++)
		*((long long int*)dest+i) = *((long long int*)source+i);
}

void simd_memcpy(char* dest, char* source, size_t count)
{
	count /= 0x10;
	for (size_t i = 0; i < count; i++)
	{
		__m128i temp = _mm_loadu_si128((__m128i*)source+i);
		_mm_storeu_si128((__m128i*)dest + i, temp);
	}
}
int check_memcpy(char* dest, char* source, size_t count)
{
	for (size_t i = 0; i < count; i++)
	{
		if (source[i] != dest[i])
			return 0;
	}
	puts("OK!");
	return 0;
}

simd_memcpy 함수를 보면 __m128i 라는 (union)자료형이 등장하는데, 이는 128bit 자료형이다. 쉽게 말하면 배열을 그냥 옮겨서 온 것이라고 생각하면 편하다.

우리는 __mm_loadu_si128 함수(함수이지만 내용물은 어셈블리 한줄)를 이용해서 정렬되지 않은(loadu 에서 u가 unaligned) 메모리의 128bit 값을 가져와서 temp에 저장한다. 그리고 그 후 _mm_sotreu_si128 함수를 통해서 복사할 곳에 temp를 dest에 복사한다.

결과는 아래와 같다.

약 2.37배 정도 SIMD 를 사용한 것이 속도가 더 빨랐다. 이론상으로는 한번에 64bit크기를 복사하는 for_memcpy보다 2배정도 빨라야 하는데, 더 빠르게 나왔다. 상당히 신기하다.

Intrinsic 이란?

SSE 명령어들은 기본적으로 어셈블리이기 때문에 프로그래머가 쉽게 쓸 수 있게 패킹해 놓은 함수이다. inline으로 바로 들어가서 추가적인 오버해드가 없다.

이 intrinsic들은 https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=load&expand=3910,3416&techs=SSE,SSE2,SSE3 에서 확인 가능하다.

이 외에도 다양한 연산자(곱셈, 덧셈, 빼기, 나누기) 등등 이 있으니 위 사이트에서 찾아서 원하는 연산자를 사용하면 될 것 같다. 아쉬운 점은 AVX 명령어까지도 int/int 같은 연산은 불가능하다. double/double, float/float 만 가능하며 직접 우리가 쉬프트명령을 통해서 구현해야 하는 듯 하다.

결론

우리는 작업의 병렬화가 가능할 때 SSE 명령어를 통해서 속도향상을 꾀할 수 있다는 것을 알았다. 앞으로 이를 이용하여 최적화를 하면 좋을 것 같다. 단점이라 하면 SIMD 는 SSE~SSE4.X + AVX2 까지 파편화가 심하기 때문에 실제 프로젝트에서는 cpu id를 얻어와서 해당 명령어가 지원되는지 하나하나 검사하는 과정이 필요하다. (일례로 AVX는 인텔 3세대인 샌디브릿지부터 지원된다)

다음 포스팅은 cash line과 메모리 정렬에 관해서 다룰 것 같다.