Offsprings :
شکل ‏۴‑۱۱- روش تقاطع تک نقطه­ای [۵۰]
تقاطع در الگوریتم ژنتیک باعث از بین رفتن پراکندگی یا تنوع ژنتیکی جمعیت می‌شود زیرا اجازه می‌دهد ژن‌های خوب یکدیگر را بیابند. بر اساس مباحث تئوری تقاطع، اعضا با تطابق بالا باعث به وجود آمدن اعضایی می‌شوند که از تطابق میانگین، تطابق بیشتری دارند.
عملگر جهش^[۱۷۹] : در طبیعت برخی عوامل باعث به وجود آمدن تغییرات غیرقابل‌پیش‌بینی در کروموزم‌ها می‌شوند. از آن­جایی که الگوریتم‌های ژنتیکی از قانون تکامل پیروی می‌کنند، در این الگوریتم‌ها نیز عملگر جهش با احتمال کم اعمال می‌شود. به‌طورکلی، گاهی اوقات در الگوریتم ژنتیک برای آن­که فرزندان بتوانند برخی ویژگی­هایی که در والدینشان وجود نداشته است، به دست آورند از عملگر جهش استفاده می­ شود. این عملگر از قرار گرفتن الگوریتم ژنتیک در بهینه­ محلی جلوگیری می‌کند و همچنین با بهره گرفتن از آن می­توان فضاهای ناشناخته مسئله را جستجو نمود. در جهش ممکن است ژنی از مجموعه ژن‌های جمعیت حذف شود یا ژنی که تا به حال در جمعیت وجود نداشته است به آن اضافه شود. البته جهش نباید زیاد صورت بگیرد زیرا در این حالت الگوریتم ژنتیک به جستجوی کاملاً تصادفی تبدیل خواهد شد. جهش یک ژن به معنای تغییر آن ژن است و وابسته به نوع کدگذاری، روش‌های متفاوتی برای اعمال آن استفاده می‌شود.

در روش پیشنهادی، از اعضای جمعیت به تعداد نرخ جهش به طور تصادفی انتخاب می­ شود و سپس به ازای هر عضو انتخاب شده، یکی از ژن­ها به طور تصادفی برگزیده می­ شود. در این مسئله طول کروموزوم برابر با تعداد وظایف می­باشد و بنابراین ژنی به طور تصادفی از بازه­ی [۱… n] انتخاب می­ شود. حال با توجه به این­که ژن انتخاب شده شامل وظیفه مورد نظر و هسته پردازشی نگاشت شده بر روی آن می­باشد به طور مثال فرض می­ شود وظیفه i انتخاب شده بر روی هسته پردازشی j نگاشت شده است. همان­طور که گفته شد، هر وظیفه دارای برداری است شامل اتلاف توان حاصل از اجرای وظیفه مذکور بر روی هسته­های پردازشی مختلف. بنابراین برای اعمال عملگر جهش ابتدا بررسی می­ شود که آیا این وظیفه i انتخاب شده بر روی هسته­ی نگاشت شده فعلی (هسته­ی j) دارای کم­ترین توان مصرفی هست یا نه. اگر وظیفه i دارای کمترین توان مصرفی بر روی هسته­ی j باشد، در این صورت ژن دیگری در این کروموزوم به طور تصادفی انتخاب می­ شود و محتوای این دو ژن که شامل هسته­های پردازشی وظایف مربوط به آن­ها است، جابجا می­گردد. حال اگر وظیفه­ی i دارای کم­ترین توان مصرفی بر روی هسته پردازشی j نباشد، با توجه به بردار مربوط به اتلاف توان اجرای وظیفه­ی i بر روی هسته­های مختلف، هسته­ی پردازشی که این وظیفه بر روی آن کم­ترین توان مصرفی را دارد، یافت می­ شود و با هسته­ی j جایگزین می­گردد.
همان­گونه که ملاحظه می­ شود، در این الگوریتم به دلیل آن­که یکی از اهداف مسئله، کمینه­کردن توان مصرفی می­باشد، سعی شده است که عملگر جهش علاوه بر ایجاد تغییرات تصادفی در ساختار ژن­ها که به طور معمول انجام می­ شود، به گونه ­ای توان مصرفی را کاهش دهد.
ایجاد جمعیت جدید: پس از اعمال عملگرهای ژنتیکی مجموعه ­ای از جواب­های جدید ایجاد می­ شود. همان­طور که در مراحل الگوریتم ذکر شد، در مرحله ۶، نسل جدید فرزندان با نسل قبل که شامل والدین است، تجمیع می­ شود. برای ادامه روند الگوریتم لازم است از روشی مناسب استفاده نمود تا بهترین جواب­ها با توجه به اندازه جمعیت به نسل بعد منتقل شوند. در روش پیشنهادی، پس از ایجاد جمعیت اولیه و اعمال هر یک از عملگرهای جهش و تقاطع، کیفیت هر راه­حل ایجاد شده توسط تابع برازندگی مشخص می­ شود. سپس در مرحله ۷ که شامل عملیات چندهدفه می­باشد، هر یک از جواب­ها در جمعیت تجمیع شده به کمک روش مرتب­سازی نامغلوب در جبهه­ی مربوط به خود قرار می­گیرند. شماره جبهه­ی هر جواب، رتبه­ی آن را مشخص می­ کند. هرچه این شماره کمتر باشد جواب بهتر است. سپس به کمک روش فاصله ازدحام فاصله هر جواب نسبت به جواب­های دیگر در همان جبهه مشخص می­ شود. هر جوابی که دارای مقدار بیشتری باشد نشان‌دهنده آن است که در بخش­های خلوت­تر از فضای پاسخ واقع شده است و در نتیجه دارای الویت بالاتری خواهد بود. دادن الویت بالاتر به این دست جواب­ها سبب خواهد شد تا جستجو به سمت فضاهای ناشناخته گرایش پیدا کند. بنابراین در مرحله­ مرتب­کردن جواب­ها در عملیات چند هدفه، ابتدا جواب­ها براساس فاصله­ی ازدحام­شان به صورت نزولی مرتب می­شوند و سپس براساس رتبه­شان که همان شماره­ جبهه­ی هر جواب می­باشد، به صورت صعودی مرتب می­شوند. در نتیجه راه­حل­هایی که از لحاظ شماره جبهه بهتر هستند بالاتر قرار می­گیرند و در درون جبهه جواب­هایی که از نظر فاصله­ی ازدحام بهتر هستند بالاتر قرار می­گیرند. حال برای انتخاب جمعیت جدید جهت ادامه­ الگوریتم، چون جواب­ها اکنون مرتب شده هستند، از ابتدا به تعداد اندازه­ جمعیت انتخاب می­ شود زیرا بهترین جواب­ها بالاتر قرار گرفته­اند (مرحله ۸) . انجام این کار باعث می­ شود بهترین جواب­ها در نسل­های بعد نیز باقی بمانند و بر اثر عملگرهای ژنتیکی از بین نروند که در الگوریتم ژنتیک به این ویژگی، نخبه سالاری^[۱۸۰] گفته می­ شود. پس از انتخاب بهترین جواب­ها برای نسل بعد، چون ممکن است این جواب­های جدید دوباره بر یکدیگر غلبه کنند، بنابراین این عملیات چندهدفه بار دیگر بر روی جمعیت نهایی انتخاب شده اعمال می­ شود (مرحله ۹). در نهایت به ابتدای حلقه بازگشته و تا برقراری شرط توقف این عملیات تکرار می­ شود.
نتیجه‌گیری
یک برنامه کاربردی بی­درنگ دارای تعدادی وظیفه و ارتباطات بین آن­ها با عنوان جریان­های ترافیکی می­باشد. هر یک از این وظایف و جریان­های ترافیکی دارای ویژگی­هایی از جمله نیازمندی­های زمانی سخت می­باشند. در این فصل روشی بر مبنای الگوریتم ژنتیک چندهدفه NSGA-II ، برای نگاشت این دسته از برنامه ­های کاربردی بر روی هسته­های پردازشی شبکه بر تراشه ارائه گردید. در روش پیشنهادی هسته­های پردازشی شبکه از نوع ناهمگن می­باشند و به عبارتی عناصر پردازشی متفاوت هستند. در این الگوریتم دو هدف وجود دارد: ۱) کمینه کردن اتلاف توان کلی که ناشی از اتلاف توان برای انتقال بسته­های اطلاعاتی در سطح شبکه و اتلاف توان اجرای وظایف بر روی مولفه­های پردازشی است. ۲) کمینه کردن تعداد وظایف و جریان­های ترافیکی که قابل زمان­بندی نیستند و مهلت اتمام­شان رعایت نشده است.
در این فصل هم­چنین مدل­های تحلیلی مربوط به زمان­بندی و توان مصرفی و جزئیات الگوریتم ژنتیک از جمله نحوه­ نمایش جواب­ها، ایجاد جمعیت اولیه­ای، عملگرهای ژنتیکی و … توضیح داده شدند.
فصل پنجم
ارزیابی نتایج
مقدمه
در این فصل نتایج پیاده‌سازی روش پیشنهادی در محیط ویندوز و نرم‌افزار متلب ارائه می‌شود. نتایج حاصل از آزمایش­ها از نظر معیارهای مختلف شامل تعداد وظایف و جریان‌های ترافیکی غیر قابل زمانبندی و توان مصرفی مورد ارزیابی و مقایسه قرار گرفته‌اند. در ارزیابی نتایج دو معیار امکان‌پذیری و میزان بهره‌وری راه ‌حل ‌ها نیز بررسی شده است. همان‌طور که نتایج آزمایشات نشان می‌دهد، روش پیشنهادی با در نظر گرفتن این دو معیار نسبت به روش‌های موجود سریع‌تر به جواب‌های بهینه همگرا می‌شود.
در ادامه این فصل ابتدا معیارهای استفاده‌شده برای ارزیابی الگوریتم­، تعریف‌شده‌اند. سپس محک مورد استفاده به عنوان برنامه کاربردی برای ورودی الگوریتم معرفی می‌شود و در انتها نیز نتایج به دست آمده از آزمایش‌ها و نمودارهای مربوط به هر یک ارائه‌شده و به طور کامل مورد ارزیابی و تجزیه و تحلیل قرارگرفته است.
معیارهای ارزیابی
به منظور بررسی میزان کارایی روش پیشنهادی برای نگاشت وظایف یک برنامه کاربردی بر روی هسته‌های پردازشی یک شبکه بر تراشه، باید مجموعه جواب‌های تولید شده از جنبه‌های مختلف مورد ارزیابی قرار گیرند تا کارایی الگوریتم مورد نظر مشخص گردد. در این پایان نامه برای ارزیابی کارایی هر یک از راه‌ حل ‌های نگاشت ایجاد شده توسط الگوریتم ژنتیک چند هدفه‌ی NSGA-II از معیارهای شناخته‌شده‌ای شامل میزان اتلاف توان و تعداد وظایف و جریان‌های ترافیکی که قابل زمان‌بندی نیستند و هم‌چنین معیارهای جدید ارائه شده با عنوان امکان‌پذیری و میزان بهره‌وری استفاده شده است. ویژگی­های هر یک از این معیارها در ادامه این بخش به صورت مختصر توضیح داده‌شده است و بررسی دقیق آن‌ها در بخش نتایج به دست آمده انجام خواهد شد.
در واقع هر یک از راه‌ حل ‌های نگاشت در الگوریتم ژنتیک توسط تابع برازندگی ارزیابی می‌شوند و همان‌طور که در فصل قبل توضیح داده شد، در این تابع جواب‌ها براساس دو هدف که در حقیقت همان دو معیار زیر می‌باشند، بررسی می‌شوند. این دو معیار در فصل قبل به طور کامل همراه با تحلیل‌های مربوط به هر یک توضیح داده شدند بنابراین در این‌جا مفاهیم هر یک به طور مختصر بیان می‌گردد.
معیار میزان توان مصرفی: این معیار میزان اتلاف توان کلی هر یک ازجواب‌های تولید شده توسط الگوریتم در هر نسل را مشخص می‌کند. این توان ناشی از اجرای وظایف کاربرد مورد نظر بر روی هسته‌های پردازشی مختلف و هم‌چنین انتقال بسته‌های جریان‌های ترافیکی در سطح شبکه است. برای محاسبه‌ی این توان کلی از مدل تحلیلی ارائه شده در معادله‌های ۴-۷ و ۴-۸ استفاده می‌شود.
معیار تعداد کل وظایف و جریان‌های ترافیکی غیر قابل زمان‌بندی: در این‌جا منظور از قابلیت زمانبدی آن است که هر یک از وظایف و جریان‌های ترافیکی در محدوده‌ی زمانی تعیین شده‌ی خود، اعمال‌شان را انجام دهند. این اعمال برای وظایف شامل اجرای آن‌ها و برای جریان‌های ترافیکی شامل رساندن بسته‌ها به مسیریاب مقصد می‌باشد. به طور کلی در مسئله نگاشت یکی از مهم‌ترین اهداف یافتن راه‌حل نگاشتی است که در آن همه‌ی وظایف و جریان‌های ترافیکی مربوط به آن‌ها حتی در بدترین موقعیت‌ها مهلت اتمام‌شان رعایت شود و در واقع قابل زمان‌بندی باشند. بنابراین این معیار برای هر راه‌حل تعداد وظایف و جریان‌های ترافیکی که از مهلت اتمام‌شان تجاوز می‌کنند و در واقع قابل زمان‌بندی نیستند، را مشخص می‌کند. واضح است که هر چه این مشخصه برای یک جواب کم‌تر باشد آن جواب بهتر است. برای ارزیابی و محاسبه‌ی این ملاک برای هر یک از راه‌ حل ‌های ارائه شده توسط الگوریتم ژنتیک از تابع هدف بیان شده در معادله‌ی ۴-۱۱ استفاده می‌شود که در این معادله، مدل‌های تحلیلی مطرح شده در معادلات ۴-۱ و ۴-۶ به کار برده شده است.
نتایج حاصل از ارزیابی الگوریتم ژنتیک چندهدفه به طور کلی براساس دو معیار فوق می‌باشد. هم‌چنین دو معیار جدید در ادامه ارائه شده است که این دو معیار موجب تسریع در روند همگرایی الگوریتم می‌گردند و در واقع باعث می‌شوند که نتایج سریع‌تر به حالت بهینه‌ی هر یک از دو معیار قبلی برسند. بنابراین در بخش ارزیابی نتایج، آزمایشات انجام شده با/ بدون در نظر گرفتن این ملاک‌های جدید مطرح شده است. این دو معیار جدید ارائه شده عبارتند از:
معیار امکان‌پذیر بودن جواب‌ها: با توجه به این‌که در روش پیشنهادی هسته‌های پردازشی ناهمگن هستند، بنابراین وظایف کاربرد مورد نظر بر روی عناصر پردازشی مختلف زمان اجرای متفاوتی دارند و همان‌گونه که ذکر شد یکی از ویژگی‌های مرتبط با هر وظیفه، مشخصه‌ی می‌باشد که بیانگر بدترین زمان اجرای وظیفه‌ی i بر روی هر یک از هسته‌های پردازشی است. اما این وظایف ممکن است بر روی برخی از مولفه‌های پردازشی قابل اجرا نباشند که در این صورت مقدار مربوط به آن هسته در بردار آن وظیفه برابر مقدار بی‌نهایت در نظر گرفته می‌شود. واضح است که هنگامی که یک وظیفه بر روی یک هسته‌ی پردازشی قابل اجرا نیست به طور متناظر توان اجرایی مربوط به آن نیز برابر بی‌نهایت فرض می‌شود. بنابراین در این روش تابعی تحت عنوان امکان‌پذیری یا همان Feasibility تعریف شده است که پس از تولید هر راه‌حل در مرحله‌ی ایجاد جمعیت اولیه و توسط هر یک از عملگرهای ژنتیکی تقاطع و جهش، بررسی می‌کند که در هر یک از راه‌ حل ‌های ایجاد شده جواب غیر قابل قبول وجود نداشته باشد. به عبارتی این تابع در هر جواب جستجو می‌کند که آیا وظیفه‌ای بر روی هسته‌ی پردازشی که بر روی آن قابل اجرا نیست نگاشت شده است یا خیر. اگر چنین وظیفه‌ای یافت شد، از بین هسته‌های پردازشی که وظیفه‌ی مذکور بر روی آن قابل اجرا است، یک هسته به طور تصادفی انتخاب می‌شود و وظیفه‌ی مورد نظر بر روی این هسته‌ی جدید نگاشت می‌شود.
معیار میزان بهره‌وری هسته‌های پردازشی: در این­جا فرض شده است که هر هسته پردازشی قابلیت اجرای چندین وظیفه را دارد. در واقع هر هسته برای انجام زمان­بندی وظایف، دارای صف­های اولویت­دار می­باشد و از داوری انحصاری اولویتی استفاده می­ کند. به عبارتی وظیفه با اولویت بالاتر برای اجرا شدن توسط هسته مربوطه نسبت به وظایف اولویت پایین­تر حق تقدم دارد. در حقیقت هسته‌های پردازشی، یک ظرفیت پردازشی دارند و هر وظیفه‌ی i دارای میزان بهره‌وری بر روی هر هسته‌ی پردازشی j می‌باشد[۷۹]. در واقع میزان بهره‌وری یک وظیفه بر روی یک هسته بیانگر بخشی از ظرفیت پردازشی مورد نیاز آن وظیفه بر روی هسته‌ی نگاشت شده می‌باشد [۸۰]. هدف از به کار بردن آزمون میزان بهره‌وری هسته‌های پردازشی، بررسی این موضوع می‌باشد که همه‌ی وظایف نگاشت شده بر روی یک هسته‌ی خاص از ظرفیت آن هسته تجاوز نکنند[۸۱]. بنابراین برای هر هسته‌ی پردازشی، میزان بهره‌وری برابر است با مجموع میزان بهره‌وری وظایفی که بر روی این هسته نگاشت شده‌اند که این مقدار نباید از یک تجاوز کند. به عبارتی برای هر هسته‌ی j باید شرط زیر برقرار باشد [۷۹].
۵‑۱
معرفی محک^[۱۸۱] مورد استفاده
برای ارزیابی روش تحلیلی پیشنهادی، برنامه‌ی کاربردی انتخاب شده به عنوان محک، یک وسیله نقلیه‌ی خودمختار^[۱۸۲] می‌باشد. این کاربرد مثال خوبی از یک برنامه کاربردی با ارتباطات موازی بر روی یک سیستم نهفته همراه با حجم بالای جریان‌های ارتباطی می‌باشد[۷۵]. در این نوع از کاربردها برای تضمین سرویس‌های ارتباطی لازم است از محدودیت‌های زمانی استفاده شود.
مدل کاربرد وسیله نقلیه‌ی خودمختار که در این‌جا در نظر گرفته شده است شامل یک سیستم هدایت^[۱۸۳] و یک سیستم کنترل وسیله نقلیه^[۱۸۴] می‌باشد.سیستم هدایت برای تشخیص یک فضای نامعلوم طراحی شده است. در واقع این سیستم پایگاه داده‌ی مربوط به موانع را با بهره گرفتن از اطلاعات به دست آمده توسط حسگرهای فراصوتی^[۱۸۵] و عکس‌برداری^[۱۸۶] تکمیل می‌کند. این سیستم هم‌چنین با توجه به شکل ۵-۱ دارای سیستم کنترل جهت^[۱۸۷] و پایداری^[۱۸۸] می‌باشد.شکل ۵-۱ ساختار اصلی این کاربرد را نشان می‌دهد[۱۳].
با توجه به شکل دو دوربین در جمع‌ آوری اطلاعات موانع نقش کلیدی دارند. هر یک ازآ‌ها با سرعت ۲۵ فریم بر ثانیه به سیستم بازخورد می‌دهد و هر فریم دارای وضوح ۴۸۰×۶۴۰ و نمایش ۸ بیت رنگ می‌باشد. هر فریم دارای اطلاعات لازم برای تخمین پس زمینه و استخراج ویژگی می‌باشد. با بهره گرفتن از اطلاعات دو دوربین فاصله‌ی وسیله‌ی نقلیه تا مانع تخمین زده می‌شود و موقعیت دقیق مانع به دست آمده و به پایگاه داده اضافه می‌شود و وسیله‌ی نقلیه از این پایگاه داده در فرایند هدایت استفاده می‌کند. در واقع سیستم هدایت با تحلیل موقعیت فعلی وسیله، جهت فعلی و جستجو در پایگاه داده، سرعت و جهت وسیله‌ نقلیه را کنترل می‌کند.سیستم کنترل پایداری وسیله نقلیه اطلاعات حاصل از فشار تایرها و معیارهای لرزش را از حسگرها جمع‌ آوری می‌کند و سرعت را تنظیم و وضعیت حرکتی را کنترل می‌کند [۸]. این برنامه کاربردی به خاطر قدرت پردازشی مورد نیاز توسط زیرسیستم‌های آن و هم‌چنین به دلیل محدودیت‌های مربوط به توان مصرفی بهتر است که از شبکه روی تراشه استفاده کند.
شکل ‏۵‑۱- مدل کاربرد وسیله­ نقلیه­ی خودمختار [۱۳]
جدول ۵-۱ وظایف تشکیل‌دهنده‌ی این برنامه کاربردی را به همراه عملکرد هر یک از آن‌ها نشان می‌دهد. با توجه به این جدول کاربرد مورد نظر دارای ۳۳ وظیفه می‌باشد.
جدول ۵-۲ نشان‌دهنده‌ی جریان‌های ترافیکی حاصل از ارتباطات بین این وظایف است. با توجه به این جدول برنامه­ی کاربردی مورد نظر دارای ۳۸ جریان ارتباطی بین وظایف می­باشد. همان­طورکه در فصل قبل گفته شد، هر جریان ارتباطی دارای شش مشخصه است که این جدول نشان­دهنده این شش ویژگی برای هر یک از آن­ها می­باشد. ستون Source و Destination در جدول بیانگر شماره مربوط به وظیفه­ی مبدا و وظیفه­ی مقصد ارتباط مورد نظر می­باشد. پارامتر vol مقدار داده­ای که در یک ارتباط منتقل می­ شود را نشان می­دهد که این مشخصه براساس تعداد فلیت­ها می­باشد که هر فلیت دارای ۳۲ بیت است. ستون مربوط به Period همان­گونه که از نام آن مشخص است بیانگر دوره­ هر ارتباط می­باشد و درواقع فاصله­ی زمانی بین آزاد شدن بسته­های متوالی ارتباط مورد نظر را نشان می­دهد. پارامترهای Deadline و Priority نیز به ترتیب بیانگر مهلت اتمام و اولویت جریان ارتباطی هستند.
جدول ‏۵‑۱- وظایف تشکیل دهنده کاربرد [۷۵]