PGCL+ (Parallel Graph Component Labeling and Linking)

  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]을 기록한다.
  

Figure 2. PGCL+ InitLink 2

  
  마지막 단계에서는 클러스터에 속하는 각 쓰레드로 하여금 해당 클러스터와 좌표를 수정하도록 함으로써 최종 좌표와 크기를 계산하도록 한다.
  

Figure 3. PGCL+ Link

  
  ※ 이 글의 저작권은 유진인스텍(주)와 (주)웨이브앤프랙탈에 있습니다.
  

---

[1] 다수의 쓰레드가 동일한 변수를 경쟁적으로 변경하는 경우이므로, exclusive access가 보장되도록 해야 한다.

[2] 클러스터에 속하는 결함픽셀의 수와 일치한다.