بخشی از مقاله
چکیده
سیستمهای چندپردازندهای جهت بالا بردن سرعت سیستم و کارایی آن به وجود آمدهاند. جهت رسیدن به این هدف یک سیستم زمانبند کارآمد بهعنوان یک بخش مهم برای محیط چندپردازندهای ضروری هست.سیستم زمانبندی در محیط چندپردازندهای باید با استفاده از یک الگوریتم کارا، منابع سیستم را به شکلی به برنامه کاربر که از تعداد زیادی وظیفه مستقل از هم تشکیل شده است، تخصیص دهد با توجه به استراتژی بهینهسازی، پارامتر خواستهشده - زمان - مینیمم شود.
مسئله زمانبندی ایستای وظایف در سیستمهای چندپردازندهای به دلایل استفاده بهینه از پردازندهها و همچنین صرف زمان کمتر،دارای اهمیت فراوانی است.این مسئله از رده مسائل سخت و غیرقطعی است و به دست آوردن جواب بهینه دارای پیچیدگی زمانی بالایی است که برای حل آن نمیتوان از الگوریتمهای قطعی و با پیچیدگی چندجملهای استفاده کرد بلکه باید از الگوریتمهای فراابتکاری مانند الگوریتم ژنتیک، تپه نوردی، جستجوی ممنوعه، شبیهسازی سردکردن تدریجی و سایر روشهای ابتکاری استفاده کرد.
در این پایاننامه برای زمانبندی وظایف در محیط چندپردازندهای دو مدل پیشنهاد شده است مدل اول استراتژی الگوریتم ژنتیک استفاده شده است و مدل دوم ا الگوریتم رقابت استعماری به کار گرفته شده است و مقایسه این دو مدل زمانبند نشان میدهد که زمانبند دوم - الگوریتم رقابت استعماری - نتایج بهتری برای زمانبندی دارد و زمان اتمام کل را در زمان کمتری انجام میدهد. همچنین برای سنجش کارایی مدل پیشنهادی دوم با شش الگوریتم غیرژنتیک ETF - ، DLS ،LAST ، HLFET، ISH و - MCP نیز مقایسه شده است نتایج نشان میدهد که مدل پیشنهادی دوم - الگوریتم رقابت استعماری - زمان اتمام کل وظایف را در زمان کمتری انجام میدهد، توانسته این مقدار را بهبود دهد..شبیهسازی مدلهای پیشنهادی در محیط متلب انجام شده است.
-1 مقدمه
سیستمهای پردازش موازی امروزه کاربردهای زیادی در زمینههای پردازش اطلاعات، مدلسازی آبوهوا، سیستمهای پایگاه داده، شبیهسازی بلادرنگ سیستمهای پویا و پردازش تصویر دارند. بیشترین کارایی از این سیستمها وقتی به دست میآید که راهکارهای تقسیمبندی کارها بین پردازندهها بهصورت کارا بهکاربرده شود. یکی از وظایف مهم سیستمعامل، زمانبندی منابع برای تخصیص بهکاربران است که یکسری محدودیتها را اعمال میکند . وقتی دادهای بین چند پروسه و برنامه بهصورت اشتراکی استفاده میشود، برای عملیاتی که قرار است روی داده انجام دهند، بین پروسهها یک زمانبندی مشخص میکند که کدام پروسه در کدام زمان به داده دسترسی داشته باشد . کدام کاربر در چه زمانی با کدام منبع ارتباط داشته باشد.
زمانبندی 1 به مجموعهای از مکانیزم ها و سیاستها گفته میشود که یک سیستمعامل برای اجرای فرایندها به کار میبرد . مسئله زمانبندی در یک سیستم چندپردازندهای - -Al - Mouhamed, 1990; A. S. Wu, Yu, Jin, Lin, & Schiavone, 2004 و در سیستمهای توزیعشده ناهمگن - Ilavarasan & Thambidurai, 2007 - از رده مسائل سخت است - . - Holland & Goldberg, 1989به همین جهت از روشهای ابتکاری و غیرقطعی استفاده میشود.هر چند در روشیهاابتکاری لزوماً جواب کاملاً بهینه را نخواهیم داشت. ولی در یک بازه زمانی معقول،جوابی نزدیک به جواب بهینه به دست خواهیم آورد.
قضیه :1-2 هیچ الگوریتم زمانبند مبتنی بر افراز که بتواند بهصورت موفقیتآمیز وظیفههای موجود در T را روی M پردازنده زمانبندیکند، به شرطی که U - T - > - M + 1 - /2 وجود نداردAndersson & Jonsson, 2000; Lauzac, - . - - U - T ne - p. - Melhem, & Mosse, 1998نتایج نظری نشان میدهد که مسئلهی زمانبندی سیستمهای بیدرنگ چندپردازنده در اکثر موارد از مرتبهی زمانی غیرچندجملهای2 است. قضیههای ادامه دلیلی بر این مدعا هستند:قضیه :2-2 مسئلهی زمانبندی M پردازنده، به همراه مجاز بودن انقطاع، درجایی که باید تعداد وظیفههایی که تأخیر دارند کمینه شوند، از مرتبه زمانی غیر چندجملهای - NPC - است - - Stankovic, Spuri, Di Natale, & Buttazzo, 1995 .قضیه :3-2 کمینه کردن تأخیر کل N وظیفهی مستقل از هم روی یک ماشین موازی از مرتبه زمانی غیر چندجملهای - 3NPH - است .
-2 مروری بر پژوهش های انجام شده
پیج و همکاران در سال 2005، یک الگوریتم برای طراحی پویا وظایف ناهمگونی بر روی پردازنده های ناهمگن در یک سیستم توزیع شده طراحی کردند. زمانبندی در محیطی با منابع دینامیک تغییر می کند و با منابع سیستم متغیر سازگار است .این کار به صورت دسته ای عمل می کند و از الگوریتم ژنتیکی برای به حداقل رساندن کل زمان اجرا به کار بردند. .زمانبندی پیشنهادی را با شش برنامه زمانبندی دیگر، سه حالت دسته ای و سه زمانبندی فوری حالت مقایسه کرده اند .نتایج کارآمدتری نسبت به تمامی زمانبندیهای دیگر را در طیف وسیعی از سناریوهای مختلف به دست آوردهاند . - Page & Naughton, 2005 - ماین گان هانگ4 و همکاران در مقاله خود در سال 2010 یک الگوریتم جدید زمانبندی ساده به نام LSTR، بهعنوان یک الگوریتم پویا با اولویت برای محیط چندپردازنده استفاده کردند و مقادیر بهینه خود را با تستهای مختلف نشان دادند.
- Hwang, Pankoo Kim و . - Dongjin Choi 2010 جی یون لی5 و همکاران در سال 2016 در مقاله خود به اصلاح گروه الگوریتم زمانبندی بلادرنگ با توجه به واحد اصلی زمانبندی پرداختند و زمانبندی بلادرنگ را با توجه به تخصیص اولویت از سطح وظیفه تا سطح ترد توسعه دادند - Lee, 2016 - .آویناش مالیک6 و همکاران، در سال 2018 در استراتژی خود فرمول دقیق SMT7 از مسائل زمانبندی را اساس کار خود قراردادند که تنها نیاز به یک متغیر شرطی دارد. زمانبند بهینه پیشنهادشده را در تمرینهایی بیش از هزار گراف وظایف ارزیابی شده است و در مقایسه با فرمول MILP8 قابلفهمتر و پیشرفتهتر است - . - 0DOLN' :DONHU' 2ʼ6XOOLYDQ' 6LQQHQ' 2018
-3 مواد و روشها
در این بخش مقاله ، به شرح روشهایی که برای انجام پژوهش استفاده شده است پرداخته می شود.
-1-3 الگوریتم رقابت استعماری
الگوریتم رقابت استعماری9، همانند سایر روشهای بهینهسازی تکاملی، با تعدادی جمعیت اولیه شروع میشود. در این الگوریتم، هر عنصر جمعیت، یک کشور نامیده میشود. کشورها به دودسته مستعمره و استعمارگر تقسیم میشوند.
-2-3 مراحل الگوریتم رقابت استعماری
همانند دیگر الگوریتمهای تکاملی، این الگوریتم، نیز با تعدادی جمعیت اولیه تصادفی که هرکدام از آنها یک "کشور" نامیده میشوند؛ شروع میشود. تعدادی از بهترین عناصر جمعیت بهعنوان امپریالیست انتخاب میشوند. باقیمانده جمعیت نیز بهعنوان مستعمره، در نظر گرفته میشوند. استعمارگران بسته به قدرتشان، این مستعمرات را با یکروند خاص که در ادامه میآید؛ به سمت خود میکشند. قدرت کل هر امپراتوری ، به هر دو بخش تشکیلدهنده آن یعنی کشور امپریالیست - بهعنوان هسته مرکزی - و مستعمرات آن، بستگی دارد. در حالت ریاضی، این وابستگی با تعریف قدرت امپراتوری بهصورت مجموع قدرت کشور امپریالیست، بهاضافه درصدی از میانگین قدرت مستعمرات آن، مدل شده است.
-3-3 شکلدهی امپراتوریهای اولیه
در بهینهسازی، هدف یافتن یک جواب بهینه برحسب متغیرهای مسئله، است. ما یک آرایه از متغیرهای مسئله را که باید بهینه شوند، ایجاد میکنیم. در الگوریتم ژنتیک این آرایه، کروموزوم نامیده میشود. در اینجا نیز آن را یک کشور مینامیم. در یک مسئلهی بهینهسازیN بعدی، یک کشور، یک آرایهی 1 N است.
