بخشی از مقاله
چکیده
امروزه سیستمهای چندپردازندهای کاربرد وسیعی در محاسبات موازی دارند. یک روش زمانبندی مناسب، در کاهش زمان اجرای وظایف و بهرهوری منابع بسیار تأثیرگذار است. این زمانبندی باید بهگونهای انجام شود که بتواند زمان لازم برای اجرای کل برنامه را با در نظر داشتن زمان اجرای وظایف و بیکاری پردازندهها، کمینه نماید. با توجه به NP کامل بودن مسئله زمانبندی گراف وظایف، رویکردهای مبتنی بر روشهای قطعی در این زمینه کارا نخواهد بود؛ بنابراین استفاده از الگوریتمهای فرا مکاشفهای و الگوریتمهای ترکیبی برای حل این مسئله مؤثر خواهد بود لذا بهرهگیری از الگوریتم جستجوی گردابی، روش مناسبی جهت زمانبندی در سیستمهای چندپردازندهای میباشد.
در این مقاله، مسئله را به کمک روش ترکیبی جدیدی که مبتنی بر الگوریتم جستجوی گردابی است حل نمودیم. روش ترکیبی با در نظر گرفتن اولویت زمانبندی انجام کارها بر اساس زودترین زمان شروع کار و در نظر گرفتن اجرای والد خود و ترکیب آن با الگوریتم جستجوی گردابی برای انتخاب بهترین جواب برای مسئله، میتواند بهطور مؤثری برای مسائل زمانبندی در اکثر محیطهای موازی مورد استفاده قرار گیرد. نتایج حاصل شده نشان میدهد الگوریتم پیشنهادی جواب بهینهی زمانبندی را در مقایسه با سایر روشهای متداول نتیجه میدهد.
مقدمه
قابلیت دسترسی به سیستمهای چندپردازندهای قدرتمند، با برقراری ارتباط از طریق لینکهای پرسرعت مستلزم پیادهسازی یک بستر محاسباتی موازی برای برنامههای اجرایی با خواستههای گوناگون میباشد.[1] جهت بهره-برداری کامل از چنین سیستمهای محاسباتی برنامههای اجرایی آنها به تعدادی کار تجزیه میشوند که ممکن است وابسته یا غیر وابسته به یکدیگر باشند. [2,3] طراحی بهینه تکالیف یعنی یکسانسازی و سپس زمانبندی مناسب در مجموعههای متنوعی از دستگاهها، با هدف تنظیم کارآمدی کلی سیستم و گردآوری پتانسیلهای احتمالی در نتایج توزیعی ازجمله جوانب بحرانی محسوب میشود.
بهطورکلی مسئله زمانبندی تکالیف در گراف جهتدار بدون دور - - 1DAG مدلسازی شده است که در آن تکالیف برنامه اجرایی از طریق گرههای گراف و وابستگی بین دادهها میان کارهای مختلف به تصویر کشیده شده است. هزینه برقراری ارتباط درروی یالها و هزینههای محاسبات در نودها نشان داده شده است. مسئله زمانبندی موردنظر در اینجا یک مدل استاتیک است، زیرا ویژگیهای مختلف برنامه اجرایی همچون زمان اجرای کلیه کارها در منابع مجزا و هزینه ارتباطی میان آنها از قبل مشخص هستند. همچنین سیستم پردازش موازی بهصورت یکنواخت و انحصاری فرض شده است، یعنی اگر یک کار برای پردازش به یک پردازنده تخصیص داده شد تا اجرای کامل آن نمیتوان پردازنده را از آن کار پس گرفت.
در متون علمی برای حل مسئله زمانبندی کارها الگوریتمهای زیادی مطرح شده است که جز مسائل NP کامل2 هستند[4] و یافتن راهحل بهینه برای این مسائل مستلزم استراتژیهای زمانبندی کارآمدتر است. افزایش سرعت و کارآمدی تنها زمانی قابل حصول خواهد بود که زمانبندی کارها در ماشینها بهطور صحیح و مناسب صورت گیرد زیرا میتواند بهدرستی همسانی سیستم را بکار گیرد. در روشهای کلاسیک، به دست آوردن جوابکاملاً بهینه یا یک زمانبندی کمینه، بسیار زمانگیر است و در بسیاری مواقع، اجرای تصادفی کارها به زمان بیشتری نیاز دارد، بنابراین از روشهای مکاشفهای استفاده میشود، که در روشهای مکاشفه ای لزوماً جواب کاملاً بهینه به دست نمیآید ولی در یک بازه زمانی معقول، جوابی نزدیک به جواب بهینه به دست میآید.
روشهای مکاشفهای بسیاری ارائهشده است که عبارتند از: GA3 [5,6] و 4SA و VS5 [7] و 6ACO و 7BA و TS8 [8] و .PSO9 [9] یکی از کارآمدترین روشهای مکاشفهای، الگوریتم جستجوی گردابی10 است. مطالعه پیشنهادی برحسب عملکرد متفاوت و پارامترهای سرعت نظیر کارآمدی، افزایش سرعت، طول زمانبندی و مدتزمان تکمیل کارها11 با مقاله مطرحشده در [10] مقایسه میشود. بر اساس یافتههای حاصل از آنالیز شبیهسازی گسترده[11,12,13,14]، الگوریتم پیشنهادی از الگوریتمهای قبلی بهطور قابلتوجهی پیشی میگیرد. در ادامه مقاله، ابتدا در بخش 2 به معرفی مسئله زمانبندی پرداختهشده، سپس در بخش 3 الگوریتم جستجوی گردابی و در بخش 4 رویکرد پیشنهادی با بهرهگیری از الگوریتم جستجوی گردابی ارائهشده است. در بخش 5 پیادهسازی و نتایج شبیهسازی شرح داده شده و بخش 6 شامل نتیجهگیری و کارهای آتی میباشد.
مسئله زمانبندی وظایف
هدف یافتن یک زمانبندی بهینه برای اجرای گراف وظایف روی یک ساختار چندپردازندهای میباشد بهطوریکه زمان کل اجرا یعنی زمان پایان آخرین واحد کاری کمینه گردد. فرض بر این است که بین همه پردازندهها یک ارتباط مستقیم وجود دارد و یا به عبارتی توپولوژی اتصال پردازندهها، یک گراف کامل میباشد.[3,6] ورودی مسئله بهصورت گراف جهتدار بدون دور به نام گراف وظایف G= - V,E - نشان داده میشود. هر گره، عضوی از مجموعه V بوده و یک واحد کاری یا وظیفه از برنامه را نشان میدهد بهطوریکه وزن این گرهها مشخصکننده زمان اجرای واحد کاری مربوط خواهد بود.
این گراف همچنین مجموعهای از یالها، یعنی E را در بردارد که بیانگر روابط پیشنیازی بین واحدهای کاری هستند، به این صورت که با داشتن یالی بهصورت - ti,tj - تازمانیکه ti اجرایش را به پایان نرساند، tj نمیتواند اجرایش را آغاز کند. در گراف وظایف، گرههای بدون والد، گره ریشه و گرههای فاقد فرزند، گره برگ نام دارند. شکل - - 1 یکی از پارامترهای بسیار تأثیرگذار در زمانبندی ایستا هزینه اجرای کارها و زودترین زمان شروع کار - - 12EST میباشد که مشخصات مرتبط با گراف شکل - - 1 در جدول - - 1 نمایش دادهشده است.
الگوریتم جستجوی گردابی
الگوریتم ج ستجوی گردابی در سال 2015 تو سط دوگان و اولمز برای حل مسائل بهینه سازی ارائه شد.[7] الگوریتم جستجوی گردابی یک روش غیر جمعیتی است که در هر تکرار از الگوریتم، فضای اطراف بهترین پاسخ یافته شده را با توجه به شعاع، مورد ج ستجو قرار میدهد. سپس شعاع تا نیمه اجرای الگوریتم بهصورت خطی و پسازآن بهصورت غیرخطی کاهش مییابد. بهاینترتیب جستجوی گردابی در ابتدای عملکرد خود دارای رفتار پویشی13 و در انتهای اجرایش رفتاری انتفاعی14 را از خود نشان میدهد.
