پیاده سازی محیط Grid و برنامه نویسی موازی

[آبجی]

سیستم های Grid نوعی از سیستم های توزیع شده یا موازی هستند که اشتراک ، انتخاب و جمع آوری منابع را در فواصل جغرافیایی فراهم می اورد. بر اساس این تعریف ملاحظه میشود که امکان اجام کارها بصورت موازی وجود دارد.شاید مهمترین دلایل استفاده از سیستم های موازی را بتوان در 4 مورد زیر خلاصه نمود:
1- Application ها بطور حریضانه به دنبال منابع هستند .
2- کامپیوترهای موجود معماری تک پردازنده و ترتیبی دارند .
3- پیشرفت تکنولوژی شبکه های کامپیوتری .
4- محدودیت فیزیکی سخت افزارها در افزایش سرعت .
با توجه به موارد فوق درمی یابیم موازی سازی یک امر ضروری برای انجام کارهای بزرگ و سنگین می باشد.با انجام موازی سازی قابلیتهایی نظیر ،توازن سازی ،همپام سازی ، در دسترس بودن ، انعطاف پذیری و کاهش هزینه امکان پذیر میشود.اما برای نوشتن برنامه های موازی به محیطی نیاز است که این کار انجام گیرد .در این مورد کلا" دو دیدگاه وجود دارد .
الف – Implicit parallelism
در این دیدگاه موازی سازی توسط زبانها و کمپایلرهای موازی پشتیبانی میشوندو تمامی عملیات مربوط به موازی سازی در آن زبانها یا کمپایلرها حمایت می شوند.این زبانها و کمپایلرها خاص ابر رایانه ها طراحی میشوند.
ب – Explicit parallelism
در این دیدگاه زبان موازی نداریم ، در واقع از همان زبانهای سریال استفاده میشود و این برنامه نویس است که موازی سازی را انجام می دهد.برای این منظور برنامه نویس می بایست قسمتهای موازی را تشخیص داده و بکمک ابزار برنامه نویسی آنها را از هم جدا کند. این روش که در سیستم های Grid و Cluster کاربرد دارد برنامه به بخشهای زیر تقسیم می شود :
1- تقسیم بندی فرایندها
2- نگاشت روی پردازنده ها
3- ساختارهای ارتباطی
سپس می بایست مدل برنامه نویسی موازی تعیین گردد .بطور کلی مدلهای برنامه نویسی موازی بصورتهای زیر وجود دارد :
1- Share memory
در این حالت معماری مابصورت حافظه مشترک بوده و دستورات بصورت Read و Write می باشند.برخی از این ابزار عبارتند از : DSM ، Java ، Openmp.
2- Message passing
در این حالت در محیط شبکه هر سیستم حافطه و پردازنده خودش را دارد و از دستورات Send و Receive استفاده میشود. برخی از این ابزار عبارتند از : MPI و PVM
تذکر: نسخه تحت ویندوز MPICH می باشد که شامل توابع کتابخانه ای برای نوشتن برنامه های موازی است .در پروژه نیز ما از این ابزار استفاده کرده ایم .
3- Hybrid
به ترکیبی از دو مدل فوق اشاره دارد .برخی از این ابزار عبارتند از MPI,Openmp.
4- Object & Service Oriented
این ابزار در سطح کاربر بوده و بالاتر از Middleware قرار می گیردولی کارایی کم میشود.برخی از این ابزار عبارتند از Dcom و Corba .
برای انجام برنامه نویسی موازی می بایست بخشاهای زیر را در کد ایجاد کرد و رعایت نمود:
1- Partitiong که برای بخش بخش کردن Task بکار می رود.
2- Communication برای برقرای ارتباط بین بخشهای جدا شده در فاز اول می بایست رعایت شود.
3- Agglomeration که نحوه اتصال دو بخش فوق را بعد از برقرای ارتباط و بخش بندی را مشخص می کند.
4- Mapping/Scheduling که نسبت دادن کارها به پردازندها را انجام میهد بطوریکه زمان انجام کار حداقل شده و راندامان بالایی داشته باشیم .
برنامه نویسی موازی یک Task پیچیده است زیرا برنامه هایی را که مینویسیم شامل بخشهای موازی است .ابزارهای برنامه نویسی کمک می کنند تا حدی این پیچیده گی کاهش یابد.برای نوشتن برنامه ای موازی به چنین محیطهایی نیاز داریم .مهمترین نکته ای که از دیدگاه کاربر مهم است آنستکه برخی از چیزها را Transparence کنیم و همچنین بتوانداز مفاهیم قبلی برنامه نویسی استفاده نماید.
در این روش برنامه به یکسری زیر برنامه تقسیم می شود و هر بخش از آن بین گره های شبکه اجرای می گردد.هر زیر برنامه بصورت ترتیبی نوشته شده است ولی چون همه پردازنده ها موازی برنامه را اجرا می کنند در نتیجه برنامه موازی اجرای میشود.متغیرهایی که روی هر پردازنده اجرا میشوند کاملا"Private هستند و برای ارتباط فقط از مبداء به مقصد پیام ارسال میشود.
همانطور که اشاره شد برای انجام برنامه نویسی موازی از ابزار MPICH که کتابخانه ای از توابع موازی را فراهم می آورد استفاده شده است .هدف از این پروژه انجام عملیات ضرب ماتریس بصورت موازی است .همانطور که در نمودارملاحظه میشود این پروسه روی چندین ماشین اجرا شده است .با افزایش تعداد ماشینها سرعت انجام عملیات نیز افزایش می یابد.
MPICH ابزاری است که توابع استاندارد کتابخانه ای MPI را برای اجرا در انواع سیستم ها فراهم می آورد. این ابزار در سیستم های عامل NT4,window 2000,windows xp و Windows server قابل استفاده است و هر جا که ارتباطات بصورت TCP/IP وجود دارد قابل بکارگیری است.همچنین برای کمپایل برنامه های نوشته شده از محیط 6.x++ VC بهره می بریم .
در این برنامه عمدتا از دستورات انتقال پیام استفاده شده است و باتوجه به کاربرد این دستورات در برنامه این دستورات را بصورت زیر شرح می دهیم .
همانطور که ذکر شده این برنامه براساس Message passing کار می کند .بطور کلی به دو صورت گروهی (Collective) و نقطه به نقطه (Point to point) انتقال پیام انجام میشود.در حالت اول یک فرستنده به چندین گیرنده پیام را ارسال می کند.و در حالت نقطه به نقطه یک فرستنده و یک گیرنده داریم که پیام را بیکدیگر ارسال می نمایند.این روش خود بصورتهای زیر انجام میشود:
1- سنکرون : در این حالت دقیقا وقتی که گیرنده می خواهد داده را بردارد، فرستنده متوجه میشود.به عبارتی وقتی کار ارسال پیام تمام شد فرستنده متوجه میشود و ادامه کار منوط به این است گیرنده داده را بردارد. برای مثال ماشین فاکس چنین خصوصیتی دارد.
2- آسنکرون :در این حالت فرستنده از برداشتن داده توسط گیرنده آگاه نیست .به عبارتی وقتی پیام سیستم را ترک می کند متوجه نمی شویم که رسیده است یا نه . برای مثال سیستم پست نامه را میتوان نام برد.
3- عملیات بلوک کردن :وقتی انجام میشود و نتیجه را باز می گرداند که عملیات تکمیل شده باشد.
4- عملیات بدون بلوک کردن : در این حالت عملیات شروع شده و معلوم نیست چه زمانی خاتمه می یابد.به عبارتی برای اطمینان از انجام عملیات باید تست انجام شود.برای مثال سمافور در سیستم عامل اینچنین است .
با توجه به مطالب فوق می توان دریافت که ارسال سنکرون Blocking و ارسال آسنکرون Non blocking است .
در مقابل ارتباطات گروهی قادر هستند که عملیات زیر را انجام دهند :
1- میتوان از آنها بعنوان ارتباطات نقطه به نقطه استفاده نمود.
2- امکان انجام پردازشهای سنکرون ( Barrier) را دارد .
3- قابلیت انجام ارتباطات یک به چند ( Broadcast ) را دارد.
4- قابلیت انجام عملیات Reduction بدین معنی که ترکیب داده از پردازنده های متعدد برای تولید نتیجه نهایی و بر آیند.

همانطور که اشاره شده MPI یک زبان نیست بلکه یک کتابخانه از توابع به منظور نوشتن برنامه های موازی است و می بایست هدر فایلهای آن را در سورس برنامه معرفی نمود.فرمت توابع MPI که بهنگام برنامه نویسی بکار گرفته میشود بصورت زیر است :

MPI_Xxxxx(parameter,…);

عمده توابعی که در برنامه استفاده شده است تقریبا" مشابه برنامه محاسبه عدد P می باشد.با این تفاوت که در این جا عملیات ضرب ماتریس انجام میشود. به منظور تمایز پروسس های مختلف اولین روتین که بکار می رود MPI_Initاست .این روتین یک گروه یا Communicator ایجاد می کند و به تمام پردازنده هایی که در یک گروه هستند شماره ای اختصاص می دهد.به این شماره اصطلاحا" Rankگفته میشود.بصورت پیش فرض Masterشماره Rank صفر را می گیرد و بقیه پردازندهها به ترتیب شماره گذاری میشوند.در واقع Rank به پروسه IDاست .
الگوریتم کار بدین صورت است که بعد از تعریف متعیرها ی مورد نیاز ،زمان شروع برنامه را ثبت می کنیم سپس برای نمایش شماره و نام ماشین پردازش گر از فرمان Fprintf استفاده کرده ایم که در واقع MyID و processor name را بر می گرداند.سپس تعداد سطر و ستون ماتریس مورد نظر را تعریف می کنیم .این مقادیر ثابت می باشند و انجام تغییرات آن منوط به دستکاری در سورس برنامه است.در واقع دو ماتریس 1000 در 1000 در این برنامه در هم ضرب شده اند .که بصورت ریاضی بصورت 1000*1000*1000 تعریف میشود. در ادامه بعد از تخصیص حافظه مورد نیاز ماتریسها را بصورت تصادفی مقدار دهی می کنیم و در بخش آخر عملیات ضرب ماتریسها انجام میشود.برای این منظور ابتدا توسط تابع MPI_Bcast اندازه هر یک از ماتریسها برای بقیه گره ها معرفی می کنیم . در واقع در شرط اول فقط اطلاعات ماتریس ها برای ID صفر و رد شرط دوم اطلاعات مورد نیاز سایر گره ها مشخص میشود.در بخش عمل ضرب ماتریسها بدین صورت انجام میشود هر پروسس یک سطر از ماتریس را در کل ماتریس بعدضرب می کند .در این جا نتایج خروجی توسط تابع Printf چاپ نشده است و تنها زمان محاسبه وپردازش چاپ گردیده است .
سورس برنامه به پیوست تقدیم شده است ( برنامه و توضیحات روی CD نیز وجود دارد). برای درک بیشتر برنامه توابعی که در بکار رفته است را در ادامه به تفکیک شرح می دهیم :
1- MPI_Comm_Rank : این تابع شماره Rank را بر می گرداند .برای مثال روی Master شماره صفر را میدهد .
2- MPI_Comm_size : این تابع سایز گروه در Communicator را بر می گرداند به عبارتی تعداد پروسه هایی که در گروه وجود دارند را می دهد.
3- MPI_Send : این تابع که به ارسال استاندارد مشهور است و مهم آنستکه که عملیات ارسال تکمیل شده باشد.به عبارتی زمانی کامل میشود که پیام ارسال شده باشد و از نوع Blocking است .
4- MPI_Recv : در تابع دریافت استاندارد بااجرای Send ،طرف گیرنده ،بهنگام اجرای Receive یک پیام به فرستنده ارسال می کند .
5- MPI_Wtime : این تابع Wall clock رابر می گرداند .هر وقت بخواهیم زمان را اندازه گیری کنیم این تابع را بعد از Send و بعد از Receive صدا می زنیم .
6- MPI_Bcast :از این تابع برای ارسال یک به چند استفاده می کنیم .به عبارتی از گره ریشه پیام را به یک سری از زیر گره های ارسال می کنیم .
7- MPI_Reduce : این تابع وظیفه ارسال نتایج حاصل از پردازش زیرگره ها را به گره ریشه را دارد.
8- MPI_Barrier :از این تابع برای سنکرون کردن گره ها استفاده میشود. به عبارتی منتظر می ماند تا الباقی گره ها نتایج را ارسال نمایند .
این برنامه در یک محیط شبکه Workgroup با 5 سیستم اجرا شده است . مشخصات این سیستم ها طبق جدول زیر است .

نام ماشین

نوع پردازنده

میزان حافظه اصلی

Laptop

1.6 centrino

512MB DDR

Hossini

1.83 dual core napa

512 MB DDR2/533

Hasani

3000 full cache LGA

512 MB DDR2/677

Ruhi

3000 full cache LGA

512 MB DDR2/677

Sabser(Server HP ML370)

Dual Xeon 3.6 2MB L2

2GB DDR2/677 ECC

همانطور که از جدول فوق پیداست این 5 سیستم برای اجرای ماتریس 1000*1000 در نظر گرفته شده اند.همانطور که از نتایج خروجی و نمودار پیداست .با اجرای مرحله به مرحله برنامه زمان اجرای پردازش ثبت شده است .برای اینکه بتوانیم برنامه ها را بصورت موازی اجرا نمامیم می بایست در ابتدا MPICHرا در تمامی ماشینها نصب کنیم .بعد از نصب برای اینکه تمامی سیستم ها با هم کار کنند اولا یک کاربر مشترک با رمز عبور یکسان باید تعریف گردد و ثانیا در صورتیکه Firewall روی کارت شبکه سیستم فعال است باید غیر فعال گردد.در مرحله بعد با کاربر و رمزی که برای آن تعریف کرده ایم MPI registerرا اجرا می کنیم تا رجیستر گردد.سپس فایل کمپایل شده (فایل اجرایی برنامه ) در تمامی کامپیوترهای شبکه در یک پوشه که نام آن در تمامی سیستم ها یکسان است و به اشتراک گذاشته شده کپی می کنیم سپس از طریق MPIch Configure tool. لیست ماشینهای شبکه را اضافه می کنیم و برنامه را در ماشین Master اجرا می کینم در اولین مرحله با 1 ماشین بیشترین زمان انجام محاسبه ثبت شده است .با افزایش تعداد پردازنده ها تا 5 عدد کاملا" زمان پردازش بهینه شده و در کمترین مقدار خود قرار گرفته است .اما با زیاد کردن تعداد ماشین ها چون هر ماشین ممکن بوده است بیشتر از یک عمل را انجام دهد به علت وجود پروسه های مختلف برای تقسیم کار و همچنین به علت وجود سربار در ارتباطات زمان انجام پردازش سیر صعودی به خود میگیرد.همچنین نمودار نشان می دهد که همیشه با افزایش تعداد پردازنده ها زمان پردازش افزایش نمی یابد و به علت وجود سربار سیستم بصورت None dedicate عمل خواهد کرد.

[hirmand]

سلام
خیلی خوب بود
خیلی کمکم کرد
ای کاش کدش رو هم می دادین

[آبجی]

سلام
خیلی خوب بود
خیلی کمکم کرد
ای کاش کدش رو هم می دادین

منظورتون از کد چی هست ؟؟؟

این هم یک پی دی اف در این مورد :

ﻳﻚ ﻣﺤﻴﻂ ﺑﺮﻧﺎﻣﻪ ﻧﻮﻳﺴﻲ ﺳﻄﺢ ﺑﺎﻻ در ﻣﺤﻴﻂ ﮔﺮﻳﺪ