زمانبندی وظيفهها در سيستمهای بیدرنگ نهفته چندهستهای با هدف بهبود انرژی مصرفی و کارايی
توضیحات
زمانبندی وظيفهها در سيستمهای بیدرنگ نهفته چندهستهای با هدف بهبود انرژی مصرفی و کارايیاین پایان نامه در قالب فرمت word قابل ویرایش ، آماده پرینت و ارائه به عنوان پروژه پایانی میباشد. صفحه عنوان فهرست مطالب...............................................................................................................................................................هشت چکيده 1 فصل اول :مقدمه 1-1 پيشگفتار 2 1-2 توصيف مسئله 3 1-3 ساختار پايان نامه 4 فصل دوم :مفاهيم اوليه 2-1 سيستم های تعبيهشده 6 2-1-1 مصرف انرژی در سيستمهای تعبيهشده 8 2-2 سيستم های تعبيهشده بیدرنگ 9 2-2-1 انواع سيستم های بیدرنگ از نظر محدوديت زمانی 11 2-2-2 تابع بهرهوری در سيستمهای بیدرنگ 12 2-3 وظيفه 13 2-3-1 مدل وظيفه بیدرنگ 14 2-3-2 دستهبندی وظايف بیدرنگ 15 2-4 سررسيد 16 2-5 هسته پردازنده 18 2-6 منابع 18 2-7 مفاهيم زمانبندی 19 2-7-1 تعاريف مربوط به مبحث زمانبندی 20 2-8 سيستم های چندهستهای 21 2-9 نتيجهگيری 22 فصل سوم : مرور منابع و کارهای انجامشده 3-1 طبقه بندی روشهای زمانبندی 23 3-2 الگوريتمهای زمانبندی بیدرنگ تک پردازنده 26 3-3 طبقهبندی معماری سيستمهای چندهستهای 29 3-4 زمانبندی بیدرنگ چندهستهای 30 3-4-1 معايب روشهای زمانبندی عمومی و جزبندی 32 3-5 زمانبندی چند هستهای مبتنی بر DVFS 34 3-6 بررسی کارهای گذشته 37 3-6-1 الگوريتم توزيع بار غير تعادلی LU-McEP 37 3-6-2 الگوريتم زمانبندی غيرتعادلی جزبندی با RBound 42 3-6-3 الگوريتم زمانبندی چند سطحی PDAMS 47 3-6-4 الگوريتم زمانبندی پيشنهادی در مرجع ]37[ 59 3-7 نتيجهگيری 65 فصل چهارم : الگوريتم پيشنهادی 4-1 جايگاه الگوريتم پيشنهادی 66 4-2 کليات الگوريتم پيشنهادی 68 4-3 مدل وظيفه الگوريتم پيشنهادی 68 4-4 مدل سيستم الگوريتم پيشنهادی 69 4-5 شرح کامل الگوريتم پيشنهادی 71 4-5-1 بخش اول الگوريتم پيشنهادی (تفکيک وظايف و هستهها) 71 4-5-2 بخش دوم الگوريتم پيشنهادی (توزيع وظايف بين هستهها) 72 4-5-3 الگوريتم پيشنهادی تنظيم فرکانس سررسيد محور (بخش سوم الگوريتم پيشنهادی) 83 4-6 نتيجهگيری 88 فصل پنجم :شبيهسازی و ارزيابی الگوريتم پيشنهادی 5-1 تنظيمات اوليه شبيهسازی 89 5-2 محيط شبيهسازی 91 5-3 ارزيابی انرژی مصرفی 92 5-4 ارزيابی کارايی 97 5-4-1 ارزيابی نرخ نقض سررسيد 97 5-4-2 ارزيابی متوسط زمان پاسخ وظايف غيرتناوبی 99 5-4-3 ارزيابی متوسط زمان انتظار وظايف غيرتناوبی 101 5-5 نتيجهگيری 102 فصل ششم : نتيجهگيری و پيشنهادات 6-1 نتيجهگيری 103 6-2 پيشنهادات 104 مراجع 105 واژگان اختصاری 108 فهرست شکل¬ها شکل 2-1- تابع بهرهوری u(t) برای انواع مختلف وظایف بیدرنگ 13 شکل 2-2- نمودار گذار حالت یک وظیفه 14 شکل 2-3 سررسید متناظر و سررسید مطلق یک وظیفه 17 شکل 3-1 تفسیمبندی انواع روشهای زمانبندی 26 شکل 3-2 مثالی از کاربرد زمانبندی تک هستهای با استفاده از الگوریتم EDF 27 شکل 3-3 بررسی اجمالی معماری پردازنده AMP و SMP 30 شکل 3-4 مثالی از زمانبندی تولید شده امکانپذیر، از الگوریتم : الف) جزءبندی ب) کاملا مهاجرتی ج) مهاجرتی محدودشده 32 شکل 3-5 مثالی کمی متفاوت از مثال قبلی ، که با رویکرد جزءبندی، قابل زمانبندی نیست 33 شکل 3-6 طبقهبندی الگوریتمهای زمانبندی چندهستهای 34 شکل 3-7 نمونهای از تنظیم فرکانس و ولتاژ در زمان سکون وظیفه، الف) بدون DVFS ب) با DVFS 36 شکل 3-8 شبه کد الگوریتم تخصیص وظایف 40 شکل 3-9 الگوریتم ScaleTaskSet 43 شکل 3-10 شبه کد الگوریتم RBound-FF 45 شکل 3-11 الگوریتم اختصاص دادن وظایف در مرجع [35] 46 شکل 3-12 مدل سیستم مرجع [36] 50 شکل 3-13 شبه کد الگوریتم ED3VFS 54 شکل 3-14 مثالی از بارگذاری غیرتعادلی 55 شکل3-15 مثالی از توزیع وظایف بیدرنگ 56 شکل 3-16 شبه کد الگوریتم توزیع وظایف TLDHLB 59 شکل 3-17 شبهکد الگوریتم جزبندی با WFD 61 شکل 3-18 شبه کد زمانبند پیشنهادی در [37] 62 شکل 3-19 شبهکد سیاست اجرای EDF 62 شکل 3-20 شبهکد سیاست زمانبندی TBS و EDF 63 شکل 3-21 شبهکد روش مهاجرت وظایف غیرتناوبی در [37] 63 شکل 3-22 نمودار زمانی مثال مربوطه در [37] 65 شکل 4-1 ساختار کلی زمانبندی سیستم پیشنهادی 67 شکل 4-2 مدل سیستم پیشنهادی 70 شکل 4-3 شبهکد الگوریتم توزیع وظایف تناوبی 76 شکل 4-6 شبهکد الگوریتم پیشنهادی توزیع وظایف غیرتناوبی 80 شکل 4-7 فلوچارت الگوریتم پیشنهادی توزیع وظایف غیرتناوبی 81 شکل 4-8 نمودار زمانی اجرای یک وظیفه با الگوریتم تنظیم فرکانس پیشنهادی 84 شکل 5-1 مقایسه انرژی مصرفی حالتهای مختلف نسبت تفکیک هستهها برای وظایف تناوبی و غیرتناوبی 93 شکل 5-2 انرژی مصرفی الگوریتم پیشنهادی در شش مجموعه وظیفه مختلف 94 شکل 5-3 مقایسه انرژی مصرفی الگوریتم پیشنهادی با الگوریتمهای LU-McEP و PDAMS 95 شکل 5-4 مقایسه انرژی مصرفی الگوریتم پیشنهادی با الگوریتمهای LU-McEP و PDAMS در 6 مجموعه وظیفه مختلف 96 شکل 5-5 مقایسه نرخ نقض سررسید وظایف در همه حالتهای ممکن الگوریتم پیشنهادی 97 شکل 5-6 مقایسه میزان نرخ نقض سررسید الگوریتم پیشنهادی با الگوریتمهای LU-McEP و PDAMS 98 شکل 5-7 مقایسه میزان نرخ نقض سررسید الگوریتم پیشنهادی ما با الگوریتمهای LU-McEP و PDAMS را در تمام حالتها 99 شکل 5-8 مقایسه زمان پاسخ وظایف غیرتناوبی الگوریتم ما با الگوریتمهای LU-McEP و PDAMS 100 شکل 5-9 مقایسه متوسط زمان پاسخ وظایف غیرتناوبی الگوریتم ما با الگوریتمهای LU-McEP و PDAMSدر همه حالتها 101 شکل 5-10 مقایسه متوسط زمان انتظار وظایف غیرتناوبی الگوریتم پیشنهادی ما نسبت به الگوریتمهای LU-McEP و PDAMS 102 فهرست جدول¬ها جدول 2-1 خلاصهای از مشخصههای یک سیستم تعبیهشده بیدرنگ 10 جدول 3-2 مشخصات وظایف تناوبی در مثال مربوطه در [37] 64 جدول 3-3 مشخصات وظایف غیرتناوبی در مثال مربوطه در [37] 64 جدول 4-1 فرکانسها و توان متناظر هر سطح فرکانسی 85 جدول 4-2 مثال عددی از الگوریتم تنظیم فرکانس سررسیدمحور پیشنهادی 86 جدول 5-1 مشخصات پردازنده چندهستهای PowerPC 405PL شرکت IBM 89 چکيده امروزه با پیشرفت¬های چشمگیر در صنعت الکترونیک و نیاز روزافزون به تکنولوژی¬های کنترلی، کاربرد و اهمیت سیستم¬های تعبیهشده نیز بیشتر شده است تا جاییکه سیستم¬های تعبیهشده از مهمترین زمینه¬های پژوهشی در سالهای اخیر محسوب می¬شوند. در اکثر مواقع، عملیات در یک سیستم تعبیهشده باید در زمان کوتاه و مناسبی اجرا شوند، از اینرو عموماً اکثر سیستم¬های تعبیهشده، بی¬درنگ می¬باشند. تجهیزات نظامی و صنعتی، تلفن همراه و کاربردهای تجاری همچون دستگاههای خودپرداز و سیستم¬های هوشمند، نمونههایی از سیستم¬های تعبیهشده بی¬درنگ می¬باشند. علاوه بر بی¬درنگ بودن، مصرف انرژی مناسب نیز یکی دیگر از مشخصه¬های اصلی سیستم¬های تعبیهشده می¬باشد که یک مسئله اساسی پیش روی طراحان سیستم-های دیجیتال محسوب می¬شود. یکی از مسائل مهم در سیستم¬های چند هسته¬ای زمانبندی وظیفه¬ها و اجرای آنها توسط هسته¬های موجود است. برخلاف سیستم¬های تک هسته¬ای که مسئله زمانبندی فقط در مورد زمان می¬باشد، در سیستم¬های چند هسته¬ای این مسئله یک مسئله دو بعدی است و علاوه بر زمان ، مکان و فضای اجرای هسته¬ها را هم شامل می¬شود، یعنی تصمیم¬گیری می¬شود که یک وظیفه چه زمانی و توسط کدام هسته اجرا شود و هدف آن استفاده بهینه از توان پردازشی موجود، افزایش بازده و حداقل کردن زمان پاسخ سیستم است. در این پایان نامه ما بروی چهار مشکل اصلی در این نوع سیستم ها تمرکز می¬کنیم: مصرف انرژی ، بهرهوری سیستم، کارایی سیستم، زمان پاسخ سیستم. یکی از مهم ترین مسائلی که روی تمامی این چهار مشکل تاثیر مستقیم دارد نحوه توزیع بار بین منابع موجود است که در اینجا منظور از منابع، هسته¬های یک پردازنده چند هسته¬ای می¬باشد. یک توزیع ناکارامد بار روی هسته¬ها باعث مصرف انرژی بیشتر و پایین آمدن بهره¬وری و کارایی کل سیستم می¬شود. بیشتر روش¬هایی که تاکنون ارائه شدهاند، بدون توجه به نوع وظیفه، آنها را بین پردازنده¬ها توزیع می-کنند و بیشتر به تمرکز روی روش¬های تنظیم فرکانس و ولتاژ هر هسته بسنده می¬کنند. الگوریتم پیشنهادی ما در این پروژه، یک الگوریتم سه سطحی می¬باشد که در سطح اول یک روش جدید برای تفکیک وظایف تناوبی از وظایف غیرتناوبی متناسب با تعداد هسته¬های موجود ارائه می¬شود. سطح دوم از دو قسمت تشکیل می¬شود. در قسمت اول یک الگوریتم جدید برای توزیع وظایف تناوبی بین هسته¬های مربوط به آن ها که در سطح اول الگوریتم مشخص شده، ارائه می¬شود و در قسمت دوم الگوریتم توزیع وظایف غیرتناوبی بین هسته¬های مشخص شده برای آنها ، مطرح می¬شود. در سطح سوم الگوریتم جدیدی برای تنظیم فرکانس و ولتاژ سررسید محور بیان می¬کنیم. نتایج شبیه¬سازی نشان می¬دهد که الگوریتم پیشنهادی ما در مقایسه با الگوریتمهای موجود، در حین اینکه باعث کاهش مصرف انرژی کل سیستم می-شود، بهره¬وری و کارایی سیستم و همچنین زمان پاسخ وظایف غیر تناوبی را بهبود بخشیده است و با توجه به تامین سررسیدهای زمانی بیشتر برای وظایف تناوبی وکاهش زمان پاسخ وظایف غیرتناوبی با حفظ میزان کارایی و پایین بودن نسبی مرتبه زمانی اجرای الگوریتم، کیفیت سیستم افزایش پیدا خواهد کرد. کلمات کلیدی : زمانبندی، وظایف بیدرنگ، پردازندههای چند هستهای ، سیستم¬های تعبیهشده فصل اول فصل اول :مقدمه 1-1 پيشگفتار سیستمهای تعبیهشده یکی از بخشهای اصلی زندگی ما هستند و نقش مهمی در آسان نمودن زندگی مدرن ما ایفا میکنند. از تلفنهای هوشمند که امکانات متنوعی را در اختیار کاربران قرارمیدهند گرفته تا لوازم منزل، آسانسورها، ترمز در یک خودرو و سیستم های هدایت موشک همگی نمونه هایی از سیستم های تعبیهشده هستند. امروزه بیش از 98 درصد تمام پردازندههای تولیدشده در جهان در سیستمهای تعبیهشده استفاده شده است. این پردازشگرهای تعبیهشده در نگاه اول کاربر، قابل مشاهده نیستند؛ در هرصورت عملکرد صحیح آنها برای درست کار کردن هرسیستمی ضروری است. در اکثر مواقع عملیات در یک سیستم تعبیهشده باید در زمان کوتاه و مناسبی اجرا شوند. از این رو اکثر سیستمهای تعبیهشده، بیدرنگ میباشند، بنابراین زمان پاسخ در سیستم های تعبیهشده بیدرنگ از اهمیت بالایی برخوردار است. علاوه بر بیدرنگ بودن و اهمیت زمان پاسخ، مصرف انرژی کم نیز یکی از مهمترین ویژگیهای یک سیستم تعبیهشده می باشد.از دیگر ویژگیهای یک سیستم تعبیهشده می توان به تولید گرمای پایین و هزینه کم اشاره کرد. مبحث انرژی و توان مصرفی مانع از افزایش سرعت مخصوصا در سیستمهای چندهستهای میشود. سیستمهای بیدرنگ می توانند بهره خوبی از پردازندههای چندهستهای ببرند، یعنی وظیفههای مستقل میتوانند به طور همزمان اجرا شوند و خیلی سریع باهم بین هستهها ارتباط برقرار کنند. یکی از مسائل مهم در سیستمهای چندهستهای که تاثیر مستقیم روی مصرف انرژی، زمان پاسخ،کارایی و بهرهوری سیستم دارد، زمانبندی وظیفهها و اجرای آنها توسط هستههای موجود است. بنابراین به زمانبندیهایی احتیاج داریم که بتوانند با یک توزیع بار مناسب بین هستهها و روش مطلوب زمانبندی در هر کدام از هستهها، به مصرف انرژی پایین، زمان پاسخ حداقل، بهرهوری مناسب و کارایی بالا در یک سیستم بیدرنگ تعبیهشده دست پیدا کنند. 1-2 توصيف مسئله یکی از اساسیترین مفاهیم در سیستمهای تعبیهشده بیدرنگ، زمانبندی، سیاست و نحوه توزیع وظایفی است که در سیستم وارد یا ایجاد می شوند. این مسئله باید باتوجه به نوع کاریرد یک سیستم تعبیهشده، حساسیتها ومحدودیتها، در مرحله طراحی سیاستگذاری شود. به طور کلی زمانبندی میبایست دارای خصوصیات اولیهای باشد که این خصوصیات در جهت کاربرد سیستم نمایان می شوند. از آنجا که سیستمهای بیدرنگ سطح وسیعی از سیستمهای موجود را شامل میشوند، نوع زمانبندی اجرای وظایف در آنها اهمیت زیادی دارد که محدودیت زمانی بین همه آنها مشترک است. در سیستمهای چندهستهای برخلاف سیستمهای تک هستهای که مسئله زمانبندی فقط در مورد زمان میباشد، این موضوع یک مسئله دوبعدی است و علاوه بر زمان، مکان و فضای اجرای وظایف در یکی از هسته ها را هم شامل می شود. یعنی تصمیمگیری می شود که یک وظیفه چه زمانی و توسط کدام هسته اجرا شود و هدف آن استفاده بهینه از توان پردازشی موجود، افزایش بازده و حداقل کردن زمان پاسخ سیستم است. در برخی سیستمها هم بار کاری زیادی به سیستم وارد می شود، بنابراین باید جلوی مسئله اضافه بار را گرفت تا سیستم وظیفههایی که در حال اجرا و در صف اجرا قرار دارد را به درستی و در زمان مقرر به اتمام برساند. اگر بار کاری زیاد از حد باشد ممکن است برخی سررسیدها از دست برود و درنتیجه کارایی یک سیستم بیدرنگ زیر سوال برود. بنابراین یک توزیع مناسب وظایف بین هستهها و زمانبندی کارامد میتواند این مشکل را کمتر کند. در برخی از کاربردها، زمان پاسخ سیستم از اهمیت بالایی برخوردار است وهر چه سریعتر تعداد وظایف بیشتری را انجام دهد، به رضایت بیشتر کاربر منجر میشود. با فراگیر شدن سیستمهای نهفته میزان مصرف انرژی سیستم نیز بشدت مورد توجه قرار گرفته است. وجود محدودیت در انرژی باطری در سیستمهای نهفته قابل حمل، جلوی افزایش سرعت پردازندهها را گرفته است، بنابراین وجود راهکاری در این گونه سیستمها که بتواند مصرف انرژی را همزمان با افزایش بهره وری و کارایی بهبود دهد، میتواند پیشرفت بزرگی محسوب شود. در این تحقیق ما روشی را برای توزیع بار بین هستهها و زمانبندی وظایف درهریک از هستهها ارائه می دهیم تا بتوانیم پارامترهای مهم انرژی مصرفی، زمان پاسخ، کارایی سیستم و بهره وری آن را بهبود ببخشیم. راهکاری که ما ارائه دادهایم در واقع به نوع ماهیت یک وظیفه اهمیت می دهد و براساس تناوبی یا غیرتناوبی بودن آن، شالوده و اهداف الگوریتم پیشنهادی شکل می گیرد. این تفکیک وظایف به خاطر ماهیت هر کدام از این نوع وظایف است، دغدغه ما در این پژوهش این است که بتوانیم یک نوع تعادل بین انرژی مصرفی و کارایی سیستم برقرار کنیم. یعنی با ارائه یک زمانبندی برای وظایف سیستم، آنها را طوری بین هستهها توزیع کنیم که حداقل انرژی مصرفی و همزمان با آن بهترین کارایی برای سیستم را به دنبال داشته باشد. 1-3 ساختار پايان نامه در فصل اول به صورت مختصر به اهمیت، دغدغهها و کاربردهای مختلف سیستمهای تعبیهشده و مشخصههای کاربردی آن پرداخته میشود و پس از آن به سراغ توصیف مسئله رفته واهمیت آن را بیان میکنیم. در پایان نیز خلاصهای از ساختار بخشها و فصلهای مختلف پایاننامه را شرح میدهیم. در فصل دوم، مفاهیم و تعاریف اولیه که برای درک مسئله اهمیت دارد را به تفصیل شرح داده و بررسی میکنیم. ابتدا سیستمهای تعبیهشده را تعریف کرده و مهمترین خواص این سیستمها را به طور کامل شرح میدهیم. سپس به بیان اهمیت مصرف انرژی در سیستمهای تعبیهشده میپردازیم و بیان خواهیم کرد که چطور یک توزیع مناسب وظایف بین هستههای یک پردازنده چندهستهای، میتواند باعث کاهش انرژی مصرفی در سیستم مخصوصا سیستمهایی که دارای محدودیت منبع تامینکننده انرژی هستند، شود. سپس سیستمهای بیدرنگ را توضیح داده و انواع سیستمهای بیدرنگ از نظر محدودیت زمانی را بیان میکنیم. سپس تابع سودمندی در یک سیستم بیدرنگ را با توجه به نوع ماهیت وظایف بیان کرده و رسم میکنیم. سپس به تعریف یک وظیفه پرداخته و حالتهای مختلفی که یک وظیفه میتواند در طول حیاتش در سیستم تجربه کند را با رسم شکل بیان میکنیم. پس از آن وظیفه بیدرنگ و مشخصههای مهم آن را بیان میکنیم و انواع وظایف بیدرنگ را بر اساس فرکانس آزاد شدنشان شرح میدهیم. سپس به تعریف سررسید یک وظیفه پرداخته و انواع آن را بر اساس وابستگی آن به زمان آزاد شدن و همچنین وابستگی آن به دوره تناوب وظیفه شرح میدهیم. پس از تعریف هسته پردازنده در یک سیستم چندهستهای و منابع در یک سیستم تعبیهشده، به بررسی مفاهیم زمانبندی و اصطلاحات مختلف در زمانبندی یک سیستم میپردازیم و در نهایت سیستمهای چندهستهای را تعریف کرده و ویژگیها و عملکرد آنها را شرح میدهیم. در فصل سوم ابتدا به طبقهبندی انواع روشهای زمانبندی تکهستهای میپردازیم و سپس چندتا از الگوریتمهای معروف زمانبندی تک هستهای را شرح میدهیم. سپس انواع معماری سیستمهای چندهستهای را تشریح میکنیم و پس از آن به توصیف طبقهبندی انواع روشهای زمانبندی چندهستهای و مزایا و معایب هرکدام خواهیم پرداخت. سپس روشهای زمانبندی مبتنی بر تنظیم فرکانس و ولتاژ را بیان میکنیم و در نهایت به شرح کامل الگوریتمهای زمانبندی چندهستهای ارائه شده در مقالههای مرتبط گذشته میپردازیم و مزایا و معایب آنها را تحلیل میکنیم. در فصل چهارم الگوریتمی برای توزیع و زمانبندی وظایف در یک سیستم چندهستهای پیشنهاد خواهد شد. این الگوریتم شامل سه سطح است، سطح اول تفکیک وظایف و هستههای متناسب با آنها، سطح دوم الگوریتمی برای توزیع واختصاص وظایف بین هستهها و سطح سوم، یک الگوریتم انرژی- سررسید محور، برای تنظیم فرکانس هستهها متناسب با سررسید و زمان اجرای وظایف میباشد. در این فصل ابتدا جایگاه الگوریتم پیشنهادی خود را در بین طبقهبندی انواع الگوریتمهای زمانبندی چندهستهای مشخص میکنیم و سپس ساختار کلی زمانبندی پیشنهادی خود را با رسم شکل دقیق آن بیان میکنیم. سپس به بیان کلیات الگوریتم پیشنهادی خود پرداخته و مدل وظیفه و تمامی مشخصههای آن در الگوریتم خود را تشریح میکنیم. سپس مدل سیستم پیشنهادی خود را بیان میکنیم و بعداز آن به شرح کامل همراه با جزئیات الگوریتم پیشنهادی خود میپردازیم. در فصل پنجم نحوه شبیه سازی، محیط آن و شرایط سیستم شرح داده خواهد شد و نتایج آزمایش و مقایسه با دیگر روشها بیان خواهد شد. ابتدا به بیان تنظیمات اولیه شبیهسازی خواهیم پرداخت و سپس محیط شبیهسازی و زبان برنامه نویسی مورد استفاده برای شبیهسازی را بیان خواهیم کرد. سپس به ارزیابی مصرف انرژی، میزان نقض سررسید، متوسط زمان پاسخ وظایف غیرتناوبی و متوسط زمان انتظار آنها در الگوریتم پیشنهادی در مقایسه با دیگر الگوریتمها با نشان دادن نمودار خواهیم پرداخت. در فصل ششم به بیان نتیجهگیری نهایی این پژوهش پرداخته خواهد شد و پیشنهاداتی برای کارهای آینده ارائه میشود.