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

چکیده

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

کلمات کلیدی

شبکه بر روی تراشه،  الگوریتم مسیریابی،تطبیقی ، تاخیر، کارایی، مصرف انرژی.

 1- مقدمه

طبق قانون مور به طور کلی پیچیدگی سیستم ها تقریبا هر دو سال یکبار، دو برابر می شود، به عبارت دیگر پارامترهایی نظیر تعداد ترانزیستورها در یک تراشه، فرکانس کلاک، میزان حافظه وغیره هر دو سال، دو برابر می شود. همچنین قدرت پردازش پردازنده ها به صورت نمایی در حال افزایش است. اما رفته رفته با رسیدن به حد بالای انتقال اطلاعات، برای رسیدن به سرعت بیشتر به فکر استفاده از پردازنده های موازی افتاده ایم. لذا برای رسیدن به سرعت بیشتر به جای رسیدن به تکنولوژی بهتر، به استفاده از معماری بهتر می پردازند.

ایده طراحی سیستم بر روی تراشه از آنجا مطرح شد که با افزایش دانش فشرده سازی تا حد امکان بلوک های یک مدار را که روی یک برد مدار چاپی وجود داشت، در داخل یک تراشه مجتمع کنند. این معماری مزایایی از قبیل کاهش توان مصرفی، مقاومت بیشتر در برابر نویز محیطی، کوتاهتر شدن زمان طراحی و کوچکتر شدن حجم مدار و غیره را در بر داشت.[1,2].

اما امروزه با پیشرفت سریع صنعت نیمه هادی ها، شمار واحدهای قابل پیاده سازی در یک سیستم بر روی تراشه افزایش یافته است. این روند رو به رشد امکان انجام پردازش موازی را در یک تراشه فراهم کرده است. با توجه به عدم کارایی گذرگاه های میان ارتباطی مورد استفاده در سیستم بر روی تراشه ها، برای تعداد زیاد پردازنده ها، در اوایل دهه ی جاری موضوع شبکه بر روی تراشه یا NoC مطرح شد و مورد توجه محققین قرار گرفت.

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

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

در شکل1 معماری یک شبکه بر روی تراشه نشان داده شده است. همانطور که ملاحظه میشود، یک NoC به طور ساده از لینک ها و گره ها تشکیل شده و هر گره از یک عنصر پردازشی  و یک مسیریاب تشکیل شده است[3,4].

گراف تشکیل شده از اتصال گره ها در طراحی شبکه، همبندی شبکه را مشخص می کند. گره ها به هر صورت دلخواهی میتوانند متصل شوند که از این بین، مهمترین همبندی های موجود عبارتند از: توری دو بعدی، حلقه، توری مدور و غیره اشاره کرد. در بین این همبندی ها، همبندی توری با توجه به ساختار ساده و قابلیت پیاده سازی آسان آن، بیشتر مورد استفاده قرار گرفته است

در شبکه های NoC برای رسیدن از یک گره به گره دیگر، چندین مسیر مختلف وجود دارد. بنابراین باید الگوریتمی وجود داشته باشد تا به وسیله آن بتوان مسیر رسیدن به مقصد را بدست آورد که به آن الگوریتم مسیریابی گفته می شود. تقسیم بندی های مختلفی نیز روی آنها انجام شده است. معمولاٌ سه معیار: محل تصمیم گیری در مورد مسیر، چگونگی مشخص نمودن مسیر و میزان اهمیت طول مسیر برای تقسیم بندی این الگوریتم ها به کار برده می شود[5]. 

شکل (1): معماری یک شبکه بر روی تراشه [1]

براساس محل تصمیم گیری در مورد مسیر، الگوریتم های مسیریابی به دو دسته مسیریابی مبدا و مسیریابی توزیع شده تقسیم می شوند. در نوع اول، مسیر در مبدأ مشخص می شود و تمام اطلاعات مربوط به آن در بخش سرآیند بسته قرار داده می شود. در حالی که در الگوریتم های مسیریابی توزیع شده، در طول مسیر در مورد ادامه آن تصمیم گیری می شود. بنابراین در بخش سرآیند بسته کافی است آدرس مقصد قرار داده شود. در این روش در صورت بسته بودن مسیر امکان تعویض آن وجود دارد.

بر اساس چگونگی تعیین مسیر، الگوریتم های مسیریابی به دو دسته تطبیقی و قطعی تقسیم بندی می شوند. در الگوریتم های قطعی، تصمیم گیری فقط بر اساس آدرس مبدا و مقصد انجام می شود، بنابراین تمام بسته هایی که دارای آدرس مبدأ و مقصد یکسان هستند، از مسیر یکسانی عبور می کنند. اما در الگوریتم های تطبیقی، علاوه بر آدرس مبدأ و مقصد، ترافیک لحظه ای شبکه نیز در تعیین مسیر مؤثر است و اگر ترافیک مسیر زیاد باشد، امکان تغییر مسیر و استفاده از مسیرهای خلوت تر وجود دارد. بنابراین بسته هایی که دارای مبدأ و مقصد مشترکی هستند، ممکن است از مسیرهای متفاوتی با تأخیرهای متفاوت برای انتقال، استفاده کنند. در این دسته از الگوریتم ها امکان وقوع بن بست و سردرگمی هم وجود دارد[6].

بر اساس طول مسیر، الگوریتم های مسیریابی به دو دستة کمینه و غیر کمینه تقسیم میشوند. در نوع اول همیشه از کوتاهترین مسیرها استفاده می شود، ولی در الگوریتم های غیرکمینه، شرط استفاده از کوتاهترین مسیر الزامی نیست و می توان جهت کاهش تأخیر دریافت بسته ها از مسیرهای طولانی تر نیز استفاده کرد. در مسیریابی توزیع شده، در گره مبدا فقط آدرس مقصد مشخص می شود و در بخش سرآیند بسته قرار می گیرد. در حین حرکت بسته، در هر گره به صورت مجزا در مورد نحوه ادامه مسیر تصمیم گیری می شود.

در مسیر حرکت بسته اگر بافرهای گره  های بعدی که باید گیرنده بسته باشند، پر باشند، بسته نمی تواند به مسیر خود ادامه دهد و برای همیشه از حرکت باز می ایستد که به آن بن بست می گویند. به تعبیری بن بست در شبکه هنگامی رخ می دهد که تعدادی از منابع شبکه به صورت چرخشی در انتظار یکدیگر باشند[5].

اگر از الگوریتم مسیریابی غیر کمینه استفاده کنیم برای رسیدن از مبدا به مقصد، مسیرهای بیشتری نسبت به مسیریابی کمینه وجود دارد که می تواند موجب سردرگمی بسته شود، بدین معنی که بسته در اطراف گره مقصد در گردش است ولی به گره مقصد نمی رسد. این مشکل می تواند با توجه به شرایط شبکه از بین برود. اگر منابع لازم برای ارسال بسته به علت ترافیک شدید شبکه در خدمت بسته های دیگر باشد، بسته نمی تواند عبور کند و برای همیشه در یک نقطه می ایستد به این حالت می گویند قحطی زدگی [7].

3- کارهای گذشته

در سالهای گذشته محققین سعی بر ایجاد الگوریتم های مسیریابی با حداکثر کارایی برای شبکه بر روی تراشه داشته اند. در این بخش به معرفی این الگوریتم های مسیریابی می پردازیم.

3-1- الگوریتم مسیریابی XY

در مسیریابی قطعی ، مسیر بسته ها بین مبدا و مقصد به صورت قطعی است و تغییر نمی کند. در این روش مسیر مربوط به مسیریابی قبل از ارسال بسته ها به شبکه تعیین می گردد. بسیاری از شبکه ها با این مسیریابی سازگار هستند، زیرا پیاده سازی آن آسان و ارزان است. سوییچ ها در این مسیریابی به آسانی پیاده سازی می شوند. یک مثال از مسیریابی قطعی ، مسیریابی XY است. استراتژی مسیریابی XY می تواند در همبندی مش دوبعدی منظم به کار برده شود. موقعیت گره های مش و مولفه های شبکه به وسیله مختصات شان توضیح داده خواهد شد. مختصات X برای جهت افقی و مختصات Y برای جهت عمودی است. در انتخاب خروجی XY بسته ها ابتدا در بعد X پیش می روند یا مسیردهی می شوند و سپس در بعد Y مسیردهی می شوند[5].

3-2- الگوریتم مسیریابی West First

هدف از این الگوریتم این است که گره هایی که در سمت غرب مش قرار دارند اولویت بیشتری نسبت به بقیه دارند. در این الگوریتم هنگامی که مختصات X مبدا از مختصات X مقصد بزرگتر باشد، در این صورت بسته به همان روش XY مسیریابی می شوند و اگر مختصات X گره مبدا از مختصات X گره مقصد کوچکتر باشد در این صورت بسته ها به صورت توافقی در جهات شرق ، شمال یا جنوب هدایت می شود. زمان کل برای انتقال یک بسته در الگوریتم توافقی کاهش داده می شود، چرا که هنگامی که به یک حال بلوکه می رسیم و نمی توانیم به سمت آن گره حرکت کنیم، توافقی به یک مسیر دیگری حرکت می کنیم[5].

3-3- الگوریتم مسیریابی North Last

هدف از این الگوریتم این است که گره هایی که در سمت شمال مش قرار دارند اولویت کمتری نسبت به بقیه دارند. در این الگوریتم هنگامی که مختصات Y مبدا از مختصات Y مقصد بزرگتر باشد، در این صورت بسته به همان روش XY مسیریابی می شوند و اگر مختصات Y گره مبدا از مختصات Y گره مقصد کوچکتر باشد در این صورت بسته ها به صورت توافقی در جهات غرب ، جنوب یا شرق هدایت می شود[5].

3-4- الگوریتم مسیریابی Negative First

هدف این الگوریتم این است که گره هایی که در سمت جنوب و غرب مش قرار دارند اولویت بیشتری نسبت به بقیه گره ها دارند. در این الگوریتم بسته ها در جهت منفی شمال یا غرب حرکت می کنند. اگر مختصات X گره مبدا از مختصات X گره مقصد بزرگتر و مختصات Y گره مبدا از مختصات Y گره مقصد کوچکتر و یا برعکس  باشد، در این صورت بسته ها به صورت معین مسیریابی می شود این الگوریتم از بن بست و گرسنگی محفوظ است[6].

3-5- الگوریتم مسیریابی Odd Even

الگوریتم Odd-Even یکی دیگر از الگوریتم های تطبیقی می باشد که مبتنی بر مدل چرخشی عمل می نماید این الگوریتم در مقایسه با الگوریتم های مسیریابی تطبیقی دیگری که از کانال مجازی استفاده نمی کنند، دارای قابلیت تطبیق پذیری بیشتری بوده و سربار کمی دارد. 

این الگوریتم نیز همانند دیگر الگوریتم ها، برای اجتناب از بروز بن بست، یک سری محدودیت ها را در انجام چرخش ها اعمال می کند. در OE با ایجاد محدودیت در مکانهایی که بعضی چرخش ها می توانند اتفاق بیافتند از بروز انتظار چرخ های ممانعت به عمل می آید تا بدین ترتیب از بن بست اجتناب شود. بنابراین در این مدل هیچ یک از چرخشها حذف نمی شود. این باعث می شود که درجه تطبیق پذیر بودن این الگوریتم نسبت به الگوریتم های پیشین بسیار بیشتر باشد.

به طور کلی در OE دو قاعده اصلی وجود دارد:

• قاعده یک: در هر گره واقع شده در یک ستون زوج هیچ بسته ای مجاز نیست چرخش از شرق به شمال و چرخش از شرق به جنوب انجام دهد.

• قاعده دو: در هر گره واقع شده در یک ستون فرد هیچ بسته ای که چرخش از جنوب به غرب و چرخش از شمال به غرب انجام داشته باشد.

اثبات شده که هر الگوریتم مسیریابی که از قواعد OE استفاده نماید عاری از بن بست خواهد بود[7].

3-6- الگوریتم مسیریابی DyAD

ایده الگوریتم مسیریابی DyAD این است که در ترافیک پایین در مد قطعی کار کند تا تاخیر کمتری داشته باشد و هر گاه که ازدحام شبکه از یک حد معین بالاتر رفت، مسیریابی در مد وفقی انجام شود. بر طبق آخرین گزارشها الگوریتم وفقی Odd-Even نسبت به سایر الگوریتم های وفقی ارائه شده دارای کارایی بهتری می باشد. یکی دیگر از دلایل استفاده از این الگوریتم این است که تمامی الگوریتم های توسعه یافته بر اساس Odd-Even عاری از بن بست بوده و دارای درجه وفقیت بسیار بالاتری نسبت به دیگر الگوریتم ها می باشند. هنگامی که لازم باشد تا بسته را در مد قطعی مسیردهی کنیم، همان الگوریتم Odd-Even را می توان به گونه ای تغییر داد که بصورت قطعی عمل کند. این کار نیز با حذف خواص وفقی این الگوریتم به سادگی امکانپذیر می باشد. این الگوریتم قطعی را DyAD می نامیم. 

بدین دلیل در مد قطعی از این روش استفاده می شود که اولا مبتنی بر Odd-Even بوده و عاری از بن بست است، ثانیا بدلیل سازگاری با Odd-Even برای پیاده سازی مسیریاب آن دیگر نیازی به استفاده از تجهیزات اضافی وجود ندارد، زیرا این الگوریتم مبتنی بر همان قواعد Odd-Even می باشد و تمام تجهیزات لازم جهت پشتیبانی از آن قبلا برای Odd-Even استفاده شده است. بنابراین هم در زمان کم ازدحام بودن شبکه و هم در زمان ازدحام بالا کارآیی شبکه افزایش می یابد. چراکه این الگوریتم هم از مزایای الگوریتم های قطعی و هم از مزایای الگوریتم Odd-Even استفاده می کند که دارای درجه وفقیت مناسبی می باشد و برای پیاده سازی آن نیز، نیازی به سخت افزار اضافی نمی باشد[8].

4- معرفی الگوریتم مسیریابی تطبیقی جدید

در این قسمت، با الهام از الگوریتمهای معرفی شده در بخش 2 به معرفی یک الگوریتم تطبیقی جدید با نام الگوریتم مسیریابی مسیر تصادفی یا RPRA ، برای مسیریابی در NoC می پردازیم. اگر بتوانیم در الگوریتم مسیریابی XY به گونه ای عمل کنیم که در هنگام قرار گرفتن در یک گره تصمیم گیری برای انتخاب مسیر ارسال بسته بر پایه مقایسه دو پارامتر X یا Y باشد، آنگاه بطور موثری میزان تاخیر شبکه کاهش می یابد[11]. 

تصمیم گیری برای حرکت بر مبنای هر دو پارامتر X و Y در یک گره، تعداد تصمیم گیری های تا رسیدن به مقصد را کاهش داده و تاثیر مثبتی بر روی تاخیر شبکه دارد. به این معنا که به جای چهار حالت، تمام حالات ممکن بین دو گره در شبکه که شامل هشت حالت مختلف است، را مورد بررسی قرار دهیم. اساس کار الگوریتم مسیریابی تطبیقی در شکل 2 نشان داده شده است. 

این الگوریتم نیز همانند XY از نوع آزاد از بن بست است. روش کار این الگوریتم شبیه به الگوریتم مسیریابی  XY اما با کمی تفاوت می باشد. به عنوان مثال برای مسیریابی بسته اطلاعاتی در یک گره در صورتی که مختصات X مقصد بزرگتر از X گره فعلی باشد و همچنین مختصات Y گره مقصد کوچکتر از Y فعلی باشد، دو حالت امکان پذیر است 

• بسته  اطلاعاتی ابتدا به سمت بالا (شمال) و سپس به سمت راست (شرق) ارسال می گردد.

• بسته اطلاعاتی ابتدا به سمت راست (شرق) و سپس به سمت بالا (شمال) ارسال می شود.

انتخاب یکی از این دو حالت به صورت تصادفی خواهد. ای کار باعث خواهد شد تا ترافیک در سطح شبکه توزیع شود. لازم به ذکر است که در اینجا هر دو مقایسه در یک گره صورت می گیرد.

شکل (2): نحوه عملکرد الگوریتم مسیریابی تطبیقی جدید

5- نتایج شبیه سازی الگوریتم مسیریابی

در این قسمت به ارزیابی الگوریتم های معرفی شده در بخش های قبل می پردازیم.

5-1- معرفی محیط شبیه سازی

 این شبیه سازی ها در محیط نرم افزار  [13]Noxim انجام شده است. این شبیه ساز بر خلاف شبیه سازهای دیگر در زمینه شبکه به صورت اختصاصی برای کار بر روی NoC طراحی شده است. شبیه ساز فوق یک نرم افزار متن باز و تحت سیستم عامل لینوکس می باشد. یکی از امکانات این نرم افزار شبیه ساز، قابلیت تعریف و ایجاد الگوریتم های مسیریابی در متن برنامه است.

شبیه سازی در یک شبکه بر روی تراشه از نوع مش با اندازه 8×8 انجام شده است. هر عنصر پردازشی بسته هایی با اندازه 8 فلیت تولید و در شبکه تزریق می کند. اندازه بافر هر کانال مجازی برابر 4 می باشد استراتژی انتخاب مسیر از نوع [12]Neighbors-on-Path و تعداد دفعات اجرای شبیه سازی 40000 سیکل می باشد.

5-2- ارزیابی تحت ترافیک تصادفی 

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

نتایج حاصل از بررسی حداکثر میزان تاخیر در الگوریتم های مسیریابی مذکور، در شکل (3) قابل مشاهده است. در نمودار این شکل محور افقی نشان دهنده نرخ تولید بسته ها توسط عناصر پردازشی شبکه و محور عمودی، حداکثر میزان تاخیر می باشد. از مقایسه فوق این نکته برآورد می شود که میزان تاخیر برای الگوریتم مسیریابی تطبیقی جدید، کمتر از الگوریتم های قطعی و نیمه تطبیقی دیگر می باشد

شکل (3): مقابسه الگوریتم های مسیریابی از نظر تاخیر در مدل ترافیکی تصادفی

از پارامترهای دیگری که به بررسی آن پرداخته شد، کارایی شبکه می باشد، که نتایج حاصل در شکل (4) ذکر شده است. در نمودار این شکل محور افقی نشان دهنده نرخ تولید بسته ها توسط عناصر پردازشی شبکه و محور عمودی، میزان کارایی شبکه می باشد. این مقایسه به خوبی بیانگر این واقعیت است که  که میزان کارایی الگوریتم مسیریابی تطبیقی جدید به مراتب بهتر از الگوریتم های دیگر می باشد.

شکل (4): مقایسه الگوریتم های مسیریابی از نظر کارایی در مدل ترافیکی تصادفی

آخرین پارامتری که مورد بررسی قرار گرفته است میزان کل انرژی مصرف شده الگوریتم پیشنهادی با سایر الگوریتم ها می باشد. شکل (5) نمایانگر نتایج حاصل از این بررسی است. در نمودار این شکل محور افقی نشان دهنده نرخ تولید بسته ها توسط عناصر پردازشی شبکه و محور عمودی، میزان مصرف انرژی شبکه می باشد. همانطور که انتظار می رفت میزان کل انرژی در الگوریتم مسیریابی جدید کمتر از سایر الگوریتم ها می باشد.

شکل (5): مقایسه الگوریتم های مسیریابی از نظر توان در مدل ترافیکی تصادفی

6- نتیجه

یکی از مسائل مطرح در مورد شبکه های روی تراشه و یا به اختصار NoC، سرعت انتقال بسته های اطلاعاتی است. انتخاب الگوریتم مسیریابی مناسب از جمله عواملی است که تاثیر مستقیم در این امر دارد. 

همانطور که در بخش 4 مشاهد شد نتایج حاصل از پیاده سازی الگوریتم مسیریابی تطبیقی جدید به مراتب بهتر از نتایج حاصل از الگوریتم های مسیریابی قطعی و نیمه تطبیقی موجود می باشد. با دقت بر روی شکل های 3 تا 8 می توان به این مهم پی برد که انتخاب یک الگوریتم سریع و بهینه، تا چه اندازه می توناد در افزایش کارایی یک NoC موثر باشد.