Abstract

This paper addresses the problem of application mapping onto Butterfly-Fat-Tree (BFT) based Network-on-Chip design. It proposes a new mapping technique based on discrete Particle Swarm Optimization (PSO) to map the cores of the core graph to the routers. The basic PSO has been augmented by running multiple PSO and deterministically generating a part of the initial population for PSO. The mapping results have been compared with well-known techniques reported in the literature for a number of benchmark applications. The reported strategy produces results superior to those obtained via existing approaches within a reasonable CPU time.

References

• L. Benini, G. De Micheli, "Networks on Chips: A New SoC Paradigm," IEEE Computer, vol. 35, no. 1, pp. 70-78, 2002.
• W. J. Dally, B. Towles, "Route Packets, Not Wires: On-Chip Interconnection Networks," Proceedings of the Design Automation Conference (DAC), pp. 684-689, 2001.
• S. Kumar, A. Jantsch, J. P. Soininen, M. Forsell, M. Millberg, J. Oberg, K. Tiensyrja, A. Hemani, "A Network on Chip Architecture and Design Methodology," Proceedings of ISVLSI, pp. 117-124, 2002.
• S. Kundu, S. Chattopadhyay, "Interfacing Cores and Routers in Network-on-Chip Using GALS," IEEE International Symposium on Integrated Circuits (ISIC), pp. 154-157, 2007.
• L. Benini, "Application Specific NoC Design," IEEE Design, Automation and Test in Europe Conference (DATE'06), vol. 1, pp. 1–5, 2006.
• H. Elmiligi, A. A. Morgan, M. W. El-Kharashi, F. Gebali, "A Topology-based Design Methodology for Networks-on-Chip Applications," In Proceedings of the second International Design and Test Workshop (IDT'07), pp. 61–65, 2007.
• P. P. Pande, C. Greca, M. Jones, A. Ivanov, R. Saleh, "Performance Evaluation and Design Trade-offs for MP-SOC Interconnect Architectures," IEEE Transactions on Computers, vol. 54, no. 8, pp. 1025–1040, 2005.
• A. O. Balkan, Q. Gang, U. Vishkin, "Mesh-of-Trees and Alternative Interconnection Network for Single-Chip Parallel Processing," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 17, pp. 1419-1432, 2009.
• K. Manna, S. Chattopadhaya, I. Sengupta, "An Efficient Routing Technique for Mesh-of-Tree-based NoC and its Performance Comparison," International Journal of High Performance Systems Architecture, vol. 4, no. 1, pp 25-37, 2012.
• S. Kundu, S. Chattopadhyay, "Design and Evaluation of Mesh-of-Tree based Network-on-Chip using Virtual Channel Router," Journal of Microprocessors and Microsystems, Elsevier, vol. 36, issue 6, pp. 471–488, 2012.
• N. Koziris, M. Romesis, P. Tsanakas, G. Papakonstantinou, "An Efficient Algorithm for the Physical Mapping of Clustered Task Graphs onto Multiprocessor Architectures," Proceedings of 8th EuroPDP, pp. 406-413, 2000.
• P. K. Sahu, S. Chattopadhyay, "A Survey on Application Mapping Strategies for Network-on-Chip Design," Journal of Systems Architecture, Elsevier, vol. 59, 2013, pp. 60-76.
• J. Hu, R. Marculescu,"Energy-Aware Mapping for Tile-based NOC Architectures Under Performance Constraints," ASP-DAC, pp. 233-239, 2003.
• S. Murali, G. De Micheli, "Bandwidth Constrained Mapping of Cores onto NoC Architectures," Proceedings of Design, Automation and Test in Europe Conference and Exhibition (DATE), vol. 2, pp. 896-901, 2004.
• K. Srinivasan, K. S. Chatha, A Technique for Low Energy Mapping and Routing in Network-on-Chip Architecture, IEEE International Symposiun on Low Power Electronics and Design (ISLPED), pp. 387-392, 2005.
• T. Shen, C. H. Chao, Y. K. Lien, and A. Y. Wu, "A New Binomial Mapping and Optimization Algorithm for Reduced-Complexity Mesh- based on-Chip Network," Proceedings of NOCS'07, pp. 317-322, 2007.
• R. Mehran, S. Saeidi, A. Khademzadeh, A. A. Kusha, "Spiral: A Heuristic Mapping Algorithm for Network on Chip," IEICE Electronics Express, vol. 4, no. 15, pp. 478-484, 2007.
• M. Janidarmian, A. Khademzadeh, M. Tavanpour, "Onyx: A New Heuristic Bandwidth-Constrained Mapping of Cores onto Network on Chip," IEICE Electronics Express, vol. 6, no. 1, pp. 1-7, 2009.
• M. Tavanpour , A. Khademzadeh, M. Janidarmian, "Chain-Mapping for Mesh based Network-on-Chip Architecture," IEICE Electronics Express, vol. 6, no. 22, pp. 1535-1541, 2009.
• Y. Chen, L. Xie, J. Li, "An Energy-Aware Heuristic Constructive Mapping Algorithm for Network on Chip," International Conference on ASIC (ASICON), pp. 101-104, 2009.
• M. Reshadi, A. Khademzadeh, A. Reza, "Elixir: A New Bandwidth-Constrained Mapping for Networks-on-Chip," IEICE Electronics Express, vol. 7, no. 2, pp. 73-79, 2010.
• S. Tosun, "New Heuristic Algorithm for Energy Aware Application Mapping and Routing on Mesh-based NoCs," Journal of System Architecture, Elsevier, 57, pp. 69-78, 2011.
• P. K. Sahu, K. Manna, T. Shah, and S. Chattopadyay, "Extending Kernighan–Lin partitioning heuristic for application mapping onto Network-on-Chip," Journal of System Architecture, Elsevier, vol. 60, pp. 562-578, 2014.
• P. K. Sahu, N. Shah, K. Manna, S. Chattopadhyay, "A New Application Mapping Algorithm for Mesh based Network-on-Chip Design," IEEE International Conference (INDICON), pp. 1-4, 2010.
• P. K. Sahu, K. Manna, T. Shah, and S. Chattopadyay, "Thermal Uniformity-Aware Application Mapping for Network-on-Chip Design," International Journal of Computer Applications, vol. 99 (2), pp. 8-22, 2014.
• T. Lei, S. Kumar, "A Two-step Genetic Algorithm for Mapping Task Graphs to a Network on Chip Architecture," Proceedings of the Euromicro Symposium on Digital System Design (DSD), pp. 180-187, 2003.
• K. Bhardwaj, R. K. Jena, "Energy and Bandwidth Aware Mapping of IPs onto Regular NoC Architectures Using Multi-objective Genetic Algorithms," International Symposium on System-on-Chip (SOC), pp. 27-31,2009.
• F. M. Darbari, A. Khademzadeh, G. G. Fard, "CGMAP: A New Approach to Network-on-Chip Mapping Problem," IEICE Electronics Express, vol. 6, no. 1, pp. 27-34, 2009.
• G. Fen, W. Ning, "Genetic Algorithm based Mapping and Routing Approach for Network on Chip Architectures," Chinese Journal of Electronics, vol. 19, no. 1, pp. 91-96, 2010.
• M. Tavanpour, A. Khademzadeh, S. Pourkiani, M. Yaghobi, "GBMAP: An Evolutionary Approach to Mapping Cores onto a Mesh-based NoC Architecture," Journal of Communication and Computer, vol. 7, no. 3, pp. 1-7, 2010.
• W. Zhou, Y. Zhang, Z. Mao, "Link-load Balance Aware Mapping and Routing for NoC, WSEAS Transactions on Circuits and Systems," vol. 6, issue 11. pp. 583-591, 2007.
• W. Lei, L. Xiang, "Energy- and Latency-Aware NoC mapping Based on Discrete Particle Swarm Optimization," Proceedings of IEEE Internationa Conference on Communications and Mobile Computing, pp. 263-268, 2010.
• A. H. Benyamina, P. Boulet, A. Aroul, S. eltar, K. Dellal, "Mapping Real Time Applications on NoC Architecture with Hybrid Multi-objective Algorithm," International Conference on Metaheuristics and Nature Inspired Computing, pp. 1-10, 2010.
• P. K. Sahu, P. Venkatesh, S. Gollapalli, S. Chattopadhyay, "Application Mapping onto Mesh Structured Network-on-Chip using Particle Swarm Optimization," IEEE International symposium on VLSI (ISVLSI), pp. 335-336, 2011.
• P. K. Sahu, T. Shah, K. Manna, and S. Chattopadhyay, "Application Mapping onto Mesh based Network-on-Chip using Discrete Particle Swarm Optimization," IEEE Transactions on VLSI Systems (T-VLSI), vol. 2, issue 22, pp. 300-312, 2014.
• J. Wang, Y. Li, S. Chai, Q. Peng, "Bandwidth-Aware Application Mapping for NoC-Based MPSoCs," Journal of Computational Information Systems, 7:1, pp. 152-159, 2011.
• P. K. Sahu, N. Shah, K. Manna, S. Chattopadhyay, "An Application Mapping Technique for Butterfly-Fat-Tree Network-on-Chip," IEEE International Conference on Emerging Applications and Information Technology (EAIT), pp. 383-386, 2011.
• P. K. Sahu, N. Shah, K. Manna, S. Chattopadhyay, "A New Application Mapping Strategy for Mesh-of-Tree based Network-on-Chip," IEEE International Conference on Emerging Trends in Electrical and Computer Technology (ICETECT), pp. 518-523, 2011.
• P. K. Sahu, A. Sharma, S. Chattopadhyay, "Application Mapping onto Mesh-of-Tree based Network-on-Chip using Discrete Particle Swarm Optimization," IEEE International Symposium on Electronic System Design (ISED), pp. 172-176, 2012.
• P. P. Pande, C. Grecu, A. Ivanov, R. Saleh, "High-Throughput Switch-based Interconnect for future SoCs," IEEE International Workshop on System-on-Chip for Real Time Applications, pp. 304–310, 2003.
• I. Kennedy, R. C. Eberhart, "Particle Swarm Optimization," Proceedings of IEEE International Conference on Neural Networks, NJ. pp. 1942-1948, 1995.
• K. Wang, L. Huang, C. Zhou, W. Pang, "Particle Swarm Optimization for Traveling Salesman Problem," Proceedings of the Second International Conference on Machine Learning and Cybermetics, pp. 1583-1585, 2003.
• Yuhui Shi, Russell Eberhart, "Parameter Selection in Particle Swarm Optimization," Springer Berlin/ Heidelberg, vol. 1447/1998, pp. 591-600, 2006.
• L. Guilan, Z. Hai, S. Chunhe, "Convergence Analysis of a Dynamic Discrete PSO Algorithm," International Conference on Intelligent Networks and Intelligent Systems (ICINIS), pp. 89-92, 2008.
• A. B. Röhler, S. Chen, "An Analysis of Sub-swarms in Multi-swarm Systems," Proceedings of Joint Australasian Conference in Artificial Intelligence, Springer-Verlag, pp. 271–280, 2011.
• S. Chen, J. Montgomery "Selection Strategies for Initial Positions and Initial Velocities in Multi–optima Particle Swarms," Proceedings of the Genetic and Evolutionary Computation Conference, pp. 53–60,2011.
• B. Kernighan, S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell System Technical Journal, vol. 49, no. 2, pp. 291–307, 1970.
• G. V. Varatkar, R. Marculescu, "On-Chip Traffic Modelling and Synthesis for MPEG-2 Video applications," IEEE Trasactions on Very Large Scale Integration (VLSI) Systems, vol. 12, issue. 1, pp. 108-119, 2004.
• K. C. Chang, T. F. Chen, Low-power Algorithm for Automatic Topology Generation for Application-specific Networks on Chips, IET Computers & Digital Techniques, vol. 2, no. 3, pp. 239-249, 2008.
• B. S. Feero, P. P. Pande, "Networks-on-chip in a three-dimensional environment: A performance evaluation," IEEE Transactions on Computers, vol. 58, no. 1, pp. 32-45, 2009.
• "HSPICE Reference Guide", Version U-2003. 09, September 2003, Synopsys Inc.
• "Design Vision User Guide", Version U-2003. 03, March 2003, Synopsys Inc.
• "Synopsys Prime Power Mannual", Version Y-2006. 06, June 2006, Synopsys Inc.
• C. A. Nicopoulor, D. Park, J. Kim, N. Vijaykrishnan, M. S. Yousif, C. R. Das, "ViChaR: A Dynamic Virtual Channel Regulator for Network-on-Chip Routers," IEEE/ACM Symposium on Micro architecture, pp. 333-346, 2006.
• S. Pasricha, N. Dutta, "On-chip Communication Architectures: System on Chip Interconnect," Morgan Kaufmann Publishers, Chapter: 5, Page: 176, Table 5. 7: 2008.
• S. Traboulsi, N. Pohl, J. Hausner, A. Bilgic, V. Frascola, "Power Analysis and Optimization of the ZUC Stream Cipher for LTE-Advanced Mobile Terminals," IEEE Latin American Symposium on Circuits and Systems, pp. 1-4, 2012.
• R. P. Dick, D. L. Rhodes, W. Wolf, "TGFF: Task Graphs For Free," Proceedings of International Workshop on Hardware/Software Codesign, 1998.