نوع فایل: word
قابل ویرایش 71 صفحه
چکیده:
زمانبندی کارها در سیستم های چند پردازنده ای شامل نگاشت کردن کارهای موجود در یک Task Graph به هریک از پردازنده ها می باشد. یک Task Graph گرافی غیر چرخشی می باشد که هر یک از گره های آن شامل کارهای محاسباتی است که بین گره ها روابط تقدم و تاخر وجود دارد. آنچه که در این زمانبندی مهم است اینکه باید طوری صورت گیرد که مدت زمان اجرای کل کارها مینیمم گردد.
این مسئله که NP (غیرچند جمله ای) است دارای روش های حل مختلفی است که یکی از آنها الگوریتم ژنتیک می باشد.
در این پروژه یکی از روش های چند جمله ای برای این مسئله ارائه گردیده است که برای پایه نمایش دو کروموزومی می باشد.
این روش با استفاده از یک محیط شبیه سازی پیاده سازی شده و نتایج حاصله قابل مشاهده می باشد.
مقدمه:
مسئله زمانبندی کارها درسیستم های چند پردازنده ای برپایه زمانبندی مجموعه ای از کارها که به صورت جزئی مرتبند بنا نهاده شده است . به زبان ساده زمانبندی به مفهوم تخصیص منابع موجود (مثلا پردازنده ها ) به کارهای محاسباتی است که بین این کارها ویژگی ترتیب جزئی برقرار است یعنی اینکه بین کارها تقدم وتاخر اجرا وجود دارد.
مجموعه Task هایی که قراراست اجرا گردد برروی یک گراف غیرچرخشی (Direct Acyclic Graph) بنامTask Graph قراردارد.
هدف از نگاشت Task های موجود به هریک از پردازنده ها این است که اجرای کلیه Taskها درحداقل زمان ممکن گردد.
مسئله زمانبندی کارها به عنوان یک مسئله انتزاعی بررسی میگردد وزمینه های کاربردی این مسئله می تواند درپردازش موازی و زمانبندی حرکت قطارها وحل مشکل ترافیک شهری وکاربردهایی درخط تولید کارخانجات واقتصاد وتحقیق درعملیات ومواردی دیگرباشد. زمانبندی کارها به عنوان یک مسئله Np-Hard (غیر چندجمله ای )محسوب میگردد ووروش های مختلفی برای به دست آوردن جوابهای Optimal بکارگرفته شده است.
یکی ازاین روش ها الگوریتم های ژنتیک می باشد که دارای ماهیت تصادفی بوده ومبتنی برمفاهیم ژنتیک بوده و برگرفته ازنظریه تکاملی داروین می باشد. اگوریتم های ژنتیکی باتقلید از مفهوم تکامل تدریجی باایجاد یکسری کروموزوم ها به عنوان اعضای جمعیت واعمال یکسری عملگرها مانند Selection و Crossover و Mutation و تولید جمعیت جدید به ایجاد نتایج بهینه می پردازد.
دراین پایان نامه الگوریتم ارایه شده دارای ساختارنمایشی دوکروموزومی بوده و به (Bi-Chromosal Genetic Algorithm)BCGA معروف است.
البته الگوریتم های ژنتیکی وغیرژنتیکی دیگری برای حل مسئله زمانبندی کارها درسیستم چند پردازنده ای وجود دارد .
فهرست مطالب:
چکیده
1) مقدمه
2) اصول الگوریتم های ژنتیکی
1-2) تاریخچه
2-2) صورت کلی الگوریتم های ژنتیکی
3-2) تعاریف مقدماتی الگوریتم های ژنتیکی
5-2) انواع عملگرها
6-2) شرایط توقف الگوریتم های ژنتیکی
7-2) پارامترهای الگوریتم ژنتیکی
3- تعاریف مربوط به مسئله زمان بندی چند پردازنده ای وGraph Task
4) الگوریتم های ارائه شده برای مسا له زمانبندی کارها
1-4 )الگوریتم های غیرژنتیکی برای حل مسئله
2-4) الگوریتم های ژنتیکی برای حل مسئله
1-2-4) الگوریتم ژنتیکی PGA
2-2-4) الگوریتم ژنتیکی بانمایش رشته ای متغیر
فصل پنجم الگوریتم ژنتیکی دوکروموزومی (BCGA) برای مسئله زمانبندی
1-5) نمایش کروموزوم ها (Representation)
3-1-5) نگاشت کردن یک زمان بندی به جفت کروموزوم
2-5) عملگرهای ژنتیکی به کاررفته درالگوریتم BCGA
3-5) محاسبه تابع Fitness
4-5) شرط خاتمه الگوریتم
5-5) پارامترهای دیگر الگوریتم
6) نتایج محیط شبیه سازی شده
7) نتیجه گیری و راهکارهای آینده
منابع
پیوست
منابع و مأخذ:
- X.yao "An Overview of evolutionary computation", Chinese Journal of Advanced Software Research (Allerton Press , INC , New york , 1996)
- A Comparison of General Approaches to Multiprocessor Scheduling - Parallel Processing Symposium, 1997. Proceedings., Ilth International
- Genetic Scheduling for Parallel Processor Systems:
Comparative Studies and
Performance Issues
Albert Y. Zomaya, Senior Member, IEEE, Chris Ward, and Ben Macey
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 10, NO. 8, AUGUST 1999
- yu – Kwong kwak and Ishfaq Ahmad , "Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessor",The university of hong kong And The Hong kong university of Science and Technology
پروژه کاربرد الگوریتم ژنتیک درزمانبندی کارهای سیستم های چند پردازنده ای. doc