KAIST, 초대규모 그래프 프로세싱 시뮬레이션 기술 개발
KAIST, 초대규모 그래프 프로세싱 시뮬레이션 기술 개발
  • 함예솔
  • 승인 2021.04.23 17:11
  • 조회수 1008
  • 댓글 0
이 기사를 공유합니다

국내 연구진이 오늘날 정보통신(IT) 분야에서 광범위하게 사용되는 그래프 타입의 데이터를 실제로 저장하지 않고도 알고리즘을 계산할 수 있는 '그래프 프로세싱 시뮬레이션'이라는 신개념 기술을 세계 최초로 개발하는 데 성공했습니다. 데이터를 저장할 필요가 없어 1조 개 간선의 초대규모 그래프도 PC 한 대로 처리가 가능합니다. 해당 연구는 온라인으로 열린 데이터베이스 분야 최고 국제학술대회 중 하나인 IEEE ICDE에서 발표됐습니다. 
 

PC 1대로 1조개 규모의 그래프 알고리즘 계산한다 

 

KAIST 전산학부 김민수 교수 연구팀이 1조 개 간선의 초대규모 그래프에 대해 데이터 저장 없이 알고리즘을 계산할 수 있는 신개념 기술을 세계 최초로 개발했습니다. 

알고리즘 연구 중요해요. 출처: fotolia
알고리즘 연구 중요해요. 출처: fotolia

오늘날 웹, SNS, 인공지능, 블록체인 등의 광범위한 분야들에서 그래프 타입의 데이터에 대한 다양한 알고리즘들의 연구가 매우 중요합니다. 그러나 그래프 데이터의 복잡성으로 인해 그 크기가 커질 때 막대한 규모의 컴퓨터 클러스터가 있어야만 알고리즘 계산이 가능하다는 문제가 있습니다.

 

김 교수 연구팀은 이를 근본적으로 해결하는 T-GPS(Trillion-scale Graph Processing Simulation)라는 기술을 개발했습니다. 이 T-GPS 기술은 그래프 데이터를 실제로 디스크에 저장하지 않고도 마치 그래프 데이터가 저장돼 있는 것처럼 알고리즘을 계산할 수 있고, 계산 결과도 실제 저장된 그래프에 대한 알고리즘 계산과 완전히 동일하다는 장점이 있습니다.


그래프 알고리즘은 그래프 처리 엔진 상에서 개발되고 실행됩니다. 이는 산업적으로 널리 사용되는 SQL 질의를 데이터베이스 관리 시스템(DBMS) 엔진 상에서 개발하고 실행하는 것과 유사한 방식입니다.

 

지금까지는 그래프 알고리즘을 개발하기 위해 먼저 합성 그래프를 생성 및 저장한 후, 이를 다시 그래프 처리 엔진에서 메모리로 적재해 알고리즘을 계산하는 2단계 방법을 사용했습니다. 그래프 데이터는 그 복잡성으로 인해 전체를 메모리로 적재하는 것이 요구되며, 그래프의 규모가 커지면 대규모 컴퓨터 클러스터 장비가 있어야만 알고리즘을 개발하고 실행할 수 있다는 커다란 단점이 있었습니다.

종래의 2단계 방식은 실제 소규모 그래프로부터 특징 파라메터(parameter)들을 뽑아내어 RMAT이나 BA 모델을 따르는 대규모 합성 그래프를 생성(1번 과정)하거나, 또는 실제 소규모 그래프의 특성을 따르는 대규모 합성 그래프를 생성(2번 과정)한 후, 디스크에 모두 저장한다. 그 후 컴퓨터 클러스터 메인 메모리에 모두 적재한 후, 분산 그래프 처리 엔진을 이용하여 그래프 알고리즘을 실행(3번 과정)한다. 그래프 데이터의 크기가 커지면 메모리 부족으로 실패하거나, 또는 실행 시간이 매우 오래 소요된다. 출처: KAIST
종래의 2단계 방식은 실제 소규모 그래프로부터 특징 파라메터(parameter)들을 뽑아내어 RMAT이나 BA 모델을 따르는 대규모 합성 그래프를 생성(1번 과정)하거나, 또는 실제 소규모 그래프의 특성을 따르는 대규모 합성 그래프를 생성(2번 과정)한 후, 디스크에 모두 저장한다. 그 후 컴퓨터 클러스터 메인 메모리에 모두 적재한 후, 분산 그래프 처리 엔진을 이용하여 그래프 알고리즘을 실행(3번 과정)한다. 그래프 데이터의 크기가 커지면 메모리 부족으로 실패하거나, 또는 실행 시간이 매우 오래 소요된다. 출처: KAIST

김 교수팀은 합성 그래프와 그래프 처리 엔진 분야에서 국제 최고 권위의 학술대회에 매년 논문을 발표하는 등 세계 최고의 기술력을 보유하고 있으며 그 기술들을 바탕으로 기존 2단계 방법의 문제를 해결했습니다.

 

그래프 데이터상에서 그래프 알고리즘이 계산을 위해 접근하는 부분을 짧은 순간 동안 실시간으로 생성해, 마치 그래프 데이터가 존재하는 것처럼 알고리즘을 계산하는 겁니다. 이때 그래프 데이터를 아무렇게 실시간 생성하는 것이 아니라 합성 그래프 모델에 따라 생성하고 저장한 것과 동일하도록 실시간 생성하는 것이 핵심 기술 중 하나입니다.

 

또한, 그래프 처리 엔진이 실시간으로 생성되는 그래프를 실제 그래프처럼 인식하고 알고리즘을 완전히 동일하게 계산하도록 엔진을 수정한 것이 또 다른 핵심 기술입니다.

 

김민수 교수 연구팀은 T-GPS 기술을 종래의 2단계 방법과 성능을 비교한 결과, 종래의 2단계 방법이 11대의 컴퓨터로 구성된 클러스터에서 10억 개 간선 규모의 그래프를 계산할 수 있었던 반면, T-GPS 기술은 1대의 컴퓨터에서 1조 개 간선 규모의 그래프를 계산할 수 있어 컴퓨터 자원 대비 10,000배 더 큰 규모의 데이터를 처리를 할 수 있음을 확인했습니다. 또한, 알고리즘 계산 시간도 최대 43배 더 빠름을 확인했습니다.

 

교신저자로 참여한 김민수 교수는 "오늘날 거의 모든 IT 분야에서 그래프 데이터를 활용하고 있는바, 연구팀이 개발한 새로운 기술은 그래프 알고리즘의 개발 규모와 효율을 획기적으로 높일 수 있어 산업적 측면에서 파급 효과가 매우 클 것으로 기대한다" 라고 말했습니다.


##참고자료##

  • Himchan Park et al., Trillion-scale Graph Processing Simulation based on Top-Down Graph Upscaling, IEEE 37th International Conference on Data Engineering (ICDE)


댓글삭제
삭제한 댓글은 다시 복구할 수 없습니다.
그래도 삭제하시겠습니까?
댓글 0
댓글쓰기
계정을 선택하시면 로그인·계정인증을 통해
댓글을 남기실 수 있습니다.

  • 충청남도 보령시 큰오랏3길
  • 법인명 : 이웃집과학자 주식회사
  • 제호 : 이웃집과학자
  • 청소년보호책임자 : 정병진
  • 등록번호 : 보령 바 00002
  • 등록일 : 2016-02-12
  • 발행일 : 2016-02-12
  • 발행인 : 김정환
  • 편집인 : 정병진
  • 이웃집과학자 모든 콘텐츠(영상,기사, 사진)는 저작권법의 보호를 받은바, 무단 전재와 복사, 배포 등을 금합니다.
  • Copyright © 2016-2022 이웃집과학자. All rights reserved. mail to contact@scientist.town
ND소프트