매트릭스의 비선형 메모리 레이아웃을 시도하여 캐시 활용도를 높일 수 있습니다. 4x4 32 비트 플로트 타일을 사용하면 각 캐시 라인에 대한 단일 액세스만으로 전치를 수행 할 수 있습니다. 플러스 보너스 타일 transposes로 _MM_TRANSPOSE4_PS 쉽게 할 수 있습니다.
매우 큰 매트릭스를 조 변경하는 것은 여전히 매우 메모리 집약적 인 작업입니다. 여전히 대역폭은 많이 제한되어 있지만 적어도 캐시 워드로드는 거의 최적입니다. 성능이 여전히 최적화 될 수 있는지 여부는 알 수 없습니다. 필자의 테스트에 따르면 몇 년 전의 랩탑은 약 300ms 동안 16k * 16k (1G 메모리)를 옮겨 다니는 것으로 나타났습니다.
_mm_stream_sd도 사용하려고했지만 실제로 어떤 이유로 성능이 저하되었습니다. 비 실제 메모리가 _mm_stream_ps로 성능이 떨어지는 이유에 대해 실제적인 추측을하기에는 충분히 이해하지 못합니다. 가능한 이유는 캐시 라인이 이미 쓰기 작업을 위해 L1 캐시에 준비되어 있다는 것입니다.
그러나 실제로 비선형 매트릭스의 중요한 부분은 전치가 완전하고 단순한 승법을 타일 친숙한 순서로 실행하지 않을 가능성이 있습니다. 그러나 알고리즘에서 캐시 관리에 대한 지식을 향상시키기 위해 사용하는 코드 만 옮겨 놓을 수 있습니다.
프리 페치가 메모리 대역폭 사용을 향상시키는 지 아직 테스트하지 않았습니다. 현재 코드는 사이클 당 약 0.5 명령 (좋은 CPU 친숙한 코드는이 CPU에서주기 당 약 2 개씩 실행 됨)에서 실행되므로 프리 페치 명령어에 많은 여유 시간이 생겨 런타임시 프리 페칭 타이밍을 최적화하는 데 상당히 복잡한 계산이 가능합니다.
내 트랜스 포즈 벤치 마크 테스트의 예제 코드는 다음과 같습니다.
#define MATSIZE 16384
#define align(val, a) (val + (a - val % a))
#define tilewidth 4
typedef int matrix[align(MATSIZE,tilewidth)*MATSIZE] __attribute__((aligned(64)));
float &index(matrix m, unsigned i, unsigned j)
{
/* tiled address calculation */
/* single cache line is used for 4x4 sub matrices (64 bytes = 4*4*sizeof(int) */
/* tiles are arranged linearly from top to bottom */
/*
* eg: 16x16 matrix tile positions:
* t1 t5 t9 t13
* t2 t6 t10 t14
* t3 t7 t11 t15
* t4 t8 t12 t16
*/
const unsigned tilestride = tilewidth * MATSIZE;
const unsigned comp0 = i % tilewidth; /* i inside tile is least significant part */
const unsigned comp1 = j * tilewidth; /* next part is j multiplied by tile width */
const unsigned comp2 = i/tilewidth * tilestride;
const unsigned add = comp0 + comp1 + comp2;
return m[add];
}
/* Get start of tile reference */
float &tile(matrix m, unsigned i, unsigned j)
{
const unsigned tilestride = tilewidth * MATSIZE;
const unsigned comp1 = j * tilewidth; /* next part is j multiplied by tile width */
const unsigned comp2 = i/tilewidth * tilestride;
return m[comp1 + comp2];
}
template<bool diagonal>
static void doswap(matrix mat, unsigned i, unsigned j)
{
/* special path to swap whole tile at once */
union {
float *fs;
__m128 *mm;
} src, dst;
src.fs = &tile(mat, i, j);
dst.fs = &tile(mat, j, i);
if (!diagonal) {
__m128 srcrow0 = src.mm[0];
__m128 srcrow1 = src.mm[1];
__m128 srcrow2 = src.mm[2];
__m128 srcrow3 = src.mm[3];
__m128 dstrow0 = dst.mm[0];
__m128 dstrow1 = dst.mm[1];
__m128 dstrow2 = dst.mm[2];
__m128 dstrow3 = dst.mm[3];
_MM_TRANSPOSE4_PS(srcrow0, srcrow1, srcrow2, srcrow3);
_MM_TRANSPOSE4_PS(dstrow0, dstrow1, dstrow2, dstrow3);
#if STREAMWRITE == 1
_mm_stream_ps(src.fs + 0, dstrow0);
_mm_stream_ps(src.fs + 4, dstrow1);
_mm_stream_ps(src.fs + 8, dstrow2);
_mm_stream_ps(src.fs + 12, dstrow3);
_mm_stream_ps(dst.fs + 0, srcrow0);
_mm_stream_ps(dst.fs + 4, srcrow1);
_mm_stream_ps(dst.fs + 8, srcrow2);
_mm_stream_ps(dst.fs + 12, srcrow3);
#else
src.mm[0] = dstrow0;
src.mm[1] = dstrow1;
src.mm[2] = dstrow2;
src.mm[3] = dstrow3;
dst.mm[0] = srcrow0;
dst.mm[1] = srcrow1;
dst.mm[2] = srcrow2;
dst.mm[3] = srcrow3;
#endif
} else {
__m128 srcrow0 = src.mm[0];
__m128 srcrow1 = src.mm[1];
__m128 srcrow2 = src.mm[2];
__m128 srcrow3 = src.mm[3];
_MM_TRANSPOSE4_PS(srcrow0, srcrow1, srcrow2, srcrow3);
#if STREAMWRITE == 1
_mm_stream_ps(src.fs + 0, srcrow0);
_mm_stream_ps(src.fs + 4, srcrow1);
_mm_stream_ps(src.fs + 8, srcrow2);
_mm_stream_ps(src.fs + 12, srcrow3);
#else
src.mm[0] = srcrow0;
src.mm[1] = srcrow1;
src.mm[2] = srcrow2;
src.mm[3] = srcrow3;
#endif
}
}
}
static void transpose(matrix mat)
{
const unsigned xstep = 256;
const unsigned ystep = 256;
const unsigned istep = 4;
const unsigned jstep = 4;
unsigned x1, y1, i, j;
/* need to increment x check for y limit to allow unrolled inner loop
* access entries close to diagonal axis
*/
for (x1 = 0; x1 < MATSIZE - xstep + 1 && MATSIZE > xstep && xstep; x1 += xstep)
for (y1 = 0; y1 < std::min(MATSIZE - ystep + 1, x1 + 1); y1 += ystep)
for (i = x1 ; i < x1 + xstep; i += istep) {
for (j = y1 ; j < std::min(y1 + ystep, i); j+= jstep)
{
doswap<false>(mat, i, j);
}
if (i == j && j < (y1 + ystep))
doswap<true>(mat, i, j);
}
for (i = 0 ; i < x1; i += istep) {
for (j = y1 ; j < std::min(MATSIZE - jstep + 1, i); j+= jstep)
{
doswap<false>(mat, i, j);
}
if (i == j)
doswap<true>(mat, i, j);
}
for (i = x1 ; i < MATSIZE - istep + 1; i += istep) {
for (j = y1 ; j < std::min(MATSIZE - jstep + 1, i); j+= jstep)
{
doswap<false>(mat, i, j);
}
if (i == j)
doswap<true>(mat, i, j);
}
x1 = MATSIZE - MATSIZE % istep;
y1 = MATSIZE - MATSIZE % jstep;
for (i = x1 ; i < MATSIZE; i++)
for (j = 0 ; j < std::min((unsigned)MATSIZE, i); j++)
std::swap(index(mat, i, j+0), index(mat, j+0, i));
for (i = 0; i < x1; i++)
for (j = y1 ; j < std::min((unsigned)MATSIZE, i) ; j++)
std::swap(index(mat, i, j+0), index(mat, j+0, i));
}
테스트중인 크기와 숫자를 표시 할 수 있습니까? – Mysticial
관련 캐시 라인이로드되면 캐시에서 캐시를 업데이트해야합니다 (간단한 테스트 케이스에있을 가능성이 큽니다). –
이 테스트의 결과는 캐시의 현재 내용에 따라 다르며 캐시 누락/히트가 결과에 영향을 미칠 수 있습니다. 아마 테스트를 다시 할 가치가 있지만 매번 알려진 캐시 상태에서 시작할 필요가있을 것입니다. 각 테스트가 도움이 될 수 있기 전에 캐시를 무효화하십시오. –