SSE를 이용한 4샘플 무분기 치환 for SW Occlusion Culling

게시일: megayuchi님이 작성

요 근래에 Voxel 오브젝트 컬링을 위해 SW Occlusion Culling을 사용한다고 포스팅 했었다.
SW Occlusion Culling이라봐야 별거 없다.
잠깐 그 내용을 상기해보면…

  1. CPU측에서 사용할 수 있는 Z-Buffer(그냥 32bits float타입의 메모리 버퍼)를 잡는다.
  2. Voxel오브젝트의 Min박스의 z값을 그린다. z값이 기존 값보다 작거나 같을 경우만 덮어쓴다.
  3. 이후에 테스트할 다른 Voxel오브젝트의 Max 박스의 z값을 z-buffer의 값과 비교한다. 기존값보다 z값이 작으면 바로 리턴한다. 이 오브젝트는 화면에 보이는 것으로 판정한다. z테스트에 하나도 통과 못하면 그려지지 않는 오브젝트이다.

이렇다. 꽤 삽질을 해서 구현했고 지금은 아주 잘 돌아간다.
문제는 속도.

지금은 512 x 512 z-buffer를 사용하고 있는데 느리지는 않다. 하지만 테스트할 오브젝트 개수가 많아지고 정밀도를 위해 z-buffer 해상도를 높여야한다면 성능 문제가 생길거라고 예상한다.

이 문제가 계속 신경 쓰여서 다음 진도를 나갈 수가 없었다.
z-test를 멀티스레드로 해볼까도 생각했는데 삼각형을 그릴때 겹치는 구간이 있으면 스레드간 동기화를 해줘야하고 Thread Pool을 사용한다고 해도 스레드가 wait하고 resume하는 과정에서 상당한 딜레이가 있을 것이다. 멀티 스레드를 사용하는 방법은 일단 제외.

SSE의 SIMD기능을 사용해서 싱글 스레드로 4픽셀이나 8픽셀씩 처리하는 방법을 생각해봤다.
음 이건 가능할것 같다.

다만 문제는..내 지금껏 경험으로 볼때 별로 빠르지 않거나 심지어 느릴수도 있다는 것이다.

먼저 C코드를 보자.
삼각형-정확히는 Voxel오브젝트의 Min박스,또는 Max박스를 이루는 삼각형들-을 그릴때 스캔라인을 따라 한 줄씩 그리게 된다.
스캔라인의 시작,끝 점이 주어지고 시작점에서의 z값과 한 픽셀이 옆으로 이동하면서 증가하는 z값의 변화량이 주어진다.


inline UINT DrawLineSingleSample(int start_x, int end_x, float* pDest, float z, float z_pitch)
{
UINT	PixelCount = 0;

for (int x = start_x; x <= end_x; x++)
{
if (z <= *pDest)
{
*pDest = z;
PixelCount++;
}
z += z_pitch;
pDest++;
}
return PixelCount;
}

아주 심플하다. if문이 느릴것 같지만 생각보다 훨씬 빠르다.

이제 이 코드를 SSE의 cmpps명령을 사용해서 한번에 4샘플씩 비교 치환하는 코드로 바꿀 생각이다.
cmpss,cmpps를 사용하면 dest레지스터에 0xffffffff또는 0을 세팅해주는데 이걸 xor마스크로 사용해서 치환할 값으로 덮을지, 원래 값으로 덮을지 결정하는 것이다.이렇게 하면 좋은점은…

  1. 분기가 없다.
  2. 동시에 4픽셀 처리가 가능하다.

뭐 좋다. 4픽셀을 동시에 처리하는거야 좋지. 문제는 다음과 같다.

  • if문(분기)을 사용하는 경우 z값 비교후 같거나 작으면 z값을 써넣기 하지 않고 바로 리턴한다.
  • 무분기 치환을 할 경우 원래의 같거나 작을때 원래의 z값이 보존은 되지만, 원래의 z값을 써넣기 하는 것이지 써넣기 안하고 바로 건너뛰는건 아니다. 그러니까 4픽셀에 대해서 동시에 read하고 4픽셀을 동시에 write하는 것이다.

즉 분기를 하는 경우는 read하고 wrtie하지 않을때도 있지만 무분기 치환 기법을 사용하는 경우 read후에는 항상 write를 할 수 밖에 없다. 여기서 옛날 기억이 떠오른다.  xor가지고 문자열 치환 코드 만들때 이렇게 작업해서 C-if구문보다 느린 결과를 얻어서 절망했던 기억이 있다.

당시 내 생각엔 어차피 read를 시도했으니 해당 메모리는 이미 cache에 맵핑되어 있고 write할때도 1클럭만에 끝낼줄 알았다. 근데 테스트 해보니 read만 하고 빠져나가는거랑 read한담에 write를 하는거랑 성능 차이가 크더란 말이다.
분기에서 오는(분기예측 실패까지도 감안하여) 성능 저하보다 write를 항상 하는데서 오는 성능 저하가 훨씬 컸다.

이번에 작업하려는 것도 4샘플을 동시에 처리하는데선 장점이 있지만 4샘플에 대한 비교작업 후에 xor, 그리고 치환된값, 혹은 원래값 4샘플을 동시에 써넣는 부하가 있다.
그 때 그 xor무분기 치환문 이후로 이런 식의 코드가 분기문 코드보다 빨랐던 기억이 없다. 그래서 엄청 망설였다…

하지만 역시 짜놓고 절망하는 편이 좋겠지.

그래서 만들어 봤다. 난 어셈으로 직접짜는걸 좋아하지만 여러가지 이유로 이번엔 Compiler Intrinsic을 사용했다. 참고로 어셈으로 짜게되면 x86빌드는 인라인 어셈을 써도 되지만 x64빌드는 매크로 어셈으로 짜야해서 좀 귀찮다.

우선 SSE의 PS계열 명령을 사용해서 4샘플씩 동시에 처리하는 코드이다.
이 코드가 핵심이다. Width = end_x – start_x + 1로 주어진다.

inline unsigned int CompareAndSetLine4Samples(float* p_out_z,float z,float z_pitch,float* pDest,UINT Width)
{
unsigned int Count = 0;

__m128i zero = _mm_setzero_si128();
__m128 xmm_pitch = _mm_set_ps(z_pitch+z_pitch+z_pitch,z_pitch+z_pitch,z_pitch,0);

for (UINT i=0; i&lt;Width; i++)
{
__m128 xmm_src = _mm_set1_ps(z);
xmm_src = _mm_add_ps(xmm_src,xmm_pitch);

__m128 xmm_dest = _mm_load_ps(pDest);
__m128 xor_mask = _mm_xor_ps(xmm_src, xmm_dest);
__m128 and_mask = _mm_cmp_ps(xmm_src, xmm_dest, 2);

xor_mask = _mm_and_ps(xor_mask, and_mask);
xmm_dest = _mm_xor_ps(xmm_dest, xor_mask);

__m128i cmp_result = _mm_sub_epi32(zero, _mm_castps_si128(and_mask));	// 0 - (-1) or 0 - 0
__m128i sum = _mm_hadd_epi32(cmp_result, cmp_result);

Count += sum.m128i_i32[0] + sum.m128i_i32[1];

_mm_store_ps(pDest, xmm_dest);
pDest += 4;
z += (xmm_pitch.m128_f32[3] + z_pitch);
}
*p_out_z = z;
return Count;
}

그런데 이 코드만으론 부족하다 왜냐하면 SSE명령어들은 상당 수 16bytes align을 요구한다.
어셈으로 작성할 경우 movups같은걸로 align되지 않은 메모리도 억세스할 수 있지만 성능이 떨어진다. 따라서 CRT의 memcpy()을 본받아 메모리 블럭에서 align된 어드레스가 나올때까지 1샘플씩 처리하고 align된 어드레스부터 4샘플씩 처리하기로 한다. 물론 짜투리 영역이 align되지 않을 경우도 있고 이 경우도 마찬가지로 1샘플씩 처리한다.

1샘플,그러니까 4바이트씩 처리할 무분기 치환 SSE코드를 한벌 더 만든다.

inline unsigned int CompareAndSetLineSingleSample(float* p_out_z,float z,float z_pitch,float* pDest,UINT Width)
{
unsigned int Count = 0;

__m128i zero = _mm_setzero_si128();

for (UINT i=0; i<Width; i++)
{
__m128 xmm_src = _mm_set1_ps(z);
__m128 xmm_dest = _mm_load_ss(pDest);
__m128 xor_mask = _mm_xor_ps(xmm_src, xmm_dest);
__m128 and_mask = _mm_cmp_ps(xmm_src, xmm_dest, 2);

xor_mask = _mm_and_ps(xor_mask, and_mask);
xmm_dest = _mm_xor_ps(xmm_dest, xor_mask);

__m128i cmp_result = _mm_sub_epi32(zero, _mm_castps_si128(and_mask));	// 0 - (-1) or 0 - 0

Count += cmp_result.m128i_i32[0];

_mm_store_ss(pDest, xmm_dest);
pDest++;
z += z_pitch;
}
*p_out_z = z;
return Count;
}

그리고 얘네들을 사용해서 스캔라인을 따라 삼각형의 한 줄을 그려낼 함수이다. 메모리의 어드레스가 align되어있는지를 판별해서 4픽셀씩 처리하거나 1픽셀씩 처리한다. 저 맨 위의 C코드와 같은 일을 한다.

inline UINT DrawLine4SamplesSSE3(int start_x, int end_x, float* pDest, float z, float z_pitch)
{
UINT	width = end_x - start_x + 1;
UINT	PixelCount = 0;

while (width)
{
if (Is16BytesAligned((DWORD_PTR)pDest) && width >= 4)
{
UINT xword_count = width / 4;

PixelCount += CompareAndSetLine4Samples(&z, z, z_pitch, pDest, xword_count);
pDest += (xword_count * 4);
width -= (xword_count * 4);
}
else
{
DWORD_PTR	next_aligned_addr = ((DWORD_PTR)pDest + 16) & (~15);

UINT	unaligned_size = (UINT)(next_aligned_addr - (DWORD_PTR)pDest);
UINT dword_count = unaligned_size / 4;
if (dword_count > width)
dword_count = width;

PixelCount += CompareAndSetLineSingleSample(&z, z, z_pitch, pDest, dword_count);
pDest += dword_count;
width -= dword_count;

}
}

return PixelCount;
}

[성능비교]
일단 잘 작동한다. 물론 잘 작동할때까지 이런저런 삽질을 했다. 대단치 않으니 넘어간다.
이렇게 복잡하게 짰는데 저 위의 간단한 C코드보다 빠를까?

테스트를 해보자.
1024 x 1024 사이즈의 32bit float타입의 버퍼를 만든다. 0부터 1사이의 float값을 무작위로 생성해서 모든 픽셀에 채워넣는다.

초기 z값은 0, z증가분은 1/1024 로 한줄씩 1024픽셀을 비교하고 치환한다. 일반적으로 삼각형을 그릴때 이렇게 전체를 다 덮는 경우는 별로 없지만 테스트니까 1024 x 1024 모든 픽셀을 다 억세스하도록 이렇게 테스트 한다.

[테스트 결과]
테스트 머신 : i7 2600K 4.2GHz
테스트 단위 : clocks

[debug build]
SSE 4샘플 무분기 치환 : 15523832 clocks
분기 1샘플 치환 : 18105338 clocks

[release build]
SSE 4샘플 무분기 치환 : 2727668 clocks
분기 1샘플 치환 : 10201081 clocks

기쁘다! 빠르다! 무려 3.7배나 빠르다! 4샘플 동시 처리라는게 의미가 있다.
잠깐. 여기서 한 가지 더 생각해보자. 그럼 무분기 치환은 의미가 있었나? 난 무분기 치환을 하려고 한게 아니고 SIMD특성상 4샘플 동시 비교 후에 jmp할 방법이 없으니 할 수 없이 무분기 치환을 한거라고.
그럼 1샘플씩 처리하면서 if를 사용하지 않고 무분기 치환을 하는 경우는 if문을 사용했을때와 비교해서 빠를까? 느릴까?

그래서 비교해봤다. 위에 적어놓은 1샘플씩 처리하는 SSE코드만을 사용한 경우이다.

[relesae build]
SSE 1샘플 무분기 치환 : 9577121 clocks
분기 1샘플 치환 : 9930463 clocks

아주 근소하게..무분기 치환쪽이 빠르다. 사실 여러번 테스트 해보면 항상 근소한 차이가 나는건 맞지만 10%정도 확률로 분기 치환쪽이 빠르기도 하다.

[결론]
SIMD기능을 사용한 n샘플 처리는 쓸모가 있다.
무분기 치환이 빠를 수 있지만 항상 그렇진 않다.
분기문은 느리지 않다.

답글 남기기

댓글을 게시하려면 다음의 방법 중 하나를 사용하여 로그인 하세요:

Gravatar
WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. ( 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. ( 로그아웃 /  변경 )

취소

%s에 연결하는 중