블록 중심 그래프 처리 시스템의 로드 밸런싱을 위한 동적 블록 재배치 기법
Dynamic Block Reassignment for Load Balancing of Block-Centric Graph Processing Systems
- 주제(키워드) 블록 중심 처리 , 대규모 그래프 데이터 , 로드 밸런싱 , 블록 재배치
- 발행기관 아주대학교
- 지도교수 오상윤
- 발행년도 2018
- 학위수여년월 2018. 2
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000027199
- 본문언어 한국어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
최근 웹, 소셜 네트워크 서비스, 모바일, 사물인터넷 등 ICT 기술의 발전으로 인해 처리 및 분석이 필요한 그래프 데이터의 규모가 급속하게 증가하였다. 이러한 대규모 그래프 데이터는 단일 기기에서의 처리가 어려우므로 여러 기기에 나누어 분산 병렬 처리하는 것이 필요하지만, 기존 그래프 처리 방식들은 단일 메모리 환경을 기반으로 연구되어 분산 병렬 처리에 적용하기 힘들다. 이에 보다 효과적인 대규모 그래프 처리를 위해 정점 중심 방식의 그래프 처리 시스템들과 정점 중심 방식의 단점을 보완한 블록 중심 방식의 그래프 처리 시스템들이 등장하였다. 이러한 시스템들은 초기 그래프 분할 상태가 전체 처리 성능을 좌우하지만, 한 번에 최적의 상태로 그래프를 분할하는 것이 매우 어렵다. 따라서 그래프 처리 시간에 점진적으로 그래프 분할 상태를 개선하는 여러 로드 밸런싱 기법들이 연구되었다. 그러나 기존 기법들은 대부분 정점 중심 그래프 처리 시스템만을 고려하여 블록 중심 그래프 처리 시스템에 바로 적용하기 어렵다. 본 논문에서는 블록 중심 그래프 처리 시스템에서 동적으로 블록을 재배치하여 그래프 분할 상태를 개선하는 로드 밸런싱 기법을 제안한다. 제안 기법은 동적 블록 재배치를 통해 지역적 정보를 기반으로 점진적으로 해를 개선해 나가며, 해를 찾아 나가는 과정에서 지역 최적해를 벗어나기 위한 블록 분할 전략을 함께 제시한다. 본 제안 기법의 평가를 위하여 기존 블록 기반 시스템의 핵심 기능을 가지는 시스템을 구현하고, 구현된 시스템상에서 성능평가가 진행되었다. 제안 기법의 성능은 데이터 규모가 작은 경우에는 약간의 오버헤드가 존재하나 데이터 규모에 따라 전반적으로 9.5%의 성능 향상을 보였으며, 그래프의 평균 차수에 따라 성능 향상의 폭이 증가하는 것을 확인하였다. 향후 확률적 요소와 그래프 특성에 따른 제안기법의 효과 분석에 관한 연구가 진행되면 블록 중심 그래프 처리 시스템의 로드 밸런싱 기법 연구의 토대가 될 것으로 기대한다.
more초록/요약
As the development of ICT technologies such as web, social network service, and mobile, the scale of graph data required for processing and analysis has been increased rapidly. For these large-scale graphs easily exceed a capacity of a single machine, they need to be processed in distributed/parallel. Traditional graph algorithm has been studied based on single shared memory, so that it is difficult to be applied on distributed/parallel environment. To handle this challenge and process large-scale graphs more effectively, several vertex-centric graph processing systems and block-centric graph processing systems have been proposed. In these systems, the initial quality of graph partition significantly affects the overall performance. Since it is difficult to obtain optimally partitioned graph at a time, several dynamic load balancing techniques have been proposed to improve the quality of graph partition in runtime. However, most of them are focused on vertex-centric systems without any consideration of block-centric ones. In this paper, we present a load balancing method that can be applied to block-centric graph processing systems. Our solution gradually improves the quality of graph partition by dynamically reassigning blocks in runtime, and also suggests block split strategy for escaping local optimum solution. To evaluate proposed method, a system with core functionality of block-centric graph processing system was implemented and performance evaluation was conducted on the implemented system. As a result, the proposed method showed about 9.5% improvement in overall performance depending on the data size.
more목차
1. 서 론 1
가. 연구배경 및 필요성 1
나. 연구 내용 및 논문 구성 5
2. 관련 연구 6
가. 정점 중심 및 블록 중심 그래프 처리 시스템 6
1) 정점 중심 그래프 처리 시스템 동작 구조 8
2) 블록 중심 그래프 처리 시스템 동작 구조 11
나. 정점 중심 그래프 처리 시스템을 위한 로드 밸런싱 기법 15
1) 모니터링 기반의 동적 정점 재배치 기법 15
2) 토폴로지 기반 동적 정점 재배치 기법 19
3) 예측 모델 기반 동적 정점 재배치 기법 19
3. 동적 블록 재배치를 통한 부하 분산 기법 20
가. 작업 성능 모델링 22
나. 블록 재배치 수행 단계 및 처리 구조 24
1) Balancing Manager 25
2) 부하 불균형 여부 판단 26
3) 블록 재배치 과정 종료 28
다. 블록 재배치 알고리즘 29
1) 블록 재배치 알고리즘 29
2) 블록 분할 알고리즘 35
4. 성능평가 39
가. 성능평가 환경 40
1) 실험 환경 40
2) 실험 데이터 41
3) 시스템 구현 42
나. 성능 평가 결과 43
5. 결론 및 향후 과제 46
참고문헌 47
