user8209

دانشگاه صنعتی اصفهان
دانشکده برق و کامپیوتر
زمان‌بندی وظیفه‌ها در سیستم‌های بی‌درنگ نهفته چند‌هسته‌ای با هدف بهبود انرژی مصرفی و کارایی
پایان نامه کارشناسی ارشد مهندسی کامپیوتر – معماری سیستم های کامپیوتری
حسین محمودی
استاد راهنما
دکتر محمدعلی منتظری
1394
2259965-40649100
دانشگاه صنعتی اصفهان
دانشکده برق و کامپیوتر
پایان‌نامه‌ی کارشناسی ارشد رشته‌ی مهندسی کامپیوتر – معماری سیستم‌های کامپیوتری آقای حسین محمودی
تحت عنوان
زمان‌بندی وظیفه‌ها در سیستم‌های بی‌درنگ نهفته چند هسته‌ای با هدف بهبود انرژی مصرفی و کارایی
در تاریخ 27/03/94 توسط کمیته‌ی تخصصی زیر مورد بررسی و تصویب نهایی قرار گرفت.
1- استاد راهنمای پایان‌نامهدکتر محمدعلی منتظری
2- استاد داوردکتر شادرخ سماوی
سرپرست تحصیلات تکمیلی دانشکدهدکتر سید محمدعلی خسروی‌فرد
تقدیر و تشکر
از یکتا خالق مهربان و قدرتمندم که در تمام لحظه‌های زندگی‌ام یاری دهنده از سر لطف و حکمت بوده و هست سپاس‌گذارم، خدایی که نور، گرما و جاذبه‌ی حضورش را در سراسر فضا-زمان زندگی‌ام حس می‌کنم.
خدای را بسی شاکرم که از روی کرم پدر و مادری فداکار نصیبم ساخته تا در سایه درخت پر بار وجودشان بیاسایم و از ریشه آنها شاخ و برگ گیرم و از سایه وجودشان در راه کسب علم و دانش تلاش نمایم . والدینی که بودنشان تاج افتخاری است بر سرم و نامشان دلیلی است بر بودنم چراکه این دو وجود پس از پروردگار مایه هستی ام بوده اند دستم را گرفتند و راه رفتن را در این وادی زندگی پر از فراز و نشیب آموختند.
از زحمات فراوان استاد راهنمای بزرگ و دلسوزم جناب دکتر محمدعلی منتظری کمال تشکر و قدردانی را دارم که در تمامی مراحل پروژه همواره حامی بنده بوده و دلسوزانه مرا راهنمایی کردند.
همچنین بر خود واجب می‌دانم از خواهران عزیزم که در تمام دوران تحصیلی‌ام تا دانشگاه همواره دلسوزانه حامی‌ام بودند و مرا به این مسیر علم و دانش هدایت کردند، کمال تشکر و قدردانی را داشته باشم.
عشق واژه ایست که پیچیده‌ترین فرمول‌های ریاضی و مهندسی از درک آن عاجزند، واژه‌ای که دوست، همکلاسی و همسرم برایم قابل فهم کرده است. همسری مهربان و دلسوز که محو سادگی شگفت‌انگیزش شده ام، همسری که در تمام مراحل این پروژه حامی‌ام بوده و از هیچ لطفی دریغم نکرده ‌است. بدین وسیله از حمایت‌ها و راهنمایی‌‌های او که آرامش را به من هدیه داده تشکر و قدردانی می‌کنم.
از آموزگارانم در تمام طول تحصیلم، که برایم زندگی، بودن و انسانیت را معنا کردند سپاسگذارم. بدون شک جایگاه و منزلت معلم، اجّل از آن است که در مقام قدردانی از زحمات بی شائبه ی او، با زبان قاصر و دست ناتوان، چیزی بنگاریم.
همچنین از راهنمایی‌های دوستان خوبم دکتر امین اباذری و محمدحسین کیانی که در طول پروژه حمایتم کردند کمال تشکر را دارم.
کلیه‌ی حقوق مادی مترتب بر نتایج مطالعات، ابتکارات و نوآوری‌های ناشی از تحقیق موضوع این پایان‌نامه (رساله) متعلق به دانشگاه صنعتی اصفهان است.
تقدیم به :
پدرم به استواری کوه،
مادرم به لطافت باران ،
و
دوست و همسرم به زلالی چشمه
که آفتاب مهرشان درون قلبم،همیشه پابرجاست و هرگز غروب نخواهد کرد.
2465705-41910فهرست مطالب
0فهرست مطالب

صفحهعنوان
فهرست مطالب...............................................................................................................................................................هشت
TOC \o "1-3" \h \z \u چکیده PAGEREF _Toc422592119 \h 1فصل اول :مقدمه1-1 پیشگفتار PAGEREF _Toc422592121 \h 21-2 توصیف مسئله PAGEREF _Toc422592122 \h 31-3 ساختار پایان نامه PAGEREF _Toc422592123 \h 4فصل دوم :مفاهیم اولیه2-1 سیستم های تعبیه‌شده PAGEREF _Toc422592125 \h 62-1-1 مصرف انرژی در سیستم‌های تعبیه‌شده PAGEREF _Toc422592126 \h 82-2 سیستم های تعبیه‌شده بی‌درنگ PAGEREF _Toc422592127 \h 92-2-1 انواع سیستم های بی‌درنگ از نظر محدودیت زمانی PAGEREF _Toc422592128 \h 112-2-2 تابع بهره‌وری در سیستم‌های بی‌درنگ PAGEREF _Toc422592129 \h 122-3 وظیفه PAGEREF _Toc422592130 \h 132-3-1 مدل وظیفه بی‌درنگ PAGEREF _Toc422592131 \h 142-3-2 دسته‌بندی وظایف بی‌درنگ PAGEREF _Toc422592132 \h 152-4 سررسید PAGEREF _Toc422592133 \h 162-5 هسته پردازنده PAGEREF _Toc422592134 \h 182-6 منابع PAGEREF _Toc422592135 \h 182-7 مفاهیم زمانبندی PAGEREF _Toc422592136 \h 192-7-1 تعاریف مربوط به مبحث زمانبندی PAGEREF _Toc422592137 \h 202-8 سیستم های چندهسته‌ای PAGEREF _Toc422592138 \h 212-9 نتیجه‌گیری PAGEREF _Toc422592139 \h 22فصل سوم : مرور منابع و کارهای انجام‌شده3-1 طبقه بندی روش‌های زمانبندی PAGEREF _Toc422592141 \h 233-2 الگوریتم‌های زمانبندی بی‌درنگ تک پردازنده PAGEREF _Toc422592142 \h 263-3 طبقه‌بندی معماری سیستم‌های چندهسته‌ای PAGEREF _Toc422592143 \h 293-4 زمانبندی بیدرنگ چندهسته‌ای PAGEREF _Toc422592144 \h 303-4-1 معایب روش‌های زمانبندی عمومی و جزبندی PAGEREF _Toc422592145 \h 323-5 زمانبندی چند هسته‌ای مبتنی بر DVFS PAGEREF _Toc422592146 \h 343-6 بررسی کارهای گذشته PAGEREF _Toc422592147 \h 373-6-1 الگوریتم توزیع بار غیر تعادلی LU-McEP PAGEREF _Toc422592148 \h 373-6-2 الگوریتم زمانبندی غیرتعادلی جزبندی با RBound PAGEREF _Toc422592149 \h 423-6-3 الگوریتم زمانبندی چند سطحی PDAMS PAGEREF _Toc422592150 \h 473-6-4 الگوریتم زمانبندی پیشنهادی در مرجع ]37[ PAGEREF _Toc422592151 \h 593-7 نتیجه‌گیری PAGEREF _Toc422592152 \h 65فصل چهارم : الگوریتم پیشنهادی4-1 جایگاه الگوریتم پیشنهادی PAGEREF _Toc422592154 \h 664-2 کلیات الگوریتم پیشنهادی PAGEREF _Toc422592155 \h 684-3 مدل وظیفه الگوریتم پیشنهادی PAGEREF _Toc422592156 \h 684-4 مدل سیستم الگوریتم پیشنهادی PAGEREF _Toc422592157 \h 694-5 شرح کامل الگوریتم پیشنهادی PAGEREF _Toc422592158 \h 714-5-1 بخش اول الگوریتم پیشنهادی (تفکیک وظایف و هسته‌ها) PAGEREF _Toc422592159 \h 714-5-2 بخش دوم الگوریتم پیشنهادی (توزیع وظایف بین هسته‌ها) PAGEREF _Toc422592160 \h 724-5-3 الگوریتم پیشنهادی تنظیم فرکانس سررسید محور (بخش سوم الگوریتم پیشنهادی) PAGEREF _Toc422592161 \h 834-6 نتیجه‌گیری PAGEREF _Toc422592162 \h 88فصل پنجم :شبیه‌سازی و ارزیابی الگوریتم پیشنهادی5-1 تنظیمات اولیه شبیه‌سازی PAGEREF _Toc422592164 \h 895-2 محیط شبیه‌سازی PAGEREF _Toc422592165 \h 915-3 ارزیابی انرژی مصرفی PAGEREF _Toc422592166 \h 92center674868نه
0نه
5-4 ارزیابی کارایی PAGEREF _Toc422592167 \h 975-4-1 ارزیابی نرخ نقض سررسید PAGEREF _Toc422592168 \h 975-4-2 ارزیابی متوسط زمان پاسخ وظایف غیرتناوبی PAGEREF _Toc422592169 \h 995-4-3 ارزیابی متوسط زمان انتظار وظایف غیرتناوبی PAGEREF _Toc422592170 \h 1015-5 نتیجه‌گیری PAGEREF _Toc422592171 \h 102فصل ششم : نتیجه‌گیری و پیشنهادات6-1 نتیجه‌گیری PAGEREF _Toc422592173 \h 1036-2 پیشنهادات PAGEREF _Toc422592174 \h 104مراجع PAGEREF _Toc422592175 \h 105واژگان اختصاری PAGEREF _Toc422592176 \h 108
center4137575ده
0ده

فهرست شکلها
TOC \h \z \c "شکل" شکل 2-1- تابع بهره‌وری u(t) برای انواع مختلف وظایف بی‌درنگ PAGEREF _Toc422763903 \h 13شکل 2-2- نمودار گذار حالت یک وظیفه PAGEREF _Toc422763904 \h 14شکل 2-3 سررسید متناظر و سررسید مطلق یک وظیفه PAGEREF _Toc422763905 \h 17شکل 3-1 تفسیم‌بندی انواع روش‌های زمانبندی PAGEREF _Toc422763906 \h 26شکل 3-2 مثالی از کاربرد زمانبندی تک هسته‌ای با استفاده از الگوریتم EDF PAGEREF _Toc422763907 \h 27شکل 3-3 بررسی اجمالی معماری پردازنده AMP و SMP PAGEREF _Toc422763908 \h 30شکل 3-4 مثالی از زمانبندی تولید شده امکان‌پذیر، از الگوریتم : الف) جزءبندی ب) کاملا مهاجرتی ج) مهاجرتی محدودشده PAGEREF _Toc422763909 \h 32شکل 3-5 مثالی کمی متفاوت از مثال قبلی ، که با رویکرد جزءبندی، قابل زمانبندی نیست PAGEREF _Toc422763910 \h 33شکل 3-6 طبقه‌بندی الگوریتم‌های زمانبندی چندهسته‌ای PAGEREF _Toc422763911 \h 34شکل 3-7 نمونه‌ای از تنظیم فرکانس و ولتاژ در زمان سکون وظیفه، الف) بدون DVFS ب) با DVFS PAGEREF _Toc422763912 \h 36شکل 3-8 شبه کد الگوریتم تخصیص وظایف PAGEREF _Toc422763913 \h 40شکل 3-9 الگوریتم ScaleTaskSet PAGEREF _Toc422763914 \h 43شکل 3-10 شبه کد الگوریتم RBound-FF PAGEREF _Toc422763915 \h 45شکل 3-11 الگوریتم اختصاص دادن وظایف در مرجع [35] PAGEREF _Toc422763916 \h 46شکل 3-12 مدل سیستم مرجع [36] PAGEREF _Toc422763917 \h 50شکل 3-13 شبه کد الگوریتم ED3VFS PAGEREF _Toc422763918 \h 54شکل 3-14 مثالی از بارگذاری غیرتعادلی PAGEREF _Toc422763919 \h 55شکل3-15 مثالی از توزیع وظایف بی‌درنگ PAGEREF _Toc422763920 \h 56شکل 3-16 شبه کد الگوریتم توزیع وظایف TLDHLB PAGEREF _Toc422763921 \h 59شکل 3-17 شبه‌کد الگوریتم جزبندی با WFD PAGEREF _Toc422763922 \h 61شکل 3-18 شبه کد زمانبند پیشنهادی در [37] PAGEREF _Toc422763923 \h 62شکل 3-19 شبه‌کد سیاست اجرای EDF PAGEREF _Toc422763924 \h 62شکل 3-20 شبه‌کد سیاست زمانبندی TBS و EDF PAGEREF _Toc422763925 \h 63شکل 3-21 شبه‌کد روش مهاجرت وظایف غیرتناوبی در [37] PAGEREF _Toc422763926 \h 63شکل 3-22 نمودار زمانی مثال مربوطه در [37] PAGEREF _Toc422763927 \h 65شکل 4-1 ساختار کلی زمانبندی سیستم پیشنهادی PAGEREF _Toc422763928 \h 67شکل 4-2 مدل سیستم پیشنهادی PAGEREF _Toc422763929 \h 70شکل 4-3 شبه‌کد الگوریتم توزیع