بخشی از مقاله
چکیده - شبکه بر روي تراشه، مجموعهاي از تکنیکها و ابزارهائی در زمینه طراحی شبکه و بهکارگیري آنها است که دنبالهاي از ایده سیستم بر روي تراشه میباشد. کارایی NoC علاوه بر انتخاب نوع و ابعاد توپولوژي به طور گستردهاي وابسته به روش سوئیچینگ و تکنیک مسیریابی بهکار رفته در آن میباشد. در ارتباطات تکپخشی، پیغام از یک پردازنده مبدأ به مقصد ارسال میشود. در ارتباطات همهپخشی، پیغام از یک پردازنده مبدأ به کلیه پردازندههاي مقصد ارسال میشود و در ارتباطات چندپخشی، پیغام از یک پردازنده مبدأ به تعدادي از پردازنده هاي مقصد ارسال میشود.
با این تعاریف ارتباطات تکپخشی و همهپخشی حالتهاي خاصی از ارتباطات چندپخشی میباشند. ارتباطات چندپخشی به طور وسیعی در سیستم بر روي تراشه چندپردازندهاي بکار میروند در این مقاله انواع روش هاي مسیریابی براي شبکه هاي بر روي تراشه از نوع چند پخشی ارایه می گردد که علاوه بر نحوه عملکرد ، ویژگی و خصوصیت همراه با مزایا و معایب، هریک از الگوریتم ها در شرایط مختلف ترافیکی شبکه باهم مقایسه می گردند.
-1 مقدمه
الگوریتمهاي مسیریابی روشهایی را جهت ارتباط بین پردازندهها برقرار میکنند. این ارتباطات میتوانند به صورت تکپخشی1، همهپخشی2 و چندپخشی3 باشند.[1] در ارتباطات تکپخشی، پیغام از یک پردازنده مبدأ - واحد حافظه، IP و غیره - به یک پردازنده مقصد ارسال میشود. در ارتباطات همهپخشی، پیغام از یک پردازنده مبدأ به کلیه پردازندههاي مقصد ارسال میشود و در ارتباطات چندپخشی، پیغام از یک پردازنده مبدأ به تعدادي از پردازندههاي مقصد ارسال میشود. با این تعاریف ارتباطات تکپخشی و همهپخشی حالتهاي خاصی از ارتباطات چندپخشی میباشند. ارتباطات چندپخشی به طور وسیعی در سیستم بر روي تراشه چندپردازندهاي بکار میروند و از جمله کاربردهاي مسیریابی چندپخشی در پردازش هاي موازي4 ، هماهنگ سازي پالس ساعت5 ، تکرار6 و حافظههاي نهان میباشند.
-2 الگوریتمهاي مسیریابی چندپخشی
در صفحه بندي مقاله براي تمام صفحه ها، حاشیه متن از بالا الگوریتم هاي مسیریابی چند پخشی به سه روش کلی قابل پیادهسازي میباشند: بر پایه تکپخشی7، بر پایه درخت8 و بر پایه مسیر.9 ارتباطات چندپخشی با روش "بر پایه تک پخشی" با ارسال مجزاي پیغام از مبدأ به کلیه مقصدها صورت می پذیرد. در روش "بر پایه درخت" یک درخت پویش تشکیل می شود که ریشه همان گره مبدأ است و پیغام از طریق شاخه هاي این درخت به کلیه مقصدها می رسد و در روش "بر پایه مسیر" گره مبدأ، آدرس گره هاي مقصد را به ترتیبی در سرآیند پیغام قرار می دهد که اولین آدرس در سرآیند، اولین مقصدي است که در مسیر قرار دارد.
یکی از مسائل مهم در مسیریابی چندپخشی، بدون بن بست بودن الگوریتم هاي ارائه شده است که بسیاري از محققان به آن پرداختهاند. در تعدادي از تحقیقات به منظور جلوگیري از بنبست از کانالهاي مجازي استفاده میشود که اغلب الگوریتم هاي مسیریابی چند پخشی بر پایه درخت از این دسته میباشند. در برخی دیگر از الگوریتمها همانند مسیریابی چند پخشی با استفاده از مسیر هامیلتون10، بدون استفاده از کانالهاي مجازي از بروز بنبست جلوگیري میشود.
1-2 مسیریابی چندپخشی بر پایه تکپخشی
در این روش پیغام ها فقط به صورت تک پخشی به کلیه مقصدها فرستاده میشوند و براي حمایت از مسیریابی چندپخشی، پیغام یکسان به صورت مجزا به کلیه مقصدها ارسال می شود. بدیهی است که با این روش، بن بست جدیدي بوجود نمی آید. از معایب این روش تزریق چندین کپی از یک پیغام مشابه به شبکه است که باعث افزایش ترافیک در شبکه می شود و از آنجا که کپی هاي پیغام باید یکی پس از دیگري وارد شبکه شوند، تاخیر شروع11 در گره مبدأ افزایش می یابد. این روش زمانی مفید است که تعداد متوسط مقصدهاي یک پیغام کم باشد و پیاده سازي سخت افزاري چند پخشی ها مقرون بصرفه نباشد. شکل 1 مثالی از مسیریابی چندپخشی بر پایه تک پخشی در توري دو بعدي 6*6 را نشان می دهد که الگوریتم مسیریابی تکپخشی از نوع XY میباشد.
2-2 مسیریابی چندپخشی بر پایه درخت
در مسیریابی چند پخشی بر پایه درخت، یک درخت پویش تشکیل می شود که ریشه آن همان گره مبدأ است و پیغام به شاخه هاي این درخت فرستاده می شود.[10] ممکن است پیغام در گره هاي میانی تکرار شده و به شاخه هاي پایین تر آن ارسال گردد. در این روش، تقسیم بندي گره هاي مقصد در مبدأ صورت می پذیرد و کپی هاي مجزا به یک یا چند کانال خروجی فرستاده می شود. همچنین پیغام می تواند در گره هاي میانی کپی شده و به کانال هاي خروجی فرستاده شود تا سرانجام پیغام به کلیه گره هاي مقصد برسد. گره مقصد میتواند هم برگ و هم گره میانی باشد. بنابراین همه گره ها باید قادر به کپی نمودن پیغام و ارسال آن به کانالهاي خروجی باشند. عمل کپی کردن می تواند توسط نرم افزار انجام شود ولی اگر این کپی کردن سخت افزاري صورت پذیرد داراي پیچیدگی زیادي می شود هرچند که براي شبکه هاي با سوئیچینگ wormhole مناسب است.
3-2 مسیریابی چندپخشی بر پایه مسیر
براي پشتیبانی از مسیریابی wormhole در همه پخشی و چندپخشی که فارغ از بن بست می باشند، الگوهاي ارتباطی بر پایه درخت غیر از مواردي که پیغام ها خیلی کوتاه باشند، مفید نخواهد بود چراکه با مسدود شدن شاخه اي از درخت، کل درخت مسدود می شود. یک راه حل مناسب براي غلبه بر این مشکل ممنوعیت از شاخه شدن گره هاي میانی است که این راه حل منجر به ارائه الگوهاي چندپخشی بر پایه مسیر می شود.
