پژوهش user6-759

یکشنبه 7 آبان 1396 ساعت 18:07
چالش اساسی در این گونه ساختارها وجود قابلیتی در تراشه طراحی شده میباشد که بتواند با برقراری تعادل بین معیارهای مختلف که حائز اهمیت میباشند، کیفیت سرویس مورد نظر را فراهم آورد.معرفی شبکه روی تراشهکاهش ترانزیستورها به کمتر از 50 […]

  

سایت دانلود پژوهش ها و منابع علمی

سایت دانلود پژوهش ها و منابع علمی دانشگاهی فنی تخصصی همه رشته ها – این سایت صرفا جهت کمک به گردآوری داده ها برای نگارش پژوهش های علمی و صرفه جویی در وقت پژوهشگران راه اندازی شده است

پژوهش user6-759

پژوهش user6-759

پژوهش user6-759

چکیده
امروزه با پیشرفت فنآوری نیمههادیها، تعداد مولفههای پردازشی در یک سیستم روی تراشه (SOC) افزایش یافته است. معماری ارتباطی در این قبیل سیستمها مبتنی بر گذرگاه میباشد. از این رو، با افزایش تعداد مولفههای پردازشی و با توجه به عدم کارایی و توسعهپذیری گذرگاه، مفهوم شبکه روی تراشه یا NOC به عنوان یک طرح ارتباطی درون تراشهای کارآمد و مقیاسپذیر، جهت غلبه بر مشکلات گذرگاهها مطرح شده است. یکی از چالشهای مهم در تحقیقات مربوط به NOCها، مسئله نگاشت وظایف یک برنامه کاربردی بر روی هستههای پردازشی متصل به مسیریابهای شبکه است که این هستهها میتوانند به صورت همگن یا ناهمگن باشند. از طرف دیگر، یکی از پرکاربردترین برنامههای کاربردی، برنامههای کاربردی تعبیه شده با نیازمندیهای زمانی بیدرنگ میباشند. در بسیاری از کارهای انجام شده، به مسئله نگاشت بر روی هستههای پردازشی همگن پرداخته شده است و سعی در ارائه راه حل کارآمد کردهاند. اما تقریبا در اکثر طرحهای پیشنهاد شده، ویژگی ناهمگن بودن هستهها علیرغم آنکه به واقعیت نزدیکتر است، نادیده گرفته شده است. همچنین ویژگی بیدرنگ بودن کاربردها، مورد توجه عمده کارهای پژوهشی انجام گرفته، نیز نبوده است. یکی از چالشهای دیگر در شبکه روی تراشه، میزان توان مصرفی در NOC میباشد. در این پایاننامه، به مسئله نگاشت وظایف یک برنامه کاربردی بیدرنگ سخت بر روی هستههای پردازشی NOC با فرض ناهمگن بودن، پرداخته شده است بهطوریکه علاوه بر اینکه محدودیتهای زمانی وظایف رعایت شود، اتلاف توان در شبکه روی تراشه نیز کمینه گردد. با توجه به این که حل بهینه مسئله نگاشت یک مسئله NP-hard است، در طرح پیشنهادی از یک الگوریتم ژنتیک چند هدفه استفاده میشود. برای همگرایی سریعتر الگوریتم، معتبر بودن هر راه حل بدست آماده اعتبارسنجی میگردد تا هزینه اجرای الگوریتم ژنتیک کاهش یابد. اگر چه طرح پیشنهادی برای شبکههای روی تراشه ناهمگن ارائه شده است اما مقایسه نتایج آن با طرحهای روی تراشههای همگن نشان دهندهی سربار ناچیز طرح پیشنهادی است.
کلمات کلیدی: 1- شبکه روی تراشه 2-نگاشت 3-برنامه کاربردی بی‌درنگ سخت 4-الگوریتم ژنتیک چندهدفه
فصل اول
فصل اول: مقدمهمقدمهبا توسعه فن‌آوری نیمه هادیها امکان تجمیع تعداد زیادی المان پردازشی و حافظهای مختلف شامل پردازندههای سیگنال، سختافزارهای خاص منظوره، مدارهای منطقی برنامهپذیر، پردازندههای همه منظوره و انواع حافظه و مدارات جانبی در داخل یک تراشه فراهم شده است که این مفهوم به سیستم روی تراشه شناخته شده است[1]. در این قبیل سیستمها ارتباطات بین مولفههای گوناگون که یک چالش مهم محسوب می‌شود، همان‌طور که در شکل 1-1 نشان داده شده است به صورت نقطه به نقطه یا از طریق گذرگاهها برقرار می‌شود[2]. در اتصالات نقطه به نقطه بین هر دو هستهی پردازشیِ نیازمند به ارتباط، یک اتصال اختصاصی ایجاد میشود. از آنجا که این روش تنها از سیمها (و بدون استفاده از سختافزار اضافه) برای انتقال دادهها استفاده میکند، بهترین کارایی و توان مصرفی را برای برقراری ارتباط بین تعداد کم هستهها ارائه میکند. اما این روش دارای مشکلات زیادی از جمله عدم مقیاسپذیری، پیچیدگی زیاد طراحی و مسیریابی اتصالات در سطح مدار و هزینهی پیادهسازی بالا است. ایرادهای فوق باعث میشود که استفاده از اتصالات نقطه به نقطه فقط در سیستمهای کوچک مقرون به صرفه باشد. با بزرگ شدن اندازهی سیستم، استفاده از اتصالات نقطه به نقطه به علت زیاد شدن سیمهای مورد نیاز و مشکلات طراحی، امکانپذیر نیست[2]. روش دیگر، یعنی معماری ارتباطی مبتنی بر گذرگاه، هستههای پردازشی را با استفاده از یک کانال مشترک به یکدیگر ارتباط میدهد. در مقایسه با اتصالات نقطه به نقطه، گذرگاه مشترک پیچیدگی طراحی سطح مدار کمتری دارد و چون از کانالهای کمتری استفاده میکند، هزینهی پیادهسازی آن نیز پایینتر میباشد. اما گذرگاه مشترک دارای مشکل اساسی عدم مقیاسپذیری توان و کارآیی می‌باشد. با زیاد شدن تعداد دستگاههای متصل به گذرگاه، طول آن و نیز مدارات ارسال و دریافت دادهی متصل به آن افزایش یافته و باعث ایجاد یک بار خازنی زیاد میگردند. تمام این بار خازنی در جریان یک انتقال داده شارژ و دشارژ میشود. این امر، تأخیر و توان مصرفی گذرگاه مشترک را به طرز چشمگیری افزایش میدهد. افزون بر این، تمام عناصر متصل به گذرگاه از یک مسیر واحد استفاده مینمایند و لذا در هر لحظه فقط دو گره با هم ارتباط دارند و سایر گرهها باید منتظر آزاد شدن کانال بمانند. این امر موجب کاهش شدید کارآیی سیستم به ویژه هنگامیکه عناصر متقاضی ارتباط زیاد باشند، می‌شود [4]. با توجه به این مشکلات، روش گذرگاه نمیتواند پاسخگوی نیازهای ارتباطی تراشههای آینده باشد. بنابراین نیاز به یک ساختار ارتباطی برای تجمیع تعداد زیادی هستههای پردازشی در کنار یکدیگر میباشد به طوری که این ساختار ارتباطی مقیاسپذیر بوده و کارایی بالا داشته باشد[4].
با افزایش قدرت پردازشی تراشهها پیچیدگی و قابلیت برنامههای کاربردی نیز افزایش یافته است و این افزایش پیچیدگی سختافزار و نرمافزار در سیستمهای روی تراشه و پردازندههای چند هستهای، به نوبهی خود افزایش حجم و پیچیدگی ترافیک ارتباطی داخل تراشه را موجب میشود. از سوی دیگر، کاهش اندازهی مشخصهی ترانزیستورها مشکلات و چالشهای دیگری را در سطح مدار به ویژه برای ساختارهای ارتباطی درون تراشه، به همراه دارد. مواجهه با این پیچیدگی ارتباطات و همچنین مسائل موجود در فن‌آوریهای جدید VLSI نیاز به بازنگری روشهای سنتی ارتباطی درون تراشه را ایجاد کرد و شبکه روی تراشه به عنوان یک طرح ارتباطی درون تراشهای نوین برای رفع و کاهش این مشکلات مورد توجه قرار گرفت[5].
2628902073275(1)
(2)
00(1)
(2)
1447804009593شکل STYLEREF 1 \s ‏1 SEQ شکل \* ARABIC \s 1 1- نمایی کلی از سیستم بر تراشه با دو ساختار ارتباطی (1) گذرگاه (2) نقطه به نقطه [2]شکل STYLEREF 1 \s ‏1 SEQ شکل \* ARABIC \s 1 1- نمایی کلی از سیستم بر تراشه با دو ساختار ارتباطی (1) گذرگاه (2) نقطه به نقطه [2]شبکههای ارتباطی روی تراشه که Network-on-Chip (NoC) نامیده میشوند یک راهحل ممکن برای ارتباطات روی تراشه‌ی پلتفرمهای SOC جهت غلبه بر محدودیتهای گذرگاهها میباشند. شبکه بر تراشه شامل واحدهای عملیاتی است که از طریق شبکهای از مسیریاب‌ها با هم در ارتباط میباشند. در این‌جا به جای استفاده از سیمهای اختصاصی از شبکه برای ارتباط بین مولفهها استفاده میشود که موجب تاخیر کمتر، اتلاف توان کمتر و به طور کلی کارایی بالاتری میشود[5]. شبکه روی تراشه مزایای زیادی از جمله پودمانی بودن و مقیاسپذیری را دارا میباشد [2]. همچنین NOC مباحث مربوط به محاسبات و ارتباطات را به طور مجزا انجام میدهد[1].
چالش اساسی در این گونه ساختارها وجود قابلیتی در تراشه طراحی شده میباشد که بتواند با برقراری تعادل بین معیارهای مختلف که حائز اهمیت میباشند، کیفیت سرویس مورد نظر را فراهم آورد.
معرفی شبکه روی تراشهکاهش ترانزیستورها به کمتر از 50 نانومتر، منجر به افزایش تعداد ترانزیستورها به بیش از چندین میلیارد در یک تراشه میگردد. بنابراین باید روشهای جدیدی برای مدیریت حجم انبوهی از ترانزیستورها بر روی یک تراشه اعمال شود[5]. سیستم بر تراشه و شبکه بر تراشه دو روش پیادهسازی برای این مشکلات هستند. سیستم بر تراشه شامل تعداد زیادی هستههای عملیاتی با قابلیت بهکارگیری مجدد میباشد و برای ارتباط این هستهها نیاز به معماریهای ارتباطی مقیاسپذیر و با قابلیت گسترش و کارایی بالا میباشد. سیستم‌های روی سیلیکون متفاوت از سایر سیستم‌ها، باید بهگونهای صحیح طراحی شوند که نیازی به تغییر یا تعمیر در آنها نباشد، زیرا این کار برای آنها عملا غیرممکن میباشد. سیستم روی تراشه نیاز به شیوههای طراحی دارد که با دیگر انواع طراحی در سیستمهای با مقیاس بزرگ عمومیت دارد[1]. نگاه به روشهای طراحی اتصالات روی تراشه و مقایسهی این اتصالات با اتصالات گسترده روی شبکهی اینترنت میتواند مفید باشد. شبکهی اینترنت قادر به کنترل پیچیدگی سیستم و ایجاد سرویس مطمئن، با وجود مشکلات و خطاهای محلی است. به همین دلیل، فن‌آوری شبکه قادر است که کیفیت سرویس را، حتی با وجود تفاوت در گرههای اینترنتی و پیوندها، برای ما تضمین کند. واضح است که فن‌آوری شبکه ابزار مناسبی برای بهبود فن‌آوری طراحی سیستم در مدارهای بسیار مجتمع است. از طرف دیگر، تلاش بر این است که به کمک خصوصیات شبکه، به ارتباط قابل اطمینان و پر سرعت بر روی تراشه دست یافت. بعضی بر این باورند که شبکه بر روی تراشه به این معناست که پروتکلهای شبکه مانند TCP/IP بر روی برد سیلیکونی آورده شود. چنین کاری به خاطر تاخیر بالا و پیچیدگی آن امکان پذیر نیست[6]. ارتباطات بر روی تراشه باید پر سرعت باشد. به همین دلیل روشهای ایجاد شبکه بر روی تراشه باید ساده و موثر باشند و معیارهایی از قبیل پهنای باند، تاخیر، مصرف توان باید بهینه شوند. مدارهای بسیار مجتمع دارای لایههای مختلف سیم هستند که میتوانند برای انتقال داده و اطلاعات کنترلی مورد استفاده قرار گیرند. گذرگاههای داده برای انتقال موازی اطلاعات استفاده میشوند. وجود واحدهای محاسباتی و ذخیرهکننده بر روی تراشه، سرعت انتقال را بسیار بالا میبرد. با این حال، استفاده از گذرگاه در سیستمها، محیط را تبدیل به محیطی رقابتی میکند. به عبارتی معماری ارتباطی کنونی سیستم بر تراشهها گذرگاههای مشترک و گذرگاههای سلسله مراتبی هستند که مقیاسپذیری و توسعهپذیری کمی دارند. بنابراین رشد تعداد هستهها در تراشه باعث ایجاد گلوگاه در گذرگاههای ارتباطی سیستم بر تراشه میگردد[4]. همچنین با کوچک شدن اندازهی ترانزیستورها و سرعت بالای واحدهای محاسباتی، سهم تاخیر سیمها و ارتباطها در تعیین کارآیی و توان مصرفی پررنگتر شده است. اگر چه تاخیر دروازهها با روند تکنولوژی کاهش مییابد اما تاخیر سیمها ثابت میماند و در حقیقت نسبت به دروازهها بیشتر میشود. برای کاهش اثر این تاخیرها، باید معماریهایی جایگزین معماریهای رایج شوند که با کاهش طول اتصالات و حذف سیمهای بلند مشکلات ناشی از این تاخیرها را در بلوکهای عملیاتی کاهش دهد. در واقع هدف اصلی جداسازی بخشهای ارتباطی از بخشهای محاسباتی و ذخیرهسازی میباشد. این رویکرد باعث ارائه و توسعه معماریهای جدیدی شد که تحت عنوان شبکه بر تراشه از آنها یاد میشود[5]. شبکه بر تراشه ساختار ارتباطی با قابلیت استفاده مجدد فراهم میکند که این ویژگی برای طراحان تراشه اهمیت بسیار زیادی دارد؛ زیرا منجر به کاهش زمان مابین طراحی محصول و ارائه آن به بازار میشود. به طور خلاصه، مهمترین هدف برای استفاده از شبکه بر روی تراشه، دستیابی به کارایی بالا است[2].
به طور خلاصه می‌توان گفت شبکه بر تراشه شامل واحدهای عملیاتی است که از طریق شبکهای از مسیریاب‌ها با هم در ارتباط میباشند. چالش اساسی در این گونه ساختارها وجود قابلیتی در تراشه طراحی شده میباشد که بتواند با برقراری تعادل بین معیارهای مختلف که حائز اهمیت میباشند، کیفیت سرویس مورد نظر را فراهم آورد[1].
از مهمترین مزایای شبکه روی تراشه، میتوان به موارد زیر اشاره کرد:
مقیاسپذیری: از آنجایی که ارتباط بین گرههای مختلف از طریق مسیریابی بستهها انجام میشود، تعداد زیادی گره را میتوان بدون استفاده از سیمهای سراسری طولانی به یکدیگر متصل کرد. همچنین با افزایش تعداد گرهها در شبکه، پهنای باند نیز افزایش مییابد. [3]
قابلیت استفادهی مجدد: استفادهی مجدد به عنوان یکی از مؤثرترین روشها، جهت افزایش بهرهوری طراحی شناخته شده است. وجود تشابه در مسیریابهای شبکه روی تراشه و همچنین برخی از هستههای پردازشی مانند ریزپردازندهها، موجب سهولت در امر طراحی شده است. مسیریابها، کانالهای ارتباطی و پروتکلهای ارتباطی سطوح پایین را میتوان یک بار طراحی کرده و مشکلات سطح مدار آنها مانند هم‌شنوایی ، مسیریابی اتصالات، و نویز را رفع نمود. سپس میتوان مراحل بهینهسازی و آزمون را روی آن انجام داد و پس از آن، به دفعات زیاد در طرحهای دیگر استفاده کرد. در ضمن بسیاری از هستههایی که قبلاً برای معماری خاصی مانند گذرگاه مشترک طراحی شده بودند را میتوان با استفاده از رابط شبکهی مناسب، مجدداً در شبکه روی تراشه مورد استفاده قرار داد[3].
پیشبینی پذیری: نظم موجود در شبکههای روی تراشه موجب تسهیل درکنترل و بهبود معیارهای الکتریکی و پیشبینی دقیقتر زمانبندی مدار میشود. این عوامل موجب کاهش قابل توجه در زمان طراحی میگردد[2].
قابلیت بهینهسازی توان و تاخیر: هر چند مدارات مورد نیاز شبکه روی تراشه یک منبع مهم مصرف توان و ایجاد تاخیر در ارتباطات درون تراشهای است، اما شبکههای روی تراشه این قابلیت بالقوه را دارند که با بهینهسازی و سفارشیسازی معیارها و نگاشت مناسب وظایف، توان و تاخیر بهتری از روشهای ارتباطی معادل ارائه دهند[3].
تنوع و تعداد بیشتر اتصالات: در شبکههای روی تراشه یکی از محدودیتهای بزرگ شبکههای میان ارتباطی خارج تراشه، یعنی محدودیت تعداد پایههای تراشهها (به عنوان گرههای شبکه) و در نتیجه پهنای بیتی اتصالات، تا حد زیادی از بین رفته است. به علاوه، در این شبکهها میتوان از تنوع در توان مصرفی و سرعت سیمها برای بهینهسازی ارتباطات درون تراشهای استفاده کرد[2].
مسئله نگاشت در شبکه روی تراشهیکی از چالشها در طراحی شبکه روی تراشه، مسئله نگاشت میباشد. به طور کلی در پژوهشهای انجام شده در این زمینه، مسئله نگاشت به دو دسته تقسیم میشود[7]:
نگاشت هستههای پردازشی بر روی گرههای یک شبکه روی تراشه: نگاشت هستههای پردازشی مورد نیاز یک کاربرد بر روی گرههای یک شبکه روی تراشه یکی از موثرترین راههای بهینهسازی شبکههای روی تراشه به ازای یک کابرد خاص است. در این حالت ابتدا در ورودی مسئله مشخص شده است که هر یک از وظایف کاربرد بر روی کدام هسته پردازشی اجرا میشود و سپس مسئله به نگاشت این هستهها بر روی گرههای شبکه میپردازد (شکل 1-2). هدف بیشتر الگوریتمهای نگاشت، کنار هم قرار دادن هستههای پردازشی است که حجم ارتباطی زیادی با یکدیگر دارند. از یک دیدگاه، میتوان این نگاشت را به دو دستهی کلی تقسیم کرد. در دستهی اول، نگاشت بر روی گرههای یک شبکه با همبندی معلوم (اغلب توری) انجام میگیرد، در حالی که در دستهی دوم، ابتدا یک همبندی خاص منظوره طبق نیازمندیهای ترافیکی کاربرد ساخته شده و سپس عملیات نگاشت بر اساس این همبندی و یا هم‌زمان با ساخت آن انجام میپذیرد[8].
نگاشت وظایف یک برنامه کاربردی بر روی هستههای پردازشی: در برخی از شبکه روی تراشهها هستههای پردازشی به مسیریاب‌ها متصل شدهاند[9] و در این حالت فرض میشود که مکان هستههای پردازشی بر روی گرههای یک شبکه روی تراشه از قبل و در زمان طراحی مشخص شده است و در مسئله نگاشت به تخصیص وظایف یک کاربرد بر روی هستههای پردازشی پرداخته میشود که به آن نگاشت وظیفه گفته میشود . با توجه به شکل 1-3 اینگونه مسائل در برخی تحقیقات با مسئله زمانبندی وظایف نیز همراه بوده است به گونهای که مشخص میشود وظایف نگاشت شده بر روی یک هسته پردازشی هر کدام در چه زمانی توسط هسته مورد نظر پردازش شوند.

شکل STYLEREF 1 \s ‏1 SEQ شکل \* ARABIC \s 1 2- مسئله نگاشت هستههای پردازشی به گرههای شبکه روی تراشه[8]ثابت شده است که مسئلهی نگاشت یک مسئلهی NP-hard است و جواب بهینه تنها بعد از امتحان تمام حالات ممکن مشخص میشود[7]. برای همین اگر فرض شود امتحان هر حالت ممکن 01/0 میلی ثانیه طول بکشد، یافتن جواب بهینه برای نگاشت 16 وظیفه بر روی 16 گره شبکه 108×9/2 ثانیه معادل 6/6 سال به طول میانجامد. به همین دلیل، این مسئله در بسیاری از مقالات با روشهای مکاشفهای حل شده است.
در این پایاننامه به حالت دوم مسئله نگاشت یعنی به عبارتی به نگاشت وظایف یک برنامهی کاربردی بر روی هستههای پردازشی پرداخته میشود.

شکل STYLEREF 1 \s ‏1 SEQ شکل \* ARABIC \s 1 3- مسئله نگاشت وظایف بر روی هسته‌های پردازشی شبکه[10]مفهوم برنامههای کاربردی بیدرنگدر سیستمهای بیدرنگ صحت و درستی سیستم تنها وابسته به تولید نتایج درست نمی‌باشد بلکه به زمان تولید نتایج نیز بستگی دارد [11]. برنامههای کاربردی بیدرنگ در این قبیل سیستمها دارای وظایف بیدرنگ میباشند که این وظایف در این قبیل سیستم‌ها در پاسخ به یک اتفاق که ممکن است از داخل یا خارج سیستم رخ دهد، ایجاد میشوند. به طور مثال یک وظیفه ممکن است به خاطر یک رخداد داخلی از قبیل یک وقفه ساعت که هر چند میلیثانیه اتفاق میافتد و به طور دورهای دمای یک محفظه را اعلام میکند، ایجاد شود. وظیفه دیگری ممکن است به خاطر یک رخداد خارجی مانند فشار دادن یک سوئیچ توسط کاربر، ایجاد شود. هر یک از این وظایف دارای محدودیت زمانی به نام مهلت اتمام می‌باشند که بیانگر حداکثر زمان وظیفه برای اتمام اجرا و تولید نتایج‌اش می‌باشد[12]. مهلت اتمام وظایف مختلف ممکن است متفاوت باشد. در سیستمهای بیدرنگ همهی بستههای داده متعلق به یک وظیفه باید در آن مهلت اتمام مشخص شده به وظیفه مقصد تحویل داده شوند و از دست دادن زمان اتمام در این سیستمها به همان میزان که یک پکت در مسیر خراب یا دور انداخته شود، یک شکست تلقی میشود[11]. ارتباطات بیدرنگ به طور معمول در سیستمهای بحرانی ایمنی مانند کنترل روبات، وسایل نقلیه الکترونیکی و... استفاده میشوند [13].
برنامههای کاربردی بیدرنگ به دو دسته تقسیم میشوند[11]:
برنامههای کاربردی بیدرنگ سخت : در این قبیل برنامههای کاربردی، اتمام زود هنگام وظایف چندان حائز اهمیت نمیباشد بلکه مسئله مهم آن است که همهی وظایف برنامهی کاربردی مورد نظر در تمامی زمانها مهلت اتمامشان را رعایت کنند و از آن زمان تعیین شده تجاوز نکنند. بنابراین برنامههای کاربردی بیدرنگ سخت انعطافپذیر نیستند و تجاوز از مهلت اتمام را نمیتوانند تحمل کنند. به همین دلیل لازم است که تمام ملزومات سیستم در زمان طراحی در نظر گرفته شوند و در واقع نوعی تضمین فراهم میشود. همچنین به دلیل همین عدم انعطافپذیری این برنامههای کاربردی، رفتارهای پویای سیستم نامطلوب است مگر اینکه آن رفتار را به عنوان یک وضعیتی از سیستم مدل کرد که بتواند در زمان طراحی تحلیل شود[11]. Æthereal, Nostrum و Mangoنمونههای NOCهایی هستند که ارتباطات بیدرنگ سخت را پیادهسازی میکنند[13].
برنامههای کاربردی بیدرنگ نرم : این برنامههای کاربردی در بسیاری از حوزهها از قبیل سیستم‌های چندرسانه‌ای، محاسبات توزیع شده که نیازمند کارایی بالا هستند، ارائه شدهاند[11]. برنامههای کاربردی بیدرنگ نرم، نیز دارای محدودیتهای زمانی میباشند اما در برنامههای کاربردی مذکور، کیفیت سرویس دارای اهمیت بالاتری است. به عبارتی در این برنامههای کاربردی تا حدی قابل قبول است که برخی از ترافیکهای ارتباطی به درستی سرویس داده نشوند (یعنی تا حدودی محدودیتهای زمانیشان را رعایت نکنند) به شرط آنکه عملکرد آن در یک سطح مشخصی باقی بماند[11]. به بیان دیگر، میانگین زمان پاسخ وظایف، معیار مهم در اندازهگیری کارایی در این دسته از برنامههای کاربردی میباشد وکمینهکردن هرچه بیشتر زمان پاسخ وظایف حائز اهمیت است. بنابراین هیچ گونه تضمین مطلقی برای رفتارهای زمانی این نوع سیستمها لازم نیست، در حالی که کارایی باید به طور میانگین در یک سطح قابل قبولی باشد. به خاطر همین انعطافپذیری این سیستمها به سیستمهای بیدرنگ نرم معروفاند[11]. نمونهای از سیستمهای بیدرنگ نرم، سیستمهای چندرسانهای هستند[13].
مسئله توان در شبکه بر روی تراشهاگرچه شبکه روی تراشه در ابتدا با هدف بهبود سرعت انتقال مطرح شد، ولی با توجه به اهمیت کنونی توان مصرفی، بررسی عوامل مصرف توان در شبکه روی تراشه و کنترل آن امری اجتناب ناپذیر است و به عبارتی توان بمصرفی یکی از مهمترین معیارهای ارزیابی شبکه روی تراشه میباشد. عوامل زیادی روی توان مصرفی شبکه روی تراشه تاثیر میگذارند، که عبارتند از : ساختار مسیریابها، روش راهگزینی، الگوریتم مسیریابی، الگوی ترافیکی[1]. اما یکی از چالشهای اصلی در ازریابی توان در شبکه روی تراشه، بررسی توان مصرفی ناشی از ارتباطات بین هستههای پردازشی و همچنین اتلاف توان در المانهای شبکه از جمله مسیریاب میباشد. توان مصرفی شبکه، متوسط توان مصرف شده توسط شبکه (مسیریابها و اتصالات) را در طول مدت اجرا (و یا شبیهسازی) نشان میدهد. این توان شامل توان پویای ناشی از فعالیت اجزای شبکه و نیز توان ایستا ناشی از جریانات نشتی است. یک معیار مهم دیگر برای ارزیابی مصرف انرژی شبکه، متوسط انرژی فلیت (و یا بسته) است که انرژی متوسطی را نشان میدهدکه برای هدایت یک فلیت از گره مبدا به گره مقصد لازم است. اندازه گیری دقیق توان تنها با سنتز کامل توصیف سختافزاری شبکه (شامل جایابی و مسیریابی اتصالات) و توسط ابرازهای خاصی قابل انجام است[7]. در این پایاننامه به دلیل آنکه استفاده از شبیهساز نیاز به زمان زیادی برای تحلیل هر راهحل در الگوریتم ژنتیک دارد، از مدلهای تحلیلی برای ارزیابی توان مصرفی در شبکه روی تراشه استفاده میشود که در ادامه به طور کامل توضیح داده خواهد شد.
هدف پایان‌نامهیکی از چالشهای مهم در تحقیقات مربوط به شبکه روی تراشه، مسئله نگاشت برنامه کاربردی بر روی هستههای پردازشی متصل به مسیریابهای شبکه میباشد. برنامههای کاربردی انواع مختلفی دارند که یکی از پرکاربردترین آنها، برنامههای کاربردی تعبیه شده میباشند. برنامههای کاربردی تعبیه شده پیچیده که دارای ارتباطات زیادی بین مولفههای مختلف میباشند و همچنین نیازمند کارایی و توان محاسباتی بالایی هستند، مناسبتر است که از معماری شبکه روی تراشه بهره ببرند. این دسته از برنامههای کاربردی دارای نیازمندیهای زمانی بیدرنگ میباشند. به عبارتی وظایف این برنامههای کاربردی برای آنکه مهلت اتمام موردنظرشان رعایت شود، باید در تمامی موقعیتها، محاسبات و ارتباطاتشان به موقع انجام شود. با وجود این اهمیت برای سیستمهای تعبیه شده، تحقیقات کمی بر روی تامین ضمانت برای برنامههای کاربردی بیدرنگ سخت که شامل چندین مولفه ارتباطی روی NOC هستند، انجام شده است. همچنین همانگونه که ذکر شد، یکی از معیارهای مهم در ارزیابی شبکه روی تراشه، مسئله توان مصرفی در NOC میباشد. از این رو هدف از انجام این پایاننامه، پرداختن به مسئله نگاشت وظایف یک برنامه کاربردی بیدرنگ سخت بر روی هستههای پردازشی NOC است بهطوریکه علاوه بر اینکه محدودیتهای زمانی وظایف رعایت شود، اتلاف توان در شبکه روی تراشه نیز کمینه گردد. به دلیل آنکه مسئله نگاشت یک مسئله NP-hard است و یافتن جواب بهینه نیازمند امتحان تمام حالات ممکن است، از این رو، روشی مبتنی بر الگوریتم تکاملی ژنتیک چندهدفه ارائه شده است که هم پاسخگوی اهداف مذکور باشد و هم توانایی رقابت با روشهای مشابه را از جنبههای مختلف داشته باشد.
ساختار ادامه پایان‌نامهدر فصل دوم مروری بر مفاهیم و معماری شبکه روی تراشه ارائه شده که در این فصل به بیان همبندی شبکه، روشهای راهگزینی، مسیریابی و الگوریتمهای مسیریابی، کانال مجازی و معیارهای ارزیابی در شبکه روی تراشه پرداخته شده است. در فصل سوم مروری بر ادبیات موضوع ارائه شده، که شامل مفاهیم نگاشت ایستا و پویا و بررسی کارهای مرتبط با هر یک از آن‌ها میباشد. در فصل چهارم روش پیشنهادی برای نگاشت وظایف یک برنامه کاربردی بیدرنگ سخت بر روی هستههای پردازشی NOC بر مبنای الگوریتم ژنتیک ارائه شده است که شامل نحوه مدل کردن مسئله، اهداف الگوریتم، نحوه انجام آن و اجزاء تشکیل‌دهنده‌ی این روش می‌باشد. در فصل پنجم ضمن معرفی معیارهای ارزیابی و محک مورد استفاده، نتایج حاصل از الگوریتم پیشنهادی براساس معیارهای معرفی شده، مورد بررسی و ارزیابی قرار گرفته‌اند. در آخر در فصل ششم خلاصهای از پایاننامه، نتیجهگیری کلی از کارهای انجام‌شده و پیشنهادهایی برای ادامهی این کار ارائه شده است.
فصل دوم
فصل دوم: معماری شبکه روی تراشهمقدمهبا پیشرفت روزافزون فنآوری و رشدسطح فشردهسازی، ابعاد تراشهها و حجم پردازندهها کاهش یافته است که این کاهش حجم پردازندهها، موجب عدم تعادل بین تاخیر دروازهها و تاخیر سیمها بر روی تراشه شده است. در این ارتباط، اگر چه تاخیر دروازهها با روند فنآوری کاهش مییابد اما تاخیر سیمها ثابت میماند و در حقیقت نسبت به دروازهها بیشتر میشود. برای کاهش اثر این تاخیرها، باید معماریهایی جایگزین معماریهای رایج شوند که با کاهش طول اتصالات و حذف سیمهای بلند مشکلات ناشی از این تاخیرها را در بلوکهای عملیاتی کاهش دهند. در واقع نکته اصلی جداسازی بخشهای ارتباطی از بخشهای محاسباتی و ذخیرهسازی میباشد. از این رو امروزه ارتباطات روی تراشه یکی از مهمترین عوامل برای افزایش کارایی سیستمهای روی تراشه است. یکی از راهحلهای ارائه شده در زمینهی ارتباط روی تراشه، استفاده از فنآوری شبکه بر روی تراشه است، که مشکلات ارتباطات را تا حد زیادی حل میکند[4]. شبکه بر تراشه ساختار ارتباطی با قابلیت استفاده مجدد فراهم میکند که این ویژگی برای طراحان تراشه اهمیت بسیار زیادی دارد؛ زیرا منجر به کاهش زمان مابین طراحی محصول و ارائه آن به بازار میشود. همچنین این ساختار ارتباطی که در آن ارتباط میان واحدهای مختلف از طریق بستههای مسیریابی شده توسط مسیریابها و راهگزینهای تعبیه شده در شبکه واقع بر روی تراشه برقرار میشود، نه تنها از قابلیت مقیاسپذیری و توسعهی بالایی برخوردار است، بلکه با کاهش طول سیمهای بلند سراسری کشیده شده در سطح تراشه به کاهش توان مصرفی نیز منجر خواهد شد[2]. در ادامه این فصل به بررسی اجمالی مفاهیم شبکه روی تراشه شامل معماری NOC، انواع همبندیهای شبکه، مسیریابی و الگوریتمهای مسیریابی، روشهای راهگزینی و کانال مجازی در شبکه روی تراشه پرداخته میشود.
معماری شبکه روی تراشهمعماریهای سنتی ارتباطی درون تراشهی مبتنی بر گذرگاه مشترک و اتصالات اختصاصی نقطه به نقطه به دلیل مقیاسپذیری ضعیف مساحت و کارایی، برای پیادهسازی سیستمهای پیچیده و در مقیاس بزرگ امروزی مناسب نیستند[4]. این چالش از یک سو، و مقیاسپذیری و کارایی بالای شبکههای ارتباطی در سیستمهای چندپردازندهای و چند کامپیوتری از سوی دیگر، طراحان و پژوهشگران را بر آن داشت تا ساختار مشابهی را به عنوان جایگزین روشهای سنتی ارتباطات داخل تراشه مطرح نمایند. از این رو، ایدهی شبکه روی تراشه به عنوان یک راهحل امید بخش برای غلبه بر مشکلات فوق مطرح شد[1].
معماری سیستمهای مبتنی بر شبکه روی تراشه شامل دهها و صدها هستهی همگن یا ناهمگن می‌باشد. در حالت همگن همهی هستهها یکسان و در حالت ناهمگن هستههای پردازشی متفاوت از یکدیگر می‌باشند مانند ریزپردازندههای همه منظوره،پردازندهی خاص منظوره، بلوک حافظه، کنترلکنندهی I/O و... است که از طریق یک شبکه ارتباطی مبتنی بر مسیریاب به یکدیگر متصل شدهاند. در هر گره شبکه، هسته پردازشی به یک مسیریاب متصل میشود و این مسیریاب از طریق اتصالات نقطه به نقطه در شبکه ارتباطی به سایر مسیریابها وصل میشود. ارتباط بین گرهها از طریق تولید بستههای داده و ارسال آنها به آدرس گره مقصد بر روی این زیرساخت ارتباطی انجام میشود[14].
همان طور که در شکل 2-1 نشان داده شده است، شبکههای روی تراشه از سه قسمت اصلی تشکیل شدهاند: رابط شبکه، مسیریابها و اتصالات بین مسیریابها. یک اتصال در شبکه روی تراشه شامل دو کانال فیزیکی میباشد که ارتباطی دوطرفه بین مسیریاب‌ها برقرار میکند (دو کانال یک طرفه در دو جهت مخالف). در هر گره شبکه، هسته پردازشی به یک مسیریاب متصل میشود و این مسیریاب از طریق اتصالات در یک شبکهی ارتباطی به سایر مسیریابها وصل میشود. ارتباط بین گرهها از طریق تولید بستههای داده و ارسال آنها بر روی این زیرساخت ارتباطی انجام میشود[14].

شکل STYLEREF 1 \s ‏2 SEQ شکل \* ARABIC \s 1 1- معماری شبکه روی تراشه [15]رابط شبکه ارتباط منطقی بین هسته و مسیریاب را ایجاد میکند زیرا ممکن است هر هسته پردازشی پروتکل ارتباطی مجزا از شبکه داشته باشد بنابراین این رابط این کار را از طریق بستهبندی دادهها در سمت فرستنده و بازکردن بستهها و سپس استخراج دادههای آن در سمت گیرنده برقرار میکند. به بیان دقیقتر، این رابط وظیفهی تبدیل یک پیام به چندین بسته در طرف فرستنده و ترکیب بستهها و بازسازی پیام در سمت مقابل را بر عهده دارد[13]. برای این منظور، رابط شبکه وظیفهی تبدیل دادههای هستهی پردازشی به بستههای قابل انتقال در شبکههای روی تراشه را بر عهده دارد. در طرف دیگر انتقال، رابط شبکه بستههای رسیده را به دادههای قابل فهم برای هستهی پردازشی تبدیل مینماید. همچنین هستههای پردازشی هر کدام یک فرنکانس کاری متفاوتی دارند که برای ارتباط با یکدیگر نیاز به همزمان‌سازی دارند که این همزمان‌سازی توسط رابط شبکه انجام میشود[14].
مسیریابها عناصر اصلی تشکیلدهندهی شبکه روی تراشه میباشند که وظیفه انتقال بستهها را از هسته پردازشی مبدا به هسته پردازشی مقصد برعهده دارند. مسیریابها از میانگیرهای ورودی-خروجی، شبکهی راهگزینی تقاطعی و یک کنترلکننده، تشکیل شدهاند. میانگیرها را میتوان با ثباتها یا حافظهی ایستا پیادهسازی کرد. معمولا هر میانگیر بخشی از یک بسته را در خود جای میدهد. در واقع لزوم استفاده از میانگیر در مسیریاب به خاطر آن است که هنگامی که در شبکه ازدحام رخ میدهد و بسته نمیتواند به مسیرش ادامه دهد، اطلاعات بسته در مسیریاب ذخیره شود. با توجه به شکل 2-2، در یک مسیریاب با p درگاه ورودی و خروجی، یک راهگزین تقاطعی به اندازه p×p ارتباط هر درگاه ورودی به هر درگاه خروجی مسیریاب را فراهم میآورد. کنترلکننده از واحدهای انتخابکنندهی کانال خروجی (مسیریابی)، تخصیصدهندهی کانال خروجی و کانال مجازی و تخصیصدهندهی اولویت تشکیل شده است و وظیفهی آن هدایت بستههای ورودی به یکی از درگاههای خروجی میباشد. به طور کاملتر میتوان این‌گونه بیان کرد که عملیات محاسبهی مسیر و محاسبات واحدتخصیص کانال مجازی تنها برای سرآیند بستهها صورت میگیرد. در واحد محاسبه مسیر، درگاه خروجی که بسته باید به آن ارسال شود به همراه مجموعه کانالهای مجازی مجاز برای بسته، مشخص میگردند. در واحد تخصیص کانال مجازی، یکی از کانالهای مجازی که در واحد قبل مشخص شده بود، به فلیت سرآیند تخصیص داده میشود. واحد تخصیصدهندهی کانال خروجی، یک نوبت زمانی برای استفاده از راهگزین تقاطعی به هر فلیت اختصاص میدهد تا فلیتها از درگاه ورودی به درگاه خروجی مناسب، بدون رخداد تصادم انتقال یابند. سپس بستههایی که به آنها اجازه عبور از راهگزین تقاطعی داده شده است،به کانال خروجی مناسب هدایت میشوند[16].

شکل STYLEREF 1 \s ‏2 SEQ شکل \* ARABIC \s 1 2- ساختار کلی مسیریاب در شبکه روی تراشه [16]هم‌بندی شبکهمعماری شبکه بیانکننده همبندی و سازماندهی فیزیکی اتصالات داخلی شبکه است. همبندی یک شبکه با استفاده از نحوه اتصال گرههای آن که همان مسیریاب‌ها هستند، توسط پیوندها یا کانالهای ارتباطی مشخص میشود. شکل همبندی شبکه میتواند تاثیر زیادی در کارایی شبکه داشته باشد[14]. انتخاب همبندی نخستین گام درطراحی شبکه است زیرا مسیریابی و سیاست کنترل جریان به شدت وابسته به الگوی ارتباطی بین مسیریابها است[17]. تاکنون همبندیهای مختلفی برای شبکه روی تراشه ارائه شده است که مهمترین آنها عبارتند از: ستاره، توری ، هشت وجهی، توری مدور، SPIN و BFT. در شکل 2-3 بعضی از این آرایشها نمایش داده شدهاند[18]. Guerrier و Greinerدر[18] معماری SPIN را برای ارتباطات داخلی راهگزینها بر روی تراشه پیشنهاد کرده‌اند. همانگونه که در شکل 2-3 ج نشان داده شده است این معماری با درختی بیان شده است که در این درخت هر گره چهار فرزند دارد و والدین در هر سطحی چهار دفعه تکرار میشوند. هم‌چنین Kumar در [18] برای NOC یک شبکه توری بر مبنای معماری اتصالات داخلی معروف به CLICHE پیشنهاد کرده است. این معماری شامل یک ساختار توری m×n از راهگزینها است که ارتباط منابع محاسباتی توسط این راهگزینها را برقرار میکند (شکل2-3 ب).

شکل STYLEREF 1 \s ‏2 SEQ شکل \* ARABIC \s 1 3- همبندیهای مختلف شبکه بر روی تراشه، الف) توری مدور، ب) توری، ج) SPIN ، د) BFT، ه) هشت وجهی، و) توری مدور تا خورده [18]مشکل اصلی همبندی توری قطر شبکه میباشدکه تاثیر منفی در کارایی آن دارد. قطر شبکه برابر با بیشینه کوتاهترین مسیرهای ممکن بین هر دو گره در یک شبکه است[19]. شبکه توری مدور در راستای کاهش تاخیر شبکه توری با حفظ سادگی توسطDally و Towlesدر[18] برای معماری NOC پیشنهادشده است. همانگونه که در شکل 2-3 الف ملاحظه میشود در این مدل هر راهگزین 5 درگاه دارد که یکی از آنها به منبع محلی متصل شده و بقیه به نزدیکترین راهگزینهای همسایه متصل شدهاند و تنها تفاوت این همبندی با همبندی توری در راهگزینهای لبه شبکه میباشد که توسط کمربندهایی به راهگزینهای لبه متضاد شبکه متصل شدهاند[20]. به خاطر اینکه اتصالات راهگزینهای انتهایی در مدل توری مدور طولانی است و باید سیمهای بلندتری در شبکه قرار داد در نتیجه تاخیرهای اضافی در شبکه ایجاد میشود که میتوان با چند لایه کردن این مشکل را حل کرد و در نتیجه همبندی توری مدور تاخورده ایجاد میشود[19].
معماری هشتوجهی که توسط Karim و همکارانش پیشنهاد شد، با توجه به شکل 2-3 ه، شامل 8 گره و 12 پیوند دوطرفه میباشد. هر گره یک عنصر پردازشی و یک راهگزین دارد[18]. در معماری BFT، هستههای پردازشی در برگهای درخت و راهگزینها در رئوس قرار گرفتهاند. برای هر گره جفت مقدار (L,P) استفاده میشود که L، سطح گره و P موقعیت گره در آن سطح را نشان میدهد[18]. ویژگی مشترک این همبندیها این است که هستههای پردازشی با کمک راهگزینهای هوشمند با یکدیگر ارتباط برقرار میکنند. در واقع راهگزینها یک بستر مقاوم را برای انتقال داده برای هستههای عملیاتی فراهم میکنند. از میان معماریهای فوق نوع توری مدور تاخورده برای پیاده سازی VLSI مناسب میباشد[18]. با وجودی که شبکههای ارتباطی در معماریهای چندپردازندهای متداول به صورت چندبعدی استفاده میشوند ولی در شبکههای روی تراشه به منظور کوتاه نگه داشتن طول سیمها از همبندیهای دوبعدی استفاده میشود که در این میان همبندی توری با توجه به ساختار ساده و قابلیت پیادهسازی آسان، بیشتر مورداستفاده قرار گرفته است[20].
مسیریابی و الگوریتم‌های مسیریابیمسیریابی یکی از معیارهای مهم در شبکه روی تراشه برای ارتباط بین عناصر پردازشی است. منظور از مسیریابی ارسال بستههای داده از طریق شبکه ارتباطی که توسط همبندی شبکه مشخص شده است، از یک هسته پردازشی به هستهای دیگر در شبکه میباشد. در شبکههای ارتباطی معمولا برای رسیدن از یک گره به گره دیگر، چندین مسیر مختلف وجود دارد. الگوریتمی که مسیر حرکت بسته از گره مبدا به گره مقصد را در شبکه ارتباطی مشخص میکند، الگوریتم مسیریابی نامیده میشود[3]. در طراحی یک الگوریتم مسیریابی، معمولا ویژگیهایی مانند تطبیقپذیری ، عدم حضور بن بست، تحملپذیری خطا و اشکال و یافتن کوتاهترین مسیرها مورد بررسی قرار میگیرند که بسته به کاربرد، ویژگیهای مسیریابی مشخص میشوند[17].
با توجه به شکل 2-4 دستهبندیهای متفاوتی برای الگوریتمهای مسیریابی ارائه شده است[21]. در مسیریابی با آدرس یکتا ، بستههای داده به یک مقصد فرستاده میشوند در حالیکه در مسیریابی با چندین آدرس ، بستههای داده به مقصدهای مختلف فرستاده میشوند. برای ارتباطات روی تراشه، به خاطر وجود ارتباطات نقطه به نقطه بین مولفههای مختلف درون تراشه، روش مسیریابی با آدرس یکتا عملیتر به نظر میآید[21]. معمولا سه معیار محل تصمیمگیری در مورد مسیر، چگونگی مشخص نمودن مسیر و میزان اهمیت طول مسیر برای تقسیمبندی این الگوریتمها به کار برده میشود. براساس محل تصمیمگیری در مورد مسیر، الگوریتمهای مسیریابی به دو دستهی مسیریابی مبدا و مسیریابی توزیع شده تقسیم میشوند. در نوع اول، مسیر در مبدا مشخص میشود و تمام اطلاعات مربوط به آن در بخش سرآیند بسته قرار داده میشود. در حالیکه در الگوریتمهای مسیریابی توزیع شده، در طول مسیر در مورد ادامه آن تصمیمگیری میشود. بنابراین در بخش سرآیند بسته کافی است آدرس مقصد قرار داده شود. در این روش در صورت بسته بودن مسیر امکان تعویض آن وجود دارد[20]. به ترکیب مسیریابی مبدا و مسیریابی توزیعشده، مسیریابی چندمرحله‌ای گفته می‌شود. در مسیریابی متمرکزشده ، یک کنترلکنندهی مرکزی جریان دادهها را در سیستم کنترل میکند[21].
بر اساس چگونگی تعیین مسیر، الگوریتمهای مسیریابی به دو دستهی تطبیقی و قطعی تقسیمبندی میشوند. در الگوریتمهای قطعی، تصمیمگیری فقط براساس آدرس مبدا و مقصد انجام میشود و بنابراین تمام بستههایی که دارای آدرس مبدا و مقصد یکسان هستند، ازمسیر یکسانی عبور میکنند. اما در الگوریتمهای تطبیقی علاوه بر آدرس مبدا و مقصد، ترافیک لحظهای شبکه نیز در تعیین مسیر موثر است و اگر ترافیک مسیر زیاد باشد، امکان تغییر مسیر و استفاده از مسیرهای خلوتتر وجود دارد. بنابراین بستههایی که دارای مبدا و مقصد مشترکی هستند، ممکن است از مسیرهای متفاوت با تاخیرهای مختلف برای انتقال استفاده کنند[20].
الگوریتمهای قطعی معمولا پیادهسازی سادهتری دارند در حالیکه الگوریتمهای تطبیقی معمولا کارایی و تحملپذیری خطای بیشتری را فراهم میکنند. بعضی از شبکهها از ترکیب دو نوع الگوریتم برای مسیریابی استفاده میکنند، به این ترتیب که بعضی از کانالها برای مسیریابی قطعی و بقیه برای مسیریابی تطبیقی استفاده میشوند. در نتیجه در این دسته از الگوریتمها مزایای هر دو روش به قیمت افزایش مساحت، پیچیدگی سیمکشی و احتمالا توان مصرفی، وجود خواهد داشت[20].

شکل STYLEREF 1 \s ‏2 SEQ شکل \* ARABIC \s 1 4- دستهبندی الگوریتمهای مسیریابی [21]براساس طول مسیر، الگوریتمهای مسیریابی به دو دستهی کمینه و غیر کمینه تقسیم میشوند. در نوع اول همیشه از کوتاهترین مسیرها استفاده میشود ولی در الگوریتمهای غیرکمینه، شرط استفاده از کوتاهترین مسیر الزامی نیست و میتوان جهت کاهش تاخیر بستهها از مسیرهای طولانیتر نیز استفاده کرد[20]. در این پایاننامه به خاطر سادگی پیادهسازی از الگوریتم قطعی XY استفاده شده است. بر این اساس در ادامه این الگوریتم به طور خلاصه توضیح داده خواهد شد.
الگوریتم مسیریابی XY :
این الگوریتم از نوع الگوریتمهای قطعی میباشد. در این روش هر بسته ابتدا در جهت محور x مسیریابی میشود و آنقدر این عمل ادامه مییابد تا این که بسته به ستونی برسد که در آن ستون هسته عملیاتی مقصد قرار دارد. سپس مسیریابی در جهت محور y به همین طریق انجام میگیرد تا به هسته مقصد موردنظر برسد[22]. در شکل 2-5 چهار حالت مختلف این الگوریتم نشان داده شده است. این الگوریتم جزء الگوریتم های کمینه است و بستهها کوتاهترین مسیر را بین مبدا و مقصد طی میکنند و برای شبکههای روی تراشه با همبندی توری و توری مدور مناسب است. در این الگوریتم آدرس هر مسیریاب با مختصات آن مشخص میشود بنابراین با فرض اینکه (Sx,Sy) ، (Dx,Dy) و (Cx,Cy) به ترتیب آدرس مسیریابهای مبدا، مقصد و مسیریاب جاری باشند، شبه کد این الگوریتم به صورت شکل 2-6 میباشد. با توجه به شبه کد در این الگوریتم آدرس مسیریاب فعلی (Cx,Cy) با آدرس مسیریاب مقصد(Dx,Dy) که در سرآیند بسته ذخیره شده است، مقایسه میشود. اگر آدرس مسیریاب فعلی با آدرس مسیریاب مقصد برابر باشد، بسته به درگاه محلی مسیریاب جهت تحویل به هسته پردازشی متصل به آن، فرستاده میشود. در غیر این صورت برای حرکت در راستای افقی، آدرس Dx با آدرس Cx مقایسه میشود. اگر Cx<Dx باشد، بسته به درگاه شرقی و اگر Cx>Dx باشد، بسته به درگاه غربی مسیریاب فعلی فرستاده میشود و اگر Cx=Dx باشد، به مفهوم آن است که بسته به ستون مسیریاب مقصد رسیده است و حرکت در راستای افقی پایان مییابد. در این حالت آدرسها در راستای عمودی یعنی Cy و Dy مقایسه میشوند. اگر Cy<Dy باشد، بسته به درگاه جنوبی و اگر Cy>Dy باشد، بسته به درگاه شمالی مسیریاب فعلی فرستاده میشود و اگر Cy=Dy شده باشد، به مسیریاب مقصد رسیده است[23].
راه‌گزینیالگوریتم مسیریابی مسیری که پیغامها باید از مبدا تا مقصد طی کنند، تعیین می‌کند در حالیکه سیاست راهگزینی مشخص میکند که هر پیغام چگونه مسیریاب را طی کند[17]. به عبارتی روش راهگزینی تعیینکنندهی نحوه ذخیره شدن بستهها در مسیریابهای میانی و ارسال آنها به گرهی بعدی میباشد[3]. با توجه به شکل 2-7 روشهای راهگزینی به طور کلی به دو دستهی راهگزینی بستهای و راهگزینی مداری تقسیم میشوند[21].

شکل STYLEREF 1 \s ‏2 SEQ شکل \* ARABIC \s 1 5- مسیرهای پیموده شده توسط الگوریتم XY [23]
شکل STYLEREF 1 \s ‏2 SEQ شکل \* ARABIC \s 1 6- شبه کد الگوریتم مسیریابی XY [23]در راهگزینی مداری ابتدا یک مسیر از گرهی مبدا به گرهی مقصد درشبکه رزرو میشود و سپس ارسال داده آغاز میگردد. با عبور سرآیند بسته که حاوی اطلاعات مسیریابی است از مسیریابهای بین مبدا و مقصد، در حین مسیریابی سرآیند، این مسیر برای آن جریان داده ذخیره میشود. پس از رسیدن بسته سرآیند به مقصد، یک پیغام تایید به مبدا فرستاده میشود تا برقراری مسیر انتقال داده را به اطلاع مبدا برساند[3].به این ترتیب پس از برقراری مسیر، ارسال داده از مبدا به سمت مقصد شروع میشود (شکل 2-8). از جمله مشکلات این روش میتوان به کاهش بهرهوری منابع در شبکه (به علت عدم امکان استفادهی سایر جریانهای داده از منابع، ناشی از در انحصار قرار گرفتن منابع تا پایان عملیات انتقال داده برای یک جریان داده) و سربار زمان برپایی مدار اشاره نمود. از طرفی، این روش راهگزینی، برای پیامهای طولانی و جریانهای ارتباطی که نیاز به پهنای باند تضمین شده دارند، بسیار مناسب است[3].
راهگزینی بستهای، سیاست غالب در شبکههای روی تراشه میباشد. در این روش با توجه به شکل 2-9، پیغامها به تکههایی با اندازهی ثابت به نام بسته شکسته میشوند و هر بسته به صورت مستقل مسیریابی میشود. بنابراین هر بسته باید اطلاعات کنترلی و مسیریابی را برای رسیدن به گرهی مقصد به همراه داشته باشد[20]. با توجه به شکل، در این روش هنگامی که یک بسته توسط گرههای میانی دریافت میشود، چون اطلاعات مسیر را دارد، منتظر دریافت سایر بستههای یک پیغام نمیماند. به همین دلیل، بستههای یک پیغام میتوانند به طور همزمان از چندین مسیر عبور کرده و به مقصد برسند[18].

شکل STYLEREF 1 \s ‏2 SEQ شکل \* ARABIC \s 1 7- روشهای راهگزینی [21]
شکل STYLEREF 1 \s ‏2 SEQ شکل \* ARABIC \s 1 8- راهگزینی مداری [18]
شکل STYLEREF 1 \s ‏2 SEQ شکل \* ARABIC \s 1 9- راهگزینی بستهای [18]راهگزینی بستهای همانگونه که در شکل 2-7 نشان داده شده است به سه دسته تقسیم میشود[21]:
راهگزینی ذخیره و ارسال: در این روش پیامها به بخشهای مستقل کوچکتری به نام بسته تقسیم میشوند و فقط زمانی که بسته به طور کامل به کانال ورودی یک مسیریاب برسد، میتواند به کانال خروجی مدنظر فرستاده شود. در نتیجه، در این روش چون کل بسته ذخیره میشود، حافظهی میانگیر زیادی مورد نیاز است. همچنین اینکار افزایش تاخیر بستهها را به دنبال دارد. از طرفی، این روش برای پیامهای کوتاه که تعداد آنها زیاد نیست، بسیار مناسب است زیرا برخلاف روش راهگزینی مداری، سربار زمان برپایی مدار وجود ندارد[3].
راهگزینی برشی: در این روش کوچکترین واحد داده بسته نمیباشد، بلکه هر بسته به واحدهای کوچکتری به نام فلیت تقسیم میشود و به محض آزاد بودن درگاه خروجی برای یک بسته، فلیتهای آن بسته میتوانند فرستاده شوند، بدون اینکه نیاز باشد کل بسته به درگاه ورودی رسیده باشد. در نتیجه، تاخیر بستهها در این روش نسبت به روش ذخیره و ارسال کاهش مییابد. اگر درگاه خروجی یک بسته اشغال باشد، کل بسته در حافظه میانگیر ذخیره میشود[3].
راهگزینی خزشی: این روش راهگزینی بسیار شبیه راهگزینی برشی است. با این تفاوت که در این روش راهگزینی، اندازهی حافظه میانگیر مورد نیاز نسبت به روش برشی کاهش مییابد[3]. در روش مذکور، همانطور که در شکل 2-10 مشاهده میشود، یک بسته به واحدهای کوچکتری با طول ثابت به نام فلیت تقسیم میشود. هر بسته یک فلیت سرآیند دارد که شامل اطلاعات مسیریابی است و ابتدا مسیریابها را طی و با توجه به اطلاعاتش مسیر را مشخص میکند سپس سایر فلیتها همان مسیر تعیین شده را میپیمایند. در این روش به دلیل اینکه بسته به واحدهای کنترلی کوچکتر شکسته میشود، به فضای میانگیر کمتری نیاز دارد و اندازه حافظه میانگیر ورودی به اندازهی چندین فلیت است[11]. درشبکههای ارتباطی متداول، عرض کانالهای فیزیکی به چند بیت محدود میشوند. بنابراین فلیتها معمولا به قسمتهایی شکسته میشوند که فیت نام داشته و تعداد بیتهای آنها برابر عرض کانال فیزیکی در شبکه میباشد. در شبکههای روی تراشه عرض کانالها به مراتب بیشتر است ولی عناصر حافظه، مساحت و توان مصرفی آنها به عنوان یک عامل محدود کننده باعث شکستن فلیتها به فیتها میشود[20].
در روش راهگزینی خزشی، هنگامی که یک بسته به درگاه خروجی یک مسیریاب نیاز دارد و آن درگاه توسط بستهای دیگر اشغال است، این بسته در شبکه باقی میماند و حافظهی میانگیر مسیریابهای قبلی که در آنها قرار دارد را اشغال میکند. از آن جایی که حافظههای میانگیر به صورت یک صف از نوع اولین ورودی-اولین خروجی پیادهسازی شده‌اند هیچ بسته دیگری نمیتواند از آنها استفاده کند و آن مسیر برای بستههای دیگر مسدود میشود و در اصطلاح ایجاد بنبست میکند[3]. این موضوع در شکل 2-11 نشان داده شده است. راهحل ارائه شده برای این مشکل استفاده از کانالهای مجازی است که در ادامه توضیح داده شده است. روشی که در اکثر طراحیهای شبکههای روی تراشه مورد استفاده قرار میگیرد راهگزینی خزشی میباشد، زیرا در این شبکهها محدودیت حافظه میانگیر وجود دارد. به عبارتی، چون میانگیرها انرژی بالایی را مصرف و سطح زیادی را اشغال میکنند، استفاده از این روش راهگزینی در شبکههای روی تراشه که نیاز به فضای حافظه کمتری نسبت به روش‌های دیگر دارند، مرسوم‌تر می‌باشد[3] (شکل 2-12). علاوه بر این، در این شبکهها نیاز است که تاخیر بستهها حداقل مقدار ممکن را داشته باشد که این روش نسبت به دو روش دیگر تاخیر کمتری دارد [3].

شکل STYLEREF 1 \s ‏2 SEQ شکل \* ARABIC \s 1 10- اجزای یک پیغام در راهگزینی خزشی [11]
شکل STYLEREF 1 \s ‏2 SEQ شکل \* ARABIC \s 1 11- مسدود شدن یک بسته در شبکه و ایجاد بن بست [24]
شکل STYLEREF 1 \s ‏2 SEQ شکل \* ARABIC \s 1 12- روشهای راهگزینی ذخیره و ارسال (a) و خزشی (b) [25]کانال مجازیدر شبکههای روی تراشه با توجه به روش راهگزینی، همه یا قسمتی از بسته در میانگیر ذخیره میشود و چون عملکرد حافظه میانگیر به صورت یک صف اولین ورودی-اولین خروجی است، تا هنگامی که بسته به طور کامل از آن خارج نشود بسته دیگری نمیتواند وارد حافظه میانگیر شود. لذا سایربستهها برای استفاده از کانال فیزیکی باید منتظر خالی شدن حافظه میانگیر بمانند[3]. بنابراین بدون استفاده از کانال مجازی استفاده از پهنای باند کانال فیزیکی کاهش مییابد و دسترسی پیغامها به کانالهای خروجی انحصاری خواهد شد. برای رفع این مشکل و جلوگیری از ایجاد بنبست میتوان از کانالهای مجازی استفاده کرد که پهنای باند کانال فیزیکی را بین چندین جریان ارتباطی به اشتراک میگذارند. کانالهای مجازی همچنین باعث کاهش تاخیر ارسال پیغام در شبکههای خزشی میشوند. با توجه به شکل 2-13 کانالهای مجازی با تسهیم کردن دسترسی به کانال این امکان را فراهم میکنند که کانال فیزیکی با وجود مسدود شدن یک پیغام توسط بقیه پیغامها مورد استفاده قرار گیرد[20].

شکل STYLEREF 1 \s ‏2 SEQ شکل \* ARABIC \s 1 13- تسهیم کردن کانال خروجی و رفع بنبست توسط کانال مجازی [24]نتیجه‌گیریارتباطات روی تراشه یکی از مهمترین عوامل برای افزایش کارایی سیستمهای روی تراشه است. یکی از راهحلهای ارائه شده در زمینهی ارتباط روی تراشه، استفاده از فنآوری شبکه بر روی تراشه است، که مشکلات ارتباطات را تا حد زیادی حل میکند.
در این فصل معماری شبکه روی تراشه به همراه برخی از مهمترین ویژگیهای آن مورد بررسی قرار گرفت. همچنین هر یک از مفاهیم همبندی شبکه و انواع آن، روشهای راهگزینی، مسیریابی و انواع الگوریتمهای مسیریابی و کانال مجازی در شبکه روی تراشه به همراه جزئیات مربوط به هر یک تشریح شدند.
فصل سوم
فصل سوم: مروری بر مفاهیم نگاشت و کارهای انجام شده
مقدمهیک بخش مهم در روند طراحی و ساخت یک شبکه روی تراشه، عملیات نگاشت وظایف یک کاربرد مورد نظر، بر روی یکی از انواع همبندیهای شبکه بر تراشه میباشد. در واقع مسئله نگاشت، بر اساس تابع هدف مورد نظر و معماری شبکه، مشخص کننده‌ی آن است که هر یک از وظایف یک برنامهی کاربردی به کدام عنصر پردازشی در شبکه اختصاص یابد. نتایج نگاشت تاثیر بسزایی بر روی میزان مصرف انرژی، اتلاف توان، میانگین تاخیر، کارایی و سایر معیارهای کیفیت سرویس در شبکه روی تراشه دارد.

پژوهش

دسته‌بندی نشده

No description. Please update your profile.

LEAVE COMMENT

نظرات (0)
امکان ثبت نظر جدید برای این مطلب وجود ندارد.