فایل زمانبندی وظایف در سیستم¬های تعبیه¬شده بی¬¬درنگ برداشتگر انرژی با هدف کاهش نرخ خطای سررسید

جزئیات و دریافت

این پایان نامه در قالب فرمت word قابل ویرایش ، آماده پرینت و ارائه به عنوان پروژه پایانی میباشد.

فهرست مطالب
عنوان                                                                                                                                                                               صفحه
فهرست مطالب    ...............................................................................................................................................................هشت
چکیده    ..................................................................................................................................................................................1
فصل اول: توصیف مسئله
1-1 مقدمه    2
1-2  ساختار پایان نامه    4
فصل دوم : مفاهیم اولیه
2-1  مقدمه    6
2-2 سیستمهای تعبیه شده    6
2-3  سیستم بی درنگ    8
2-4  زمانبندی وظایف    9
2-4-1  انواع زمانبندی    9
2-5  تعاریف اولیه    10
2-6  الگوریتمهای زمانبندی اولیه    12
2-6-1  الگوریتم زمانبندی نزدیکترین سررسید اول (EDF)    12
2-6-2  الگوریتم زمانبندی نرخ یکنواخت (RMS)    13
2-7  برداشت انرژی محیطی    14
2-7-1  اجزای سیستم تعبیه شده مبتنی بر برداشت انرژی    15
2-7-2  انواع سیستم برداشتگر انرژی    16
2-8  مدیریت توان در سیستمهای تعبیه شده    19
2-9  نتیجه گیری    20
فصل سوم : بررسی منابع و کارهای انجام شده
3-1 مقدمه    21
3-2  الگوریتمهای زمانبندی سیستم تعبیه شده بدون برداشتگر انرژی    22
3-2-1  الگوریتم زمانبندی MILP وLEDF    23
3-3  عوامل مشترک در زمانبندی سیستمهای بیدرنگ برداشتگر انرژی    24
3-4  الگوریتمهای زمانبندی سیستم تعبیه شده مبتنی بر برداشتگر انرژی    25
3-4-1 روش زمانبندی LSA    25
3-4-2  روش زمانبندی EA-DVFS    30
3-4-3  روش  زمانبندی AS-DVFS    33
3-4-4  روش زمانبندی LM-APM    35
3-4-5  روش زمانبندی HA-DVFS    41
3-4-6   الگوریتم انتخاب فرکانس باتوجه به وضعیت سیستم    48
3-5  نتیجه گیری    54
فصل چهارم : الگوریتم پیشنهادی
4-1 مقدمه    55
4-2  ذخیره ساز انرژی    56
4-2-1  مزایای ابرخازن در برابر باطری با قابلیت شارژ مجدد    56
4-2-2  معایب ابرخازن در برابر باطری با قابلیت شارژ مجدد    57
4-3  مدل سیستم    61
4-3-1  مدل برداشتگر انرژی    61
4-3-2  مدل پردازنده    61
4-3-3  مدل ذخیره ساز انرژی    62
4-3-4  مدل وظیفه    63
4-4  الگوریتم زمانبندی بیدرنگ    63
4-4-1  انتخاب بازه زمانی    65
4-4-2  محاسبه انرژی مورد نیاز برای اجرای وظایف موجود در بازه    65
4-4-3  محاسبه موجودیت انرژی    66
4-5  نتیجه گیری    74
فصل پنجم : شبیه سازی و نتیجه گیری
5-1 مقدمه    75
5-2 تنظیمات اولیه    75
5-3  مقایسه نرخ خطای سررسید    78
5-4  کمترین ظرفیت ذخیره سازی برای داشتن نرخ خطای سررسید صفر    85
5-5  سودمندی انرژی    87
5-6  نرخ خطای سررسید در حالت عدم وجود واحد ذخیره ساز انرژی    89
5-7 : بررسی سربار زمانبندی    89
5-8  نتیجه گیری    90
5-9  پیشنهادات    91
مراجع    92

فهرست شکل¬ها

شکل 1-1 : نمودار مشخصات یک وظیفه    11
شکل 2-1 : نوع اول سیستم برداشتگر انرژی    16
شکل3-1 : منحنی توان در روش LSA    26
شکل 3-2 : مدل سیستم روش LM-APM    36
شکل 3-3 :  شبه کد الگوریتم HA_DVFS قسمت تنظیم بارکاری پردازنده و انتخاب پویای ولتاژ و فرکانس    44
شکل 3-4 : زمانبندی دو وظیفه    45
شکل 3-5 : شبه کد الگوریتم بهره وری از انرژی سرریز شده    46
شکل 4-1 : اتصال دو باطری برای جداسازی فازهای شارژ و دشارژ    59
شکل 4-2: مدل سیستم پیشنهادی    61
شکل 4-3: محاسبه dl در حالت Edemand = EH(tc , Dmax) + ES(tc)    68
شکل 4-4 : شبه کد الگوریتم پیشنهادی    73
شکل 5-1 : نمودار توان برداشت PH(t)    76
شکل 5-2 : مقایسه نرخ خطای سررسید الگوریتم پیشنهادی با سایر الگوریتم ها    79
شکل 5-3 نمودار خطی تغییرات نرخ خطای سررسید الگوریتم ها در مقادیر متفاوت بهره وری    80
شکل 5-4 :  4 نمونه گیری از انرژی خورشیدی    80
شکل 5-5 : مقایسه نرخ خطای سررسید برای 5000 مجموعه وظیفه    81
شکل 5-6 : مقایسه نرخ خطای الگوریتم ها در مقادیر مختلف ظرفیت باطری و بهره وری    83
شکل 5-7 : مقایسه نرخ خطای سررسید در حالت ذخیره ساز دوگانه و باطری    84
شکل 5-8 : مقایسه نرخ خطای سررسید در مقادیر مختلف ذخیره سازی باطری و ابرخازن    85
شکل 5-9 : مقایسه حداقل ظرفیت واحد ذخیره سازی برای داشتن خطای سررسید صفر    86
شکل 5-10: نمودار کارایی انرژی در مقادیر مختلف بهره وری    88
شکل 5-11 : مقایسه نرخ خطای سررسید در دو حالت صحت و حذف واحد ذخیره ساز انرژی    89

فهرست جدول¬ها

جدول 4-1 : مقایسه باطری و ابرخازن    58
جدول 4-2 : حالات کاری باطری های شکل4-1    59
جدول 5-1 : مشخصات پردازنده XScale اینتل    76
جدول 5-2: نرخ خطای سررسید الگوریتم HA-DVFS براساس شکل 5-4    80
جدول 5-3 : محاسبه سربار زمانبندی الگوریتم ها    90

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

کلمات کلیدی :  سیستم¬های تعبیه شده، برداشتگر انرژی، زمانبندی بی¬درنگ، ذخیره¬ساز انرژی غیرایده¬آل

فصل اول
فصل اول: توصیف مسئله

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

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