臺灣博碩士論文加值系統

網路單晶片是為了應付未來極為複雜的系統單晶片的通訊需求所提出的一種新的設計方式。在這篇論文中，我們提出一個基於基因演算法的任務排程方法，把應用排程至一個異質性網路單晶片。這個任務排程方法試著去為每一個任務找到最適合的處理器，使得系統的資料處理率提升至最大。在基因演算法中，隨著任務數目的增加，排程所需的時間也會跟著增加，而且在資料處理率的表現也會變差。所以我們提出分割的基因演算法來改良這樣的狀況。實驗結果顯示，我們提出的演算法可以有效提升基因演算法的效能，而且排程時間上也有明顯的改良。

Network-on-Chip is a new design paradigm to meet the communication requirement of future billion-transistor System-on-Chip.　In this thesis,　we propose a genetic algorithm based task scheduling technique to schedule the applications to the heterogeneous Network-on-Chip architecture. The task scheduling process attempts to arrange the allocation of processor for each task such that the system throughput is maximized. In genetic algorithm, with the increasing of task number, the scheduling time will increase, and the performance in system throughput will become worse. So we propose a partition genetic algorithm to improve this kind of situation. The experimental results show that proposed algorithm not only upgrade the performance of genetic algorithm, but also shorten the scheduling time obviously.

Chapter 1 Introduction 1
1.1 Technology Trend 1
1.2 Concept of Network-on-Chip 2
1.3 Motivation 4
1.4 Thesis Organization 5
Chapter 2 Preliminary 6
2.1 Related Works 7
2.1.1 Design Methodology 7
2.1.2 Scheduling 8
2.2 Our Design Flow 12
2.3 Our NoC Platform 13
2.3.1 Task Graph 17
2.3.2 Performance Evaluation 19
2.4 Genetic Algorithms 19
Chapter 3 Task Scheduling 22
3.1 Assumption 23
3.2 Problem Formulation 25
3.3 GA-based Task Scheduling Flow 26
3.4 Initial Population 27
3.5 Selection 31
3.6 Crossover 32
3.6.1 Proposed Crossover Method 32
3.6.2 Partition 34
3.6.3 Conditional Crossover 37
3.6.4 Task Range 38
3.6.5 Two-Step Crossover 39
3.7 Mutation 40
3.8 Simulation and Insertion 41
3.9 Termination 42
Chapter 4 Experimental Results 43
4.1 Experimental Environment and Flow 44
4.2 Analysis 47
Chapter 5 Conclusions and future work 62
5.1 Conclusions 62
5.2 Future work 63

[1] R. Ho, K. Mai, and M. Horowitz, "The future of wires," IEEE, vol. 89, no. 4, pp. 490-504, April 2001.
[2] William J. Dally and J. Poulton, "Digital Systems Engineering," Cambridge University Press, 1998.
[3] Cesar Albenes Zeferino and Altamiro Amsdeu Susin, "SoCIN: A Parametric and Scalable Network-on-Chip," 16th Symposium on Integrated Circuits and Systems Design, pp. 169-174, Sep. 2003.
[4] Axel Jantsch, and Hannu Tenhunen, "Networks on Chip," Kluwer Academic Publishers, 2003.
[5] Adrijean Adriahantenaina, Herv�� Charlery, Alain Greiner, Laurent Mortiez and Cesar Albenes Zeferin, "SPIN: a scalable, packet switched, on-chip micro-network," Design, Automation and Test in Europe Conference and Exhibition, supplements 70-73, 2003.
[6] Luca Benini and Giovanni De Micheli, "Networks on Chips: a New SoC Paradigm," Computer, Volume 35, Issue 1, pp. 70-78, Jan. 2002.
[7] William J. Dally and Brian Towles, "Route Packets, Not Wires: On-Chip Interconnection Networks," Design Automation Conference, pp. 684-689, June 2001.
[8] Pierre Guerrier and Alain Greiner, "A Generic Architecture for On-Chip Packet-Switched Interconnections," Design, automation and test in Europe, pp. 250-256, 2000.
[9] Shashi Kumar, Axel Jantsch, Juha-Pekka Soininen, Martti Forsell, Mikaek Millberg, Johny �鉉erg, Kari Tiensyrj�� and Ahmed Hemani, "A Network on Chip Architecture and Design Methodology," IEEE Computer Society Annual Symposium on VLSI, pp. 105-112, April 2002.
[10] Daniel Wiklund and Dake Liu, "SoCBUS: Switched Network on Chip for Hard Real Time Embedded Systems," Parallel and Distributed Processing Symposium, April 2003.
[11] Doris Ching, Patrick Schaumont and Ingrid Verbauwhede, "Integrated modeling and Generation of a Reconfigurable Network-on-chip," 18th International Parallel and Distributed Processing Symposium, pp. 139-145, 2004.
[12] Davide Berozzi and Luca Benini, "Xpipes: A Network-on-Chip Architecture for Gigascale Systems-on-Chip," Circuit and Systems Magazine, Volume 4, Issue 2, pp. 18-31, 2004.
[13] Srinivasan Murali and Giovanni De Micheli, "Bandwidth-Constrained Mapping of Cores onto NOC Architectures," Design, Automation and Test in Europe Conference and Exhibition, volume. 2, pp. 896-901, Feb. 2004.
[14] Tang. Lei and Shashi Kumar, "A Two-Step Genetic Algorithm for Mapping Task Graphs to a Network on Chip Architecture," Euromicro Symposium on Digital System Design, pp. 180-187, Sep. 2003.
[15] Edwin S.H. Hou and Nirwan Ansari, "A Genetic Algorithm for Multiprocessor Scheduling," IEEE Transactions on Parallel and Distributed Systems, Volume 5, pp.113-120, 1994.
[16] Yi-Hsuan Lee and Cheng Chen, "A Modified Genetic Algorithm for Task Scheduling in Multiprocessor Systems," The Ninth Workshop on Compiler Techniques for High-performance Computing, 2003.
[17] Wan-Hsi Hsieh, "GA-Based Task Scheduling for Heterogeneous Network-on-Chip," National Chiao Tung University, Master Thesis, 2005.
[18] Liang-Yu Lin, Cheng-Yeh Wang, Pao-Jui Huang, Chih-Chieh Chou and Jing-Yang Jou, "Communication-driven Task Binding for Multiprocessor with Latency Insensitive Network-on-Chip," Asia and South Pacific Design Automation Conference, Jan. 2005.
[19] Jingcao Hu and Radu Marculescu, "Energy-Aware Mapping for Tile-based NoC Architectures Under Performance Constraints," Asia & South Pacific Design Automation Conference, pp. 233-239, Jan. 2003.
[20] Jingcao Hu and Radu Marculescu, "Energy- and Performance-Aware Mapping of Regular NoC Architectures," IEEE transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume 24, Issue 4, pp.551-562, April 2005.
[21] Kenjiro Taura and Andrew Chien, "A Heuristic Algorithm for Mapping Communicating Tasks on Heterogeneous Resources," 9th Heterogeneous Computing Workshop, pp. 102-115, May 2000.
[22] David E. Goldberg, "Genetic Algorithms in Search, Optimization & Machine Learning, " Addison-Wesley Publishers, 1989.
[23] Baxter, M. J., Tokhi, M. O. and Fleming, P. J. "An investigation of the heterogeneous mapping problem using genetic algorithms," CONTROL '96, UKACC.
[24] R.J.H. Hoes, "Predictable Dynamic Behavior in NoC-based Multiprocessor System-on-Chip," M.Sc. Thesis, TUE, Eindhoven, Dec. 2004.
[25] Robert P. Dick, David L. Rhodes, and Wayne Wolf, "TGFF: task graphs for free," 6th International Workshop on Hardware/Software Codesign, pp. 97-101, 1998.