فهرست مطالب

چکيده……………………………………………………………………. 1

فصل اول: مقدمه

با توسعه فن‌آوری نیمه هادی¬ها امکان تجمیع تعداد زیادی المان پردازشی و حافظه¬ای مختلف شامل پردازنده¬های سیگنال ، سخت¬افزارهای خاص منظوره ، مدارهای منطقی برنامه¬پذیر ، پردازنده¬های همه منظوره و انواع حافظه و مدارات جانبی در داخل یک تراشه فراهم شده است که این مفهوم به سیستم روی تراشه شناخته شده است[1]. در این قبیل سیستم¬ها ارتباطات بین مولفه¬های گوناگون که یک چالش مهم محسوب می‌شود، همان‌طور که در شکل 1-1 نشان داده شده است به صورت نقطه به نقطه یا از طریق گذرگاه¬ها برقرار می‌شود[2]. در اتصالات نقطه به نقطه بين هر دو هسته¬ي پردازشيِ نيازمند به ارتباط، يك اتصال اختصاصي ايجاد مي¬شود. از آن¬جا كه اين روش تنها از سيم¬ها (و بدون استفاده از سخت¬افزار اضافه) براي انتقال داده¬ها استفاده مي¬كند، بهترين كارايي و توان مصرفي را براي برقراري ارتباط بين تعداد كم هسته¬ها ارائه مي¬كند. اما اين روش داراي مشكلات زيادي از جمله عدم مقياس¬پذيري ، پيچيدگي زياد طراحي و مسيريابي اتصالات در سطح مدار و هزينه¬ي پياده¬سازي بالا است. ايرادهاي فوق باعث مي¬شود كه استفاده از اتصالات نقطه به نقطه فقط در سيستم¬هاي كوچك مقرون به صرفه باشد. با بزرگ شدن اندازه¬ي سيستم، استفاده از اتصالات نقطه به نقطه به علت زياد شدن سيم¬هاي مورد نياز و مشكلات طراحي، امكان¬پذير نيست[2]. روش ديگر، يعني معماري ارتباطي مبتني بر گذرگاه، هسته¬هاي پردازشي را با استفاده از يك كانال مشترك به يكديگر ارتباط مي¬دهد. در مقايسه با اتصالات نقطه به نقطه، گذرگاه مشترك پيچيدگي طراحي سطح مدار كم¬تري دارد و چون از كانال¬هاي كم¬تري استفاده می¬کند، هزينه¬ي پياده¬سازي آن نيز پايين¬تر مي¬باشد. اما گذرگاه مشترك دارای مشكل اساسي عدم مقياس¬پذيري توان و كارآيی می‌باشد. با زياد شدن تعداد دستگاه¬هاي متصل به گذرگاه، طول آن و نيز مدارات ارسال و دريافت داده¬ي متصل به آن افزايش يافته و باعث ايجاد يك بار خازني زياد مي¬گردند. تمام اين بار خازني در جريان يك انتقال داده شارژ و دشارژ می¬شود. اين امر، تأخير و توان مصرفي گذرگاه مشترك را به طرز چشم¬گيري افزايش مي¬دهد. افزون بر اين، تمام عناصر متصل به گذرگاه از يك مسير واحد استفاده مي¬نمايند و لذا در هر لحظه فقط دو گره با هم ارتباط دارند و ساير گره¬ها بايد منتظر آزاد شدن كانال بمانند. اين امر موجب كاهش شديد كارآيي سيستم به ويژه هنگامي¬كه عناصر متقاضي ارتباط زياد باشند، می‌شود [4]. با توجه به اين مشكلات، روش گذرگاه نمي¬تواند پاسخگوي نيازهاي ارتباطي تراشه¬هاي آينده باشد. بنابراین نیاز به یک ساختار ارتباطی برای تجمیع تعداد زیادی هسته¬های پردازشی در کنار یکدیگر می¬باشد به طوری که این ساختار ارتباطی مقیاس¬پذیر بوده و کارایی بالا داشته باشد[4].
با افزایش قدرت پردازشی تراشه¬ها پیچیدگی و قابلیت برنامه¬های کاربردی نیز افزایش یافته است و این افزایش پیچیدگی سخت¬افزار و نرم¬افزار در سیستم¬های روی تراشه و پردازنده¬های چند هسته¬ای، به نوبه¬ی خود افزایش حجم و پیچیدگی ترافیک ارتباطی داخل تراشه را موجب می¬شود. از سوی دیگر، کاهش اندازه¬ی مشخصه¬ی ترانزیستورها مشکلات و چالش¬های دیگری را در سطح مدار به ویژه برای ساختارهای ارتباطی درون تراشه، به همراه دارد. مواجهه با این پیچیدگی ارتباطات و هم¬چنین مسائل موجود در فن‌آوری¬های جدید VLSI نیاز به بازنگری روش¬های سنتی ارتباطی درون تراشه را ایجاد کرد و شبکه روی تراشه به عنوان یک طرح ارتباطی درون تراشه¬ای نوین برای رفع و کاهش این مشکلات مورد توجه قرار گرفت[5].
شبکه¬های ارتباطی روی تراشه که Network-on-Chip (NoC) نامیده می¬شوند یک راه¬حل ممکن برای ارتباطات روی تراشه‌ی پلتفرم¬های SOC جهت غلبه بر محدودیت¬های گذرگاه¬ها می¬باشند. شبکه بر تراشه شامل واحدهای عملیاتی است که از طریق شبکه¬ای از مسیریاب‌ها با هم در ارتباط می¬باشند. در این‌جا به جای استفاده از سیم¬های اختصاصی از شبکه برای ارتباط بین مولفه¬ها استفاده می¬شود که موجب تاخیر کمتر، اتلاف توان کمتر و به طور کلی کارایی بالاتری می¬شود[5]. شبکه روی تراشه مزایای زیادی از جمله پودمانی بودن و مقیاس¬پذیری را دارا می¬باشد [2]. هم¬چنین NOC مباحث مربوط به محاسبات و ارتباطات را به طور مجزا انجام می¬دهد[1].

مسئله نگاشت وظایف بر روی هسته‌های پردازشی شبکه

مسئله نگاشت وظایف بر روی هسته‌های پردازشی شبکه

1-1 مقدمه…………………………………………………………………….. 3
1-2 معرفی شبکه روی تراشه…………………………………………….. 5
1-3 مسئله نگاشت در شبکه روی تراشه………………………………… 8
1-4 مفهوم برنامه های کاربردی بیدرنگ………………………………… 10
1-5 مسئله توان در شبکه بر روی تراشه……………………………….. 12
1-6 هدف پایان‌نامه………………………………………………………… 12
1-7 ساختار ادامه پایان‌نامه………………………………………………… 13

برای دانلود رایگان قسمت های بیشتراز فایل به انتهای مطلب مراجعه کنید

فصل دوم: معماری شبکه روی تراشه

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

- معماری شبکه روی تراشه

– معماری شبکه روی تراشه

2-1 مقدمه…………………………………………………………………… 14
2-2 معماری شبکه روی تراشه……………………………………………. 15
2-3 هم‌بندی شبکه…………………………………………………………. 18
2-4 مسیریابی و الگوریتم‌های مسیریابی………………………………… 20
2-5 راه‌گزینی…………………………………………………………………. 23
2-6 کانال مجازی……………………………………………………………… 28
2-7 نتیجه‌گیری……………………………………………………………….. 29

فصل سوم: مروری بر مفاهیم نگاشت و کارهای انجام شده

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

نگاشت دقیق نگاشتی است که بر مبنای برنامه¬نویسی و فرمول¬بندی ریاضی راه¬حل بهینه را به دست می¬آورد. برنامه¬نویسی خطی عدد صحیح ، برنامه¬نویسی خطی غیر عدد صحیح و برنامه¬نویسی خطی ترکیبی سه نوع از مهم-ترین الگوریتم¬های نگاشت دقیق هستند[9]. در [26] یک روش MILP جهت نگاشت وظیفه برای سیستم¬های چندپردازنده¬ای ناهمگن ارائه شده است. در این جا ابتدا به طور حریصانه هسته¬ها بر روی همبندی خاص نگاشت و سپس در مرحله بهبود، موقعیت¬های نسبی هسته¬ها توسط جستجوی ممنوع ثابت می¬شوند. در [27] از روش MILP برای ساخت معماری NOC استفاده شده است که هدف، بهینه سازی و کمینه کردن مصرف توان با در نظر گرفتن محدودیت¬های کارایی می¬باشد. در ILP ، گلوگاه اصلی زمان اجرا می¬باشد که برای کاهش زمان اجرا، گراف وظیفه-ی کاربرد مورد نظر به تعدادی خوشه تقسیم بندی شده است. در [28] یک روش ILP دو مرحله¬ای برای تخصیص وظایف و نگاشت داده روی سیستم چندپردازنده¬ای متقارن ارائه شده است. در [10] ، رقابت در شبکه مورد بررسی قرار گرفته است. در این روش از یک فرمول بندی ILP برای نگاشت کاربرد رقابت-آگاه جهت کمینه کردن رقابت استفاده شده است. در شبکه بر تراشه، سیم¬ها با یک شبکه¬ای از پیوند¬های مشترک جایگزین شده¬اند و مسیریاب¬ها بسته¬های داده را از طریق پیوند¬ها به طور هم¬زمان جابجا می¬کنند. بنابراین ازدحام ترافیک در پیوند¬ها ممکن است موجب کاهش عملکرد سیستم شود. رقابت در شبکه ممکن است در منبع، در مقصد و یا در مسیر باشد. کاهش رقابت در شبکه موجب کاهش تاخیر بسته¬ها می¬شود ولی اتلاف انرژی ارتباطی را افزایش می¬دهد. به دلیل آن که برخی از این روش¬ها زمان پردازش بالایی دارند در [29] جهت غلبه بر این مشکل، گراف وظایف کاربرد را خوشه¬بندی کرده و براساس تعداد خوشه¬ها، معماری توری را به شبکه¬های توری با ابعاد کوچک¬تر تقسیم می¬کند. برای نگاشت خوشه¬ها به زیرشبکه¬های توری مربوطه از فرمولبندی ILP استفاده شده است. در انتها همه¬ی زیرشبکه¬های توری برای تعیین راه¬حل نهایی ادغام می¬شوند. در این مورد زمان پردازنده بهبود پیدا می¬کند اما هزینه ارتباطی خوبی به دست نمی¬آید.
3-2-2 نگاشت مبتنی بر جستجو

دو نوع الگوریتم نگاشت ایستا از نوع مبتنی بر جستجو وجود دارد : 1) نگاشت مبتنی بر جستجوی قطعی 2) نگاشت مبتنی بر جستجوی اکتشافی [9]
نگاشت مبتنی بر جستجوی قطعی :
الگوریتم¬های نگاشت قطعی تمام فضای جستجو را بررسی می¬کنند. الگوریتم شاخه وحد جزء این دسته از الگوریتم¬های نگاشت است. این الگوریتم با جستجوی راه¬حل در شاخه¬های درخت و محدود کردن راه¬حل¬های غیرمجاز، نگاشت مناسب را پیدا می¬کند[9]. این الگوریتم برای مسائل کوچک مناسب است زیرا زمان جستجو با افزایش اندازه مسئله به طور نمایی افزایش می¬یابد[11]. در [30] یک نگاشت انرژی آگاه و در [31] یک نگاشت انرژی و کارایی- آگاه با استفاده از الگوریتم شاخه و حد برای معماری NOC ارائه شده است که با هدف کمینه کردن انرژی ارتباطی، محدودیت¬های طراحی را از طریق رزوکردن پهنای باند برآورده می¬کند. در این جا الگوریتم سعی می¬کند هم¬زمان یک نگاشت بهینه و یک تابع مسیریابی پیدا کند که علاوه بر رعایت محدودیت پهنای باند، انرژی ارتباطی را بهینه کند. در[32] نیز از محدودیت پهنای باند و روش شاخه و حد برای نگاشت استفاده شده است. در روش مذکور ابتدا با استفاده از درخت جستجو یک مجموعه نگاشت با کم¬ترین هزینه ارتباطی پیدا می¬شود و سپس درگام بعدی نگاشت¬هایی با کم¬ترین تاخیر ارتباطی و توان مصرفی باقی می¬مانند. این روش نسبت به روش¬های قبلی از نظر کاهش تاخیر ارتباطی و توان مصرفی بهتر است.

- مثال ادغام دوجمله¬ای

– مثال ادغام دوجمله¬ای

3-1 مقدمه………………………………………………………………….. 30
3-2 روش‌های نگاشت ایستا……………………………………………… 30
3-2-1 نگاشت دقیق……………………………………………………….. 32
3-2-2 نگاشت مبتنی بر جستجو…………………………………………. 33
3-3 روش‌های نگاشت پویا ………………………………………………….46
3-4 نتیجه‌گیری……………………………………………………………… 48

فصل چهارم: روش پیشنهادی

یکی از چالش¬های مهم در تحقیقات مربوط به شبکه روی تراشه، مسئله نگاشت وظایف یک برنامه کاربردی بر روی هسته¬های پردازشی متصل به مسیریاب¬های شبکه می¬باشد. همان گونه که قبلا اشاره شد، برنامه¬های کاربردی انواع مختلفی دارند که یکی از پرکاربردترین آن¬ها، برنامه¬های کاربردی بی‌درنگ با نیازمندی‌های زمانی سخت می‌باشند که در این قبیل کاربردها، وظایف باید مهلت اتمام‌شان را رعایت کنند و از آن زمان تجاوز نکنند. به عبارتی این وظایف باید در تمامی موقعیت¬ها، محاسبات و ارتباطات¬شان به موقع انجام شود. در این فصل ابتدا به معرفی روش پیشنهادی بر مبنای الگوریتم تکاملی ژنتیک برای نگاشت وظایف یک برنامه کاربردی بی‌درنگ سخت بر روی شبکه بر تراشه پرداخته می‌شود و ویژگی‌ها و اهداف این روش مورد بررسی قرار می‌گیرد. سپس اجزای روش پیشنهادی با جزئیات کامل و به طور دقیق‌تری بیان شده‌اند که شامل تحلیل‌های مربوط به زمان‌بندی، تحلیل‌های توان مصرفی، الگوریتم ژنتیک چندهدفه NSGA-II و زیر بخش‌های مختلف آن می‌باشد.
4-2 معرفی طرح کلی روش پیشنهادی
همان طور که در فصل‌های قبل توضیح داده شد، از زمان ظهور شبکه روی تراشه تاکنون تحقیقات قابل توجهی در زمینه نگاشت وظایف برنامه‌های کاربردی انجام شده است که معمولا اهداف نگاشت بهینه کردن کارایی و هزینه NOC بوده است. در شبکه روی تراشه برای ارزیابی کارایی از معیارهایی مانند توان مصرفی، زمان اجرای وظایف و تاخیر انتقال بسته‌ها استفاده می‌شود. از این رو در بسیاری از کارهای انجام شده، با مشخص کردن رابطه‌ای بین نگاشت وظایف روی NOC و این معیارها سعی در بهینه کردن روش‌های نگاشت شده است.
برنامه‌های کاربردی در سیستم‌های نهفته که دارای نیازمندی‌های زمانی بی‌درنگ سخت می‌باشند، ارتباطات زیادی بین مولفه‌های مختلف دارند و نیازمند کارایی و توان محاسباتی بالایی می‌باشند. بنابراین این دسته از کاربردها مناسب¬تر است که از معماری شبکه روی تراشه بهره ببرند[47]. از آن¬جایی که تحقیقات کمی بر روی فراهم آورن ضمانت برای کاربردهای بی‌درنگ بر روی این قبیل سیستم‌ها انجام شده است و اهمیت زیادی نیز دارد، در این پایان‌نامه به ارائه طرحی برای زمان‌بندی برنامه‌های کاربردی بی‌درنگ با نیازمندی‌های زمانی سخت می‌پردازیم. ارتباطات بی¬درنگ بین این قبیل کاربردها، نیازمندی¬های سختی دارد و صحت و درستی آن نه تنها به نتایج ارتباط بلکه به حد نهایی زمان اتمام بستگی دارد. برای یک بسته که در شبکه منتقل می¬شود این حد زمانی برابر تاخیر شبکه بسته است. زیرا یک بسته مانند بسته‌های کنترلی اگر خیلی دیر توسط مقصد دریافت شود درواقع بی¬استفاده خواهد بود. از این رو، بدترین معیار زمانی قابل قبول که تعریف می¬شود مهلت اتمام یک بسته است[11]. بنابراین این کاربردها دارای مجموعه¬ای از وظایف بی¬درنگ می¬باشندکه این وظایف به صورت دوره¬ای یا پراکنده آزاد می¬شوند و با فرستادن پیغام¬هایی با هم در ارتباط هستند. بنابراین یک کاربرد شامل مجموعه¬ای از وظایف بی¬درنگ و ارتباطات بین آن¬ها یا به عبارتی جریان¬های ترافیکی می¬باشد. هر یک از این وظایف دارای یک مهلت اتمام هستند که بیانگر حداکثر زمان مورد نیاز برای پردازش وظیفه و تولید نتایج می¬باشد. هم¬چنین هر جریان ترافیکی بین وظایف نیز دارای مهلت اتمام مشخص می¬باشد که بیانگر حداکثر زمان لازم برای تحویل بسته¬های داده متعلق به وظیفه مبدا، به هسته پردازشی که وظیفه مقصد بر روی آن مستقر شده است، می¬باشد. بنابراین برای رعایت این نیازمندی¬های زمانی، تاخیر ارتباطی بین جریان¬های ترافیکی باید محدود شود. به عبارتی بیشترین تاخیر شبکه برای هر بسته نباید از مهلت اتمام¬اش تجاوز کند.
در اکثر شبکه روی تراشه¬ها برای سرویس¬دادن به جریان¬های ترافیکی که نیاز به استفاده هم¬زمان از منابع شبکه از جمله پیوندها دارند، از روش تسهیم زمانی استفاده می¬شود. در این روش برای تضمین پهنای باند مورد نیاز هر جریان ترافیکی جهت استفاده از منابع، از قبل یک برش زمانی به آن اختصاص داده می¬شود[11] اما در این¬جا همانند [48] از شبکه بر تراشه با کانال¬های مجازی دارای اولویت استفاده می¬شود و بنابراین هر بسته یک اولویت دارد. در این حالت بسته¬های هر جریان ترافیکی با اولویت بالاتر، برای انتقال در سطح شبکه نسبت به بسته¬هایی با اولویت پایین¬تر حق تقدم دارند. مزیت اصلی این روش نسبت به حالت TDM آن است که نیاز به ذخیره منابع از قبل نیست و بنابراین ترافیک¬های با اولویت پایین اگر هیچ درخواستی از جریان¬های ترافیکی اولویت بالاتر وجود نداشته باشد همیشه می-توانند از منابع NOC استفاده کنند[11]. هم¬چنین به خاطر همین در نظر گرفتن اولویت¬ها، رقابت در شبکه قابل پیش-بینی خواهد بود و با استفاده از روش تحلیلی قابلیت زمان¬بندی که در ادامه توضیح داده خواهد شد، می¬توان بیشترین زمانی که یک جریان ترافیکی خاص قبل از انتقال در سطح شبکه باید تحمل کند، محاسبه کرد.

4-1 مقدمه……………………………………………………………………… 49
4-2 معرفی طرح کلی روش پیشنهادی……………………………………. 50
4-3 اجزای طرح پیشنهادی…………………………………………………. 53
4-3-1 مدل کاربرد…………………………………………………………….. 53
4-3-2 مدل معماری شبکه بر تراشه………………………………………. 56
4-3-3 مدل تحلیلی بررسی قابلیت زمانبندی……………………………… 58
4-3-4 مدل تحلیلی توان………………………………………………………. 63
4-3-5 الگوریتم ژنتیک چند هدفه NSGA-IIا………………………………… 64
4-4 نتیجه‌گیری………………………………………………………………… 75

فصل پنجم: ارزیابی نتایج

در این فصل نتایج پیاده‌سازی روش پیشنهادی در محیط ویندوز و نرم‌افزار متلب ارائه می‌شود. نتایج حاصل از آزمایش¬ها از نظر معیارهای مختلف شامل تعداد وظایف و جریان‌های ترافیکی غیر قابل زمانبندی و توان مصرفی مورد ارزیابی و مقایسه قرار گرفته‌اند. در ارزیابی نتایج دو معیار امکان‌پذیری و میزان بهره‌وری راه‌حل‌ها نیز بررسی شده است. همان‌طور که نتایج آزمایشات نشان می‌دهد، روش پیشنهادی با در نظر گرفتن این دو معیار نسبت به روش‌های موجود سریع‌تر به جواب‌های بهینه همگرا می‌شود.
در ادامه این فصل ابتدا معیارهای استفاده‌شده برای ارزیابی الگوریتم¬، تعریف‌شده‌اند. سپس محک مورد استفاده به عنوان برنامه کاربردی برای ورودی الگوریتم معرفی می‌شود و در انتها نیز نتایج به دست آمده از آزمایش‌ها و نمودارهای مربوط به هر یک ارائه‌شده و به طور کامل مورد ارزیابی و تجزیه و تحلیل قرارگرفته است.
معیارهای ارزیابی
به منظور بررسی میزان کارایی روش پیشنهادی برای نگاشت وظایف یک برنامه کاربردی بر روی هسته‌های پردازشی یک شبکه بر تراشه، باید مجموعه جواب‌های تولید شده از جنبه‌های مختلف مورد ارزیابی قرار گیرند تا کارایی الگوریتم مورد نظر مشخص گردد. در این پایان¬نامه برای ارزیابی کارایی هر یک از راه‌حل‌های نگاشت ایجاد شده توسط الگوریتم ژنتیک چند هدفه‌ی NSGA-II از معیارهای شناخته‌شده‌ای شامل میزان اتلاف توان و تعداد وظایف و جریان‌های ترافیکی که قابل زمان‌بندی نیستند و هم‌چنین معیارهای جدید ارائه شده با عنوان امکان‌پذیری و میزان بهره‌وری استفاده شده است. ویژگی¬های هر یک از این معیارها در ادامه این بخش به صورت مختصر توضیح داده‌شده است و بررسی دقیق آن‌ها در بخش نتایج به دست آمده انجام خواهد شد.
در واقع هر یک از راه‌حل‌های نگاشت در الگوریتم ژنتیک توسط تابع برازندگی ارزیابی می‌شوند و همان‌طور که در فصل قبل توضیح داده شد، در این تابع جواب‌ها براساس دو هدف که در حقیقت همان دو معیار زیر می‌باشند، بررسی می‌شوند. این دو معیار در فصل قبل به طور کامل همراه با تحلیل‌های مربوط به هر یک توضیح داده شدند بنابراین در این‌جا مفاهیم هر یک به طور مختصر بیان می‌گردد.
معیار میزان توان مصرفی: این معیار میزان اتلاف توان کلی هر یک ازجواب‌های تولید شده توسط الگوریتم در هر نسل را مشخص می‌کند. این توان ناشی از اجرای وظایف کاربرد مورد نظر بر روی هسته‌های پردازشی مختلف و هم‌چنین انتقال بسته‌های جریان‌های ترافیکی در سطح شبکه است. برای محاسبه‌ی این توان کلی از مدل تحلیلی ارائه شده در معادله‌های 4-7 و 4-8 استفاده می‌شود.
معیار تعداد کل وظایف و جریان‌های ترافیکی غیر قابل زمان‌بندی: در این‌جا منظور از قابلیت زمانبدی آن است که هر یک از وظایف و جریان‌های ترافیکی در محدوده‌ی زمانی تعیین شده‌ی خود، اعمال‌شان را انجام دهند. این اعمال برای وظایف شامل اجرای آن‌ها و برای جریان‌های ترافیکی شامل رساندن بسته‌ها به مسیریاب مقصد می‌باشد. به طور کلی در مسئله نگاشت یکی از مهم‌ترین اهداف یافتن راه‌حل نگاشتی است که در آن همه‌ی وظایف و جریان‌های ترافیکی مربوط به آن‌ها حتی در بدترین موقعیت‌ها مهلت اتمام‌شان رعایت شود و در واقع قابل زمان‌بندی باشند. بنابراین این معیار برای هر راه‌حل تعداد وظایف و جریان‌های ترافیکی که از مهلت اتمام‌شان تجاوز می‌کنند و در واقع قابل زمان‌بندی نیستند، را مشخص می‌کند. واضح است که هر چه این مشخصه برای یک جواب کم‌تر باشد آن جواب بهتر است. برای ارزیابی و محاسبه‌ی این ملاک برای هر یک از راه‌حل‌های ارائه شده توسط الگوریتم ژنتیک از تابع هدف بیان شده در معادله‌ی 4-11 استفاده می‌شود که در این معادله، مدل‌های تحلیلی مطرح شده در معادلات 4-1 و 4-6 به کار برده شده است.
نتایج حاصل از ارزیابی الگوریتم ژنتیک چندهدفه به طور کلی براساس دو معیار فوق می‌باشد. هم‌چنین دو معیار جدید در ادامه ارائه شده است که این دو معیار موجب تسریع در روند همگرایی الگوریتم می‌گردند و در واقع باعث می‌شوند که نتایج سریع‌تر به حالت بهینه‌ی هر یک از دو معیار قبلی برسند. بنابراین در بخش ارزیابی نتایج، آزمایشات انجام شده با/ بدون در نظر گرفتن این ملاک‌های جدید مطرح شده است. این دو معیار جدید ارائه شده عبارتند از:
معیار امکان‌پذیر بودن جواب‌ها: با توجه به این‌که در روش پیشنهادی هسته‌های پردازشی ناهمگن هستند، بنابراین وظایف کاربرد مورد نظر بر روی عناصر پردازشی مختلف زمان اجرای متفاوتی دارند و همان‌گونه که ذکر شد یکی از ویژگی‌های مرتبط با هر وظیفه، مشخصه‌ی (C_i ) ⃗ می‌باشد که بیانگر بدترین زمان اجرای وظیفه‌ی i بر روی هر یک از هسته‌های پردازشی است. اما این وظایف ممکن است بر روی برخی از مولفه‌های پردازشی قابل اجرا نباشند که در این صورت مقدار مربوط به آن هسته در بردار (C_i ) ⃗ آن وظیفه برابر مقدار بی‌نهایت در نظر گرفته می‌شود. واضح است که هنگامی که یک وظیفه بر روی یک هسته‌ی پردازشی قابل اجرا نیست به طور متناظر توان اجرایی مربوط به آن نیز برابر بی‌نهایت فرض می‌شود. بنابراین در این روش تابعی تحت عنوان امکان‌پذیری یا همان Feasibility تعریف شده است که پس از تولید هر راه‌حل در مرحله‌ی ایجاد جمعیت اولیه و توسط هر یک از عملگرهای ژنتیکی تقاطع و جهش، بررسی می‌کند که در هر یک از راه‌حل‌های ایجاد شده جواب غیر قابل قبول وجود نداشته باشد. به عبارتی این تابع در هر جواب جستجو می‌کند که آیا وظیفه‌ای بر روی هسته‌ی پردازشی که بر روی آن قابل اجرا نیست نگاشت شده است یا خیر. اگر چنین وظیفه‌ای یافت شد، از بین هسته‌های پردازشی که وظیفه‌ی مذکور بر روی آن قابل اجرا است، یک هسته به طور تصادفی انتخاب می‌شود و وظیفه‌ی مورد نظر بر روی این هسته‌ی جدید نگاشت می‌شود.

5-1 مقدمه………………………………………………………………………. 77
5-2 معیارهای ارزیابی……………………………………………………………. 77
5-3 معرفی محک مورد استفاده……………………………………………….. 80
5-4 محیط شبیه‌سازی…………………………………………………………… 84
5-5 ارزیابی نتایج ……………………………………………………………………85
5-6 نتیجه‌گیری…………………………………………………………………… 100

برای دانلود رایگان قسمت های بیشتراز فایل به انتهای مطلب مراجعه کنید

فصل ششم: جمع‌بندی و ارائه‌ی پیشنهادات

6-1 مقدمه………………………………………………………………………… 101
6-2 مرور مطالب………………………………………………………………….. 102
6-3 کارهای آینده…………………………………………………………………. 104
6-4 نتیجهگیری……………………………………………………………………. 105
مراجع……………………………………………………………………………….. 106

Abstract

Today, with advances in semiconductor technology, the number of processing elements in a system-on-chip (SOC) is increased. Communication architecture of such systems is based on the bus. Hence, by increasing the number of processing components and due to the lack of bus performance and expandability, the network on-chip or NOC concept as an efficient and scalable inter-chip communication plan, to overcome the buses problems has been proposed. One of the major challenges in the NOC research is the problem of mapping tasks of an application on the homogeneous or even heterogeneous processing cores connected to the network routers. On the other hand, one of the most versatile applications is embedded applications with real-time requirements. In many previous works, the problem of mapping has been investigated for homogeneous processing cores. In other words, although heterogeneous cores are closer to the real application, most of the proposed schemes have ignored this property. In addition, the the characteristic of real-time application wasn’t the main focus of the previous research works. One of the other challenges in the network on-chip is the power consumption in the NOC. In this thesis, at first a survey of the work done in the last one decade in the domain of application mapping is discussed then a new application mapping for hard real time application for heterogeneous core based on multi objective genetic algorithm is proposed. Since, optimal solution is a NP-hard problem, we use genetic algorithm to achieve semi-optimal solutions. In addition, the proposed method prevents infeasible solutions being produced in new generations. This strategy cause that the proposed scheme converge to the pareto-optimal solution faster than other schemes. Experimental results are presented and evaluated using several well-known metrics as well as a new metric. This shows the effectiveness of the proposed method compared to other approaches.



بلافاصله بعد از پرداخت به ایمیلی که در مرحله بعد وارد میکنید ارسال میشود.


فایل pdf غیر قابل ویرایش

قیمت25000تومان

خرید فایل word

قیمت35000تومان