پایان نامه رایگان درمورد الگوریتم زمانبندی، اشتراک منابع، عدم تقارن

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

)/(“D” “” _”i” ” ” ) ” ≤1″ (1)

که در آن Ci بدترین حالت زمان اجرا، Ti دوره تناوب هر وظیفه و Di سررسید هر وظیفه می‌باشد.
همچنین می‌توان گفت که EDF در صورتی بهینه است که برای زمانبندی وظایف روی پردازنده‌ای استفاده شود که در آن انحصاری بودن مجاز باشد و وظایف نگران منابع نباشند ]23[ .
الگوریتم EDF در سیستم‌های تک‌پردازنده ، نوعا به دیگر الگوریتم‌های اولویت پویای بدون محدودیت، ترجیح داده‌ می‌شود. به هر حال EDF یک نمونه کلیدی از الگوریتم‌های غیرآگاه به WCET می‌باشد، به این صورت که اولویت وظایف را در هنگام آزادشدن آن‌ها اختصاص داده و منحصرا به سررسید مطلق آن‌ها بستگی دارد]21[ .
یکی دیگر از الگوریتم‌های زمانبندی معروف، الگوریتم زمانبندی نرخ یکنواخت است که الگوریتمی اولویت‌دار و ایستا (زمانبندی در زمان کامپایل مشخص میشود) می‌باشد. این الگوریتم اولویتها را براساس دوره تناوب اختصاص می‌دهد، طوریکه وظیفه با کوتاهترین دوره تناوب و یا بالاترین نرخ اجرا، بالاترین اولویت را پیدا می‌کند. Liu و Layland نشان دادند که درصورتی‌که تخصیص اولویت RMS امکان پذیر نباشد در اینصورت مجموعهای از وظایف قابل زمانبندی نیستند]24[ .
در این الگوریتم فرض می‌شود که تمامی وظایف به‌صورت دوره‌‌ای تکرار می‌شوند، همچنین همزمانی102 ، اشتراک منابع و مبادله103 و تغییر داده در وظایف وجود ندارد. طبق این الگوریتم تمامی وظایف با مشخصه بی‌درنگ سخت درصورتیکه شرط زیر برقرار باشد همواره در سررسید متناظرشان اجرا می‌شوند]24[ :

∑_”i=1″ ^”N” ▒”Ei ” /”Ti ” ” ≤ n (” “2” ^(“1″ /”n” ) “-1 ) (2)”
که در آن n تعداد وظایف، “Ei” بدترین حالت زمان اجرای هر وظیفه و “Ti” دوره تناوب هر وظیفه می‌باشد.
زمانیکه n→∞ مقدار n (2^(1/n)-1 )~ 0.693 و این یعنی برای اینکه تمامی وظایف بی‌درنگ سخت در زمان مناسب اجرا شوند، پردازنده باید 70% زمان خود را صرف این وظایف کند و این درحالی است که پردازنده، قادر به اختصاص 100% زمان خود به وظایف بی‌درنگ نرم میباشد بنابراین این ویژگی خوب نیست چراکه در این‌صورت زمانی برای تغییر کدها و مشخصههای اضافه‌شده نداریم. در واقع باید سیستمی طراحی کرد که کمتر از 60% تا 70% از زمان پردازنده به اجرای وظایف اختصاص یابد. علاوه بر مشکلات گفته‌شده در صورتی‌که وظیفه با بالاترین نرخ اجرا، بالاترین اولویت را داشته باشد ممکن است وظیفهای که خیلی مهم نیست و درعین حال زیاد اجرا میشود بالاترین اولویت را بگیرد و این باعث وقوع قحطی در وظایف مهم‌تر با نرخ اجرای کمتر میشود]24[ و ]25[ .
3-3 طبقه‌بندی معماری سيستم‌های چندهسته‌ای
در میان تعداد زیادی از انواع مدل‌های چندپردازنده، چه طراحی‌های سخت‌افزاری چه طراحی‌های نرم‌افزاری، دو نوع طرح معماری مرجع وجود دارد که یکی پردازنده‌های چندهسته‌ای همگن(SMP)104 و دیگری پردازنده‌های چندهسته‌ای ناهمگن (AMP)105 نام دارد.
SMP یک مجموعه به هم متصل دارای معماری پردازنده‌های یکسان است که از طریق یک گذرگاه مشترک باهم ارتباط دارند. (شکل 3-3 ) در این سیستم‌ها، تمامی پردازنده‌ها دارای نسخه یکسانی از سیستم‌عامل هستند و در هنگام نیاز با هم ارتباط برقرار می‌کنند.
این طرح که بصورت گسترده در کامپیوترهای شخصی و رومیزی استفاده میشود عموماً برای کنترل و هموار کردن مسیر تعادل بارگذاری پویا در محاسبات کاربردهای چند وظیفهای، بصورت بسیار رایجی استفاده میشود. ارزش مدل برنامهنویسی واضحتر (دید حافظه یکنواخت) توسط تعداد زیادی از شیوههای سختافزاری تخصیص داده شده بیان میشود. بعنوان مثال مدیریت وابستگی حافظه نهان106، مسیریابی IRQ 107 (که میتواند برای سیستمهای تعبیهشده، هم به سبب نیازمندیهای مساحت و هم نیازمندیهای توان، بسیار هزینه بر باشد.). بنابراین در مقیاس کوچک و سیستمهای تعبیهشده بسیار مجتمعشده، AMP، اغلب بعنوان راهنمایی برای انتخاب استفاده میشود.
AMP میتواند بصورت یک طرح چندپردازندهای (شکل 3-3- ب) که در آن تمامی پردازندهها مستقل بوده و نیازی به اشتراکگذاری تمامی حافظه فیزیکی نیست، بیان شود. بطور نمونه اکثر شیوههای اتصال برای ارتباطات داخلی پردازنده، توسط سختافزار ارائه میشود. این محدودیت، یک تأثیر قوی و شایان برروی سازماندهی نرمافزار سراسری دارد که نیازمند راهکارهایی برای توزیع و از حالت متمرکز درآوردن، میباشد. بعنوان مثال یک سیستمعامل مشخص باید بصورت مستقل برروی هر پردازنده، اجرا شده و بصورت جداگانه و بدون هیچ حمایت مستقیمی، عملیاتش را انجام دهد. پردازنده‌های چندهسته‌ای ناهمگن از هسته‌هایی تشکیل شده اند که مجموعه دستورات یکسانی را پشتیبانی می‌کنند اما دارای کارایی متفاوتی هستند، این هسته‌ها در فرکانس کاری، توان مصرفی، در اندازه حافظه نهان و بعضی صفات ساختاری دیگر باهم متفاوت هستند. عدم تقارن می‌تواند به صورت هدفمند و طی فرایند ساخت مجزا و برنامه‌ریزی شده یا به دلیل رخداد انحراف در فرایند ساخت حادث شود، یا ناشی از تنظیم فرکانس ساعت باشد]4[ .

یک پردازنده ناهمگن می‌تواند به کارایی بالاتری با توان مصرفی پایین‌تر نسبت به پردازنده‌های همگن دست یابد، زیرا وظایف می‌توانند بروی هسته‌هایی اجرا شوند که خواص متناسب با آن وظایف را دارا هستند.علاوه بر این سیستم‌های ناهمگن در مواقعی که بار کاری سیستم ترکیبی از کارهای موازی و ترتیبی است، به کارایی بالاتری دست پیدا می‌کند. حتی درون ناحیه SMP، نیز تفاوت مدلهای ساختاری بسیاری موجود است]21[ . در دهه گذشته، سرعت محاسباتی پردازندهها، سریعتر از پهنای باند حافظه سیستم، افزایش یافته است. همچنین برنامه‌های کاربردی با محیط بی‌درنگ اغلب نمی‌توانند غیر جبرگرایی مرتبط با معماری SMP را تحمل کنند]26[ .

3-4 زمانبندی بیدرنگ چندهسته‌ای
مادامیکه بحث توان محاسباتی در سیستمهای چندهستهای مطرح است، توسعه الگوریتمهای زمانبندی برای این سیستمها نیز چه از دید نظری108 و چه از دید نرمافزاری، بسیار حائز اهمیت است.
از دید تحلیلی در بحث چندپردازندهای، با دو موضوع مواجه هستیم:
نگاشت وظیفه به پردازنده
زمانبندی وظایف نگاشت شده به یک پردازنده
بنابراین در صورتیکه m پردازنده P1,P2,…,Pm موجود باشند، دو محدودیت مطرح میشود:
هر پردازنده، حداکثر در هر زمان، تنها به یک وظیفه میتواند اختصاص یابد.
هر وظیفه حداکثر در هر زمان، تنها بروی یک پردازنده میتواند زمانبندی شود.
واضح است که در حوزه بیدرنگی، هرچه منابع محاسباتی بیشتر باشد، بهبود کارایی زمانبندی نیز بیشتر خواهد بود.
به طور کلی الگوریتمهای زمانبندی سیستمهای چندهستهای به سه دسته قابل تقسیم هستند:
الگوریتمهای بدون مهاجرت109 (جزءبندی110) :
در این الگوریتمها بصورت پیشفرض، یک جزءبندی ایستا از n وظیفه به m زیرمجموعه مجزا تعریف می‌شود. سپس هر زیرمجموعه به صورت محلی، بروی یک پردازنده توسط یک الگوریتم زمانبندی مختص سیستم‌های تک‌پردازنده، زمانبندی می‌شود. در واقع هر هسته پردازنده، وظایف مشخص شده خودش را با استفاده از یک الگوریتم جدا، زمانبندی می‌کند. ( شکل 3-4 – الف )
الگوریتم‌های کاملا مهاجرتی111 (عمومی112) :
در این سیاست یک زمانبند به عنوان نماینده کل سیستم، اجرای هر وظیفه روی هر پردازنده را زمانبندی می‌کند، بعلاوه اجرای وظایف می‌تواند، با احتمالی بیشتر از یک بار به حالت معلق رفته، سپس مجددا بازیابی شود و این بازیابی می‌تواند، در پردازنده متفاوتی رخ دهد. یعنی وظایف می‌توانند علاوه بر این که روی هر کدام از هسته‌ها اجرا شوند، می‌توانند بین هسته‌های پردازنده جابجا شوند. در این حالت یک صف تنهای عمومی برای همه وظایف بکار برده می‌شود و وظایف می‌توانند براساس اولویتشان بوسیله یک زمانبند، زمانبندی شوند. ( شکل 3-4 – ب )
الگوریتم‌های مهاجرتی محدودشده113 (دوگانه114) :
در این حالت تمامی وظایف می‌توانند، در پردازنده‌های متفاوتی اجرا شوند، اما حتی در صورت انحصاری بودن یک وظیفه باید کاملا بروی تنها یک پردازنده اجرا شوند. در واقع این نوع زمانبندی، ترکیبی از دو زمانبندی عمومی و جزبندی است که در آن برخی وظایف نمی‌توانند بین هسته‌ها جابجا شوند، در حالی که برخی دیگر از وظایف می‌توانند جابجا شوند. ( شکل 3-4 – ج )

وظيفه
دوره‌تناوب
زمان اجرا
بهره‌وری
T1
4
2
0.5
T2
5
2
0.4
T3
10
8
0.8


شکل 3-4 مثالی از زمانبندی تولید شده امکان‌پذیر، از الگوریتم : الف) جزءبندی ب) کاملا مهاجرتی ج) مهاجرتی محدودشده ]21[
شکل 7شکل 3-4 مثالی از زمانبندی تولید شده امکان‌پذیر، از الگوریتم : الف) جزءبندی ب) کاملا مهاجرتی ج) مهاجرتی محدودشده [21]
الگوریتم‌های جزءبندی به دلیل سادگی پیاده‌سازی ساده، به‌صورت گسترده مورد استفاده قرار می‌گیرند. کارایی این دسته از الگوریتم‌ها، زمانیکه از الگوریتم‌های مبتنی بر تک‌پردازنده شناخته‌شده و معروف مانند EDF و RMS استفاده می‌کنند، منطقی است ]21[ .

3-4-1 معايب روش‌های زمانبندی عمومی و جزبندی
یکی از مهم‌ترین معایب زمانبندی عمومی این است که جابجایی وظایف بین هسته‌ها باعث بوجود آمدن ترافیک زیادی در حافظه نهان پردازنده می‌شود و ضعف وابستگی پردازنده و سربار انحصار طلبی، باعث می‌شود که سیستم‌های تعبیه‌شده، دچار آسیب شوند.
در طرف مقابل، روش جزبندی باعث می‌شود که متوسط زمان پاسخ سیستم برای کارهایی با اندازه بزرگ و وسیع بهبود پیدا کند. با این وجود نظریه جزءبندی، شامل چند عیب می‌باشد. در سیستم‌های پویا، هنگامی‌که وظایف در زمان اجرا وارد سیستم می‌شوند، این نظریه مشکل ساز می شود. چراکه ورود یک وظیفه جدید در سیستم، موجب می‌شود، مجموعه وظایف مجددا جزءبندی شوند و این باعث افزایش سربار زمان اجرا می‌شود.
بزرگترین عیب نظریه جزءبندی، این است که وقتی وظایف تناوبی، زمانبندی می‌شوند، این نظریه یک روش نیمه بهینه می‌باشد. به عنوان مثال، سه وظیفه با مشخصات موجود در جدول شکل 3-5 را در نظر بگیرید. در این حالت زمانبند باید بلافاصله متوجه شود که حتی اگر فاکتور بهره‌وری کل، تغییری نکند، در این هنگام هیچ الگوریتم زمانبندی جزءبندی‌‌ ای قادر به زمانبندی این مجموعه وظایف بروی یک m پردازنده ( m<3 ) نخواهد بود، چراکه تقاضای محاسباتی هر زیرمجموعه ممکن، از 2 و یا تعداد بیشتری وظیفه، از ظرفیت محاسباتی یک تک پردازنده تجاوز خواهد‌کرد]21[ .
وظيفه
دوره‌تناوب
زمان اجرا
بهره‌وری
T1
4
2
0.5
T2
5
3
0.6
T3
10
6
0.6

شکل 3-5 مثالی کمی متفاوت از مثال قبلی ، که با رویکرد جزءبندی، قابل زمانبندی نیست]21[
شکل 8شکل 3-5 مثالی کمی متفاوت از مثال قبلی ، که با رویکرد جزءبندی، قابل زمانبندی نیست.[21]
از دید نظری، کران‌های بهره‌وری شناخته‌شده تاکنون(که ضمانت می‌کنند، قادر به زمانبندی مجموعه وظایفی با فاکتور بهره‌وری داده‌شده، هستند ) برای نسخه‌های جزءبندی EDF و RMS ، محافظه‌کار می‌باشند. در حالت کلی، هیچ الگوریتم جزءبندی شده‌ای، دارای بدترین حالت بهره‌وری روی m پردازنده، بیشتر از “(m+1)” /”2″ ندارد. توجه شود که m+1 وظیفه، هرکدام با بهره‌وری “(1+ϵ)” /”2″ نمی‌تواند بروی m پردازنده جزءبندی شود. در صورتیکه0 ⇾ϵ ، کل بهره‌وری چنین مجموعه وظایفی به سمت “(m+1)” /”2″ ، میل خواهد‌کرد]21[ .
بطور کلی کران‌های بهره‌وری بهتر، می‌تواند توسط ایجاد محدودیت‌هایی روی بهره‌وری هر وظیفه، ایجاد شود. فرض کنید UMax بیشترین بهره‌وری هر وظیفه در مجموعه وظایف است، هر وظیفه می‌تواند به یک پردازنده که ظرفیت مجزایی از حداکثر UMax دارد، اختصاص یابد. این بدین معنی است که اگر یک مجموعه از وظایف قابل زمانبندی نباشند، دراین صورت هر پردازنده باید یک ظرفیتی حداقل به اندازه UMax داشته باشد. از این رو کل بهره‌وری چنین مجموعه وظیفه‌ای، بیشتر از m(1-UMax)+UMax خواهدبود. به عبارتی هر مجموعه وظیفه با حداکثر بهره‌وری به میزان m-(m-1)UMax ، قابل زمانبندی است]21[ . در شکل 3-6 نمودار تقسیم بندی الگوریتم‌های زمانبندی چندهسته‌ای نشان داده شده است.

شکل 3-6 طبقه‌بندی الگوریتم‌های زمانبندی چندهسته‌ای ]21[
شکل 9شکل 3-6 طبقه‌بندی الگوریتم‌های زمانبندی چندهسته‌ای
3-5 زمانبندی چند هسته‌ای مبتنی بر DVFS115
در طی سال‌های گذشته تولیدکنندگان برای بهبود عملکرد پردازنده‌ها، از طریق بالابردن فرکانس ساعت پردازنده‌ها، باهم رقابت می‌کردند. اما تحت تکنولوژی‌های ساخت و فرایندساخت پردازنده، بالاترین فرکانس کاری یک پردازنده مبتنی بر CMOS 116، به بالاترین ولتاژ منبع احتیاج دارد. از آنجا که ولتاژ منبع تغذیه تاثیر مستقیمی روی سرعت پردازنده دارد، زمانبندی وظایف و انتخاب ولتاژ منبع باید همزمان مورد توجه قرار گیرد ]27[ .
توان مصرفی پویای ( Pdynamic) یک پردازنده مبتنی بر CMOS ، با فرکانس کاری و ولتاژ منبع رابطه مستقیم دارد، یعنی:
P_dynamic∝f×V_dd^2 (3)
بنابراین افزایش فرکانس کاری، فقط باعث افزایش بهره‌وری نمی‌شود، بلکه باعث می‌شود توان مصرفی نیز افزایش یابد. با توجه به این حقیقت که دستگاه‌هایی که از باطری‌های قابل حمل استفاده ‌می‌کنند، دارای انرژی محدودی هستند، تحقیقات روی ذخیره توان، توجه زیادی را به خود جلب کرده است که اغلب آن‌ها از تکنیک‌های DVFS برای افزایش طول عمر باطری دستگاه‌های قابل حمل استفاده کرده اند ]28[ .
DVFS ولتاژ منبع و فرکانس کاری پردازنده را به صورت همزمان کاهش می‌دهد تا بتواند زمانی که ما نیاز به بهره‌وری کمی داریم، انرژی را ذخیره کند. همانند مغز انسان که مقدار زیادی انرژی مصرف می‌کند، پردازنده یک سیستم نیز انرژی زیادی را مصرف می‌کند. بنابراین معماری‌های چندهسته‌ای می‌توانند بهره زیادی از تکنولوژی DVFS ببرند ]29[ .
در سیستم‌های چندهسته‌ای اولیه، همه هسته‌های پردازنده دارای یک ساعت مشترک بودند. تحت این معماری، هنوز DVFS می‌تواند باعث ذخیره انرژی شود، اما محدودیت‌های زیادی در این بین وجود دارد که ایجاد توازن بین کارایی و توان مصرفی را سخت‌تر کرده است. در پردازنده‌های امروزی هر هسته می‌تواند با فرکانس و ولتاژ متفاوتی کار کند. این پردازنده‌ها در دو مدل وجود دارند، حالت بسته117 و حالت برخط118. در حالت بسته، فرکانس هسته‌های پردازنده نمی‌تواند در حین اجرای یک وظیفه تغییر کند و فقط در ابتدا که وظیفه اجرایش آغاز می‌شود، می‌تواند تغییر کند. اما در حالت برخط، فرکانس هسته‌ها می‌تواند در هر لحظه از اجرای وظیفه تغییر کند ]30[ .
دو استراتژی برای استفاده از تکنیک‌های DVFS برای کاهش مصرف انرژی وجود دارد:
تغییر ولتاژ و فرکانس در زمان سکون وظیفه119
تغییر ولتاژ و فرکانس در هنگام دسترسی به منابع خارجی
در روش اول که تغییر ولتاژ و فرکانس در زمان سکون وظیفه می باشد (منظور از زمان سکون وظیفه، مدت زمانی است که وظیفه در صف آماده پردازنده منتظر می‌شود تا اجرایش آغاز شود یا ادامه پیدا کند)، وقتی که پردازنده شروع به اجرای وظیفه می‌کند، فرکانس اجرایی آن در نسبت بین بدترین حالت زمان اجرا و سررسید وظیفه، ضرب می‌شود تا با این کار فرکانس اجرایی آن کاهش یافته و در نتیجه توان مصرفی کاهش یابد. مثالی از این حالت را در شکل3-7 مشاهده می‌کنید.

شکل 3-7 نمونه‌ای از تنظیم فرکانس و ولتاژ در زمان سکون وظیفه، الف) بدون , DVFS ب) با DVFS
شکل 10شکل 3-7 نمونه‌ای از تنظیم فرکانس و ولتاژ در زمان سکون وظیفه، الف) بدون , DVFS ب) با DVFS
در مرجع ]31[ روشی پیشنهاد شده که در آن از ترکیب دو مولفه برخط و برون خط استفاده شده تا هم قید زمانی را در نظر بگیرند و هم انرژی مصرفی را کاهش دهند. در این روش، مولفه برون‌خط، کمترین سزعت ممکن پردازنده را پیدا می‌کند که در این سرعت پایین، همچنان همه قیود زمانی بهبود داشته است. از سوی دیگر مولفه برخط به صورت پویا سرعت عملیاتی را تغییر می‌دهد تا انرژی و توان بیشتری ذخیره شود. بنابراین زمان اجرای وظیفه، ممکن است کمی تغییر کند.
در مرجع ]32[ نیز از یک وقفه برای بروز رسانی فرکانس مناسب استفاده شده تا تغییرات ناگهانی حجم‌بار، در نظر گرفته شود. در این الگوریتم از داده‌های مربوط به تاریخچه برای پیشبینی حجم‌بار بعدی استفاده می‌شود و سپس با توجه به خطای پیشبینی120، نرخ بروز رسانی فرکانس، تنظیم می‌شود.
روش دوم که تغییر فرکانس و ولتاژ در هنگام دسترسی به منابع خارجی است، هنگامی استفاده می‌شود که وظایف ما دارای محدودیت حافظه و I/O (ورودی/خروجی) باشند. می‌دانیم که سرعت عملیاتی حافظه و لوازم جانبی بسیار کمتر از پردازنده است، بنابراین برای وظایفی که مکرراً باید منتظر رسیدن مقادیرشان از حافظه یا I/O هستند، فرکانس عملیاتی پردازنده می‌تواند کاهش پیدا کند ]33[ . بنابراین تا وقتی که پردازنده منتظر مقادیر خارجی برای پایان دادن به وظیفه مورد است، توان کمتری مصرف می‌شود.

3-6 بررسی کارهای گذشته
در این بخش به بررسی و شرح کامل چند الگوریتم پیشنهاده‌شده مهم زمانبندی و توزیع وظایف در سیستم‌های تعبیه‌شده چند هسته‌ای خواهیم پرداخت و همچنین مزایا و معایب آن‌ها را را بیان می‌کنیم.

3-6-1 الگوريتم توزيع بار غير تعادلی LU-McEP121
یکی از کارهایی که برای کاهش مصرف انرژی و توان پردازنده‌های چندهسته‌ای تعبیه‌شده انجام شده، روش پیشنهادی در مرجع ]34[ بوده که یک روش بارگیری نامتعادل122 است که وظایف را به دو دسته تناوبی و غیرتناوبی تقسیم می‌کند.در این روش، وظایف تناوبی به حداقل هسته‌ها متمرکز می‌شوند تا بقیه هسته‌ها بتوانند خاموش بمانند. برای اینکه هیچ سررسیدی از دست نرود، این روش از دو الگوریتم زمانبندی استفاده کرده است که یکی RMS و دیگری SQ 123 می‌باشد. RMS برای متمرکز کردن وظایف تناوبی استفاده شده است و برای اینکه بفهمد که یک وظیفه تناوبی، امکان متمرکزسازی دارد یا نه از حد آستانه بهره‌وری124 استفاده می‌کند تا تعیین کند که یک وظیفه تناوبی چقدر قابلیت متمرکز سازی دارد. رابطه حد آستانه بهره‌وری به صورت زیر است:
∑_(i=)^n▒C_i/T_i ≤n(√(n&2)-1) (4)
که در آن، n تعداد کل وظایف تناوبی است، C زمان اجرای هر وظیفه و T دوره‌تناوب هر وظیفه می‌باشد.
از الگوریتم SQ در این روش برای توزیع وظایف غیرتناوبی روی هسته‌های باقیمانده استفاده شده است. در SQ یک وظیفه جدید به هسته‌ای که کمترین تعداد وظایف را دارد، فرستاده می‌شود.
مهم‌ترین چیز برای سنجیدن کارایی وظایف تناوبی، اجرای قبل از سررسید آن می‌باشد، تا اجرای سریع آن‌ها. یعنی در وظایف تناوبی مشکل زمان انتظار نسبت به سررسید خیلی مهم نیست. در مقابل در وظایف غیرتناوبی که کمتر اتفاق می‌افتند و خیلی زود در آینده‌ای نزدیک رخ نمی‌دهند( مانند ورودی‌های کاربر، از قبیل لمس‌کردن صفحه نمایش لمسی و باز کردن یک برنامه کاربردی )، از روش توزیع بار استفاده می‌کنیم. وقتی کار یک وظیفه غیرتناوبی تمام می‌شود، هسته متناظرش می‌تواند خاموش شود، همچنین حافظه نهان آن هسته نیز می‌تواند خاموش شود، چون وظیفه از نوع غیرتناوبی است و قرار نیست تا آینده‌ای نزدیک دوباره تکرار شود. همچنین از آنجایی که زمان پاسخ از سررسید در این وظایف مهم‌تر است، به علت توزیع این وظایف بین بقیه پردازنده‌ها، زمان پاسخ‌دهی آن‌ها کاهش می‌یابد.
دو روش در مدیریت توان به عنوان نماینده‌ای از بقیه روش‌ها وجود دارد:
DVS 125
DPM 126
DVS به طور معمول برای ذخیره و صرفه‌جویی توان استفاده می‌شود، زیرا توان پویا با Vdd متناسب است که Vdd ولتاژ منبع می‌باشد.
p=∑▒〖C_L×f×V_dd^2 〗 (5)
که در آن CL ظرفیت خازن بارگذاری می‌باشد. امروزه با تکنولوژی نانو، که ولتاژ منبع را می‌توان به اندازه ولتاژ آستانه127 پایین آورد ( ولتاژ آستانه، حداقل ولتاژ لازم برای کارکردن پردازنده است)، بهره‌وری DVS کمتر شده است. بنابراین خیلی مشکل است که از DVS به عنوان یک روش با بهره‌وری خوب در محیط‌هایی با بارگذاری متغییر پویا استفاده‌شود. از این‌رو محاسبه سطح ولتاژ مناسب برای هر وظیفه در زمان اجرا مشکل است. برای استفاده DVS در محیط‌های واقعی غیرقابل پیشبینی، نیاز به زیرساخت‌های پیشبینی اضافی می باشد، اما این زیرساخت‌های اضافی باعث ایجاد سربار در سیستم‌های تعبیه‌شده می‌شوند که باعث محدود کردن منابع سخت‌افزاری می‌گردد.
در این مقاله از روش DPM برای کاهش مصرف توان استفاده شده است که هسته‌ها را به صورت پویا خاموش می‌کند. این روش بیشتر در کاهش توان نشتی128 موثر است. روش‌های کاهش دما( مدیریت دما) باید شامل انتخاب یک سیاست در زمانبندی باشند، اگرچه پردازنده‌های تعبیه‌شده‌‌‌، در مقایسه با پردازنده‌هایی با کارایی بالا مانند Intel CORE i7 سبب افزایش دمای بیش از اندازه نمی‌شوند.بنابراین در این الگوریتم از دما صحبتی نشده‌است.
برای وظایف غیرتناوبی که مجبور نیستیم محتویاتشان را بعداز اتمام اجرا در حافظه نهان نگه داریم( چون به ندرت رخ می‌دهند و دیربه دیر تکرار می‌شوند)، می‌توانیم هسته‌ها را به طور کامل خاموش کنیم و حتی حافظه نهان مربوطه را هم خاموش نماییم. اما برای وظایف تناوبی این‌طور نیست، حتی در حالت بیکار129 هم باید هسته‌ها و حافظه نهان روشن بمانند.
بهترین مثال‌ها برای وظایف تناوبی، برنامه‌های دنباله‌دار( جریان‌دار پشت‌سرهم) هستند، مانند پخش یک آهنگ یا اجرای یک بازی یا پخش فیلم و… و بهترین مثال‌ها برای وظایف غیرتناوبی، برنامه‌هایی هستند که با کاربر در تعامل هستند، مانند پیمودن صفحه‌های منوهای یک تلفن‌همراه و یا بازکردن برنامه‌ها و لمس‌کردن روی آیکون‌ها و…
در وظایف تناوبی، داده‌ها باید مکررا درحال رمزگذاری و رمزگشایی باشند که دارای نرخ رمزگشایی نیز می‌باشند، به عنوان مثال اگر فرض کنیم در یک برنامه پخش آهنگ، زمان اجرای هر وظیفه به‌طور متوسط 200 میلی‌ثانیه و دوره تناوب آن یک ثانیه باشد، آنگاه بهره‌وری پردازنده برای این برنامه U=C/T=200ms/1000ms=0.2 می‌باشد. ( جون همواره زمان اجرای یک وظیفه از دوره‌تناوب آن کمتر است. در این نوع از برنامه‌ها که مسئله زمان مارا راضی نگه می‌دارد، نیازی به سرعت بیش‌از اندازه پردازش نداریم.
بنابراین در مثال قبل که مربوط به برنامه H.264130 بود( یک برنامه رمزگشایی است که در پخش فایل‌های چندرسانه‌ای استفاده میشود)، فقط در هر ثانیه به 20 درصد از قدرت پردازش پردازنده احتیاج داشتیم. این یعنی 80 درصد از توان پردازشی پردازنده می‌تواند به وظایف دیگر اختصاص پیدا کند. از سوی دیگر برنامه‌هایی نظیر لمس‌کردن صفحه نمایش لمسی، شروع و فشاردادن یک برنامه کاملا تصادفی و غیرقابل پیشبینی اتفاق می‌افتند، و این وظایف که با کاربر در ارتباط هستند، وقتی که رخ می‌دهند باید بلافاصله اجرا شوند. اگرچه از نظر سررسید سخت‌گیری‌ ندارند، اما تاخیر پاسخ‌دهی این‌گونه وظایف، کاملا واضح توسط کاربر قابل مشاهده و ناخوشایند است.

شرح جزئيات الگوريتم:
استراتژی که دراینجا توسط Jeon ، Lee و Chung پیشنهاد شده]34[، دو نوع وظیفه را پوشش می‌دهد، به این صورت که وظایف تناوبی را به حداقل هسته‌ها و وظایف غیرتناوبی را به بقیه هسته‌های پردازنده اختصاص می‌دهد. از این طریق، هم مصرف انرژی بدلیل اختصاص وظایف تناوبی به کمترین تعداد هسته‌ها، کاهش می‌یابد و هم بدلیل توزیع وظایف غیرتناوبی به بقیه هسته‌ها، متوسط زمان انتظار برای اجرای وظایف غیرتناوبی کاهش داده‌ می‌شود.
برای وظایف تناوبی، بارگذاری روی یک هسته، زمانی تغییر می‌کند که سیستم در دو شرایط مختلف قرار گیرد:
1)موقعی که یک وظیفه جدید ایجاد می‌شود. 2)موقعی که یک وظیفه موجود به پایان می‌رسد.
در هردو حالت با استفاده از RMS نباید سررسید وظایف از دست برود. وقتی که یک وظیفه جدید ایجاد می‌شود، زمانبند به دنبال هسته‌ای می‌گردد که روشن باشد و کمترین بارگیری را داشته‌ باشد. وقتی هیچ هسته‌ای وجود نداشته باشد که بتواند وظیفه جدید را اجرا کند، یکی از هسته‌هایی که خاموش بودند، روشن می‌شوند و این وظیفه جدید به آن اختصاص میابد. وقتی یک وظیفه موجود کارش تمام شود، زمانبند چک می‌کند که آیا این هسته که اخیرا این وظیفه روی آن کارش تمام شد، می‌تواند خاموش شود یا خیر.
برای به حداقل رساندن تعداد هسته‌های روشن، زمانبند به دنبال هسته‌ دیگری می‌گردد تا وظایف تناوبی باقیمانده را به آن منتقل کند، به این صورت که اگر هر هسته‌ای که بارکاری آن به اندازه کافی کم باشد تا بتواند وظایف باقیمانده از یک هسته دیگر را اجرا کند، پیدا شود، وظایف باقیمانده از هسته قبلی به این هسته انتقال می‌یابند و هسته قبلی خاموش می‌شود، در غیر این صورت جابجایی مجدد برویش انجام نمی‌شود.

TaskInit (pNewtask,pSchedparam,… )
Do task initialization
// find a core on which new task is to be assigned according to
// the task’s scheduling policy.
If (pSchedparam->schedpolicy == RMS)
// if periodic task, find the an idle core
Core = findBusiestCore();
If (pSchedparam-schedpolicy ==FCFS)
// if aperiodic task, find the an idle core
Core = findIdlestCore();

Insert the to the selected core’s readt queue
شکل 3-8 شبه کد الگوریتم تخصیص وظایف]34[
شکل 11شکل 3-8 شبه کد الگوریتم تخصیص وظایف [34]
در شکل 3-8 شبه‌کد تخصیص یک وظیفه جدید ایجاد شده، براساس مشخصات وظیفه می‌باشد. این کد با سیاست زمانبندی خود در واقع وظایف تناوبی را از وظایف غیرتناوبی جدا می‌کند.(تمایز قائل می‌شود)
اگر وظیفه جدید ایجاد شده تناوبی بود، پررفت‌وآمدترین هسته برای اجرای این وظیفه جدید، انتخاب می‌شود و تا زمانی که سررسید آن فرابرسد می‌تواند اجرا شود. اما اگر وظیفه جدید ایجادشده، غیرتناوبی بود، بیکارترین هسته انتخاب خواهد شد تا وظیفه در آن اجرا شود.
این تراکم بارگذاری روی تعداد کمی هسته( توسط وظایف غیرتناوبی) ممکن است منجر به این شود که بخشی از ظرفیت محتوای حافظه نهان L1 از دست برود. به هر حال پردازنده‌های چندهسته‌ای جدیدنتنها دارای حافظه نهان L1 برای هر هسته به صورت جداگانه هستند، بلکه دارای یک حافظه نهان L2 مشترک بسیار بزرگ نیز هستند. این حافظه نهان L2 می‌تواند جریمه فقدان131 حافظه نهان L1 را به حداقل ممکن برساند که در مقایسه با زمان کل اجرا، زیاد نیست. در

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