پایان نامه رایگان درمورد انرژی مصرفی، الگوریتم زمانبندی، قابلیت اعتماد

دانلود پایان نامه ارشد

زمایش این مقاله که از پردازنده ARM11MPcore استفاده شده، دارای 4 حافظه نهان L1 32 کیلوبایتی و یک حافظه نهان L2 یک مگابایتی است.
برای وظایف غیرتناوبی از الگوریتم‌های دیگری استفاده شده است که یکی برای زمانبندی درون‌هسته‌ای132 و دیگری برای زمانبندی بین‌هسته‌ای133 استفاده می‌شود. برای زمانبندی درون‌هسته‌ای در اینجا از الگوریتم SQ استفاده شده است که به این معنی است که وقتی یک وظیفه جدید بوجود آمد، آن را به هسته‌ای می فرستد که دارای کوتاه ترین صف وظایف درحال انتظار برای اجرا باشد. در واقع وظایف غیرتناوبی تا حد امکان به صورت مساوی بین هسته‌ها توزیع می‌شوند. اما برای زمانبندی بین‌هسته‌ای از سیاست FCFS 134 استفاده می‌شود.

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

3-6-2 الگوريتم زمانبندی غيرتعادلی جزبندی با RBound
در مرجع ]35[ نیز همانند مرجع ]34[ از یک روش بارگذاری غیرتعادلی استفاده شده است که روی وظایف تناوبی و غیرتناوبی در سیستم‌های تعبیه‌شده بی‌درنگ چندهسته‌ای سخت، برای کاهش مصرف توان اعمال می‌شود. در این مقاله از یک معماری زمانبندی دو سطحی استفاده شده است که در سطح بالایی وظایف تناوبی بوسیله الگوریتم RBound-FF که این الگوریتم در قسمت بعدی توضیح داده خواهد شد، به تعداد محدودی از هسته‌ها فرستاده می‌شوند و وظایف غیرتناوبی به هسته‌های باقیمانده ارسال می‌شوند. اما در سطح پایینی این طرح زمانبندی، از دو زمانبند استفاده شده است، یکی برای وظایف تناوبی و دیگری برای وظایف غیر تناوبی. برای وظایف تناوبی از الگوریتم RMS استفاده شده و برای وظایف غیرتناوبی، الگوریتم DMS 135 بکار برده شده است. مشخصه‌هایی که برای یک وظیفه در این مقاله استفاده شده عبارت‌انداز:
Ti : دوره تناوب وظیفه تناوبی i
Ci : بدترین حالت زمان اجرای یک وظیفه تناوبی
Pi : اولویت هر وظیفه تناوبی که برابر است با 1/T_i و برای وظایف غیرتناوبی برابر است با 1/D_i
RMS : الگوریتم زمانبندی نرخ یکنواخت که برای زمانبندی وظایف تناوبی استفاده شده است.
Ai : زمان ورود یک وظیفه غیر تناوبی
Di : سررسید هر وظیفه
DMS : الگوریتم زمانبندی سررسید یکنواخت
در هر دو حالت تناوبی و غیرتناوبی، وظایف قابل دسترسی که اولویت بالاتری داشته باشند، پردازش می‌شوند.
الگوريتم RBound-FF :
Rbound یک شرایط قابل زمانبندی تک پردازنده‌ای برای RMS است، که با استفاده از دوره‌تناوب وظایف تناوبی، بهره‌وری بالایی برای پردازنده ایجاد می‌کند. مجموعه وظایف ورودی T با m وظیفه، بوسیله Rbound شدن، مطابق الگوریتم scale task set که در شکل 3-9 آورده‌شده است، تبدیل به مجموعه T’ می‌شود. این الگوریتم، مجموعه وظایفی را پیدا می‌کند که نسبت حداکثر و حداقل دوره تناوب‌هایش، کمتر از 2 باشد. در واقع یک اجازه‌ای بر اساس Rbound برای T’ صادر می‌شود. R را به عنوان نسبت کمترین به بیشترین دوره تناوب بین همه وظایف در سیستم تعریف می‌کنیم. بنابراین با r<2 در پایان الگوریتم برای m وظیفه داریم:
(6) -1) + 2/(r-1) URbound (r,m) = (m-1)( r^(1/(m-1))
Rbound می‌گوید که اگر T’ خروجی الگوریتم ScaleTaskSet باشد و عبارت
(7) ≤ URbound (r,m) ∑▒〖Ci/Ti〗
برقرار باشد(r=Tm’/T1′ )، آنگاه T یک مجموعه وظیفه قابل زمانبندی روی یک تک پردازنده بوسیله RMS است.
Scale TaskSet(Input: T)
Begin
Sort the tasks in T by increasing period
While T1 ≤ Tm /2
Ci = 2 Ci
Ti = 2 Ti
Sort the task in T by increasing period
End while
∀ i, T_i^’=T_i; C_i^’=C_i;
Return (T’)
end
شکل 12شکل 3-9 الگوریتم ScaleTaskSet [35]
جزبندی با Rbound :
بیشتر الگوریتم‌های پیشنهاد شده با RMS اولویت‌دار، براساس جزبندی‌کردن هستند، بنابراین زمانبندی عمومی با RMS اولویت‌دار می‌تواند بازده کمی در بدترین حالت روی بهره‌وری پردازنده داشته باشد. استراتژی جزبندی شامل دو قسمت زیر است:
تخصیص دادن وظایف به هسته‌ها
زمانبندی وظایف روی هر پردازنده
در الگوریتم RBound ، زمانی که r مربوط به هر وظیفه، به عدد 1 نزدیک می‌شود، این نوع وظایف به هسته یکسانی فرستاده می‌شوند، در نتیجه بهره‌وری پردازنده به 100 درصد می‌رسد (صرف نظر از تعداد وظایف). برای نزدیک شدن r به 1 باید وظایفی که نزدیک‌ترین دوره تناوب را دارند، در مجموعه وظایف مندرج شده T’ قرار داد شوند و این کار با مرتب‌کردن وظایف در T’ براساس افزایش دوره تناوب و سپس فرستادن وظایف به پردازنده با روش‌های Next-Fit و یا First-Fit امکان‌پذیر می‌باشد. در اینجا برای وظایف تناوبی از روش First-Fit استفاده شده است، زیرا First-Fit به خاطر جستجو در یک مجموعه جهانی136 از بین پردازنده‌های جستجو شده بوسیله Next-Fit ، بهتر از Next-Fit عمل می‌کند. در سیستم‌هایی با وظایف تناوبی، عمل تخصیص وظایف، زمانی اتفاق می‌افتد که یک وظیفه جدیدی بوجود می آید. به هر حال RBound-FF وقتی که مجموعه وظایف تناوبی سیستم، بر اساس دوره تناوب، مرتب شوند، می‌تواند بیشترین بهره‌وری پردازنده را به ما بدهد. بنابراین در اینجا فقط وظایف تناوبی، در مرحله مقداردهی اولیه وظیفه، به هسته‌های مناسب محدود می‌شوند و سپس وقتی که این وظایف به طور کامل ایجاد شدند، به هسته‌ها اختصاص می‌یابند.

RBound-FF_init(Input: T,p)
Begin
ScaleTaskSet(T , T’)
For (i=1 ; i≤m ,i++)
For (j=1 ; j≤pn ; j++)
If ( τi can be admitted by Rbound an pj )
Bound τi to pj
Else
If (j== pn) return(REJECT)
Endif
Endfor
Endfor
Return(ACCEPT)
end
شکل 3-10 شبه کد الگوریتم RBound-FF ]35[
شکل 13شکل 3-10 شبه کد الگوریتم RBound-FF [35]
بهره‌وری RBound برای وظايف غيرتناوبی:
برای وظایف غیرتناوبی، مجموعه V(t) به عنوان مجموعه همه وظایف درگیری که وارد شده‌اند، اما سررسیدشان سپری نشده است، به صورت زیر تعریف می‌شوند:
V(t) = { Ti | Ai ≤ t < Ai + Di } (8)
S(t) که زیرمجموعه V(t) است، شامل فقط وظایفی در V(t) است که بعداز شروع آخرین دوره تناوب زمان بیکاری پردازنده، وارد شوند. و در نهایت می‌رسیم به تعریف بهره‌وری ترکیبی که عبارت انداز:
u(t)=∑_(Ti ∈s(t))▒C_i/D_i (9)
یک مجموعه از n وظیفه غیرتناوبی، بوسیله سیاست زمانبندی DMS ، قابل زمانبندی است هرگاه :
∀ t :U(t)≤UB(n) (10)
که UB(n) به صورت زیر تعریف می‌شود:
UB(n)={█(1/2+1/2n for n<3@1/(1+√(1/2(1-1/(n-1)))) for n≥3)┤ (11)
معماری زمانبندی الگوريتم مرجع ]35[ :
می‌دانیم که وظایف تناوبی در سیستم‌های تعبیه‌شده، دائم در حال تکرار شدن اجرایشان هستند، تا زمانیکه پردازنده خاموش شود. بنابراین بهتر است که بین تکرار وظایف، هسته‌ها بجای اینکه خاموش و روشن شوند، به حالت مصرف‌پایین137 بروند. در این الگوریتم وظایف تناوبی را به تعداد کمی هسته محدود کرده اند تا به حداقل هسته‌ها برای روشن ماندن نیاز داشته باشند، از سوی دیگر، وظایف غیرتناوبی را که خیلی کمتر رخ می‌دهند، به بقیه هسته‌ها اختصاص داده اند.وقتی اجرای یک وظیفه به پایان رسید، هسته‌ متناظر آن، همانند حافظه نهان آن، میتواند خاموش شود، بنابراین نیازی نیست محتوای مقادیر این وظایف که قرار نیست تا آینده‌ای نزدیک اتفاق بیوفتد، نگهداری شود. در الگوریتم این مقاله، وظایف تناوبی به وسیله الگوریتم RBound-FF به حداقل هسته‌ها اختصاص می‌یابند و وظایف غیرتناوبی بین بقیه هسته‌ها به صورت عادلانه توزیع می‌شوند. شبه کد این الگوریتم را در شکل 3-11 صفحه بعد مشاهده می‌کنید.
Task assignment(Inpot: τj , schedparam)
Begin
If(schedparam ->scedpolicy == RMS)
Assign τj to its bounded core
Endif
If(schedparam -scedpolicy == DMS)
Pi = IDLestCore_RestCore()
If (τj can be admitted on Pi)
Assign τj to Pi
Endif
Else return(REJECT)
Endif
end
شکل 3-11 الگوریتم اختصاص دادن وظایف در مرجع ]35[
شکل 14شکل 3-11 الگوریتم اختصاص دادن وظایف در مرجع [35]
مزايا و معايب اين الگوريتم:
این الگوریتم بدلیل استفاده از RMS در زمانبندی وظایف تناوبی و الگوریتم DMS برای زمانبندی وظایف غیرتناوبی، می‌تواند تاثیر بسازیی در کاهش نرخ نقض سررسید وظایف گردد. همچنین در این الگوریتم نیز وظایف تناوبی از وظایف غیرتناوبی تفکیک شده و جداگانه توزیع می‌شوند که در مصرف انرژی موثر می‌باشد.
اما از جمله معایب این الگوریتم این است که، ورود یک وظیفه جدید در سیستم، موجب می‌شود، مجموعه وظایف مجددا توسط الگوریتم RBound جزءبندی شوند و این مسئله باعث افزایش سربار زمان اجرا می‌شود. همچنین در این الگوریتم نیز فشار زیادی روی تعداد محدودی از هسته‌ها برای اجرای وظایف غیرتناوبی می‌باشد که باعث می‌شود کارایی سیستم پایین بیاید.

3-6-3 الگوريتم زمانبندی چند سطحی 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 )d_i@0 OW)┤

پایان نامه
Previous Entries پایان نامه رایگان درمورد الگوریتم زمانبندی، اشتراک منابع، عدم تقارن Next Entries پایان نامه رایگان درمورد انرژی مصرفی، الگوریتم زمانبندی، مصرف انرژی