탐색 알고리즘의 GP-GPU 기반 병렬화
GP-GPU based Parallelization for Search Optimazation Algorithms
- 주제(키워드) GPU , GPGPU , 최적화 알고리즘
- 발행기관 강릉원주대학교 일반대학원
- 지도교수 김영태
- 발행년도 2015
- 학위수여년월 2015. 2
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 세부전공 초고속컴퓨팅
- 원문페이지 47
- 실제URI http://www.dcollection.net/handler/kangnung/000000007009
- 본문언어 한국어
초록/요약
GP-GPU는 그래픽 계산 장치로서 전력 소모량이 낮고, 다중의 코어들이 격자 형태로 배치되어 있고, 많은 쓰레드를 사용하는 장치이다. 이 GP-GPU를 사용하기 위해 그래픽 하드웨어 제작회사인 Nvidia에서는 CUDA model를 배포하였다. CUDA는 GP-GPU에서 제공하는 많은 쓰레드와 메모리를 사용자가 제어할 수 있게 하는 model로서 본 논문에서는 CUDA의 활용성을 검증하기 위해 인공지능 분야의 탐색 알고리즘인 Scatter Search, Differential Evolution, Harmony Search, Bacterial Foraging Optimization을 사용하였다. 모든 알고리즘은 동일한 방법으로 병렬화를 진행하였으며 각 알고리즘마다 CUDA를 적용한 결과에 대해 평가하였다. 그 결과 최적화 탐색 알고리즘에서 사용되는 문제의 차원이 크고 CUDA에서 사용하는 쓰레드의 크기가 클수록 CPU 프로그램을 사용하는 것보다 병렬화 프로그램을 사용하는 것이 더 좋다는 결과를 얻었다. 또한 같은 GP-GPU를 적용하더라도 사용한 쓰레드의 수에 따라 처리 속도의 차이가 생기고, 알고리즘에서 CUDA를 적용한 부분의 계산량에 따라 비 병렬 프로그램 대비 병렬 프로그램의 수행 시간이 더 단축되고, 병렬 프로그램에서 더 많은 쓰레드를 사용하는 것이 좋다는 결론을 얻었다. 향후 연구과제로는 CUDA 메모리 복사의 오버헤드를 줄이는 병렬화 프로그램을 구현하고자 한다.
more목차
1. 서론 ·······································································································1
2. 연구 배경 ·······························································································4
2.1 적용문제 ····························································································4
2.2 Scatter Search 알고리즘 ···································································4
2.2.1 SelectSubset 함수 ·······································································5
2.2.2 Recombine 함수 ··········································································6
2.3 Differential Evolution 알고리즘 ··························································8
2.3.1 newSample 함수 ·········································································9
2.4 Harmony Search 알고리즘 ······························································10
2.5 Bacterial Foraging Optimization 알고리즘 ········································12
2.5.1 Chemotaxis 함수 ·······································································13
3. CUDA를 적용한 알고리즘 구현 ·······························································16
3.1 CUDA ·····························································································16
3.2 Scatter Search 알고리즘 병렬화 ·······················································17
3.3 Differential Evolution 알고리즘 병렬화 ·············································22
3.4 Harmony Search 알고리즘 병렬화 ····················································23
3.5 Bacterial Foraging Optimization 알고리즘 병렬화 ·····························25
4. 성능평가 및 분석 ···················································································28
4.1 실험환경 ··························································································28
4.2 CUDA 적용 결과 ··············································································29
4.2.1 Scatter Search 프로그램 실행 결과 ············································29
4.2.2 Differential Evolution 프로그램 실행 결과 ···································30
4.2.3 Harmony Search 프로그램 실행 결과 ·········································31
4.2.4 Bacterial Foraging Optimization 프로그램 실행 결과 ·················32
4.3 정량적 분석 ······················································································33
4.4 정성적 분석 ······················································································37
5. 결론 ·····································································································42
참고문헌 ···································································································44
