عنوان

ارائه ی رویکرد جدید تکامل برای زمان‌بندی گراف وظایف بر روی سامانه‌های چندپردازنده‌ای ناهمگن

‭۱۶۲۸۶پ‬

per

ارائه ی رویکرد جدید تکامل برای زمان‌بندی گراف وظایف بر روی سامانه‌های چندپردازنده‌ای ناهمگن

/فرج قاسم‌زاده گچه

: علوم ریاضی

، ‮‭۱۳۹۵‬

، راشدی

چاپی

کارشناسی ارشد

علوم کامپیوتر گرایش سیستم های کامپیوتری

‮‭۱۳۹۵/۱۱/۰۶‬

تبریز

با گسترش روزافزون استفاده از کامپیوتر برای انجام برنامه‌های محاسبات بزرگ و پیچیده، نیاز به پردازش سریع افزایش یافته و به ی نیاز اساس تبدیل شده است .در پاسخ به این نیاز، استفاده از پردازنده‌های زیاد و ناهم‌ن رواج یافته است .در سامانه‌های ناهم‌ن، همه پردازنده‌ها از ی نوع نیستند و زمان اجرای ی وظیفه بستگ به نوع پردازنده‌ای که در آن اجرا م‌شود، دارد .ی از روش‌های به دست آوردن کارآیی بالا در چنین س‌وهایی، زمان‌بندی گراف وظایف بوده که ثابت شده است در حالت کل ی مسئله چندجمله‌ای غیرقطع-سخت م‌باشد .به خاطر اهمیت مسئله زمان‌بندی گراف وظایف روی سیستم‌های چندپردازنده‌ای، این موضوع به‌طور گسترده بررس شده و ال‌وریتم‌های مختلف برای حل این موضوع ارائه شده است .هدف از انجام این پایان‌نامه ارائه ی روی‌رد جدید تکامل برای زمان‌بندی گراف وظایف بر روی سیستم‌های چندپردازنده‌ای ناهم‌ن م‌باشد .در این روی‌رد نوین در ابتدا با استفاده از ادغام صحیح وظایف گراف، سع شده است گراف وظایف تا حدودی از یال‌های ارتباط اضافه، حذف گردد .سپس با استفاده از ال‌وریتم تکامل تخمین توزیع، ترتیب درست از اجرای وظایف گراف را ارائه م‌دهیم و درنهایت با استفاده از ال‌وریتم جست‌جوی همسای متغیر، پردازنده‌ها را به هدف بهینه کردن طول نهایی زمان‌بندی گراف وظایف، به وظیفه‌ها اختصاص م‌دهیم .نتایج حاصل از پیاده‌سازی روی‌رد ارائه شده بر روی گراف‌های وظایف مورد آزمون در این پایان‌نامه به خوبی نشان م‌دهد که این روش از روش‌های پیشین و ال‌وریتم‌های معروف بهتر عمل کرده است و طول نهایی زمان‌بندی گراف وظایف را به مقدار قابل توجه بهبود بخشیده است

With the increasing use of computers to perform complex computing applications require increased processing speed has become a basic requirement. In response to this need, the use of heterogeneous processors with many cores has increased. In heterogeneous systems, all processors are not of a kind. Depending on the type of processor time to perform a task in which it is implemented. One of the ways to obtain high efficiency in such platforms is scheduling the tasks graph. In general, an issue that has been proven non-deterministic polynomial-hard. Because of the importance of the scheduling tasks graph on SMP systems, this issue has been widely studied And several algorithms have been proposed to solve this issue. In this approach, using new initially proper integration tasks graph, trying to some extent tasks graph of the crest of the optimal added, Then using an estimate of the distribution algorithm of tasks in order to implement the graph, Finally with the use of neighborhood variable search algorithm, processors to optimize timing during the final of the tasks graph assigned tasks. the results of the implementation of the presented approach on the tasks graphs benchmark in this dissertation to suggest that the approach of the previous approaches and better known algorithms acted and the ultimate elongation graph scheduling tasks into a significant amount of improved

قاسم‌زاده گچه، فرج

عیسی زاده، آیاز، استاد راهنما

ایزدخواه، حبیب، استاد راهنما

سیاه و سفید

نمایه‌سازی قبلی