In Multi-Core Technology epoch, Network on Chip (NoC) architectures has been acknowledged as a solution to solve the design challenges of System on Chips (SoCs). The communication issue is played major role in design of effective NoCs. In order to achieve better communication among the multiple cores in NoC, an efficient routing algorithm is required. To evaluate the performance of NoCs, the performance parameters like throughput, energy and path length are focused by applying different routing algorithms. In this paper, we have analyzed network partitioning based on routing path and implemented two different routing algorithms named as Path Based Shortest Path (PBSP) and All Pair Shortest Path (APSP) algorithms for multicast messaging. These algorithms are developed and evaluated using C/C++ and Network Simulator for 2D Mesh NoC respectively. And finally we compare and analyze these two algorithms in terms of throughput and energy

در عصر فناوری چند هسته ای، معماری های شبکه بر روی تراشه به عنوان راهکاری برای حل چالش های موجود در طراحی سیستم روی تراشه ها مورد قبول قرار گرفته است. مسئله ارتباطات نقشی اساسی در طراحی NoC های موثر بازی می کند. برای رسیدن به ارتباطات بهتر در میان چندین هسته در NoC ، نیازمند یک الگوریتم مسیریابی کارآمد هستیم. برای ارزیابی کارآیی NoC ها، پارامترهای کارآیی نظیر بازده، انرژی و طول مسیر با اعمال الگوریتم های مسیریابی متفاوت مورد توجه قرار می گیرند. در این مقاله ما مسئله پارتیشن بندی شبکه بر اساس مسیر مسیریابی را بررسی کرده و دو الگوریتم مسیریابی متفاوت به نامهای Path Based Shortest Path (PBSP) و All Pair Shortest Path (APSP)  را برای ارسال پیامها به چند مقصد (ارتباطات یک به چند) پیاده سازی نموده ایم. این الگوریتم ها برای NoC ی مش دوبعدی و به ترتیب توسط C/C++ و شبیه ساز Network Simulator ساخته و ارزیابی می شوند. نهایتا دو الگوریتم را از نظر توان مصرفی و انرژی مقایسه و بررسی می کنیم.

1-مقدمه

با  گسترش ابعاد تکنولوژی، تعداد سلولهای هسته که در یک سیستم بر تراشه (SoC) تجمع یافته اند نیز به شدت در حال افزایش است.  با افزایش پیاپی تعداد سلولهای هسته ارتباطات سنتی SoC گلوگاه ارتباطات موجود در تراشه شد. SoC ها همچنین با چالشهای دیگری مثل پیچیدگی سیستم های گروه بندی، تاثیر منفی گسترش ابعاد تکنولوژی بر ارتباطات سراسری، نیاز به ساخت طراحی ها و پلتفرم های چند منظوره و منعطف روبرو هستند. با تحقیق بر چالشهای طراحی SoC، شبکه بر تراشه (NoC) به عنوان راه حل این مشکلات شناخته شده است. NoC ، مفاهیم شبکه را به طراحی معماری SoC اعمال کرده و همزمان گلوگاه ارتباطی و سایر چالشهایی را که پیشتر در [1] و [2] به آنها اشاره شده است برطرف می نماید. اخیرا معماری های NoC در زمینه های توپولوژی شبکه، طراحی روتر و الگوریتم مسیریابی تحت بررسی هستند که بر مواردی همچون کارایی، هزینه، بازده و مصرف انرژی اثر می گذارد. علاوه بر این پارامترها، تعدادی از الگوریتم های مسیریابی برای یافتن کوتاهترین مسیر از گره مبدا به گره مقصد براساس تکنیک های مسیریابی از قبیل ارتباطات یک به یک یا یک به چند استفاده می شوند. همچنین بسیاری از محققین تکنیک های مسیریابی متفاوتی برای توپولوژی های NoC متنوع ایجاد نموده اند [3]. در این مقاله ما به معرفی دو الگوریتم متفاوت برای یافتن کوتاهترین مسیر از مبدا به مقصد می پردازیم، این الگوریتم ها به ترتیب Path Based Shortest Path (PBSP) و  All Pair Shortest Pathتغییریافته (Modified APSP)  نام دارند. این دو الگوریتم که بر NoC ی پارتیشن بندی شده پیاده سازی خواهند شد از مزایای پروتکل مسیریابیAd-hoc On-Demand Distance Vector بهره مند می شوند...