ی PDAMS 138
در مرجع ]36[ ، مسئله زمانبندی چندهسته‌ای توان محور139 به دو قسمت زیر تقسیم می‌شود:
توزیع بار 140 بین هسته‌ها
زمانبندی توان محور برای هر هسته
با توجه به همین تقسیم‌بندی، برای هر کدام از این موارد، الگوریتم‌هایی جداگانه پیشنهاد شده است. برای کم‌کردن محدودیت‌ها وساختن یک الگوریتمی که اجرایش راحت‌تر باشد، از دست دادن برخی سررسیدها در این پژوهش اجازه داده شده است. مدلی که در این مقاله پیشنهاد شده، بشرح زیر می‌باشد.
مدل سیستم پیشنهادی مقاله ]36[ :
در این سیستم، یک واحد پردازنده به عنوان مدیر141 و n تا هسته پردازنده به عنوان برده142 ، وجود دارند و هر هسته پردازنده برای خودش یک سیستم‌عامل خاص دارد و می‌تواند به صورت مستقل، فرکانس و ولتاژ عملیاتی خود را تغییر و تنظیم کند. وقتی وظایف در این سیستم توزیع می‌شوند، واحد پردازنده مدیر، اطلاعات هر هسته را بوسیله IPC 143 مبادله می‌کند و سپس این وظایف را بین هسته‌ها توزیع می‌کند. سپس هسته‌ها، وظایفی که به آنها توزیع شده است را به صورت مستقل زمانبندی می‌کنند. تحت این معماری، الگوریتم پیشنهادی این مقاله می‌تواند هم برای سیستم‌های چندهسته‌ای همگن و هم ناهمگن پذیرفته شود و هر هسته پردازنده می‌تواند خودش را مدیریت کند.
ورودی‌های الگوریتم:
یک مجموعه کلی برای همه وظایف در نظر می‌گیریم:
T= { Treal , Tnormal } (12)
Treal مجموعه وظایف بی‌درنگ می‌باشد و Tnormal مجموعه وظایف معمولی است. همچنین هر وظیفه بی‌درنگ دارای مشخصات زیر می‌باشد:
زمان آزادشدن
اولویت
سررسید متناظر
همچنین این وظایف می‌توانند تناوبی یا غیرتناوبی باشند. در محیط های پویا، بدست آوردن همه اطلاعات یک وظیفه مشکل می باشد و همچنین سربار الگوریتم‌های بهینه‌سازی استفاده شده، بسیار سنگین است( هنگامی که هر وظیفه آزاد می شود). بنابراین در این مقاله سعی شده است که بدون در نظر گرفتن زمان اجرای وظایف، وظایف بی‌درنگ را زمانبندی کند.
با اینکه سررسیدهای سخت ضمانت نشده است ولی روش‌هایی که پیشنهاد داده شده تا حد امکان باعث کاهش از دست دادن سررسیدها شده است..
Tnormal فقط از مشخصه‌های اولویت و زمان آزاد شدن تشکیل شده است. در کل، ترتیب اجرای وظایف بی‌درنگ براساس سررسید مطلق وظایف می‌باشد. اولویت وظایف بی‌درنگ فقط وقتی که دو یا چند وظیفه دارای سررسید مطلق یکسانی باشند، استفاده می شود.
خروجی الگوریتم :
خروجی الگوریتم PDAMS، یک مجموعه‌ای از زمانبندی‌های ممکن S که :
S= { S1 , S2 , … , Sn } (13)
که در آن Si عبارت‌انداز نتیجه زمانبندی کردن i اُمین هسته پردازنده برده و فرکانس و ولتاژ عملیاتی تنظیم‌شده که بوسیله الگوریتم پیشنهادی ایجاد شده است.
اهداف مسئله :
برای به حداقل رساندن انرژی مصرفی کل Etotal ، تابع هدف به صورت زیر تعریف می‌شود:
Minimize (Etotal) (14)
Ei =??E_ij (15)
Etotal = ??E_i (16)
که در اینجا، Ei عبارتنداز انرژی مصرفی i اُمین هسته پردازنده برده و Eij عبارت‌اند از، انرژی مصرفی j اُمین وظیفه (وظیفه شماره j )، در هسته شماره i ، که به صورت زیر تعریف می شود:
E_ij=???(p_ijk ?×t_ijk) (17)
p_ijk=c×v_ijk^2׃_ijk (18)
که در اینجا p_ijk عبارت اند از، توان مصرفی وظیفه شماره j در k اُمین برش زمانی144 ، در هسته شماره i . همچنین t_ijk عبارت‌اند از، طول (مدت زمان) k اُمین برش زمانی برای j اُمین وظیفه در i اُمین هسته پردازنده.
از آنجا که مد عملیاتی برای هر وظیفه داده شده، تحت الگوریتم پیشنهادی همیشه یکسان نیست، انرژی مصرفی در هر برش زمانی باید به صورت جداگانه محاسبه شود.
در رابطه قبل، c عبارت‌اند از ظرفیت خازن بار، Vijk ولتاژ عملیاتی و ƒijk فرکانس عملیاتی وظیفه شماره j در k اُمین برش زمانی، در هسته شماره i پردازنده است.
در این مقاله به وظایف اجازه داده می‌شود تا بعداز اتمام سررسیدشان هم اجراشوند تا به اتمام برسند. به علت اینکه بعداز از دست رفتن یک سررسید، سرعت پردازش افزایش می‌یابد، بنابراین آن وظیفه می‌تواند سریع‌تر اجرایش تمام شود.
بنابراین قید کارایی، می‌تواند به صورت زیر بیان شود:
Minimize (??M_i ) (19)
که در آن M_i به این صورت تعریف می‌شود که اگر سررسید i اُمین وظیفه از دست برود مقدار آن یک است و درغیر این صورت صفر است:
M_i={?(1 if f_(t_i )[email protected] OW)? (20)
که در آن f_(t_i ) زمان پایان یافتن وظیفه شماره i و d_i سررسید مطلق آن می‌باشد.شکل 3-12 بلوک دیاگرام مدل این سیستم را نشان می‌دهد.
شکل 3-12 مدل سیستم مرجع ]36[
شکل 15شکل 3-12 مدل سیستم مرجع [36]
الگوریتم پیشنهادی در این مقاله از سه بخش اصلی متفاوت تشکیل می‌شود که عبارت‌انداز:
الگوریتم M-EDF 145
الگوریتم ED3VFS 146
الگوریتم TLDHLB 147
الگوریتم M-EDF برای زمانبندی وظایفی است که به یکی از هسته‌های پردازنده، توزیع شده است. الگوریتم ED3VFS ، نسخه پیشرفته الگوریتم D3VFS 148 است و برای تنظیم مد عملیاتی روی هرهسته پردازنده استفاده می‌شود. در نهایت نیز الگوریتم TLDHLB برای توزیع وظایف بین هسته‌ها استفاده می‌شود ودارای دو سطح می‌باشد:
سطح اول دارای یک استراتژی بارگذاری غیرتعادلی می‌باشد
سطح دوم دارای یک استراتژی بارگذاری تعادلی می‌باشد
برای مثال وقتی، یک وظیفه جدید که نیاز دارد تا توسط یک هسته سرویس داده شود، از راه برسد، الگوریتم TLDHLB آن را با درنظر گرفتن تعادل بارگذاری، به یک هسته مناسب توزیع می‌کند. بعداز اینکه هسته، وظیفه را دریافت کرد، الگوریتم M-EDF ، این وظیفه جدید را زمانبندی می‌کند، همزمان با آن الگوریتم ED3VFS نیز روی این هسته به صورت دوره‌ای اجرا خواهد شد تا انرژی مصرفی را کاهش دهد.
الگوریتم M-EDF :
الگوریتم زمانبندی اصلی که در هسته سیستم عامل میکروسی‌2 149 استفاده شده، یک الگوریتم زمانبندی براساس اولویت بنیادی است. برای اینکه هم وظایف بی‌درنگ و هم وظایف معمولی را همزمان پوشش دهد، الگوریتم M-EDF به عنوان جایگزینی برای الگوریتم EDF انتخاب شده است. در واقع M-EDF ترکیبی از EDF و زمانبندی اولویت ثابت150 می‌باشد. برای وظایف بی‌درنگ از الگوریتم EDF استفاده شده است. هنگامی که دو یا چند وظیفه بی‌درنگ دارای سررسید برابری باشند یا برای وظایف معمولی، M-EDF از الگوریتم زمانبندی اولویت ثابت برای مشخص کردن ترتیب اجرای وظایف استفاده می‌کند.
در واقع اگر همزمان یک وظیفه بی‌درنگ و یک وظیفه معمولی در صف آماده باشند، M-EDF وظیفه بی‌درنگ را برای اجرا انتخاب می‌کند. برای مشارکت و همکاری کردن با الگوریتم TLDHLB برای ذخیره توان ایستا، در اینجا M-EDF طوری تغییر داده شده است که وقتی یک وظیفه دارای بالاترین اولویت، در حالت بیکار باشد و هیچ وظیفه دیگری برای اجرا نباشد، بتواند هسته پردازنده را خاموش کند. یعنی وقتی هسته پردازنده، همه وظایف را به اتمام رساند، خودش را خاموش خواهدکرد تا انرژی کمتری مصرف شود.
الگوریتم ED3VFS :
این الگوریتم برای تنظیم کردن فرکانس و ولتاژ پردازنده، به صورت پویا استفاده می‌شود. در این الگوریتم دو پارامتر با نام‌های ? و ? وجود دارند که این دو پارامتر در الگوریتم D3VFS به صورت پیش‌فرض روی عدد 10 تنظیم می‌شوند و به صورت زیر تعریف می‌شوند:
? : هرگاه وظیفه‌ای به اندازه ? واحد زمانی اجرایش طول کشید ولی تمام نشد و همچنان پردازنده در حال اجرای آن بود، الگوریتم D3VFS اجرا می‌شود تا فرکانس و ولتاژ را بالاتر ببرد و سرعت سیستم زیاد شود تا بهره‌وری بیشتر شود( ولی مصرف انرژی نیز افزایش می‌یابد)
? : هرگاه به اندازه ? واحد زمانی، هیچ وظیفه‌ای، سررسیدش را از دست ندهد، آنگاه این الگوریتم اجرا می‌شود تا فرکانس و ولتاژ را کم کند تا انرژی مصرفی کاهش یابد. ( ? بزرگتر باعث افزایش انرژی مصرفی و افزایش سرعت می‌شود)
در این مقاله با الهام بخشیدن از D3VFS ، یک روش بهتری برای تنظیم پارامترهای ? و ? ، پیشنهاد شده است تا بتواند کارایی سیستم زمانبندی را بهبود دهد. سه اشکال موجود در D3VFS عبارت انداز:
در D3VFS ، سررسید مربوط به وظایف، نیازی ندارد که بیشتر از 10 یا یک مقدار آستانه ثابتی باشد. هنگامی که کوتاه‌ترین سررسید کمتر از 10 باشد، ? و ? منفی می‌شوند، که باید اصلاح شود.
لزومی ندارد که ? و ? حتما باهم برابر باشند، زیرا اثرات آن‌ها باهم متفاوت است. در الگوریتم ED3VFS ، مقدار ? بزرگتر درنظر گرفته شده تا زمان بیشتری پردازنده در سرعت پایین بماند، زیرا سیستم در سرعت‌های آهسته‌تر، فرکانس عملیاتی را افزایش خواهد داد. این باعث می‌شود تا مقدار توان ذخیره شده بیشتر شود (یعنی هرچقدر بتوانیم سرعت سیستم را آهسته نگه داریم، انرژی بیشتری را ذخیره کرده‌ایم). از سوی دیگر ? برای کاهش فرکانس عملیاتی استفاده می‌شود، هرچقدر ? بزرگتر باشد، باعث می‌شود که سیستم برای مدت طولانی در سرعت بالا بماند، بنابراین باعث می‌شود که بهره‌وری بهتر شود اما توان بیشتری را مصرف می‌کند.
معمولاً در یک سیستم بیشتر از یک وظیفه همزمان در حال کار هستند و در محیط‌های واقعی این وظایف همیشه شبیه هم نیستند. بهترین تنظیمات برای هر وظیفه این است که متفاوت باشد، بنابراین دادن تنظیمات متفاوت برای مجموعه وظایف متفاوت انعطاف‌پذیرتر است.
برای حل این مشکلات بالا، در این مقاله یک روش متفاوتی برای بهبود کارایی و بهترشدن الگوریتم ذخیره توان پیشنهاد شده است. شبه کد این الگوریتم در شکل 3-13 نشان داده شده است.
ایده اصلی الگوریتم ED3VFS این است که تنظیمات ? و ? آزادانه تغییر داده می‌شود، در واقع با تغییر مجموعه وظایف، این دو پارامتر، دو مقدار متفاوت دارند.
در الگوریتم ED3VFS ، پارامترهای ? و ? به صورت زیر مقداردهی می‌شوند:
?={?((0.2D_sr)¦(0.4D_sr )@(0.6D_sr)¦(0.8D_sr ))? (21)
?=D_sr-? (22)
که در آن D_sr عبارت انداز کوتاه‌‌ترین سررسید مربوط به وظیفه‌ها.
همانطور که مشاهده می‌کنید در اینجا اثر ? و ? ، عکس هم درنظر گرفته شده است. نتایج آزمایشات مقایسه بین ED3VFS و D3VFS نشان داد که انرژی مصرفی ED3VFS در ?=0.2D_sr ,0.6D_sr ,0.8D_sr کمتر از D3VFS بوده است. همچنین از دست دادن سررسیدها نیز در ?=0.2D_sr

این مطلب رو هم توصیه می کنم بخونین:   منابع تحقیق با موضوعآموزش و پرورش، نهج البلاغه، حوزه و دانشگاه
دسته‌ها: No category

دیدگاهتان را بنویسید