الگوریتم ژنتیک ترکیبی زمانبندی گراف وظایف در معماری چند پردازنده ای

سال انتشار: 1391
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 1,891

فایل این مقاله در 6 صفحه با فرمت PDF قابل دریافت می باشد

این مقاله در بخشهای موضوعی زیر دسته بندی شده است:

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

ICEEE04_320

تاریخ نمایه سازی: 6 مهر 1391

چکیده مقاله:

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

کلیدواژه ها:

زمانبندی چند پردازنده ای ، گراف وظایف و الگوریتم های ژنتیک

نویسندگان

مصطفی ماهی

مربی، گروه مهندسی کامپیوتر و فناوری اطلاعات، دانشگاه پیام نور

پریسا امین نژاد

مهندسی کامپیوتر، دانشگاه آزاد اسلامی واحد بناب، دانشکده برق و کامپیو

مراجع و منابع این مقاله:

لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :
  • th Irarnian _ _ _ (ICEEE2012) _ Practical ...
  • M. R. Garey and D. S. Johnson, Computers and Intractability: ...
  • Y. K. Kwok and I. Ahmad, Benchmarking and Comparison of ...
  • J. J. Hwang, Y. C. Chow, F. D. Anger and ...
  • G. C. Sih and E. A. Lee, A Compile-Time for ...
  • Architectures, IEEE Transaction on Parallel and Distributed Systems, Vol. 4, ...
  • J. Baxter and J H. Patel, The LAST Algorithm: A ...
  • Conference on Parallel Processing, Vol. 2, August 1989, pp. 217-222. ...
  • E. G. Coffman, Computer and Job-Shop Scheduling Theory, John-Wiley, 1976. ...
  • B. Kruatrachue and T. G. Lewis, Duplication Heuristics ...
  • Precedence Task Scheduler for Parallel Processor Systems, Technical Report, Oregon ...
  • M. Y. Wu and D. D. Gajski, Hypertool: A Mes ...
  • Systems, IEEE Trans. on Parallel and Distributed Systems, Vol. 1, ...
  • Kwok and I. Ahmad, Benchmarking and Comparison of the Task ...
  • Min-You Wu, MCP Revisited, Department of and ...
  • J. Brest and V Zumer, A Comparison of the Static ...
  • Multiproces _ Scheduling Algorithms for Efficient Parallel Processing, IEEE Transaction ...
  • M. Rinehart, v. Kianzad, and Sh. S. Bhattacharyya, A Modular ...
  • M. A. _ -Mouhamed, Lower Bound on the Number of ...
  • , No. 12, Dec. 1990, pp. 1390-14)1. ...
  • A. S. Wu, H. Yu, Sh. Jin, K. Ch. Lin ...
  • B. Shirazi, M. Wang and G. Pathak, Analysis and Evaluation ...
  • R. C. Correa, A. Ferreira and P. Rebreyend, Scheduling Multiproce ...
  • D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine ...
  • S. J. Kim and J C. Browne, A General Approach ...
  • نمایش کامل مراجع