Breadth-first search 벤치마크의 성능비교 및 구현개선에 관한 연구

Abstract

최근 들어 빅데이터, 그 중에서 소셜네트워크가 폭발적으로 성장함에 따라 소셜네트워크 데이터의 중요성이 높아지고 있다. 이런 방대한 양의 데이터들은 그래프 데이터구조를 이용하여 저장되고 분석된다. 그래프는 선으로 연결된 객체들을 나타낼 때 사용하는 표현법으로 소셜네트워크에서는 사용자를 노드, 사용자간의 관계를 엣지로 표현한다. 이런 소셜네트워크 데이터에서 의미 있는 정보를 얻기 위해서는 데이터를 분석하는 과정이 필요하며, 분석은 모든 노드를 순회하며 노드의 상태들을 확인하며 진행된다. 따라서 소셜네트워크 데이터분석에 그래프순회는 중요한 부분이다. 대표적인 그래프순회 알고리즘인 Breadth-first search(BFS)는 순회시작 노드와 인접해있는 모든 노드들을 우선적으로 방문한 후, 방문한 노드와 인접한 노드들을 순차적으로 순회한다. 이런 순회방식은 그 특성상 같은 레벨에 위치하는 노드들을 병렬적으로 처리할 수 있다. BFS는 전체적인 틀은 동일하지만 다양한 구현의 벤치마크들이 있다. 구현에 따라서 확인해야 할 엣지의 수를 줄이거나, 노드를 접근하는 순서 등을 바꿔서 성능 향상을 도모한다. 또한 각 벤치마크의 특성이 다르므로 워크로드에 따라 성능이 다르다. 본 논문에서는 최근 발표된 주요 BFS 벤치마크 5종을 선택하고 각종 워크로드를 사용하여 수행시간과 메모리 측면에서 성능을 비교 및 분석하고, 워크로드 특성을 고려하여 적합한 벤치마크를 제시한다. 또한 일부 벤치마크에 대해서는 구현개선을 통하여 성능을 개선하였다. 마지막으로 메모리와 벤치마크 성능간의 상관관계를 파악하여, 차후 벤치마크의 구현을 개선하거나 메모리접근 방식의 최적화를 통해 전체적인 성능 향상이 가능할 수 있음을 보였다.