WebGL2에서 GPGPU 바이트 닉 정렬

이전 기사에서 JavaScript로 바이트 닉 정렬을 구현해 보았습니다.
자바 스크립트에서 바이트 닉 정렬 - Qiita

알고리즘을 이해할 수 있었으므로, 바이트 닉 소트의 본령이 발휘할 수 있는 WebGL로 GPGPU 바이트 닉 소트를 구현해 보았습니다.

WebGL에서는 사이즈가 2의 n승의 텍스처를 준비해, 그 텍스처에 오프 스크린 렌더링으로 몇번이나 도중 상태를 기입하면서 값을 소트 해 갑니다. 텍스처는 2차원입니다만, 내부에서는 텍셀의 값을 바탕으로 1차원으로 변환해 소트를 실시하고 있습니다.

이하는 바이트 닉 소트의 진행해 가는 과정의 텍스처의 모습이 되고 있습니다. 최종적으로 좌하가 작은 값(흑), 우상이 큰 값(흰)이 되어 갑니다.



길기 때문에 소스 코드 전문은 게재하지 않습니다. 이 기사에서는 요점만을 해설해 갑니다.
Github에 소스 코드를 넣어 두었으므로 전체 텍스트를 확인하십시오. 실제로 움직이는 것도 볼 수 있습니다.
aadebdeb/WebGL2_BitonicSort: GPGPU Bitonic Sort with WebGL2

먼저 텍스처를 초기화합니다. 이번에는 시각화 할 때 알기 쉽도록 아래 셰이더에서 0에서 1까지의 임의 값을 각 텍셀에 씁니다.

#version 300 es

precision highp float;

out float o_value;

uniform vec2 u_randomSeed;

float random(vec2 x){
  return fract(sin(dot(x,vec2(12.9898, 78.233))) * 43758.5453);
}

void main(void) {
  o_value = random(gl_FragCoord.xy * 0.01 + u_randomSeed);
}

JavaScript 버전 바이트 닉 정렬 에서는 bitonicsort 함수로 이중 루프를 돌려, kernel 함수로 스왑 처리를 실시하고 있었습니다. bitnoicsort 함수의 이중 루프는 WebGLb판에서도 다음과 같이 똑같이 실시합니다만, kernel 함수로 하고 있는 처리는 프래그먼트 쉐이더를 이용해 실시합니다.

for (let i = 0; i < sizeN; i++) {
  for (let j = 0; j <= i; j++) {
    executeKernel(writableFramebuffer.framebuffer, readableFramebuffer.texture, textureSize, i, j);
    swapFramebuffer();
  }
}

executeKernel 함수는 다음 단편 셰이더를 사용하여 스왑 처리를 수행합니다. 하는 것은 JavaScript 버전 바이트 닉 정렬의 마지막에 게재한 코드와 같습니다. u_blockStep 와 u_subBlockStep 가 Javascript판의 kernel 함수의 인수 p , 와 q 에 각각 대응하고 있습니다. 2차원의 좌표로부터 1차원의 인덱스로의 변환과 그 역방향으로의 변환을 실시하기 위해서 convertCoordToIndex 와 convertIndexToCoord 를 정의하고 있습니다.

#version 300 es

precision highp float;

out float o_value;

uniform sampler2D u_valueTexture;
uniform uint u_size;
uniform uint u_blockStep;
uniform uint u_subBlockStep;

uint convertCoordToIndex(uvec2 coord) {
  return coord.x + coord.y * u_size;
}

uvec2 convertIndexToCoord(uint index) {
  return uvec2(index % u_size, index / u_size);
}

void main(void) {
  uint index = convertCoordToIndex(uvec2(gl_FragCoord.xy));
  uint d = 1u << (u_blockStep - u_subBlockStep);

  bool up = ((index >> u_blockStep) & 2u) == 0u;

  uint targetIndex;
  if ((index & d) == 0u) {
    targetIndex = index | d;
  } else {
    targetIndex = index & ~d;
    up = !up;
  }

  float a = texelFetch(u_valueTexture, ivec2(gl_FragCoord.xy), 0).x;
  float b = texelFetch(u_valueTexture, ivec2(convertIndexToCoord(targetIndex)), 0).x;
  if ((a > b) == up) {
    o_value = b; // swap
  } else {
    o_value = a; // no_swap
  }
}

추가

여기까지 소개한 구현에서는 1개의 값 밖에 가지지 않는 배열을 소트 하는 경우를 예로 했습니다. 이 때는 값이 같은 때에는 스왑해도 하지 않아도 어느 쪽이라도 문제 없었습니다. 그러나, vec2 등 2개 이상의 값을 가지는 배열을 그중의 1 요소로 소트 하는 경우에는, 이하와 같이 같은 값일 때에 반드시 스왑할지 스왑하지 않는지를 결정해 두지 않으면 안됩니다 응.

  vec2 a = texelFetch(u_valueTexture, ivec2(gl_FragCoord.xy), 0).xy;
  vec2 b = texelFetch(u_valueTexture, ivec2(convertIndexToCoord(targetIndex)), 0).xy;
  if ((a.x == b.x || (a.x > b.x) == up) { // x要素でソート, 値が同じときは必ずswapする
    o_value = b; // swap
  } else {
    o_value = a; // no_swap
  }