وبلاگ

که در آن Si عبارت‌انداز نتیجه زمانبندی کردن i اُمین هسته پردازنده برده و فرکانس و ولتاژ عملیاتی تنظیم‌شده که بوسیله الگوریتم پیشنهادی ایجاد شده است. اهداف مسئله : برای به حداقل رساندن انرژی مصرفی کل Etotal ، تابع هدف به صورت زیر تعریف می‌شود: Minimize (Etotal) (14) Ei = (۱۵) Etotal = (۱۶) که در اینجا، Ei عبارتنداز انرژی مصرفی i اُمین هسته پردازنده برده و Eij عبارت‌اند از، انرژی مصرفی j اُمین وظیفه (وظیفه شماره j )، در هسته شماره i ، که به صورت زیر تعریف می شود: (۱۷) (۱۸) که در اینجا عبارت اند از، توان مصرفی وظیفه شماره j در k اُمین برش زمانی[۱۴۴] ، در هسته شماره i . همچنین عبارت‌اند از، طول (مدت زمان) k اُمین برش زمانی برای j اُمین وظیفه در i اُمین هسته پردازنده. از آنجا که مد عملیاتی برای هر وظیفه داده شده، تحت الگوریتم پیشنهادی همیشه یکسان نیست، انرژی مصرفی در هر برش زمانی باید به صورت جداگانه محاسبه شود. در رابطه قبل، c عبارت‌اند از ظرفیت خازن بار، Vijk ولتاژ عملیاتی و ƒijk فرکانس عملیاتی وظیفه شماره j در k اُمین برش زمانی، در هسته شماره i پردازنده است. در این مقاله به وظایف اجازه داده می‌شود تا بعداز اتمام سررسیدشان هم اجراشوند تا به اتمام برسند. به علت اینکه بعداز از دست رفتن یک سررسید، سرعت پردازش افزایش می‌یابد، بنابراین آن وظیفه می‌تواند سریع‌تر اجرایش تمام شود. بنابراین قید کارایی، می‌تواند به صورت زیر بیان شود: (۱۹) که در آن به این صورت تعریف می‌شود که اگر سررسید i اُمین وظیفه از دست برود مقدار آن یک است و درغیر این صورت صفر است: (۲۰) که در آن زمان پایان یافتن وظیفه شماره i و سررسید مطلق آن می‌باشد.شکل ۳-۱۲ بلوک دیاگرام مدل این سیستم را نشان می‌دهد. شکل ۳-۱۲ مدل سیستم مرجع ]۳۶[ شکل ۱۵شکل ۳-۱۲ مدل سیستم مرجع [۳۶] الگوریتم پیشنهادی در این مقاله از سه بخش اصلی متفاوت تشکیل می‌شود که عبارت‌انداز: الگوریتم M-EDF [۱۴۵] الگوریتم ED3VFS [۱۴۶] الگوریتم TLDHLB [۱۴۷] الگوریتم M-EDF برای زمانبندی وظایفی است که به یکی از هسته‌های پردازنده، توزیع شده است. الگوریتم ED3VFS ، نسخه پیشرفته الگوریتم D3VFS [۱۴۸] است و برای تنظیم مد عملیاتی روی هرهسته پردازنده استفاده می‌شود. در نهایت نیز الگوریتم TLDHLB برای توزیع وظایف بین هسته‌ها استفاده می‌شود ودارای دو سطح می‌باشد: سطح اول دارای یک استراتژی بارگذاری غیرتعادلی می‌باشد سطح دوم دارای یک استراتژی بارگذاری تعادلی می‌باشد برای مثال وقتی، یک وظیفه جدید که نیاز دارد تا توسط یک هسته سرویس داده شود، از راه برسد، الگوریتم TLDHLB آن را با درنظر گرفتن تعادل بارگذاری، به یک هسته مناسب توزیع می‌کند. بعداز اینکه هسته، وظیفه را دریافت کرد، الگوریتم M-EDF ، این وظیفه جدید را زمانبندی می‌کند، همزمان با آن الگوریتم ED3VFS نیز روی این هسته به صورت دوره‌ای اجرا خواهد شد تا انرژی مصرفی را کاهش دهد. الگوریتم M-EDF : الگوریتم زمانبندی اصلی که در هسته سیستم عامل میکروسی‌۲ [۱۴۹] استفاده شده، یک الگوریتم زمانبندی براساس اولویت بنیادی است. برای اینکه هم وظایف بی‌درنگ و هم وظایف معمولی را همزمان پوشش دهد، الگوریتم M-EDF به عنوان جایگزینی برای الگوریتم EDF انتخاب شده است. در واقع M-EDF ترکیبی از EDF و زمانبندی اولویت ثابت[۱۵۰] می‌باشد. برای وظایف بی‌درنگ از الگوریتم EDF استفاده شده است. هنگامی که دو یا چند وظیفه بی‌درنگ دارای سررسید برابری باشند یا برای وظایف معمولی، M-EDF از الگوریتم زمانبندی اولویت ثابت برای مشخص کردن ترتیب اجرای وظایف استفاده می‌کند. در واقع اگر همزمان یک وظیفه بی‌درنگ و یک وظیفه معمولی در صف آماده باشند، M-EDF وظیفه بی‌درنگ را برای اجرا انتخاب می‌کند. برای مشارکت و همکاری کردن با الگوریتم TLDHLB برای ذخیره توان ایستا، در اینجا M-EDF طوری تغییر داده شده است که وقتی یک وظیفه دارای بالاترین اولویت، در حالت بیکار باشد و هیچ وظیفه دیگری برای اجرا نباشد، بتواند هسته پردازنده را خاموش کند. یعنی وقتی هسته پردازنده، همه وظایف را به اتمام رساند، خودش را خاموش خواهدکرد تا انرژی کمتری مصرف شود. الگوریتم ED3VFS : این الگوریتم برای تنظیم کردن فرکانس و ولتاژ پردازنده، به صورت پویا استفاده می‌شود. در این الگوریتم دو پارامتر با نام‌های α و β وجود دارند که این دو پارامتر در الگوریتم D3VFS به صورت پیش‌فرض روی عدد ۱۰ تنظیم می‌شوند و به صورت زیر تعریف می‌شوند: α : هرگاه وظیفه‌ای به اندازه α واحد زمانی اجرایش طول کشید ولی تمام نشد و همچنان پردازنده در حال اجرای آن بود، الگوریتم D3VFS اجرا می‌شود تا فرکانس و ولتاژ را بالاتر ببرد و سرعت سیستم زیاد شود تا بهره‌وری بیشتر شود( ولی مصرف انرژی نیز افزایش می‌یابد) β : هرگاه به اندازه β واحد زمانی، هیچ وظیفه‌ای، سررسیدش را از دست ندهد، آنگاه این الگوریتم اجرا می‌شود تا فرکانس و ولتاژ را کم کند تا انرژی مصرفی کاهش یابد. ( β بزرگتر باعث افزایش انرژی مصرفی و افزایش سرعت می‌شود) در این مقاله با الهام بخشیدن از D3VFS ، یک روش بهتری برای تنظیم پارامترهای α و β ، پیشنهاد شده است تا بتواند کارایی سیستم زمانبندی را بهبود دهد. سه اشکال موجود در D3VFS عبارت انداز: در D3VFS ، سررسید مربوط به وظایف، نیازی ندارد که بیشتر از ۱۰ یا یک مقدار آستانه ثابتی باشد. هنگامی که کوتاه‌ترین سررسید کمتر از ۱۰ باشد، α و β منفی می‌شوند، که باید اصلاح شود. لزومی ندارد که α و β حتما باهم برابر باشند، زیرا اثرات آن‌ها باهم متفاوت است. در الگوریتم ED3VFS ، مقدار α بزرگتر درنظر گرفته شده تا زمان بیشتری پردازنده در سرعت پایین بماند، زیرا سیستم در سرعت‌های آهسته‌تر، فرکانس عملیاتی را افزایش خواهد داد. این باعث می‌شود تا مقدار توان ذخیره شده بیشتر شود (یعنی هرچقدر بتوانیم سرعت سیستم را آهسته نگه داریم، انرژی بیشتری را ذخیره کرده‌ایم). از سوی دیگر β برای کاهش فرکانس عملیاتی استفاده می‌شود، هرچقدر β بزرگتر باشد، باعث می‌شود که سیستم برای مدت طولانی در سرعت بالا بماند، بنابراین باعث می‌شود که بهره‌وری بهتر شود اما توان بیشتری را مصرف می‌کند. معمولاً در یک سیستم بیشتر از یک وظیفه همزمان در حال کار هستند و در محیط‌های واقعی این وظایف همیشه شبیه هم نیستند. بهترین تنظیمات برای هر وظیفه این است که متفاوت باشد، بنابراین دادن تنظیمات متفاوت برای مجموعه وظایف متفاوت انعطاف‌پذیرتر است. برای حل این مشکلات بالا، در این مقاله یک روش متفاوتی برای بهبود کارایی و بهترشدن الگوریتم ذخیره توان پیشنهاد شده است. شبه کد این الگوریتم در شکل ۳-۱۳ نشان داده شده است. ایده اصلی الگوریتم ED3VFS این است که تنظیمات α و β آزادانه تغییر داده می‌شود، در واقع با تغییر مجموعه وظایف، این دو پارامتر، دو مقدار متفاوت دارند. در الگوریتم ED3VFS ، پارامترهای α و β به صورت زیر مقداردهی می‌شوند: (۲۱)