یک برنامه، یک هدف، چند پردازنده



پارسا ستوده*نيا

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

تفاوت دو دیدگاه برنامه*سازی ترتیبی و موازی تنها از تقسیم یک مسئله به مسائل مستقل کوچک*تر و سپردن آن*ها به واحدهای پردازشی جداگانه آغاز می*شود، اما در پی آن مفاهیم متعددی مطرح می*شود که اغلب در برنامه*نویسی معمولی مطرح نبوده یا ماهیت آن*ها با مفهوم متناظر آن در برنامه*نویسی معمولی كاملاً متفاوت است. حتی برخی مفاهیم در یک معماری خاص مطرح می*شود و در معماری دیگر كاملاً بی*معنی است و برای آن معادلی وجود ندارد. چیزی که در اینجا اهمیت دارد آن است که فردی که می*خواهد وارد دنیای برنامه*نویسی موازی شود باید سعی كند وارد نگرش*ها و دیدگاه*های موازی شود و ویژگی*های برنامه*های موازی، مفاهیم، مسائل و مشکلاتی را که در این شاخه از علم کامپیوتر مطرح است، بشناسد. زمانی که این کار به درستی انجام شد، فرد با انتخاب و استفاده از ابزار و زبان مورد نظر خیلی زود معادل هر مفهوم را در آن ابزار پیدا کرده و راه خود را به سرعت در آن خواهد*یافت. شاید اصطلاحات از ابزاری به ابزار دیگر متفاوت باشد یا شاید يك زبان امکان خاصی برای کاربران خود در نظر*گرفته که در زبان دیگر وجود ندارد که البته این خصوصیت طبیعی*زبان*ها است، اما مفاهیم مشترک است. اگر در گام نخست هدف را به درک این مفاهیم و کسب نوع نگرش به مسائل معطوف*کنیم، بدون شک از پیچیدگی و بزرگی هیچ زبان و ابزاری هراس نخواهیم داشت و تمام آن*ها را امکاناتی برای عملی کردن دانسته*های خود خواهیم دانست. روزگاری انجام محاسبات ریاضی با سرعتی فراتر از سرعت محاسبات انسانی یک رؤیا بود. اما امروز شاهد نگرشی كاملاً متفاوت با نگرش پیشین هستیم. حل بسياري از مسائل به طور ذاتي زمان بسیار زیادی می*طلبد و گاهی این زمان بسیار فراتر از حد انتظار است. ممکن است ماهیت مسئله طوری باشد که به حل آن در مدت زمان خاصی نیاز داشته باشیم که در این صورت، صرف زمانی بیش از آن، در عمل حل مسئله را بی*ارزش می*کند. به عنوان مثال، پردازش*های مربوط به پیش*بینی وضع هوای فردا باید در کمتر از یک روز به پاسخ برسد یا زمان*بندی درس*هاي دانشگاه که از جمله مسائل پیچیده و بغرنج به شمار می*رود و گاهی یافتن راه*حل بهینه به سال*ها زمان نیاز دارد، باید در مدت زمان معقولی (از زمان اعلام برنامه استادان تا چند روز قبل از شروع ترم جدید) به جواب برسد تا پاسخ مسئله، ارزش عملی داشته باشد. برخی مسائل نیز هستند که حل آن*ها با سریع*ترین کامپیوترهای امروزی به زمانی بیش از طول عمر انسان نیاز دارد! در چنین حالتی است که ایده استفاده از n پردازنده معمولی به جای n برابر*کردن سرعت پردازشی یک پردازنده به ذهن می*رسد و در صورتی که بتوان مسئله را نیز به n قسمت مجزا و تقریباً مستقل از هم تقسیم*کرد، در حقیقت به هدف نهایی خود بسیار نزدیک خواهیم شد. اینجا است که برنامه*نویسی موازی به عنوان یک راهکار مطرح می*شود.

پردازش
برای ایجاد برنامه برای کامپیوترهای موازی، به یک ابزار مفهومی مفید به نام «پردازش» نیاز داریم که به طور اساسي دنباله*ای از اعمال است که می*تواند توسط یک پردازنده منفرد اجرا شود. پردازش، مهم*ترین قالب ساختمانی یک برنامه موازی است و تا پردازش ایجاد نشود، امکان فعالیت*های محاسباتی در برنامه*ها وجود نخواهد داشت. یک پردازش می*تواند به عنوان یک قطعه کد از برنامه تصور شود که برای اجرا به یک پردازنده واگذار شده است. با این تعریف، برنامه*های ترتیبی معمولی را می*توان حالت خاصی از برنامه*های موازی در نظر گرفت که در آن*ها تنها یک پردازش و یک پردازنده وجود دارد.در مبحث موازی معمولاً اجرای برنامه*ها به این صورت است که برنامه اصلی، نخستين پردازش را آغاز کرده و آن را برای اجرا به نخستين پردازنده واگذار می*کند. برنامه اصلی ممکن است شامل دستوراتی مانند انتساب، شرط*ها، حلقه*ها و... باشد که در برنامه*های عادی نیز وجود دارند. اما یک سری دستورات دیگر نیز در آن*ها وجود خواهد داشت که در برنامه*های ترتیبی یافت نمی*شوند و آن دستورات موجب می*شوند پردازش*های جدیدی ایجاد شده و برای اجرا به پردازنده*های مختلف واگذار شود. پردازش اصلی را در اصطلاح پردازش پدر یا مولد و پردازش*های ایجاد شده توسط پردازش اصلی را پردازش*های فرزند می*گویند. هریک از پردازش*ها خود این پتانسیل را دارند که در صورت نیاز پردازش*های دیگری ایجاد*کرده و خود پدر آن پردازش*ها شده و سرپرستی آن*ها را به*عهده بگیرند.

کانال*های ارتباطی پردازش*ها
همان*طور که می*دانید در برنامه*های ترتیبی معمولی، یک بار که داده*های ورودی مشخص می*شوند*، دستورالعمل*های برنامه درترتیب خاصی اجرا می*شوند و برای داده*های ورودی یکسان، ترتیب اجرای دستورات همواره یکسان است. در برنامه*های موازی با اين*كه ترتیب اجرای دستورالعمل*ها در هر پردازش به طور كامل معین است، اما رابطه بین اجرای دستورالعمل*ها در پردازش*های متفاوت مشخص نیست. به علت تأخير*های غیرقابل پیش*بینی و تأثیرات محیطی روی پردازنده*ها، نمی*توان به طور كامل مطمئن بود که پردازش*های موازی در مقایسه با یکدیگر تا چه*حد سریع هستند. فرض کنید یک پردازش پدر در بدنه خود دو پردازش P1 و P2 را ایجاد می*کند. اگر این دو پردازش مستقل از هم باشند، زمان نسبی اجرای آن*ها مهم نیست. پردازش پدر منتظر می*شود تا هر دو پردازش فرزند خاتمه یابند و اگر یکی از پردازش*ها از دیگری سریع*تر باشد بر درستی اجرای برنامه اثر نخواهد گذاشت. اما اگر پردازش*های موازی از متغیرهای اشتراکی استفاده کنند ممکن است این وضعیت پیچیده*تر شود. به عنوان مثال به شکل 1 توجه کنید. فرض کنید پردازش P1 یک مقدار را محاسبه کرده و آن را داخل متغیر C می*نویسد و پردازش P2 آن را خوانده و برای محاسبات خود استفاده می*کند. با توجه به اين*كه P1 و P2 پردازش*های موازی هستند، سرعت اجرای آن*ها مشخص نیست. بنابراین، هيچ راهی وجود ندارد كه بتوان ترتیب انجام عمل خواندن و نوشتن پردازش*ها را روی متغیر اشتراکی C نسبت به یکدیگر تعیین كرد.
شکل 1
برای مدیریت این حالت که از قضا در بسیاری از برنامه*های موازی رخ می*دهد می*توان از متغیر کانال استفاده کرد. یک متغیر کانال خاصیتی دارد که می*تواند وضعیت تهی بودن را نشان دهد. زمانی که یک پردازش سعی می*کند یک کانال تهی را بخواند، اجرای پردازش به طور خودکار تا وقتی که پردازش*های دیگر مقداری را داخل کانال بنویسند به تعویق می*افتد. بنابراین، اگر متغیر اشتراکی C را از نوع کانال تعریف کنیم، اگر تا زمانی که مقداری درون آن نوشته نشده است P2 سعی کند آن را بخواند، به حالت تعلیق در می*آید. اما اگر پیش از آن P1 مقداری را درون آن نوشته باشد خواندن متغير بدون وقفه انجام می*شود. در برخی از حالت*ها تعامل پردازش*ها به صورت «تولیدکننده-*مصرف*کننده» است. در این حالت پردازش P1 به طور مستمر مقادیری برای مصرف P2 تولید می*کند و با توجه به اختلاف سرعت پردازنده*ها ممکن است پیش از مصرف مقدار تولید*شده قبلی، مقدار بعدی نیز تولید شود. اگر متغیر C یک متغیر اشتراکی معمولی باشد، بدون اين*كه مقدار قبلی مصرف شده باشد مقدار بعدی جایگزین آن می*شود که در بسیاری از موارد، این حالت مطلوب نیست. اما اگر C از نوع متغیر کانال باشد، پردازش P1 می*تواند با هر سرعتی مقادیر مورد نظر را تولید کند و این مقادیر را درون C قرار دهد. C نیز این خاصیت را دارد که می*تواند همه مقادیر تولید شده را نگه داشته و به نوبت در اختیار P2 قرار دهد. بنابراین P1 می*تواند با هر سرعتی اجرا شده و حتی پیش از آن*که P2 نخستين مقدار تولید شده را بخواند، به پایان برسد. در صورتی که زبانی از متغیرهای کانال پشتیبانی نکند و ساختار داده*ای مشابهی نیز در آن وجود نداشته باشد، شاید تنها راه*حل موجود برای پیش*گیری از بروز خطای منطقی در برنامه، همگام*کردن پردازش P1 و P2 در هر مرحله از تولید و مصرف باشد. به این معنی که P2 منتظر P1 بماند تا مقداری تولید کند و از طرفی تا یک مقدار مصرف نشده است، مقداری تولید نشود و P1 منتظر بماند تا P2 مقدار تولیدی را مصرف کند.

حلقه*های تکرار موازی
در برنامه*نویسی موازی همانند برنامه*نویسی معمولی، حلقه*ها برای انجام امور*تکراری استفاده می*شوند. با این تفاوت که می*توان در کنار آن*ها حلقه*هایی داشت که در آن همه تکرارها به*صورت موازی انجام شود. در آن صورت باید آن حلقه را به شکلی از حلقه*های معمولی متمایز ساخت. به*عنوان مثال ممکن است در یک زبان به جای کلمه کلیدی for از forall استفاده کرد یا در زبان دیگر بعد از ساختار معمولی for از عبارت کلیدی do in parallel استفاده کرد. در حالت معمول به عنوان مثال وقتی در شبه*کدی می*گوییم:

for i=1 to 100 do something(); به این معنی است که کاری به ترتیب 100 انجام شود و در آن هر تکرار بلافاصله بعد از اتمام تکرار قبل آغاز می*شود. اما زمانی که گفته می*شود:
for i=1 to 100 do in parallel something();

به این معنی است که صد پردازش ایجاد شده و پردازنده*های شماره يك تا صد آن کار را به صورت موازی با هم انجام دهند. ممکن است حلقه*های تکرار به صورت تودرتو نیز استفاده شوند. از آن*جا که در پردازش*های موازی نیز گاهی لازم است کاری به صورت ترتیبی انجام شود، حلقه*های تودرتو نیز ممکن است ترکیبی از حلقه*های ترتیبی و موازی باشند. به عنوان مثال:

for i=1 to 10 do
for j=1 to 20 do in parallel
something();
در این شبه*کد بيست پردازش ایجاد می*شود و هریک به پردازنده شماره يك تا بيست سپرده می*شود و آن پردازنده*ها به*طور موازی تابع () somethingرا فراخوانی می*کنند و بعد پردازش مربوطه پایان می*یابد و این کار تا ده بار تکرار می*شود. باید توجه داشت که در هر بار تکرار حلقه بیرونی، بيست پردازش ایجاد و از بین می*روند. یعنی در مجموع دويست پردازش در نوبت*های بيست تایی ایجاد و از بین می*روند. اما به عنوان مثال به شبه*کد زير توجه کنید:

for i=1 to 10 do in parallel
for j=1 to 20 do
something();
در این حالت ده پردازش ایجاد می*شود و هریک به پردازنده شماره يك تا ده سپرده می*شود. سپس هر پردازش، تابع () something را بيست بار پشت سر هم فراخوانی کرده و بعد کار پردازش به پایان می*رسد. با اتمام همه پردازش*ها کار این قطعه کد به پایان خواهد رسید و در مجموع تنها بيست پردازش خواهیم داشت. حال تفاوت دو حالت قبل را با حالت زير مقایسه کنید:

for i=1 to 10 do in parallel
for j=1 to 20 do in parallel
something();
در این حالت 20×10 یعنی دويست پردازش ایجاد*شده و به پردازنده*های شماره (1،1)، (1،2)،...(1،20)، (2،1)، (2،2)،...(2،20)،...(10،20) یا به عبارتی به دويست پردازنده سپرده می*شوند و این پردازنده*ها به محض شروع پردازش، به*طور همزمان یک بار تابع() something را فراخوانی کرده و سپس پردازش آن*ها به پایان می*رسد.

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

همگام*سازی
بسیاری از الگوریتم*هایی که برای اجراي موازي دستورات، موازی*سازی می*شوند، الگوریتم*هایی هستند که پردازش*های موازی حاصل از آن*ها بدون نیاز به ارتباط با دیگر پردازش*ها، به محاسبات خود پرداخته و آن را ادامه می*دهند. در این الگوریتم*ها با وجود نیاز پردازنده*ها به برخی مقادیر داده*ای مشترک، هر پردازنده می*تواند بدون هیچ*گونه وابستگی به مقادیر میانی تولید*شده توسط پردازنده*های دیگر، به اجرای خود ادامه*دهد. این نوع از الگوریتم*ها روی هر دو معماری چندپردازنده*ای و شبکه*های کامپیوتری خوب اجرا شده و می*تواند سرعت اجرای*بالایی داشته باشد. اما الگوریتم*های دیگری نیز وجود دارند که در آن*ها هر پردازنده محاسبات تکراری یکسانی را روی یک جزء متمایز داده*ای انجام می*دهد، اما پردازنده*ها باید در انتهای هر تکرار با یکدیگر همگام شوند و نتایج میانی خود را در اختیار دیگر پردازنده*ها قرار دهند.
یکی از مهم*ترین و اصلی*ترین کاربردهای پردازش و محاسبات موازی، حل مسائل عددی با مقیاس بزرگ است. این مسائل به نوعی شامل آرایه*های چندبعدی بزرگ هستند که به دلیل متمایز بودن عناصر آرایه از یکدیگر، قابلیت بالایی برای موازی شدن دارند و می*توانند به صورت هم*روند پردازش شوند. تکنیک*های محاسباتی عددی روی این*آرایه*ها، معمولاً حالت تکرارپذیر داشته و هر تکرار، مرحله*ای از پیشرفت محاسبات به سوی پاسخ نهایی را تشکیل می*دهد. به بیانی دیگر در هر تکرار، از نتایجی که از تکرار قبل به*دست آمده است، استفاده شده تا برنامه به تدریج به سمت یک جواب با دقت مطلوب همگرا شود. بنابراین، هیچ پردازنده*ای با وجود آن*که ممکن است تکرار خود را بسیار سریع*تر از سایر پردازنده*ها انجام داده*باشد، نمی*تواند تکرار i+1ام را آغاز کند، مگر اين*كه همه پردازنده*ها تکرار iام را پایان داده باشند. این کار به همگام*سازی یا سنکرون کردن معروف است. این نوع برنامه*های موازی روی سیستم*های چندپردازنده*ای اجرای خوبی دارند. زیرا معمولاً زمان لازم برای همگام*سازی تمام پردازنده*ها به نسبت کوچک بوده و این کار روی قابلیت اجرایی برنامه تأثیر زیادی نخواهد داشت. اما همگام*سازی روی شبکه*های کامپیوتری به دلیل آن*که پردازنده*ها حالت توزیع*شده دارند، اثر بیشتری روی زمان اجرا خواهد داشت. به همین دلیل، اگر در به*کارگیری این روش به دقت عمل نکنیم با کاهش شدید قابلیت اجرایی برنامه و سرعت آن روبه*رو خواهیم شد.
روش*های متعددی برای همگام*سازی وجود دارد. برای نمونه برخی از سیستم*ها به منظور فراهم آوردن یک مکانیزم همگام*سازی، یک عملگر حصاربندی (Barrier) دارند که در زبان برنامه*نویسی موازی وجود دارد. در این روش، نقطه*ای داخل یک برنامه تعیین می*شود که در آنجا پردازش*های موازی برای یکدیگر به حال انتظار قرار می*گیرند. پردازش*های اولیه که دستورالعمل حصاربندی را اجرا می*کنند تا زمانی که تمام پردازش*های دیگر وارد این نقطه شوند، در انتظار باقی می*مانند. پس از اين*كه تمام پردازش*ها به نقطه حصاربندی رسیدند، همگی دوباره آزاد شده و اجرای همزمان خود را ادامه خواهند داد.