اکنون
که با مفاهیم مطرح در برنامهسازی موازی و همروند کردن الگوریتمها آشنا
شدهاید، بهتر است با یک زبان و ابزار ساده به تمرین و یادگیری
برنامهنویسی موازی بپردازیم. در این مقاله مفسر مالتیپاسکال را
انتخابکردهایم. همانطور که از نام این ابزار میتوان دریافت، زبان مورد
استفاده این مفسر، همان زبان پاسکال است که به دلیل پشتیبانی از
برنامهنویسی چندپردازندهای (Multi processor) و چندکامپیوتری (Multi
computer)، مالتیپاسکال نام گرفته است. این ابزار توسط بروس لستر به عنوان
پروژه تحقیقی در دپارتمان علوم کامپیوتر دانشگاه ماهاریشی طراحی شده که
نرمافزاری کم حجم و ساده و در عین حال توانمند است که در خط فرمان اجرا
میشود و به نصب نیازی ندارد. شما میتوانید این برنامه را بهطور مستقیم
از اين آدرس
دریافت کنید. با داشتن يك پيش زمينه قبل از شروع کار با این زبان با
آمادگی ذهنی کامل و نگرشی عمیقتر برنامهنویسی موازی را آغاز کنید. در ضمن
به دلیل آنكه در این مقاله مفاهیم عمومی برنامهنویسی موازی مطرح شده
است، حتی اگر در آینده قصد کار با مالتی پاسکال را ندارید، خواندن و درک
کدهای موجود و توضیحات مربوطه میتواند در ايجاد زمينهذهني برای کار با هر
زبان دیگر مفید واقع شود. به بیان دیگر، در اینجا انتخاب مالتیپاسکال به
این دلیل بوده است که به واسطه آن، برخی مفاهیم مهم به صورت عملی بیان شود و
مطرح کردن آن فقط برای برنامهنویسان علاقهمند به این زبان نیست.اين مطلب يكي از مقالات بخش ويژه نشريه ماهنامه شبكه در شماره 115 با عنوان برنامهنویسی موازی ميباشد. جهت دريافت اين بخش ويژه به بخش پروندههاي ويژه سايت مراجعه نمائيد.
هدف از
طراحی مالتیپاسکال، ارائه یک زبان برنامهنویسی همراه با مفاهیم مربوط به
زبانهای موازی است که برای نمایش الگوریتمهای موازی روی معماریهای
چندپردازندهای و شبکههای کامپیوتری استفاده شود. بنابراین، برای
برنامهنویس تجربه مستقیمی از برنامهنویسی موازی واقعی را فراهم میکند.
ویژگیهای موجود در این زبان برای دانشجویانی که برنامهنویسی موازی انجام
میدهند، این امکان را فراهم میآورد که تکنیکهای مهم و اصول طراحی و
پیادهسازی الگوریتمهای موازی مؤثر و کارا را روی دو معماری
چندپردازندهای و چندکامپیوتری فرا گرفته و این اطلاعات را برای
کامپیوترهای موازی خاص که از زبانهای برنامهنویسی دیگری پشتیبانی
میکنند، به کار ببرند. مجموعه دستورات مالتیپاسکال، بسیاری از
تواناییهای برنامهنویسی موازی را داشته و برنامهنویسانی که بتوانند
بهطور حرفهای با آن کار کنند، ميتوانند به سادگی و به سرعت خود را با
دیگر زبانهای برنامهنویسی هماهنگ کنند.
در
برنامهنویسی معمولی، هر برنامه دو مؤلفه اساسی به نام متغیر و رویه دارد.
متغیرها شامل دادههایی هستند که میتوان آن را جزئي نرمافزاری از
سختافزار حافظه برشمرد. رویهها نیز روی مقادیر دادهای کار میکنند که
میتوان آن را جزئي نرمافزاری از سختافزار پردازنده به شمار آورد. یک
تناظر به این شکل بین تواناییهای یک زبان و سختافزار موجود، به
برنامهساز کمک میکند تا برنامه خود را دقیقتر طراحی کند.مالتیپاسکال
مستقل از ماشین طراحی شده است و میتواند روی گستره وسیعی از سیستمهای
موازی شامل سیستمهای چندپردازندهای با حافظه اشتراکی یا شبکههای
کامپیوتری مبتنی بر انتقال پیام بین پردازندههای آنها همراه با حافظه
محلی اجرا شود. یکی از تواناییهای این زبان، ایجاد پردازشهای موازی به
صورت پویا بهمنظور اجرا روی پردازندههای فیزیکی است. مالتیپاسکال
این امکان را فراهم میآورد که دادهها با استفاده از متغیرهای اشتراکی که
یک انتزاع نرمافزاری برای حافظه اشتراکی در سیستمهای چندپردازندهای
هستند، بین پردازندهها به اشتراک گذاشته شوند. این مسئله، انعکاسی از
معماری سختافزاری چندپردازندهای در مالتیپاسکال است که در نمودار 1 این
تناظر را مشاهده میکنید. متغیرهای اشتراکی از جنس متغیرهای معمولی هستند.
با این تفاوت که همه پردازندهها میتوانند به آن دسترسی داشته باشند.
نمودار 1
در
شبکههای کامپیوتری، هر پردازنده یک حافظه محلی دارد و چیزی تحت عنوان
حافظه اشتراکی تعریف نشده است. همانطور که پیش از این بیان شد، در
شبکههای کامپیوتری ارتباط پردازندهها از طریق کانالهای ارتباطی و رد و
بدل کردن پیام صورت میگیرد. مقادیر میانی تولید شده در محاسبات از طریق
این کانالهای ارتباطی، از یک پردازنده به پردازنده دیگر منتقل میشود. این
کانالهای ارتباطی در مالتیپاسکال متغیر کانال نام دارد. متغیرهای کانال
در مالتیپاسکال که در همین مقاله بیشتر به آنها خواهیم پرداخت،
موجودیتهای مفهومی نرمافزاری هستند که پردازشهای موازی مبتنی بر انتقال
پیام از طریق آنها میتوانند با یکدیگر ارتباط برقرار کنند. این شیوه
متفاوت برنامهنویسی به دلیل وجود نداشتن حافظه اشتراکی در شبکههای
کامپیوتری است. نمودار 2 تناظر ميان نگرشهای مهم شبکههای کامپیوتری و
تواناییهای مالتیپاسکال را نشان میدهد.
نمودار2
متغیرهای محلی و اشتراکی در مالتیپاسکال
همانطور
که گفتیم در برنامهنویسی موازی و معماری چندپردازندهای به دلیل وجود
حافظه اشتراکی، متغیرهایی تحت عنوان متغیر اشتراکی وجود دارند که میتوانند
توسط همه پردازندهها مورد دستیابی قرار ف
دیگر، متغیرهایی به نام متغیرهای محلی وجود دارند که تنها برای پردازنده
خاصی در دسترس هستند و با اینکه آنها نیز در داخل حافظه اشتراکی نوشته
میشوند، اما از دید سایر پردازندهها پنهان هستند. در هر برنامه
مالتیپاسکال، همه متغیرهایی که در ابتدای برنامه اصلی اعلان شوند،
متغیرهای اشتراکی هستند و به طور مستقيم توسط همه پردازندهها قابل دسترسی
هستند. اگر همه دستورات ایجاد پردازشها داخل بدنه اصلی برنامه باشند،
آنگاه هیچگونه متغیر اشتراکی دیگری وجود نخواگیرند.
از طرهد داشت. همه متغیرهایی که در داخل رویهها و توابع اعلان میشوند،
متغیرهای محلی هستند و تنها توسط Process يا پردازهاي که رویه را فراخوانی
میکند، قابل دسترسی هستند. اما مالتیپاسکال اجازه میدهد که دستورات
ایجاد پردازه در هر جایی از برنامه از جمله داخل یک رویه به کار روند و در
این حالت این امکان برای متغیرهای محلی یک رویه وجود دارد که بین گروه
کوچکی از پردازههابه اشتراک گذاشته شوند. این یکی از تواناییهای پیشرفته
مالتیپاسکال به شمار میرود که با استفاده از آن میتوان در بسیاری از
الگوریتمها، انعطاف بیشتری به برنامه داده و کارکرد آن را بهبود بخشید.
متغیرهای کانال
نوع
دیگری از متغیرها در مالتیپاسکال متغیرهای کانال هستند که جنس آنها
درواقع صفی از متغیرها است. یک پردازه میتواند مقدارهای مختلف از یک نوع
را داخل یک متغیر کانال بنویسد. با این کار، مقادیر مورد نظر به ترتیب
داخل آن صف قرار میگیرند. محتوای این متغیر کانال میتواند به صورت موازی
توسط کامپیوترهای دیگر خوانده شود. با هر بار خواندهشدن از متغیر کانال،
یک مقدار از ابتدای صف حذف میشود. در واقع میتوان متغیر کانال را متغیری
فرض کرد که وقتی به آن مقداری نسبت میدهیم، اگر مقدار قبلی هنوز استفاده
نشده باشد پاک نمیشود و مقدار جدید نیز در کنار سایر مقادیر آن حفظ
میشود. تنها وقتی یک مقدار از متغیر کانال حذف میشود كه توسط کامپیوتری
خوانده شده و مقدار آن استفاده شده باشد.البته، متغیرهای کانال میتوانند
برای سیستمهای چندپردازندهای با استفاده از حافظه مشترک پیادهسازی شوند.
در این سیستمها متغیرهای کانال میتوانند برای همگامسازی پردازه با
یکدیگر و تبادل داده بین آنها استفاده شود. متغیرهای اشتراکی ساده که
میتوانند آزادانه توسط پردازههای موازی خوانده یا نوشته شوند، برای ایجاد
انواع پردازههای تعاملی که برای برنامههای موازی روی سیستمهای
چندپردازندهای مورد نیازاست، کافی نیستند. مالتیپاسکال برای کمک به
همگامسازی پردازهها، یک توانایی استاندارد به نام قفلهای چرخشی
(Spinlock) دارد که بهطور مؤثری در ایجاد کارهای اتمیک مفید هستند. کارهای
اتمیک به اموری گفته میشود که در صورت انجام باید کامل و بدون وقفه انجام
شوند.
دستور forall
در
مالتیپاسکال دستوری به نام forall وجود دارد که معادل موازی دستور for
است. این دستور که توانمندترین روش برای ایجاد پردازشهای موازی است به
تعداد شمارنده حلقه، پردازش ایجاد کرده و با اجرای همروند آنها سرعت
اجرای برنامه را افزایش میدهد. دستور forall بهویژه زمانی که با
آرایههای بزرگ در روشهای محاسبات عددی کار میکنیم، بسیار مفید خواهد
بود. برنامهای که در ادامه مشاهده میکنید، با استفاده از دستور forall و
200 پردازه که بهطور موازی روی 200 عنصر آرایه اجرا میشوند، ریشه دوم یا
جذر هر عنصر را محاسبه کرده و در همان سلول حافظه ذخیره میکند.
Program Squareroot;
var
A: array [1..200] of Real;
i: Integer;
begin
{...}
forall i:=1 to 200 do
A[i]:=sqrt(A[i]);
{...}
end.
در
این برنامه پردازنده شماره صفر، پردازه اصلی یا پردازه پدر را اجرا میکند و
پس از ایجاد دويست پردازه فرزند برای بيست پردازنده فیزیکی در معماری
چندپردازندهای، محاسبات روی خانه شمارهi آرایه A واقع در حافظه اشتراکی
توسط پردازنده شماره i صورت میگیرد. در ضمن در این برنامه بهطور خودکار
یک کپی از i با مقدار متناظر با شماره پردازه برای هر پردازنده به صورت
محلی در حافظه اشتراکی ایجاد میشود که هر پردازه به i محلی خود دسترسی خواهد داشت. به
این ترتیب که متغیر محلی i برای پردازه اول مقدار 1، برای پردازه دوم
مقدار 2 و... را خواهد داشت. بنابراین، با وجود اینکه پردازندهها، قطعه
کد یکسانی را اجرا میکنند، اما تفاوت در نتایج ناشی از تفاوت مقدار در
متغیر محلی i خواهد بود. یک بار که پردازه
ایجاد میشود و مقدار منحصربهفرد اندیس forall به آن اختصاص مییابد، این
مقدار در داخل پردازه تبدیل میشود و هرگونه تلاش برای تغییر مقدار این
اندیس در یک دستورالعمل انتساب، به وقوع یک خطا از سوی مفسر منجر خواهد شد.
لازم است به این نکته نیز اشاره شودکه یک اندیس forall نمیتواند در یک دستور خواندن (read) قرار گیرد یا اینکه بهصورت یک پارامتر متغیر، بین رویهها یا توابع
منتقل شود. اما مقدار آن میتواند به تابع یا رویهای ارسال شود یا بهطور
کلی در هر مجموعه دستوراتی که مقدار آن را تغییر ندهد، استفاده شود.
گرانولیته پردازهها و عملگر grouping
یکی از مفاهیم مهم در برنامهنویسی موازی، زمان اجرای هر پردازه است که به گرانولیته پردازش (Process Granularity) معروف است. همانطور
که میدانید در هر سیستم کامپیوتری همواره یک سربار زمانی مربوط به ایجاد
یک پردازه و ارسال آن به پردازندههای مختلف وجود دارد. اگر زمان اجرای
بدنه هر پردازه از یک میزان خاصی کمتر باشد، موازیسازی عملاً بیاثر و
گاهی کندتر از اجرای ترتیبی آن خواهد شد. بنابراین، برای بالا رفتن کارایی
حاصل از موازیسازی باید نسبت زمان اجرای بدنه پردازه به زمان ایجاد آن به
قدر کافی بزرگ باشد. به
عنوان مثال، در قطعه کد قبل اگر نسبت زمان محاسبه جذر عدد به زمان ایجاد
پردازه به قدر کافی بزرگ نباشد، شاید کارایی برنامه بالا نرود. اما
مالتیپاسکال امکانی را فراهم میآورد که با دستهبندی اندیسهای حلقه از
تعداد پردازهها کاسته و به مقدار بدنه هر پردازه بیافزاید. این امکان با اضافهکردن کلمه کلیدی grouping به دستور forall فراهم میشود. یک نمونه گروهبندیشده برنامه قبل به این صورت خواهد بود:
Program Squareroot;
var
A: array [1..200] of Real;
i: Integer;
begin
{...}
forall i:=1 to 200 grouping 20 do
A[i]:=sqrt(A[i]);
{...}
end.
به این
ترتیب، به جای ایجاد دويست پردازه کوچک، ده پردازه بزرگتر خواهیم داشت که
هر پردازه وظیفه محاسبه جذر بيست عدد را به عهده خواهد داشت. با این
افزایش زمانی اجرای هر پردازه انتظار میرود که کارایی برنامه نسبت به
حالت اول بهتر شود. از طرف دیگر، اگر میزان گروهبندی خیلی بزرگ شده و به
اندیس پایانی نزدیکتر شود، باز هم از کارایی برنامه کاسته شده و برنامه به
سمت اجرای ترتیبی پیش خواهد رفت. در مثالی که مشاهده کردید، اگر عدد
گروهبندی دويست و یا بیشتر از آن شود، تنها یک پردازه فرزند ایجاد شده و
کل محاسبات توسط آن انجام میشود و در واقع برنامه به
شکل ترتیبی در میآید. در حالتی هم که کلمه کلیدی grouping ذکر نشود،
مقدار پیشفرض 1 برای آن درنظرگرفته میشود که همانطور كه گفته شد ممکن
است به علت کوچک بودن بدنه پردازه موجب افت کارایی شود. اما عددی بین يك
تا دويست وجود خواهد داشت که انتخاب آن برای گروهبندی بیشترین کارایی را
درپی خواهد داشت که آن عدد، مقدار بهینه گروهبندی است.
بهطور
کلی با انجام محاسبات میتوان مقدار بهینه گروهبندی در یک برنامه را در
هر حلقه، نسبت به تعداد کل تکرار حلقه forall و عملی که انجام میشود
محاسبه کرد و به این ترتیب، به حداکثر میزان کارایی و تسریع الگوریتم دست
یافت. برای این کار کافی است زمان کل اجرای حلقه forall را بر حسب متغیر G
(مقدار گروهبندی) محاسبه کنیم. با
مشتق گرفتن از رابطه بهدست آمده و برابر صفر قرار دادن آن، معادلهای
بهدست خواهد آمد که با حل آن و بهدست آوردن مقدار G (که همان مینیمم
نمودار زمانی متناظر با رابطه اولیه است) بهترین مقدار برای گروهبندی
بهینه بهدست میآید.
البته،
همیشه نیاز به محاسبه دقیق G از طریق محاسبات گفته شده نیست، بلکه یک حدس
تقریبی نیز برای بیشتر برنامهها مؤثر خواهد بود. به طور معمول بهتر است
اندازه گروه بهینه برای یک دستور forall که بدنه آن بسیار کوچک است، جذر
تعداد اندیسهای حلقه انتخاب شود. در حالتهایی که بدنه حلقه forall به قدر
کافی بزرگ به نظر میرسد نيز اصلاً به گروهبندی نیازی نیست. در ادامه
ذکر یک نکته نیز لازم به نظر میرسد كه مستقل از اندازه بدنه دستور forall
گاهی با محدودیت تعداد پردازندهها مواجه هستیم. در آن زمان نیز بهتر است
از گروهبندی استفاده شود. به عنوان مثال، اگر بدانیم تنها بيست پردازنده
در اختیار داریم و اندیس حلقه برابر صد باشد بهتر است از گروهبندی با
مقدار پنج استفاده کنیم. درغیراینصورت، مقداری از زمان به دلیل ایجاد
تعدادی پردازه و همچنین سويیچ کردن هر پردازنده بین پردازههای محوله به
هدر خواهد رفت. اگرچه با بزرگ
بودن بدنه حلقه، زمان ایجاد پردازشها زیاد نخواهد بود، اما در هر صورت
زمان اجرای کل از حالتی که در آن از گروهبندی استفاده شده است بیشتر
خواهد شد و کارایی به همان نسبت افت پیدا خواهد کرد.