GPGPU 기반 온도 병렬 시뮬레이티드 어닐링 알고리즘
A temperature parallel simulated annealing algorithm based on GPGPU
- 주제(키워드) GPGPU , CUDA , Simulated annealing
- 발행기관 서강대학교 일반대학원
- 지도교수 박성용
- 발행년도 2012
- 학위수여년월 2012. 2
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/sogang/000000047431
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작원 보호를 받습니다.
초록/요약
시뮬레이티드 어닐링은 자연현상을 모방한 범용 조합 최적화 알고리즘으로서 알고리즘 프레임워크가 유연하고 최상에 가까운 해를 얻을 수 있는 장점이 있어 다양한 조합 최적화 문제에 적용 되어왔다. 하지만 상당히 좋은 해를 얻기 위해 기존의 최적화 알고리즘에 비해 많은 시간을 필요로 하는 문제가 있다. 이러한 문제를 해결하기 위해 계산 시간 단축을 목적으로 시뮬레이티드 어닐링을 병렬화 하는 연구가 행해지고 있다. 그러한 방법들 중, 온도 병렬 시뮬레이티드 어닐링 알고리즘은 기존의 병렬 시뮬레이티드 어닐링 알고리즘에 비해 해의 품질을 저하시키지 않으면서 빠른 시간에 양호한 해를 얻을 수 있다는 것이 증명되어 있다. 이러한 장점으로 인해 온도 병렬 시뮬레이티드 어닐링에 대한 연구가 최근까지 진행되고 있으나 아직까지 GPU 환경에서 구현하려는 시도가 없었다. GPU는 CPU 이상의 연산 능력과 메모리 대역폭을 지니고 있고, CPU보다 병렬 처리에 특화되어 있다. 따라서 병렬 알고리즘의 경우 GPU를 이용하여 수행하는 것이 유리하다. 하지만 CPU와 GPU는 서로 다른 구조와 프로그래밍 모델을 지니고 있어 기존의 CPU 환경에서 사용되는 알고리즘을 GPU 환경에 바로 적용 시킬 경우 성능을 보장할 수 없게 된다. 본 논문에서는 Nvidia의 GPGPU 기술인 CUDA 기반의 온도 병렬 시뮬레이티드 어닐링 알고리즘을 구현하고 GPGPU 환경에서 동작하는 온도 병렬 시뮬레이티드 어닐링 알고리즘의 성능을 향상시킬 수 있는 방법을 제안한다. 결과적으로 본 논문의 실험을 통해 제안한 알고리즘을 적용하였을 경우 제안한 알고리즘을 적용 하지 않은 알고리즘에 비해 최대 3.03배의 성능 향상이 있음을 확인하였다.
more초록/요약
Simulated annealing is a general purpose combinatorial optimization algorithm that mimics the natural phenomena. Framework of this algorithm has the advantage of being able to obtain near-optimal solutions with flexibility, have been applied to a variety of combinatorial optimization. However, to get a pretty good solution, there is a problem that requires more processing time compared to the existing optimization algorithms. To solve this problem have been studied to parallelize the simulated annealing to reduce the computation time. One of these methods is called the temperature parallel simulated annealing algorithm. This algorithm is compared to existing algorithms, and it is proved that produce good solutions in less time without compromising the quality of a solution. Due to these advantages, the temperature parallel simulated annealing was studied recently. But so far there was no attempt to implement in GPU environment. GPU has more computational power and memory bandwidth than CPU. Also, It is specific to parallel processing than CPU. Thus, the parallel algorithm using the GPU is advantageous to performance. However, CPU and GPU has a different structure and programming model, so the original CPU version algorithm should be modified to be used in GPU. In this paper, we propose to improve the performance of the temperature parallel simulated annealing algorithm in a GPGPU environment. This algorithm has been implemented on a GPU using Nvidia CUDA GPGPU technology. The experimental results show that the proposed algorithm obtains up to 3.03x speedup compared with the general approach.
more