효율을 위해 작은 차원의 N 개의 벡터 (X, Y, Z라고 가정 해 봅시다)를 어떻게 저장해야하는지 궁금합니다.N 개의 벡터를위한 메모리 레이아웃
캐시 지역에 대한 이유 때문에 다른 [N] [3] (행 주요) 다음에 벡터를 패킹하면 레이아웃 [3] [N]보다 더 나은 결과를 얻을 것이라고 기대했습니다 (차원 X, Y 그런 다음 Z가 연속적으로 배치됩니다.) OpenMP를 사용하여 vectory 작업을 수행 할 때.
그러나 각 벡터에 3x3 매트릭스를 곱하고 인텔 MKL BLAS를 사용하면 레이아웃 [3] [N]이 두 배 빠름을 발견했습니다.
캐시 지역은 비 스트라이드 데이터에 대해 SSE 명령어가 작동한다는 점에서 카운터 밸런스가 맞춰져 있다고 생각합니다. 이것은 사람들이 (예를 들어 컴퓨터 그래픽에서) 어떻게 벡터를 저장하고 다른 장단점이 있는지 궁금해하게합니다.
사용되는 데이터 레이아웃에는 두 가지가 있습니다. 구조 배열 (AoS)과 배열 구조 (SoA)입니다.
의 AoS :
struct
{
float x;
float y;
float z;
} points[N];
SOA :
× 3 행렬M와 AOS의 경우에서의 각 점을 승산하기 위해
struct
{
float x[N];
float y[N];
float z[N];
} points;
는 루프 본체 보이는 같은
r[i].x = M[0][0]*points[i].x +
M[0][1]*points[i].y +
M[0][2]*points[i].z;
// ditto for r[i].y and r[i].z
SSE는 한 번에 4 개의 부동 소수점을 곱할 수 있으며 (AVX는 8 개의 부동 소수점을 곱할 수 있음) 문제는 벡터 레지스터에 3 개의 부동을로드하는 것이 매우 비효율적 인 동작이라는 것입니다. float 필드를 추가하여 구조체를 패딩 할 수 있지만 두 벡터 피연산자의 4 번째 부동 소수점이 사용되지 않거나 쓸모없는 정보를 포함하므로 연산 능력의 1/4이 손실됩니다. 포인트를 벡터화 할 수도 없습니다 (예 : points[i].x에서 points[i+3].x으로 즉시로드하려면 수집로드가 필요하므로 x86에서는 아직 지원되지 않습니다 (AVX2 가능 CPU가 사용 가능 해지면 변경 될 수 있지만).
r.x[i] = M[0][0]*points.x[i] +
M[0][1]*points.y[i] +
M[0][2]*points.z[i];
// ditto for r.y[i] and r.z[i]
그것은 기본적으로 동일하게 보이지만, 매우 중요한 차이가있다 : SOA의 경우
는 내부 루프이다. 이제 컴파일러는 벡터 명령을 사용하여 한 번에 4 포인트 (또는 심지어 AVX로 8 포인트)를 처리 할 수 있습니다. 예 : 그것은 루프를 풀다 다음과 같은 벡터 동등한로 변환 할 수 있습니다 세 가지 벡터로드, 세 스칼라 - 벡터 곱셈, 세 가지 벡터 추가하고, 여기에서 벡터 저장이 있습니다<r.x[i], r.x[i+1], r.x[i+2], r.x[i+3]> =
M[0][0]*<x[i], x[i+1], x[i+2], x[i+3]> +
M[0][1]*<y[i], y[i+1], y[i+2], y[i+3]> +
M[0][2]*<z[i], z[i+1], z[i+2], z[i+3]>
. 이들 모두는 SSE의 벡터 기능을 100 % 활용합니다. 유일한 문제는 점의 수가 4로 나눌 수없는 경우이지만 배열을 쉽게 채울 수 있거나 컴파일러가 나머지 반복을 직렬로 수행하기 위해 스칼라 코드를 생성 할 수있는 경우입니다. 어느 쪽이든, 많은 포인트를 가지고 있다면, 각 포인트에서 하드웨어를 지속적으로 사용하지 않는 것보다 나머지 1 ~ 3 포인트에 약간의 성능 만 잃는 것이 훨씬 더 유리합니다.
반면에 자주 (x,y,z) 랜덤 포인트의 튜플에 액세스해야하는 경우 SoA 구현은 3 가지 캐시 라인 읽기 (데이터가 캐시에 맞지 않는 경우)를 초래하지만 AoS 구현에서는 하나의 캐시 라인 읽기 또는 2 개 (패딩 1은 2 개의로드가 필요한 경우를 회피 할 수 있음). 따라서 해답은 데이터 구조가 어떤 종류의 연산이 알고리즘을 지배하는지에 따라 달라집니다.