[OpenCL] 다익스트라 알고리즘 (Dijkstra Algorithm)

pikamon·2021년 2월 2일

목록 보기

4/4

개발 환경 설정은 아래 링크를 참고하자.
https://velog.io/@pikamon/OpenCL-1

1. 다익스트라 알고리즘

다익스트라(Dijkstra) 알고리즘이란 노드 간 최단 경로를 구하는 대표적인 알고리즘 중 하나이다. 노드와 노드 간에 음이 아닌 가중치를 갖는 간선으로 이루어진 그래프가 주어질 때, 다이나믹 프로그래밍(Dynamic Programming) 기법을 이용하여 한 노드에서 다른 노드까지의 최단거리를 구한다. 시간 복잡도는 구현 방법에 따라 O(|E| * log|V|) 또는 O(|V|^2+|E|) 등으로 나뉘어진다.

2. 일반적인 구현

위와 같은 그래프가 주어졌을 때, 정점 A에서 E로 가는 최단거리의 가중치 합을 구하는 다익스트라 알고리즘은 아래와 같다.

dijkstra.c

#include <stdio.h>
#include <stdlib.h>

#define N 5
#define X 1000000007

int main(void)
{
	int graph[N][N] = {
		{ 0, 2, 3, 5, X, },
		{ 2, 0, X, 2, X, },
		{ 3, X, 0, 2, X, },
		{ 5, 2, 2, 0, 1, },
		{ X, X, X, 1, 0, },
	};
	int visited[N] = { 0, };
	int dist[N];
	int start, end;

	// 시작, 끝 노드 설정
	start = 0;
	end = 4;

	for (int i = 0; i < N; i++)
	{
		dist[i] = X;
	}

	// 다익스트라 알고리즘 시작
	dist[start] = 0;

	for (int i = 0; i < N; i++)
	{
		int min = X;
		int v = 0;

		for (int j = 0; j < N; j++)
		{
			if (visited[j] == 0 && min > dist[j])
			{
				min = dist[j];
				v = j;
			}
		}

		visited[v] = 1;

		for (int j = 0; j < N; j++)
		{
			if (dist[j] > dist[v] + graph[v][j])
			{
				dist[j] = dist[v] + graph[v][j];
			}
		}
	}

	// 결과 출력
	printf("%d\n", dist[end]);

	system("pause");

	return 0;
}

최단 경로는 A - B - D - E 이며 가중치 합은 5이다.

컴파일 후 실행하면 아래와 같이 최단 경로의 가중치 합이 출력되는 것을 볼 수 있다.

3. OpenCL로의 변환

1. 변환의 필요성

실생활을 예로 들면, MRI 장비로 측정한 인간의 대뇌 피질 이미지를 분석하여 이를 삼각형 메쉬구조로 모델링할 수 있는 툴이 있다고 한다. 모델링된 그래프는 일반적으로 위에서 본 노드와 간선을 가진 형태인데, 노드와 간선의 수가 굉장히 많아서 CPU만으로는 원하는 계산을 모두 수행하기 버겁다는 문제가 있었다고 한다. 그래서 병렬처리를 이용하여 연산 속도를 늘릴 방법이 필요했다고 한다.

2. 그래프 자료구조

논문 Accelerating Large Graph Algorithms on the GPU using CUDA 에서는 호스트에 있는 어떤 사용 가능한 계산 하드웨어에서도 수행할 수 있는 다익스트라 알고리즘을 구현했다고 한다.

가장 중요한 것은 멀티코어 프로세서에서 효율적으로 접근할 수 있도록 그래프 자료구조를 구성하는 것이라고 하는데, 위 논문에서는 아래와 같이 세 가지 배열을 이용하였다고 한다.

vertexArray : vertexArray 배열의 각 원소는 이 점에 연결되어 있는 선들 중에서 첫 번째 선에 해당하는 edgeArray 원소를 가리키는 인덱스 값이다.

edgeArray : edgeArray에는 현재 노드에서 이 선에 연결되는 노드의 번호가 저장된다.

weightArray : weightArray 배열의 각 원소는 edgeArray의 각 원소의 가중치를 나타낸다.

일반적으로 우리가 그래프를 표현할 때 사용하는 모든 n×n 행렬이나 희소행렬을 위 1차원 배열 3개로 변환할 수 있는데, OpenCL에서는 이 변환된 형태의 배열을 이용하여 계산을 수행한다.

용어 설명이 어려울 수 있는데, 아래의 예제를 통해 이해해보자.

예제 1. vertexArray, edgeArray, weightArray 구하기

위와 같은 양방향 그래프가 있다고 하자. 노드 A~E를 각각 0~5번째 노드라고 할 때, 이를 간선 기준으로 아래와 같은 희소행렬로 나타낼 수 있다.

int edges[][3] = {
	{ 0, 1, 2 },
	{ 0, 2, 3 },
	{ 0, 3, 5 },
	{ 1, 3, 2 },
	{ 2, 3, 2 },
	{ 3, 4, 1 },
};

이를 단방향 그래프로 바꾸면 아래와 같다.

int edges[][3] = {
	{ 0, 1, 2 },
	{ 0, 2, 3 },
	{ 0, 3, 5 },
	{ 1, 0, 2 },
	{ 1, 3, 2 },
	{ 2, 0, 3 },
	{ 2, 3, 2 },
	{ 3, 0, 5 },
	{ 3, 1, 2 },
	{ 3, 2, 2 },
	{ 3, 4, 1 },
	{ 4, 3, 1 },
};

여기서 vertexArray, edgeArray, weightArray를 구하면 아래와 같다.

int edges[][3] = {
	{ 0, 1, 2 },  /* 0 */
	{ 0, 2, 3 },
	{ 0, 3, 5 },
	{ 1, 0, 2 },  /* 3 */
	{ 1, 3, 2 },
	{ 2, 0, 3 },  /* 5 */
	{ 2, 3, 2 },
	{ 3, 0, 5 },  /* 7 */
	{ 3, 1, 2 },
	{ 3, 2, 2 },
	{ 3, 4, 1 },
	{ 4, 3, 1 },  /* 11 */
};

int vertexArray[5]	= { 0, 3, 5, 7, 11 };
int   edgeArray[12]	= { 1, 2, 3, 0, 3, 0, 3, 0, 1, 2, 4, 3 };
int weightArray[12]	= { 2, 3, 5, 2, 2, 3, 2, 5, 2, 2, 1, 1 };

vertexArray[i]의 각 원소는 i번째 노드에 대한 간선이 시작되는 위치임을 알 수 있다.
edgeArray[i]의 각 원소는 희소행렬에 정의된 도착노드임을 알 수 있다.
weightArray[i]의 각 원소는 희소행렬에 정의된 가중치임을 알 수 있다.

예제 2. 원래 행렬로 복원하기

아래 코드를 실행하면 우리가 구한 vertexArray, edgeArray, weightArray로부터 원래의 희소행렬 그래프를 복원할 수 있는 것을 볼 수 있다.

#include <stdio.h>
#include <stdlib.h>

#define V 5
#define E 12

int main(void)
{
	int vertexArray[V + 1]	= { 0, 3, 5, 7, 11, E };
	int   edgeArray[E]		= { 1, 2, 3, 0, 3, 0, 3, 0, 1, 2, 4, 3 };
	int weightArray[E]		= { 1, 3, 1, 5, 2, 3, 5, 5, 2, 5, 2, 2 };

	for (int index = 0; index < V; index++)
	{
		int srcNode = index;
		int base = vertexArray[srcNode];
		int size = vertexArray[index + 1] - vertexArray[index];
		for (int offset = 0; offset < size; offset++)
		{
			int dstNode = edgeArray[base + offset];
			int weight = weightArray[base + offset];

			// Print graph
			printf("%d -> %d : %d\n", srcNode, dstNode, weight);
		}
	}

	system("pause");
	return 0;
}

실행하면 아래와 같이 원래의 희소행렬과 동일한 값이 출력되는 것을 볼 수 있다.

이를 통해 희소행렬과 vertexArray-edgeArray-weightArray는 상호 변환될 수 있다는 것을 알 수 있다.

위 세 가지 배열 외에도 커널 내에서 계산 중에 사용되는 배열이 있다.

maskArray : 해당 노드에 대해 알고리즘을 수행할 필요가 있는지 여부를 0 또는 1로 저장한다.

updatingCostArray : 최적해를 계산하기 위한 임시공간.

costArray : 계산된 최적해를 저장한다.

이렇게 총 6개의 배열이 사용되는 셈이다.

4. OpenCL 코드 구현

모든 정점에서 모든 정점으로 가는 최단 거리를 구하는 코드를 만들어보자.

1. 커널 및 호스트 코드 구현

작성한 커널 함수는 아래와 같다.

dijkstra.cl

// TODO: Add OpenCL kernel code here.

__kernel void dijkstra1(__global int *vertexArray, __global int *edgeArray, __global float *weightArray,
							 __global int *maskArray, __global float *costArray, __global float *updatingCostArray,
							 int vertexCount, int edgeCount)
{
	int tid = get_global_id(0);

	if (maskArray[tid] != 0)
	{
		maskArray[tid] = 0;

		int edgeStart = vertexArray[tid];
		int edgeEnd;
		if (tid + 1 < (vertexCount))
		{
			edgeEnd = vertexArray[tid + 1];
		}
		else
		{
			edgeEnd = edgeCount;
		}

		for (int edge = edgeStart; edge < edgeEnd; edge++)
		{
			int nid = edgeArray[edge];

			if (updatingCostArray[nid] > (costArray[tid] + weightArray[edge]))
			{
				updatingCostArray[nid] = (costArray[tid] + weightArray[edge]);
			}
		}
	}
}

__kernel void dijkstra2(__global int *vertexArray, __global int *edgeArray, __global float *weightArray,
								__global int *maskArray, __global float *costArray, __global float *updatingCostArray,
								int vertexCount)
{
	int tid = get_global_id(0);

	if (costArray[tid] > updatingCostArray[tid])
	{
		costArray[tid] = updatingCostArray[tid];
		maskArray[tid] = 1;
	}

	updatingCostArray[tid] = costArray[tid];
}

__kernel void initializeBuffers(__global int *maskArray, __global float *costArray, __global float *updatingCostArray,
								 int sourceVertex, int vertexCount)
{
	int tid = get_global_id(0);

	if (sourceVertex == tid)
	{
		maskArray[tid] = 1;
		costArray[tid] = 0.0;
		updatingCostArray[tid] = 0.0;
	}
	else
	{
		maskArray[tid] = 0;
		costArray[tid] = FLT_MAX;
		updatingCostArray[tid] = FLT_MAX;
	}
}

호스트 코드는 아래와 같다.

host.cpp

(작성 예정)

3. 실행 결과

(작성 예정)

4. 솔루션 첨부

글을 쓰면서 직접 작성한 Visual Studio 솔루션을 깃허브에 푸시하였다.
https://github.com/pikamonvvs/OpenCL-DijkstraAlgorithm

필요하면 내려받아서 실행해보면 될 것 같다.

5. 참고 문헌

OpenCL 프로그래밍 가이드 (저자: 아프탑 문시) - 책 링크
opencl-book-examples - https://github.com/victusfate/opencl-book-examples/tree/master/src/Chapter_16/Dijkstra
minhee님의 블로그 - https://velog.io/@minhee/dijkstraalgorithm
캐스피님의 블로그 - https://kaspyx.tistory.com/64

pikamon

개발자입니당 *^^* 깃허브 https://github.com/pikamonvvs

이전 포스트