مسيريابي چندپخشی کارا در شبکه‌هاي روی تراشه بازپیکربند
الموضوعات :فاطمه نصیری 1 , حمید سربازی آزاد 2 , احمد خادم‌زاده 3
1 - دانشگاه آزاد اسلامی واحد علوم و تحقیقات
2 - دانشگاه صنعتی شریف
3 - مرکز تحقیقات مخابرات ایران
الکلمات المفتاحية: شبکه روی تراشه شبکه بازپیکربند مسیریابی چندپخشی توان مصرفی تأخیر متوسط,
ملخص المقالة :
الگوریتم‌های مسیریابی متعددی برای ارتباطات تک‌پخشی و چندپخشی در سیستم‌های روی تراشه چندپردازنده‌ای ارائه شده است. پروتکل‌های چندپخشی برای شبکه‌های روی تراشه در سال‌های اخیر، در هماهنگ‌سازی ساعت، دسترسی‌های مکرر به حافظه‌های مشترک توزیع‌شده، هم‌زمانی و همسان‌سازی حافظه‌های نهان مورد استفاده قرار می‌گیرند. الگوریتم‌های مسیریابی تک‌پخشی برای هدایت بسته‌های چندپخشی مناسب نیستند چون احتمال بروز مشکلاتی از قبیل افزایش ترافیک، ازدحام و بن‌بست را در شبکه روی تراشه بالا می‌برند. از جمله راهکارهای برجسته برای ارتباطات چندپخشی در سیستم‌های چندکامپیوتری عبارتند از الگوریتم‌های مبتنی بر مسیر و الگوریتم‌های مبتنی بر درخت که در سال‌های اخیر این راهکارها به شبکه‌های روی تراشه نیز تعمیم داده شده‌اند. در این مقاله، طرح پیشنهادی با استفاده از شبکه بازپیکربند، سعی در کاهش توان مصرفی و تأخیر بسته‌های چندپخشی در طول مسیر دارد. به طور دقیق‌تر، چنین ساختاری با استفاده از سوییچ‌های ساده در همبندی بازپیکربند به جای مسیریاب‌ها و با بخش‌بندی شبکه به اندازه‌های کوچک‌تر، درخت‌هایی را برای هدایت بسته‌های چندپخشی می‌سازد که منجر به بهبود توان مصرفی و تأخیر ارسال پیام می‌شود. نتایج به دست آمده از شبیه‌سازی بر روی ترافیک‌های واقعی و ساختگی، نشان از برتری روش پیشنهادی ارائه‌شده در مقایسه با روش‌های قبلی مبتنی بر درخت با حداکثر کاهش 33% توان مصرفی و 51% تأخیر متوسط بسته‌ها دارد
[1] W. J. Dally and B. Towles, "Route packets, not wires: on-chip interconnection networks," in Proc. Design Automation Conf,. DAC’01, pp. 684-689, Las Vegas, NV, USA, 22-22 Jun. 2001.
[2] W. O. Cesario, et al., "Multiprocessor SoC platforms: a component-based design approach," IEEE Design & Test of Computers, vol. 19, no.6, pp. 52-63, Nov.-Dec. 2002.
[3] L. Benini and G. De Micheli, "Networks on chips: a new SoC paradigm," Computer, vol. 35, no. 1, pp. 70-78, Jan. 2002. [4] N. E. Jerger, L. S. Peh, and M. H. Lipasti, "Virtual circuit tree multicasting: a case for onchip hardware multicast support," in Proc. of the Int. Conf. on Computer Architecture, pp. 229-240, Beijing, China, 21-25 Jun. 2008.
[5] P. McKinely, H. Xu, A. H. Esfahanian, and L. Ni, "Unicast-based multicast communication in wormhole-routed networks," IEEE Trans. of Parallel and Distributed Systems, vol. 5, no. 12, pp. 1252-1265, Dec. 1994.
[6] E. A. Carara and F. G. Moraes, "Deadlock-free multicast routing algorithm for wormhole-switched mesh networks-on-chip," in Proc. Computer Society Annual Symp. on the VLSI, ISVLSI’08, pp. 341-346, Montpellier, France, 7-9 Apr. 2008.
[7] X. Lin and L. M. Ni, "Multicast communication in multicomputer networks," IEEE Trans. on Parallel and Distributed Systems, vol. 4, no. 10, pp. 1105-1117, Oct. 1993.
[8] F. Nasiri, H. Sarbazi-Azad, and A. Khademzadeh, "Reconfigurable multicast routing for networks on chip," Microprocessors and Microsystems, vol. 42, pp. 180-189, May 2016.
[9] M. Modarressi, A. Tavakkol, and H. Sarbazi-Azad, "Application-aware topology reconfiguration for on-chip networks," IEEE Trans. on Very Large-Scale Integrated Circuits and Systems, vol. 19, no. 11, pp. 2010-2022, Nov. 2011.
[10] M. Modarressi and H. Sarbazi-Azad, "Reconfigurable cluster-based networks-on-chip for application-specific MPSoCs," in Proc. IEEE 23rd Int. Conf. on Application-Specific Systems, Architectures, and Pricessors, ASAP’12, pp. 153-156, Delft, Netherlands, 9-11 Jul. 2012.
[11] Y. Choi and T. M. Pinkston, "Evaluation of crossbar architectures for deadlock recovery routers," J. of Parallel and Distributed Computing, vol. 61, no. 1, pp. 49-78, Jan. 2001.
[12] R. V. Boppana, S. Chalasani, and C. S. Raghavendra, "Resource deadlock and performance of wormhole multicast routing algorithms," IEEE Trans. on Parallel and Distributed Systems, vol. 9, no. 6, pp. 535-549, Jun. 1998.
[13] M. Ebrahimi, M. Danestalab, P. Liljeberg, and H. Tenhunen, "HAMUM-a novel routing protocol for unicast and multicast traffic in MPSocs," in Proc. 18th Euro Micro Conf. on Parallel, Distributed and Network Based Processing, PDP’10, pp. 525-532, Pisa, Italy, 17-19 Feb. 2010.
[14] P. Bahrebar and D. Stroobandt, "Improving hamiltonian-based routing methods for on-chip networks: a turn model approach," in Proc. 14th Conf. on Design, Automation & Test in Europe, DATE’14, 4 pp., Dresden, Germany, 24-28 Mar. 2014.
[15] M. R. Arun, P. A. Jisha, and J. Jose, "A novel energy efficient multicasting approach for mesh NoCs," Procedia Computer Science, vol. 93, pp. 283-291, 2016.
[16] M. R. Arun and P. A. Jisha, "SMDP-single message duplicate in partition, a multicast routing method in mesh 2D NoC," in Proc. 3rd Int. Conf. on Innovations in Information Embedded and Communication Systems, pp. 676-680, 2016.
[17] Z. Wang, et al., "An adaptive partition-based multicast routing scheme for mesh-based networks-on-chip," Computers & Electrical Engineering, vol. 51, pp. 235-251, Apr. 2016.
[18] Xmulator NoC Simulator, Available: www.xmulator.org, Apr. 2012.
[19] W. Hu, Z. Lu, A. Jantsch, and H. Liu, "Power-efficient tree based multicast support for networks-on-chip," in Proc. 16th Asia and Pacific Design Automation Conf., ASP-DAC’11, pp. 363-368, Yokohama, Japan, 25-28 Jan. 2011.
[20] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 2001.
[21] C. J. Glass and L. M. Ni, "The turn model for adaptive routing," in Proc. Int. Conf. Computer Architecture, ISCA’92, pp. 278-287, Gold Coast, Australia, 19-21 May 1992.
[22] S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta, "The SPLASH-2 programs: characterization and methodological considerations," in Proc. Int. Conf. Computer Architecture, ISCA’95, vol. 23, pp. 24-36, S. Margherita Ligure, Italy, 22-24 Jun. 1995.
[23] A. Nayebi, S. Meraji, A. Shamaei, and H. Sarbazi-Azad, "XMulator: a listener-based integrated simulation platform for interconnection networks," in Proc. Int. Conf. on Modelling and Simulation, AMS’07, pp. 128-132, Phuket, Thailand, 27-30 Mar. 2007.
[24] W. Hang-Sheng, Z. Xinping, P. Li-Shiuan, and S. Malik, "Orion: a power-performance simulator for interconnection networks," in Proc. 35th Annual IEEE/ACM Int. Symp. on Microarchitecture, MICRO’02, pp. 294-305, Istanbul, Turkey, 18-22 Nov. 2002.
[25] H. Kahng, B. Li, L. Peh, and K. Samadi, "ORION 2.0: a fast and accurate NoC power and area model for early-stage design space exploration," in Proc. 9th Conf. on Design, Automation & Test in Europe, DATE’09, pp. 423-428, Nice, France, 20-24 Apr. 2009.
