روش بهینهسازی کلونی مورچه یک روش احتمالاتی مبتنی بر جمعیت میباشد که از رفتار مورچهها در پیدا کردن مسیرها از کلونی به یک منبع غذا، الهام گرفته شده است. بنابراین وقتی یک مورچه یک مسیر خوب از کلونی به منبع غذا را پیدا می کند به علت بازخورد مثبت، بقیه مورچهها به احتمال زیاد آن مسیر را دنبال می کنند و در نهایت همه به یک مسیر هدایت میشوند. در [۵۳] الگوریتمی براساس روش کلونی مورچه، برای نگاشت وظایف کاربرد بر روی هستههای پردازشی شبکه بر تراشه جهت کمینهکردن پهنای باند مورد نیاز پیشنهاد شده است که نتایج با روشهای نگاشت تصادفی مقایسه شده است.
( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )
روشهای اکتشافی سازنده :
در روشهای اکتشافی سازنده، راه حلهای مجاز جزیی به ترتیب ایجاد میشوند تا اینکه راه حل نهایی نگاشت به دست آید. روشهای اکتشافی سازنده ممکن است همراه با تکرارهای بهبود دهنده یا بدون تکرارهای بهبود دهنده باشند. روشهای اکتشافی سازنده معمولا سریعتر از روشهای اکتشافی قابل تغییر هستند[۹].
روشهای اکتشافی سازنده بدون تکرارهای بهبود دهنده:
این الگوریتمها یک بار با انتخاب هستهها بر اساس معیارهای از پیش تعیین شده، هستههای یک گراف هسته را به همبندی NOC، نگاشت می کنند. موقعیت هستهها پس از مشخص شدن تغییر نمیکند و هیچ بهینهسازی در راهحل اولیه برای رسیدن به جواب بهتر انجام نمی شود[۹]. در [۵۴] وظایف کاربرد مورد نظر به خوشههایی تقسیم میشوند و هر خوشه شامل وظایفی است که باید روی یک پردازنده اجرا شوند و بنابراین برای افزایش موازیسازی هیچ سربار ارتباطی ندارند. در این جا یک الگوریتم دو مرحله ای نگاشت برای قرار دادن خوشه ها بر روی پردازندهها ارائه شده است به طوری که خوشههایی با بیشترین میزان ارتباطات در شبکه پردازندهها بر روی گرههای نزدیک به هم قرار میگیرند. در [۵۵] یک الگوریتمUMARS[115] ارائه شده است که نگاشت، تخصیص مسیر و تخصیص برشهای زمانی را برای کمینه کردن انرژی ارتباطی با هم انجام میدهد. این روش هستهها را روی همبندی NOC، نگاشت و ارتباطهای آنها را مسیریابی می کند و برشهای زمانی را به صورت TDMA[116] به طوری که محدویتهای کاربرد را برآورده کند، تخصیص میدهد. در [۵۶] روش SMAP، نگاشت کاربرد و مسیریابی وظایف را برای شبکه توری دو بعدی NOC جهت کاهش زمان اجرا و انرژی ارتباطی انجام میدهد. در این روش با توجه به شکل ۳-۴ وظیفه با بالاترین اولویت در مرکز نگاشت می شود و بقیه وظایف به صورت مارپیچ از وظایف نگاشت شده به سمت مرزهای شبکه نگاشت میشوند به طوری که هستههایی که بیشترین ارتباط را با هم دارند در نزدیکترین مکان ممکن نسبت به هم قرار گیرند. در [۵۷] یک الگوریتم بهینهسازی و نگاشت دوجملهای هستههای پردازشی، برای کاهش هزینه سختافزاری شبکه روی تراشه به نام BMAP ارائه شده است. این الگوریتم خیلی سریع و موثر است و پیچیدگی محاسباتی کمتری نسبت به NMAP [58] دارد. الگوریتم BMAP از سه مرحله تشکیل شده است: رتبه بندی هستههای پردازشی، ادغام مجموعه هستهها و دوبارهسازی مجموعه هستهها. رتبه بندی هستهها به پهنای باند ارتباطی بین آنها بستگی دارد. رتبه هر هسته برابر جمع پهنای باند ارتباطی از آن هسته به سایر هستهها و از سایر هستهها به این هسته میباشد. با توجه به شکل ۳-۵ وابسته به رتبه بندی هستهها، مجموعه هستههایی که بیشترین ارتباط را با هم دارند، در هر تکرار دو به دو با هم ادغام میشوند. نیازمندیهای جدید مجموعه هستههای ادغام شده، دوباره محاسبه و مجموعه هستهها دوباره ایجاد میشوند.
در [۵۹]، RMAP یک روش نگاشت کاربرد قابلیت اطمینان آگاه[۱۱۷] برای شبکه بر تراشه توری دو بعدی میباشد که گراف کاربرد را به دو زیر گراف به گونه ای تقسیم می کند که ترافیک ارتباطی بین زیر گرافها کمینه و ترافیک داخل هر زیر گراف بیشینه گردد. یک زیر گراف به گرههای مثلث بالایی NOC و زیر گراف دیگر به گرههای مثلث پایینی NOC، نگاشت میشوند. این روش از توزیع غیر یکنواخت ترافیک روی کانالهای شبکه استفاده می کند تا بستهها را به طور موثر مسیریابی کند.
شکل ۳‑۴- نگاشت کاربرد روی NOC به صورت مارپیچ [۵۶]
در [۶۰] همه گرهها و ارتباط بین آنها به صورت درخت نشان داده میشوند. در این درخت راس با بیشترین حجم ارتباطی به عنوان ریشه انتخاب می شود. گرههایی که با ریشه در ارتباط هستند به عنوان فرزندان آن در نظر گرفته میشوند. هنگام نگاشت، گره ریشه در مرکز شبکه توری قرار میگیرد و پیمایش از مرکز به سمت بیرون معماری شبکه بر تراشه انجام میگیرد. روش دیگر به نام CastNet میباشد که یک روش مسیریابی و نگاشت کاربرد، انرژی-آگاه برای شبکه توری دو بعدی است که در [۶۱] معرفی شده است. قبل از نگاشت، بر اساس پهنای باند ارتباطی کلی و میانگین پهنای باند ارتباطی هر وظیفه، یک لیست اولویت برای وظایف ایجاد می شود. با توجه به این لیست، وظیفه اولیه انتخاب می شود. اگر برابری وجود داشت انتخاب وظیفه به طور تصادفی انجام می شود. وظیفه بعدی که برای نگاشت انتخاب می شود وظیفه ای است که بیشترین ارتباط را با وظیفه نگاشت شده دارد. اگر دوباره برابری وجود داشت وظیفه ای انتخاب میشودکه اولویت بالاتری دارد. در [۶۲] الگوریتم EAMS، برای نگاشت مناسب وظایف برنامه کاربردی بر روی هستههای پردازشی شبکه ارائه شده است. هدف اصلی کمینه کردن انرژی مصرفی کلی میباشد در حالی که وظایف مذکور نیز مهلت اتمامشان را رعایت کنند. در اینجا فرض شده است که معماری NOC شامل هستههای پردازشی ناهمگن است که این هستهها از نظر انرژی مصرفی و تاخیر متفاوتاند. این الگوریتم، وظایف را به دو دستهی وظایف بحرانی و غیر بحرانی تقسیم می کند. وظایفی که مهلت اتمام نزدیکتری دارند و امکان از دست رفتن زمانشان وجود دارد وظایف بحرانی و سایر وظایف را وظایف غیر بحرانی میگویند. بنابراین در این روش ابتدا وظایف بحرانی و سپس وظایف غیر بحرانی نگاشت میشوند.
شکل ۳‑۵- مثال ادغام دوجملهای (N=16) [57]
روشهای اکتشافی سازنده با تکرارهای بهبود دهنده:
در این روشها ابتدا با توجه به یک سری معیارها، هستههای گراف هسته یا وظایف گراف کاربرد به همبندی شبکه بر تراشه، نگاشت میشوند سپس برای پیدا کردن جوابهای بهتر، با بهره گرفتن از تکرار الگوریتم سعی می شود راهحل موجود بهبود یابد[۹].
در [۵۸]، روش NMAP، یک روش نگاشت سریع میباشد که ضمن رعایت محدودیتهای پهنای باند، میانگین تاخیر ارتباطی را کمینه می کند. از آنجایی که یک مسیر قطعی بین هستههای پردازشی موجب می شود پهنای باند زیادی روی پیوندها نیاز باشد بنابراین نیازمندیهای پهنای باند می تواند توسط تقسیم ترافیک بین هستهها از طریق چندین مسیر، به طور قابل توجهی کاهش یابد. این الگوریتم هم برای یک مسیریابی کمینه و هم برای یک مسیریابی تقسیم ترافیک[۱۱۸] پیشنهاد شده است. روش NMAP شامل سه مرحله میباشد : در مرحله مقداردهی اولیه، هستهای که بیشترین تقاضای ارتباطی را دارد، در همبندی شبکه روی تراشه به گرهای که بیشترین همسایه را دارد نگاشت می شود. سپس هستهای که بیشترین ارتباط را با هسته فعلی نگاشت شده دارد انتخاب می شود. در نتیجه هزینه ارتباطی (تعداد گام × پهنای باند) کمینه می شود. این فرایند تا زمانی که همه هستهها نگاشت شوند، ادامه پیدا می کند. در مرحله بعدی الگوریتم دایجسترا برای پیدا کردن کوتاهترین مسیر با درنظر گرفتن محدودیتهای پهنای باند اعمال می شود. در مرحله آخر، راهحل اولیه با به کار بردن مرحله دوم برای هر جفت هسته نگاشت شده به طور تکرارشونده بهبود مییابد.
همه روشهای پیشنهادی قبلی از مدل ارتباطی وزندار[۱۱۹] برای محاسبه حجم ارتباط هر کانال استفاده می کنند اما زمانهای ارتباطی در نظر گرفته نشده است. برای در نظر گرفتن هر دو معیار در [۶۳] یک مدل محاسبات و وابستگی ارتباطات[۱۲۰] پیشنهاد شده است. این مدل کاربردها را روی شبکه بر تراشه منظم با در نظر گرفتن محدودیتهای پهنای باند نگاشت و میانگین تاخیر ارتباطی را کمینه می کند. در [۶۴] یک روش نگاشت مبتنی بر الگوریتم تبرید شبیه‌سازی شده[۱۲۱] برای شبکه توری دو بعدی در NOC پیشنهاد شده است که ناحیه مصرفی و بیشینه پهنای باند را کمینه می کند. هم چنین یک الگوریتم مسیریابی موثر ارائه شده است که از بین مسیرهای جایگزین، براساس موقعیت شبکه و اشغال بودن صفها یک مسیر را انتخاب می کند. در [۶۵] از ترکیب روشهای مبتنی بر خوشهبندی با تبرید شبیه‌سازی شده، برای نگاشت کاربرد استفاده شده است. در این روش برای کاهش پیچیدگی، عمل نگاشت به جای آنکه بر اساس گره انجام شود بر اساس خوشه انجام می شود. روش خوشهبندی روشی است که گرهها را براساس فاصله فیزیکی بین آنها در همبندی شبکه به گروههایی تقسیم می کند. خوشهبندی از معماری شبکه و تقاضای ارتباطی کاربردها استفاده می کند. بنابراین در اینجا ابتدا یک نگاشت اولیهای مبتنی بر روش خوشهبندی انجام می شود و در نهایت برای به دست آوردن نگاشت بهتر از روش تبرید شبیه‌سازی شده استفاده می شود.
در [۶۶] روش Onyx، یک روش نگاشت کاربرد با محدودیتهای پهنای باند برای کمینهکردن هزینه های ارتباطی NOC میباشد. در این روش هسته با بیشترین پهنای باند ارتباطی در مرکز نگاشت می شود. سپس رتبهی بقیهی هستههای نگاشت نشده مطابق با حجم ارتباطیای که با هستههای نگاشت شده دارند، تنظیم می شود. هستههای نگاشت نشده مطابق با شکل ۳-۶، برای قرار گرفتن در نزدیکترین فاصله ممکن با هسته مربوطه، مسیر لوزی شکل را در نظر میگیرند تا اینکه مکان خالی مشخص شود. در [۶۷] ، نیز یک روش نگاشت برای کاهش هزینه ارتباطی کلی پیشنهاد شده است. در این روش قبل از نگاشت، لیستهای اولویت با توجه به درجه اتصالات گرهها و پهنای باند ارتباطی تهیه میشوند. با توجه به لیستهای اولویت، روش موجود همان طور که در شکل ۳-۷ نشان داده شده است در یک روش زیگزاکی از یک گوشه شبکه توری شروع به نگاشت وظایف می کند و در گوشه دیگر به پایان میرساند.
شکل ۳‑۶- مفهوم انتخاب مسیر لوزی شکل [۶۶]
شکل ۳‑۷- مسیر زیگزاک برای نگاشت هسته [۶۷]
در [۶۸] برای استفاده بهینه از منابع روی تراشه، یک الگوریتم دو مرحله ای نگاشت برای چندین کاربرد پیشنهاد شده است به طوری که میانگین فاصله ارتباطی برای مجموعه کاربردها کم شود که این امر موجب کاهش تاخیر شبکه و مصرف انرژی نیز می شود. الگوریتم شامل یک مرحله نگاشت کاربرد و یک مرحله نگاشت وظیفه میباشد. مرحله نگاشت کاربرد چندین کاربرد را نگاشت می کند. این کار با هدف بهینهکردن آرایش[۱۲۲] چندین کاربرد روی NOC و پیدا کردن ناحیهای با حداقل فاصله میانگین گرهها[۱۲۳] برای هر کاربرد، انجام می شود. سپس در مرحله نگاشت وظیفه، وظایف یک کاربرد را به طوری که فاصله ارتباطی کلی حداقل شود، نگاشت می کند. نگاشت وظایف هر کاربرد از یک مدل درخت بر مبنای نگاشت ذکر شده در [۶۰] استفاده می کند. در [۶۹] ، الگوریتم LMAP، یک الگوریتم نگاشت برای کاهش هزینه های ایستا و پویای شبکه توری مبتنی بر NOC میباشد. این الگوریتم سه مرحله دارد: در مرحله قسمتبندی از روش قسمتبندی Kernighan-Lin (K-L) برای مشخصکردن نزدیکی هستهها با بهره گرفتن از تحلیل پهنای باند آنها و نیازمندیهای ارتباطی، استفاده شده است. در واقع این روش قسمتبندی، قرارگیری هستههایی که به طور مکرر با هم در ارتباط هستند را در یک قسمت تضمین می کند. این قسمتبندی دو بخشی به طور معکوس اعمال می شود تا در بخش نهایی، نزدیکترین دو هسته باقی بمانند. مرحله دوم، نگاشت اولیه میباشد. در این مرحله قرارگیری هستههای یک کاربرد روی شبکه توری بر اساس نتایج نهایی قسمتبندی K-L انجام می شود. بعد از نگاشت اولیه، در مرحله سوم با بهره گرفتن از تکرارهای بهبود دهنده، توسط جابجایی هستهها در درون ناحیه، نگاشت نهایی به دست مییاید. بنابراین الگوریتم LMAP، محدودیتهای پهنای باند را برآورده و میانگین تاخیر ارتباطی را کمینه می کند.
یک الگوریتم زمانبندی انرژی-آگاه در [۷۰] ارائه شده است که با در نظر گرفتن محدودیتهای زمانی، به طور ایستا ارتباطات بین وظایف و محاسبات آنها بر روی معماری شبکه برتراشه ناهمگن را، زمانبندی می کند. به عبارتی این الگوریتم وظایف را به عناصر پردازشی مختلف تخصیص میدهد و سپس اجرای آنها را زمانبندی می کند. همچنین الگوریتم به طور همزمان تاخیرهای ارتباطی را در نظر میگیرد و ارتباطات را نیز زمانبندی می کند. برای مدل کردن انرژی علاوه بر انرژی تلف شده در مسیریابها و پیوندها برای انتقال اطلاعات از یک عنصر پردازشی به عنصری دیگر، انرژی تلف شده برای اجرای وظایف بر روی عناصر پردازشی نگاشت شده مربوطهشان، در نظر گرفته می شود و هدف کمینه کردن این انرژی کلی است. این الگوریتم سه مرحله دارد: ۱) مرحله تخصیص زمان سکون[۱۲۴] به هر وظیفه که اگر وظیفه ای بر روی عنصری که بیشترین تاثیر را بر روی انرژی مصرفی و کارایی دارد، نگاشت شده باشد، زمان سکون بیشتری به آن اختصاص داده می شود. ۲) زمانبندی بر اساس سطح. ۳) جستجو و اصلاح زمانهای اتمامی که از دست رفتهاند.
روشهای نگاشت پویا
برخلاف نگاشت ایستا که در آن همه راه حلهای نگاشت قبل از شروع اجرای کاربرد و در زمان طراحی مشخص میشوند، در نگاشت پویا، نگاشت هستههای پردازشی و تخصیص وظایف و مشخص کردن ترتیب آنها در طول اجرای کاربرد اعمال می شود و ممکن است مکان وظایف بر روی عناصر پردازشی شبکه بر تراشه با توجه به بار فعلی پردازندهها در طول زمان اجرای کاربرد تغییر کند. در نگاشت پویا، زمان مورد نیاز برای اجرای الگوریتم نگاشت و پیدا کردن یک راهحل مناسب مهم است چرا که همین زمان یک بالاسری[۱۲۵] برای زمان اجرای کلی کاربرد میباشد. در واقع باید یک تعادلی بین کیفیت جواب و زمان اجرای الگوریتم مورد استفاده برقرار شود[۱۱]. نگاشت پویا برای شبکه بر تراشههایی مناسب است که نیازمند تحمل خطا میباشند. این نوع نگاشت، سعی می کند تنگناهای عملکرد و کارایی را تشخیص دهد و حجم بار را بین هستههای عملیاتی توزیع کند[۷]. چون در این روش، نگاشت به بار فعلی پردازندهها بستگی دارد بنابراین راه حل مناسبی است اما سربار محاسباتی الگوریتم نگاشت ممکن است موجب افزایش تاخیر و مصرف انرژی کاربرد در زمان اجرا شود. همچنین پیادهسازی نگاشت پویا نسبت به حالت ایستا دشوارتر است و هیچ تضمینی وجود نداردکه یک نگاشت پویا راه حلهای کلی بهینه ایجاد کند[۱۱]. بنابراین در این پایاننامه از روش نگاشت ایستا استفاده شده است چرا که ماهیت غیرقطعی بودن روشهای پویا، برای برنامه های کاربردی بیدرنگ سخت که در این کار مورد استفاده قرار میگیرند، مناسب نیست. در ادامه اشاره مختصری به برخی از روشهای نگاشت پویا می شود.
در [۷۱] با توجه به شکل ۳-۸ یک روش سلسله مراتبی تکرار شونده، برای نگاشت یک کاربرد بر روی شبکه بر تراشه ناهمگن در زمان اجرا، ارائه شده است که کاربرد مورد نظر با مجموعه ای از جریانها یا وظایف ارتباطی مدل شده است. برای کاهش انرژی مصرفی، الگوریتم نگاشت سعی می کند هر وظیفه را در نزدیکترین وظیفه ای که با آن ارتباط دارد قرار دهد.
Step 1: assign processes to tile types
Step 2: assign (sets of) processes to tiles
Step 3: detailed routing of communication
Step 4: check global constrains (e.g. timing)
شکل ۳‑۸- روش نگاشت پویای سلسله مراتبی [۷۱]
در [۷۲] روشهای اکتشافی برای نگاشت پویای وظایف ارائه شده است که در مرحله نخست، برای وظایف یک نگاشت اولیهای مشخص می شود و سپس در مرحله بعد نگاشت پویا اعمال می شود. مرحله نگاشت پویا ممکن است از یکی از روشهای اولین آزاد[۱۲۶] ، نزدیکترین همسایه[۱۲۷]، بار کانال بیشینه کمینه[۱۲۸]، حداقل میانگین بار کانال[۱۲۹] و بار مسیر[۱۳۰] استفاده کند. در روش اولین آزاد، اولین گره آزاد که می تواند وظیفه درخواست شده را اجرا کند، انتخاب می شود. روش نگاشت نزدیکترین همسایه شبیه روش اولین آزاد است با این تفاوت که وظیفه درخواست شده در گره آزاد همسایهی گرهای که آن درخواست را داده، قرار میگیرد. روش MMC ، یک روش نگاشت اکتشافی ازدحام-آگاه میباشد که بیشینه بار پیوند را کاهش میدهد. روش MAC شبیه روش MMC میباشد که به منظور کاهش میانگین بار در پیوندهای شبکه، بار ارتباطی را روی شبکه بر تراشه توزیع می کند. روشهای MMC و MAC در هنگام نگاشت یک وظیفه جدید، همه پیوندهای شبکه بر تراشه را در نظر میگیرند. بنابراین روش نگاشت آنها زمانبر میباشد. روش بار مسیر(PL)، تنها پیوندهایی که توسط وظیفه مورد نظر برای نگاشت استفاده می شود، در نظر میگیرد و بنابراین بر این مشکل غلبه می کند. از میان روشهای استفاده شده در این مقاله، روش PL در مقایسه با سایر روشها بهترین راهحل را ایجاد می کند.
نتیجه‌گیری
در این فصل سعی شد خلاصهای از روشهای نگاشت کاربرد در شبکه روی تراشه ارائه گردد. این روشها به دو دستهی نگاشت ایستا و نگاشت پویا تقسیم میشوند. نگاشت ایستا شامل نگاشت دقیق و نگاشت مبتنی بر جستجو میباشد. در این ارتباط، اهم الگوریتمهای مبتنی بر جستجو عبارتند از: جستجوی قطعی مانند روش شاخه و حد، روشهای اکتشافی قابل تغییر مانند الگوریتم ژنتیک و روشهای اکتشافی سازنده با/بدون تکرارهای بهبود دهنده. در نگاشت ایستا بیشتر الگوریتمها اتلاف انرژی ارتباطی را تحت محدودیتهای پهنای باند کمینه میکنند. برخی از این الگوریتمها یک هدفه و برخی چندهدفه میباشند. همچنین تعدادی از روشهای ذکر شده برای دستیابی به نگاشت بهینهتر از الگوریتمهای مسیریابی استفاده می کنند. شیوه های نگاشت پویا سربار محاسباتی بالایی دارند که موجب افزایش تاخیر و مصرف انرژی کاربرد در زمان اجرا می شود. علاوه بر این پیادهسازی نگاشت پویا نسبت به حالت ایستا دشوارتر است و هیچ تضمینی وجود نداردکه یک نگاشت پویا راه حلهای کلی بهینه ایجاد کند.
فصل چهارم
فصل چهارم: روش پیشنهادی
مقدمه
یکی از چالشهای مهم در تحقیقات مربوط به شبکه روی تراشه، مسئله نگاشت وظایف یک برنامه کاربردی بر روی هستههای پردازشی متصل به مسیریابهای شبکه میباشد. همان گونه که قبلا اشاره شد، برنامه های کاربردی انواع مختلفی دارند که یکی از پرکاربردترین آنها، برنامه های کاربردی بیدرنگ با نیازمندیهای زمانی سخت میباشند که در این قبیل کاربردها، وظایف باید مهلت اتمامشان را رعایت کنند و از آن زمان تجاوز نکنند. به عبارتی این وظایف باید در تمامی موقعیتها، محاسبات و ارتباطاتشان به موقع انجام شود. در این فصل ابتدا به معرفی روش پیشنهادی بر مبنای الگوریتم تکاملی ژنتیک برای نگاشت وظایف یک برنامه کاربردی بیدرنگ سخت بر روی شبکه بر تراشه پرداخته می‌شود و ویژگی‌ها و اهداف این روش مورد بررسی قرار میگیرد. سپس اجزای روش پیشنهادی با جزئیات کامل و به طور دقیق‌تری بیان شده‌اند که شامل تحلیل‌های مربوط به زمانبندی، تحلیل‌های توان مصرفی، الگوریتم ژنتیک چندهدفه NSGA-II و زیر بخش‌های مختلف آن میباشد.
معرفی طرح کلی روش پیشنهادی
همان طور که در فصل‌های قبل توضیح داده شد، از زمان ظهور شبکه روی تراشه تاکنون تحقیقات قابل توجهی در زمینه نگاشت وظایف برنامه‌های کاربردی انجام شده است که معمولا اهداف نگاشت بهینه کردن کارایی و هزینه NOC بوده است. در شبکه روی تراشه برای ارزیابی کارایی از معیارهایی مانند توان مصرفی، زمان اجرای وظایف و تاخیر انتقال بستهها استفاده می‌شود. از این رو در بسیاری از کارهای انجام شده، با مشخص کردن رابطه‌ای بین نگاشت وظایف روی NOC و این معیارها سعی در بهینه کردن روشهای نگاشت شده است.
برنامه‌های کاربردی در سیستم‌های نهفته[۱۳۱] که دارای نیازمندیهای زمانی بیدرنگ سخت میباشند، ارتباطات زیادی بین مولفه‌های مختلف دارند و نیازمند کارایی و توان محاسباتی بالایی میباشند. بنابراین این دسته از کاربردها مناسبتر است که از معماری شبکه روی تراشه بهره ببرند[۴۷]. از آنجایی که تحقیقات کمی بر روی فراهم آورن ضمانت برای کاربردهای بیدرنگ بر روی این قبیل سیستم‌ها انجام شده است و اهمیت زیادی نیز دارد، در این پایاننامه به ارائه طرحی برای زمانبندی برنامه‌های کاربردی بیدرنگ با نیازمندیهای زمانی سخت می‌پردازیم. ارتباطات بیدرنگ بین این قبیل کاربردها، نیازمندیهای سختی دارد و صحت و درستی آن نه تنها به نتایج ارتباط بلکه به حد نهایی زمان اتمام بستگی دارد. برای یک بسته که در شبکه منتقل می شود این حد زمانی برابر تاخیر شبکه بسته است. زیرا یک بسته مانند بستههای کنترلی اگر خیلی دیر توسط مقصد دریافت شود درواقع بیاستفاده خواهد بود. از این رو، بدترین معیار زمانی قابل قبول که تعریف می شود مهلت اتمام یک بسته است[۱۱]. بنابراین این کاربردها دارای مجموعه ای از وظایف بیدرنگ میباشندکه این وظایف به صورت دورهای[۱۳۲] یا پراکنده[۱۳۳] آزاد میشوند و با فرستادن پیغامهایی با هم در ارتباط هستند. بنابراین یک کاربرد شامل مجموعه ای از وظایف بیدرنگ و ارتباطات بین آنها یا به عبارتی جریانهای ترافیکی میباشد. هر یک از این وظایف دارای یک مهلت اتمام هستند که بیانگر حداکثر زمان مورد نیاز برای پردازش وظیفه و تولید نتایج میباشد. همچنین هر جریان ترافیکی بین وظایف نیز دارای مهلت اتمام مشخص میباشد که بیانگر حداکثر زمان لازم برای تحویل بستههای داده متعلق به وظیفه مبدا، به هسته پردازشی که وظیفه مقصد بر روی آن مستقر شده است، میباشد. بنابراین برای رعایت این نیازمندیهای زمانی، تاخیر ارتباطی بین جریانهای ترافیکی باید محدود شود. به عبارتی بیشترین تاخیر شبکه برای هر بسته نباید از مهلت اتماماش تجاوز کند.
در اکثر شبکه روی تراشهها برای سرویسدادن به جریانهای ترافیکی که نیاز به استفاده همزمان از منابع شبکه از جمله پیوندها دارند، از روش تسهیم زمانی[۱۳۴] استفاده می شود. در این روش برای تضمین پهنای باند مورد نیاز هر جریان ترافیکی جهت استفاده از منابع، از قبل یک برش زمانی به آن اختصاص داده می شود[۱۱] اما در اینجا همانند [۴۸] از شبکه بر تراشه با کانالهای مجازی دارای اولویت استفاده می شود و بنابراین هر بسته یک اولویت دارد. در این حالت بستههای هر جریان ترافیکی با اولویت بالاتر، برای انتقال در سطح شبکه نسبت به بستههایی با اولویت پایینتر حق تقدم دارند. مزیت اصلی این روش نسبت به حالت TDM آن است که نیاز به ذخیره منابع از قبل نیست و بنابراین ترافیکهای با اولویت پایین اگر هیچ درخواستی از جریانهای ترافیکی اولویت بالاتر وجود نداشته باشد همیشه میتوانند از منابع NOC استفاده کنند[۱۱]. همچنین به خاطر همین در نظر گرفتن اولویتها، رقابت در شبکه قابل پیش بینی خواهد بود و با بهره گرفتن از روش تحلیلی قابلیت زمانبندی که در ادامه توضیح داده خواهد شد، میتوان بیشترین زمانی که یک جریان ترافیکی خاص قبل از انتقال در سطح شبکه باید تحمل کند، محاسبه کرد.
هستههای پردازشی شبکه روی تراشه شامل دو نوع میباشند: هستههای همگن و هستههای ناهمگن. در شبکه روی تراشه همگن، همه عناصر پردازشی یکسان هستند و بنابراین نرخ اجرای همه وظایف بر روی همه هستههای پردازشی یکسان است. در حالی که در شبکه روی تراشه ناهمگن، عناصر پردازشی متفاوتاند و با توجه به شکل ۴-۱ این عناصر میتوانند واحد پردازش مرکزی[۱۳۵] ، واحد پردازش سیگنال دیجیتال، پردازنده ویدئو، واحدهای حافظه و … باشند. بنابراین نرخ اجرای وظایف بستگی به پردازنده و وظیفه مورد نظر دارد. به طوری که همه وظایف ممکن است نتوانند بر روی همه پردازندهها اجرا شوند[۷۳].
در بسیاری از کارهای انجام شده، به مسئله نگاشت بر روی هستههای پردازشی همگن پرداخته شده است و سعی در ارائه راه حل کارآمد کرده اند. اما تقریبا در اکثر طرحهای پیشنهاد شده، ویژگی ناهمگن بودن هستهها علیرغم آنکه به واقعیت نزدیکتر است، نادیده گرفته شده است. بنابراین در روش پیشنهادی هدف، یافتن یک راهحل مناسب، برای نگاشت وظایف یک برنامه کاربردی بیدرنگ با نیازمندیهای زمانی سخت بر روی یک شبکه بر تراشه ناهمگن میباشد. از طرفی یکی از معیارهای مهم در ارزیابی کارایی شبکه بر تراشه، توان مصرفی میباشد که چون مسیریابها، پیوندها و سایر عناصر شبکه از مهمترین منابع مصرف توان محسوب میشوند بنابراین اتلاف توان به الگوهای ارتباطی مختلف بستگی دارد و این الگوهای ارتباطی در اثر نگاشتهای متفاوت ایجاد میشوند. این الگوهای ارتباطی همچنین بر روی تاخیر بسته تاثیر میگذارند زیرا در یک شبکه مبتنی بر بسته، تاخیر بسته به طور مستقیم وابسته به فاصله بین گرههای ارتباطی و رقابت با دیگر جریانهای ترافیکی است[۴۷]. بنابراین نگاشت مناسب نگاشتی است که این تاخیر برای هر جریان ترافیکی از مهلت اتمام آن تجاوز نکند.
شکل ۴‑۱- نمونه ای از شبکه روی تراشه ناهمگن [۷۴]
به دلیل آنکه مسئله نگاشت یک مسئله NP-hard است و یافتن جواب بهینه نیازمند امتحان تمام حالات ممکن است، از این رو، روش پیشنهادی مبتنی بر الگوریتم تکاملی ژنتیک چندهدفه است که از دو مدل تحلیلی به منظور توابع هدف استفاده شده است. یک مدل تحلیلی برای بررسی محدودیتهای زمانی وظایف و ارتباطات بین آنها بیان شده است که این مدل با محاسبه زمان پاسخ هر وظیفه و تاخیر انتقال بسته برای هرجریان ترافیکی بین وظایف، تعداد وظایف و جریانهای ترافیکی که از مهلت اتمام مورد نظرشان تجاوز کرده اند، مشخص می کند. همچنین یک مدل تحلیلی برای محاسبه اتلاف توان ارائه شده است. در روشهای انجام شده قبلی به دلیل آنکه شبکه بر تراشه مورد نظر آنها از نوع همگن بوده است تنها اتلاف توان ناشی از ارتباطات بین هستههای پردازشی و اتلاف توان در المانهای شبکه از جمله مسیریاب در نظر گرفته شده است اما درروش پیشنهادی به دلیل فرض ناهمگن بودن عناصر پردازشی، علاوه بر اتلاف توان ارتباطی، توان مصرفی برای اجرای هر یک از وظایف بر روی هستههای پردازشی نیز در نظر گرفته شده است. در ادامه این فصل بر روی این مدلهای تحلیلی توضیحات کاملتری داده خواهد شد.
به طور کلی این الگوریتم ژنتیک به دنبال نگاشت مناسب وظایف بر روی هستههای پردازشی NOC است به طوری که در همه زمانها در عین رعایت همه محدودیتهای زمانی وظایف و جریانهای ارتباطی، اتلاف توان نیز کمینه گردد. در این جا همان طور که گفته شد، چون هستههای پردازشی ناهمگن هستند و برخی از وظایف نمی توانند بر روی تعدادی از عناصر پردازشی شبکه بر تراشه اجرا شوند با بهره گرفتن از یک تابع بررسی میشودکه آیا همه وظایف بر روی هستههای پردازشی مجاز که امکان اجرا بر روی آنها را دارند، نگاشت شده اند یا نه. همچنین، در نگاشت وظایف، یک آزمایش میزان بهره‌وری هستههای پردازشی در نظر گرفته شده است. به عبارتی ارزیابی می شود که مجموع بدترین زمان اجرای همه وظایف نگاشت شده بر روی یک هسته پردازشی از ظرفیت هسته مورد نظر تجاوز نکند.
اجزای طرح پیشنهادی
از آنجا که در روش پیشنهادی از الگوریتم ژنتیک چندهدفه برای یافتن جوابهای بهینه استفاده شده است در این بخش الگوریتم ژنتیک چندهدفه NSGA-II و اجزای آن مطابق با مسئله مورد نظر به طور کامل معرفی می شود. همچنین اجزای مختلف راهکار پیشنهادی شامل مدل کاربرد، مدل معماری NOC، مدل تحلیلی مربوط به زمانبندی و مدل توان درادامه این بخش با جزئیات کامل ارائه‌شده‌اند.
مدل کاربرد
مدل کاربرد از تعدادی وظیفه که به صورت دورهای آزاد میشوند، تشکیل شده است. یعنی به عبارتی وظایف پس از یک بازه زمانی ثابت و مشخصی تکرار میشوند. همچنین این مدل شامل ارتباطات بین وظایف نیز میباشد که با فرستادن پیغامهایی با هم تبادل اطلاعات می کنند. به این ارتباطات جریانهای ترافیکی[۱۳۶] گفته می شود.
هر وظیفه با شش مشخصه نشان داده می شود که عبارتند از:
: بدترین زمان اجرای[۱۳۷] وظیفه میباشد که در این جا چون شبکه بر تراشه ناهمگن است بنابراین هر وظیفه روی هر هسته پردازشی، بدترین زمان اجرای مجزایی دارد. از این رو یک بردار به طول تعداد هستههای پردازشی است که هر عنصر این بردار بیانگر بدترین زمان اجرای وظیفه iام بر روی هستهی مربوطه میباشد. اگر یک وظیفه نتواند بر روی هستهای اجرا شود، بدترین زمان اجرای آن بینهایت در نظر گرفته می شود.
: با فرض ناهمگن بودن شبکه بر تراشه، یک بردار به طول تعداد هستههای پردازشی است که هر عنصر این بردار بیانگر توان مصرفی ناشی از پردازش و اجرای وظیفه iام بر روی هستهی مربوطه میباشد. اگر یک وظیفه نتواند بر روی هستهای اجرا شود، همانند بدترین زمان اجرای آن، اتلاف توان مربوط به آن هسته نیز بینهایت در نظر گرفته می شود.
: مهلت اتمام وظیفه میباشد که بیانگر حداکثر زمانی است که یک وظیفه فرصت دارد اجرایش تمام شود و نتایج را تولید کند.
: این معیار معرف دوره یک وظیفه میباشد. در واقع بیانگر فاصله زمانی بین وارد شدن نمونههای متوالی و دورهای وظیفه است که در این جا چون فرض شده است که وظایف به صورت دورهای آزاد میشوند ثابت است. در صورتی که وظایف به صورت پراکنده آزاد شوند این برابر با کمترین فاصله زمانی بین نمونههای متوالی میباشد.
: این معیار اولویت هر وظیفه را نشان میدهد که در این جا هر وظیفه یک اولویت یکتا دارد.
: میزان تاخیر آزاد شدن[۱۳۸] وظیفه میباشد که به معنای بیشینه انحراف نمونههای متوالی وارد شده از دوره تناوبشان است. درواقع طبق [۱۲] فاصله بین ورود[۱۳۹] یک وظیفه و آزاد شدن آن را تاخیر آزاد شدن آن وظیفه میگویند.
