زمانبندی ایستای کارهای مستقل در سیستم های چندپردازنده ای همگن با استفاده از رهیافت بهینه سازی کلونی مورچه ها

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

کلیدواژه ها:

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