대용량 LiDAR 데이터의 병렬 보간 처리를 위한 MPI와 MapReduce 비교
Comparisons of MapReduce and MPI for Parallel Interpolation of Large-scale LiDAR Data
- 발행기관 아주대학교
- 지도교수 박승규, 오상윤
- 발행년도 2014
- 학위수여년월 2014. 8
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000017362
- 본문언어 한국어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
LiDAR 데이터는 항공 LiDAR 센서를 통해 획득한 3차원의 공간정보로서 매우 정밀하다. 다양한 분야 특히, 지리정보시스템에서 사용되는 LiDAR 데이터는 센서 기술의 발달로 획득하는 데이터의 양이 증가하고 있고 정확한 공간정보에 대한 요구가 많아짐에 따라 데이터를 분석하는 방법이 복잡해지고 있다. 데이터의 규모에 및 알고리즘의 복잡도에 비례하여 처리시간도 증가하기 때문에 이를 해결하기 위해 효과적인 병렬처리 기법이 필요하며 특히, MPI 및 MapReduce를 이용한 고성능 병렬 처리 방식 연구가 활발히 진행되고 있다. 하지만 대용량 LiDAR 데이터 보간 처리의 병렬화에 있어서 여러 문제점들이 나타날 수 있고 사용한 알고리즘에 따라 낮은 효율을 보이는 경우가 발생할 수 있기 때문에 병렬화의 이점을 보일 수 있는 효과적인 병렬처리 구조가 필요하다. 본 논문에서는 LiDAR 데이터의 병렬 보간 처리에 있어서 나타날 수 있는 문제점들을 도출하고 이를 기반으로 하여 MPI와 MapReduce 모델을 사용하여 효율적인 분산 처리를 위해 각 모델의 구조에 적합한 소프트웨어를 구현하고 이를 통해 MPI와 MapReduce를 비교한다. 또한, 분산 시스템에서 효율적인 LiDAR 데이터 보간 처리를 위해 MPI 기반의 자료구조 생성 기법을 제안한다. 분산 시스템에서 LiDAR 데이터 보간 처리는 단일 시스템과는 다르게 격자간의 경계 불일치, 불균등한 작업량과 같은 여러 문제점들이 발견될 수 있다. 이러한 문제점들을 해결하기 위해 MPI에서는 버켓팅을 통해 경계 불일치 문제를 해결하고 불균등한 작업량은 각 코어에서 처리할 격자의 크기를 다양하게 설정함으로서 문제를 해결하였다. MapReduce에서는 경계불일치 문제를 해결하기 위해 보간에 필요한 점들을 모두 하나의 격자에 위치시키는 방법을 사용하였다. LiDAR 데이터를 병렬 보간 처리하는데 있어 MPI와 MapReduce를 전체 실행 시간 및 경계 불일치 문제를 해결하기 위해 사용한 자료구조 생성 시간 등의 측면에서 비교하였다. 그 결과, LiDAR 데이터처럼 경계 값 교환이 한 번만 일어나는 경우 통신을 사용하지 않는 쪽이 더 효율을 보이며 파일입출력을 사용하지 않고 C로 구현된 프로그램을 사용하는 등, 구조적인 측면 및 프레임워크의 차이로 인해 MPI가 맵리듀스보다 더 좋은 성능을 보이는 것을 확인하였다.
more목차
1. 서 론 1
2. 병렬 프로그래밍 모델 3
가. MPI Programming Model 3
나. MapReduce Programming Model 5
다. Hybrid MR-MPI 7
3. LiDAR 데이터 보간 처리에 대한 관련 연구 10
가. 탐색을 위한 자료구조 10
나. 보간법(Interpolation) 12
다. 병렬 환경에서 LiDAR 데이터 보간 처리에 관한 연구 13
4. 문제 정의 16
5. Case Study: MPI and MapReduce 21
가. MPI 21
(1) 처리량 발란싱을 위한 다양한 그리드 사이즈 접근법 21
(2) 경계 불일치 현상 22
나. MapReduce 28
6. 실험 결과 30
가. 실험 환경 30
(1) MPI와 MapReduce 실험 비교 32
(2) Bucketing과 메시지 패싱 비교 35
7. 비교 분석 37
8. 결론 및 향후 과제 40
