Practical SIMD Programming
Introduction
현대 CPUs들은 점점 더 최상의 성능을 얻기 위해 병렬성에 의존한다. 가장 잘 알려진 형태는 task parallelism인데, 그것은 여러개의 코어들, 하이퍼쓰레딩, 그리고 multitasking operating system을 지원하는 dedicated instructions에 의해서 하드웨어 수준으로 지원된다. instruction level parallelism이라고 알려진 병렬성은 덜 알려져있다 : 여러개의 명령어들을 동시에 실행하는 CPU의 능력이다. 즉, 같은 사이클에서, 한 단일 쓰레드에서 이다. 오리지널 펜티엄 같은 오래된 CPUs들은 high-latency floating point operations에 대해 병렬로 두 개의 파이프라인들을 활용하여 명령어들을 수행하기 위해 이것을 사용했다. 일반적으로, 이것은 프로그래머에게도 분명하게 발생한다. 최근의 CPUs들은 instruction level parallelism의 급격하게 다른 형태를 사용한다. 이러한 CPUs들은 vector operations의 다용도의 집합을 이용한다 : 4개 또는 8개의 입력에 대해 작동하는 명령어들, 4개 또는 8개의 결과를 만들어내면서, 하나의 cycle안에. 이것은 SIMD로 알려져있다: Single Instruction, Multiple Data. 이 compute potential를 이용하기 위해, 우리는 더 이상 컴파일러에게 의존할 수 없다. 광범위한 데이터 병렬성을 보여주는 알고리즘들은 explicit SIMD programming으로부터 가장 이득을 얻는다. 4배 ~ 8배 그리고 그 이상으로 잠재적 성능 향상이 있다. 이 문서는 C++과 C#에서 SIMD programming에 대한 실용적인 입문을 제공한다.
SIMD Concepts
CPU는 연산할 데이터를 저장할 registers를 사용한다. 일반적인 레지스터는 32 또는 64bits를 저장하고 단일의 scalar value를 보유한다. CPU 명령어들은 일반적으로 두 개의 operands에 대해서 작동한다. 다음의 코드를 고려해라:
vec3 velocity = GetPlayerSpeed(); float length = velocity.Lenght();
vector의 길이를 계산하는 line은 많은 scalar operations을 요구한다:
x2 = velocity.x * velocity.x y2 = velocity.y * velocity.y z2 = velocity.z * velocity.z sum = x2 + y2 sum = sum + z2 length = sqrtf(sum)
Vector registers는 4개 (SSE) 또는 8개 (AVX) scalars를 저장한다. 이것은 C# 또는 C++ vector가 assembler level의 vector로 남아있게 된다는 것을 의미한다 : 세 개의 registers에 세 개의 별개의 값들을 저장하기 보다, 우리는 single vector register에 4개의 값들 (x, y, z 그리고 dummy value)를 저장한다. 그리고 x, y, 그리고 z를 별개로 제곱하는 것이 아니라, 우리는 세 개의 값을 (뿐만 아니라 dummy value도) 곱하는 단일의 SIMD 명령어를 사용한다.
이 간단한 예제는 SIMD code를 다룰 때 우리가 다룰 필요가 있는 많은 문제들을 보여준다:
- 세 개의 컴포넌트를 가진 벡터에 대해 연산을 할 때, 우리는 vector processor의 완전한 연산 잠재성을 사용하지 않는다 : 우리는 SIMD register에서 'slots'의 25% (SSE) 또는 62.5% (AVX)를 낭비한다.
- vector register에서 세 개의 scalars를 저장하는 것은 무료가 아니다 : 그 비용은 우리가 나중에 논의할 많은 요소들에 의존한다. 이것은 계산에 어떤 오버헤드를 더한다.
- 마지막 줄의 square root는 여전히 단일 값에 대해 수행된다. 그래서, 비록 이것은 가장 비싼 line일지라도, 그것은 vector hardware로부터 이익을 얻지 못하고 우리의 이득을 제한한다.
이러한 걱정들을 완화하는 믿을만한 방법이 있다. 우리의 어플리케잇녀이 실제로 4명의 플레이어가 있는 게임이라고 가정하자:
for (int i = 0; i < 4; ++i) { vec3 velocity = GetPlayerSpeed(); float length = velocity.Length(); }
이 시나리오에서, 우리는 동시에 4개의 벡터들에 대해 연산할 수 있다:
x4 = GetPlayerXSpeeds(); y4 = GetPlayerYSpeeds(); z4 = GetPlayerZSpeeds(); x4squared = x4 * x4; y4squared = y4 * y4; z4squared = z4 * z4; sum4 = x4sqaured + y4squared; sum4 = sum4 + z4squared; length4 = sqrtf4(sum4);
우리가 완전히 SIMD vectors로부터 C++/C# vector 개념을 분리시킨다는 것을 주목해라: 우리는 간단히 병렬로 원래의 스칼라 함수를 4번 실행하기 위해 SIMD vectors를 사용한다. 모든 라인은 이제 100% 효율성으로 SIMD instruction을 사용한다 (당연하게도, 우리는 AVX에 대해 8명의 플레이어들이 필요하다), 그리고 심지어 그 square root는 이제 4개의 숫자에 대해 계산된다.
여기에서 주의해야 할 한 가지 중요한 것이 있다: 처음 세 개의 lines을 효율적으로 만들기 위해, player speeds는 이미 `SIMD_friendly` format으로 저장되어야만 한다, 즉 : xxxx, yyyy, zzzz 으로. 이렇게 구성된 데이터는 직접적으로 vector register에 복사되어질 수 있다.
우리는 그 컴파일러가 우리를 위해 이것을 자동으로 하도록 기대할 수 없다. 효율적은 SIMD code는 효율적인 데이터 layout을 요구한다; 즉 이것은 수동으로 되어야만 한다.
Data parallelism
4명의 플레이어가 있는 예제는 AVX machines에서 연산 잠재력의 50%를 낭비할 것이다. 명백히, 우리는 좀 더 많은 일이 필요하다. 효율적인 SIMD code는 많은 data parallelism을 요구하는데, 거기에서, operations의 한 sequence가 많은 inputs들에 대해 실행된다. 100% 효율성에 도달하는 것은 그 input array size가 4 또는 8의 배수일 것을 요구한다. 그러나 어떤 큰 input array size에 대해, 우리는 이 최적의 것에 매우 가깝게 되고, AVX 성능은 간단히 SSE 성능의 두배가 된다.
data-parallel 알고리즘에 대해, SIMD register에 있는 스칼라들 각각은 한 'thread'에 대한 데이터를 보유한다. 우리는 register에 있는 slots들을 lanes라고 부른다. 이 입력 데이터는 stream이라고 불려진다.
Into the Mud
만약 너가 C++ 프로그래머라면, 너는 아마도 기본 형들에 대해 친숙하다: char, short, int, float, 등. 이러한 각각은 특정한 크기를 갖는다 : char는 8bits, short는 16, int와 float 32. Bits은 그냥 bits이고, 그러므로 float와 int 사이의 차이는 해석에 있다. 이것은 우리가 어떤
못된 것들을 하게 한다:
int a; float& b = (float&)a;
이것은 한 정수와, a를 가리키는 한 float reference를 만든다. 변수 a와 b가 이제 같은 메모리 위치를 차지하기 때문에, a를 바꾸는 것은 b를 바꾸고, 역으로도 된다. 이것을 얻는 대안은 union을 사용하는 것이다:
union { int a; float b; };
또 다시, a와 b는 같은 메모리 위치에 있다. 여기에서 또 다른 예시가 있다:
union { unsigned int a4; unsigned char a[4]; };
이 번에, 네 개의 chars의 작은 배열은 32-bit integer 값 a4에 중복된다. 우리는 이제 배열 a[4]를 통해 a4에 있는 개별 bytes를 접근할 수 있다. a4가 이제 기본적으로 4개의 1-byte 'lanes'를 가지고 있다는 것을 주목해라. 이것은 어느정도 우리가 SIMD로 얻는 것과 유사하다. 우리는 심지어 32개의 1-bit value로서 a4를 사용할 수 있고, 그리고 그것은 32개의 boolean values를 저장하는 효율적인 방법이다.
SSE register는 128bit 크기이고, 만약 4개의 float를 저장하도록 사용한다면 __m128로 이름 지어졌고, ints에 대해서는 __m128i로 이름지어져있다. 편의성을 위해, 우리는 __m128를 'quadfloat'로, __m128i를 'quadint'로 발음할 것이다. 그 AVX versions은 __m256 ('octfloat')이고 __m256i ('octint')이다. SIMD types를 사용할 수 있기 위해서, 우리는 몇 가지 헤더들을 인클루드 할 필요가 있다:
#include "nmmintrin.h" // for SSE 4.2 #include "immintrin.h" // for AVX
__m128 변수는 4개의 floats를 포함하고, 그래서 우리는 또 다시 union trick를 사용할 수 있다:
union { __m128 a4; float a[4]; };
이제 우리는 편리하게 __m128 vector에 있는 개별 floats를 접근할 수 있다.
우리는 또한 quadfloat를 직접 생성할 수 있다:
__m128 a4 = _mm_set_ps(4.f, 4.1f, 4.2f, 4.3f); __m128 b4 = _mm_set_ps(1.f, 1.f, 1.f, 1.f);
그것들을 함께 더하기 위해서, 우리는 _mm_add_ps를 사용한다:
__m128 sum4 = _mm_add_ps(a4, b4);
그 __mm_set_ps와 _mm_add_ps 키워드들은 intrinsic이라고 불려진다. SSE와 AVX intrinsics은 모두 단일 assembler instruction으로 컴파일 된다; 이러한 것들을 사용하는 것은 우리가 필수적으로 우리의 프로그램에서 어셈블러 코드를 직접 작성하는 것을 의미한다. 가상으로 무든 스칼라 연산에 대한 intrinsic이 있다:
_mm_add_ps(a4, b4); _mm_sub_ps(a4, b4); _mm_mul_ps(a4, b4); _mm_div_ps(a4, b4); _mm_sqrt_ps(a4); _mm_rcp_ps(a4); // 역수
AVX에 대해, 우리는 비슷한 intrinsics를 사용한다: 간단히 _mm 대신에 _mm256을 앞에 붙인다. 그래서 _mm256_add_ps(a4, b4) 등이 된다.
SSE와 AVX 명령어들에 대한 완전한 overview는 여기에서 찾을 수 있다:
https://software.intel.com/sites/landingpage/IntrinsicsGuide/
너는 안전하게 2000년도 이후에 생상된 어떤 CPU가 4.2까지의 SSE를 지원한다는 것을 가정할 수 있다. AVX와 특히 AVX2는 좀 더 최근의 기술이다; 지원하는 프로세서들에 대한 목록을 위해 위키피디아를 체크해라:
https://en.wikipedia.org/wiki/Advanced_Vector_Extensions
SIMD in C#
이전 섹션은 C++의 사용을 가정했었다. 운 좋게도, SIMD는 C#에서도 또한 이용가능하다. 비록 그 구현이 훌륭하지 않을지라도.
SIMD 지원은 System.Numerics.Vectors package에서 찾아질 수 있다. 처음에, 너는 Nuget Package Manager를 통해 어셈블리의 최신 버전 (글 쓰는 시점에는 4.3.0)를 추가할 필요가 있다.
여기에 몇 가지 실험을 위해 우리가 사용할 작은 C# program이 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 | using System.Numerics; namespace test { class P { static void Main(string[] args) { var lanes = Vector<int>.Count; int[] a = { 1, 2, 3, 4, 5, 6, 7, 8 }; int[] b = { 1, 1, 1, 1, 1, 1, 1, 1 }; int[] c = new int[a.Length]; for( int i = 0; i < a.Length; i += lanes ) { var a8 = new Vector<int>(a, i); var b8 = new Vector<int>(b, i); (a8 + b8).CopyTo(c, i); }}}} |
Main 함수에서 첫 번째 line은 너의 하드웨어에 의해 지원되는 lanes의 개수를 결정한다. C#은 너가 SSE 또는 AVX를 선택하도록 하지 않는다. 대신에 하드뒈어 독립적으로 설계되었다. Lanes은 4 또는 8일 수 있고, 미래 하드웨어에는 아마도 16일 수 있다. 만약 우리가 line 5에 breakpoint를 넣는다면, lanes은 최근의 CPU에서 4로 나올 것이다. 이것을 해겨랗기 위해, Project -> Properties로 가서, Build tab를 선택하고, `Prefer 32-bit`를 비활성화해라. 이제 lanes은 AVX2-capable processor에서 8이 될 것이다.
8개의 lanes으로 Vector<int>는 octint이다. 그 loop에서 octint a8은 배열 a의 8개의 값으로 채워지고, b8은 배열 b의 8개의 값으로 채워진다. 그것들은 함께 더해지고, 그 결과는 배열 c에 복사되고, 그 배열은 최종 결과를 가지게 된다.
질문 : C# compiler는 실제로 SIMD code를 만들어내는가? 이것을 결정하기 위해서, 우리는 깊게 파고들 필요가 있다.
