۰٫۶

T3

۱۰

۶

۰٫۶

شکل ۳-۵ مثالی کمی متفاوت از مثال قبلی ، که با رویکرد جزءبندی، قابل زمانبندی نیست]۲۱[
شکل ۸شکل ۳-۵ مثالی کمی متفاوت از مثال قبلی ، که با رویکرد جزءبندی، قابل زمانبندی نیست.[۲۱]
از دید نظری، کران‌های بهره‌وری شناخته‌شده تاکنون(که ضمانت می‌کنند، قادر به زمانبندی مجموعه وظایفی با فاکتور بهره‌وری داده‌شده، هستند ) برای نسخه‌های جزءبندی EDF و RMS ، محافظه‌کار می‌باشند. در حالت کلی، هیچ الگوریتم جزءبندی شده‌ای، دارای بدترین حالت بهره‌وری روی m پردازنده، بیشتر از ندارد. توجه شود که m+1 وظیفه، هرکدام با بهره‌وری نمی‌تواند بروی m پردازنده جزءبندی شود. در صورتیکه۰ ⇾ϵ ، کل بهره‌وری چنین مجموعه وظایفی به سمت ، میل خواهد‌کرد]۲۱[ .

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

بطور کلی کران‌های بهره‌وری بهتر، می‌تواند توسط ایجاد محدودیت‌هایی روی بهره‌وری هر وظیفه، ایجاد شود. فرض کنید UMax بیشترین بهره‌وری هر وظیفه در مجموعه وظایف است، هر وظیفه می‌تواند به یک پردازنده که ظرفیت مجزایی از حداکثر UMax دارد، اختصاص یابد. این بدین معنی است که اگر یک مجموعه از وظایف قابل زمانبندی نباشند، دراین صورت هر پردازنده باید یک ظرفیتی حداقل به اندازه UMax داشته باشد. از این رو کل بهره‌وری چنین مجموعه وظیفه‌ای، بیشتر از m(1-UMax)+UMax خواهدبود. به عبارتی هر مجموعه وظیفه با حداکثر بهره‌وری به میزان m-(m-1)UMax ، قابل زمانبندی است]۲۱[ . در شکل ۳-۶ نمودار تقسیم بندی الگوریتم‌های زمانبندی چندهسته‌ای نشان داده شده است.
الگوریتم‌های زمانبندی چندهسته‌ای
مهاجرتی محدود(دوگانه)
کاملا مهاجرتی (عمومی)
بدون مهاجرت( جزبندی )
شکل ۳-۶ طبقه‌بندی الگوریتم‌های زمانبندی چندهسته‌ای ]۲۱[
شکل ۹شکل ۳-۶ طبقه‌بندی الگوریتم‌های زمانبندی چندهسته‌ای
۳-۵ زمانبندی چند هسته‌ای مبتنی بر DVFS[115]
در طی سال‌های گذشته تولیدکنندگان برای بهبود عملکرد پردازنده‌ها، از طریق بالابردن فرکانس ساعت پردازنده‌ها، باهم رقابت می‌کردند. اما تحت تکنولوژی‌های ساخت و فرایندساخت پردازنده، بالاترین فرکانس کاری یک پردازنده مبتنی بر CMOS [۱۱۶]، به بالاترین ولتاژ منبع احتیاج دارد. از آنجا که ولتاژ منبع تغذیه تاثیر مستقیمی روی سرعت پردازنده دارد، زمانبندی وظایف و انتخاب ولتاژ منبع باید همزمان مورد توجه قرار گیرد ]۲۷[ .
توان مصرفی پویای ( Pdynamic) یک پردازنده مبتنی بر CMOS ، با فرکانس کاری و ولتاژ منبع رابطه مستقیم دارد، یعنی:
(۳)
بنابراین افزایش فرکانس کاری، فقط باعث افزایش بهره‌وری نمی‌شود، بلکه باعث می‌شود توان مصرفی نیز افزایش یابد. با توجه به این حقیقت که دستگاه‌هایی که از باطری‌های قابل حمل استفاده ‌می‌کنند، دارای انرژی محدودی هستند، تحقیقات روی ذخیره توان، توجه زیادی را به خود جلب کرده است که اغلب آن‌ها از تکنیک‌های DVFS برای افزایش طول عمر باطری دستگاه‌های قابل حمل استفاده کرده اند ]۲۸[ .
DVFS ولتاژ منبع و فرکانس کاری پردازنده را به صورت همزمان کاهش می‌دهد تا بتواند زمانی که ما نیاز به بهره‌وری کمی داریم، انرژی را ذخیره کند. همانند مغز انسان که مقدار زیادی انرژی مصرف می‌کند، پردازنده یک سیستم نیز انرژی زیادی را مصرف می‌کند. بنابراین معماری‌های چندهسته‌ای می‌توانند بهره زیادی از تکنولوژی DVFS ببرند ]۲۹[ .
در سیستم‌های چندهسته‌ای اولیه، همه هسته‌های پردازنده دارای یک ساعت مشترک بودند. تحت این معماری، هنوز DVFS می‌تواند باعث ذخیره انرژی شود، اما محدودیت‌های زیادی در این بین وجود دارد که ایجاد توازن بین کارایی و توان مصرفی را سخت‌تر کرده است. در پردازنده‌های امروزی هر هسته می‌تواند با فرکانس و ولتاژ متفاوتی کار کند. این پردازنده‌ها در دو مدل وجود دارند، حالت بسته[۱۱۷] و حالت برخط[۱۱۸]. در حالت بسته، فرکانس هسته‌های پردازنده نمی‌تواند در حین اجرای یک وظیفه تغییر کند و فقط در ابتدا که وظیفه اجرایش آغاز می‌شود، می‌تواند تغییر کند. اما در حالت برخط، فرکانس هسته‌ها می‌تواند در هر لحظه از اجرای وظیفه تغییر کند ]۳۰[ .
دو استراتژی برای استفاده از تکنیک‌های DVFS برای کاهش مصرف انرژی وجود دارد:

  • تغییر ولتاژ و فرکانس در زمان سکون وظیفه[۱۱۹]
  • تغییر ولتاژ و فرکانس در هنگام دسترسی به منابع خارجی

در روش اول که تغییر ولتاژ و فرکانس در زمان سکون وظیفه می باشد (منظور از زمان سکون وظیفه، مدت زمانی است که وظیفه در صف آماده پردازنده منتظر می‌شود تا اجرایش آغاز شود یا ادامه پیدا کند)، وقتی که پردازنده شروع به اجرای وظیفه می‌کند، فرکانس اجرایی آن در نسبت بین بدترین حالت زمان اجرا و سررسید وظیفه، ضرب می‌شود تا با این کار فرکانس اجرایی آن کاهش یافته و در نتیجه توان مصرفی کاهش یابد. مثالی از این حالت را در شکل۳-۷ مشاهده می‌کنید.
شکل ۳-۷ نمونه‌ای از تنظیم فرکانس و ولتاژ در زمان سکون وظیفه، الف) بدون , DVFS ب) با DVFS
شکل ۱۰شکل ۳-۷ نمونه‌ای از تنظیم فرکانس و ولتاژ در زمان سکون وظیفه، الف) بدون , DVFS ب) با DVFS
در مرجع ]۳۱[ روشی پیشنهاد شده که در آن از ترکیب دو مولفه برخط و برون خط استفاده شده تا هم قید زمانی را در نظر بگیرند و هم انرژی مصرفی را کاهش دهند. در این روش، مولفه برون‌خط، کمترین سزعت ممکن پردازنده را پیدا می‌کند که در این سرعت پایین، همچنان همه قیود زمانی بهبود داشته است. از سوی دیگر مولفه برخط به صورت پویا سرعت عملیاتی را تغییر می‌دهد تا انرژی و توان بیشتری ذخیره شود. بنابراین زمان اجرای وظیفه، ممکن است کمی تغییر کند.
در مرجع ]۳۲[ نیز از یک وقفه برای بروز رسانی فرکانس مناسب استفاده شده تا تغییرات ناگهانی حجم‌بار، در نظر گرفته شود. در این الگوریتم از داده‌های مربوط به تاریخچه برای پیشبینی حجم‌بار بعدی استفاده می‌شود و سپس با توجه به خطای پیشبینی[۱۲۰]، نرخ بروز رسانی فرکانس، تنظیم می‌شود.
روش دوم که تغییر فرکانس و ولتاژ در هنگام دسترسی به منابع خارجی است، هنگامی استفاده می‌شود که وظایف ما دارای محدودیت حافظه و I/O (ورودی/خروجی) باشند. می‌دانیم که سرعت عملیاتی حافظه و لوازم جانبی بسیار کمتر از پردازنده است، بنابراین برای وظایفی که مکرراً باید منتظر رسیدن مقادیرشان از حافظه یا I/O هستند، فرکانس عملیاتی پردازنده می‌تواند کاهش پیدا کند ]۳۳[ . بنابراین تا وقتی که پردازنده منتظر مقادیر خارجی برای پایان دادن به وظیفه مورد است، توان کمتری مصرف می‌شود.
۳-۶ بررسی کارهای گذشته
در این بخش به بررسی و شرح کامل چند الگوریتم پیشنهاده‌شده مهم زمانبندی و توزیع وظایف در سیستم‌های تعبیه‌شده چند هسته‌ای خواهیم پرداخت و همچنین مزایا و معایب آن‌ها را را بیان می‌کنیم.
۳-۶-۱ الگوریتم توزیع بار غیر تعادلی LU-McEP[121]
یکی از کارهایی که برای کاهش مصرف انرژی و توان پردازنده‌های چندهسته‌ای تعبیه‌شده انجام شده، روش پیشنهادی در مرجع ]۳۴[ بوده که یک روش بارگیری نامتعادل[۱۲۲] است که وظایف را به دو دسته تناوبی و غیرتناوبی تقسیم می‌کند.در این روش، وظایف تناوبی به حداقل هسته‌ها متمرکز می‌شوند تا بقیه هسته‌ها بتوانند خاموش بمانند. برای اینکه هیچ سررسیدی از دست نرود، این روش از دو الگوریتم زمانبندی استفاده کرده است که یکی RMS و دیگری SQ [۱۲۳] می‌باشد. RMS برای متمرکز کردن وظایف تناوبی استفاده شده است و برای اینکه بفهمد که یک وظیفه تناوبی، امکان متمرکزسازی دارد یا نه از حد آستانه بهره‌وری[۱۲۴] استفاده می‌کند تا تعیین کند که یک وظیفه تناوبی چقدر قابلیت متمرکز سازی دارد. رابطه حد آستانه بهره‌وری به صورت زیر است:
(۴)
که در آن، n تعداد کل وظایف تناوبی است، C زمان اجرای هر وظیفه و T دوره‌تناوب هر وظیفه می‌باشد.
از الگوریتم SQ در این روش برای توزیع وظایف غیرتناوبی روی هسته‌های باقیمانده استفاده شده است. در SQ یک وظیفه جدید به هسته‌ای که کمترین تعداد وظایف را دارد، فرستاده می‌شود.
مهم‌ترین چیز برای سنجیدن کارایی وظایف تناوبی، اجرای قبل از سررسید آن می‌باشد، تا اجرای سریع آن‌ها. یعنی در وظایف تناوبی مشکل زمان انتظار نسبت به سررسید خیلی مهم نیست. در مقابل در وظایف غیرتناوبی که کمتر اتفاق می‌افتند و خیلی زود در آینده‌ای نزدیک رخ نمی‌دهند( مانند ورودی‌های کاربر، از قبیل لمس‌کردن صفحه نمایش لمسی و باز کردن یک برنامه کاربردی )، از روش توزیع بار استفاده می‌کنیم. وقتی کار یک وظیفه غیرتناوبی تمام می‌شود، هسته متناظرش می‌تواند خاموش شود، همچنین حافظه نهان آن هسته نیز می‌تواند خاموش شود، چون وظیفه از نوع غیرتناوبی است و قرار نیست تا آینده‌ای نزدیک دوباره تکرار شود. همچنین از آنجایی که زمان پاسخ از سررسید در این وظایف مهم‌تر است، به علت توزیع این وظایف بین بقیه پردازنده‌ها، زمان پاسخ‌دهی آن‌ها کاهش می‌یابد.
دو روش در مدیریت توان به عنوان نماینده‌ای از بقیه روش‌ها وجود دارد:

  • DVS [۱۲۵]
موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...