در روش راه­گزینی خزشی، هنگامی که یک بسته به درگاه خروجی یک مسیریاب نیاز دارد و آن درگاه توسط بسته­ای دیگر اشغال است، این بسته در شبکه باقی می­ماند و حافظه­ میانگیر مسیریاب­های قبلی که در آن­ها قرار دارد را اشغال می­ کند. از آن جایی که حافظه­های میانگیر به صورت یک صف از نوع اولین ورودی-اولین خروجی پیاده­سازی شده‌اند هیچ بسته دیگری نمی­تواند از آن­ها استفاده کند و آن مسیر برای بسته­های دیگر مسدود می­ شود و در اصطلاح ایجاد بن­بست می­ کند[۳]. این موضوع در شکل ۲-۱۱ نشان داده شده است. راه­حل ارائه شده برای این مشکل استفاده از کانال­های مجازی است که در ادامه توضیح داده شده است. روشی که در اکثر طراحی­های شبکه ­های روی تراشه مورد استفاده قرار می­گیرد راه­گزینی خزشی می­باشد، زیرا در این شبکه­ ها محدودیت حافظه میانگیر وجود دارد. به عبارتی، چون میانگیر­ها انرژی بالایی را مصرف و سطح زیادی را اشغال می­ کنند، استفاده از این روش راه­گزینی در شبکه ­های روی تراشه که نیاز به فضای حافظه کمتری نسبت به روش‌های دیگر دارند، مرسوم‌تر می‌باشد[۳] (شکل ۲-۱۲). علاوه بر این، در این شبکه­ ها نیاز است که تاخیر بسته­ها حداقل مقدار ممکن را داشته باشد که این روش نسبت به دو روش دیگر تاخیر کمتری دارد [۳].

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

شکل ‏۲‑۱۰- اجزای یک پیغام در راه­گزینی خزشی [۱۱]
شکل ‏۲‑۱۱- مسدود شدن یک بسته در شبکه و ایجاد بن بست [۲۴]
شکل ‏۲‑۱۲- روش­های راه­گزینی ذخیره و ارسال (a) و خزشی (b) [25]
کانال مجازی
در شبکه ­های روی تراشه با توجه به روش راه­گزینی، همه یا قسمتی از بسته در میانگیر ذخیره می­ شود و چون عملکرد حافظه میانگیر به صورت یک صف اولین ورودی-اولین خروجی است، تا هنگامی که بسته به طور کامل از آن خارج نشود بسته دیگری نمی­تواند وارد حافظه میانگیر شود. لذا سایربسته­ها برای استفاده از کانال فیزیکی باید منتظر خالی شدن حافظه میانگیر بمانند[۳]. بنابراین بدون استفاده از کانال مجازی استفاده از پهنای باند کانال فیزیکی کاهش می­یابد و دسترسی پیغام­ها به کانال­های خروجی انحصاری خواهد شد. برای رفع این مشکل و جلوگیری از ایجاد بن­بست می­توان از کانال­های مجازی استفاده کرد که پهنای باند کانال فیزیکی را بین چندین جریان ارتباطی به اشتراک می­گذارند. کانال­های مجازی هم­چنین باعث کاهش تاخیر ارسال پیغام در شبکه ­های خزشی می­شوند. با توجه به شکل ۲-۱۳ کانال­های مجازی با تسهیم کردن[۸۶] دسترسی به کانال این امکان را فراهم می­ کنند که کانال فیزیکی با وجود مسدود شدن یک پیغام توسط بقیه پیغام­ها مورد استفاده قرار گیرد[۲۰].
شکل ‏۲‑۱۳- تسهیم کردن کانال خروجی و رفع بن­بست توسط کانال مجازی [۲۴]
نتیجه‌گیری
ارتباطات روی تراشه یکی از مهم­ترین عوامل برای افزایش کارایی سیستم­های روی تراشه است. یکی از راه­ حل­های ارائه شده در زمینه­ ارتباط روی تراشه، استفاده از فن­آوری شبکه بر روی تراشه است، که مشکلات ارتباطات را تا حد زیادی حل می­ کند.
در این فصل معماری شبکه روی تراشه به همراه برخی از مهم­ترین ویژگی­های آن مورد بررسی قرار گرفت. هم­چنین هر یک از مفاهیم هم­بندی شبکه و انواع آن، روش­های راه­گزینی، مسیریابی و انواع الگوریتم­های مسیریابی و کانال مجازی در شبکه روی تراشه به همراه جزئیات مربوط به هر یک تشریح شدند.
فصل سوم
فصل سوم: مروری بر مفاهیم نگاشت و کارهای انجام شده
مقدمه
یک بخش مهم در روند طراحی و ساخت یک شبکه روی تراشه، عملیات نگاشت وظایف یک کاربرد مورد نظر، بر روی یکی از انواع هم­بندی­های شبکه بر تراشه می­باشد. در واقع مسئله نگاشت، بر اساس تابع هدف مورد نظر و معماری شبکه، مشخص کننده‌ی آن است که هر یک از وظایف یک برنامه­ی کاربردی به کدام عنصر پردازشی در شبکه اختصاص یابد. نتایج نگاشت تاثیر بسزایی بر روی میزان مصرف انرژی، اتلاف توان، میانگین تاخیر، کارایی و سایر معیارهای کیفیت سرویس در شبکه روی تراشه دارد.
در این فصل هدف کلی بررسی برخی مفاهیم نگاشت و مروری بر روی کارهای انجام شده قبلی در زمینه الگوریتم­های نگاشت می­باشد.
روش‌های نگاشت ایستا
روش­های نگاشت در [۹] با توجه به زمانی که وظایف یک کاربرد برای پردازش به هسته­های عملیاتی شبکه روی تراشه، تخصیص داده می­شوند، به نگاشت پویا و نگاشت ایستا طبقه ­بندی می­شوند (شکل ۳-۱).
در نگاشت ایستا، برنامه کاربردی که قرار است بر روی شبکه بر تراشه اجرا شود، در زمان طراحی مشخص است و به طور پویا تغییر نمی­کند. بنابراین نگاشت مربوط به وظایف قبل از اجرای کاربرد و در زمان طراحی مشخص می­ شود. برای یک کاربرد و زیرساخت­های ارتباطی داده شده، با توجه به در دسترس بودن تمامی اطلاعات لازم، الگوریتم نگاشت ایستا سعی می­ کند بهترین مکان وظایف را در زمان طراحی مشخص کند[۱۱]. در این روش چون نگاشت قبل از اجرای کاربرد کامل می­ شود، الگوریتم نگاشت تنها یک بار در زمان کامپایل اجرا می شود. بنابراین روی کارایی مربوط به کاربرد در زمان اجرا تاثیر نمی­گذارد[۷]. در نگاشت ایستا چون پلتفرم برای اجرای کاربرد موردنظر اختصاص یافته، هیچ گونه رفتار پویایی از قبیل اضافه­شدن، حذف یا مهاجرت وظایف در طول زمان اجرا، قابل قبول نیست. بنابراین انتظار می­رود که الگوریتم­های نگاشت ایستا، راه­ حل­های نزدیک به راه­حل بهینه بیشتری ایجادکنند[۱۱]. روش­های نگاشت ایستا به دو دسته­ی نگاشت دقیق[۸۷] و نگاشت مبتنی بر جستجو[۸۸] تقسیم می­شوند[۹].
شکل ‏۳‑۱- طبقه ­بندی روش­های نگاشت [۹]
نگاشت دقیق
نگاشت دقیق نگاشتی است که بر مبنای برنامه­نویسی و فرمول­بندی ریاضی راه­حل بهینه را به دست می ­آورد. برنامه­نویسی خطی عدد صحیح[۸۹]، برنامه­نویسی خطی غیر عدد صحیح[۹۰] و برنامه­نویسی خطی ترکیبی[۹۱] سه نوع از مهم­ترین الگوریتم­های نگاشت دقیق هستند[۹]. در [۲۶] یک روش MILP جهت نگاشت وظیفه برای سیستم­های چندپردازنده­ای ناهمگن ارائه شده است. در این جا ابتدا به طور حریصانه هسته­ها بر روی همبندی خاص نگاشت و سپس در مرحله بهبود، موقعیت­های نسبی هسته­ها توسط جستجوی ممنوع[۹۲] ثابت می­شوند. در [۲۷] از روش MILP برای ساخت معماری NOC استفاده شده است که هدف، بهینه سازی و کمینه کردن مصرف توان با در نظر گرفتن محدودیت­های کارایی می­باشد. در ILP ، گلوگاه اصلی زمان اجرا می­باشد که برای کاهش زمان اجرا، گراف وظیفه­ی کاربرد مورد نظر به تعدادی خوشه تقسیم بندی شده است. در [۲۸] یک روش ILP دو مرحله­ ای برای تخصیص وظایف و نگاشت داده روی سیستم چندپردازنده­ای متقارن[۹۳] ارائه شده است. در [۱۰] ، رقابت در شبکه مورد بررسی قرار گرفته است. در این روش از یک فرمول بندی ILP برای نگاشت کاربرد رقابت-آگاه[۹۴] جهت کمینه کردن رقابت استفاده شده است. در شبکه بر تراشه، سیم­ها با یک شبکه­ ای از پیوند­های مشترک جایگزین شده ­اند و مسیریاب­ها بسته­های داده را از طریق پیوند­ها به طور هم­زمان جابجا می­ کنند. بنابراین ازدحام ترافیک در پیوند­ها ممکن است موجب کاهش عملکرد سیستم شود. رقابت در شبکه ممکن است در منبع، در مقصد و یا در مسیر باشد. کاهش رقابت در شبکه موجب کاهش تاخیر بسته­ها می­ شود ولی اتلاف انرژی ارتباطی را افزایش می­دهد. به دلیل آن که برخی از این روش­ها زمان پردازش بالایی دارند در [۲۹] جهت غلبه بر این مشکل، گراف وظایف کاربرد را خوشه­بندی کرده و براساس تعداد خوشه ­ها، معماری توری را به شبکه ­های توری با ابعاد کوچک­تر تقسیم می­ کند. برای نگاشت خوشه ­ها به زیرشبکه­های توری مربوطه از فرمولبندی ILP استفاده شده است. در انتها همه زیرشبکه­های توری برای تعیین راه­حل نهایی ادغام می­شوند. در این مورد زمان پردازنده بهبود پیدا می­ کند اما هزینه ارتباطی خوبی به دست نمی­آید.
نگاشت مبتنی بر جستجو
دو نوع الگوریتم نگاشت ایستا از نوع مبتنی بر جستجو وجود دارد : ۱) نگاشت مبتنی بر جستجوی قطعی[۹۵] ۲) نگاشت مبتنی بر جستجوی اکتشافی[۹۶] [۹]
نگاشت مبتنی بر جستجوی قطعی :
الگوریتم­های نگاشت قطعی تمام فضای جستجو را بررسی می­ کنند. الگوریتم شاخه وحد[۹۷] جزء این دسته از الگوریتم­های نگاشت است. این الگوریتم با جستجوی راه­حل در شاخه­ های درخت و محدود کردن راه­ حل­های غیرمجاز، نگاشت مناسب را پیدا می­ کند[۹]. این الگوریتم برای مسائل کوچک مناسب است زیرا زمان جستجو با افزایش اندازه مسئله به طور نمایی افزایش می­یابد[۱۱]. در [۳۰] یک نگاشت انرژی آگاه و در [۳۱] یک نگاشت انرژی و کارایی- آگاه[۹۸] با بهره گرفتن از الگوریتم شاخه و حد برای معماری NOC ارائه شده است که با هدف کمینه کردن انرژی ارتباطی، محدودیت­های طراحی را از طریق رزوکردن پهنای باند برآورده می­ کند. در این جا الگوریتم سعی می­ کند هم­زمان یک نگاشت بهینه و یک تابع مسیریابی پیدا کند که علاوه بر رعایت محدودیت پهنای باند، انرژی ارتباطی را بهینه کند. در[۳۲] نیز از محدودیت پهنای باند و روش شاخه و حد برای نگاشت استفاده شده است. در روش مذکور ابتدا با بهره گرفتن از درخت جستجو یک مجموعه نگاشت با کم­ترین هزینه ارتباطی پیدا می­ شود و سپس درگام بعدی نگاشت­هایی با کم­ترین تاخیر ارتباطی و توان مصرفی باقی می­مانند. این روش نسبت به روش­های قبلی از نظر کاهش تاخیر ارتباطی و توان مصرفی بهتر است.
نگاشت مبتنی بر جستجوی اکتشافی :
از آن­جایی که مسائل نگاشت جزء مسایل NP-hard هستند بنابراین برای حل آن­ها در اندازه­ های عملی­شان از روش­های جستجوی اکتشافی استفاده می­ شود. مسائل در اندازه­ های کوچک­تر می­توانند با روش­های قطعی مانند روش شاخه وحد راه حل بهینه را ایجاد کنند[۹].
روش­های اکتشافی شیوه ­های بهینه­سازی و جستجوی شبه­تصادفی هستند که کشف و استخراج فضای راه­حل را براساس تجربه به دست آمده، انجام می­ دهند. این روش­ها هنگامی که جستجوی کامل فضای راه­حل و روش­های قطعی بسیار مشکل باشند و پیچیدگی زمانی به طور نمایی با اندازه مسئله رشد کند، استفاده می­شوند.روش­های اکتشافی در زمان نسبتا کوتاه جواب مناسب را ایجاد می­ کنند[۳۳].
روش­های اکتشافی برای حل مسئله نگاشت کاربرد به دو دسته­ی روش­های اکتشافی قابل تغییر[۹۹] و روش­های اکتشافی سازنده[۱۰۰] تقسیم می­شوند[۹].
روش­های اکتشافی قابل تغییر :
این روش­ها راه­ حل­های نگاشت موجود را تغییر می­ دهند تا به راه­حل بهتر برسند. نمونه ­ای از این روش­های اکتشافی روش­های تکاملی شامل الگوریتم ژنتیک، الگوریتم بهینه­سازی ازدحام ذرات[۱۰۱]، الگوریتم کلونی مورچه[۱۰۲] و… می­باشند[۹].
روش­های اکتشافی قابل تغییر برپایه­ی الگوریتم ژنتیک :
الگوریتم ژنتیک الگوریتم جستجوی تصادفی بر مبنای عملیات ژنتیک طبیعی می­باشد. یک جمعیت ثابت از کروموزوم­ها بعد از چندین نسل از طریق اصل انتخاب طبیعی تکامل می­یابند. هر کروموزوم یک راه حل بالقوه را مشخص می­ کند. برای ایجاد نسل جدید از عملگرهای تقاطع و جهش استفاده می­ شود. عمل تقاطع، دو یا تعدادی کروموزوم والد را انتخاب می­ کند و با ترکیب قسمت­ هایی از آن­ها با هم کروموزوم فرزند را ایجاد می­ کند. عملیات تقاطع می ­تواند تک نقطه یا چندین نقطه باشد. عمل جهش شامل انتخاب یک کروموزوم والد و تغییر برخی از بخش­های آن به طور تصادفی می­باشد. نرخ جهش را می­توان برای کنترل نرخ همگرایی به کمینه­های محلی یا سراسری کنترل کرد. معیار خاتمه می ­تواند ملاک­های متفاوتی باشد از جمله این­که هیچ بهبودی در چند نسل گذشته ایجاد نشده باشد.
در [۳۴] منابع محاسباتی در شبکه روی تراشه شامل مجموعه ­ای از هسته­های پردازشی ناهمگن هستند. در این مقاله یک الگوریتم ژنتیک دو مرحله­ ای برای نگاشت گراف وظایف کاربرد بر روی هسته­های پردازشی شبکه بر تراشه، پیشنهاد شده است به طوری که زمان اجرای کلی گراف وظایف کمینه گردد. برای تخمین زمان اجرا از یک مدل تاخیر بر مبنای تاخیر سیستم و تاخیر یال، استفاده شده است. تاخیر سیستم یک گراف وظیفه برابر تاخیر مسیر بحرانی در اجرای آن و تاخیر یال می‌باشد که تاخیر یال برابر است با میزان تاخیر انتقال داده بین دو راس که بر روی گره­های مختلف NOC نگاشت شده ­اند. در گام نخست با فرض این‌که تاخیر یال­ها ثابت و برابر با میانگین تاخیر می­باشد، وظایف به هسته­های مختلف تخصیص داده می­شوند. در گام دوم هسته­های پردازشی به کاشی­های[۱۰۳] شبکه بر تراشه، نگاشت می­شوند و با در نظر گرفتن تاخیر یال واقعی بر مبنای مدل ترافیکی شبکه، تاخیر کل سیستم کمینه می­گردد. در [۳۵] یک مدل تاخیر برای نگاشت کاربرد روی شبکه بر تراشه ارائه شده است که الگوریتم ژنتیک برمبنای این مدل تاخیر می ­تواند کاربرد مورد نظر را به طور بهینه نگاشت کند به طوری که حداقل میانگین تاخیر را داشته باشد. در این الگوریتم، جمعیت متناسب با موقعیت هسته­ها روی همبندی شبکه بر تراشه است. جمعیت اولیه به طور تصادفی انتخاب می­ شود و تابع برازندگی[۱۰۴] در واقع میانگین زمان انتظار است. برای ایجاد نسل­های بعدی از تقاطع چند نقطه­ای با انتخاب نقاط تقاطع به طور تصادفی استفاده می­ شود. کروموزوم با زمان انتظار کمتر شانس بیشتری برای شرکت در تقاطع دارد. اندازه کروموزوم برابر با تعداد هسته­ها درگراف هسته می­باشد. جهش به طور تصادفی با احتمالی بر روی کروموزوم اعمال می­ شود. این عملیات تکرار می­ شود تا کمترین میانگین زمان انتظار در چندین تکرار، بدون تغییر بماند. بهترین جواب در آخر موقعیت­ مطلوب هسته­ها روی شبکه بر تراشه را نشان می­دهد. در [۳۶] یک الگوریتم ایستایی که از لحاظ انرژی کارا است، ارائه شده است. در واقع این الگوریتم سعی می­ کند مصرف انرژی ارتباطات بین وظایف را در شبکه بر تراشه­ای که ولتاژ پیوندها در آن قابل تنظیم است، بهینه کند. در این جا از سه الگوریتم ژنتیک استفاده شده است که عبارتند از: الگوریتم ژنتیکی برای تخصیص وظایف به هسته­های پردازشی که دارای محدودیت سطح هستند (GA-TA)، الگوریتم ژنتیکی برای تخصیص هسته­های پردازشی به کاشی­های NOC (GA-TM) و یک الگورینم ژنتیک برای پیدا کردن مسیر بهینه (GA-RPA). در هر یک از این الگوریتم­ها ساختارکروموزوم و عملگرهای ژنتیک با توجه به نوع مسئله متفاوت می­باشند.
یک الگوریتم ژنتیک چند هدفه در [۳۷] برای نگاشت کاربرد پیشنهاد شده است که توان مصرفی و ناحیه مصرفی تراشه را کاهش و به طور کلی کارایی را بهبود می­دهد. این روش ابتدا وظایف کاربرد مورد نظر را به هسته­ها تخصیص می­دهد و سپس هسته­ها را به کاشی­های مختلف شبکه بر تراشه، نگاشت می­ کند به طوری که محدودیت­های مسئله را برآورده سازد. در این جا نگاشت هسته­ها همراه با تخصیص مسیریابی انجام می­ شود که این کار بعد از نگاشت وظیفه موجب کاهش فاصله­های ارتباطی می­ شود. در [۳۸] و [۳۹] نویسندگان سعی می­ کنند با بهره گرفتن از الگوریتم ژنتیک چندهدفه SPEA[105] یک مجموعه نگاشت غالب[۱۰۶] پیدا کنند به طوری که اتلاف توان شامل توان محاسباتی و توان ارتباطی کمینه و کارایی بیشینه گردد. مجموعه نگاشت غالب، شامل جواب­هایی است که در آن هیچ نگاشتی یافت نشود که از یکی از نگاشت­های موجود در این مجموعه برتر باشد. در این جا برای بررسی کارایی، تاخیر ارتباطی شامل تاخیر راه ­اندازی، تاخیر شبکه و تاخیر مربوط به مسدود شدن، ارزیابی می­شوند.
در [۴۰] هدف ارائه الگوریتمی است که پاسخ نزدیک به حالت بهینه را در زمان معقولی به دست آورد. به خاطر همین امر در این جا از الگوریتم ژنتیک چند هدفه NSGA-II در دو مرحله مختلف استفاده شده است. همان گونه که در شکل ۳-۲ نشان داده شده است، مرحله اول این الگوریتم شامل بخش محاسباتی است که گراف وظایف یک کاربرد را با هدف کمینه­کردن انرژی محاسباتی توسط کاهش توان مصرفی و کمینه­کردن هزینه کلی منابع، به هسته­های پردازشی مناسب نگاشت می­ کند. در واقع خروجی این مرحله یک گراف ارتباطی بین هسته­ها است. مرحله دوم شامل بخش ارتباطی است که ورودی این مرحله گراف ارتباطی بین هسته­ها و خروجی آن یک نگاشت بهینه بر روی NOC است. در این مرحله هدف نگاشت، کاهش میانگین فاصله ارتباطی بین هسته­ها و کمینه­کردن بیشترین پهنای باند مورد نیاز است.
Task Assignment
Evaluation
Core Tile Mapping
Evaluation
TA-GA
CT-GA
P-I
P-II
شکل ‏۳‑۲- جریان طراحی الگوریتم در [۴۰]
در [۴۱] نیز یک الگوریتم ژنتیک چندهدفه برای نگاشت مجموعه هسته­های پردازشی به معماری شبکه بر تراشه ارائه شده است که اهداف آن بهینه کردن هزینه ارتباطی کلی و مصرف انرژی تحت محدودیت­های پهنای باند است. برای این منظور، با در نظر گرفتن مسیریاب­هایی با چندین کانال مجازی، از یک مدل تحلیلی صف برای ارزیابی تاخیر و از یک مدل آزمایشی در سطح دروازه[۱۰۷] برای ارزیابی انرژی مصرفی، استفاده شده است. همین نویسندگان در [۴۲] یک الگوریتم ژنتیک چند هدفه برای نگاشت هسته­های پردازشی بر روی معماری شبکه ارائه کرده ­اند.به عنوان ورودی مسئله از قبل وظایف کاربرد مورد نظر به هسته­های پردازشی تخصیص داده شده ­اند و معماری شبکه شامل یک همبندی دلخواه با بهره گرفتن از یک الگوریتم مسیریابی فاقد بن بست می­باشد. در این­جا هدف به دست آوردن نگاشتی است که میانگین تاخیر بسته­ها و توان تلف شده کلی شبکه کمینه گردد. برای تسریع در جستجوی فضای طراحی مانند [۴۱] از مدل­های تحلیلی به عنوان توابع هدف استفاده شده است. روش CGMAP که یک روش نگاشت کاربرد مبتنی بر الگوریتم ژنتیک می­باشد، در [۴۳]، پیشنهاد شده است. این روش از عملگر نگاشت بی نظم[۱۰۸] به جای فرایندهای تصادفی در الگوریتم ژنتیک استفاده می­ کند. در این­جا مفهوم دنباله­ی نامنظم با الگوریتم ژنتیک برای به دست آوردن نگاشت بهینه ترکیب شده است. در [۴۴]، GAMR، یک روش نگاشت و مسیریابی بر مبنای الگوریتم ژنتیک است و دارای دو مرحله می­باشد: در مرحله اول ، هسته­های پردازشی بر روی منابع مختلف نگاشت می­شوند. در مرحله دوم یک مسیریابی کمینه قطعی فاقد بن بست برای هر ارتباط برقرار می­ شود بدون این­که مکانی که در گام قبلی برای هر هسته مشخص شده، تغییر کند. در [۴۵] یک الگوریتم A3MAP[109] برای NOC همگن با همبندی توری منظم، NOC ناهمگن با همبندی توری نامنظم و معماری NOC سفارشی[۱۱۰]، پیشنهاد شده است. در این جا مسئله نگاشت توسط دو روش اکتشافی حل می­ شود، الگوریتم آرامش[۱۱۱] به عنوان یک الگوریتم سریع و الگوریتم ژنتیک برای پیدا کردن نگاشت بهتر. نتایج نشان می­دهد که کارایی الگوریتم پیشنهادی در کاهش ترافیک با بهره گرفتن از الگوریتم ژنتیک بهتر از الگوریتم آرامش بوده است. در [۴۶] یک الگوریتم MAIA[112] بر پایه رویکردهای تکاملی پیشنهاد شده است که وظایف کاربرد را جهت کاهش مصرف توان و تاخیر کلی شبکه، نگاشت می­ کند. این الگوریتم یک مجموعه گسترده­ای از ویژگی­ها را جمع می­ کند که جستجوی محلی را بهبود می­دهد. درحالی که با بهره گرفتن از حفظ گوناگونی راه­حل­ها در جمعیت، از همگرایی زود هنگام جلوگیری می­ کند.
یکی از انواع برنامه ­های کاربردی که بیشتر در سیستم­های تعبیه شده مورد استفاده قرار می­گیرند، کاربردهای بی­درنگ می­باشند. در تحقیقات قبلی ذکر شده، نگاشت با هدف بهینه­کردن کارایی و هزینه انجام می­شد و بیشتر سعی می­کردند توان مصرفی و زمان اجرای وظایف را کاهش دهند. اما در برخی از کارهای انجام شده، چون بحث کاربردهای بی­درنگ مطرح است هدف اصلی آن است که تضمین شود همه وظایف و جریان­های ترافیکی بین آن­ها تحت هر سناریویی مهلت اتمام­شان رعایت شود. در [۴۷] الگوریتم ژنتیکی برای نگاشت وظایف یک برنامه کاربردی بی­درنگ با نیازمندی­های زمانی سخت پیشنهاد شده است که در آن از تحلیل­های زمان­بندی ارائه شده در [۴۸] به عنوان تابع برازش استفاده می­ شود. به عبارتی بررسی می­ شود که در هر نگاشت چه تعدادی از ارتباطات بین وظایف، مهلت اتمام­شان را از دست داده­اند که در این تحلیل بیشینه تاخیر شبکه بسته نیز در نظر گرفته می­ شود. در واقع هدف، یافتن نگاشتی است که در آن همه انتقال­های جریان­های ترافیکی بین وظایف قبل از مهلت اتمام­شان به پایان برسد. در [۴۹] نیز کاربردهای بی­درنگ با نیازمندی­های زمانی سخت مطرح است و از همان مدل کاربرد و مدل معماری در [۴۷] استفاده شده است. در این­جا با بهره گرفتن از الگوریتم ژنتیک به دنبال پیدا کردن نگاشتی است که در آن علاوه بر این­که جریان­های ترافیکی مهلت اتمام­شان رعایت شود، وظایفی که بر روی عناصر پردازشی نگاشت می­شوند نیز مهلت اتمام­شان رعایت شود که برای این منظور از یک تحلیل زمان پاسخ[۱۱۳] برای بررسی زمان­بندی وظایف استفاده می­ شود. اگر به ازای هر وظیفه نگاشت شده بر روی یک هسته پردازشی خاص، زمان پاسخ آن وظیفه از مهلت اتمام آن کمتر یا مساوی باشد بیانگر آن است که مجموعه وظایف بر روی آن هسته قابل زمان­بندی[۱۱۴] هستند. هم­چنین این الگوریتم علاوه بر نگاشت وظایف، ترتیب اولویت آن­ها را بررسی می­ کند. در الگوریتم ژنتیک به کار برده شده، از انتخاب مسابقه­ای با اندازه­ های ۲ و ۵ استفاده شده است و برای نمایش کروموزوم­ها روش­های index، standard-binary، gray-coding، xypairs و allXsAllYs به کار رفته است. در این­جا دو تابع برازش وجود دارد: ۱) F0 : بیانگر تعداد وظایف و ارتباطاتی است که مهلت اتمام­شان را از دست داده­اند. ۲) : در این تابع زمان پاسخ هنگامی که مقدار آن از بگذرد، به بی­نهایت تنظیم می­ شود. حد n به عنوان ورودی مسئله است و مهلت اتمام وظیفه‌ی i می‌باشد.
در [۵۰] یک روش برای نگاشت وظایف کاربرد بی­درنگ با نیازمندی­های زمانی سخت، پیشنهاد شده است به طوری که نیازمندی­های زمانی وظایف و ارتباطات بین آن­ها در همه حالات برآورده شود و در عین حال اتلاف توان نیز کمینه گردد. برای پیاده­سازی این روش نگاشت از یک الگوریتم ژنتیک چند هدفه NSGAII استفاده شده است. ساختار کروموزوم به‌گونه‌ای است که اندیس ژن‌ها بیانگر وظایف و مقدار هر ژن در داخل کروموزوم بیانگر شماره­ هسته پردازشی است که وظیفه بر روی آن نگاشت شده است. در این­جا فرض شده است که شبکه بر تراشه شامل هسته­های پردازشی همگن می­باشد و بنابراین در تحلیل­های توان تنها اتلاف توان در انتقال اطلاعات از یک عنصر پردازشی به عنصری دیگری در نظر گرفته شده است. بنابراین در الگوریتم ژنتیک به کار رفته، دو تابع هدف وجود دارد. تابع هدف اول برای کمینه­کردن تعداد وظایف و جریان­های ترافیکی که قابل زمان­بندی نیستند و از مهلت اتمام­شان تجاوز می­ کنند و تابع هدف دوم برای کمینه کردن اتلاف توان می­باشد. برای عمل تقاطع از تقاطع یک نقطه­ای و برای عمل جهش از تغییر درصدی از ژن­ها (با توجه به نرخ جهش) استفاده شده است. عمل انتخاب نیز بر اساس انتخاب مسابقه­ای دودویی می­باشد.
اشکال اصلی الگوریتم ژنتیک نرخ پایین همگرایی است. برای افزایش نرخ همگرایی و این که سریع­تر جواب نهایی به دست آید، باید نرخ جهش افزایش یابد.
روش­های اکتشافی قابل تغییر برپایه­ی الگوریتم ازدحام ذرات و کلونی مورچه :
الگوریتم ازدحام ذرات یک روش تصادفی مبتنی بر جمعیت است که از رفتار دسته جمعی پرندگان الهام گرفته شده است. در این الگوریتم چندین راه­حل داوطلب، هم­زمان با هم وجود دارد. هر راه­حل را یک ذره می­گویند که یک مقدار برازندگی دارد. حرکت ذرات در فضای مسئله، با توجه به تجربه خود ذره و تجربه ذرات همسایه انجام می­ شود[۹].
در [۵۱]، یک الگوریتم نگاشت کاربرد دو مرحله­ ای مبتنی بر الگوریتم PSO ارائه شده است که انرژی ارتباطی شبکه بر تراشه را کمینه و برای ایجاد تعادل در بار پیوند، از مسیریابی استفاده می­ کند. ساختار ذره و ایجاد ذرات اولیه شبیه ساختار کروموزوم و روش­­های الگوریتم ژنتیک می­باشد. در [۵۲] ، PSMAP ، یک روش فرااکتشافی با بهره گرفتن از PSO برای کاهش هزینه پویا و ایستای شبکه بر تراشه دو بعدی می­باشد. یک ذره، متناسب با نگاشت مناسب هسته­ها به مسیریاب­ها می­باشد. مثالی از ساختار یک ذره در شکل ۳-۳ نشان داده شده است. اگر تعداد مسیریاب­ها(گره­ها) در گراف همبندی از تعداد هسته­ها در گراف هسته­ها بیشتر باشد، تعدادی گره اضافی به گراف هسته افزوده می­ شود تا دو عدد مثل هم شوند. گره­های اضافی به همه هسته­ها و خودشان متصل می­شوند. یالی که گره­های اضافی را به یکدیگر یا به هسته­ها متصل کرده است هزینه­اش صفر می‌باشد. اگر فرض شود تعداد هسته­ها در گراف هسته بعد از اضافه کردن گره­های اضافی درصورت نیاز N باشد و N گره هم در گراف همبندی وجود داشته باشد، یک ذره شامل جایگشت اعداد از ۱ تا N است که مکان هسته­ها به گره­های گراف همبندی را نشان می­دهد. هزینه ارتباطی نهایی بستگی به موقعیت هسته­ها در ذره دارد. در اینجا هزینه ارتباطی کلی به عنوان تابع برازش در نظر گرفته می­ شود.
شکل ‏۳‑۳- ساختار ذره در الگوریتم PSO [52]

موضوعات: بدون موضوع  لینک ثابت


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