[박혜웅] Matrix-Java-Toolkits vs CUDA LIbrary

Power Iteration Method를 이용하면, PageRank와 비슷한 방식으로 사용자에 대한 랭킹 연산을 할 수 있다.

원래 알고리즘은 "Matrix*Matrix" 연산을 하지만, 수행 시간을 고려하면 "Matrix*Vector"가 더 빠르다.

이전 포스트 [박혜웅] JAVA libraries for Linear Algebra (선형대수학), Sparse Matrix (희소행렬) 에서 Sparse Matrix용 JAVA 라이브러리를 소개한 적 있고, 그 중에서 MTJ가 가장 낫다고 평가한 바 있다.

"Matrix*Vector" 연산에 대하여 CUDA Library와 MTJ Library 의 수행 시간을 비교해 보자.

이 테스트는 대기업 인트라넷(또는 소용량 SNS)을 기준으로 하여 예상 수행시간을 계산하였다.

대기업에의 사원수가 10,000명이고, 각 사원(user)의 평균 하루에 3개의 글(content)을 쓴다고 가정하였다.

또, 연산 기간(period)에 포함되는 데이타는 1년간 사원들이 쓴 글이라고 하면 약 천만*천만에 대한 행렬이 생성된다.

개인적인 경험에 비추어 보면 exponent가 100 ~1000 사이에서 수렴할 것으로 추측한다.

실험 결과, GPU 연산을 수행하는 CUDA 라이브러리가 약 4~7배 빨랐다.

따라서 CUDA 라이브러리를 사용할 수 있고 연산 종류가 간단하다면 CUDA가 나을 것이고,

Matrix에 대한 다양한 연산이 필요하다면 MTJ를 활용하는 것이 나을 것이다.

<연산 식>

b = (A * x) / norm

A: Matrix

x: vector  (초기값은 원소값이 모두 1인 벡터)

b: vector

norm: max_element(A*x), "A*x"의 원소 중 최대값.

<가정>

users: 10,000 

contents / day: 3

period: 365 days

nonzeros(A) / rows(A) = 3.0

rows(A)=cols(A)= 10,000 명 * 3개/일 * 365일 = 10,950,000 (약 천만)

nonzeros(A)= rows(A) * 3.0 = 32,850,000 (약 3천만)

 

<실행 환경>

총 수행 시간 = (Reading data file to matrix A) + (Calculation of A * x ) + (Writing result file from vector b)

JVM option: -Xms4G -Xmx4G

OS:  CentOS release 4.5 (Final) Linux version 2.6.9-55.ELsmp

CPU: Intel(R) Xeon(R) CPU E5430  @ 2.66GHz * 1 Unit

인텔(소켓771) / 64(32)비트 / 쿼드 코어 / 2.66GHz / 6MB x2

VGA: Nivida Geforce GTX280

지포스 GTX280 / 600MHz / GDDR3(DDR3) / 2000~2499MHz / 1GB / 512-bit / PCI-Express 2.0 x16

MEM: 8GB

<수행 결과>

rows(A): 10,000,000, cols(A): 10,000,000, nonezero(A): 32,000,000

rows(y): 10,000,000

filesize(A):1.1GB

filesize(y):266M 

exponent for A: 10

Elapsed: 0 hour  2 min 28 sec (MTJ)

Elapsed: 0 hour  0 min 41 sec (CUDA)

exponent for A: 100 

Elapsed: 0 hour  7 min  5 sec (MTJ)

Elapsed: 0 hour  1 min 22 sec (CUDA)

exponent for A: 1000

Elapsed: 0 hour 51 min 13 sec (MTJ)

Elapsed: 0 hour  8 min  4 sec (CUDA)