بخشی از مقاله
چکیده
یکی از چالشهای موجود در سیستمهای موازی، زمانبندی است. زمانبندی بهینه وظایف در سیستمهای موازی بر روی کارایی سیستم تاثیر زیادی دارد. بعضی از سیستمهای موازی به صورت بلادرنگ هستند و ممکن است برخی وظایف برای اجرا دارای ضربالاجل باشند که باید قبل از فرارسیدن زمان ضربالاجلشان اجرا شوند، در غیر اینصورت از بین خواهند رفت و باید دوباره به سیستم اختصاص داده شوند. لذا در چنین شرایطی وظایف باید بگونهای به پردازندهها اختصاص داده شوند که اولا، حداقل تعداد وظایف از بین بروند و ثانیا، سیستم زمان پاسخ و بهرهوری مناسبی داشته باشد. در این مقاله یک روش جدید مبتنی بر الگوریتم ژنتیک و منطق فازی برای زمانبندی وظایف بر روی سیستمهای موازی ناهمگنِ بلادرنگ معرفی شده است. نتایج بدست آمده از شبیهسازیهای انجام شده نشانگر کاهش تعداد وظایف از دست رفته در مقایسه با الگوریتمهای مشابه دیگر است. همچنین زمان پاسخ بدست آمده از روش پیشنهادی با توجه به تعداد وظایف پردازش شده در مقایسه با روشهای مشابه دیگر مناسب است و بهره وری بالایی را نسبت به این روشها دارد.
کلید واژه- زمانبندی، سیستمهای موازی چند پردازندهای، ضربالاجل، الگوریتم ژنتیک، منطق فازی
.1 مقدمه
پردازش موازی یا محاسبات موازی به اجرای همزمان یک برنامه که به بخشهای کوچکتری تقسیم شدهاست، بر روی چند پردازنده موازی به منظور دستیابی به سرعت بیشتر اطلاق میشود. ایده اصلی این است که فرایند حل یک مساله را معمولاً میتوان به زیروظایف خردتری تقسیم کرد که با اجرای همزمان این زیروظایف و هماهنگ کردن آنها مساله اصلی در زمان کوتاهتری حل میشود 1]، .[2
با توجه به اینکه امروزه پردازش موازی نقش بسیار مهمیدر عرصههایی از جمله برنامههای شبیهسازی در تحقیقات هستهای، نانو فناوری محاسباتی، برنامههای پیشبینی وضعیت هوا، برنامههای فیلمسازی کامپیوتری، برنامههای ساخت انیمیشن حرفهای و بسیاری از زمینههای مختلف دیگر را دارد، لذا استفاده از سیستمهای چند پردازندهای یا سیستمهای موازی به یک نیاز اساسی تبدیل شده است 1]، .[6-3
یکی از مسائل مهم در سیستمهای چند پردازندهای زمانبندی و نحوه تخصیص وظایف به پردازندهها است 13]، .[14 زمانبندی بر روی سیستمهای چند پردازنده به این صورت تعریف میشود که چند وظیفه به صورت همزمان برروی چند پردازنده اجرا میشوند . تعیین ترتیب چگونگی ورود وظایف به پردازندهها برای اجرا، تاثیر مستقیمی را برروی زمان اجرای کل، کارآیی پردازندهها و غیره دارد. بعضی از سیستمهای موازی به صورت بلادرنگ هستند 2]، [15 و باید وظایف در آنها در زمانهای مشخصی وارد سیستم شده و اجرا شوند. در واقع وظایف دارای ضربالاجل هستند و باید قبل از ضربالاجل زمانبندی شوند که در غیر اینصورت از بین خواهند رفت 3-1]، 4، .[7
در این مقاله یک روش جدید مبتنی بر الگوریتم ژنتیک و منطق فازی برای زمانبندی وظایف در سیستمهای چندپردازندهای ناهمگن بلادرنگ معرفی شده است. طبق روش ارائه شده ابتدا وظایف براساس زمان ضربالاجلشان با استفاده از منطق فازی در دستههایی تقسیم میشود و سپس هر دسته مطابق با الویتشان با استفاده از الگوریتم ژنتیک زمانبندی میشوند. در ادامه این مقاله ابتدا مدل سیستم و مسئله مورد نظر تعریف میگردد؛ سپس روش پیشنهادی به طور کامل تشریح میگردد. در نهایت نتایج بدست آمده مورد ارزیابی قرار گرفته و تجزیه و تحلیل میگردد.
-2 تعریف مسئله
سیستمهای چند پردازنده موازی میتوانند به دو صورت همگن و ناهمگن باشند. ناهمگن بودن به این معنا است که پردازندهها سرعت و ظرفیت پردازشی متفاوتی دارند، در حالی که در سیستمهای همگن همه پردازندهها از قدرت و ظرفیت پردازشی یکسانی برخوردار هستند. از آنجایی که محیط پردازندهها به صورت ناهمگن است بنابراین پردازندهها سرعت وقدرت پردازشی متفاوتی را دارند و از این جهت هر وظیفه برای اجرا در پردازندههای مختلف زمان اجرای متفاوتی را نیاز دارد تا بطور کامل اجرا شود. همچنین فرض میکنیم که زمانبندی به صورت قطعی است. زمانبندی قطعی یعنی اینکه تمامی اطلاعات را درباره وظایف در اختیار داریم، این اطلاعات میتواند شامل اطلاعاتی از قبیل زمان اجرا هر وظیفه و ضربالاجل هر وظیفه باشد .[10-8]
برای تعریف روشنتر مسئله از یک مثال استفاده میکنیم، جدول - 1 - مثالی را نشان میدهد که 5 وظیفه و 2 پردازنده ناهمگن وجود دارد، همچنین هر یک از وظایف دارای ضربالاجل هستند که به علت ناهمگن بودن پردازندهها هر وظیفه دارای زمان اجرای متفاوت بر روی پردازندههای مختلف است. برای مثال فرض میکنیم وظایف با ترتیب T3, T5, T4, T2 ,T1 از چپ به راست وارد سیستم شوند. در این صورت زمانبندی به صورت شکل - 1 - خواهد بود، T3 ابتدا وارد پردازنده 1 میشود و زمان اجرای T1 طبق جدول - 1 - در پردازنده اول برابر با 3 است. سپس T5 وارد پردازنده دوم میشود که زمان اجرای آن برابر با 4 است و به همین ترتیب تا آخر. نتیجه بدست آمده از این ترتیب زمانبندی به این صورت است که یک وظیفه از دست میرود و زمان پاسخ برابر با 10 میشود.
اما اگر ترتیب وظایف به صورت T1, T3, T5, T4, T2 از چپ به راست باشد در این صورت ابتدا T1 وارد پردازنده اول میشود که زمان اجرای آن 4 است. سپس T3 وارد پردازنده دوم میشود که زمان اجرای آن 5 است. بنابراین ضربالاجل وظایف T5، T4 و T2 گذشته است و این وظایف از دست میروند. نتیجه بدست آمده از این ترتیب به این صورت است که 3 وظیفه از دست میرود و زمان پاسخ برابر با 5 است، که این نحوه زمانبندی در شکل - 2 - نشان داده شده است.
با توجه به مثال بالا، ترتیب زمانبندی اول نسبت به ترتیب زمانبندی دوم بهینه است. چون هم تعداد وظایف از دست رفته در ترتیب زمانبندی اول کم است و هم زمان پاسخ بدست آمده نسبت به تعداد وظایف پردازش شده، مناسب است. لذا در سیستمهای چند پردازنده موازی ناهمگن بلادرنگ، نحوه اختصاص وظایف به پردازندهها بطوری که هزینهها، زمان پردازش دادهها، کارایی سیستم، تعداد وظایف از دست رفته و غیره حداقل شود، به عنوان یک چالش و مسئله مهم محسوب میشود.
.3 روش پیشنهادی
در این بخش یک روش جدید مبتنی بر منطق فازی و الگوریتم ژنتیک برای زمانبندی وظایف در سیستمهای چند پردازنده موازی - ناهمگن - معرفی میشود. طبق روش پیشنهادی ابتدا وظایف براساس قوانین فازی در سه گروه تقسیم میشوند. سپس الگوریتم ژنتیک در هر گروه به صورت مجزا اجرا میشود و سپس جواب نهایی برای مسئله ارائه میگردد. در ادامه به بررسی روش پیشنهادی میپردازیم.
.1-3 مرحله اول: فازیسازی
همانطور که گفته شد، وظایف دارای ضربالاجل هستند. لذا اگر ضربالاجل یک وظیفه فرا رسد در این صورت آن وظیفه از بین خواهد رفت. در روش پیشنهادی از دو پارامتر برای فازیسازی استفاده شده است. این دو پارامتر عبارتاند از:
- زمان ضربالاجل هر وظیفه
- میانگین زمان اجرای هر وظیفه در پردازندههای مختلف
