بخشی از مقاله
چکیده
- تخصیص وظایف و زمانبندی آنها بر روی سیستمهای چندپردازنده موازی به این صورت تعریف میشود که چند وظیفه همزمان روی چند پردازنده اجرا میشوند. در مسائل زمانبندی هدف این است که کارها بدون تأخیر و زودرسی انجام شوند. هدف یافتن یک زمانبندی بهینه از کارهاست. الگوریتمهای زیادی به صورت اکتشافی و تقریبی برای حل مسأله زمانبندی ماشینهای موازی وجود دارد. در این مقاله پنج الگوریتم زمانبندی در ماشینهای موازی و چندپردازنده بررسی میشود. این الگوریتمها شامل روشهای مبتنی بر الگوریتم ژنتیک، اجتماع مورچگان و الگوریتم مبتنی بر عامل میباشد. الگوریتمهای مبتنی برژنتیک راه حل خوبی را برای تخصیص وظایف به پردازندهها ارائه میکنند. همچنین نتایج بیانگر این موضوع هستند که الگوریتمهای مبتنی بر روش اجتماع مورچگان و مبتنی بر عامل زمانبندیهای مناسبی را ارائه میدهند.
کلید واژه- الگوریتم اجتماع مورچگان، الگوریتم ژنتیک، زمانبندی، ماشینهای چند پردازنده موازی.
-1 مقدمه
بــا گســترش روزافــزون اســتفاده از کــامپیوتر در کارهــای تحقیقاتی نیاز به پردازش سریع افزایش یافتـه و بـه یـک مسـئله اساسی تبدیل شده است. امـروزه پـردازش مـوازی نقـش بسـیار جدی در این زمینه ایفا میکند. مفهوم پردازش موازی به اجـرای چند وظیفه که میتوانند به صورت همزمان روی چنـد پردازنـده اجرا شود، اشاره میکند. یک سیستم پردازش موازی، از تعـدادی پردازنده یکسـان تشـکیل شـده اسـت، کـه از طریـ ق مسـیرهای ارتباطی یکسانی با یکدیگر در اتباط هستند. مسئله زمانبنـدی در سیستمهای چندپردازنـدهای بـا تخصـیص بهینـه مجموعـه ای از وظایف و ترتیب اجرای آنهـا کـه مجمـوع کـل زمـان اجـرا را در سیستم چند پردازنده مـوازی بـه حـداقل برسـاند، سـروکار دارد. تخصیص وظایف و زمانبندی آنها روی سیستمهای چند پردازنده موازی به این صورت تعریف میشود که چند وظیفـه بـه صـورت همزمان بر روی چند پردازنده اجرا میشوند. الگوریتمهای زیادی
وجود دارد که به صورت اکتشـافی و تقریبـی عمـل زمانبنـدی را انجام میدهند. در زمانبندی ماشینهای موازی، ابتدا تعدادی کار با زمان پردازش مشخص، چندین ماشین مـوازی یکسـان و یـک موعد مقرر داریم. هدف یافتن یک زمانبندی بهینه از کارهاسـت. در این مسائل n کار در m ماشین پردازش میشوند. هر کار فقـط روی یک ماشین قابل پردازش است. تخصیص کارها به ماشینهـا و پردازش آنها در هـر ماشـین، دو مسـأله اساسـی در زمانبنـدی ماشینهای موازی است. تعیین ترتیب چگونگی ورود وظـایف بـه پردازندهها برای اجرا، بر روی زمان اجرای کل کارایی پردازندههـا تأثیر مستقیم دارد. زودرسی و تأخیر، دو معیار مهم در زمانبندی ماشینهای موازی است.
ادامه مقاله به این صورت سازماندهی شـده اسـت: در بخـش بعدی دو روش زمانبندی کارآمد با اسـتفاده از الگـوریتم ژنتیـک معرفی مـیشـود. در بخـش سـوم، الگـوریتم زمانبنـدی ژنتیـک کوانتومی توصیف میشود. الگوریتم زمانبندی مبتنی بـر اجتمـاع مورچگان در بخـش چهـارم معرفـی شـده اسـت. بخـش پـنجم، الگوریتم زمانبندی مبتنی بر عامل را توضیح میدهـد. در بخـش
زذتل خغ1سکطغکطکسغپه
حغحل شAلع ,لاهلاکغهعطکل y,هق ذصستص
آخر هم نتیجهگیری آورده شده است.
-2 زمانبندی در ماشینهای چند پردازنده موازی با استفاده از الگوریتم ژنتیک
در این بخـش دو روش مبتنـی بـر الگـوریتم ژنتیـک بـرای مسئله زمانبندی وظایف در سیستمهـای چنـد پردازنـده مـوازی معرفی میشود. الگوریتم ژنتیک با یک نسل اولیه شروع میشـود که هر یک از افراد این نسل یک راهحل قابل قبول بـرای مسـئله هستند. تابع معیار میـزان شایسـتگی هـر یـک از افـراد نسـل را ارزیابی میکند. در حالت کلی الگوریتم ژنتیک شامل عملگرهـای کلیدی ترکیب، جهـش و انتخـاب اسـت. بـرا ی هـر یـک از ایـن عملگرهای جهش و ترکیب، احتمـال جهـش و احتمـال ترکیـب انتخاب میشود. در ادامـه ایـن روش بـه طـور کامـل شـرح داده میشود.
