(۲۲)
که در آن عبارت انداز کوتاه‌‌ترین سررسید مربوط به وظیفه‌ها.
همانطور که مشاهده می‌کنید در اینجا اثر α و β ، عکس هم درنظر گرفته شده است. نتایج آزمایشات مقایسه بین ED³VFS و D³VFS نشان داد که انرژی مصرفی ED³VFS در β=۰٫۲ کمتر از D³VFS بوده است. همچنین از دست دادن سررسیدها نیز در β=۰٫۲ ، صفر بوده است، یعنی هیچ سررسیدی از دست نرفته است. در β=۰٫۶ نیز کمتر از D³VFS، سررسید از دست داده شد، یعنی با این تنظیمات جدید در ED³VFS، هم انرژی کمتر و هم بهره‌وری بیشتر( از دست دادن سررسید کمتر) اتفاق افتاده است.
بهترین حالتی که هم انرژی کمتری مصرف شده و هم سررسید کمتری از دست برود به این صورت شد که اگر وظایف ما بی‌درنگ سخت باشد:
β= ۰٫۲D_sr , α= ۰٫۸D_sr (۲۳)
و اگر بی‌درنگ نرم باشد :
β= ۰٫۶D_sr , α= ۰٫۴D_sr (۲۴)
(۱) Initially setting the power mode of DSP to default level f_d .
(۲) Every timer interrupt occur
(۳) if (There is any real time task)
(۴) Setting α = D_sr × ۰٫۲
(۵) Setting β = D_sr - α
(۶) if (Deadline missed)
(۷) Extending deadline of the task that missed deadline for d_e ticks.
(۸) Rising power mode.
(۹) else if (Utilization of DSP > S_r for α ticks)
(۱۰) Rising power mode
(۱۱) else if (There is no deadline missed for β ticks)
(۱۲) Falling power mode
(۱۳) else
(۱۴) setting the power mode of DSP to deadline level f_d
(۱۵) endif
شکل ۳-۱۳ شبه کد الگوریتم ED³VFS ]36[
الگوریتم TLDHLB : شکل ۱۶شکل ۳-۱۳ شبه کد الگوریتم ED3VFS [36]
برای سیستم‌هایی که دارای محدودیت توان باطری هستند، این ایده که اجازه دهیم همه‌ هسته‌های پردازنده همواره در حالت فعال باشند، ایده خوبی نیست، زیرا باعث می‌شود انرژی زیادی مصرف شود. در یک سیستم چندهسته‌ای، متعادل کردن حجم‌کار بین هسته‌‌ها، می‌تواند زمان اتمام کل همه وظایف را کاهش دهد، یعنی هسته‌های پردازنده می‌توانند برای مدت بیشتری به حالت خواب^[۱۵۱] بروند و انرژی بیشتری را ذخیره کنند.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

در سطح اول این الگوریتم دو سطحی، از یک استراتژی بارگذاری غیرتعادلی برای ذخیره توان ایستا استفاده شده است. ایده اصلی در این استراتژی توزیع بار، عبارت انداز:
توزیع وظایف به هسته‌هایی از پردازنده که در حالت فعال هستند و خاموش کردن هسته‌ها، وقتی که همه وظایف موجود در صف آن هسته به اتمام برسند.
برای مثال فرض کنید یک واحد پردازنده مدیر داریم و دو هسته تحت نظر آن قرار دارند. همانطور که در شکل ۳-۱۴ مشاهده می‌شود، در ابتدا که هیچ وظیفه‌ای وجود ندارد، هر دو هسته خاموش هستند. وقتی وظیفه T₁ آزاد می‌شود، پردازنده مدیر وضعیت هسته‌ها را چک می‌کند، اگر هیچ کدام از هسته‌ها در حالت فعال نبودند، هسته شماره ۱ را روشن می‌کند و T₁ را به آن اختصاص می‌دهد. براساس ED³VFS، هسته شماره ۱ ، در سرعت پیش فرض کار خواهد کرد که معمولا در کمترین سرعت خود قرار دارد. در ادامه که چند وظیفه دیگر که به سیستم اضافه می‌شود، پردازنده مدیر آنها را به هسته‌ای می‌فرستد که فعال باشد و در بالاترین فرکانس خود نباشد. پس از مدتی که سرعت هسته شماره ۱ به حداکثر خود رسید، حال اگر T_n آزاد شود، پردازنده مدیر آن را به هسته شماره ۲ که خاموش بوده ارسال می‌کند. وقتی که هسته شماره ۱ تمام وظایف خود را به پایان رساند، این هسته خودش را به وسیله الگوریتم MEDF، خاموش می‌کند.

شکل ۳-۱۴ مثالی از بارگذاری غیرتعادلی – a : حالت آغازین –b : وظیفه t₁ آزاد شده و هسته ۱ شده است- c : زمانی که هسته ۱ در حالت حداکثر فرکانس کار می‌کند،وظیفهn آزاد شده و در نتیجه هسته۲ روشن شده و وظیفهn به آن اختصاص میابد – d : هسته ۱ اجرای همه وظایفی که به آن اختصاص داده شده بود را تمام می‌کند و خودش را خاموش می‌کند. ]۳۶[
شکل ۱۷شکل ۳-۱۴ مثالی از بارگذاری غیرتعادلی
در لایه دوم این الگوریتم، یک استراتژی بارگذاری تعادلی وجود دارد. وقتی که دو یا چند هسته در حال کار در حالت فعال باشند، استراتژی بارگذاری تعادلی در سطح دوم، وظایف جدید آزادشده را توزیع خواهد کرد. برخلاف روش‌های سنتی که شامل وظایف بی‌درنگ نمی‌شدند، در این سیستم به صورت همزمان هم وظایف معمولی و هم وظایف بی‌درنگ در نظر گرفته شده است. استراتژی بارگذاری سنتی، برای سیستم‌های بی‌درنگ طراحی نشده است، بنابراین در این مقاله یک معیار توزیع جدیدی پیشنهاد شده که مشکل توزیع وظایف بی‌درنگ را حل می‌کند.
این استراتژی جدید، از سررسید وظایف به عنوان یک معیار برای بارگذاری تعادلی استفاده می‌کند. هرچقدر بتوانیم وظایف را بر اساس سررسیدشان، یکنواخت‌تر توزیع کنیم، احتمال از دست دادن سررسید کمتری خواهیم داشت. شکل۳-۱۵ یک مثال ساده از این موضوع است که در آن دو هسته و چهار وظیفه وجود دارند. این مثال نشان می‌دهد که نتیجه یکی از دو توزیع وظایف، به شکست منجر می شود. در شکل ۳-۱۵ الف ، وظیفه۱ در سررسید d₁ به اتمام می‌رسد، بنابراین برای اجرای وظیفه ۲ به اندازه کافی زمان وجود ندارد و در نتیجه سررسید آن از دست میرود. برای وظیفه ۴ نیز در هسته ۲ ، همین شرایط وجود دارد. در شکل ۳-۱۵ ب ، از یک توزیع متفاوتی استفاده شده است که نتیجه آن اجرای به موقع وظایف و از دست نرفتن سررسیدهای آنان می‌باشد. در این حالت، برش زمانی^[۱۵۲] بین دو سررسید، طولانی‌تر است که این بدین معنی است که زمان بیشتری برای اجرای وظیفه بعدی وجود دارد، در نتیجه احتمال از دست رفتن سررسید کاهش می‌یابد.
شکل۳-۱۵ مثالی از توزیع وظایف بی‌درنگ؛ الف) توزیع ناجور وظایف؛ ب) توزیع مناسب وظایف ]۳۶[
شکل ۱۸شکل۳-۱۵ مثالی از توزیع وظایف بی‌درنگ
در این ایده، از پارامتر واریانس سررسید هر وظیفه، به عنوان یک معیار برای توزیع سررسید استفاده شده‌ است. از آنجایی که واریانس، چگونگی توزیع یک مجموعه از اعداد را شرح می‌دهد، در نتیجه واریانس می‌تواند به عنوان بیان کننده تراکم توزیع داده‌ها استفاده شود.
یک واریانس کوچک از سررسید یک وظیفه، نشان می‌دهد که فاصله زمانی بین دو سررسید، کوتاه است. معادله زیر فرمول محاسبه واریانس را نشان می‌دهد:
(۲۵)
که در آن N تعداد داده‌ها، ، داده شماره i و میانگین داده‌هاست.
غیراز این توزیع وظایف براساس سررسید، از سه استراتژی دیگر نیز برای توزیع وظایف معمولی، استفاده شده است. این سه استراتژی همچنین برای وظایف بی‌درنگی که یکنواختی توزیع سررسیدشان باهم برابر است نیز استفاده می‌شود.
استراتژی اول، به ترتیب اجرای وظایف در هر هسته مربوط می‌شود، به این معنی که، توزیع کننده، یک وظیفه را به هسته‌ای می‌فرستد که بالاترین اولویت را به آن وظیفه بدهد. برای مثال فرض کنید که دو هسته و دو وظیفه روی هر هسته داشته باشیم. حال وقتی یک وظیفه جدید آزاد می‌شود، اگر اولویت اجرای این وظیفه، در هسته شماره ۱، دومین باشد (یعنی اگر این وظیفه را به هسته اول بفرستیم، زمانبندی که هسته اول با توجه به وظایف موجود در صف خود، انجام می‌دهد، به این صورت می‌باشد که این وظیفه، دومین وظیفه‌ برای اجرا است) و در هسته شماره ۲، سومین اولویت را داشته باشد، این وظیفه به هسته اول فرستاده می‌شود.
دومین استراتژی، به تعداد وظایف موجود در صف هر هسته توجه می‌کند. به این معنی که توزیع‌کننده، وظیفه جدید را به هسته‌ای می‌فرستد که کمترین تعداد وظیفه در آن باشد.
وقتی توزیع‌کننده نتوانست با این استراتژی‌ها، تصمیم بگیرد که وظیفه را به کدام هسته بفرستد، آنگاه از آخرین استراتژی استفاده خواهد شد. این استراتژی بسیار ساده می‌باشد، به این صورت که ، توزیع‌کننده هسته‌ای را انتخاب می‌کند که شماره سریال کوچکتری داشته باشد و همچنین در حالت فعال قرار داشته باشد. شبه کد این الگوریتم را به صورت کامل در شکل ۳-۱۶ مشاهده می‌کنید.
همانطور که در این شبه‌کد مشاهده می‌کنید، پس از بررسی وضعیت هسته‌ها توسط پردازنده مدیر، در سطح اول الگوریتم توزیع ابتدا بررسی می شود که اگر همه هسته‌ها خاموش بودند، هسته‌ای که شماره سریال کمتری دارد، وظیفه به آن اختصاص میابد. در غیر این صورت اگر چند هسته روشن و در حداکثر فرکانس درحال کار بودند و چند هسته خاموش بودند، آنگاه یکی از هسته‌های خاموش انتخاب شده و وظیفه به آن اختصاص می یابد. اگر همه هسته‌ها روشن باشند و یکی از هسته‌های روشن در حداکثر فرکانس خود کار نکند، وظیفه به آن ارسال می‌شود، اما اگر هیچ‌کدام از حالت‌های ذکر شده برقرار نشد، وارد سطح دوم الگوریتم شده و هسته‌ای که واریانس سررسید آن کمتر باشد توسط تابع maxuniformity() انتخاب می‌شود، و اگر حداقل دو هسته واریانس سررسید برابری داشتند، توسط تابع minorder() هسته‌ای انتخاب می‌شود که اگر وظیفه در صف آن قرار گیرد، زودتر اجرا می شود. اگر باز هم دو هسته وجود داشتند که شرایط یکسانی داشتند، تابع mintaskNum() وظایف را به هسته‌ای کمترین تعداد وظایف را در صف خود دارد می‌فرستد. اگر دو صف با تعداد وظایف برابر وجود داشت، توسط تابع minSerial() وظیفه به هسته‌ای که شماره سریال کمتری دارد ارسال می شود.
مزایا و معایب این الگوریتم:
این الگوریتم یکی از بهترین الگوریتم‌های توزیع وظایف در سیستم‌های چندهسته‌ای می‌باشد که با یک توزیع بار حساب شده بین هسته‌ها، توانسته نرخ نقض سررسید وظایف را بخوبی کاهش داده و همچنین بهره‌وری و کارایی سیستم را بسیار بهبود ببخشد. همچنین با یک الگوریتم تنظیم ولتاژ و فرکانس سررسید محور مناسب، توانسته انرژی مصرفی را با در نظرگرفتن سررسید وظایف، تا حد زیادی کاهش دهد.
از جمله معایب این الگوریتم، که ما آن‌ ها را در الگوریتم پیشنهادی خود بهبود داده‌ایم این است که این الگوریتم، بدون توجه نوع وظایف بی‌درنگ و ماهیت آن‌ ها، آن‌ ها را بین هسته‌ها توزیع کرده است که این مسئله تا حد زیادی می‌تواند روی انرژی مصرفی سیستم و همچنین زمان پاسخ وظایف، تاثیر منفی بگذارد. در واقع این الگوریتم هیچ تمایزی از لحاظ تناوبی و غیرتناوبی بودن وظایف بی‌درنگ، قائل نیست و این مسئله می‌تواند زمان پاسخ وظایف غیرتناوبی را افزایش دهد. همچنین عیب دیگر این الگوریتم، بالا بودن پیچیدگی و محاسبات زیاد آن، برای توزیع و زمانبندی اجرای وظایف است و همچنین الگوریتم تنظیم فرکانس و ولتاژ سررسید محور آن، دارای دو پارامتر کنترل‌کننده است که این موضوع باعث سوئیچ زیاد بین سطوح مختلف فرکانسی پردازنده خواهد شد وسربار الگوریتم را نیز افزایش می‌دهد.
(۱) Initialy turning off all of DSP’s , DSP_off = DSP_all
(۲) When a task that need be processd by DSP is released