隨著VLSI製程技術上的進步，電子元件的體積逐漸縮小，單一晶片中可以放入更多的運算元件，這使得晶片上的資料傳輸量越來越龐大，因此過去常使用的傳輸方式已經無法負荷如此龐大的傳輸量。為了因應日漸複雜及龐大的傳輸需求，一種新的資料傳輸架構網路單晶片 (NoC) 被提出。任務對應(Application Mapping)是在設計上其中一個重要的議題，它將會直接的影響到晶片的能源消耗以及運算效率。此問題是屬於一種NP-hard問題，因此要如何在合理的時間內得到好的結果將是一個主要挑戰。
在本篇論文中我們提出了一個新的演算法SPMAP來解決在mesh topology上的任務對應問題，目的為降低能源消耗。此演算法會將原圖轉換為spanning tree之後計算每個core的degree以及在spanning tree中高度來決定擺放的順序，之後再將每個core放置於適當的位置。從比較結果可看出我們所提出的演算法在大多數的常見影音服務中可以找到與ILP相同的解，而在隨機benchmark的部分，當core的數量持續成長時，我們能用較短的時間獲得優於CastNet與NMAP的解。

Application mapping is an important part of Network-on-Chip (NoC) design, it tries to map the application onto a NoC-based platform. Because mapping an application onto the mesh architecture is NP-hard, there is no known algorithm for solving this problem in polynomial time. In this thesis, we propose a new application mapping algorithm for mapping an application onto the mesh topology Network-on-Chip architecture to minimize the energy consumption. We compare the proposed algorithm with some previously proposed algorithm and exact mapping technique. Our experiments on multimedia benchmarks show that the proposed mapping algorithm obtains the same solutions as the ILP generated solutions on most of case. On random benchmarks containing higher number of cores, we use less execution time to find better solution than CastNet and NMAP in large scale mesh-based NoC.

[1] Intel Teraflops Research Chip. http://www.intel.com/pressroom/kits/teraflops/.

[2] 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.

[3] 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.

[4] R. P. Dick, D. L. Rhodes, and W. Wolf, "TGFF: Task graphs for free." Proc. Int. Workshop Hardware/Software Codesign, pp.97 -101, 1998.

[5] M. R. Garey and D. S. Johnson, "Computers and intractability: A guide to the theory of NP-completeness." Freeman, 1979.

[6] C. J. Glass and L. M. Ni, “The turn model for adaptive routing,” ACM SIGARCH Computer Architecture News. Vol. 20. No. 2,pp. 278–287, 1992.

[7] A. Hemani, A. Jantsch, S. Kumar, A. Postula, J. Oberg, M. Millberg, and D. Lindqvist, "Network on a Chip: An architecture for billion transistor era", Proc. of the IEEE NorChip Conference, Nov. 2000.

[8] J. Hu, R. Marculescu, "Energy- and performance-aware mapping for regular NoC architectures." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 24, no. 4, pp. 551–562 , 2005.

[9] 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.

[10] 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 Euro PDP, pp. 406–413, 2000.

[11] K. S. M. Li, "CusNoC: Fast full-chip custom NoC generation," IEEE Transactions on VLSI systems, vol. 21, no. 4, pp. 692-705, Apr 2013.

[12] R. Marculescu, U.Y. Ogras, L.S. Peh, N.E. Jerger, Y. Hoskote, "Outstanding research problems in NoC design: systems, microarchitecture, and circuit perspectives." IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, vol. 28, no. 1, pp. 03–21, 2009.

[13] A. Morgan, H. Elmiligi, M. El-Kharashi, F. Gebali, "Unified multi-objective mapping and architecture customisation of networks-on-chip." IET Computers Digital Techniques, vol. 7, no. 6, pp. 282-293, 2013.

[14] 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.

[15] 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.

[16] T. Shen, C.H. Chao, Y.K. Lien, 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.

[17] P. K. Sahu and S. Chattopadhyay, "A survey on application mapping strategies for network-on-chip design." Journal of Systems Architecture, vol. 59, no. 1, pp. 60–76, 2013.

[18] P.K. Sahu, N. Shah, K. Manna, S. Chattopadhyay, "A new application mapping
algorithm for mesh based Network-on-Chip design." Annual IEEE India Conference (INDICON), pp. 1–4, 2010.

[19] P.K. Sahu, T. Shah, K. Manna, S. Chattopadhyay, "Application mapping onto mesh based Network-on-Chip using discrete particle swarm optimization," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 22, no. 2, pp. 300–312, 2014.

[20] P.K. Sahu, P. Venkatesh, S. Gollapalli, S. Chattopadhyay, "Application mapping
onto mesh structured Network-on-Chip using particle swarm optimization." IEEE Computer Society Annual Symposium on VLSI, pp. 335–336, 2011.

[21] 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.

[22] 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.

[23] S. Tosun, O. Ozturk, M. Ozen, "An ILP formulation for application mapping onto Network-on-Chips." International Conference on Application of Information and Communication Technologies (AICT), pp.1-5, 2009.

[24] S. Tosun, "New heuristic algorithm for energy aware application mapping and routing on mesh-based NoCs." Journal of System Architecture, vol. 57, no. 1, pp. 69-78, 2011.

[25] S. Tosun, "Clustered-based application mapping method for Network-on-Chip, "Advances in Engineering Software, vol. 42, no. 10,pp. 868–874, 2011.

[26] L. Zhou, M. Jing, Z. Yu, and X. Zeng, "Task-binding based branch-and-bound algorithm for NoC mapping." Circuits and Systems (ISCAS), 2012 IEEE International Symposium on. (ISCAS’12), pp. 648–651, 2012.