網路單晶片是一種系統晶片的架構，比起使用匯流排的架構更能處理龐大的資料跟傳輸量。任務對應在網路單晶片設計中是重要的一環，對應結果會對處理器之間的溝通成本造成影響。對應任務到網格結構上是一個被證明為NP-hard問題的constrained quadratic assignment problem例子。本論文提出一個對應任務到網格拓樸NoC結構上的多目標基因演算法，稱為Genetic Mapping Algorithm(GMA)。我們將task graph編碼為基因後，以對應於網格上的任務間的幾何關係作為交配運算子。從執行效率跟能量效率兩個層面去考量基因適應性，引用Pareto efficiency的概念挑選出滿足大多數情境需求的基因。最後我們實作演算法，用TGFF產生的隨機benchmark和多媒體影音服務做為測試資料。在將包含大量核心數的random task graph放置於大規模網格基底NoC的情況，GMA能找到比NMAP品質更好的解。

Mesh-based Network-on-chip (NoC) belongs to a certain System-on-Chip architecture, which can handle a huge amount of data and transmission compared to the architecture that uses bus-based architecture. In the design of NoC, task mapping is an important step, and the corresponding result will affect the communication cost between processors. It can be said that mapping a task to mesh architecture is a constrained quadratic assignment problem sample that is proven to be an NP-hard issue. This paper therefore proposes a multi-object genetic algorithm from mapping task to mesh topology NoC structure, which can be called Genetic Mapping Algorithm (GMA). After the author encodes the geometric relation of tasks into genes, the geometric relationship corresponding to the tasks on the mesh is used as the crossover operator. This study considers gene fitness from two aspects of execution efficiency and energy efficiency, and uses Pareto efficiency to select genes that meet the needs of most situations. Finally, the author implemented the algorithm, using the random benchmark generated by TGFF as well as multimedia audio-visual services as test data. Then, by placing a random task graph containing a large number of cores in a large-scale mesh-based NoC, GMA can find a better quality solution than NMAP.

[1] Intel Teraflops Research. http://www.intel.com/pressroom/kits/teraflops/
[2] H. Arabnejad and J. G. Barbosa, “List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table,” IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 3, pp. 682-694, Mar. 2014.
[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] C. Cheng, W. Chen, “Application mapping onto mesh-based network-on-chip using constructive heuristic algorithms,” The Journal of Supercomputing 72, pp.4365–4378, 2016.
[5] N. Choudhary, M. S. Gaur, V. Laxmi, V. Singh ,“Genetic algorithm based topology generation for application specific Network-on-Chip, ” Proceedings of 2010 IEEE International Symposium on Circuits and Systems, pp. 3156-3159, 2010.
[6] N. Chatterjee, S. Paul, P. Mukherjee, S. Chattopadhyay, “Deadline and energy aware dynamic task mapping and scheduling for Network-on-Chip based multi-core platform,” Journal of Systems Architecture vol. 74, pp. 61-77, Mar. 2017.
[7] R. P. Dick, D. L. Rhodes and W. Wolf, “TGFF: task graphs for free,” Proceedings of the Sixth International Workshop on Hardware/Software Codesign. (CODES/CASHE'98), Seattle, WA, USA, 1998, pp. 97-101.
[8] M. R. Garey, D. S. Johnson, “COMPUTERS AND INTRACTABILITY A Guide to the Theory of NP-Completeness,” Computers and intractability. vol. 174, Jan. 1979.
[9] P. Guerrier, A. Greiner, “A generic architecture for on-chip packet switched interconnections,” DATE 2000, pp. 250-256, Mar. 2000.
[10] M. R. Garey and D. S. Johnson, “Computers and intractability: A guide to the theory of NP-completeness,” Freeman, 1979
[11] 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.
[12] 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,” Proceedings of the IEEE NorChip Conference, vol. 31. no. 20. Nov.2000.
[13] 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.
[14] 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 IEEE Computer Society Annual Symposium on VLSI. New Paradigms for VLSI Systems Design. ISVLSI 2002, pp. 117-124, 2002.
[15] H. J. Kim, S. Kang, “Communication-aware task scheduling and voltage selection for total energy minimization in a multiprocessor system using Ant Colony Optimization,” Information Sciences, vol. 181, pp. 3995-4008, Sep. 2011.
[16] 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.
[17] G. Leary, K. Srinivasan, K. Mehta, K. S. Chatha, “Design of Network-on-Chip Architectures With a Genetic Algorithm-Based Technique,” in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 17, no. 5, pp. 674-687, May 2009.
[18] D. Li, J. Wu, “Energy-efficient contention-aware application mapping and scheduling on NoC-based MPSoCs,” Journal Parallel and Distributed Computing, vol. 96, pp.1-11, Oct. 2016.
[19] T. Maqsood, K. Bilal, & S. A. Madani, “Congestion-aware core mapping for network-on-chip based systems using betweenness centrality,” Future Generation Computer Systems, 82, pp. 459-471,May 2018.
[20] P. Mesidis ,L. S. Indrusiak, “Genetic mapping of hard real-time applications onto NoC-based MPSoCs — A first approach,” 6th International Workshop on Reconfigurable Communication-Centric Systems-on-Chip (ReCoSoC), pp. 1-6, 2011.
[21] 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.
[22] E. Rijpkema, K. Goossens, A. Rădulescu, J. Dielissen, J. van Meerbergen, P. Wielage, E. Waterlander, “Trade-offs in the design of a router with both guaranteed and best-effort services for networks on chip”, DATE 2003, pp. 350-355, Mar. 2003.
[23] A. Racu, L. S. Indrusiak, “Using genetic algorithms to map hard real-time on NoC-based systems,” 7th International Workshop on Reconfigurable and Communication-Centric Systems-on-Chip (ReCoSoC), York, pp. 1-8, 2012.
[24] P. K. Sharma, S. Biswas, P. Mitra, “Energy efficient heuristic application mapping for 2-D mesh-based network-on-chip,” Microprocessors and Microsystems vol. 64, pp. 88-100, Feb. 2019.
[25] M. Shang, S. Sun, Q. Wang, “An efficient parallel scheduling algorithm of dependent task graphs,” Proceedings of the Fourth International Conference on Parallel and Distributed Computing, Applications and Technologies, pp. 595–598, 2003.
[26] S. Tosun, “New heuristic algorithm for energy aware application mapping and routing on mesh-bashed NoCs,” Journal of System Architecture, vol. 57, no. 1, pp.69-78, 2011.
[27] S. Venugopalan, O. Sinnen, “ILP Formulations for Optimal Task Scheduling with Communication Delays on Parallel Systems,” in IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 1, pp. 142-151, Jan. 2015.
[28] L. Zhou, M. Jing, L. Zhong, Z. Yu and X. Zeng, “Task-binding based branch-and-bound algorithm for NoC mapping,” 2012 IEEE International Symposium on Circuits and Systems (ISCAS), Seoul, pp. 648-651, 2012.