parallel_for와 Matrix 연산

TBB를 사용해서 Matrix연산 퍼포먼스를 측정해 봤다.

Matrix Multiply를 해봤는데 그런대로 볼만한 성능향상이 있어서 그 내용에 대해서 올려본다. 

Matrix 곱 연산은 N X N  두개의 행렬에 대해서 실행 했을때 O(n^3)이 나오는 복잡한 연산중에 하나이다. 게다가 매트릭스 곱은 행과 열의 관계에 대한 계산을 할때 빈번히 쓰여서 social network를 구현하기 위한 계산을 할때 자주쓰이는 재밋는 수식이다.

이 연산비교를 위해 일반적으로 시퀀셜하게 행렬 연산을 하는 함수인 SerialMatrtixMultiply를 준비했고,
병렬연산을 위해서 parallel_for 함수를 사용, blocked_range2d의 파티셔닝 정책을썼다. 그리고 데이터를 파티션하는 방법은 자동(auto_partitioner())으로 두었다.

A 매트릭스는 ‘150 X 225’이고 B 매트릭스는 ‘225 X 300’ 이다. 꽤 큰 매트릭스다.

테스트 해본 결과는 아래와 같다.(단위 : 초)

듀얼코어 core 2개
seq eslaped time : 0.063538
parallel eslaped time : 0.0353912

쿼드코어 CPU 2개 core 8개
seq eslaped time : 0.06934
parallel eslaped time : 0.01647

테스트 할때마다 미세한 성능차이는 있었지만 대부분의 값이 위와 비슷했다.

소스 코드는 아래와 같다.

[CODE C]
#include <iostream>
#include “tbb/parallel_for.h”
#include “tbb/blocked_range2d.h”
#include “tbb/task_scheduler_init.h”
#include “tbb/tick_count.h”
#include “tbb/partitioner.h”

using namespace tbb;

const size_t L = 150;
const size_t M = 225;
const size_t N = 300;

void SerialMatrtixMultiply(float c[][N], float a[][L], float b[][N]){
    for(size_t i = 0; i < M; ++i){
        for(size_t j = 0; j < N; ++j){
            float sum = 0;
            for(size_t k = 0; k < L; ++k)
                sum += a[i][k] * b[k][j];
            c[i][j] = sum;
        }
    }
}

class MatrixMultiply2D{
    float (*my_a)[L];
    float (*my_b)[N];
    float (*my_c)[N];

public:
    void operator()(const blocked_range2d<size_t>& r) const {
        float (*a)[L] = my_a;
        float (*b)[N] = my_b;
        float (*c)[N] = my_c;

        for(size_t i = r.rows().begin(); i != r.rows().end(); ++i){
            for(size_t j = r.cols().begin(); j != r.cols().end(); ++j){
                float sum = 0;
                for(size_t k = 0; k < L; ++k)
                    sum += a[i][k] * b[k][j];
                c[i][j] = sum;
            }
        }
    }
    MatrixMultiply2D(float c[][N], float a[][L], float b[][N]):my_a(a), my_b(b), my_c(c)
    {}
};

void ParallelMatrixMultiply(float c[][N], float a[][L], float b[][N]){
    parallel_for(blocked_range2d<size_t>(0, M, 0, N), MatrixMultiply2D(c,a,b), auto_partitioner());
}

int main(void){
    task_scheduler_init init;
   
    float a[M][L];
    float b[L][N];
    float c[M][N];

    srand(time(NULL));
    for(int i = 0;i < M;i++){
        for(int j = 0;j < L;j++)
            a[i][j] = rand() % 30;
    }

    for(int i = 0;i < L;i++){
        for(int j = 0;j < N;j++)
            b[i][j] = rand() % 30;
    }

    tick_count t0 = tick_count::now();
    SerialMatrtixMultiply(c,a,b);
    tick_count t1 = tick_count::now();
    std::cout << “seq eslaped time : ” << (t1 – t0).seconds() << std::endl;

    t0 = tick_count::now();
    ParallelMatrixMultiply(c,a,b);
    t1 = tick_count::now();
    std::cout << “parallel eslaped time : ” << (t1 – t0).seconds() << std::endl;

   
    return 0;
}
[/CODE]

parallel_reduce, parallel_while, parallel_scan 등등 많은 흥미로운 함수가 있지만 parallel_for가 가장 사용하기도 쉽고 사용 범위도 넓다.

시퀀셜 연산과 병렬연산의 퍼포먼스가 확연한데 저런 결과들이 쌓이면 큰 성능향상으로 이끌어 갈 수 있지 않을까 한다.

참고: Intel Threading Building Block