Chapter 34. GPU Flow-Control Idioms
원문 : NVIDIA GPU Gems2 Chapter 34. GPU Flow - Control Idioms
이 글은 개인공부를 위해 공개되어진 아티클을 번역한 글입니다.
잘못된 내용 지적이나 추가 설명등의 댓글을 환영합니다.
번역은 원하는 부분만 원하는 느낌으로 적당히 번역하였습니다.
꼭!! 원문을 보기를 추천합니다.
- 내용추가는 녹색 볼드체로 추가.
- 내가 생각하기에 중요한 부분은 붉은색으로 표시.
흐름 제어(Flow Control)는 프로그래머가 되기 위해 배우는 가장 핵심적인 개념중 하나다.
분기(Branching)와 반복(Looping)은 제한된 방식으로 지원하는 플랫폼의 소프트웨어를 작성하는데 있어
어려움을 줄 수 있는 기본적인 개념들이다.
최신 GPU는 다양한 형태로 vertex와 fragment 프로그램 분기를 지원하지만,
이 GPU들의 고도의 병렬 특성을 어떻게 사용할 것인지를 고려해야 한다.
이 챕터에서는 현재의 GPU들에서 분기의 한계점을 조사하고 GPGPU프로그램에서
반복 및 의사결정을 위한 여러가지 기술들을 설명한다.
34.1 흐름 제어 과제
우선 GPU에서 가장 명백한 형태의 흐름제어에 대해 이야기해 보자.
GPU의 현재 모든 하이레벨 셰이딩 언어는 if-then-else, for, while과 같은
전통적인 C 언어 형식의 명시적 흐름 제어 구조를 지원한다.
하지만 이들의 근본적인 구현은 CPU에서의 구현과는 많이 다르다.
아래 예제코드를 보자.
if(a) b = f(); else b = g(); |
CPU는 쉽게 Boolean a값을 기준으로 분기하여 f()나 g() 함수를 실행할 건지 판별할 수 있다.
이 분기의 성능 특성은 비교적 쉽게 이해할 수 있다.
CPU는 일반적으로 긴 명령 파이프라인을 가지고 있어서 CPU가 정확하게 어떤 특정 분기를
사용할 것인지 정확하게 예측할 수 있는 것이 중요하다.
만약 이 예측이 성공적이라면, 분기는 일반적으로 작은 패털티가 발생한다. (부하가 적게 발생한다.)
만약 분기가 올바르게 예측되지 않았다면 파이프 라인이 플러시 됨(비워짐)으로써 반드시 올바른 대상 주소가
다시 채워져야 함으로 CPU가 여러 사이클 동안 멈출 수 있다.
함수 f()와 g()가 합리적인 수의 명령어를 가지고 있다면, 이 비용은 너무 높지는 않다.
NVIDIA GeForce 6 시리즈와 같은 최신 GPU들은, 성능 특성이 조금씩 다르긴 하지만 비슷한 분기 명령을 사용한다.
오래된 GPU들은 이런 형식의 기본 분기가 없기 때문에 이러한 연산을 따라(에뮬레이트)하기 위한 전략이 필요하다.
병렬구조에서 가장 많이 사용되는 제어 메카니즘 두 가지는 단일 명령어/다중 데이터 [SIMD]와
다중 명령어/다중 데이터 [MIMD] 가 있다.
SIMD 병렬 구조에서 모든 프로세서는 동일한 명령을 동시에 수행한다.
MIMD 병렬 구조에서는 다른 프로세서들이 다른 명령을 수행할 수 있다.
분기를 구현하기 위해 현재 GPU에서 사용되는 방법은 세가지가 있다.
MIMD 분기, SIMD 분기, 그리고 조건 코드.
MIMD 분기는 마치 CPU처럼 패널티 없이 다른 프로세서가 다른 데이터 기반 분기를 가져올 수 있는 이상적인 케이스다.
NVIDIA GeForce 6 시리즈는 MIMD 분기를 버텍스 프로세서에서 지원한다.
(6시리즈부터 셰이더 모델 3.0을 지원)
SIMD 분기는 프로그램 내부에서 분기와 반복을 허용하지만, 모든 프로세서가 동일한 명령을 수행해야 해서
분기발산(divergent branch)은 성능이 하락하는 결과를 가져 올 수 있다.
예를들어, 랜덤한 값을 입력받아 이 값을 조건값으로 사용해 분기해서 각 프래그먼트의
출력값을 결정하는 프래그먼트 프로그램이 있다고 생각해 보자.
프레그먼트는 렌덤하게 다른 분기를 가질 것이고, 이로 인해 분기를 수행하지 않는 프레그먼트에 대한
스레드를 실행중인 프로세스는 다른 프로세스가 분기를 수행하는 프레그먼트에 대한 스레드의 실행을
끝낼 때 까지 기다려야 할 수도 있다.
결국은 많은 프레그먼트들이 양쪽 분기를 같이 수행하는 한, 분기 명령어의 오버헤드가 추가된다.
SIMD 분기는 분기 조건이 명료하게 "공간적으로" 일관성이 있는 경우에 무척 유용하지만,
많은 비 일관적인 분기는 부하가 심할 수 있다.
NVIDIA GeForce FX GPU는 버텍스 프로세서에서 SIMD 분기를 지원하며,
NVIDIA GeForce 6 시리즈 GPU는 프레그먼트 프로세서에서도 지원한다.
조건 코드[예측]는 예전 아키텍쳐(구조)에서 실제 분기를 예측하기 위해 사용되었다.
If-then으로 컴파일 된 아키텍쳐 구문은 반드시 모든 프래그먼트에서 분기를
수행하거나 하지않거나 둘 다 평가해야 한다.
분기 조건이 평가되어지고 조건 코드가 설정된다.
분기의 각 파트에 있는 명령어들은 반드시 레지스터에 결과값을 쓰기 이전에 조건 코드의 값을 확인한다.
결과적으로, 분기에서 수행된 명령어들만 출력으로 작성한다.
따라서, 이러한 아키텍쳐에서 모든 분기 비용은 분기의 두 부분뿐 아니라, 분기 조건을 평가하는 부하도 추가된다.
이러한 아키텍쳐에서는 분기의 사용을 절약해야 한다.
NVIDIA GeForce FX 시리즈의 GPU에서는 프래그먼트 프로세서에서 조건 코드 분기 에뮬레이션을 사용한다.
34.2 기본적인 흐름 제어 전략
34.2.1 예측
앞서 이야기 했듯이, GPU에서 분기를 구현하기 위한 가장 간단한 방법은 예측이다.
예측을 통해 GPU는 효율적으로 분기의 양측을 평가하고 나서 부울 분기 조건의 값을 기반으로 결과중 하나를 폐기한다.
이 접근법의 단점은 분기의 양측을 평가하는데 있어 만약 f()와 g() 가 큰 함수라면 비용이 비쌀 수 있다는 것이다.
예측은 작은 분기에는 효율적이지만, 보다 복잡한 분기에서는 대체적략이 필요하다.
34.2.2 파이프라인 위로 분기 이동
명시적인 분기는 GPU에서 까다로울 수 있기 때문에, 작업 레퍼토리에 여러가지 기술을 사용하는게 편하다.
유용한 전략은 흐름 제어 결정을 파이프 라인 상위 단계로 옮겨, 더 효율적으로 평가 할 수 있게 하는 것이다.
정적 분기 해결법
CPU에서 스트림 또는 데이터 배열에 대한 계산을 수행할 때, 대부분의 프로그래머들은
계산의 내부 루프 안쪽에서 분기를 피하기 위해 노력해야 한다는 것을 알고 있다.
이렇게 하면 잘못된 분기 예측 때문에 파이프라인이 멈출 수 있다.
한 예로 이산 공간 그리드에서 편미분 방정식(PDE)을 평가하는것을 생각해 보자.
유한 정의역(finite domain, FD)에서 PDE의 올바른 평가는 경계 조건을 필요로 한다.
순수한 CPU 구현은 전체 그리드를 반복하면서, 각 셀이 경계 셀인지를 결정하고,
결정 결과를 기반으로 적절한 계산을 적용할 수 있다.
더 나은 구현은 프로세스를 여러개의 루프로 나누는 것이다.
하나는 경계 셀을 제외한 그리드의 내부에, 그리고 하나 또는 그 이상은 경계 모서리로 한다.
이 정적 분기 해결법은 분기없이 효율적인 코드를 포함하는 루프를 만든다.
동일한 최적화는 대부분의 GPU에서 더욱 중요하다.
이 경우, 계산은 내부적으로 두개의 프로그램으로 나뉘는 데 하나는 내부 셀을 위한 것이고
다른 하나는 경계 셀을 위한 것이다.
내부 프로그램은 출력 버퍼의 바깥 single - cell - wide 가장자리를 제외한
전체에 걸쳐 그려진 쿼드의 프래그먼트에 적용된다
경계 프로그램은 가장자리 픽셀 위에 그려진 선의 프래그먼트에 적용되어 진다.
사전계산
앞의 예에서, 분기의 결과는 입력(또는 출력 범위)값의 큰 정의역에 대해 일정했다.
마찬가지로, 분기의 결과는 일정기간동안 또는 계산의 반복 횟수에 대해 일정할 때도 있다.
이 경우, 결과가 변경될 때에만 분기를 평가하고, 후속 반복을 통해 결과를 저장 할 수 있다.
이로인해 성능이 크게 향상될 수 있다.
NVIDIA SDK의 "gpgpu_fluid"예제는 이 기술을 사용하여 flow field의 임의 장애물의
가장자리에서 경계 조건을 계산할 때 분기를 피한다.
이러한 경우, 인접한 장애물이 없는 유체 셀은 정상적으로 처리 될 수 있지만,
인접 장애물이 있는 셀은 더 많은 작업이 요구된다.
이 셀은 장애물이 어느 방향에 있는지를 알아내기 위해 주변을 체크해야 하며,
계산에 사용될 더 많은 데이터를 찾기 위해 이 방향을 사용한다.
이 예제에서, 장애물은 사용자가 "paints"할 때만 변경된다.
그래서, 사용자가 장애물을 변경할때 까지 재사용하기 위해
오프셋 방향을 미리 계산하여 오프셋 텍스쳐에 저장할 수 있다.
34.2.3 Z-Cull
사전 계산 된 분기 결과를 한 걸음 더 앞당기고 다른 GPU 기능을 사용하여
불필요한 작업을 완전히 건너 뛸 수 있다.
최신 GPU는 보이지 않는 음영 픽셀을 피하기 위해 설계된 많은 기능이 있다.
그 중 하나가 z-cull이다.
Z-cull은 입력되는 fragment의 깊이(z)를 해당 fragment의 깊이와 비교하여
입력 fragment가 깊이 테스트에 실패하면 fragment 프로세서에서 픽셀 컬러가
계산되기 전에 폐기되도록 하는 기술이다.
따라서, 깊이 테스트를 통과 한 fragment만 처리되므로 작업이 절약되고,
어플리케이션이 더 빠르게 동작한다.
이 기술은 일반적인 계산에도 사용할 수 있다.
앞에서 언급한 유체흐름에서의 장애물 예에서, 완전히 "landlocked(육지로 둘러싸인)"인 일부 셀(세포)가 있다.
이 세포의 주변 세포는 전부 장애물 셀이다.
우리는 이 셀들에 대해서는 어떠한 계산도 할 필요가 없다.
이러한 셀들을 건너뛰기 위해, 사용자가 새로운 장애물을 칠할 때 마다 약간의 설정 작업을 한다.
각 프래그먼트의 주변을 검사하는 프래그먼트 프로그램을 실행한다.
이 프로그램은 landlocked된 프래그먼트만 가져오고 discard 키워드를 사용하여 다른 모든 프래그먼트는 폐기한다.
(discard 키워드는 Cg와 GLSL에서 사용할 수 있으며 HLSL에서는 clip()와 같다)
이 프로그램의 Cg코드는 34-1에 적혀있다.
코드 34-2에 있는 의사코드는 어떻게 z-cull을 설정하고 landlocked 셀의 처리를 건너뛰는지를 보여준다.
아래 두개의 코드에서 보면 34-1소스에서는 전처리 패스로서,
landlocked 셀이라면 0의 깊이값을, 아니라면 1의 깊이값을 가지도록 z버퍼를 "마스킹"(설정)한다
따라서, z=0.5에서 쿼드를 그릴 때, landlocked 셀은 z 버퍼의 0.0값에 의해 "blocked(차단)"될 거고
자동으로 GPU에 의해 컬링될 것이다.
만약 장애물이 상당히 크다면, 우리는 이러한 셀들을 처리하지 않음으로써 많은 작업을 줄일 수 있다.
Example 34-1. 뒤의 패스에서 Z-Culling을 위한 Z-Depth 값을 설정하는 Cg코드
half obstacles(half2 coords : WPOS, uniform samplerRECT obstacleGrid) : COLOR { // get neighboring boundary values (on or off) half4 bounds; bounds.x = texRECT(obstacleGrid, coords - half2(1, 0)).x; bounds.y = texRECT(obstacleGrid, coords + half2(1, 0)).x; bounds.z = texRECT(obstacleGrid, coords - half2(0, 1)).x; bounds.w = texRECT(obstacleGrid, coords + half2(0, 1)).x; bounds.x = dot(bounds, (1).xxxx); // add them up // discard cells that are not landlocked if (bounds.x < 4) discard; return 0; }
각주 : 위 함수는 장애물 체크를 해서 landlock셀이 아니라면 discard를 한다.
상하좌우의 텍셀을 참고해서 하나라도 landlocked셀이 아니라면 discard(폐기)한다.
이렇게 해서 주위 텍셀이 모두 landlocked이면 0으로, 아니라면 폐기시켜 버린다.
첫번째 패스에서 z값을 설정했다.
두번째 단계에서는 z 테스트를 통과하는 픽셀에서 프래그먼트 프로그램을 실행한다.
// Application Code--Preprocess pass ClearZBuffer(1.0); Enable(DEPTH_TEST); DepthFunc(LESS); BindFragmentProgram("obstacles"); DrawQuad(Z=0.0); // Application code--Passes in which landlocked cells are to be skipped Enable(DEPTH_TEST); Disable(DEPTH_WRITE); // want to read depth, but not modify it DepthFunc(LESS); // bind normal fragment program for each pass DrawQuad(Z=0.5);
각주 : 첫번째 패스에서 z버퍼값을 1로 초기화 시켜주고 "obstacles"를 실행하여
landlocked이면 0, 아니면 discard 시켰다.
그러므로 z값 0.5로 쿼드를 그린다면 ztest에 의해 landlocked 마스킹으로 0을 설정한 부분은
처리를 할 필요가 없고 GPU에 의해 자동으로 컬링되다는 개념.
이 기술을 사용하는데 있어 한가지 주의사항은 GPU에 의해 z컬링이 종종 프레그먼트 단위 기준보다
더 코어스한 해상도(저분해능, 그냥 더 낮은 해상도 라는 뜻일까?)에서 수행된다는 것이다.
GPU는 프레임 버퍼의 작은 연속적인 영역에 있는 모든 프레그먼트가 깊이 테스트에 실패할 경우에만 음영처리를 건너뛴다.
이 영역의 정확한 사이즈는 GPU마다 다양하지만, 일반적으로 z컬링은 분기가 지역성이 있을때만 성능에 도움을 준다.
이것을 설명하기 위해 z컬링의 성능을 랜덤한 부울 조건과 높은 공간 지역성을 갖는 부울 조건과 비교할 수 있다.
랜덤 부울의 경우 임의의 값으로 텍스쳐를 채운다.
공간적 지역성이 높은 부울의 경우 직사각형의 영역을 단순히 상수 부울 값으로 설정하기만 하면 된다.
그림 34-1에서 볼 수 있듯이, 분기에 많은 지역성 있는 경우 z컬링이 가장 효과적이다.
좋은 소식은 이 지역성은 분기를 성공할 가능성이 무척 낮거나(즉, 매우 적은 프래그먼트가 깊이 테스트를 통과한 경우)
무척 높을경우 자연스럽게 존재한다는 것이다.
지역성이 존재하지 않는다면, z컬링은 생각보다 좋지는 않을 것이다.
그림 34-1 z컬링을 사용할 때 분기 타입에 따른 비용
그러나 z컬링은 프레그먼트 프로그램 내부에서의 분기와는 많이 다르다는 것을 알아야 한다.
z컬링은 프래그먼트 프로그램이 실행되는 것을 방지한다.
그래서 z컬링은 정적인 사전평가된 조건을 기반으로 많은 불필요한 작업을 건너 뛸 수 있는 강력한 방법이다.
프래그먼트 프로그램 분기를 사용하여 동일한 작업을 수행하려면 프로그램 실행, 평가할 조건 및 초기에
종료 할 프로그램이 필요하다.
이 모든 것은 프래그먼트 프로그램을 건너 뛰는 것보다 더 많은 프로세서 사이클을 필요로 한다.
34.2.4 분기 명령
프래그먼트 분기 명령을 지원하는 첫번째 GPU는 NVIDIA Geforce 6 시리즈다.
이 명령은 마이크로소프트 DirectX Pixel Shader 3.0 명령어 세트와
OpenGL NV_fragement_program2 확장, 이렇게 두곳 모두에서 사용 할 수 있다.
더 많은 GPU들이 분기 명령어를 지원하기 때문에, 분기를 위한 예측을 사용하는 것이 더 이상 필요하지 않다.
하지만 초기 z-cull에 영향을 주는 지역성 문제는 이 분기 명령어에도 적용된다.
GPU는 프래그먼트 그룹에 대한 프래그먼트 프로그램을 병렬로 실행한다.
각 그룹은 하나의 분기만 실행할 수 있다.
이것이 불가능한 곳에서는 GPU가 효과적으로 예측으로 넘어간다.
그림 34-2는 분기 명령어를 사용하여 구현 된 시간 대 확률 테스트를 보여준다.
그림 34-2 Pixel Shader 3.0을 사용한 분기의 타입에 따른 부하
그림에서 알 수 있듯이, 같은 공간 지역성 값이 분기 효율성에 적용된다.
하지만 z-cull과 마찬가지로 분기의 확률이 매우 낮거나 매우 높은 경우 분기 명령어가 매우 효과적이다.
34.2.5 분기 메케니즘 선택
프로그램에 있어 효율적인 분기 메케니즘을 선택하는 것은 주로 분기 내부의 코드 크기와
state present의 크기의 크기에 달려있다.
각주 : state present가 if문에서 if문 괄호안에 들어가는 조건문을 이야기 하는 건지
아니면 if문의 조건 체크 갯수를 말하는 건지 잘 모르겠다.
예를들면 if(수식) 인지 아니면 if else else else 처럼 갯수인지....
z-cull 또는 분기 명령어에 대한 오버 헤드가 모든 이점을 무효화 할 수 있으므로
짧은 분기(2개에서 4개의 연산) 예측이 선호된다.
큰 프로그램에 포함된 분기의 경우 z-cull 대신 분기 명령어를 사용하는 것이 좋다.
비록 분기 명령이 지역성 문제에 대해 더 민감 하더라도, z-cull을 사용하면
모든 프로그램 상태를 저장하고, 별도의 패스에서 분기를 수행하고,
그리고 계속 진행할 프로그램의 상태를 복원시켜야 한다.
큰 프로그램에서 이러한 저장 과 복원은 z 컬링을 비효율적으로 만들 수 있다.
하지만, 프로그램에서 분기 요소를 효율적으로 독립시킬 수 있다면,
z-cull이 최고의 성능을 제공할 것이다.
34.3 Occlusion Queries를 사용한 데이터 기반 루프(Loop)
보이지 않는 것을 그리지 않도록 설계된 또 다른 GPU 기능은 하드웨어 오클루젼 쿼리이다.
이 기능을 사용하면 렌더링 호출로 업데이트 되는 픽셀 수를 쿼리할 수 있다.
이러한 쿼리는 파이프 라인 방식이므로 실제 픽셀을 다시 읽을 때 발생하는 것 처럼
파이프라인을 지연시키지 않고 GPU에서 제한된 양의 데이터(정수 카운트)를 다시 얻을 수 있는 방법을 제공한다.
GPGPU에서는 알려진 픽셀 범위를 갖는 쿼드를 거의 항상 그리기 때문에 34.2.3절에서
논의 된 discard 키워드로 오클루전 쿼리를 사용하여 업데이트 되고 삭제 된 프레그먼트 수를 얻을 수 있다.
이를 통해 우리는 GPU 프로세싱에 기반한 CPU에 의해 제어되는 글로벌 의사 결정을 구현할 수 있다.
모든 요소가 종료기준을 만족시킬 때 까지 스트림의 요소에서 반복적으로 진행되야 하는 계산이 있다고 가정한다.
이를 GPU에서 구현하기 위해, 우리는 계산을 구현하는 프래그먼트 프로그램 하나와 종료기준을 테스트 하는
프래그먼트 프로그램을 작성한다.
후자의 프로그램은 종료기준을 만족하는 프래그먼트를 폐기(discard)한다.
그리고 나서 아래의 의사코드와 같이 CPU에 루프를 작성한다.
이 의사코드는 모든 스트림 요소가 종료 조건을 만족시킬 때 까지 실행된다.
int numberNotTerminated = streamSize; while ( numberNotTerminated > 0 ) { gpuRunProgram(computationProgram); gpuBeginQuery(myQuery); gpuRunProgram(terminationProgram); gpuEndQuery(myQuery); numberNotTerminated = gpuGetQueryResults(myQuery); }
이 기술은 또한 이 책의 챕터 39장 "Global Illumination Using Progressive Refinement Radiosity"에서
적응형 레디오시티 솔루션과 같은 하위 구분 알고리즘에도 사용할 수 있다.
34.4 결론
프래그먼트 프로세서 레벨에서 분기 지원을 통해 최신 세대의 GPU는 GPGPU 프로그램에서
분기를 훨씬 쉽게 사용할 수 있게 한다.
if, for 그리고 while과 같은 고급 언어 구문은 GPU 어셈블리 명령어로 직접 컴파일 되므로
이전 GPU에서 필요한 것처럼 z컬링및 오클루전 쿼리와 같은 더 복잡한 전략을 사용하지 않아도 된다.
그럼에도 불구하고 GPU에서 비 간섭성 분기에 대한 페널티가 있다.
34.2.2에서 설명한 것 처럼 사전 계산과 이동 연산을 기반으로 한 기술을 사용하면 GPGPU전략으로 계속 사용할 수 있다.
Reference Link
- 연산처리의 성능 한계에 도전하는 병렬 컴퓨팅(4편)
- 정의역
- Pipeline
- 분기예측