else
(17) go to line 21
(18) Dispatch the task to DSPt.
(19) end
(20) % Second level for load balance%
(21) if (Num(maxUniformity(DSPon))==1)
(22) DSPt = maxUniformity(DSPon)
(23) else if (Num(minOrder(DSPon))==1)
(24) DSPt = minOrder(DSPon)
(25) else if (Num(minTask(DSPon))==1)
(26) DSPt = minTask(DSPon)
(27) else
(28) DSPt = minserial(DSPon)
(29) Dispatch the task to DSPt.
(30) End.شکل 19شکل 3-16 شبه کد الگوریتم توزیع وظایف TLDHLB [36]
3-6-4 الگوریتم زمانبندی پیشنهادی در مرجع ]37[
در این مقاله، یک الگوریتم زمانبندی بیدرنگ برای مجموعه وظایف ترکیبی برروی مدل چند هستهای همگن، ارائه شده است. وظایف تناوبی براساس سیاست EDF، جزءبندی شده و زمانبندی میشوند. وظایف غیرتناوبی نیز بصورت سراسری به هستههای مختلف، تخصیص داده میشوند. در ادامه به جزئیات الگوریتم میپردازیم.
سیستم بکار رفته در این مقاله، دارای m، هسته پردازشی همگن p={p1 , p2 ,… , pm} میباشدوظایف سیستم نیز شامل ترکیبی از وظایف تناوبی و غیرتناوبی است. مجموعه وظایف تناوبی T={T1 , T2, … , Tn}، شامل n وظیفه تناوبی انحصاری و مستقل است و مجموعه وظایف غیرتناوبی A={A1 ,A2 , …, Ak} شامل k وظیفه غیرتناوبی انحصاری میباشد. هر وظیفه تناوبی توسط 4 مشخصه Ai , Ci , Pi , Di که به ترتیب بیانگر زمان ورود وظیفه، بدترین حالت زمان اجرا، دوره تناوب وظیفه و سررسید متناظر آن میباشد شناسایی میشوند. در این مدل دوره تناوب وظایف، برابر با سررسید متناظرشان درنظر گرفته شده است. وظایف غیرتناوبی نیز شامل دو مشخصه Ei و Ai که به ترتیب بیانگر زمان ورود و بدترین حالت زمان اجرا است میباشد. بهرهوری وظیفه تناوبی Ti بصورت Ui=Ci/Pi تعریف میشود و جمع بهرهوری تمامی وظایف تناوبی بصورت بهرهوری کل هر هسته درنظر گرفته میشود. از آنجاییکه بیشترین مقدار بهرهوری هر هسته، یک میتواند باشد از اینرو برای بهرهوری کل سیستم داریم : U f1 ). این روند ادامه پیدا می‌کند تا در لحظه tf که کوچکتر از 4? می‌باشد، اجرای وظیفه روی هسته تمام می‌شود.
محاسبه زمان اجرای نهایی وظیفه و انرژی مصرفی آن:
برای محاسبه زمان اجرای هر وظیفه با توجه به فرکانس اجرایی هسته متناظر خودش، باید زمان اجرای هر پارت(قسمت) که وظیفه با فرکانس خاصی در حال اجرا می‌باشد را محاسبه و با هم جمع کرد.
اگر f_max حداکثر فرکانس اجرایی یک هسته، C_t بدترین حالت زمان اجرای یک وظیفه و f_t فرکانسی باشد که در هر پارت زمانی، وظیفه با آن فرکانس در حال اجرای روی هسته باشد، آنگاه بر اساس فرمول فاکتور کاهش سرعت موجود در مراجع ]38[ و ]39 [، زمان اجرای هر وظیفه به صورت زیر محاسبه می شود:
?EX?_t = f_(max )/f_t ×C_t (زمان اجرای هر وظیفه) (30)
برای محاسبه انرژی مصرفی یک وظیفه روی هسته، از رابطه زیر استفاده می‌کنیم:
E=P_t×?EX?_t (31)
که در آن Pt توان مصرفی متناظر با فرکانس اجرایی وظیفه در هر پارت زمانی است و EXt هم در واقع طول هر پارت زمانی است که وظیفه با این فرکانس و توان P متناظر با آن در حال اجرا می‌باشد.
برای محاسبه کل یک وظیفه، پس از اجرای الگوریتم تنظیم فرکانس پیشنهادی، باید انرژی تک‌ تک پارت‌هایی که وظیفه در آن‌ها با فرکانس‌های متفاوتی اجرا می‌شود، محاسبه شده و در نهایت باهم جمع گردند. علت این مسئله این است که به عنوان مثال ممکن است یک وظیفه از زمان شروع به اجرایش تا پایان کار خود، در سه سطح فرکانسی متفاوتی اجرا شود، در نتیجه می بایست انرژی مصرفی تک‌تک این سطوح را محاسبه کرده و باهم جمع کرد.
برای فهم بیشتر، مثال شکل 4-7 را در نظر بگیرید، همچنین فرض کنید پردازنده‌ای دارای چهار سطح فرکانسی و توان متناظر با آن باشد که در جدول 4-1 نشان داده شده است.
جدول 4جدول 4-1 فرکانسها و توان متناظر هر سطح فرکانسی
جدول 4-1 فرکانس‌ها و توان متناظر هر سطح فرکانسی
f3
f2
f1
fmin
فرکانس اجرایی
p3
p2
p1
pmin
توان متناظر

با توجه به شکل4-7 و جدول 4-1 ، انرژی مصرفی کل این وظیفه به صورت زیر محاسبه می‌شود:
E=(?×p_min )+(?×p_1 )+(?×p_2 )+(t_f-3?)×p_3 (32)
برای بدست آوردن tf که زمان پایان یافتن اجرای وظیفه می باشد، بر اساس فرمول (30) باید بصورت زیر عمل کنیم:
در ابتدا که هسته با فرکانس fmin شروع به اجرای وظیفه می‌کند، اگر بخواهد با این فرکانس وظیفه را اجرا کند، زمان اجرای آن برابر خواهد بود با:
f_(max )/f_min ×C_i (33)
که در اینجا fmax همان f3 می‌باشد. حال چون به اندازه ? واحد زمانی اجرایش طول کشید ولی تمام نشد، فرکانس یک سطح افزایش پیدا می‌کند، بنابراین این وظیفه A درصدش با فرکانس fmin اجرا شده و 1-A درصد از اجرایش باقی مانده است. مقدار A به صورت زیر محاسبه می‌شود:
?/(f_3/f_min ×C_i ) (34)
حال در پارت دوم که با فرکانس f1 کار می‌کند، زمان اجرایش برابر عبارت زیر خواهد بود:
(f_(3 )/f_1 ×C_i)×(1-?/(f_3/f_min ×C_i )) (35)
این روند محاسبه را ادامه می‌دهیم تا در نهایت tf محاسبه شود. در ادامه برای فهم بهتر این الگوریتم، به یک مثال عددی توجه فرمایید.
مثال:
سیستم بی‌درنگ چندهسته‌ای که هر هسته آن دارای سه سطح فرکانسی و سه توان مصرفی متناظر با فرکانس خود که در جدول زیر آورده شده را درنظر بگیرید:
جدول 5جدول 4-2 مثال عددی الگوریتم تنظیم فرکانس سررسیدمحور پیشنهادی
جدول 4-2 مثال عددی از الگوریتم تنظیم فرکانس سررسیدمحور پیشنهادی
400
200
100
فرکانس هسته MHz
450
85
60
توان مصرفی mv
فرض کنید یک وظیفه غیرتناوبی با مشخصات زیر در یک هسته شروع به اجرا می‌کند.
Ci = 5 , Dsr = 10 , Di = 10 , ? = 0.2Dsr = 2 (36)
فرض می‌کنیم وظیفه در لحظه صفر شروع به اجرا در هسته می‌شود. در ابتدا که وظیفه با فرکانس 100 مگاهرتز شروع به کار می‌کند، با فرض ادامه کار با همین فرکانس، زمان اجرای آن برابر است با:
t_1=f_(max )/f_min ×C_i=400/100×5=20 (37)
این بدین معنی است که اگر وظیفه بخواهد با همین فرکانس تا آخر اجرا شود، اجرایش 20 ثانیه طول می‌کشد، اما با توجه به الگوریتم ما و مقدار ? که در اینجا 2 می‌باشد، پس از 2 واحد زمانی از این 20 واحد، فرکانس هسته یک سطح افزایش یافته و از لحظه 2 به بعد با فرکانس 200 ، وظیفه را اجرا می‌کند. این بدین معنی است که 10 درصد از وظیفه با فرکانس 100 اجرا شده و 90 درصد از اجرایش باقی مانده است. بنابراین با فرکانس 200 ، زمان اجرای وظیفه برابر:
(400/200×5)×90%=9 (38)
یعنی با فرکانس 200، اجرای وظیفه پس از 9 واحد زمانی تمام می‌شود، اما چون گاما برابر2 است بنابراین در لحظه 4 فرکانس آن یک بار دیگر افزایش پیدا کرده و به 400 می‌رسد. بنابراین در لحظه چهار، حدود 22 درصد دیگر از وظیفه اجرا شده است و حدود 77 درصد از اجرایش باقی مانده است.
بنابراین مقدار باقی‌مانده زمان اجرای وظیفه با فرکانس 400 عبارت انداز:
(400/400×5)×77.8%=3.89 (39)
یعنی 3.89 واحد زمانی پس از لحظه 4 ، اجرای وظیفه به اتمام می‌رسد، بنابراین زمان اجرای کل وظیفه همان‌طور که در شکل 4-9 نشان داده شده، برابر است با:
2 + 2 + 3.89 = 7.89 = زمان اجرای کل وظیفه
شکل 4-9 نمودار زمانی مثال الگوریتم تنظیم فرکانس پیشنهادی
بنابراین وظیفه مورد نظر در این مثال پس از 7.89 واحد زمانی، اجرایش به پایان می رسد، در حالی که سررسید آن 10 واحد زمانی تعیین شده بود، در نتیجه این وظیفه غیرتناوبی قبل از نقض شدن سررسیدش اجرا شده است.
حال با توجه به جدول فرکانس و توان این مثال ( جدول 4-2 ) و با داشتن زمان خاتمه وظیفه، می‌توان انرژی مصرفی کل آن را به صورت زیر حساب کرد:
E=(?×p_min )+(?×p_1 )+(t_f-2?)×p_2 (40)
E=(2×60)+(2×85)+(7.89-4)×450 (41)
E=2040 (42)
4-6 نتیجه‌گیری
در این فصل الگوریتم پیشنهادی ما در این پژوهش مطرح شد که این الگوریتم دارای سه قسمت بود، بخش اول روشی برای تفکیک وظایف و اختصاص زیرمجموعه‌ای از هسته‌ یا هسته‌ها به آن بود، در بخش دوم الگوریتم جدیدی برای توزیع وظایف بین هسته‌ها بیان شد و در بخش سوم نیز راهکار جدیدی برای تنظیم فرکانس و ولتاژ هسته‌ها با درنظر گرفتن سررسید وظایف، پیشنهاد شد که با استفاده از آن زمان اجرای نهایی وظایف و انرژی مصرفی و همچنین زمان پاسخ و انتظار وظایف محاسبه می‌شود.
فصل پنجم
فصل پنجم :شبیه‌سازی و ارزیابی الگوریتم پیشنهادی
در فصل قبل به تشریح کامل الگوریتم پیشنهادی خود پرداختیم که یک الگوریتم سه سطحی بود، سطح اول تفکیک وظایف تناوبی از غیرتناوبی واختصاص بخشی از هسته به آن‌ها، سطح دوم توزیع وظایف با روشی جدید به هسته‌ها و سطح سوم الگوریتمی جدید برای تنظیم فرکانس و ولتاژ پردازنده چندهسته‌ای بود. اهداف این الگوریتم پیشنهادی ما ، رسیدن به انرژی مصرفی کمتر، کاهش زمان پاسخ و زمان انتظار وظایف غیرتناوبی، کاهش نرخ نقض سررسید وظایف و در نتیجه آن‌ها افزایش کارایی سیستم می‌باشد. در این فصل به تشریح محیط و روش شبیه‌سازی الگوریتم، ارزیابی و بیان نتیجه شبیه‌سازی و مقایسه الگوریتم پیشنهادی با مقاله‌های دیگر خواهیم پرداخت.
5-1 تنظیمات اولیه شبیه‌سازی
برای انجام آزمایش‌ها ، از پردازنده چندهسته‌ای PowerPC 405PL شرکت IBM که مخصوص سیستم‌های تعبیه‌شده ساخته شده است، استفاده کرده‌ایم. این پردازنده که دارای چهار سطح فرکانسی مجزا می باشد، بعنوان واحد پردازشی با قابلیت تنظیم پویای ولتاژ / فرکانس استفاده شده است. مشخصات این پردازنده چندهسته‌ای که از مرجع ]40[ استخراج شده، در جدول 5-1 نشان داده شده است.چ
جدول 5-1 مشخصات پردازنده چندهسته‌ای PowerPC 405PL شرکت IBM ]40[
333
266
100
33
فرکانس (MHz)
1.9
1.8
1
1
ولتاژ (V)
750
600
72
19
توان مصرفی (mW)
سیستمی که ما برای آن الگوریتم زمانبندی وظایف را پیشنهاد داده‌ایم، یک سیستم بی‌درنگ نرم می‌باشد، بنابراین مجموعه وظایفی که از آن‌ها برای پیاده‌سازی سیستم استفاده کرده‌ایم نیز وظایفی هستند که همگی دارای

این مطلب رو هم توصیه می کنم بخونین:   منابع تحقیق درموردکسب و کار، بازاریابی، بازمهندسی
دسته‌ها: No category

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