ترجمه فارسی مقاله الگوریتم های مسیریابی مبتنی بر کلونی مورچه آگاه از ازدحام برای اجرای کارآمد در پلتفرم شبکه روی تراشه
Congestion-aware ant colony based routing algorithms for efficient application execution on Network-on-Chip platform
Nadia Nedjah a,⇑,1, Luneque Silva Junior a,1, Luiza de Macedo Mourelle
واژه‌های کلیدی
شبکه بر روی تراشه ، مسیریابی بسته ، بهینه سازی کلونی مورچه
سال انتشار مقاله: Expert Systems with Applications 40 (2013) 6661–6673
مقاله ژورنالی
چکیده
شبکه برروی تراشه (NOC) یک گزینه جالب در طراحی زیر ساخت های ارتباطی برای سیستم های نهفته می باشد. یک ساختار مقیاس پذیر و ارتباطات متعادل بین هسته ها را بوجود می آورد. برنامه های موازی از معماری (NOC) بهره می برند، که معمولا ارتباطات متمرکز می باشد. بنابراین، حجم زیادی از بسته های داده به طور همزمان از طریق شبکه منتقل می شود. برای پیشگیری از تاخیرهای ازدحام که زمان اجرای برنامه های کاربردی را خراب می کند ، باید به دقت به یک استراتژی کارآمد مسیریابی فکرکرد. در این مقاله، از پارادایم (نمونه) بهینه سازی کلونی مورچه برای پیداکردن مسیرهای بهینه در یک شبکه روی تراشه (NOC) مبتنی بر مش استفاده می شود. الگوریتم های مسیریابی پیشنهادی ساده اما کارآمد می باشند. بهینه سازی مسیریابی با حداقل کردن کل تاخیر در زمان انتقال بسته ها بین وظایف تشکیل دهنده برنامه کاربردی صورت می گیرد. ارزیابی عملکرد فعلی سه جنبه دارد: اول، تاثیر الگوهای ترافیک ترکیبی شناخته شده مورد ارزیابی قرار می گیرد. دوم، برنامه های کاربردی تولید شده تصادفی توسط زیر ساخت (NOC) ترکیبی نگاشته می شوند و برخی از ترافیک های ارتباطی که الگوهای شناخته شده را دنبال می کنند برای شبیه سازی شرایط واقعی به کار گرفته می شوند. سوم، شانزده برنامه کاربردی دنیای واقعی از E3S و یک برنامه کاربردی ویژه برای پردازش تصویر دیجیتال نگاشته شده و زمان اجرای مورد ارزیابی قرار گرفته است. در هر دو مورد، نتایج بدست آمده با آنچه به عنوان هدف کلی الگوریتم برای مسیریابی بدون بن بست مقایسه شده است. مقایسه کارآمدی و برتری مسیریابی الهام گرفته از کلونی مورچه را تایید می نماید.
abstract
Networks-on-Chip (NoC) is an interesting option in design of communication infrastructures for embedded systems. It provides a scalable structure and balanced communication between the cores. Parallel applications that take advantage of the NoC architectures, are usually are communication-intensive. Thus, a big deal of data packets is transmitted simultaneously through the network. In order to avoid congestion delays that deteriorate the execution time of the implemented applications, an efficient routing strategy must be thought of carefully. In this paper, the ant colony optimization paradigm is explored to find and optimize routes in a mesh-based NoC. The proposed routing algorithms are simple yet efficient. The routing optimization is driven by the minimization of total latency during packets transmission between the tasks that compose the application. The presented performance evaluation is threefold: first, the impact of well-known synthetic traffic patterns is assessed; second, randomly generated applications are mapped into the NoC infrastructure and some synthetic communication traffics, that follow known patterns, are used to simulate real situations; third, sixteen real-world applications of the E3S and one specific application for digital image processing are mapped and their execution time evaluated. In both cases, the obtained results are compared to those obtained with known general purpose algorithms for deadlock free routing. The comparison avers the effectiveness and superiority of the ant colony inspire routing.
journal homepage: www.elsevier.com/locate/eswa
مراجع
[1] Benini, L., & De Micheli, G. (2002). Networks on chips: A new SoC paradigm.Computer, 35(1), 70–78.
[2] Bonabeau, E., Dorigo, M., & Theraulaz, G. (1999). Swarm intelligence: From natural toartificial systems. USA: Oxford University Press.
[3]Chandra Mohan, B., & Baskaran, R. (2012). A survey: Ant colony optimization basedrecent research and implementation on several engineering domain. Expert Systems with Applications, 39(4), 4618–4627.
[4] Chiu, G. M. (2000). The odd–even turn model for adaptive routing. IEEE Transactions on Parallel and Distributed Systems, 11(7), 729–738.
[5] Da Silva, M. V. C., Nedjah, N., & Mourelle, L. M. (2009). Efficient mapping of an image processing application for a network-on-chip based implementation. International Journal of High Performance Systems Architecture, 2(1), 46–57.
[6] Da Silva, M. V. C., Nedjah, N., & Mourelle, L. M. (2009). Optimal ip assignment for efficient noc-based system implementation using NSGA-II and MicroGA. IJCIS, 2(2), 115–123. Dick, R. (2012). Embedded system synthesis benchmarks suites (E3S). <http://ziyang.eecs.umich.edu/dickrp/e3s/>. [Online; accessed 02-May-2012].
[7] Dick, R. P., Rhodes, D. L., & Wolf, W. (1998). TGFF: Task graphs for free. In Proceedings of the sixth international workshop on hardware/software codesign (pp. 97–101).IEEE Computer Society.
[8] Dorigo, M., Birattari, M., & Stutzle, T. (2006). Ant colony optimization. Computational Intelligence Magazine IEEE, 1(4), 28–39.
[9] Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53–66.
[10] Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 26(1), 29–41.
[11] Duato, J. (1993). A new theory of deadlock-free adaptive routing in wormhole networks. IEEE Transactions on Parallel and Distributed Systems, 4(12), 1320–1331.
[12] Duato, J., Yalamanchili, S., & Ni, L. M. (2003). Interconnection networks: An engineering approach. Morgan Kaufmann. Edwards, S., Lavagno, L., Lee, E. A., & Sangiovanni-Vincentelli, A. (1997). Design of
embedded systems: Formal models, validation, and synthesis. Proceedings of the IEEE, 85(3), 366–390.
[13] Esser, R., & Knecht, R. (1993). Intel paragon XP/S-architecture and software environment. In Anwendungen, Architekturen Trends, Seminar (pp. 121–141). Springer-Verlag.
[14] Gheysari, K., Khoei, A., & Mashoufi, B. (2011). High speed ant colony optimization cmos chip. Expert Systems with Applications, 38(4), 3632–3639.
[15] Glass, C. J., & Ni, L. M. (1992). The turn model for adaptive routing. SIGARCH Computer Architecture News (vol. 20, pp. 278–287). ACM.
[16] Goss, S., Aron, S., Deneubourg, J., & Pasteels, J. (1989). Self organized shortcuts in the argentine ant. Naturwissenschaften, 76, 579–581. 10.1007/ BF00462870.
[17] Intel, A. (1991). Touchstone DELTA system description. Supercomputer systems division. Beaverton, OR 97006: Intel Corporation.
[18] Jَz´wiak, L., Nedjah, N., & Figueroa, M. (2010). Modern development methods and tools for embedded reconfigurable systems: A survey. Integration the VLSIJournal, 43(1), 1–33.
[19] Marcon. C. A. M. (2005). Modelos para o Mapeamento de Aplicaçُes em Infraestruturas de Comunicaçمo Intrachip. Ph.D. thesis, Universidade Federal do Rio Grande do Sul.
[20] Moraes, F., Calazans, N., Mello, A., Moller, L., & Ost, L. (2004). HERMES: An infrastructure for low area overhead packet-switching networks on chip. Integration the VLSI Journal, 38(1), 69–93.
[21] Mourelle, L. M., Ferreira, R. E., & Nedjah, N. (2010). Migration selection of strategies for parallel genetic algorithms: Implementation on networks on chips. International Journal of Electronics, 97(10), 1227–1240.
[22] Nedjah, N., Da Silva, M. V. C., & Mourelle, L. M. (2011). Customized computer-aided application mapping on noc infrastructure using multi-objective optimization. Journal of Systems Architecture: The EUROMICRO Journal, 57(1), 79–94.
[23] Ni, L. M., & McKinley, P. K. (1993). A survey of wormhole routing techniques in direct networks. Computer, 26(2), 62–76.
[24] Seitz, C. L., Athas, W. C., Flaig, C. M., Martin, A. J., Seizovic, J., Steele, C. S., & Su, W. K. (1988). The architecture and programming of the ametek series 2010 multicomputer. Proceedings of the third conference on hypercube concurrent computers and applications: Architecture, software, computer systems, and general issues (Vol. 1, pp. 33–37). ACM.
[25] Seitz, C. L., Boden, N. J., Seizovic, J., & Su, W. K. (1993). The design of the Caltech Mosaic C multicomputer. Computer, 256, 80.
[26] Trappey, C. V., Trappey, A. J. C., Huang, C. J., & Ku, C. C. (2009). The design of a JADEbased autonomous workflow management system for collaborative SoC design. Expert Systems with Applications, 36(2), 2659–2669.
[27] Zeferino, C. A., & Susin, A. A. (2003). Socin: A parametric and scalable network-onchip. In Proceedings of the 16th symposium on integrated circuits and systems design, 2003. SBCC 2003 (pp. 169–174). IEEE.
آنچه تحویل داده می شود:
- فایل ورد Microsoft Word .docx ترجمه به فارسی
- فایل PDF مقاله اصلی به زبان انگلیسی
تعداد صفحات مقاله ترجمه شده (فارسی): 44 صفحه
تعداد صفحات مقاله اصلی انگلیسی: 13 صفحه
مناسب برای دانشجویان کارشناسی و ارشد کامپیوتر (مهندسی نرم افزار و معماری کامپیوتر) و دانشجویان IT بالاخص دانشجویان سخت افزار و معماری کامپیوتر در ارشد ضمناً دانشجویان برق و الکترونیک نیز چه در مقطع ارشد و چه در مقطع کارشناسی با چنین موضوعاتی سر و کار دارند
می توان به عنوان پروژه دروس کارشناسی ارشد یا کارشناسی این پروژه را تحویل داد، دروسی مانند شبکه کامپیوتری، محاسبات توزیع شده، شبکه های کامپیوتری پیشرفته، پردازش توزیع شده، معماری کامپیوتر پیشرفته و غیره
از پایین همین صفحه می توانید این پروژه را خریداری نمایید.
ترجمه فارسی مقاله الگوریتم های مسیریابی مبتنی بر کلونی مورچه آگاه از ازدحام برای اجرای کارآمد در پلتفرم شبکه روی تراشه
