Earticle

초록

한국어

최근 멀티코어 프로세서가 널리 활용되고 있지만 프로그래머가 최적의 성능향상을 가지는 프로그램을 작성하기는 매 우 어렵다. OpenMP는 디렉티브의 삽입만으로 병렬화가 가능하지만, 최종 병렬 코드의 성능 향상은 쓰레드의 수와 쓰레드 간 작업의 분배에 크게 영향을 받는다. 본 논문은 쿼드 트리 기반 쿼리 처리 문제를 배열 기반의 트리로 변환 하여 지역성을 향상하고 자료구조의 특성에 맞게 병렬화를 진행한다. 병렬화 진행 시 동적 로드 밸런싱 기법을 통해 각 쓰레드에서 처리되는 데이터의 양을 균형적으로 할당함으로써 성능향상을 이루어내는 방법을 제안한다. 배열 기반의 쿼드 트리 데이터베이스쿼리 검색 프로그램에 동적 로드 밸런싱 기법과 병렬화를 적용한 결과를 이용 하여 쓰레드의 수와 프로그램 성능의 상관관계를 분석하고 수식화 한다. 쓰레드의 수에 따른 프로그램의 전체 수행 시간을 예상한 후 실제 수행시간과 비교할 경우 평균적으로 전체 수행시간에서 5~10%의 차이를 보인다. 이를 이용하여 최적의 성능향상을 보이는 쓰레드의 수를 예측 할 수 있다.

영어

Recently multicore processors have been widely used, however it is still very difficult to achieve optimal performance improvement by parallel programming on multi core processors. OpenMP provides reliable parallel programming interfaces which enables parallelism by the insertion of directives; nevertheless the performance of final parallel code will be determined by the number of threads and the distribution of workload between threads. In this paper, we improve locality and parallelize quad-tree based query problems by transforming tree into array-based tree. In the process of parallelization, we propose dynamic load balancing method which enables load balance between multiple threads to implement parallelized query process on tree. The experimental results shows that proposed methods successfully parallelize the tree traversal and dynamically balance the load between threads. We also analyze experimental results to correlate number of threads and performance improvement to establish performance estimation formula. The estimated execution time of program using number of threads and the actual execution time have 5-10% gap on average. We can predict the number of threads that is optimal performance improvement using the result.

목차

요약
 Abstract
 1. 서론
 2. 관련연구
  2.1 OpenMP
  2.2 쿼드 트리
  2.3 쿼드 트리 데이터베이스를 이용한 쿼리 검색 알고리즘
  2.4 연결 리스트 기반의 쿼드 트리 병렬화
 3. 배열 기반의 쿼드 트리 검색 병렬화 및 동적 로드 밸런싱 기법
  3.1 연결 리스트 기반의 쿼드 트리의 변환
  3.2 배열 기반의 쿼드 트리 검색 병렬화
  3.3 동적 로드 밸런싱
  3.4 성능 예측 기법
 4. 성능 측정 및 비교
  4.1 실험 환경
  4.2 실험 내용
  4.3 실험 결과 및 분석
 5. 결론
 Acknowledgement
 참고문헌

저자

• 성운 [ Woon Sung | 인하대학교 컴퓨터정보공학과 ]
• 박준석 [ Joonseok Park | 인하대학교 컴퓨터정보공학과 ]

참고문헌