Wave & Fractals: PGCL+

  PGCL+는, data-parallel 알고리즘을 사용하여, labeling된 이미지로부터 동일한 라벨을 갖는 픽셀을 연결(linking)하여 클러스터를 찾고 그 위치와 크기 및 클러스터의 수를 계산하기 위한 것이다.

PGCL+는 내부적으로 GPU 메모리 상에 2 개의 변수를 관리한다. 하나는 각 클러스터에 속하는 오직 한 개의 쓰레드만이 전체 클러스터 수를 증가시키도록 하기 위한 변수(V₁)이며, 또 다른 하나는 클러스터 전체 수를 저장하기 위한 것(V₂)이다.

PGCL+ V₁ 변수

  V₁은 결함이미지의 전체 픽셀 수와 같은 크기의 배열로서, 배열의 각 원소는 uint2 구조체(struct)이다. 구조체 uint2는 unsigned int형 변수 2 개를 원소로 가지며, 이들 은 각각 '변수이름.x' 및 '변수이름.y'로 참조할 수 있다.

  V₁ 배열 각 원소의 '.x' 원소는 Per-Cluster Cardinal Counter이다. 동일한 클러스터에 속하면, 즉 라벨이 같은 픽셀을 담당하는 쓰레드들은 V₁의 해당 라벨 위치의 값을 1만큼 증가^[1]시킨다(Figure 1 참조).

  '.y' 원소는 Inter-Cluster Ordinal Counter이다. 쓰레드들이 동시에 수행되더라도, 동일한 변수를 변경하는 경우 강제적으로 시차를 두게 함으로써 클러스터에 순서를 부여한다.

Figure 1. PGCL+ InitLink 1

  PGCL+는 세 단계를 거친다.

첫 번째 단계에서는 각 쓰레드로 하여금 해당하는 V₁의 원소 중 '.x' 원소를, 더불어 첫 째 쓰레드 블록의 첫 째 쓰레드로 하여금 V₂를 0으로 초기화하도록 한다.

  두 번째 단계는, Figure 1과 같이, 결함픽셀을 담당하는 각 쓰레드로 하여금 Per-Cluster Cardinal Counter를 1만큼씩 증가시키도록 한다.

이 과정에서 Counter를 0에서 1로 증가시키는 쓰레드가 클러스터마다 유일하게 식별된다(Figure 1의 경우 Thread ID 57, 67, 172, 215에 해당). 이들 쓰레드로 하여금 V₂를 1만큼씩 증가시키도록 하면서 클러스터의 순서를 파악하고, Figure 2와 같이, 해당 쓰레드의 좌표와 Cardinal Counter의 값^[2]을 기록한다.