[번역] 유향 비순환 그래프(DAG)를 이용한 GPU 작업 조직화

- 2022/05/04 (최초 작성)

- 2022/05/25 (마지막 수정)

발 번역 주의보, Figures나 예제 코드는 빠져있을 수 있습니다.

개인 공부 및 연습용으로 번역된 글입니다. 의역/오역/오타가 많을 수 있으며. 원저작권자의 별도의 허가 없이 작성되었으므로, 언제든지 삭제될 수 있습니다.

원본 아티클

---

유향 비순환 그래프(DAG)를 이용한 GPU 작업 조직화(Organizing)

by Pavlo Muratov

 

목차

• 무엇을 조직화해야 할까요?
• 그래프 만들기
• 그래프 사용하기
  • 동기화
  • 리소스 상태 전환
  • API별 뉘앙스
  • 특이사항
• 결론
• 감사인사
• 코드

---

무엇을 조직화 해야 할까요?

 

 DirectX 11과 OpenGL 스타일의 API들은 GPU에서 중요한 스케쥴링 작업이 어떻게 그리고 언제 일어나는지 정하기 위해서 복잡한 휴리스틱을 호출하기 위한 드라이버를 요구합니다. 즉시 실행-모드는 인터페이스의 성질은 모든 극단적인 경우를 처리하기 위해 복잡한 리소스 관리(book keeping)와 상태 추적을 요구합니다 - 여기서 궁극적으로 극단적인 경우란 성능에 부정적인 영향을 주거나 병렬화를 방해하는 경우를 의미합니다.

 DirectX 12, Vulkan, 그리고 Metal 2 같은 모던 그래픽스 API들은, 이런 모델을 떠나보내고 그 대신 애플리케이션 스스로 저수준 GPU 관리의 부담을 지도록 하는 방식을 선택했습니다.

 

  이런 방식을 선택했다는 것은 프레임내에서 일어나는 렌더링 작업들에 대한 고수준의 이해를 가지고 실행 전에 최적의 방법을 정할 수 있는 시스템을 디자인할 수 있는 기회를 얻었다는 것입니다. 이런 기회에는 GPU와 메모리 상태, 메모리 재사용, 큐 동기화를 최적화가 포함됩니다. 이런 시스템은 프레임의 워크플로우의 정당성을 검증하거나 불필요한 일들을 제외시키는 데 사용할 수 있어서, 사용자의 행동에 따라 자기 스스로 다시 최적화를 시도할 수 있습니다. 이때 그래프는 이런 작업을 위한 데이터 구조로써 적합합니다.

 

이 아티클에서는 다음의 주제들을 다루어 볼 것 입니다: 그래프 구축하기, 그래프를 일을 배치(batch)하거나 적절한 동기화 지점을 삽입하는 데 사용하기, 리소스 배리어 처리하기.

 

 앞으로 다룰 알고리즘의 디자인은 DirectX12 API에서 영감을 받았습니다. 끝부분에서는 상세한 구현과 함께 코드 예제들이 제공될 예정입니다.

 

*역: 번역 과정에서 A 노드가 B 노드에 의존적인 경우, A가 B에 의존적이다 (종속적임) 라고 하고. B를 A의 의존 노드라고 하였습니다. 그리고 이를 A->B라고 표기합니다 (이 표기는 의존성을 나타낼 때만 표기하고, 그래프의 방향(진행 방향), 패스의 실행 순서는 그대로 읽으시면 됩니다).

그래프 만들기

 그럼 가장 기초에서 부터 시작해보죠. 우리는 일을 조직하고 싶습니다, 그러니 일의 단위를 정해서 이를 렌더 패스(Render Pass)라고 부릅시다. 일은 만들어낸 결과를 사용하지 않으면 무용지물이죠. 그러므로 일의 출력과 입력을 정의해야 합니다. 출/입력은 읽고 쓰이는 GPU 리소스들로 정의합니다. 그리고 이 세가지 요소(정의)가 렌더 패스를 나타낼 노드와 그래프를 만들기 위해 필요한 정보의 전부입니다.

class Node
{
  void AddReadDependency(Foundation::Name resourceName, const SubresourceList& subresources);
  void AddWriteDependency(Foundation::Name resourceName, const SubresourceList& subresources);

  std::unordered_set<SubresourceName> ReadSubresources;
  std::unordered_set<SubresourceName> WrittenSubresources;
}

가장 간단한 노드 예시

class RenderPassGraph
{
  void AddPass(const RenderPassMetadata& passMetadata);
  void RemovePass(NodeListIterator it);

  NodeList Nodes;
}

그래프는 간단한 평평한 형태의 노드 리스트로도 표현 할 수 있습니다

class ResourceScheduler
{
  void NewRenderTarget(Foundation::Name resourceName);
  void NewDepthStencil(Foundation::Name resourceName); 
  void NewTexture(Foundation::Name resourceName); 
  void UseRenderTarget(Foundation::Name resourceName, const MipList& mips = { 0 });
  void UseDepthStencil(Foundation::Name resourceName);
  void ReadTexture(Foundation::Name resourceName, const MipList& mips = { 0 });
  void WriteTexture(Foundation::Name resourceName, const MipList& mips = { 0 });
  template <class T> 
  void NewBuffer(Foundation::Name resourceName, const NewBufferProperties<T>& bufferProperties = NewByteBufferProperties{ 1, 1 });
  void ReadBuffer(Foundation::Name resourceName, BufferReadContext readContext);
  void WriteBuffer(Foundation::Name resourceName);
  void ExecuteOnQueue(RenderPassExecutionQueue queue);
  void UseRayTracing();
}

그래프의 노드들 내의 의존성을 기록하기 위해 사용되는 클래스의 인터페이스 예시

 

순환 없이 다양한 의존성을 표현하는 렌더 패스 묶음

 

 자 이제 기본적인 정의를 정립하였으니, 한번 무질서면서도 의존적인 렌더 패스들의 집합을 결정적이고 모순이 없는 집합으로 정렬(order)해보도록 합시다.

 

 완전히 자동적으로 그래프를 만들기 위해서는 한 가지 중요한 성질이 필요합니다.

 

 필요한 성질은 바로 비순환성 입니다. 비순환성은 우리가 그래프를 만들기 전에 고려해야 하는 몇 가지 제한사항을 부과합니다.

 

 모든 순환 의존성은 알고리즘이 어떤 순환된 노드가 처음에오고 어떤 노드가 마지막에 와야 하는지 말해주지 않으면 모호성을 띄게 됩니다. 그러므로, 우리는 순환적인 의존성들을 피해야 합니다.

 

 또 다른 주의점은 같은 리소스를 위해 다중으로 의존성을 쓰게 되는 것입니다. 만약 두 개 이상의 렌더 패스가 같은 리소스에 대해 출력 (쓰기) 의존성을 가지도록 기록한다면. 이때 또한 한 개 이상의 솔루션이 존재할 수 있기 때문에 알고리즘이 단일 노드의 순서를 결정하는데 실패하게 됩니다. 그러므로, 두 번째로 같은 리소스에 대한 다중 쓰기 의존성을 금지하고. 각 렌더 패스가 무조건 새로운 출력을 가지도록 기록하도록 만듭시다. 단일 쓰기 의존성을 요구하는 것은 논란의 여지가 있긴 하지만 마지막에 가서 더 다뤄보도록 하고, 일단 지금은 이 제한점을 받아들이도록 합시다.

 

 자 이제 앞에서 다룬 제한점들을 마음에 새기고 깊이-우선 탐색 알고리즘의 수정된 버전에 기반을 둔 위상 정렬을 사용해서 예시 그래프를 정렬(order)해보도록 하겠습니다.

이 알고리즘은 선형 시간 안에 유향 비순환 그래프를 정렬할 수 있습니다.

 

그래프의 인접 리스트들

 

 알고리즘은 노드와 간선을 입력 받습니다. 우리는 렌더 패스의 노드를 가지고 있지만, 아직 실제론 간선들을 가지고 있진 않습니다. 아는 거라곤 오직 어떤 리소스들이 각 렌더 패스에 의해 읽히고 쓰이는 것에 대한 것에 대한 정보 뿐이죠.  하지만 이 정보는 인접 리스트라고 불리는 데이터 구조를 만드는 데 사용할 수 있습니다. 인접 리스트는 그래프에 있는 N개의 노드들을 위한 N개의 배열이고 이 배열들은 연결된 노드에 대한 참조를 포함하고 있는, 배열의 배열일 뿐입니다. 위 정보를 사용하여 가능한 노드들의 짝 사이에서의 읽기 에서 쓰기 의존성을 검사해서 인접 리스트를 만들 수 있습니다.

 

 자 이제 만들어진 인접 리스트를 통해 그래프를 정렬할 수 있습니다. 그걸 위해선 boolean 값들을 저장하는 두 개의 도우미 배열이 필요합니다. 이들의 크기는 그래프 안의 모든 노드수를 나타내는 N입니다. 하나는 "방문함(visited)"노드를 표시하기 위해 사용되고 또 다른 하나는 순환적인 의존성들을 감지하기 위해서 "쌓임(on stack)" 노드들을 표시합니다.

 

그래프를 위한 도우미 배열들 (N=9)

 

 그래프 내의 모든 노드를 순회하고, 각 노드에 대해 후위 순회를 통해 재귀 탐색을 시작해서, 만나는 노드들을 "쌓임"과 "방문함"으로 표시합니다.

 

위상 정렬(Topological sort)

 

 더 이상 자식 노드를 찾을 수 없어지면 최종 배열에 노드를 추가합니다. 그리고 스택이 되감길 때(unrolled) "쌓임" 플래그를 지우고, "방문" 플래그는 남겨둡니다. 이는 우리가 동일한 노드를 한번 이상 처리하는 것을 막는데 도움을 줍니다. 검색 도중에 이미 방문했으면서도 쌓여있다고 표시된 노드를 만나게 되면, 이는 순환적인 의존성이 존재한다는 것을 의미하며 그 즉시 작업을 멈추어야 합니다.

 

 위의 예제에서는 노드 0으로부터 시작해서, 한 번의 재귀 탐색으로 전체 그래프를 정렬할 수 있었지만. 일반적으로 이보다 더 많은 탐색이 이루어질 수도 있기 때문에 모든 노드에 대해 후위 순회가 이루어져야 합니다.

 

마지막 단계에서는 결과 배열을 뒤집습니다 (후위 순회를 했기 때문에).

위상적으로 정렬된 노드들

이제 렌더 패스를 정해진 순서대로 실행시킴으로 써 의존성 또한 지켜질 수 있습니다.

 

하지만 다음으로 넘어가기 전에 한 가지 더 짚고 넘어가야 할 점이 있습니다. 한번 그래프를 다시 보도록 하죠.

 

 그래프를 보면 서로에게 의존적이지 않은 노드들의 그룹이 존재하는 것을 발견할 수 있습니다.

이 그룹을 의존성 레벨(Dependency Levels)이라고 부르도록 합시다. 하나의 의존성 레벨 안에 있는 렌더 패스들은 무작위 순서로 실행될 수 있고 이는 병렬 작업 실행과 우리가 나중에 살펴볼 특정한 최적화들을 적용 하는데 유용하게 쓰입니다.

 

 여기서 중요한 연관성은 의존성 레벨 내에 있는 패스들이 같은 재귀 깊이(recursion depth), 더 정확히 말하자면 DAG에서의 루트 노드로부터의 최장 경로라고도 알려진 최대 재귀 깊이를 공유한다는 것입니다. 여기서 각 노드의 의존성 레벨을 찾기 위해 최장 경로 탐색 알고리즘(longest path search algorithm)을 사용할 수 있습니다.

 

 최장 경로 탐색 알고리즘을 위해 그래프 내의 노드의 수인 N만큼의 크기를 가지고 각 노드에 대한 거리를 나타내는 배열을 정의해서 값들을 0으로 초기화시켜줍니다. 또한 그래프의 위상 정렬도 해야 하는데, 이건 이미 완료 해뒀었죠. 다음으론 노드를 위상적 순서로 순회해주고 처리된 모든 노드들에 대해, 현재 노드의 거리를 사용해서 처리된 노드의 인접 노드들의 거리 또한 업데이트해줍니다. 그러면 각 노드에 정해진 거리들은 노드들의 의존성 레벨들과 같아지게 됩니다.

그럼 이제 노드들은 의존성 레벨에 다라서 디스패치 될 수 있습니다.

 

알고리즘은 고작 4줄의 의사 코드만으로 설명될 정도로 간단합니다:

Do following for every vertex u in topological order.
  Do following for every adjacent vertex v of u
    if (dist[v] < dist[u] + 1)
      dist[v] = dist[u] + 1

그래프 사용하기: 동기화

 우린 앞서 작업들의 그래프를 만들었습니다 , 하지만 작업들은 모던 그래픽 API들에 의해 주어진 커맨드 큐를 사용해서 병렬적으로 실행될 수 있습니다. 이 점이 우리한테 분리된 큐들에서 실행되는 렌더 패스들 사이의 의존성을 보존하면서 더 많은 작업들을 묶기 위해 동기화량을 최소화하는 것 그리고 성능을 향상하기 위해 Execute...()의 호출 수를 최소화해야 한다는 도전 과제를 남겨줍니다.

 

 이 섹션에서는 몇몇 시나리오를 예로 들고 이들로부터 보편적인 해결법을 찾아서 큐 사이의 최적의 동기화를 달성하기 위한 알고리즘을 개발 해보고자 합니다.

동기화 시나리오 1

동기화 시나리오 2

 

 한번 두 가지 경우를 살펴보도록 합시다. 2개의 개별적인 큐들이 있고 각 큐에는 3개의 패스들이 있습니다 (여기선 교차 큐 작업 의존성들에 집중할 것입니다, 왜냐하면 다른 경우들에선 각각의 큐에서 돌아가는 일이 자명하기 때문입니다). 단조 증가하는 인덱스가 각 패스에 부여되어 있습니다 (인덱스는 각 큐에 대해서 0부터 시작됩니다. 하지만 이 점은 크게 상관은 없고, 인덱스가 단조 증가한다는 점이 중요합니다).

 

 첫 번째 경우를 보면 다른 큐에 있는 두 개의 패스 (4, 5)에 동기화되어야 하는 패스 (3)가 있습니다(*역: 패스 (3)이 패스 (4, 5)에 의존적임). 두 번째 경우에는 반대로 하나의 패스 (1)에 동기화되어야 하는 두 개의 패스 (5, 6)이 있습니다(*역: 패스 (5, 6)이 패스 (1)에 의존적임).

 

 이 경우 첫 번째 사진을 보면 패스 (3)과 (4)를 동기화시키는 건 필요 없는 일인 것을 알 수 있습니다. 왜냐하면 그 둘의 동기화는 패스 (3)과 (5)를 동기화시키면서 자동적으로 이루어지거든요. 그러면 여기선 어떤 알고리즘이 사용돼야 할까요? 패스 (3)을 가지고, 다른 큐에 있는 의존성을 가지는 노드인 (4, 5)를 순회합니다 그리고 그중에서 가장 가깝고, 가장 높은 인덱스를 가지는 것만 취하세요. 즉, 패스 (5)만 취하고, 나머지는 무시하세요.

 

그럼, 이제 두 경우 모두에게 충분할까요? 사실 아닙니다, 두 번째 케이스가 그렇지 않다는 걸 나타냅니다.

 

 만약 두 번째 경우에서 가장 가까운 의존성만 보게 된다면, 같은 사진에서 다음과 같이 끝나게 될 겁니다: (5)는 가장 가까운 의존 노드인 (1)과 동기화를 할 것이고 (6) 또한 그럴 겁니다. 하지만 우리가 봤을 때는 (6)과 (1)의 동기화는 (5)와 (1)의 동기화로 인해 명백하게 불필요합니다. 우리가 처음 내놓았던 해결법이 두 번째 경우에서는 통하지 않게 된 거죠.

 

그럼 이제 우리가 뭘 할 수 있을까요?

 

 이 문제를 해결하기 위해 먼저 각 큐에서 동기화되어야 하는 노드에 가장 가까운 노드들의 인덱스를 가지고 있는 숫자들의 집합을 각 노드에 정해주고 이를 충분 동기화 인덱스 집합(sufficient synchronization index set; SSIS)라고 부르기로 합시다. 그럼 이제 이 SSIS에 대해 설명드리도록 하겠습니다.

 

충분 동기화 인덱스 집합

 

자 이제 이전에 보았던 두 개의 예시를 가져와서 각 노드에 SSIS를 부여해보도록 합시다.

SSIS 값을 부여한 동기화 시나리오 1

SSIS 값을 부여한 동기화 시나리오 2

 

 먼저 SSIS를 모두 0인 상태로부터 시작해서 각 노드를 통과하면서 각 노드의 다른 큐에 있는 의존 노드들을 순회하면서 현재 노드의 SSIS에 가장 가까운 의존 노드의 인덱스들을 저장합니다. 노드가 속해있는 큐에 대한 SSIS 값들은 살짝 다르게 설정되야 합니다(큐 0에 있는 노드는 SSIS[0], 큐 1에 있는 노드들에 대해서는 SSIS[1]에 저장되어야 합니다. 그리고 그 다음의 경우들에 대해서도 이런 규칙을 적용해야 합니다). 이 경우에는 의존 노드의 인덱스를 부여하는 게 아니라 (같은 큐에 있는 바로 직전의 노드), 노드 자기 자신의 인덱스를 부여합니다. 같은 큐 안에 있는 현재 그리고 이전 노드들은 리소스 읽기/쓰기에 있어서 의존적이지 않기 때문입니다. 하지만 알고리즘이 제대로 동작하기 위해선 현재 노드에 개의치 않고 바로 앞 노드를 의존 노드로써 추가해야 합니다. 물론 이 경우에도 이전 노드가 존재하는 경우에 한해서요.

 

 이 규칙에 따라서, 첫 번째 예제에서 패스 (3)의 SSIS는 (3, 5)가 되고, 두 번째 예시에서 패스 (5)의 SSIS는 (1, 5) 그리고 패스 (6)의 SSIS는 (1, 6)이 됩니다.

 

 이제 각 노드에 대해 SSIS를 만들어 줬으니 이제 불필요한 동기화들을 걸러내기 위해 간접 의존 노드들을 살펴보고 두 번째 예시에서 생겼던 문제를 해결할 수 있습니다:

노드 (6)은 (5)를 통해서 (1)과 간접적으로 동기화되기 때문에 (6)을 (1)과 동기화시키는 것은 불필요합니다.

 

간접 의존성을 찾기 위한 알고리즘의 두 번째 단계를 살펴보도록 합시다.

 

 다시 각 노드들을 순회하고 노드들의 의존 노드들을 살펴봅시다. 하지만 이번엔 의존성이 있는 패스의 SSIS 값을 현재 노드의 SSIS에 있는 값과 비교합니다.

 

 현재 SSIS와 의존성을 가지는 노드의 SSIS를 비교함으로써, 의존성을 가지는 노드와 동기화할 때 몇 개의 큐와 동기화되어야 하는지 정할 수 있습니다. 위에서 말했던 같은 큐에서의 의존성 노드들을 위한 SSIS 할당 규칙을 고려해서 "다른" 큐에서는 직접적으로 "같은" 큐에서는 비교하기 전에는 먼저 현재 노드의 SSIS에서 1을 빼줍니다.

 

 자 그럼 두 번째 케이스의 노드 (6)을 가져와서 노드의 첫 번째 의존 노드 (1)을 가져온다음, 큐 0과의 동기화를 위해 SSIS 값을 비교해보도록 합시다. SSIS(Node 6)[0] <= SSIS(Node 1)[0] -> (1 <= 1)는 참입니다 그러므로 큐 0과의 동기화는 노드 (1)과의 동기화로 처리될 수 있다는 사실을 알아냈습니다. 이제 두 번째 큐의 값을 비교해보죠. SSIS(Node 6)[1] <= SSIS(Node 1)[1] -> ((6-1)<= 0)은 거짓입니다 그리고 이는 큐 1의 동기화가 노드 (1)과의 단독 동기화로는 불가능하므로 요구된 모든 동기화를 달성하기 위한 다른 의존 노드들을 찾아야 합니다. 그럼 노드 (6)이 의존하고 있는 다른 노드인 (5)를 살펴 보도록 하죠. SSIS 값을 비교함으로써 두 큐의 동기화는 오직 (5)와의 동기화로만 이루어 진단 걸 알 수 있습니다, 왜냐하면 SSIS에서의 두 개 값 비교 양쪽 모두 SSIS(Node 6)[0] <= SSIS(Node 5)[0] -> (1 <= 1) 그리고 SSIS(Node 6)[1] <= SSIS(Node 5)[1] -> (6-1) <= 5 이므로 참이기 때문입니다 (현재 노드가 (6), 의존하고 있는 대상 노드가 (1)). (6)과 (1) 사이에서의 동기화는 이제 불필요 해졌고 동기화 대상에서 제외될 수 있습니다.

 

 N개의 큐가 존재하는 경우 같이 더 일반적인 경우에는 동기화해야 하는 큐들의 리스트와 함께 의존 노드들과 이들이 큐 리스트에서 커버하고 있는 동기화들의 개수를 만듭니다. 그 후에 커버한 동기화의 수가 최대인 노드를 선택하고 나머지는 제외시킵니다.

 

 이 일반화는 설명했던 케이스들에서의 동기화 최소화에 사용하기엔 충분합니다만. 모든 경우를 커버하기엔 여전히 충분하지 않습니다. 한번 이 알고리즘이 감당하지 못하는 예시를 하나 더 살펴보고 알고리즘의 개선점을 고민해보도록 합시다.

단 한 번의 간접 의존성 탐색으로는 충분하지 않은 더 복잡한 동기화 시나리오

 여기서 노드 (6)이 노드 (1) 이후에 큐 0과 동기화되는 것을 볼 수 있습니다. 하지만 노드 (1)과의 동기화는 불필요 합니다. 왜냐하면 (1)과의 동기화는 노드 (3)과의 동기화를 통해 이루어질 수 있기 때문이죠. 자 한번 우리가 지금껏 설계한 알고리즘을 사용해서 필요 없는 동기화를 제외시켜 보도록 하죠.

 

 먼저 동기화될 큐들의 리스트를 만들어 보도록 합시다(0, 1, 2). 그다음으로 SSIS 값들을 비교해서 필요한 최대 큐의 수와 동기화될 의존 노드들을 찾습니다.

 

가능한 동기화 상황들:

 

노드 6 -> 노드 1 : 1개 큐가 커버됩니다. 왜냐하면:

• SSIS(노드 6)[0] <= SSIS(노드 1)[0] -> (1 <= 1 == true)
• SSIS(노드 6)[1] <= SSIS(노드 1)[1] -> (3 <= 0 == false)
• SSIS(노드 6)[2] <= SSIS(노드 1)[2] -> (5 <= 0 == false)

노드 6 -> 노드 3 : 2개 큐가 커버 됩니다. 왜냐하면: 

• SSIS(노드 6)[0] <= SSIS(노드 3)[0] -> (1 <= 1 == true)
• SSIS(노드 6)[1] <= SSIS(노드 3)[1] -> (3 <= 3 == true)
• SSIS(노드 6)[2] <= SSIS(노드 3)[2] -> (5 <= 0 == false)

노드 6-> 노드 5 : 1개의 큐가 커버 됩니다. 왜냐하면:

• SSIS(노드 6)[0] <= SSIS(노드 5)[0] -> (1 <= 0 == false)
• SSIS(노드 6)[1] <= SSIS(노드 5)[1] -> (3 <= 0 == false)
• SSIS(노드 6)[2] <= SSIS(노드 5)[2] -> (5 <= 5 == true)
  

 우리가 고안한 알고리즘에 따르면 제일 많은 큐를 커버하는 (6->3)을 사용해서 동기화를 진행하고 나머지는 버려야 합니다. 하지만 실제로 그렇게 해버리면 오직 큐 0과 큐 1에 대해서만 동기화가 이뤄지고, 큐 2와의 동기화는 이뤄지지 않게 됩니다.

 

이 문제를 해결하기 위해 알고리즘을 좀 더 확장 해보도록 합시다.

 

 최대한 많은 큐 동기화들을 커버하는 의존 노드들을 찾는 첫 번째 단계 이후에, 동기화해야 하는 큐들의 리스트에서 알고리즘을 통해 처리된 큐들을 제외하고 다음 순회를 위해서 의존 노드들의 리스트에서 이미 처리된 의존 노드들을 제거합니다. 또한 처리된 큐들에 대해 허용된 종속 노드들의 SSIS 값들을 써서 현재 노드의 SSIS 값들을 업데이트합니다. 이는 종속 노드의 SSIS 값이 실제로는 현재 노드에서 예상하는 것보다 클 수도 있기 때문입니다(이 부분은 문제는 없습니다). 자 이제 우리가 동기화하고 싶은 큐들이 남았는지 검사해봅시다. 먼저, 이전 순회에서 남은 노드들의 리스트에서 제일 딱 들어맞는(best-fit) 노드들의 탐색을 반복합니다. 이 작업이 끝나고나서 의존 노드로 남아있는 노드들은 안전하게 동기화에서 제외시킬 수 있는 노드들입니다.

 

여기까지가 주어진 임의의 큐/노드 조합에서 최적 동기화 지점들을 찾기 위한 알고리즘의 마지막 열쇠입니다.

 

참고: 같은 큐 안에 있는 노드들을 의존 노드로 가지는 것은 간접 동기화들을 찾을 때에만 유용합니다. 이들은 펜스를 이용한 API 동기화로 변환되지 않습니다. 왜냐하면 같은 큐 에서의 작업은 동기화는 암묵적으로 이루어지기 때문입니다.
(*역: 같은 큐 내에서의 작업은 그 순서가 보존되므로, 별도의 동기화 없어도 된다는 뜻)

 

자 정리해보도록 합시다.

첫 번째 패스는 각 노드를 순회하면서 이들의 SSIS를 각 큐에서 가장 가까운 종속 노드를 찾음으로써 정하도록 하세요.

 동기화될 적절한 큐들의 리스트를 정하고 반복적으로 SSIS 비교를 통해서, 큐 동기화를 위한 모든 요구사항을 만족하는 가장 작은 노드들의 집합을 찾아서 쓸모없는 동기화를 제외시키기 위해서 두 번째 패스를 실행하세요.

그래프 사용하기 : 리소스 상태 전환

이제 상대적으로 쉬운 부분은 완성했으니 우리가 해놓은 것에 두꺼운 복잡함의 레이어를 추가해야하는 리소스 상태 전환으로 넘어가보도록 하죠. 가장 간단한 케이스들을 살펴보는 것부터 시작합시다. 제일 간단한 예시는 단일 큐에서의 렌더 패스들이나 서로 독립적인 여러 개의 큐들인 경우 일 겁니다.

 

단일 큐

 

한 쌍의 독립적인 큐들

이 경우엔 리소스 전환은 매우 직관적입니다: 렌더링 하고, 전환하고.. 지루할 정도로 이 두 가지 작업만이 반복되죠.

 

그런데 하나의 큐에 있는 렌더 패스가 다른 큐에서 만들어진 리소스를 사용하기 시작하면 일이 흥미로워지기 시작합니다.

교차 큐 리소스 읽기

여기엔 우리가 다뤄야 하는 두 가지의 제한 사항들이 존재합니다.

 

 첫 번째는, 리소스 상태가 전달받은 큐의 입장에서 지원하지 않는 상태일수도 있다는 것입니다.

예를 들어 그래픽스 큐에서 만들어진 RenderTarget은 컴퓨트 큐에서는 NonPixelShaderAccess로써 소비되야합니다.

 

 두 번째는, 일반 리소스는 여러 큐에 의해 읽힐 수 있으므로, 전환이 작업의 밖에 놓여서 그런 큐들에 대해 실행이 되어야 하고 따라서 동기화들도 보정되어야 한다는 것입니다.

 

 또한 리소스가 여러 큐에서 읽히지만, 전달받는 큐들의 일부 또는 전부가 일반 읽기 상태로의 전환을 지원하지 않는 것 처럼 위 두 가지 경우가 모두 섞인 경우도 발생할 수 있습니다.

 

 여기서 정확히 짚고 넘어가야 하는 것은 큐가 상태 전환을 지원하지 않더라도 여전히 그 상태에서 리소스를 사용할 수 있을지도 모른다는 것입니다. 즉, 상태 전환이 다른 어디선가 이루어져야 한다는 것입니다. (*역: 어떤 특정 상태로의 상태 전환은 불가능 하지만, 그 특정 상태에 있는 리소스를 사용하는 것은 가능하다는 것.)

 예를 들어, 만약 그래픽스 큐에서 만들어진 UnorderedAccess 리소스가 있다면. 이 리소스는 이후에 그래픽스 큐에선 PixelShaderAccess 그리고 컴퓨트 큐에서는 NonPixelShaderAccess로 읽힐 수 있고. 그러기 위해 UnorderedAccess를 양쪽 큐에서 모두 호환되는 결합된 읽기 상태로 전환해주어야 합니다 (AnyShaderAccess = PixelShaderAccess | NonPixelShaderAccess). 하지만 이런 형태의 전환은 컴퓨트 큐는 픽셀 쉐이더에 대해서는 아무런 정보가 없는 탓에, 오직 그래픽스 큐에서만 이루어질 수 있습니다. 다만, 컴퓨트 큐는 주어진 결합된 읽기 상태에서 NonPixelShaderAccess에만 신경을 쓰고, 다른 상태들을 자신이 알던 모르든 간에 무시하기 때문에. 다행히 AnyShaderAccess를 별 문제 없이 사용하게 됩니다.

 

그럼 이제 앞에서 논의한 문제들의 예시들을 몇 가지 살펴보고, 극복하기 위한 전략을 구상해봅시다.

 

호환되는 교차 큐 읽기

 자 여기 다른 큐에서 생성된 리소스를 읽고 모든 상태들이 호환돼서 상태 전환을 할 수 있는 큐가 있습니다. 이 경우에는 앞서 논의했던 알고리즘을 통해 찾아진 패스 사이에서의 동기화가 (동기화 지점) 자리에 그대로 남아있을 수 있고. 상태 전환도 리소스를 전달받은 큐에서 작업을 시작하기 전에 별 다른 문제 없이 이뤄질 수 있습니다.

 

그럼 다음으로는 같은 교차 큐 의존성 형태를 띄지만 그 안에 지원되지 않는 상태로의 전환이 존재하는 경우를 고려해봅시다.

 

큐 1이 리소스를 읽기 상태로 전환시키지 못한다고 한다면 그게 가능한 다른 큐를 찾아야만 합니다.

 그래픽스 API를 조금 추상화시켜서 그런 큐를 최적 큐(most competent queue)라고 부릅시다. 가령 큐 0이 그래픽스 큐이고 큐 1이 컴퓨트 큐라고 가정한다면. 동기화 지점과 전환 전략이 달라져야 합니다. 이제 리소스 상태 전환들을 최적 큐에 있는 별도의 커맨드 리스트로 우회(reroute) 시켜줘야 하고 양 쪽으로부터의 동기화들이 이 커맨드 리스트에 "플러그인" 되도록 재배치해야 합니다.

 

 이제 상태 전환은 상태 전환의 우회와 연관된 큐를 기다려야 하기 때문에. 동기화 최적화 알고리즘에 의해 고려되지 않았던 추가적인 동기화가 필요로 하게 됩니다. 그리고 상태 전환 이후에 동기화를 넣어 원래 큐들이 최적 큐에 동기화되도록 해주어야 합니다.

 

재배치된 전환들. 동기화들이 공통 상태 전환 커맨드 리스트에 "플러그" 되어있다.

(*역 : 위 사진에서, 큐 0의 리소스를 최적 큐에서 상태 전환을 이루어지게 하는데, 이때 최적 큐와 큐 1 사이에 동기화가 이루어지게 된다(원래 큐 0과 큐 1 사이에서 동기화가 이루어져야 했음))

 

 그럼 일반(상태) 리소스가 여러 개의 큐에게서 읽히는 경우는 어떨까요? 이때 사용되는 전략은 앞의 것과 꽤 비슷합니다. 상태 전환들을 최적 큐에 있는 별도의 커맨드 리스트로 옮긴(우회 시킨) 다음 (최적 큐가 실제로 리소스를 읽지 않는다고 해도) 큐들을 각 상태 전환들에 동기화시킵니다. 이것이 바로 다중 큐 읽기와 지원되지 않는 전환을 동일선상에서 제어하는 방법입니다.

 

 그럼 이제 우리가 제일 꺼리는 상황과 마주해봅시다(*원문: Now let's address an elephant in the room). 만약 개별적인 그룹에 속하는 큐들에서 교차-큐 읽기가 일어난다면 무슨 일이 일어날까요?

상호 의존적인 큐들의 분리된 모음(collection)들

이 경우엔 N개의 큐가 있고 M개의 패스가 있는 일반적인 경우에는 상호의존적인 큐를 가지는 분리된 모음들이 있는 더 복잡한 형태의 의존성을 가지게 되고 각 모음마다 내부에 최적 큐를 지정해주어야 합니다. 이제 우리 스스로 질문을 던져 보아야 합니다, 정말 이런 모음들까지 신경 써가면서 까지 일을 더 복잡하게 만들 필요가 있을까? 그리고 한 개 이상의 모음이 전환을 실행하기 위해 필요한 적합한 큐를 충분히 포함하지 못하면 어떤 일이 일어날까? 여기에 대한 답은 모든 게 갑자기 동기화 지옥으로 변해버릴 수 있기 때문에 어렵다 입니다. 우리는 이제 합리적으로 관리할 수 있고 성능이 좋은 하나의 알고리즘을 선택해서 정착해야만 합니다. 하지만 그전에 렌더 패스 재배열과 모든 개별적인 전환들을 이들 중 일부를 가까운 렌더 패스 작업에 넘겨주는 것 대신에 공통 커맨드로 옮기는 것에 대한 필요성을 살펴보도록 합시다.

 

 의존성 레벨 안에서 렌더 패스들의 임의적인 순서는 사실 최적의 순서는 아닙니다. 왜냐하면 API가 우리에게 분할 배리어(Split barriers)를 통해 앞서서 전환을 시작할 능력을 주었기 때문입니다. 이때 최적성(optimality)을 정하기 위한 측정 방법은 각 리소스 전환의 시작(Begin) 그리고 끝(End) 배리어 사이의 거리입니다. 전환과 관련된 멈춤(stall)들을 숨길 시간을 GPU에 더 벌어 주기 위해서 이 거리를 최대한 크게 만드는 것이 (성능적인-측면에서) 좋습니다. 그래서, 우리가 렌더 패스의 간격을 가능한 한 벌릴 수 있는 휴리스틱을 찾아내서 성능 측면에서의 승리를 축하할 수 있을까요? 개별적으로 생각한다면(*원문: In a vacuum), 네, 그럴 수 있습니다. 하지만 자세히 다시 생각해보도록 합시다. 다중 큐 리소스 읽기와 이들이 초래하는 동기화들을 생각해본다면, 전환 "간격"과 전환을 분리시키는 것은 실제로 성능상의 이점을 주기보다는 오히려 안좋은 영향을 끼치는 것을 알아챌 수 있습니다.

 

한번 한 의존성 레벨에서의 다중 패스들에 의한 다중큐 읽기의 예시를 보도록 하죠.

분리된 상태 전환의 요구사항으로 인해 의존성 레벨에서 개별적으로 동기화된 패스들

 

 우선 전환 사이의 시간적 거리(time distance)를 늘리고 싶기 때문에 각 패스에 개별적으로 적절하게 전환을 실시해주어야 합니다. 즉, 이제 더 이상 모든 전환들을 실시하는 한 개의 우회할 수 있는 커맨드 리스트를 가지지 못하고. 여러 개의 상태 전환 우회를 위한 커맨드 리스트를 가져야 하고 큐 0과 1에서의 각각의 작업 쌍들이 반드시 개별적으로 동기화되어야 한다는 것을 의미합니다. 이는 곧 작업의 병렬성을 망쳐버리게 됩니다.

 

나쁜 병렬화

 위 그림이 바로 우리가 교차 큐 리소스 읽기로 인해 다수의 동기화 지점들을 가지게 되었을 때 의존성 레벨 내에서 일어나게 되는 일입니다. 각 큐에서 심각한 멈춤(stall)이 일어나게 되죠.

 

한번 우리가 앞서 다루었던 한 개의 우회된 커맨드 리스트로 모든 전환들을 우회 시키면 어떤 일이 일어나는지 관찰 해봅시다.

 

의존성 레벨 내에서 일반적으로 전환되고 동기화된 패스들

 

이 예시에서는 똑똑한 패스 재배열과 개별 커맨드 리스트에서의 상태 전환 수행한다는 아이디어를 제외하였습니다.

 

좋은 병렬화

자 이제 동기화는 의존성 레벨의 시작 부분에서만 일어나므로 깔끔하게 병렬화된 작업을 얻습니다.

 

따라서, 교차 큐 의존성이 하나의 의존성 레벨 내에서 일어났을 땐, 다른 방법보다 전환들을 하나의 커맨드 리스트로 옮기는 것이 더 괜찮아 보입니다. 하지만 하나의 큐에서만 일어나는 작업을 가지는 복잡한 관계들 또는 의존성 레벨들과 연관이 없는 큐들에게는 어떨까요? 이들에 대해선 지능적인 패스 재배열과 리소스 전환 분리를 사용할 수 있을 것 같습니다. 실제로 그렇기도 하구요, 그러므로 우리는 실제로는 문제를 두 개의 케이스로 나누어야 합니다. 그리고 그렇게 하는 것은 상태 전환을 관리하기 위한 최종 알고리즘으로 우리를 이끌어줍니다.

개별 조건을 사용하여 다중 큐 읽기에서 연관된 큐들의 집합 모으기:만약 리소스가 종속 레벨에서 하나 이상의 큐로부터 읽힌다면, 그 큐들을 집합에 추가하세요. 그다음, 추가적으로, 상태의 비호환성으로 인한 상태 전환을 이동시킬 큐를 감지하고 그 큐도 같은 집합에 추가하세요. 이제 집합에서 최적 큐를 찾아서 앞에서 논의했듯이 모든 상태 전환과 동기화를 최적 큐로 우회(reroute) 시키세요. 아마 이런 복잡한 관계와 연관이 없는 큐들이 남을 것 입니다. 이 큐들은 동기화나 전환을 우회시키지 말고 처리하세요.

그래프 사용 하기 : API별 뉘앙스

이제 알고리즘에서 큰 부분은 끝났으니 작지만 여전히 중요한 문제들에 대해 논의 해보도록 합시다.

분할 배리어 (Split barriers)

 분할 배리어는 좋은 최적화 기법이지만, 언제나 그렇지는 않습니다. 분할 배리어는 실제론 동일한 Before 그리고 After 상태를 가지는 두 개의 배리어 이므로, 프레임을 스케줄링할 때 전달받는 큐 그리고 전달 하는 큐 양 쪽 모두 그런 상태와의 전환을 지원하는지 검사해야 합니다. 만약 그런 전환을 지원한다면, 분할 배리어를 사용하고. 그렇지 않다면, 전달 받는 큐에서만 일반적인 배리어를 사용합니다.

커맨드 리스트 일괄 배칭(batching)

 우리는 펜스 기다림 과/또는 신호에 둘러 싸인 커맨드 리스트들의 배열을 모읍니다. 각 배열(배치)는 개별적인 ExecuteCommandLists 호출을 나타냅니다.

 

 그래프의 의존성 레벨들을 통해서 먼저 큐에서 전환의 우회가 필요한 패스들을 다룹니다. 공통 전환 커맨드 리스트를 자신만의 배치로 이동시키고 앞에서 논의한 대로 (펜스의) 기다림과 신호들로 둘러쌉니다.

그다음 펜스 신호 요구가 감지될 때까지 같은 큐에 있는 패스들을 같은 배치에 추가시킴으로써 그 의존성 레벨에 있는 패스들을 배치합니다. 만약 신호가 감지됐다면, 이후의 렌더 패스들을 추가하기 위해 새로운 배치를 만듭니다.

 

 상태 큐에서 전환의 우회가 필요하지 않은 패스들을 배치할 때. 여기서도 비슷하게 배치에 패스들을 추가하고, 신호가 요구되면 새로운 배치를 만듭니다, 유일한 차이점은 wait를 요구하는 패스는 이전 배치에 머무르지 않고 새로운 배치로 추가됩니다.

GPU 메모리 로드

 앞의 내용뿐만 아니라 GPU 메모리 로드에 대해서도 신경 써주어야 합니다. 왜냐하면 다른 렌더러 디자인에서는 더 많은 리소스를 만들게 될지도 모르지만, 우리는 프레임 당 같은 리소스를 한 번만 생산 (쓰기)할 수 있다는 제한점을 가지고 있기 때문입니다. 이 문제를 해결하기 위해 동일한 속성들을 가지는 리소스들의 풀(Pool)을 사용하고 이름 앨리어싱 메커니즘을 사용하는 소위 DX11 스타일을 사용할 수 있겠지만. 최근에 들어서는 이러한 방법이 실제로 필요로 하진 않습니다. 새로운 API에서는 이 문제를 배정된 리소스(placed resources)에 대해 분리된 기간(겹치지 않는 기간) 내에서 사용되는 리소스 영역들을 중첩시킬 수 있도록 해주는 메모리 앨리어싱을 통해서 해결할 수 있도록 해줍니다.

 

 리소스 사용 타임라인을 사용해서 최적의 중첩된 메모리 공간을 찾기 위한 알고리즘은 이 아티클과 개별적인 사항이므로 별도의 아티클에서 다뤄보도록 하겠습니다.

그래프 사용 하기: 코너 케이스

 순환 의존성에 대한 참고 사항에서. 이전 프레임으로부터 시간적 재투영(temporal re-projection)을 하거나 재투영을 위해 쓰기전에 텍스처를 읽은다음, 현재 프레임 데이터를 다시 그 텍스처에 쓰고, 같은 프레임 내에서 다른 목적을 위해 다시 읽히는 경우같이 순환 참조가 필요한 경우가 생길지도 모릅니다. 만약 이런 시나리오를 가능하게 받아들인다면 순환 의존성을 해결하기 위해 엔지니어가 수동으로 조작할 수 있는 메커니즘을 가져야 할지도 모릅니다. 그리고 이러한 매커니즘은 최악의 대안이죠.

 

 더 나은 대안으로는 애초에 렌더 파이프라인이 순환 의존성 의존성을 가지지 않도록 설계 하는 겁니다. 위의 예시의 경우 하나의 텍스처를 사용하는 대신 두 개의 텍스처를 사용해서 현재의 텍스처에 쓰기 위해서 이전 프레임으로 부터 텍스처를 스케쥴링 하지 않고 프레임들 사이에서 두개의 텍스처들을 핑퐁(ping-ponging) 시키는 것으로 해결될 수 있습니다.

 

 추가적인 예를 하나 더 들어보자면, 하나의 렌더 패스에서 이미지를 구별하여 블러시킬때, 읽기-쓰기 리소스 접근이 필요할 수도 있습니다. 해결법은 그래프를 구축할 때 이 경우를 쓰기 전용 의존성으로 취급해서, 그 무엇도 실제로 우리가 나중에 동일한 렌더 패스 내부에 있는 리소스를 쓰고 읽는 것을 막을 수 없도록 하는 것입니다.

 

 우리에게 남겨진 또 다른 문제는 다중 쓰기 의존성입니다. 렌더 패스가 이미 존재하는 대상의 일부에 대해서만 쓸 때는, 메모리 대역폭 소비를 줄이기 위해 다중 패스들 내부의 같은 리소스에 쓰는 것이 바람직할 수도 있습니다. 이런 경우 다중 쓰기 의존성이 일어났을 때 이를 악물고 엔지니어들에게 렌더 패스의 순서를 해결하기 위한 추가적인 메커니즘을 제공해야 할지도 모릅니다. 간단한 예시를 들어보죠: A 쓰기, A 읽기, A 쓰기. 과연 어디에 읽기 렌더 패스가 놓여야 할까요? 첫 번째 쓰기 이후 아니면 두 번째 이후에?

 

 한 가지 방법은 "순서가 정해지지 않은" 렌더 패스의 초기 리스트를 살펴보고 이걸 힌트로써 사용하는 겁니다. 이건 당연히 초기에 그래프에 랜덤 한 순서로 렌더 패스를 던져 넣는 게 아니라, 추가하는 순서가 반드시 최종 실행 순서와 비슷해야 한다는 것을 의미합니다.

 

 그래프가 모호성을 발견했을 때 참고하는 규칙들의 모종의 리스트를 구현하는 것도 또 다른 해결법이 될 수 도 있습니다.

결론

우리는 모던 그래픽스 API가 제공하는 낮은 수준의 프레임 제어를 실제로 활용하기 위해 꽤 많은 일들을 해결했으므로 지금쯤 프레임 워크로드에 대한 고수준의 이해 없이 즉시 모드(immediate-mode)로 모든 것을 일관성 있게 만들기 위해 드라이버가 이전에 어떤 과정(hoops)들을 통과했는지 상상할 수 있을 것입니다. 각 엔진에서는 다른 디자인이 요구될지도 모르기 때문에, 저는 여기서 이 방법이 최선이라고 말씀드리지는 않겠습니다. 하지만 위에서 살펴 보았던 접근 방법들이 하나의 좋은 절충안이 될 것이라고 생각합니다.