پياده سازي يک هسته ي قابل تنظيم ضرب ماتريس هاي تنک در بردار به کمک زبان آزاد محاسبات ي رو ي پردازنده هاي گرافيکي

١ فرشيد مسيبي گروه مهندسي عمران، دانشکده فني و مهندسي، دانشگاه اصفهان

(دريافت مقاله: ٢٤/٠٢/١٣٩١- دريافت نسخه نهايي: ٠٩/١٠/١٣٩١)

چكيده – ضرب ماتريسهاي تنک در بردار اصليترين پا يه روشهاي تکراري در حل دستگاههاي معادلات خطي به شمار مي رود. تقريبـاﹰ تمـامي روش هـاي عددي نياز به حل چنين دستگاهي از معادلات خطي در فرايند حل خود دارند. تا کنون تحقيقات بسيار زيادي در اين زمينه انجام گرفته و هنوز نيز در حال انجام است. يکي از مناسبترين روشها براي انجام سريعتر اين گونه عمليات استفاده از پردازندههاي گراف يکي است . اين پردازندهها در سال هـاي اخ يـ ر رشـد بـسيار يريچشمگ از نظر قدرت پردازش داشتهاند. در اين تحق يق روش ي نو براي انجام اين عمل ياتروي پردازندههاي گراف يکي با کمک زبان آزاد محاسباتي ارائه شـدهاست. نتايج نشان ميدهد با بهينهسازي پارامترها ي اين روش ميتوان کارا يي به مراتب بالاتر از انجام اين عمل روي پردازندهها حتـي بـا کمـک اسـتاندارد بـازچندپردازنده اي به دست آورد. همچنين نتايج نشان مي دهد در نزديکي پارامترهاي بهينه اين روش حساسيت چنداني وجود ندارد که کار را براي تخمين آن ها از روي مشخصات ماتريس بسيار ساده تر مي كند.

واژگان كليدي : ضرب ماتريس هاي تنک در بردار، پردازنده هاي گرافيکي، زبان آزاد محاسباتي

Implementation of a tunable sparse matrix-vector product kernel using OpenCL on graphics processing units

F. Mossaiby
1. Department of Civil Engineering, Faculty of Engineering, University of Isfahan

Abstract: Sparse matrix-vector multiplication (SpMV) is the key operation in the iterative methods for solving linear systems of equations. Almost all numerical methods need to solve such a system in their solution procedure. There have been a lot of researches on this subject and it is still a very hot research area. One of the best methods to increase the performance of this operation is using graphics processing units (GPUs). These processors have had a great improvement in their processing capabilities. In this research, a new method to perform this operation using open computing language (OpenCL) is presented.
The results show that by optimizing the parameters of this method one can gain a much higher performance compared to CPUs, ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
* : مسئول مكاتبات، پست الكترونيكي: mossailby@eng.ui.ac.ir
١٣٩٢
even when using the open multi-processing standard (OpenMP). Also, the results show that there is not much sensitivity near the optimal parameters, which paves the way to estimate them from the matrix properties.

Keywords: Sparse matrix-vector product, Graphics processing unit (GPU), Open computing language (OpenCL)
١- مقدمه
بيشتر روشهاي عـددي در قـسمتي از رونـد حـل خـودنيازمند حل دستگاههاي معادلات خطـي هـستند. بـا افـزايش حجم مسئله، تعداد اين معادلات نيز افزا يش يافته و به سادگي ميتواند به ميليونها معادله برسد. در ا ين موارد ديگر اسـتفادهاز روشهاي مستق يم۱ حل دستگاههاي معادلات خطي هماننـدروش چولسک ي۲ به سادگي امکانپذير نيست و به جـاي آن ازروشهاي تکرار ي۳ استفاده ميشـود . از جملـه ايـ ن روشهـاميتـوان بـه روش گراديـ ان مـزدوج۴ و يـ ا گراد يـ ان مـزدوجدوگانه۵ اشاره کرد که همراه با ساير روشهايي از اين دسـت،در زمـره روش اهـ ي زيرفـضا ي کرايلـف۶ جـاي مـ يگيرنـد.
مهمترين جزء اين روشها که م يان تمام آنها مـشترک اسـت،نياز به محاسبه ضرب يک ماتر يس (که معمو ﹰلا همان مـاتريس ضرايب دستگاه معادلات است) در يک بردار است. از اين رواين جزء، پايه پياده سـازي هـر يـ ک از روش هـاي ز ي رفـضاي کرايلف است.
در اکثر روشهاي عدد ي، ماتر يس ضرا يب بهدسـت آمـدهماتريسي تنک ۷ است، بدان معني کـه بيـ شتر درا يـه هـاي آن راصفرها تـشکيل مـيدهنـد کـه در ضـرب مـاتريس در بـرداربيتاثيرند. از اين رو براي آنکه حافظه رايانه صرف نگهـداري اين صفرها نشده و همچنين برا ي جلوگ يري از انجام عمليات رياضي بيهوده و اتـلاف قـدرت پـردازش رايانـه، روش هـاي متعددي بر اي ذخ يره ماتر يسهاي تنک ابداع شده است که بـااستفاده از آنها م يتوان تنها درايههاي غ ير صـفر را بـه کمـکمقدار کمي اطلاعات جانبي بـراي بازسـازي مـاتريس اصـلي نگهداري كرد. يکي از قديميترين اين روشهـا، روش سـطرتنک فشرده ۸ [۱] است. اين روش کام ﹰلا کلي بوده ميتواند بـر خلاف برخ ي روشهاي د يگر هر ماتريسي با هر خـصوصيتي (مانند تقارن ) را نگهدار ي كند. اين خـصوصيات باعـث شـدهاست با وجود برخي مشکلات که در ادامه خواهـد آمـد، ايـ ن روش هنوز هم پرکاربردترين روش نگهـداري مـاتريس هـاي تنک باشد و بسياري از کتابخانههاي توابع و برنامهها از آن بهعنوان مبنا ي پ يادهسازي استفاده كنند.
در شکل (۱) نحوهي نگهدار ي يک ماتر يس تنک به کمکروش سطر تنک فشرده نمايش داده شده است. در ايـ ن روشبه جا ي کل ماتريس، تنها سه بردار نگهداري م يشـود . اولـين بردار، بردار مقادير نام دارد و تمام مقادير غير صفر ماتريس راسطر به سطر در خود جاي داده است. براي عملکرد بهتر ايـ ن روش، سع ي م يشود که مقادي ر يک سطر نيز به ترتيب سـتون ي کنار يکديگر قرار داده شود. غير از اين بردار، دو بـردار ديگـراز جنس اعداد صحيح تعريف م يشوند که يکي اختصاص بـهنگهداري اند يس محل شروع هر سطر در بردار مقادير داشته و ديگري شماره ستون هر يک از اعـداد ذخيـ ره شـده در بـردارمقـادير را نگهـداري مـ يکنـد. بـه ايـن ترتيـب، ابعـاد بـردار انديسهاي سطر ي و ستوني به ترت يب برابـر تعـداد سـطرها وتعداد عناصر غيرصفر ماتر يس است . براي دسترس ي به عناصـرغيرصفر يک سطر که در اعمالي مانند ضرب بردار در ماتريس مورد نياز است، ميتوان انديس سطر دلخواه و سطر پس از آن را از بردار انديسهاي سطر ي استخراج كرده و به راحتـي بـهاين عناصر دسترسي پيدا کرد. براي اين کار در تمـام سـطرها(از جمله سطر آخر) قابل انجام باشد، مرسوم اسـت کـه يـ ک انديس صور ي به انتهاي اند يسهاي سطر ي به نحـوي اضـافهميشود که قاعده بالا در مورد سطر آخر نيز برقـرار باشـد. در نتيجه ابعاد بردارهاي مقاد ير و انديس هاي ستوني برابـر تعـدادعناصر غير صفر ماتريس و تعداد عناصـر بـردار انـديس هـاي سطري، يک ي بيش از تعداد سطرها ي ماتريس خواهد بود.
با وجود قابليتهاي ذکـر شـده بـراي روش سـطر تنـک
فشــرده، مشکلاتـي نيز در اين زمينه وجود دارد که مهمترين

0123
5 1 3 2 9
0Values = [5, 1, 3, 2, 9]
1RowIndices = [0, 1, 2, 4, 5]
ColumnIndices = [1, 0, 1, 2, 3]
2
3

شکل ۱- نحوه ي نگهداري يک ماتريس در قالب سطر تنک فشرده

آنها دسترس ي نامنظم به حافظـهي را يانـه در هنگـام اعمـالي مانند ضرب ماتريس در بردار است. اين مورد باعث مـيشـوددر معماريهايي از رايانه که از حافظه سريع کمک ي۹ برا ي بالابردن سرعت حافظهي اصلي را يانه استفاده ميکنند، تعداد عدمموفقيـت در دسترسـي۱۰ بـالا رفتـه و سـرعت دسترسـي بـه حافظهي اصـلي کـاهش يابـد . از آنجـا کـه در عمـل ضـربماتريس تنک در بردار سرعت دسترسي به حافظـه بـه شـدتگلوگـاهي اسـت، ايـن کـاهش سـرعت بـه کـاهش سـرعت محاسبات خواهد انجاميد. در معمار يهاي برداري ن يز به علتنامنظمي دسترس ي به حافظه ي اصلي مـشکلات مـشابه ي روي خواهد داد . حدود ۸۰% از زمان حـل يـ ک دسـتگاه معـادلاتخطــي بــه روشهــاي زيرفــضا ي کرايلــف بــراي محاســبه حاصلضرب ماتر يس در بردار صرف م ي شود، از اين رو انجام هر چه سريعتر اين محاسـبه، نقـش بـسيار عمـدهاي در حـلسريعتر دستگاههاي معادلات خطـي دارد و ايـ ن مـورد هنـوزموضوع تحقيقات بسيار زيادي را به خود اختصاص مي دهد.
با افزا يش بيسابقه حجم محاسبات مورد نيـ از در مـسائلمهندسي و محدوديت افزا يش سرعت پردازندهها به علتهاي فراوان، مهندسان براي انجـام ايـ ن محاسـبات بـه روش هـاي ديگري رو ي آوردند که اصطلاحﹰا به آنها محاسبات با کارايي بالا۱۱ گفته ميشود. اين روشها را ميتوان به سه دسته عمـدهتفکيک کرد. در دسته اول که به آنهـا حافظـه گـسترده۱۲ ن يـز گفته ميشود، الگوريتم مسئله مورد نظـر بـه نحـوي شکـستهمي شود که رو ي تعداد ي رايانه مستقل يا گره محاسباتي۱۳ قابل انجام باشد. از آنجايي که در مراحل مياني هر گره ممکن است به نتايج ساير گره ها نياز داشته باشد، ارتباط ميان گره ها بايد به صورتي برقرار گردد. سادهترين نـوع ايـ ن ارتبـاط، اسـتفاده ازشبکههاي محل ي۱۴ است . در دسته دوم يا حافظه مشترک۱۵، ازپردازندههاي چند هستهاي۱۶ استفاده شده و مسئله م يان آنهـا تقسيم م ي شود. هر يک از اين دو دسته، مزايا و معايب خاصخود را دارا هستند و تحقيقات بـسيار گـستردهاي رو ي آنهـا انجام شده و يا در حال انجام است . در دسته سوم که به لحاظتــاريخي بــسيار جديــدتر از دو دســته قبلــي اســت، از کمکپردازندههاي محاسبات ي۱۷ برا ي انجـام محاسـبات سـريع استفاده مـيشـود . ايـ ن کمـکپردازنـدههـا مـيتواننـد شـاملشتابدهندههاي محاسباتي۱۸، پردازنده هـاي گرافي کـي۱۹ و يـ ا ساير انواع کمک پردازندهها باشند.
در سالهاي اخ ير، قدرت محاسباتي پردازندههاي گراف يکي به نحو بيسابقهاي بس يار بـيش از پردازنـدههـا افـزايش يافتـهاست. اين پردازندهها در ابتدا تنها براي انجام اعمال گرافي کـي مورد استفاده قرار ميگرفتند، امـا پـس از مـدتي محققـان بـهاستفاده از آنها در انجام سر يعتر محاسـبات روي آوردنـد. از آنجا که نرمافزار و سختافزار مورد استفاده تنها براي کارها ي گرافيکي در نظر گرفته شده بـود، امکـان اسـتفاده عمـومي ازآنها در تمامي مسائل وجود نداشت. همچنين محققان مجبوربودند از کتابخانـه هـاي توابـع گرافي کـي ماننـد کتابخانـه آزادگرافيکي۲۰ استفاده كنند که اين مورد بر سختي کار مـيافـزود[۲]. با وجود اين مشکلات، محققان بسياري از اعمال ابتدايي مانند عمل يات ماتر يسهاي پر و بردارها را روي پردازنده هـاي گرافيکي پيادهسازي كرده و به کمک آنها اعمال ي ماننـد حـلکردن دسـتگاه هـاي معـادلات خطـي را انجـام دادنـد [۳]. بـافراگيرتر شدن استفاده از پردازنده هـاي گرافي کـي، سـازندگاناين پردازندهها با ايجـاد تغييـ رات گـسترده در سـختافـزار ونرمافزار، اين پردازندههـا را بـه وسـايلي ا يـدئال بـراي انجـامبسياري از محاسبات مهندس ي تبدي ل كردند. يکي از موفق ترين نمونــه هــا در ايــن زمينــه کــودا ۲۱ [۴] متعلــق بــه شــرکت انويديا۲۲ است . کودا پس از ارائهاش در فوريه ۲۰۰۷ مـيلادي و گسترش روزافزون خود، توانسته است بـسياري از محققـانرا براي استفاده از پردازندههاي گراف يکي در محاسـبات خـودترغيب كرده و به بسياري از برنامه هـاي علمـي و تجـاري راهپيدا ک ند. کودا با هدف استفاده در محاسـبات بـا کـارايي بـالابهوجود آمده و به علت توسعهي سر يع، پـشتيباني از سيـ ستم عاملهاي معروف، رايگـان بـودن ابـزار توسـعه و مـستنداتتوانسته است جايگاه مهم ي در اين زمينـه پيـ دا كنـد . تـاکنونفعالي ت ه اي زي ادي در زمين ه اس تفاده از ک ودا در جه ت فعاليتهاي علم ي انجام شده است که به عنوان نمونه ميتوان بـه پ يـادهسـازي کتابخانـه اهـ ي توابـع مربـوط بـه بردارهـا و ماتري سهاي اشاره كرد[۵].
مشکلي که در اين هنگام به وجود آمد، اختـصاصي بـودنهر يک از زبانها و کتابخانههاي توابع به سختافزار شـرکتتوليدکننده خود بود که باعث ميشد برنامـهاي کـه بـر مبنـاي يکي از اين زب انها و کتابخانه هـاي نـرم افـزاري توسـعه يافتـهاست، قابل استفاده روي سا ير سختافزارها نباشد . براي رفـعاين مشکل در دسامبر سال ۲۰۰۸ م يلادي، شـرکت اپـل۲۳ بـهکمک تعداد ي از شرکت هـاي مهـم در ايـ ن زمينـه، زبـان آزادمحاســباتي۲۴ را ارائــه كرد [۶]. زبــان آزاد محاســباتي يــک استاندارد باز۲۵ است که فارغ از نرمافزار و سـختافـزار، يـ ک زبان واحد و يک رابط کتابخا نـه هـاي نـرم افـزاري را معرفـي ميكند که ميتواند بـراي دسترسـي و انجـام محاسـبات روي انواع پردازندهها و کمکپردازندهها مورد اسـتفاده قـرار گ يـرد.
اين استاندارد توسط برترين شرکتهاي سازنده پردازندههـا وپردازندههاي گراف يکي حمايت م يشود. مهمترين ويژگي زبـانآزاد محاسبات ي، عدم وابـستگي برنامـه بـه نـوع سـختافـزار،نرمافزار و شرکت سازنده است که باعث ميشود يـ ک برنامـهنوشته شده با اين زبان بدون تغيير و يا با تغييرات جزيي قابلاجرا رو ي سختافزارهاي مختلـف از شـرکت هـاي مختلـفباشد. بايد توجه داشت که اين مسئله جدا از بهينه بودن برنامهروي سختافزارهاي مختلف است. اين موضوع با توجـه بـهپيچيدگي سختافزار پردازندههاي گراف ي کـي بـه خـوبي قابـلدرک است . تحقيقات نش ان م يدهد در يک مقا يـ سه متناسـب،کـارايي زبـان آزاد محاسـبات ي روي سـخت اافزارهـ ي مـشابه ميتواند با کارايي کودا رقابت كند [۷]. امروزه با فراگير شـدنزبان آزاد محاسباتي، اين زبان نيـ ز راه خـود را بـه محاسـباتعددي باز كرده است. از جمله کتابخانههاي توابع بسيار را يـ ج در اين زم ينه م ي توان به کتابخانه توابع وينا سـ ي ال [۸] اشـارهكرد. اين کتابخانه علاوه بر يک مجموعه کامل از توابع مربوطبـه مـاتريس اهـ ي پـر و بردارهـا، داراي تـوابعي بـراي حـل دستگاه هاي معادلات خط ي است.

۲- سخت افزار پردازنده هاي گرافيکي
همان گونه که پيشتر اشاره شد، پردازندههاي گراف يکي درسالهاي اخ ير رشـد بـيسـابقهاي از لحـاظ قـدرت پـردازشداشتهاند. امروزه توان محاسباتي يک پردازنده گرافيک ي چندين برابر سريعترين پردازندههاي موجود است. دلايل ا ين رشد رامـي ت وان در چن د عام ل ج ستجو ک رد . ابت دا باي د گف ت پردازندههاي گراف يکي تعداد هستههاي بسيار ب يـشتري از يـ ک پردازنده عاد ي دارند . به عنـوان نمونـه يـ ک پردازنـده بـسيار پيشرفته فعلي حداکثر داراي ۸ هسته است، در صورتي که يک پردازنده گراف يکي م يتواند دارا ي ۵۱۲ هسته باشد. بدين سببپردازن ده ه اي گرافيک ي در زم ره پردازن دهه اي ب ا تع داد هستههاي زياد۲۶ طبقهبندي م يشوند. بايد دانست که هر هستهيک پردازنده گرافيک ي بسيار ضعيف تر از يک هـسته پردازنـدهعادي است، اما به لحاظ تعداد بسيار بيشتر و سـاختار خـاصپردازنـده اهـ ي گرافيکـي، ايـن پردازنـده هـا مـي تواننـد تـوان محاسباتي بسيار بالا يي از خود بروز دهند. دومين عا مل در بالابودن قدرت محاسباتي اين پردازندهها را بايد در نوع معماري آنها جستجو كرد. در اين معمـار ي، يـ ک پردازنـده گراف ي کـي مشتمل بر تعدادي واحد چندپردازنده۲۷ است که هـر يـ ک بـهنوبه خـود بـه تعـدادي واحـد محاسـباتي تقـسيم مـيشـوند .

شکل ۲- نمايي از معماري پردازنده هاي گرافيکي
شکل (۲) نمايي از اين معماري را نشان مي دهد. در هر يک از چندپردازندهها در هر زمان تنها يک دستور مـشابه روي تمـامواحدهاي محاسبات ي با دادههاي گوناگون اجـرا مـيشـود . بـههمين دل يل در اين معمار ي، محاسبات ي که شامل اجـراي يـ ک سري دستور خـاص روي حجـم بـالايي از دادههـا باشـد، بـاسرعت بس يار بالا يي اجرا ميشود. به عنوان نمونه ميتـوان بـهجمع دو بردار با تعداد بسيار ز ياد درا يهها اشاره كرد. اگـر بـهدليلي همانند وجـود دسـتورات شـرطي لازم باشـد برخـي ازواحدهاي محاسبات ي دستورات ديگري را انجام دهنـد، واحـدکنترل شاخههاي مخت لف دستورات شرطي را به صورت نوبتي در صف اجرا قرار ميدهد. واضح است که اين کـار عملکـردکلي را به شدت تحت تاثير قرار ميدهد و بايد تا حـد امکـاناز نوشتن برنامهها به اين صورت خودداري کرد . در اينجا با يد اشاره كرد در مقايسه با پردازندهها، هز ينه بهوجود آوردن يـ ک رشته اجرا ۲۸ در پردازندههاي گراف يکي بس يار کمتر است. بدين سبب يک رشته عمليات را ميتوان به هـزاران رشـته اجرايـي تقسيم كرد که واحـد کنتـرل پردازنـده گرافي کـي آنهـا را بـهترتيب به چندپردازنـدههـا و در نتيجـه واحـدهاي محاسـبات ي تخصيص داده و آنها را اجرا ميکند. عامل سو م را مـيتـوانساختار حافظه در پردازندههاي گراف يکي دانـست. در مقا يـ سه با پردازندهها، ساختار حافظه پردازنـده هـاي گراف ي کـي بـسيار پيچيدهتر است . چهار نوع حافظـه مختلـف در پردازنـده هـاي گرافيکي به کار ميرود که هـر يـ ک کـاربرد خـاص خـود رادارنـد. حافظـه اصـلي۲۹ پردازنـده گرافيکـي کـه ميـان همـه چندپردازندهها مشترک است، بيشترين حجم را دارا بوده ولـي دسترسي به آن بسيار کندتر از ساير انواع حافظـه اسـت. ا يـن تنها نوعي از انواع حافظـه هـاي موجـود روي پردازنـده هـاي گرافيکي است که امکان انتقال دادهها از حافظه اصـلي را يانـهبه آن وجود دارد. اين انتقال از طريـ ق درگـاه دادههـا ۳۰ انجـامميگيرد و با وجود سرعت بالا، چنانچه برنامهاي نياز به انتقالمکرر دادهها از حافظه اصلي رايانه به حافظه اصـلي پردازنـدهگرافيکي داشته باشـد، کـارايي آن بـه شـدت کـاهش خواهـديافت. از ديگر انواع حافظه در پردازندههاي گراف يکي م يتـوانبه حافظه ثابـت۳۱ بـراي مقـاد يري کـه در طـول اجـراي يـک رشتهمحاسباتي تغيير نميکنند اشاره كرد. همچنين ميتـوان ازحافظه محلي۳۲ که ميان واحدها ي محاسباتي يک چندپردازندهب ه ص ورت مـشترک قاب ل دسترس ي اس ت و ني ز حافظ ه خصوصي۳۳ که مختص هر واحد محاسـباتي اسـت، نـام بـرد.
حجم اين حافظهها بسيار کمتر از حافظه اصلي بوده و عمـدتﹰاسرعت دسترس ي به آنها بسيار ب يشتر اسـت. بـه عنـوان مثـالدسترسي به حافظه محلي م يتواند ۶۰۰ تا ۷۰۰ برابر سريعتـراز حافظه اصلي باشد. نکته بسيار مهم در اين جا شناخت بسيار دقيق انـواع حافظـه و اسـتفاده صـحيح از آن هـا در الگـوريتم محاسباتي است کـه ايـ ن موضـوع مـيتوانـد سـرعت انجـاممحاسبات را به حـداکثر نزديـ ک کنـد. آنچـه ذکـر شـد تنهـاگوشهاي از پيچيدگيهاي سختافزار پردازنده هـاي گراف ي کـي جديد است . شناخت دقيق سختافـزار مـيتوانـد راهگـشاي انجام محاسبات سريع با اسـتفاده از پردازنـده هـاي گراف ي کـي باشد.

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

۷- نتيجه گيري
در اين تحق يق يک هـسته ضـرب مـاتريس هـاي تنـک دربردار توسط زبان آزاد محاسبات ي رو ي پردازنده هـاي



قیمت: تومان


دیدگاهتان را بنویسید