شکل ۴‑۹ ساختار کلی الگوریتم ژنتیک ۷۰
شکل ۴‑۱۰ انتخاب مسابقه‌ای دودویی ۷۱
شکل ۴‑۱۱ روش تقاطع تک نقطه‌ای ۷۲
شکل ۵‑۱ مدل کاربرد وسیله‌ی نقلیه‌ی خودمختار ۸۰
شکل ۵‑۲ همگرایی جواب‌ها با نرخ تقاطع ۵/۰ و نرخ جهش ۰۱/۰ بدون استفاده از توابع امکان‌پذیری و میزان بهرهوری در شبکه بر تراشه ۴×۴ ۸۹
شکل ۵‑۳ همگرایی جواب‌ها با نرخ تقاطع ۵/۰ و نرخ جهش ۰۱/۰ برای کاربرد وسیله‌ی نقلیه خودمختار در روش [۵۰] ۹۰
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
شکل ۵‑۴ همگرایی جواب‌ها با نرخ تقاطع ۵/۰ و نرخ جهش ۰۱/۰ با به کار بردن توابع امکان‌پذیری و میزان بهرهوری در شبکه بر تراشه ۴×۴ ۹۱
شکل ۵‑۵ همگرایی جواب‌ها با نرخ تقاطع ۵/۰ و نرخ جهش ۰۱/۰ بدون استفاده از توابع امکان‌پذیری و میزان بهرهوری در شبکه بر تراشه ۵×۵ ۹۳
شکل ۵‑۶ همگرایی جواب‌ها با نرخ تقاطع ۵/۰ و نرخ جهش ۰۱/۰ با به کاربردن توابع امکان‌پذیری و میزان بهرهوری در شبکه بر تراشه ۵×۵ ۹۴
شکل ۵‑۷ همگرایی جواب‌ها با نرخ تقاطع ۵/۰ و نرخ جهش ۰۱/۰ بدون استفاده از توابع امکان‌پذیری و میزان بهرهوری در شبکه بر تراشه ۳×۳ ۹۵
شکل ۵‑۸ همگرایی جواب‌ها با نرخ تقاطع ۵/۰ و نرخ جهش ۰۱/۰ با به کاربردن توابع امکان‌پذیری و میزان بهرهوری در شبکه بر تراشه ۳×۳ ۹۵
شکل ۵‑۹ همگرایی جواب‌ها با نرخ تقاطع ۵/۰ و نرخ جهش ۰۱/۰ با به کار بردن توابع امکان‌پذیری و میزان بهرهوری در شبکه بر تراشه ۴×۴ با دو برابر کردن وظایف ۹۶
شکل ۵‑۱۰ همگرایی جواب‌ها با نرخ تقاطع ۵/۰ و نرخ جهش ۰۱/۰ بدون استفاده از توابع امکان‌پذیری و میزان بهرهوری در شبکه بر تراشه ۴×۴ با دو برابر کردن وظایف ۹۷
شکل ۵‑۱۱ همگرایی جواب‌ها با نرخ تقاطع ۸/۰ و نرخ جهش ۰۱/۰ با به کار بردن توابع امکان‌پذیری و میزان بهرهوری در شبکه بر تراشه ۴×۴ ۹۷
شکل ۵‑۱۲ همگرایی جواب‌ها با نرخ تقاطع ۵/۰ ، نرخ جهش ۰۱/۰ و انتخاب مسابقه‌ای با اندازه‌ی ۳ با به کار بردن توابع امکان‌پذیری و میزان بهرهوری در شبکه بر تراشه ۴×۴ ۹۸
شکل ۵‑۱۳ همگرایی جواب‌ها با نرخ تقاطع ۵/۰ و نرخ جهش ۰۱/۰ با فرض همگن بودن شبکه بر تراشه ۹۸
فهرست جدولها
عنوان صفحه
جدول ۵‑۱ وظایف تشکیل دهنده‌ی کاربرد ۸۱
جدول ۵‑۲ جریان‌های ترافیکی بین وظایف کاربرد ۸۲
جدول ۵‑۳ مشخصات وظایف کاربرد ۸۵
جدول ۵‑۴ بدترین زمان اجرا و توان مصرفی هر یک از وظایف بر روی هستههای پردازشی ۸۶
جدول ۵‑۵ معیارهای استفاده شده در الگوریتم ژنتیک چندهدفه‌ی NSGA-II 88
جدول ۵‑۶ مقادیر توابع هدف در جبهه‌ی نامغلوب نهایی ۹۲
جدول ۵‑۷ خلاصه‌ای از نتایج ارائه شده بر روی شبکه‌های با ابعاد مختلف با نرخ جهش ۰۱/۰ و نرخ تقاطع ۵/۰ ۹۹
جدول ۵‑۸ خلاصه‌ای از نتایج الگوریتم پیشنهادی در برخی حالات خاص در شبکه بر تراشه ۴×۴ ۹۹
چکیده
امروزه با پیشرفت فنآوری نیمههادیها، تعداد مولفههای پردازشی در یک سیستم روی تراشه (SOC) افزایش یافته است. معماری ارتباطی در این قبیل سیستمها مبتنی بر گذرگاه میباشد. از این رو، با افزایش تعداد مولفههای پردازشی و با توجه به عدم کارایی و توسعهپذیری گذرگاه، مفهوم شبکه روی تراشه یا NOC به عنوان یک طرح ارتباطی درون تراشهای کارآمد و مقیاسپذیر، جهت غلبه بر مشکلات گذرگاهها مطرح شده است. یکی از چالشهای مهم در تحقیقات مربوط به NOCها، مسئله نگاشت وظایف یک برنامه کاربردی بر روی هستههای پردازشی متصل به مسیریابهای شبکه است که این هستهها میتوانند به صورت همگن یا ناهمگن باشند. از طرف دیگر، یکی از پرکاربردترین برنامه های کاربردی، برنامه های کاربردی تعبیه شده با نیازمندیهای زمانی بیدرنگ میباشند. در بسیاری از کارهای انجام شده، به مسئله نگاشت بر روی هستههای پردازشی همگن پرداخته شده است و سعی در ارائه راه حل کارآمد کرده اند. اما تقریبا در اکثر طرحهای پیشنهاد شده، ویژگی ناهمگن بودن هستهها علیرغم آنکه به واقعیت نزدیکتر است، نادیده گرفته شده است. همچنین ویژگی بیدرنگ بودن کاربردها، مورد توجه عمده کارهای پژوهشی انجام گرفته، نیز نبوده است. یکی از چالشهای دیگر در شبکه روی تراشه، میزان توان مصرفی در NOC میباشد. در این پایان نامه، به مسئله نگاشت وظایف یک برنامه کاربردی بیدرنگ سخت بر روی هستههای پردازشی NOC با فرض ناهمگن بودن، پرداخته شده است به طوریکه علاوه بر اینکه محدودیتهای زمانی وظایف رعایت شود، اتلاف توان در شبکه روی تراشه نیز کمینه گردد. با توجه به این که حل بهینه مسئله نگاشت یک مسئله NP-hard است، در طرح پیشنهادی از یک الگوریتم ژنتیک چند هدفه استفاده می شود. برای همگرایی سریعتر الگوریتم، معتبر بودن هر راه حل بدست آماده اعتبارسنجی میگردد تا هزینه اجرای الگوریتم ژنتیک کاهش یابد. اگر چه طرح پیشنهادی برای شبکه های روی تراشه ناهمگن ارائه شده است اما مقایسه نتایج آن با طرحهای روی تراشههای همگن نشان دهنده سربار ناچیز طرح پیشنهادی است.
کلمات کلیدی: ۱- شبکه روی تراشه ۲-نگاشت ۳-برنامه کاربردی بیدرنگ سخت ۴-الگوریتم ژنتیک چندهدفه
فصل اول
فصل اول: مقدمه
مقدمه
با توسعه فنآوری نیمه هادیها امکان تجمیع تعداد زیادی المان پردازشی[۱] و حافظهای مختلف شامل پردازندههای سیگنال[۲]، سختافزارهای خاص منظوره[۳]، مدارهای منطقی برنامهپذیر[۴]، پردازندههای همه منظوره[۵] و انواع حافظه و مدارات جانبی در داخل یک تراشه فراهم شده است که این مفهوم به سیستم روی تراشه[۶] شناخته شده است[۱]. در این قبیل سیستمها ارتباطات بین مولفههای گوناگون که یک چالش مهم محسوب میشود، همانطور که در شکل ۱-۱ نشان داده شده است به صورت نقطه به نقطه[۷] یا از طریق گذرگاهها[۸] برقرار میشود[۲]. در اتصالات نقطه به نقطه بین هر دو هستهی پردازشیِ نیازمند به ارتباط، یک اتصال اختصاصی ایجاد می شود. از آنجا که این روش تنها از سیمها (و بدون استفاده از سختافزار اضافه) برای انتقال داده ها استفاده می کند، بهترین کارایی و توان مصرفی را برای برقراری ارتباط بین تعداد کم هستهها ارائه می کند. اما این روش دارای مشکلات زیادی از جمله عدم مقیاسپذیری[۹]، پیچیدگی زیاد طراحی و مسیریابی اتصالات در سطح مدار و هزینه پیادهسازی بالا است. ایرادهای فوق باعث می شود که استفاده از اتصالات نقطه به نقطه فقط در سیستمهای کوچک مقرون به صرفه باشد. با بزرگ شدن اندازه سیستم، استفاده از اتصالات نقطه به نقطه به علت زیاد شدن سیمهای مورد نیاز و مشکلات طراحی، امکان پذیر نیست[۲]. روش دیگر، یعنی معماری ارتباطی مبتنی بر گذرگاه، هستههای پردازشی را با بهره گرفتن از یک کانال مشترک به یکدیگر ارتباط میدهد. در مقایسه با اتصالات نقطه به نقطه، گذرگاه مشترک پیچیدگی طراحی سطح مدار کمتری دارد و چون از کانالهای کمتری استفاده می کند، هزینه پیادهسازی آن نیز پایینتر میباشد. اما گذرگاه مشترک دارای مشکل اساسی عدم مقیاسپذیری توان و کارآیی میباشد. با زیاد شدن تعداد دستگاههای متصل به گذرگاه، طول آن و نیز مدارات ارسال و دریافت دادهی متصل به آن افزایش یافته و باعث ایجاد یک بار خازنی زیاد میگردند. تمام این بار خازنی در جریان یک انتقال داده شارژ و دشارژ می شود. این امر، تأخیر و توان مصرفی گذرگاه مشترک را به طرز چشمگیری افزایش میدهد. افزون بر این، تمام عناصر متصل به گذرگاه از یک مسیر واحد استفاده مینمایند و لذا در هر لحظه فقط دو گره با هم ارتباط دارند و سایر گرهها باید منتظر آزاد شدن کانال بمانند. این امر موجب کاهش شدید کارآیی سیستم به ویژه هنگامیکه عناصر متقاضی ارتباط زیاد باشند، میشود [۴]. با توجه به این مشکلات، روش گذرگاه نمیتواند پاسخگوی نیازهای ارتباطی تراشههای آینده باشد. بنابراین نیاز به یک ساختار ارتباطی برای تجمیع تعداد زیادی هستههای پردازشی در کنار یکدیگر میباشد به طوری که این ساختار ارتباطی مقیاسپذیر بوده و کارایی بالا داشته باشد[۴].
با افزایش قدرت پردازشی تراشهها پیچیدگی و قابلیت برنامه های کاربردی نیز افزایش یافته است و این افزایش پیچیدگی سختافزار و نرمافزار در سیستمهای روی تراشه و پردازندههای چند هستهای، به نوبهی خود افزایش حجم و پیچیدگی ترافیک ارتباطی داخل تراشه را موجب می شود. از سوی دیگر، کاهش اندازه مشخصهی[۱۰] ترانزیستورها مشکلات و چالشهای دیگری را در سطح مدار به ویژه برای ساختارهای ارتباطی درون تراشه، به همراه دارد. مواجهه با این پیچیدگی ارتباطات و همچنین مسائل موجود در فن‌آوریهای جدید VLSI نیاز به بازنگری روشهای سنتی ارتباطی درون تراشه را ایجاد کرد و شبکه روی تراشه به عنوان یک طرح ارتباطی درون تراشهای نوین برای رفع و کاهش این مشکلات مورد توجه قرار گرفت[۵].
شبکه های ارتباطی روی تراشه که Network-on-Chip (NoC) نامیده میشوند یک راهحل ممکن برای ارتباطات روی تراشه‌ی پلتفرمهای SOC جهت غلبه بر محدودیتهای گذرگاهها میباشند. شبکه بر تراشه شامل واحدهای عملیاتی است که از طریق شبکه ای از مسیریابها با هم در ارتباط میباشند. در اینجا به جای استفاده از سیمهای اختصاصی[۱۱] از شبکه برای ارتباط بین مولفهها استفاده می شود که موجب تاخیر کمتر، اتلاف توان کمتر و به طور کلی کارایی بالاتری می شود[۵]. شبکه روی تراشه مزایای زیادی از جمله پودمانی بودن[۱۲] و مقیاسپذیری را دارا میباشد [۲]. همچنین NOC مباحث مربوط به محاسبات و ارتباطات را به طور مجزا انجام میدهد[۱].
(۱)
(۲)
شکل ۱‑۱- نمایی کلی از سیستم بر تراشه با دو ساختار ارتباطی (۱) گذرگاه (۲) نقطه به نقطه [۲]
چالش اساسی در این گونه ساختارها وجود قابلیتی در تراشه طراحی شده میباشد که بتواند با برقراری تعادل بین معیارهای مختلف که حائز اهمیت میباشند، کیفیت سرویس مورد نظر را فراهم آورد.
معرفی شبکه روی تراشه
کاهش ترانزیستورها به کمتر از ۵۰ نانومتر، منجر به افزایش تعداد ترانزیستورها به بیش از چندین میلیارد در یک تراشه میگردد. بنابراین باید روشهای جدیدی برای مدیریت حجم انبوهی از ترانزیستورها بر روی یک تراشه اعمال شود[۵]. سیستم بر تراشه و شبکه بر تراشه دو روش پیادهسازی برای این مشکلات هستند. سیستم بر تراشه شامل تعداد زیادی هستههای عملیاتی با قابلیت به کارگیری مجدد میباشد و برای ارتباط این هستهها نیاز به معماریهای ارتباطی مقیاسپذیر و با قابلیت گسترش و کارایی بالا میباشد. سیستمهای روی سیلیکون متفاوت از سایر سیستمها، باید بهگونه ای صحیح طراحی شوند که نیازی به تغییر یا تعمیر در آنها نباشد، زیرا این کار برای آنها عملا غیرممکن میباشد. سیستم روی تراشه نیاز به شیوه های طراحی دارد که با دیگر انواع طراحی در سیستمهای با مقیاس بزرگ عمومیت دارد[۱]. نگاه به روشهای طراحی اتصالات روی تراشه و مقایسه این اتصالات با اتصالات گسترده روی شبکه اینترنت می تواند مفید باشد. شبکه اینترنت قادر به کنترل پیچیدگی سیستم و ایجاد سرویس مطمئن، با وجود مشکلات و خطاهای محلی است. به همین دلیل، فنآوری شبکه قادر است که کیفیت سرویس را، حتی با وجود تفاوت در گرههای اینترنتی و پیوندها، برای ما تضمین کند. واضح است که فنآوری شبکه ابزار مناسبی برای بهبود فنآوری طراحی سیستم در مدارهای بسیار مجتمع است. از طرف دیگر، تلاش بر این است که به کمک خصوصیات شبکه، به ارتباط قابل اطمینان و پر سرعت بر روی تراشه دست یافت. بعضی بر این باورند که شبکه بر روی تراشه به این معناست که پروتکلهای شبکه مانند TCP/IP بر روی برد سیلیکونی آورده شود. چنین کاری به خاطر تاخیر بالا و پیچیدگی آن امکان پذیر نیست[۶]. ارتباطات بر روی تراشه باید پر سرعت باشد. به همین دلیل روشهای ایجاد شبکه بر روی تراشه باید ساده و موثر باشند و معیارهایی از قبیل پهنای باند، تاخیر، مصرف توان باید بهینه شوند. مدارهای بسیار مجتمع دارای لایه های مختلف سیم هستند که میتوانند برای انتقال داده و اطلاعات کنترلی مورد استفاده قرار گیرند. گذرگاههای داده برای انتقال موازی اطلاعات استفاده میشوند. وجود واحدهای محاسباتی و ذخیرهکننده بر روی تراشه، سرعت انتقال را بسیار بالا میبرد. با این حال، استفاده از گذرگاه در سیستمها، محیط را تبدیل به محیطی رقابتی می کند. به عبارتی معماری ارتباطی کنونی سیستم بر تراشهها گذرگاههای مشترک و گذرگاههای سلسله مراتبی هستند که مقیاسپذیری و توسعهپذیری کمی دارند. بنابراین رشد تعداد هستهها در تراشه باعث ایجاد گلوگاه در گذرگاههای ارتباطی سیستم بر تراشه میگردد[۴]. همچنین با کوچک شدن اندازه ترانزیستورها و سرعت بالای واحدهای محاسباتی، سهم تاخیر سیمها و ارتباطها در تعیین کارآیی و توان مصرفی پررنگتر شده است. اگر چه تاخیر دروازهها[۱۳] با روند تکنولوژی کاهش مییابد اما تاخیر سیمها ثابت میماند و در حقیقت نسبت به دروازهها بیشتر می شود. برای کاهش اثر این تاخیرها، باید معماریهایی جایگزین معماریهای رایج شوند که با کاهش طول اتصالات و حذف سیمهای بلند مشکلات ناشی از این تاخیرها را در بلوکهای عملیاتی کاهش دهد. در واقع هدف اصلی جداسازی بخشهای ارتباطی از بخشهای محاسباتی و ذخیرهسازی میباشد. این رویکرد باعث ارائه و توسعه معماریهای جدیدی شد که تحت عنوان شبکه بر تراشه از آنها یاد می شود[۵]. شبکه بر تراشه ساختار ارتباطی با قابلیت استفاده مجدد فراهم می کند که این ویژگی برای طراحان تراشه اهمیت بسیار زیادی دارد؛ زیرا منجر به کاهش زمان مابین طراحی محصول و ارائه آن به بازار می شود. به طور خلاصه، مهمترین هدف برای استفاده از شبکه بر روی تراشه، دستیابی به کارایی بالا است[۲].
به طور خلاصه میتوان گفت شبکه بر تراشه شامل واحدهای عملیاتی است که از طریق شبکه ای از مسیریابها با هم در ارتباط میباشند. چالش اساسی در این گونه ساختارها وجود قابلیتی در تراشه طراحی شده میباشد که بتواند با برقراری تعادل بین معیارهای مختلف که حائز اهمیت میباشند، کیفیت سرویس مورد نظر را فراهم آورد[۱].
از مهمترین مزایای شبکه روی تراشه، میتوان به موارد زیر اشاره کرد:
مقیاسپذیری: از آنجایی که ارتباط بین گرههای مختلف از طریق مسیریابی بستهها انجام می شود، تعداد زیادی گره را میتوان بدون استفاده از سیمهای سراسری طولانی به یکدیگر متصل کرد. همچنین با افزایش تعداد گرهها در شبکه، پهنای باند نیز افزایش مییابد. [۳]
قابلیت استفادهی مجدد[۱۴]: استفادهی مجدد به عنوان یکی از مؤثرترین روشها، جهت افزایش بهرهوری طراحی شناخته شده است. وجود تشابه در مسیریابهای شبکه روی تراشه و همچنین برخی از هستههای پردازشی مانند ریزپردازندهها، موجب سهولت در امر طراحی شده است. مسیریابها، کانالهای ارتباطی و پروتکلهای ارتباطی سطوح پایین را میتوان یک بار طراحی کرده و مشکلات سطح مدار آنها مانند هم‌شنوایی[۱۵] ، مسیریابی اتصالات، و نویز را رفع نمود. سپس میتوان مراحل بهینهسازی[۱۶] و آزمون[۱۷] را روی آن انجام داد و پس از آن، به دفعات زیاد در طرحهای دیگر استفاده کرد. در ضمن بسیاری از هستههایی که قبلاً برای معماری خاصی مانند گذرگاه مشترک طراحی شده بودند را میتوان با بهره گرفتن از رابط شبکه مناسب، مجدداً در شبکه روی تراشه مورد استفاده قرار داد[۳].
پیش بینی پذیری[۱۸]: نظم موجود در شبکه های روی تراشه موجب تسهیل درکنترل و بهبود معیارهای الکتریکی و پیش بینی دقیقتر زمانبندی مدار می شود. این عوامل موجب کاهش قابل توجه در زمان طراحی میگردد[۲].
قابلیت بهینهسازی توان و تاخیر: هر چند مدارات مورد نیاز شبکه روی تراشه یک منبع مهم مصرف توان و ایجاد تاخیر در ارتباطات درون تراشهای است، اما شبکه های روی تراشه این قابلیت بالقوه را دارند که با بهینهسازی و سفارشیسازی[۱۹] معیارها و نگاشت مناسب وظایف، توان و تاخیر بهتری از روشهای ارتباطی معادل ارائه دهند[۳].
تنوع و تعداد بیشتر اتصالات: در شبکه های روی تراشه یکی از محدودیتهای بزرگ شبکه های میان ارتباطی خارج تراشه، یعنی محدودیت تعداد پایه های تراشهها (به عنوان گرههای شبکه) و در نتیجه پهنای بیتی اتصالات، تا حد زیادی از بین رفته است. به علاوه، در این شبکه ها میتوان از تنوع در توان مصرفی و سرعت سیمها برای بهینهسازی ارتباطات درون تراشهای استفاده کرد[۲].
مسئله نگاشت در شبکه روی تراشه
یکی از چالشها در طراحی شبکه روی تراشه، مسئله نگاشت[۲۰] میباشد. به طور کلی در پژوهشهای انجام شده در این زمینه، مسئله نگاشت به دو دسته تقسیم می شود[۷]:
نگاشت هستههای پردازشی بر روی گرههای یک شبکه روی تراشه: نگاشت هستههای پردازشی مورد نیاز یک کاربرد بر روی گرههای یک شبکه روی تراشه یکی از موثرترین راههای بهینهسازی شبکه های روی تراشه به ازای یک کابرد خاص است. در این حالت ابتدا در ورودی مسئله مشخص شده است که هر یک از وظایف[۲۱] کاربرد بر روی کدام هسته پردازشی اجرا می شود و سپس مسئله به نگاشت این هستهها بر روی گرههای شبکه می پردازد (شکل ۱-۲). هدف بیشتر الگوریتمهای نگاشت، کنار هم قرار دادن هستههای پردازشی است که حجم ارتباطی زیادی با یکدیگر دارند. از یک دیدگاه، میتوان این نگاشت را به دو دستهی کلی تقسیم کرد. در دستهی اول، نگاشت بر روی گرههای یک شبکه با همبندی[۲۲] معلوم (اغلب توری) انجام میگیرد، در حالی که در دستهی دوم، ابتدا یک همبندی خاص منظوره طبق نیازمندیهای ترافیکی کاربرد ساخته شده و سپس عملیات نگاشت بر اساس این همبندی و یا همزمان با ساخت آن انجام میپذیرد[۸].
نگاشت وظایف یک برنامه کاربردی بر روی هستههای پردازشی: در برخی از شبکه روی تراشهها هستههای پردازشی به مسیریابها متصل شده اند[۹] و در این حالت فرض می شود که مکان هستههای پردازشی بر روی گرههای یک شبکه روی تراشه از قبل و در زمان طراحی مشخص شده است و در مسئله نگاشت به تخصیص وظایف یک کاربرد بر روی هستههای پردازشی پرداخته می شود که به آن نگاشت وظیفه گفته می شود . با توجه به شکل ۱-۳ اینگونه مسائل در برخی تحقیقات با مسئله زمانبندی وظایف نیز همراه بوده است به گونه ای که مشخص می شود وظایف نگاشت شده بر روی یک هسته پردازشی هر کدام در چه زمانی توسط هسته مورد نظر پردازش شوند.
شکل ۱‑۲- مسئله نگاشت هستههای پردازشی به گرههای شبکه روی تراشه[۸]
