ضرب دو ماتریس در Cuda

از الان تا آخر این پست میخوایم دو تا ماتریس رو در هم ضرب کنیم با استفاده از برنامه نویسی موازی!

اگر چیزی از برنامه نویسی موازی نمیدونید و یا اصلا با زبان cuda آشنا نیستید بهتره یه سری به دو تا پست قبلی من بزنید... پست اول . پست دوم .

ضرب ماتریس به صورت غیر موازی!

خب برای اینکه یه شروع خوبی داشته باشیم بهتره که از چیزی که بلد هستیم شروع کنیم!

void MatrixMul(int m1[ ][N], int m2[ ][N], int res[ ][N]){
int i, j, k;
for(i=0; i<N; i++){
    for(j=0; j<N; j++){
         res[i][j]=0;
        for(k=0; k<N; k++)
               res[i][j]+=m1[i][k] * m2[k][j];
             }
       }
}

نیاز به توضیح این یک تکه کد نیست! فکر کنم واضحه که داره چیکار میکنه. همانطور که میدونید مرتبه اجراش هم O(n^3) هستش. تا الان اثبات شده که مرتبه اجرای ضرب دو ماتریس از O(n^lg7) هست که با استراسن با راه حل تقسیم و غلبه حلش کرده.

ضرب ماتریس با استفاده از Cuda به صورت موازی

خب حالا بریم سراغ ضرب ماتریس با استفاده از برنامه نویسی موازی. همون طور که در پست اول حسابی راجع بهش حرف زدم، برای پیاده سازی برنامه نویسی موازی به GPUنیاز داریم که هر GPU از یک سری SM تشکیل شده که هر SMدر واقع یک block در برنامه نویسی cuda هستند و هر بلاک از یکسری core تشکیل شده که برای ما در برنامه نویسی cuda این ها همان thread های ما هستند.

کاری که در برنامه نویسی موازی انجام میدهیم این است که هر کدام از سطر و ستون ها که باید در هم ضرب شوند با استفاده از یک thread انجام میشوند. مثلا در شکل زیر سطر و ستونی که نشان داده شده است و یک عنصر از ماتریس نتیجه را میدهد با استفاده از یک thread انجام میگیرد.

پس اولین کاری که باید کرد این است که به هر thread بگوییم که مسئول کدام row و col هست. برای همین اول تابع باید این موضوع مشخص بشه پس به این صورت مینویسیم که:

__global__ void matrixMul(int *a, int *b, int *c, int N){

//first step
   int row = blockIdx.y * blockDim.y + threadIdx.y;

   int col = blockIdx.x * blockDim.x + threadIdx.x;

}

این قسمت میگه که مثلا thread با id (0,1) که در بلاک (0,0) قرار دارد اگر فرض کنیم بلاک ما 4*4 باشد به این صورت در نظر گرفته میشود که:

این thread مسئول حساب کردن ردیف ۱ و ستون ۰ هستش.

 // Boundary check for our matrix

if(row < N && col < N){

          int tmp = 0;

           for(int i = 0; i < N; i++){

                 tmp += a[row * N + i] * b[i * N + col];

}

// Write back the result

c[row * N + col] = tmp;

}

باقی داستان هم برمیگرده به ضرب و جمع که به راحتی انجام میشه. در این مثال در نظر بگیرید که فقط ماتریس مربعی در نظر گرفته شده است و همان طور که میبینید توانستیم در O(n) ماتریس ها را در هم ضرب کنیم و این خیلی هیجان انگیزه :)

نتیجه گیری

در این سه پستی که نوشتم راجع به برنامه نویسی موازی گفتم و بعد راجع به syntaxهای برنامه نویسی Cudaنوشتم و در آخر از این دانش ها استفاده کردم و ضرب دو ماتریس را از مرتبه O(n^3) به O(n) رساندم.

امیدوارم این سری پست ها در آینده به کار کسی بیاد و اگر تا اینجای مطلب رو خوندید. مرسی:)