Home

GPU는 데이터 병렬성을 지원하는 아키텍쳐로서 ACS 알고리즘과 같이 에이전트들이 서로 다른 데이터에 대해 동일한 연산을 수행하는 형태의 알고리즘에 적합한 구조이다. 특히, TSP 해결에 필요한 인접 도시의 적합도 판정(Fitness calculation), 여정 생성(Tour construction), 페로몬 업데이트(Pheromone update) 등은 대규모 행렬 데이터에 대한 GPU 병렬처리가 성능의 관건이다.

GPU 장치는 다수의 SM(Streaming Multiprocessor)로 구성되고, 각 SM은 내부에 SIMD 형태로 실행되는 많은 수의 stream processor(또는 core)를 갖는다. 특히 GPU 메모리 시스템은 전역 메모리(Global memory)와 공유 메모리(Shared memory)의 계층 구조를 갖는데, 전역 메모리는 CUDA 커널의 모든 쓰레드들이 접근 가능한 메모리이나 매우 느린 반면, 공유 메모리는 각 쓰레드 블록(Thread block) 내의 모든 쓰레드가 공유하는 메모리로 빠른 접근시간을 지원한다.

따라서, 데이터 병렬성이 높은 알고리즘을 GPU에서 구현할 때 전역 메모리 접근 횟수를 줄이고, 공유 메모리를 적극 활용하는 것이 필요하다. 특히 GPU에서 전역 메모리 접근이 차지하는 오버헤드가 매우 크므로 같은 블록 내의 쓰레드들이 전역 메모리의 연속된 주소들에 동시에 접근할 때 GPU에서는 이를 한꺼번에 처리하여 메모리 접근의 대역폭을 최대한 활용하는 병합 접근(Coalesced access)을 지원하도록 코드를 구성한다.

본 논문에서는 Nvidia에서 제공하는 CUDA(Compute Unified Device Architecture) 프레임워크를 사용해 병렬 프로그램을 개발했다. CUDA는 다수의 쓰레드들의 집합인 쓰레드 블럭의 개념을 지원하는데, 한 쓰레드 블럭은 한 개의 SM에 배치되고, 한 쓰레드는 그 안에서 하나의 코어에서 실행된다.

한편 SM 내에서는 각 쓰레드 블럭을 구성하는 t쓰레드들을 워프(Warp)라고 부르는 32개의 쓰레드 단위로 나누어 이들을 차례로 스케줄링을 한다. 따라서, 각 SM에 충분한 블럭들이 배치되지 않는 경우 자연히 스케줄링 워프의 개수도 적어지게 되어 SM 자원을 효과적으로 활용하지 못하는 문제가 나타나므로, 프로그램 개발자는 GPU의 전체 SM에 고르게 많은 쓰레드 블럭들이 생성되도록 알고리즘을 설계해야 한다.

본 연구에서 제안하는 알고리즘은 여정 초기화(Tour initialization), 방문 적합도 계산(Visit fitness calculation), 여정 구성(Tour construction), 여정 정리(Wrap-up tour), 페로몬 업데이트(Pheromone update)의 5개 커널로 구성되고 다음에 각각 상세히 소개된다.

ACS 알고리즘은 만족할 만한 최적해가 구해질 때까지 이 커널들을 반복 실행함으로써 TSP의 최단 경로를 계속 업데이트하게 된다. 본 연구에서 사용한 도시 그래프에서는 임의의 두 도시 간에 경로가 존재한다고 가정한다. 즉, 어떤 도시 v_i로부터 임의의 다른 도시 v_j로 가는 경로가 존재하며 이 커널은 각 도시 v_i의 위치가 (x_i, y_i)로 표현된 n개의 도시에 대해 임의의 구간 거리 d_i,j( > 0)를 구하고 해당 구간의 페로몬 τ_i,j를 적당한 초기 상수(여기서는 1/n)으로 설정한다.

(1) 여정 초기화 커널

각 개미별 초기 도시 위치를 정하고 여정의 경로 방문 정보와 경로 길이를 초기화한다. 본 구현에서는 블록 크기(=블럭 내 쓰레드의 수)를 32개로 설정하고 개미의 수(n_ant)를 32로 나눈 수, 즉 ⌈n_ant⌉/32개의 블록들을 생성하는 CUDA 커널을 작성한다.

(2) 방문 적합도 계산 커널

임의의 도시 v_i에서 나머지 모든 도시 v_j에 대해 방문 적합도(fitness)를 다음과 같이 계산한다. 이 식에서 α, β는 페로몬과 거리의 영향력을 각각 통제하기 위한 상수이다.

이 커널은 전체 도시 행렬 n × n에 대해 각 32 × 32 크기의 블록을 ⌈n/32⌉×⌈n/32⌉개 병렬 생성한다. 이 때 생성된 블록의 각 쓰레드는 자신이 담당한 도시 구간 (i,j)에 대해 전역 메모리의 배열에서 해당 페로몬 값 τ_i,j와 구간 거리 d_i,j를 읽어 위의 식을 계산하므로 자연스럽게 메모리 병합 접근이 활용될 수 있다.

(3) 여정 구성 커널

각 개미 쓰레드는 자신이 탐색할 여정을 확률 과정(Stochastic process)을 통해 구성한다. 그림 1은 6개의 인접 도시에서 1개를 선택하는 과정을 예로 보여준다. 우선 visited 배열은 각 도시에 대해 이미 방문했는지 여부를 기록하고, fitness 배열은 (2)의 과정을 통해 각 도시의 선택 적합도(또는 강도)를 나타낸다.

Fig. 1. 
Selection process example for a next visiting city

선택 과정에 앞서 visited, fitness 배열을 통해 각 도시에 대한 선택 확률을 구한다. 이를 위해 이미 방문한 도시는 제외하고, 나머지 도시들의 fitness 값의 합한 후, 이 합계(sum of fitness)에 대한 각 fitness의 비율을 해당 도시의 선택 확률(prob)을 계산한다. 당연히 이미 방문한 도시의 확률은 0이다. 그리고, 다음과 같이 누적확률분포(Cumul)를 구한다.

다음 단계에서 (0, 1) 사이의 난수를 생성하고, cumul 배열에서 이 값이 속하는 구간을 구해 다음 도시를 결정하게 된다. 이 때 난수 생성 함수는 CUDA가 제공하는 cudaRandom 함수를 사용하는데, 이 함수는 각 개미 쓰레드마다 서로 다른 seed를 설정하고 이를 curandState 객체를 통해 관리한다.

현재 구현한 알고리즘은 개미별로 여정을 생성하기 때문에 개미의 수가 병렬성을 제한한다. 또한, 각 여정 생성 시 다음 도시를 선택하는 과정이 순차적으로 실행됨으로써 병렬 효과를 기대하기 어려운 문제가 있다. 그럼에도 현재 각 블록을 32개의 쓰레드로 구성하여 전체 개미들을 블록으로 나누어 구성함으로써 GPU의 블록 점유도(Block occupancy)를 비교적 높게 유지했다. 이에 반해, 만일 한 여정의 병렬화를 극대화하기 위해 도시의 수만큼의 쓰레드로 구성된 블록을 생성하는 경우, 이 블록이 하나의 SM(Streaming Multiprocessor)의 스케쥴 자원을 과도하게 사용하여 오히려 성능이 크게 느려짐을 확인할 수 있었다.

(4) 여정 정리 커널

앞서의 (2)에서 얻어진 각 여정의 길이(여정에 속한 경로의 합)는 그때까지 발견된 최단 경로와 비교되고 더 짧은 경로일 경우 갱신된다. 이 과정 역시 최단 경로를 저장한 전역 변수에 대한 모든 쓰레드의 동시 접근이 이루어지므로, 이의 동기화를 제어하기위해 CUDA에서 제공하는 atomicMin 함수를 사용한다. 그러나, 이 함수의 사용 시 쓰레드의 병행성(Concurrency)이 낮아져 병렬화에 의한 성능 향상을 제약하고 있다.

또한, 이번에 이동한 여정을 구성하는 각 경로에 포함된 구간 (v_i, v_j)에 페로몬의 증가량을 기록하는 2차원 배열 원소 δ_i,j에 기록한다. 이 커널 역시 각 블록을 32개의 쓰레드로 구성하고 전체 개미들을 이 크기의 블록들로 나누어 구성하였다.

(5) 페로몬 업데이트 커널

여정 정리 커널을 통해 각 개미가 선택한 여정에 대한 평가가 이뤄지면, 전체 경로에 대해 페로몬 영향력을 업데이트해야 한다. 여기에는 크게 (i) 시간이 지남에 따른 페로몬의 감소와 (ii) 앞서 각 개미가 선택한 경로에 더해진 페로몬의 양(δ[i][j])을 다음과 같이 반영한다.

• (i) τ_i,j = (1 - ρ) τ_i,j (ρ는 페로몬의 증발율 상수)
• (ii) τ_i,j = τ_i,j + δ_i,j

이 커널 역시 전체 도시 행렬 n × n에 대해 각 32 × 32 크기의 블록을 ⌈n/32⌉×⌈n/32⌉개 병렬 생성한다. 이 때 생성된 블록의 각 쓰레드는 자신이 담당한 도시 구간 (i,j)에 대해 전역 메모리의 배열에서 해당 페로몬 값 τ_i,j와 구간 페로몬 증가량 δ_i,j를 읽어 위의 식을 계산하므로 병합 접근이 효과적으로 활용될 수 있다.

(1) 도시 간 평균 거리와 편차를 구하는 커널

일반적인 ACS 알고리즘에서 여정 생성 시 다음 도시는 확률적 사건으로 선택한다. 그러나, 밀집된 도시 분포 그래프의 경우, 인접 도시는 대개 일정 거리 내에 위치할 확률이 매우 높다. 따라서, 본 연구에서는 다음 도시를 일정 거리 내에서 우선 선택하도록 알고리즘을 수정 구현하였다.

이를 위해 모든 도시 간 거리를 합하고 이의 평균(μ)과 표준편차(σ)를 구하는 커널을 작성한다. 이때 n × n 도시 행렬에 대해 도시 간 거리 행렬 D를 구한 후, 쓰레드 i가 도시 i로부터 모든 다른 도시 j간의 합을 구하는 작업 병렬성을 이용하는 쓰레드 블록을 생성한다. 이 때 각 쓰레드는 자신이 구한 local_sum을 atomicAdd를 사용해 global_sum에 더하고, 최종적으로 한 쓰레드가 평균값을 계산한다. 블록의 크기를 32로 설정하고 도시의 수(n)를 32로 나눈 수, 즉 ⌈n/32⌉개의 블록들을 생성하는 커널을 작성한다. 편차를 구하는 커널 역시 이와 동일한 방법을 사용하며, 각 쓰레드는 계산된 평균과 각 도시 간 거리의 차와 그 제곱의 합을 구한 후 종적으로 편차를 계산한다.

(2) 여정 생성 시 근접성을 활용하는 커널

여정 생성을 위해 앞서 3.2절의 (3)에서 기술한 확률 과정을 동일하게 사용된다. 다만, 근접성을 활용하기 위해, 현재 도시 i에서 확률 시행을 통해 선택된 도시 j와의 거리 d_i,j의 값을 살펴보고 근접 조건을 확인한다.

첫 시행에서의 근접 조건 |d_i,j - μ| ≤ σ인 경우 해당 도시 j를 다음 선택지로 채택한다. 만일 근접 조건을 만족하지 않을 경우 재시행하고, 2차 근접 조건 |d_i,j - μ| ≤ 2σ를 만족하면 다음 선택지로 채택한다. 만일 2차 근접 조건을 만족하지 않는 경우, 아직 방문하지 않은 도시 중 가장 큰 fitness를 갖는 도시를 다음 방문지로 선택한다.

ACS를 이용한 TSP 알고리즘은 여러 차례의 반복 실행을 통해 근사 최적해를 구하지만, 알고리즘의 성능 비교를 위해서는 1회 반복에 소요된 실행 시간을 측정하였다.

표 2에 보이는 바와 같이, bier127을 제외하고 대체로 10.13~11.37배의 성능 향상을 보였는데, 이는 도시 간 거리 정보와 페로몬 잔량을 저장하는 N_city × N_city 행렬에 대해 32 × 32 병렬 블록에 의한 데이터 분산처리 효과와 연속 메모리 공간에 대한 병합 접근 효과로 분석된다.

다만, bier127의 경우 4.82배의 비교적 낮은 성능향상을 보인 것은 앞서 언급한 병렬처리 효과에 비해 여정 생성 과정에서 다음 방문 도시를 선정하는 순차적 과정이 차지하는 비중이 상대적으로 높고, 페로몬 업데이트 과정에서 사용한 atomicMin 함수가 상당한 비용을 요구하기 때문으로 분석된다.

앞서 제안한 대로 ACS 알고리즘에 노드 간 근접성을 활용한 버전을 구현하고 실험하였다. 실험 방법은 (1) 근접성에 따른 재시도가 없는 방법(No retry), (2) 1차 근접성(평균과의 차이 σ 이하)을 확인 후 1회 재시도를 하는 방법 (1 retry), (3) 1차 근접성과 2차 근접성(평균과의 차이 2σ 이하) 확인 후 재시도하는 방법(2 retries)으로 나누어 실험하였다. 실험 데이터로는 노드 수와 노드 간 분포의 복잡도가 중간 정도인 TSPLIB의 lin318 데이터를 선정하고, 반복 횟수는 30회로 제한하였다.

3가지 방식에서 두드러진 차이는 초기 결과값의 업데이트 속도이다. 근접성을 적용하지 않은 경우에 매우 큰 값에서 초기해가 시작되고, 전체적으로 근접성을 강화한 알고리즘의 초기해가 더 작은 값부터 시작해 최적해를 향해 빠르게 수렴한다.

또한, 그림 2의 결과에 보이는 바와 같이 근접성을 고려한 경우에 최종 최단경로(근사 최적해)가 더 우수함을 볼 수 있다. No retry의 경우에 최종 결과는 45038, 1 retry의 경우는 43421, 2 retries의 경우는 42857로 각각 나타났다. 다만, 3 방법 모두에서 15회 반복 이후에는 최단경로가 갱신되지 않는 한계를 보인다.

Fig. 2. 
Experiment results by exploiting proximity

그림 3은 3 방법에 의해 각각 구해진 최종 결과의 경로 연결 상태를 그림으로 비교한 것이다. 근접성을 고려하지 않은 경우 먼 거리의 노드 간 연결로 인해 최단 경로 탐색이 제약을 받는데 반해, 근접성을 고려한 경우 인근 노드로의 우선 연결로 점진적인 최단 경로 탐색이 이뤄짐을 볼 수 있다.

Fig. 3. 
Comparison of final results by exploiting proximity

개미의 수, 즉 병렬처리 쓰레드의 수에 따른 성능을 살펴보기 위해 도시의 수와 동일한 수의 개미와 2배수, 4배수, 8배수의 개미를 각각 생성하는 실험을 앞서의 4 데이터에 대해 수행하고, 각 개미의 수에 대해 동일한 실험을 10회 반복하였다.

이전의 ACS 연구에서는 도시의 수 이하의 개미를 생성하여 실험했지만, GPU의 고성능으로 수십만 개 이상의 병렬 쓰레드를 생성하는 것이 가능하다.

표 3의 결과는 10회 실행에서 best 결과와 평균 결과를 보여준다. 전체적으로 개미의 수를 증가시키는 것이 근사 최적해의 품질을 높이는데 기여한 것으로 나타났다. 또한 개미의 수가 많을 수로 빠른 속도로 최적값을 향해 수렴해 가는 경향을 보였다. 이것은 높은 병렬성이 순차적 반복 계산을 일정 부분 보상하는 것으로 분석된다.

한편 bier127과 lin318과 같이 규모가 크지 않은 데이터의 경우 4배수와 8배수 개미를 각각 투여한 결과는 근소한 차이를 보였다. 이는 주어진 데이터 크기에 비해 일정 정도 이상의 병렬성은 성능 개선에 한계를 갖는 것으로 보인다.

이상의 실험을 통해 ACS 알고리즘이 일정한 품질의 결과를 얻기 위해 적어도 데이터 크기에 상응하는 개미와 일정 횟수 이상의 반복 계산이 절대적임을 확인할 수 있다. 특히 일정 수준 이상의 병렬처리 성능이 제공되어야 고품질의 결과를 보장받을 수 있다는 점은 CPU 기반으로 ACS를 구현하는 것이 성능 면에서 한계에 다다랐음을 보여준다. 더욱이 수백 또는 수천 개의 데이터에 대해 ACS 알고리즘을 수행할 때, CPU에서 개미의 수를 그 수준으로 생성, 활용한다는 것은 그 수 만큼의 반복 연산을 일으켜 결국 GPU 기반 병렬 알고리즘과 성능 차이는 더욱 크게 벌어질 것으로 예상된다.