۳- پیاده سازی الگور یتم ضرب مـاتر یس تنـک در بردار رو ی پردازنـده هـای گراف ی کـی و تحق یقـات مرتبط
پیادهسازی الگور یتم ضرب ماتریسهای متـراکم در بـردارروی پردازندهها بس یار ساده است. شکل (۳) الگوریتم این کاررا در قالب یک برنامه به زبانC++ نشان میدهد. هنگامی کهماتریس تنک بوده و به روش سطر تنک متراکم نگهداری شدهباشد، با ید تغ ییراتی در ایـ ن الگـوریتم صـورت گ یـرد. واضـح
for (unsigned int i = 0; i < NumberOfRows; i++)
{
double Sum = 0.00;

for (unsigned int j = 0; j < NumberOfColumns; j++)
{
Sum += A[i][j] * X[j];
}

Y[i] = Sum; }
شکل ۳- پیاده سازی الگوریتم ضرب ماتریسهای متراکم در بردار روی پردازندهها

for (unsigned int i = 0; i < NumberOfRows; i++)
{
double Sum = 0.00;

for (unsigned int j = RowIndices[i]; j < RowIndices[i + 1]; j++)
{
Sum += Values[j] * X[ColumnIndices[j]];
}

Y[i] = Sum;
}
شکل ۴- پیاده سازی الگوریتم ضرب ماتریسهای تنک در بردار روی پردازندهها
است که در این حالت اعمال ضرب و جمـع تنهـا بایـ د رو ی مقادیر غ یرصفر انجام گیرد. برای این کار با توجه به شکل (۴) و با استفاده از بردار کمک ی اندیس سطرها، ابتدا و انتهـا ی هـرسطر به دست م یآید. سپس با انجام یک حلقه روی این سـطرمقادیر از بردار مقادیر ماتر یس استخراج شده و با کمک بـرداراندیسهای ستونی، در درایه مربوطه از بردار x ضرب میشود.
چنانچه تمام ی این مقاد یر برا ی یک سـطر بـا ی کـدیگر جمـعشوند، یک درا یه بردار حاصلضرب نها یی به دسـت مـیآ یـد.
چند نکته در این الگور یتم قابل توجه است . نخـست ایـ ن کـهدسترسی به بردارx بسیار نامنظم است. همان طور که پـیشتـراشاره شد، این مورد کارایی کل ی را به شدت تحت تاثیر قـرارمیدهد. نکته دوم نیاز به حاصلجمع تمام حاصل ضـرب هـای میانی۳۴ در هر سطر برای بهدست آوردن یـ ک درا یـه از بـردارحاصلضرب نها یی است که قسمت دوم الگوریتم را تـشکیل میدهد. این مورد به عنوان یکی از اعمال ابتـدایی۳۵ در بحـثپردازنده های گرافیکی مطرح است و به نام عملیات کاهش۳۶ شناخته م یشود. پیادهسازی یـ ک عمل یـات کـاهش بـا کـارایی مناسب در پردازندههای گراف یکی کار سادهای نیست و نیاز بـهدقت فراوان دارد. به عنوان آخرین مورد باید توجه داشت کـهتعداد عناصر غیرصفر در هر سطر در یـ ک مـاتریس لزومـﹰا بـایکدیگر برابر نیست. همچنین دل یلی ندارد این تعداد بر تعـدادواحدهای محاسبات ی د ر یک چندپردازنده بخـش پـذیر باشـد. بنابراین همواره تعدادی از واحدهای محاسبات ی بدون عملیات خواهند ماند که این مورد از کارایی کل ی الگـور یتم بـه شـدتخواهد کاست و در نتیجه، م یزان به ینه بودن الگـوریتم ارتبـاطتنگاتنگی با نحوهی توز یع مقـادیر غ یرصـفر مـاتریس خواهـدداشت. برخی از محققان تلاش کردهانـد بـه نحـوی بـا تغییـ ر تعداد سطرها یی کـه بـه یـ ک چندپردازنـده سـپرده مـی شـود،الگوریتم خـود را بـرای دسـتهای از مـاتریسهـا بهینـه کننـد [۹-۱۱]. در موارد ی نیز این کار توسط یک برنامه خـارجی وبه صورت خودکار انجام شده است [۱۲ و ۱۳]. البتـه لازم بـهذکر است تقریبﹰا تمام ی کارها ی انجام شـده در ایـ ن زمینـه بـرمبنــای کــودا انجــام شــده اســت و در نت یجــه منحــصر بــهسـ ختاافزارهـ ی شـرکت انویدیاسـت. در دسـته دیگـری از تحقیقات انجـام شـده، سـعی شـده اسـت بـا تغییـ ر نحـوهی نگهداری ماتر یس بر کارایی الگور یتم افزوده شود [۹ و ۱۱]. با توجه به کاربرد بسیار ز یاد روش نگهداری سطر تنک فـشرده،اسـتفاده از چنـ ین الگـوریتم هـایی مـستلزم تغییـرات کلـی در ساختار برنامههای قد یمی و یا تبد یل نوع مـاتریس اسـت کـههیچ کدام چندان مطلوب ن یـست. همچنـین سـایر روش هـای نگهداری ماتر یسهای تنک نیـ ز مـشکلاتی خـاص خـود دارابوده و نمیتوان آنها را حل نهـایی مـشکل دانـست. در ایـ ن مقاله سع ی م یشود بـا اسـتفاده از چنـدین تکن یـ ک، از جملـهتعیین تعداد سطرها در هر چندپردازنده در زمان اجرای برنامه، دادن آگاه ی اول یه به کامپایلر برا ی به ینهسازی هر چه بیـ شتر واستفاده از یک قسمت عملیـ ات کـاهش بـا حـداکثر کـارایی، کارایی کل ی الگور یتم بدون تغییر در ساختار مـاتریس تـا حـدامکان افزا یش یابد. این تکن یکهـا در قـسمت هـای آینـده بـهاختصار بیان خواهد شد.

۴- مبان ی کلی یک برنامه به زبان آزاد محاسباتی
مدل برنامهنویسی در زبان آزاد محاسباتی با آنچه در سایر مدلهای برنامهنویسی وجود دارد، قـدری متفـاوت اسـت. در این زبان الگوریتم به صورت یک سر ی رشته اجرایی در نظـرگرفته م یشود که همگی یک سر ی دستورات یکسان را اجـرامیکنند. این دستورات به صـورت یـ ک تـابع در نظـر گرفتـهمیشود که آن را هسته۳۷ م ینامند. میتـوان تـصور کـرد تمـامواحدهای محاسبات ی این تابع را فراخوانی و اجرا میکنند. بـهعنوان نمونه، برنامه جمع دو بردار با ی کـدیگر در نظـر گرفتـهمیشود. شکل (۵) الگور یتم لازم برای ایـ ن کـار را روی یـک پردازنده و نیز هسته معادل آن را در زبان آزاد محاسباتی نشانمیدهد. مهم ترین تفاوت این دو برنامه در حذف شدن حلقـهخارجی در هسته است که با اختصاص قسمت داخلـی حلقـهدر هر شمارنده به واحدهای محاسباتی، عم ﹰلا کار انجام شـدهدر دو برنامه معادل خواهد بود. توضیح چند نکته در ا یـن جـاضروری به نظر میرسد. نخست ا ین که هر واحـد محاسـباتی نیاز دارد موقعیت خود را در میان واحدهای محاسـ باتی دیگـربداند که این امر معادل اسـتفاده از شـمارنده حلقـه در برنامـهمربوط به پردازنده در شکل(۵) است . همان گونه که در شکلمشاهده م یشود، برا ی ا ین کار هسته میتواند از توابع موجـوددر زبان آزاد محاسباتی استفاده کند. نکته د یگری که باید بداناشاره کرد، این است که به دلایل بسیاری، ترتیب اجرای هسته روی واحدها ی محاسباتی در چندپردازندههای مختلـف قابـلپیشبینی ن یست. از این رو هنگامی یک حلقه خارجی را بدین صورت م یتوان به یک برنامه زبان آزاد محاسباتی تبدیل کـرد که هر بار اجرای حلقه از دفعات دیگـر کـام ﹰلا مـستقل باشـد. برنامه ساده ای که در این قسمت بدان پرداخته شد، دارا ی ایـ ن خصوصیت است، اما در برنامههای پ یچیدهتـر ماننـد عملیـ ات کاهش ا ین کار امکانپذیر نیست و باید با ارائهی یک الگوریتم سازگار با مدل برنامهنو یـسی زبـان آزاد محاسـباتی، عمل یـات
void AddVec( const double *x, const double *y, double *z, unsigned int N)
{
for (unsigned int i = 0; i < N; i++)
{
z[i] = x[i] + y[i];
}
}

__kernel void AddVec(
__global const double *x,
__global const double *y, __global double *z, unsigned int N)
{
unsigned int i = get_global_id(0);
if (i < N) {
z[i] = x[i] + y[i];
}
}

شکل ۵- برنامه جمع دو بردار با یکدیگر روی پردازنده و هستهی معادل آن در زبان آزاد محاسباتی

__kernel void SpMV_Naive(
__global unsigned int const *RowIndices,
__global unsigned int const *ColumnIndices,
__global unsigned int const *Values,
__global double const *X, __global double *Y, unsigned int N)
{
unsigned int i = get_global_id(0);
if (i < N) {
double Sum = 0.00;

for (unsigned int j = RowIndices[i]; j < RowIndices[i + 1]; j++)
{
Sum += Values[j] * X[ColumnIndices[j]];
}

Y[i] = Sum;
} }
شکل ۶- ساده ترین روش پیاده سازی الگوریتم ضرب ماتریس تنک در بردار در زبان آزاد محاسباتی
// WORKGROUP_SIZE_BITS and ROWS_PER_WORKGROUP_BITS are to be defined // on the command-line
#define WORKGROUP_SIZE (1 << WORKGROUP_SIZE_BITS)
#define ROWS_PER_WORKGROUP (1 << ROWS_PER_WORKGROUP_BITS)
#define LOCAL_WORKGROUP_SIZE_BITS (WORKGROUP_SIZE_BITS –
ROWS_PER_WORKGROUP_BITS)
#define LOCAL_WORKGROUP_SIZE (1 << LOCAL_WORKGROUP_SIZE_BITS)

__kernel void __attribute__((reqd_work_group_size(WORKGROUP_SIZE, 1, 1))) SpMV(
__global unsigned int const *RowIndices,
__global unsigned int const *ColumnIndices,
__global double const *Values,
__global double const *X, __global double *Y, unsigned int N, __local double *Buffer)
{ const unsigned int gid = get_group_id(0); const unsigned int tid = get_local_id(0);
const unsigned int lgid = tid >> LOCAL_WORKGROUP_SIZE_BITS; const unsigned int ltid = tid & (LOCAL_WORKGROUP_SIZE – 1);

const unsigned int Row = (gid << ROWS_PER_WORKGROUP_BITS) + lgid;

if (Row < N)
{
Buffer[tid] = 0.00;
const unsigned int Start = RowIndices[Row]; const unsigned int End = RowIndices[Row + 1];

// Actual multiplication
for (unsigned int i = Start + ltid; i < End; i += LOCAL_WORKGROUP_SIZE)
{
Buffer[tid] += Values[i] * X[ColumnIndices[i]];
}
}

// __local memory barrier barrier(CLK_LOCAL_MEM_FENCE);

// Reduction of results

#if LOCAL_WORKGROUP_SIZE > 512

if (Row < N)
{
if (ltid < 512)
{
Buffer[tid] += Buffer[tid + 512];
} } barrier(CLK_LOCAL_MEM_FENCE); #endif
#if LOCAL_WORKGROUP_SIZE > 256

در این سایت فقط تکه هایی از این مطلب با شماره بندی انتهای صفحه درج می شود که ممکن است هنگام انتقال از فایل ورد به داخل سایت کلمات به هم بریزد یا شکل ها درج نشود

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

اینجا کلیک کنید

if (Row < N) { if (ltid < 256)
{
Buffer[tid] += Buffer[tid + 256];
}

}
barrier(CLK_LOCAL_MEM_FENCE);

#endif

#if LOCAL_WORKGROUP_SIZE > 128
if (Row < N) { if (ltid < 128)
{
Buffer[tid] += Buffer[tid + 128];
}
}
barrier(CLK_LOCAL_MEM_FENCE);

#endif

#if LOCAL_WORKGROUP_SIZE > 64
if (Row < N) { if (ltid < 64)
{
Buffer[tid] += Buffer[tid + 64];
}
}
barrier(CLK_LOCAL_MEM_FENCE);

#endif

#if LOCAL_WORKGROUP_SIZE > 32
if (Row < N) { if (ltid < 32)
{
Buffer[tid] += Buffer[tid + 32];
} } barrier(CLK_LOCAL_MEM_FENCE);
#endif
#if LOCAL_WORKGROUP_SIZE > 16
if (Row < N) { if (ltid < 16)
{
Buffer[tid] += Buffer[tid + 16];
}
}
barrier(CLK_LOCAL_MEM_FENCE);

#endif

#if LOCAL_WORKGROUP_SIZE > 8
if (Row < N) { if (ltid < 8)
{
Buffer[tid] += Buffer[tid + 8];
}
}
barrier(CLK_LOCAL_MEM_FENCE);

#endif

#if LOCAL_WORKGROUP_SIZE > 4
if (Row < N) { if (ltid < 4)
{
Buffer[tid] += Buffer[tid + 4];
}
}
barrier(CLK_LOCAL_MEM_FENCE);

#endif

#if LOCAL_WORKGROUP_SIZE > 2
if (Row < N) { if (ltid < 2)
{
Buffer[tid] += Buffer[tid + 2];
}
}
barrier(CLK_LOCAL_MEM_FENCE); #endif
#if LOCAL_WORKGROUP_SIZE > 1
if (Row < N) {
if (ltid < 1)
{
Buffer[tid] += Buffer[tid + 1];
} } barrier(CLK_LOCAL_MEM_FENCE);
#endif
if (Row < N)
{
// Store final result if (ltid == 0)
{
Y[Row] = Buffer[tid];
}
}
}
شکل ۷ – پیاده سازی الگوریتم پیشنهادی ضرب ماتریس تنک در بردار در زبان آزاد محاسباتی

#pragma omp parallel for

for (unsigned int i = 0; i < NumberOfRows; i++)
{
double Sum = 0.00;

for (unsigned int j = RowIndices[i]; j < RowIndices[i + 1]; j++)
{
Sum += Values[j] * X[ColumnIndices[j]];
}

Y[i] = Sum;
}

شکل ۸- پیاده سازی الگوریتم ضرب ماتریس های تنک در بردار روی پردازنده ها با استفاده از استاندارد باز چندپردازنده

مورد نظر را انجام داد. همچنین در صورتی که یک قسمت ازبرنامه به نتایج قسمت قبل نیاز داشته باشـد، هـر یـ ک از ایـ ن قسمتها با ید در قالب یک هسته مستقل معرفی و بـه ترتیـ ب فراخوانی شوند . فراخوانی هر هسته جدا از زمـان اجـرای آن،به مقدار ی زمان نیاز دارد و بنابراین با ید برنامههـا بـه شـکلی نوشته شوند که کمترین تعـداد فراخـوانی هـستههـا را داشـتهباشند. واضح است با وجـود بـالاتر بـودن قـدرت محاسـباتی پردازندههای گراف یکی، نم یتوان اننتظـار داشـت عملکـرد هـربرنامهای در زبان آزاد محاسباتی بهتر از پردازندهها باشد . حتی گاهی بهتر است بخشی از برنامه روی پردازنده و بخشی رو ی پردازنده گرافیکی اجرا شود.

۵- پیاده سازی الگوریتم ضرب مـاتریس تنـک در بردار توسط زبان آزاد محاسباتی
سادهترین روش پیادهسازی الگور یتم ضرب ماتریس تنـکدر بــردار در شــکل (۶) نمــایش داده شــده اســت . در ایــن روش،همان گونه که پـیشتـر توضـیح داده شـد، تنهـا حلقـهخارجی در برنامه شکل (۵) حذف و محتویات حلقه به عنوانهسته مورد نظر معرفی شده است. واضح است که هـر واحـدمحاسباتی، محاسبه حاصلضرب یک سـطر از مـاتریس را بـرعهده خواهد داشت. در صورت ی که تعداد عناصر غیرصـفر درهـر سـطر بـا یکـدیگر مـساوی نباشـد، همـواره تعـدادی از واحدهای محاسبات ی بدون عملیـ ات خواهنـد مانـد. همچنـین الگوی دسترس ی به حافظه بسیار درهم ریخته اسـت. توضـیح بیشتر در مورد بهترین نوع دسترسی به حافظه در پردازندههای گرافیکـی خـارج از حوصـله ایـن نوشـتار اسـت و خواننـده میتواند به مراجع [۱۴ و ۱۵] مراجعه کند. ایـ ن مـوارد باعـثمی شود کارا یی این هسته بسیار پایین باشد.
در این تحق یق از چندین تکن یک برا ی افزا یش کارا یی ا یـن هسته اسـتفاده شـده اسـت. اولـین مـورد بـه کـارگیری یـ ک الگوریتم جد ید برا ی استفاده از چندین واحد محاسباتی بـرای محاسبه حاصلضرب یک سطر از ماتریس در بردار اسـت. از این د یـ دگاه مـیتـوان الگـوریتم هـای ارائـه شـده در مراجـع [۹ و ۱۱] را حالـت خاصـی از الگـوریتم ارائـه شـده در ایـن تحقیق دانست . تا حد اطلاع نگارنده ارائـه چنـین الگـوریتمی برای اول ین بار انجـام شـده اسـت. چنانچـه تمـام واحـدهای محاسباتی یک گروه کاری۳۸ بدون عملیات بماند، واحد کنترلعملیات جدیدی را به آنها تخص یص میدهد و در نتیجـه بـرکارایی الگـوریتم اضـافه مـیشـود . در ا یـ ن روش واحـدهای محاسباتی متوال ی مربوط به یک سـطر بـه خانـه هـای حافظـهمتوالی دسترس ی پیدا م یکنند. این الگو ی دسترسی بـه حافظـهبرای پردازندههای گراف ی کـی بـسیار مناسـب بـوده و سـرعتدسترسی به حافظه و در نتیجه کارا یی کلی را به شکل مناسبی بهبود م یبخشد. واضح است که بهترین تعداد واحد محاسباتی برای هر سطر به نحوهی توز یع عناصـر غیرصـفر در مـاتریس بستگی دارد . آنچه در این تحق یق برای اول ین بـار پ یـاده سـازی شده است، نحوهی خاص نوشتن هسته به شکلی است کـهبا کمک ماکروهای پ یشپردازنده۳۹ م یتوان به صورت کاملاﹰبهینه تعداد واحد محاسباتی در هر گروه کاری را تغییر داد.
پــارامتر بــسیار مهــم دیگــر در ایــن زمینــه تعــداد ســطراختصاص یافته به هر گروه کار ی است. این پـارامتر نیـ ز بـهصورت به ینه قابل تغییر با کمک ماکروهـای پـیشپردازنـدهاست. بیشتر محاسبات لازم وابسته به این پارامترها در زمانترجمهی هسته انجام میگیرد و حاصل آن یک هسته بسیار بهینه است . در بس یاری از کاربردها مانند حل یـک دسـتگاهمعادلات خطی، ماتریس با الگوی یکسان عناصـر غیرصـفربارها و بارها باید در بردار ضرب شوند. یک برنامه میتوانـد بـهنحوی نوشته شود کـه در زمـان اجـرا بـا تغییـ ر ا یـن پارامترهـا،بهینهترین حالت ممکن را بـرای ایـ ن الگـوی عناصـر غیرصـفرانتخاب و استفاده کند. از آنجا که ایـ ن محاسـبات بخـش بـسیار عمدهای از زمان کلی حل یک مسئله را تـشکیل مـیدهـد، ایـ ن بهی نهسازی کام ﹰلا به صرفه است.
تکنیک دیگری که برای افـزایش کـارایی هـستهی ضـربماتریس در بردار به کار رفتـه اسـت، اسـتفاده از یـک بخـشعملیات کـاهش بـا کـارایی بالاسـت. ایـ ن بخـش بـا کمـکماکروهای پیشپردازنده به شکلی نوشـته شـده اسـت کـه بـاپارامترهای گفته شده در بالا سازگار بوده و تغییر پارامترها بـهشکل به ینهای در نظر گرفته میشود. عملیات کاهش در چنـدمرحله انجام میشود. هنگامی که قسمت اول الگـوریتم پا یـ ان می یاب د، ب ه ازای ه ر ی ک از اع ضای گ روه ک اری ی ک حاصلجمع م یانی بهدست آمـده اسـت. نحـوه کـار عمل یـات کاهش بد ین صورت است که ابتـدا هـر گـروه کـاری بـه دوقسمت مساوی تقسیم م یشود. نیمه اول حاصـلجمـع م یـانی خود را با حاصل جمع میانی ن یمه دوم جمع کرده و جایگزین حاصــل جمع میانی خود می کنند. با این کار تعداد محاسباتی نیز نت یجه نها یی را در محل مربوطه در حافظه اصـلی ذخ یـ ره میکند. از آنجا که عملیات کاهش حداکثر در یک گروه کاری انجام م یگیرد، از حافظه محلی که میان واحـدهای محاسـباتی مشترک است، برای ذخ یره ا ین حاصلجمعهای م یانی اسـتفادهمیشود. این مورد کارایی این الگور یتم را بـه شـدت افـزایش می دهد.

۶- مثال های عددی
جدول ۱- مشخصات سیستم های رایانه های مورد استفاده
بستر نرم افزاری حافظه ی
اصلی پردازنده گرافیکی سیستم عامل حافظه
اصلی تعداد هسته ها پردازنده ردیف
NVIDIA
CUDA
4.1 1 GB NVIDIA
GeForce GTX 280 Ubuntu 10.10 (64 bit Linux) 4 GB 4 AMD Phenom Quad
core 9950 ۱
AMD
APP SDK
2.6 2 GB AMD Radeon HD 6970 Ubuntu 10.10 (64 bit Linux) 4 GB 4 Intel Core2 Quad Q8300 ۲

جدول ۲- سرعت حافظه سیستم های رایانه های مورد استفاده
پردازنده گرافیکی پردازنده ردیف
Copy Add Add ۱۲۰/۹۹ ۳۶/۴۱ ۷/۶۲ ۱
۱۳۸/۵۶ ۶۷/۲۷ ۴/۸۶ ۲
شکل (۷) متن کامل هسته پیاده سـازی شـده در زبـان آزادمحاسـباتی را نـشان مـی دهـد. بـرای بررسـی کـارایی هـسته پیادهسازی شده، دو سیستم را یانهای انتخاب شـد. مشخـصاتپردازنده، حافظـه اصـلی، پردازنـده گرافی کـی، حافظـه اصـلی گرافیکی و مشخصات نرمافزاری ا ین دو سیستم در جدول(۱) آمده است. همان گونه که پیشتر اشـاره شـد، سـرعت عمـلضرب ماتر یس در بردار، بسیار وابـسته بـه سـرعت حافظـهی مــورد اســتفاده اســت . بــرای بررســی ســرعت حافظــه درسیستمهای مورد اسـتفاده، از آزمـون اسـتریم۴۰ [۱۶] اسـتفادهشده اسـت. ا یـن آزمـون را مـیتـوان ی کـی از معـروف تـرین آزمونها در این زم ینه دانست . در ایـ ن آزمـون سـرعت چنـدعملیات ساده مانند جمع دو بردار و یا کپـی کـردن بخـشی از حافظه به عنـوان نمـودی از سـرعت قابـل دسترسـی حافظـهبهدست میآید. نظیر هم ین مورد توسط زبـان آزاد محاسـباتی روی پردازنده گرافیکی پ یـاده سـازی شـد. جـدول (۲) نتـایج حاصل از انجام آزمون را نـشان مـیدهـد . واضـح اسـت کـهسرعت حافظه در پردازندههای گراف ی کـی بـه مراتـب بـیش ازسرعت حافظه در پردازنده است و بنـابراین مـیتـوان انتظـارداشت که عمل ضرب ماتریس در بـردار روی پردازنـده هـای گرافیکی سریع تر انجام گیرد.
پیشتر اشاره شد که خصوصیات ماتریس مورد اسـتفاده واز آن جمله نحوه توزیع مقاد یر غ یـر صـفر، تـاثیر بـسیاری درنتایج بهدسـت آمـده دارد. از ا یـن رو، بـرای بـهدسـت آوردننتایجـ ی کـه بتوانـد گویای عملکرد واقعی روش باشد، از یک مجموعه ماتر یسهای تنک که در بسیاری از مقالات به آنهـا استناد م ی شود، استفاده شد. این مجموعـه شـامل ۱۴ مـاتر یس است که طیف بس یار گستردهای از مسائل را پوشش مـیدهـد .
مشخــصات ایــن مــاتریس هــا در جــدول (۳) آمــده اســت.
توضیحات بیشتر در مورد این مـاتریسهـا و منـشاء آنهـا درمرجع [۱۷] موجود است.
پیادهسازی برنامه اصلی توسط زبـان برنامـهنو یـسی C++ انجام شد. برای ترجمه برنامهها نیز از کامپایلر g++ 4.4.5 کـهبه همراه سیستم عامل عرضه میشود استفاده شده است. زمان اجرای هسته بر مبنـای زمـان روی پردازنـده (و نـه پردازنـدهگرافیکی) به کمک دقیقترین زمـانسـنج موجـود در سیـ ستم اندازهگیری شده است. این مورد از آن جهـت واجـد اهمیـ ت است که بـسیاری از مولفـان تنهـا زمـان اجـرای هـسته روی

جدول ۳- مشخصات ماتریس ها
متوسط تعداد عناصر غیر صفر در هر سطر تعداد عناصر غیر صفر تعداد ستون ها تعداد سطرها ماتریس
۲۰۰۰ ۴۰۰۰۰۰۰ ۲۰۰۰ ۲۰۰۰ Dense
۱۱۹ ۴۳۴۴۷۶۵ ۳۶۴۱۷ ۳۶۴۱۷ Protein
۷۲ ۶۰۱۰۴۸۰ ۸۳۳۳۴ ۸۳۳۳۴ FEM / Spheres
۶۴ ۴۰۰۷۳۸۳ ۶۲۴۵۱ ۶۲۴۵۱ FEM / Cantilever
۵۳ ۱۱۶۳۴۴۲۴ ۲۱۷۹۱۸ ۲۱۷۹۱۸ Wind Tunnel
۵۱ ۲۳۷۴۰۰۱ ۴۶۸۳۵ ۴۶۸۳۵ FEM / Harbor
۳۹ ۱۹۱۶۹۲۸ ۴۹۱۵۲ ۴۹۱۵۲ QCD
۵۵ ۷۸۱۳۴۰۴ ۱۴۰۸۷۴ ۱۴۰۸۷۴ FEM / Ship
۶ ۱۲۷۳۳۸۹ ۲۰۶۵۰۰ ۲۰۶۵۰۰ Economics
۴ ۲۱۰۰۲۲۵ ۵۲۵۸۲۵ ۵۲۵۸۲۵ Epidemiology
۲۲ ۲۶۲۴۳۳۱ ۱۲۱۱۹۲ ۱۲۱۱۹۲ FEM / Accelerator
۶ ۹۵۸۹۳۶ ۱۷۰۹۹۸ ۱۷۰۹۹۸ Circuit
۳ ۳۱۰۵۵۳۶ ۱۰۰۰۰۰۵ ۱۰۰۰۰۰۵ Webbase
۲۶۳۳ ۱۱۲۷۹۷۴۸ ۱۰۹۲۶۱۰ ۴۲۸۴ LP
پردازنده گراف یکی را گزارش می کنند که در نتیجه زمان صرفشده برا ی آمادهسازی هسته برای اجرا در آن منظور نمی شـود. در تمامی برنامهها، بـرای بررسـی درسـتی جـوابهـا، نتـایج بهدست آمده با نتایج برنامه مرجع روی پردازنده مقایسه شـدهو همگ ی م ورد تایی د ق رار گرفت ه اس ت. در م ورد روش پیشنهادی پارامترها با زمان گیری به نحوی انتخاب شده اند که سریع ترین حل ممکن به دست آید.
جدول ۴- زمان انجام عمل ضرب بر حسب میلی ثانیه و نسبت افزایش سرعت در سیستم شماره ۱
GPU (Proposed) GPU (Naïve) CPU (OpenMP) CPU ماتریس
سرعت نسبی زمان اجرا سرعت نسبی زمان اجرا سرعت نسبی زمان اجرا زمان اجرا ۱۵/۲۳ ۰/۷۹ ۱/۱۶ ۱۰/۴۲ ۲/۱۲ ۵/۷۰ ۱۲/۰۹ Dense
۸/۷۷ ۱/۳۱ ۲/۰۳ ۵/۶۷ ۱/۸۰ ۶/۴۱ ۱۱/۵۳ Protein
۹/۱۱ ۱/۸۱ ۲/۵۲ ۶/۵۶ ۱/۸۲ ۹/۰۷ ۱۶/۵۱ FEM / Spheres
۸/۵۳ ۱/۲۹ ۲/۴۰ ۴/۵۷ ۱/۸۷ ۵/۸۸ ۱۱/۰۰ FEM / Cantilever
۱۰/۰۵ ۳/۱۹ ۲/۸۲ ۱۱/۳۷ ۱/۹۸ ۱۶/۱۹ ۳۲/۱۰ Wind Tunnel
۸/۰۶ ۰/۸۲ ۲/۲۳ ۲/۹۶ ۱/۵۴ ۴/۲۷ ۶/۵۹ FEM / Harbor
۹/۵۲ ۰/۵۹ ۳/۰۵ ۱/۸۴ ۱/۸۶ ۳/۰۳ ۵/۶۳ QCD
۱۰/۴۱ ۲/۱۱ ۲/۵۹ ۸/۵۰ ۱/۸۷ ۱۱/۷۸ ۲۲/۰۰ FEM / Ship
۶/۷۳ ۰/۹۱ ۳/۹۳ ۱/۵۶ ۱/۸۳ ۳/۳۴ ۶/۱۱ Economics
۱۰/۳۸ ۰/۷۴ ۶/۳۶ ۱/۲۱ ۱/۶۵ ۴/۶۶ ۷/۶۹ Epidemiology
۱۰/۱۰ ۱/۰۷ ۳/۲۷ ۳/۲۹ ۲/۰۷ ۵/۲۱ ۱۰/۷۷ FEM / Accelerator
۶/۲۰ ۰/۸۵ ۳/۳۰ ۱/۶۰ ۱/۶۸ ۳/۱۴ ۵/۲۷ Circuit
۲/۶۰ ۶/۶۶ ۱/۴۷ ۱۱/۷۸ ۱/۹۳ ۸/۹۶ ۱۷/۳۱ Webbase
۱۳/۰۰ ۵/۳۲ ۰/۸۵ ۸۱/۲۳ ۱/۸۵ ۳۷/۲۹ ۶۹/۱۳ LP
جدولهای (۴) و (۵) نتایج به دسـت آمـده را بـه تفک یـک ماتریسهای مورد استفاده نشان میدهند. در ستون مربوط بـهپردازن ده، زم ان اج را ی الگ ـوریتم مرج ع ش کل (۴) روی پردازنده نشان داده شده است. این زمان بـرای مقا یـسه سـایر روشها به کاربرده شده است و افزایش سرعتها نـسبت بـهآن سنج یده شده انـد. در سـتون هـای بعـد کـارایی اسـتفاده ازاستاندارد چندپردازنده بـاز۴۱ شـکل (۸) نـسبت بـه الگـوریتم مرجع نشان داده شده است. دیده می شود استفاده از این روش که جز و روشهای حافظهی مشترک اسـت، در برخـی مـواردسرعت اجرا ی الگوریتم را افزایش داده و گاهی آن را کـاهشمیدهد. در توج یه این نتایج با ید گفت که از آنجا که مهمترین عامل در زمینه سرعت الگوریتم ضرب ماتریس هـای تنـک دربردار سرعت دسترسی به حافظه اسـت، صـرفنظـر از تعـدادهستههای پردازنده به کار رفته در اجـرای الگـوریتم، همـوارهیک حد بالا برای سرعت وجود دارد که بایـ د هز ینـهی نـسبتﹰازیاد ایجاد و از بین بردن رشتههای اجرا یی مـورد اسـتفاده دراین روش را نیز بدان افزود که ممکن است چنـین نتـایجی را به دنبال داشته باشد. در ستونهای بعد کارایی الگور یتم سـادهضرب ماتر یسهای تنک در بردار روی پردازندههای گراف یکی شکل (۶) مورد بررسی قرار گرفته است. هسته بـه کـار رفتـهبرای استخراج این نتا یج دق یقﹰا همان هسته ضرب مـاتریس دربردار مورد استفاده در کتابخانه توابع وینا س ی ال [۸] اسـت و بنابراین م یتواند بر اوردی از کـارایی نـسبی روش ارائـه شـدهبهدست دهد . دیده م یشود این الگور یتم بـا وجـود سـادگی وعدم استفاده به ینه از منابع موجود توانسته است سـرعت قابـلقبولی در مقا یسه با دو مورد قبلی کسب کند. ستون هـای آخـرنیز کارا یی روش پیشنهادی در این تحق یق را نـشان مـیدهـد . همانطور که دیده م یشود کارا یی روش بسیار بالاتر از تمامی موارد قبل بوده و در برخی موارد نزدیک ۲۰ برابر سریعتـر از الگوریتم مشابه در پردازنده عمـل کـرده اسـت . بایـ د در نظـرداشت هر چند مقادیر گزارش شده برای زمان اجـرا بـا تغییـ ر پارامترها و انتخاب بهترین مور د به دست آمدهاند، اما می تـوان
جدول ۵- زمان انجام عمل ضرب بر حسب میلی ثانیه و نسبت افزایش سرعت در سیستم شماره ۲
GPU (Proposed) GPU (Naïve) CPU (OpenMP) CPU ماتریس
سرعت نسبی زمان اجرا سرعت نسبی زمان اجرا سرعت نسبی زمان اجرا زمان اجرا ۱۹/۶۲ ۰/۴۲ ۳/۱۳ ۲/۶۶ ۰/۵۲ ۱۶/۰۰ ۸/۳۲ Dense
۱۲/۹۸ ۰/۶۹ ۱/۳۴ ۶/۷۴ ۰/۹۷ ۹/۳۲ ۹/۰۰ Protein
۱۱/۹۷ ۱/۰۸ ۱/۳۶ ۹/۵۰ ۱/۱۶ ۱۱/۱۶ ۱۲/۹۱ FEM / Spheres
۱۰/۲۹ ۰/۸۴ ۱/۳۵ ۶/۳۸ ۱/۱۶ ۷/۴۲ ۸/۵۹ FEM / Cantilever
۱۱/۴۸ ۲/۰۶ ۱/۳۵ ۱۷/۴۶ ۱/۱۳ ۲۱/۰۲ ۲۳/۶۵ Wind Tunnel
۱۰/۲۰ ۰/۵۳ ۱/۶۶ ۳/۲۵ ۱/۱۳ ۴/۸۰ ۵/۴۱ FEM / Harbor
۹/۱۳ ۰/۴۷ ۱/۵۷ ۲/۷۵ ۱/۰۷ ۴/۰۲ ۴/۳۱ QCD
۱۱/۴۸ ۱/۴۱ ۱/۴۲ ۱۱/۴۰ ۱/۱۱ ۱۴/۵۳ ۱۶/۱۷ FEM / Ship
۱۱/۳۱ ۰/۵۸ ۵/۶۹ ۱/۱۵ ۱/۷۸ ۳/۶۶ ۶/۵۴ Economics
۱۴/۰۸ ۰/۴۹ ۷/۶۰ ۰/۹۱ ۱/۰۷ ۶/۴۸ ۶/۹۳ Epidemiology
۱۲/۴۳ ۰/۷۹ ۲/۶۳ ۳/۷۳ ۰/۹۹ ۹/۸۷ ۹/۸۰ FEM / Accelerator
۴/۷۴ ۱/۱۷ ۴/۱۶ ۱/۳۳ ۱/۵۵ ۳/۵۶ ۵/۵۲ Circuit
۲/۳۴ ۶/۵۲ ۱/۵۱ ۱۰/۱۴ ۱/۲۴ ۱۲/۳۶ ۱۵/۲۸ Webbase
۱۶/۸۲ ۳/۸۲ ۱/۲۵ ۵۱/۳۳ ۱/۰۸ ۵۹/۵۰ ۶۴/۲۲ LP

جدول ۶- تاثیر پارامترها در زمان اجرای الگوریتم بر حسب میلی ثانیه

بر اساس خصوصیات ماتر یس نیز مقاد یر به ینه و یا نزد یک بـهبهینه برا ی هر ماتریس را انتخاب کرد. شبیه این کار در برخی از تحق یقات د یگر انجام گرفته و میتواند به عنوان مکمل ایـ ن تحقیق مورد نظر قـرار گ یـرد. همچنـین اجـرای الگـوریتم بـهدفعات نشان میدهد که پارامترهای به ینه تنها به نوع مـاتریس بستگی داشته و در اجراهای مختلف ثابت هستند.
برای بررس ی م یزان تـاثیر ایـ ن پارامترهـا در زمـان اجـرای
الگوریتم، ماتریس FEM / Spheres رو ی سیـ ستم شـماره (۲) در نظر گرفتـه شـده و زمـان اجـرای تمـامی حـالات ممکـنپارامترهـا در جـدول (۶) نمـایش داده شـده اسـت. مـشاهده میشود هر چند استفاده از پارامترها تاثیرات بـسیار مهمـی درسرعت اجرا ی الگور یتم دارند، اما در نزدیکی پارامتر بهینه (که در جدول با خط زیر نشان داده شده است)، حساس یت نسبتبه پارامترها نـسبتﹰا پـایین اسـت و مـیتـوان امیـ دوار بـود درصورتی که امکان بهینهسازی سرعت اجرا با زمانگیری وجودنداشته باشد، انتخاب نسبتﹰا خوب پارامترهای به ینـه منجـر بـه
واژه نامه


پاسخ دهید