زد فایل

مرجع دانلود فایل ,تحقیق , پروژه , پایان نامه , فایل فلش گوشی

زد فایل

مرجع دانلود فایل ,تحقیق , پروژه , پایان نامه , فایل فلش گوشی

پروژه کاربرد الگوریتم ژنتیک درزمانبندی کارهای سیستم های چند پردازنده ای. doc

اختصاصی از زد فایل پروژه کاربرد الگوریتم ژنتیک درزمانبندی کارهای سیستم های چند پردازنده ای. doc دانلود با لینک مستقیم و پر سرعت .

پروژه کاربرد الگوریتم ژنتیک درزمانبندی کارهای سیستم های چند پردازنده ای. doc


پروژه کاربرد الگوریتم ژنتیک درزمانبندی کارهای سیستم های چند پردازنده ای. doc

 

 

 

 

نوع فایل: 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
نظرات 0 + ارسال نظر
امکان ثبت نظر جدید برای این مطلب وجود ندارد.