대규모 그래프 처리 엔진 연구

매니코어OS
이동: 둘러보기, 검색

인터넷이 시작되면서 웹 그래프 또는 소셜 네트워크로 구성된 대규모 그래프가 보편화 되었다. 예를 들어 페이스 북은 최근 최대 규모의 소셜 그래프는 14억 개의 정점과 1 조 개의 에지다. 일반적으로 이러한 대형 그래프 처리를 위해, 200대의 컴퓨터에 분산 그래프 엔진(Giraph)를 사용하지만, 인텔 Xeon Phi매니코어와 NVMe 스토리지로 구성된 저가 시스템에 멀티 커널 운영체제가 동작하는 단일 시스템에서 대규모 그래프를 처리할 수 있는 그래프 엔진 Mosaic를 개발하였다.

Mosaic의 독창성은 대규모 그래프를 적절한 파티션 크기로 분할(타일)하고, 이 파티션을 캐시 지역성을 높이기 위해서 힐버트 순서로 탐색하여 서로 가까이 있는 정점들로 타일을 구성하는 것이다. 이 타일은 서브 그래프가 되며, 타일 크기는 LLC(Last Level Cache) 크기에 종속된다. 타일들은 NVMe로부터 빠르게 제공되며, Phi 코어에서 병렬 처리되어 로컬 정점 상태를 계산한다. 이렇게 병렬 처리되는 서브 그래프들의 결과는 Xeon 코어에서 글로벌 정점 상태로 계산된다.

mosaic1.png

상기 그림과 같이 구성된 타일들은 멀티커널 기반 Xeon Phi 매니코어 시스템에서 아래 그림과 같이 병렬처리된다.

mosaic2.png

Mosaic은 Gather-Apply-Scatter 모델과 유사한 Pull-Reduce-Apply 프로그래밍 모델을 제공한다. Pull은 타일로 나누어진 서브 그래프를 처리하는 API이며, Reduce는 같은 정점에 대해 두 개의 값으로 하나로 결합하는 글로벌 그래프 정점 상태 업데이트를 위한 API이다. Apply API는 각 정점에 대해 그래프 알고리즘을 수행하는데 사용된다. 다음은 그림은 pagerank 알고리즘의 사례이다.

mosaic3.png

기존 기술과 비교해 보면, GPGPU 기반 엔진과 비슷한 성능(조금 낮은 성능)내지만 GPGPU 기반 엔진보다 대규모 그래프 처리가 가능하다. 기존의 단일 시스템과 분산 시스템 기반의 엔진보다는 우월한 성능을 보인다.

mosaic4.png

논문 :