۳- پياده سازي الگور يتم ضرب مـاتر يس تنـک در بردار رو ي پردازنـده هـاي گراف ي کـي و تحق يقـات مرتبط
پيادهسازي الگور يتم ضرب ماتريسهاي متـراکم در بـردارروي پردازندهها بس يار ساده است. شکل (۳) الگوريتم اين کاررا در قالب يک برنامه به زبان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 رو ي سيـ ستم شـماره (۲) در نظر گرفتـه شـده و زمـان اجـراي تمـامي حـالات ممکـنپارامترهـا در جـدول (۶) نمـايش داده شـده اسـت. مـشاهده ميشود هر چند استفاده از پارامترها تاثيرات بـسيار مهمـي درسرعت اجرا ي الگور يتم دارند، اما در نزديکي پارامتر بهينه (که در جدول با خط زير نشان داده شده است)، حساس يت نسبتبه پارامترها نـسبتﹰا پـايين اسـت و مـيتـوان اميـ دوار بـود درصورتي که امکان بهينهسازي سرعت اجرا با زمانگيري وجودنداشته باشد، انتخاب نسبتﹰا خوب پارامترهاي به ينـه منجـر بـه
واژه نامه


پاسخ دهید