مقاله موازی سازی محاسبات به کمک کودا

بخشی از مقاله

موازی سازی محاسبات به کمک کودا

چکیده

امروزه یکی از دغدغههای انجام محاسبات سنگین توسط برنامهها والگوریتمهای مختلف، در زمان محاسبات می-باشند.که پیشنهادهای مختلفی در کاهش زمان طی انجام محاسبات ارائه شده است. که بدون شک موازی سازی الگوریتمهای محاسباتی بعنوان موفقترین پیشنهاد در کاهش زمان انجام محاسبات میباشد. یکی از مولفههای مهم محاسبات موازی انجام همزمان محاسبات توسط چندین هسته است. حجم زیاد و پیچیدگی محاسبات، محاسبات توسط پردازنده مرکزی را با چالشهای جدیدی مانند زمانبری مواجه ساخته است و با توجه به حجم محاسبات و اهمیت سرعت الگوریتم در انجام محاسبات، در این مقاله جهت مقایسه نتایج از الگوریتم جمع آرایهها را بهکمک پردازش موازی با معماری قدرتمند Cuda C Nvidia جهت محاسبات موازی استفاده مینماییم. و به بررسی زمان اجرا نتایج میپردازیم.

واژگان كلیدی: پردازش موازی، پردازندههای چند هسته ای، کودا،CPU،GPU

1

1 مقدمه

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

1.1 روش تحقیق

نوع پژوهشی که در این پژوهش بکار گرفته میشود از نوع کتابخانهای است. در این پژوهش در ابتدا اطالعات مورد نیاز و مرتبط با الگوریتم محاسباتی و موضوع موازی سازی با استفاده از پردازندههای گرافیکی از کتابها و مقاالت گردآوری و ارزیابی شدهاند. سپس سیستم پیشنهادی طراحی شده است بر روی سناریوهای مختلف که همان دیتاست است بکارگرفته میشود. در این پژوهش برای موازی سازی از معماری کودا استفاده شده است. در ادامه روشپیشنهادی مورد ارزیابی قرارگرفته و نتایج ثبت میشود که نتایج برگرفته از اجراهای مختلف با حجم داده های مختلف میباشد.

1.1 دادههای مورد استفاده

در این پژوهش جهت ارزیابی الگوریتم پیشنهادی از محیط ویژال استودیو با چارچوب کودا استفاده شده است. و برای تولید دیتاست از یک برنامه کمکی تحت زبان سی شارپ که به تولید تصادفی اعداد میپردازد جهت داده های اولیه برای انجام محاسبات استفاده شده است.

1.1 فرضیات پژوهش

در این مقاله فرضیات زیر در نظر گرفته شده است .

• اجرای موازی الگوریتم محاسباتی در پردازنده گرافیکی سرعتی به مراتب بیشتر نسبت به اجراء در پردازنده اصلی دارد.

• هر چقدر تعداد هستههای کارت گرافیک بیشتر باشد سرعت الگوریتم پیشنهادی بیشتر است

• هر چقدر تعداد دادههای اولیه بیشتر باشد تفاوت سرعت GPU از CPU بیشتر است .

1.4 الگوریتم موازی سازی محاسبه جمع دو آرایه

2

یکی از مهمترین بخش هر برنامه و یا هر الگوریتمی انجام محاسبات آن میباشد این الگوریتم ها انجام محاسبات را به-عهده میگیرند. در این پژوهش فرض بر این است که محاسبات برای جمع آرایهها با دادههای اولیه معطوف شده است. فرمول اصلی جمع آرایهها به شکل رابطه )1( تعریف میشود:
رابطه r)i(=∑ a(i)+b(i)+……………….n(i) ( 1

در رابطه باال، r(i) جمع آرایهها را نگهداری میکند و a(i) بعنوان آرایه اول و(b(i بعنوان آرایه دوم تا آرایه nام را دارند.

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

همانطور که واردحوزه محاسبات GPU می شویم، برنامههای کاربردی ذاتا موازی به طور فزاینده ای از توانایی فراوان محاسبات موازی GPU برای رسیدن به کارایی و بازدهی باالتر استفاده می کنند. برنامههای کاربردی که قبال به علت زمان باالی اجرای آنها نامناسب بودند امروزه توسط محاسبات GPU قابل انجام هستند [Karaboga, D, & .Basturk, B (2007)] از مسائلی که حل آن در حالت ترتیبی از مرتبه اجرای بسیار باالیی برخوردار است و دراین پژوهش برآن هستیم ،که بتوانیم الگوریتم محاسبات روی آرایهها را از روش ترتیبی و موازی پیاده سازی نماییم و با توجه به زمانهای خروجی مقایسه ای بین این دو نوع برنامه انجام دهیم.

یکی از ایرادات الگوریتمهای محاسباتی، رابطه زمان اجرای الگوریتم و تعداد داده ها است که روی آن محاسبات را انجام میدهیم. به عبارتی بهتر اگر داده های اولیه زیاد باشد زمان نشان دادن خروجی محاسبات توسط این الگوریتم های سری افزایش مییابد. یکی از روشهای افزایش شتاب و سرعت این الگوریتم استفاده از تکنیکهای موازی سازی مختلف است. امروزه واحد پردازش کارت گرافیک1 بر خالف پردازنده اصلی2 که تعداد هستههای محاسباتی محدودی دارد، دارای هزاران هسته محاسباتی و یک پردازنده اختصاصی است. معماری پردازندهکارتگرافیک به گونهای است که بسیاری از الگوریتمهای مختلف و موازی را با شتابی3 باالتر از پردازنده اصلی اجراء میکند. یکی از چارچوبهای4 پرقدرت جهت بکار گیری هستههای پردازنده کارت گرافیک، استفاده از معماری کودا5 میباشد. در این مقاله تالش

3

میشود تا الگوریتم جمع آرایه ها به شکل موازی در پردازنده کارت گرافیک به اجراء گذاشته شود و میزان شتاب آن با حالت ترتیبی مقایسه و نتایج بیان شود.

5.1 معماری كودا

پردازندههای گرافیکی که امروزه بر روی کارتهای گرافیکی نصب میشوند دارای توان پردازشی بسیار باالی نسبت به پردازندهی مرکزی است. پردازندههای گرافیکی در ابتدای امر جهت پردازش تصاویر گرافیکی گسترش پیدا کردند ولی توان پردازشی وسوسه بر انگیز این تراشهها باعث استفاده آنها درحوزههایی فراتر از امور گرافیکی گشته است، پردازندههای گرافیکی مدرن دارای معماری موازی و متشکل از صدها و هزاران هسته محاسباتی هستند که این امر باعث شده است تا این پردازندهها دارای سرعت بسیار زیادی در محاسبات گردند. مزیتهای این پردازندهها مانند قیمت مناسب و توان مصرفی کم و در حین حال پردازش سریع ، باعث شده است در جهت پیادهسازی الگوریتمها و برنامههای بینایی ماشین و پردازش تصویر به شکل موازی بکار گرفته شوند. در سالهای اخیر، افزایش روز افزون عملکرد کارت های گرافیکی، محققین را به فکر بهرهگیری از توان پردازشی آنها در کاربردهای غیر گرافیکی انداخته است. از اینرو از صنعت محاسباتی گرفتهتا محاسبات موازی دچار تغییرات گستردهای شده و در سراشیبى تند انقالب محاسباتی موازی قرار گرفته، و درنتیجه NVIDIA CUDA C تا کنون به عنوان یکی از موفقترین زبانهای عمل کرده است که تا به حال برای محاسبات موازی طراحی شده است

.[Navarro, C. A., Hitschfeld-Kahler, N., & Mateu, L. (2014)]

6.1 مقایسه تواناییهای GPU با CPU

پردازندهگرافیکی، نوعی پردازنده موازی است که بر روی کارت گرافیکها قرار دارد. که طی سالهای گذشته آن چنان تحول یافته که امروزه از نظر کارایی با پردازندهمرکزی که یک پردازنده همه منظوره به شمار میرود رقابت میکند. بکار گیری پردازندهگرافیکی در محاسبات عمومی جایگاه جدیدی برای کارت گرافیکهای قدرتمند ایجاد کرده است، جایی که از پردازندهگرافیکی دیگر برای پردازش محاسبات گرافیکی استفاده نمیشود، در عوض در نقش یک پردازنده کمکی، بخشی یا تمامی بار محاسباتی پردازندهمرکزی را تقبل کرده و به عملیات پردازش سرعت میبخشد امروزه، GPUها توان محاسباتی بهتری در مقایسه با پردازندههای مرکزی جدید دارند)همانطور که در شکل 1نشان داده شده است( و در انواع کاربردها از آنها استفاده می شود. [Kirk, D. (2007, October) ]

4

شکل:1 مقایسه توانایی انجام عملیات اعشاری در پردازندههای گرافیکی انویدیا و اینتل .[Karaboga,
D., & Basturk, B. (2007)]

در این شکل توان پردازشی خام با واحدتعداد محاسبات ممیز شناور در ثانیه 6سنجیده شده است. یکی از شاخصهها و معیارهای مقایسه سنجش قدرت کارت گرافیک در پردازش و محاسبات ، میزان توانایی آنها در انجام ممیز شناور در واحد زمان است که هر چقدر این مقدار بیشتر باشد پردازنده گرافیکی توانایی باالی جهت پردازش دارد .خطوط آبی نمایانگرتعداد ممیز شناور در ثانیه توسط CPUو خطوط سبز توسط GPUمیباشد.همانطورکه مشاهده میکنید توان پردازشی خام پردازندههای گرافیکی بسیار سریعترین از پردازندههای مرکزی بوده و رفته رفته فاصله میان این دو بیشتر میشود.[Nvidia, C . U . D. A. (2011)]

مدل برنامهنویسی برای اجراء روی پردازندهی مرکزی به طورکلی به شکل یک روندترتیبی است در واقع کدهای تشکیلدهنده یک برنامه در ابتدا به ترتیب از باال به پایین خوانده شده و پس از ترجمه، اجرا میشود در اجرای این روند موازیسازی به طور معمول در سطح باالیی بکار گرفته نمیشود زیرا تعداد هستههای پردازنده مرکزی اندک هستند و قابلیت موازی سازی باالیی در آن وجود ندارد. هرچند، پردازنده های مرکزی جدید با قابلیتهایی موازی سازی مانند نخ های چند گانه و چند هستهای ارایه شده است، اما نرخ موازی سازی در این پردازندهها بسیار کمتر از یک پردازندهگرافیکی با تعداد هسته های بیشمار است. به خاطر معماری پردازنده اصلی و عدم تطبیق کافی با موازی سازی، دستورات بیشتر کش7 میشوند و در کوانتومهای زمانی به ترتیب اجراء میشوند. در پردازنده کارت گرافیک مدلی تحت عنوان جریان 8 بر خالف پردازنده مرکزی توسعه داده شده است که قابلیت بهرهگیری از تکنیکهای موازیسازی در آن قرار داده شده است. پردازندههای گرافیکی تنها میتوانند بر روی دادهها و آرایههای مستقل از هم پردازش انجام دهند؛ اما این پردازش را در تعداد بسیار باال و به صورت همزمان اعمال میکنند.

5

این ویژگی هنگامی که نیاز به کار یکسان بر روی تعداد زیادی داده داشته باشید، مفید واقع میشود [NVIDIA, C. .(2011)]

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

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

6

مرکزی ناگزیر از داشتن چنین معماری و به تبع آن پردازش کندتری است.پردازندههای گرافیکی امروزی از چندین پردازنده با کارایی باال تشکیل شده اند که قادر به محاسبات بسیار سنگین هستند و قابلیت پشتیبانی از رابطهای برنامه-نویسی و زبانهای استاندارد مانند Cرا دارند . [NVIDIA , C. (2011) ]

7 , 1 مقایسه سخت افزار GPU با CPU

اگر بخواهیم تفاوت های این دو پردازنده را از لحاظ سخت افزاری بیان کنیم می توانیم به موارد زیر اشاره کنیم:

CPU- دارای یک فایل ثبات است در صورتی که GPUشامل مجموعه ای فایل ثبات است.

-پردازنده کارت گرافیک از گروههای نخها برای مشغول نگه داشتن واحدهای اجرا و مخفی کردن تاخیرهای حافظه استفاده می کند.

- واحد کنترل سربار را در سراسر واحدهای چندگانه اجرا پخش می کند.

- هسته CPU از هسته پردازنده کارت گرافیک کوچکتر است و همچنین تعداد هستههای آن کمتر از هستههای پردازنده کارت گرافیک است. با توجه به تعداد هستههای بیشتر در پردازنده کارت گرافیک امکان موازی سازی بیشتری توسط ان وجود دارد. اصلی ترین علت تکامل GPUها انجام محاسبات به صورت موازی است. همانطور که در شکل 3 نشان داده شده است آنها به جای کش کردن دادهها، آنها را پردازش می کنند در واقع آنها طوری طراحی شده اند که بیشتر ترانزیستورها را به پردازش داده اختصاص می دهند تا اینکه ترانزیستورها را برای کش کردن داده و جریان کنترل اختصاص دهند )بر خالف CPUها( و این به این معنا است که کار سریع تر انجام می شود [Nvidia, C. U. D. A.

.(2011)]

شکل :2 مدل تخصیص ترانزیستور برای GPUو [Nvidia, C. U . D . A . (2011)] CPU

7

از جمله تفاوتهای مهم سخت افزاری دیگر بین پردازنده اصلی و پردازنده کارت گرافیک ، تعداد و اندازه هسته آنها میباشد که مطابق شکل 3 تعداد هستهها در پردازنده کارت گرافیک بسیار بیشتر از پردازنده اصلی و اندازه هستههای پردازنده کارت گرافیک از پردازنده اصلی کوچکتر میباشد [Nickolls, J., Buck , I., Garland, M., & . Skadron, K. (2008) ]

شکل:3 تفاوت تعداد و اندازه هسته ها در پردازندههای گرافیکی و پردازنده اصلی [Nvidia, C. U. D. A. (2011)]

8, 1 معماری سخت افزاری كودا

چون اکثر زبانهای برنامه نویسی برای اجراء از یک نخ به شکل ترتیبی استفاده میکنند در معماری کودا این پروسه نیز به نوعی انجام میگیرد در واقع معماری کودا یک حالت انتزاعی از موازی سازی این نخ ترتیبی را به اجراء در میآید.

معماری کودا یک معماری مقیاس پذیر است که در آن برنامههای موازی مقیاس پذیر را میتوان در میان چندین هزار نخ همزمان و هزاران پردازنده اجرا نمود . یک برنامه کودا کامپایل شده روی هر واحد پردازش کارت با هر اندازهای از هستهها می تواند اجرا شود؛ زمانی که واحد پردازش کارت گرافیک از پردازندهها و نخهای بیشتری تشکیل شده باشد می تواند از موازی سازی با نرخ بیشتری استفاده کند.معماری کودا از پردازندههای چند هستهای و چند نخی که پردازندههای جریانی12 نامیده میشوند ساخته شده است در معماری کودا تعداد زیادی پردازندههای جریانی وجود دارد. در واقع این پردازندههای جریانی که یک واحد دستور مشترک را اجراء میکنند ، از تعدادی مشخص هسته ساخته شده اند . در شکل 4 ، قسمتی از معماری واحد پردازش کارت گرافیک در چارچوب کودا نشان داده شده است. در معماری کودا ، هر گرید دارای یک حافظه سراسری13، حافظه ثابتها14 و حافظه بافت15 است . اجزاء هر گرید یعنی بالکها