在單晶片網路架構中，任意節點或線路的損壞，都可能造成資料傳輸的困難。這些錯誤和損壞將很難被預測及避免。於是，逐步發展中的深次微米技術則建議單晶片網路應具有內建式容錯修復之能力。為了確保單晶片網路能維持正常運作，我們提出預設式備份路徑修復之機制，並針對此問題提出一些有效的解決方法。
　　為了有更好的修復成果，我們先利用基因演算法(Genetic Algorithm，GA)－一種基於自然選擇過程的一種最佳化搜尋機制，來追求效能的最佳化。基因演算法已經被廣泛應用於解決複雜的最佳化問題。然而，傳統的基因演算法並非毫無缺點；收斂速度慢及不能保證一定可以收斂到最佳解為基因演算法二項主要缺點，現今已有許多改良式基因演算法來加強執行的效能。
　　考慮到基因演算法的諸多缺點，我們提出壓縮映射基因演算法（Contract Mapping Genetic Algorithm, CMGA）來搜尋最佳備用路徑。模擬的結果顯示，該演算法不但具有較強的廣域搜索能力，而且能有效地解決過早收斂的問題。另外，對於一般化的基因演算法以及啟發式搜尋演算法也有較好的搜尋能力表現。

　　Failure of nodes or links in Network-on-Chip (NoC) may cause difficulties in data transmission. And these failures are hard to predict and avoid with current design methodologies. The demands of evolving deep-submicron VLSI technology suggest that Networks-on-Chips be designed with built-in fault-tolerance. In order to ensure Networks-on-Chips survivability for maintaining the normal operation, our proposed method is to implement the preplanned backup path restoration scheme.
　　We have presented a new method based upon a GA to find the near optimal preplanned backup paths for the primary paths in NoC. In this thesis, GA has been employed for solving many complex optimization problems. Although GA is not perfect, i.e., the speed of convergence is slow and it cannot guarantee to converge to globally optimal solution, they are more efficient in attaining near-optimal solutions significantly than conventional point-by-point exhaustive search techniques, especially in large solution spaces.
　　Taking the drawbacks of SGA into account, we adopt another genetic algorithm -- Contract Mapping Genetic Algorithm (CMGA) is proposed. Not only this algorithm can converge to globally optimal solution, but also it solves premature convergence problem efficiently. Simulation results show that the algorithm CMGA presented in this thesis performs better contrast with simple genetic algorithm and heuristic search algorithm.

[1] The International Technology Roadmap for Semiconductors: Technology Needs
1998 Updates. Semiconductor Industry Association：Austin, Texas, 1998.
[2] Kumar, S.; Jantsch, A.; Soininen, J.-P.; Forsell, M.; Millberg, M.; Oberg,
J.; Tiensyrja, K.; Hemani, A., “A network on chip architecture and design
methodology,” VLSI, Proceedings of IEEE Computer Society Annual Symposium
on, pp.105-112, 25-26 April 2002.
[3] A. Laffely, Jian. Liang, P. Jain, N. Weng, W. Burleson and R. Tessier,
“Adaptive Systems-on-a-Chip (aSoC) for Low-Power Signal Processing,”
Proceedings of the Asilomar Conference on Signals, Systems and Computers,
Monterey, California, pp.1217-1221, Nov. 2001.
[4] J. Liang, S. Swaminathan and R. Tessier, “aSoC: A Scalable, Single-Chip
Communications Architecture,” Proceedings, {IEEE} International Conference
on Parallel Architectures and Compilation Techniques, Oct. 2000.
[5] Benini, L.; De Micheli, G., “Networks on chips: a new SoC paradigm,”
Computer, Vol.35, Issue.1, pp.70-78, Jan. 2002.
[6] Marculescu, R., “Networks-on-chip: the quest for on-chip fault-tolerant
communication,” VLSI, 2003. Proceedings. IEEE Computer Society Annual
Symposium on, pp.8-12, 20-21 Feb. 2003
[7] Dumitras, T.; Kerner, S.; Marculescu, R., “Towards on-chip fault-tolerant
communication,” Design Automation Conference, 2003. Proceedings of the
ASP-DAC 2003. Asia and South Pacific, pp.225 - 232, 21-24 Jan. 2003.
[8] Dumitras, T. and Marculescu, R., ”On-chip stochastic communication,”
Proceedings of the Design, Automation and Test in Europe Conference and
Exhibition (DATE’03), 2003.
[9] G. Mohan and A. K. Somani, “Routing Dependable Connections With Specified
Failure Restoration Guarantees in WDM Networks,” Proc. IEEE INFOCOM 2000,
Mar. 2000.
[10] G. Mohan, C. S. R. Murthy, “Routing and wavelength assignment for
establishing dependable connections in WDM networks,” Fault-Tolerant
Computing, 1999. Digest of Papers. Twenty-Ninth Annual International
Symposium on, pp.94 -101, 1999.
[11] G. Mohan, C. S. R. Murthy, “Lightpath restoration in DWDM optical
networks,” IEEE Network, Vol.14, pp.24-32, Nov-Dec. 2000.
[12] R. Kawamura, I. Tokizawa, “Self-Healing Virtual Path Architecture in ATM
Networks,” IEEE Communications Magazine, pp.72-79, Sep. 1995.
[13] J. Holland, “Adaptation in Natural and Artificial Systems,” Univ. of
Michigan Press (Ann Arbor), 1975.
[14] D. E. Goldberg, “Genetic algorithms in Search, Optimization and Machine
learning,” Reading. MA: Addison Wesley, 1989.
[15] M. Mitchell, “An introduction to genetic algorithms,” London, England,
1996.
[16] Z. Michalewicz, “Genetic Algorithm + Data Structure = Evolution
Programs,” Springer-Verlag, 1994.
[17] Agarwal, A., Moritz, C. A. and Yeung D., “Exploring Optimal
Cost-Performance Designs for Raw Microprocessors,” Proceedings of the
International IEEE Symposium on Field-Programmable Custom Computing
Machines, FCCM98, April 1998.
[18] Zhang, H., Wan, M., George, V. and Rabaey, J., “Interconnect Architecture
Exploration for Low-Energy Reconfigurable Single-Chip DSPs,” Proceedings of
the WVLSI, Orlando, FL, USA, April 1999.
[19] Pierre Guerrier and Alain Greiner, “A Generic Architecture for On-Chip
Packet-Switch Interconnections,” Design, Automation and Test in Europe
Conference and Exhibition 2000, Proceedings, pp.250-256, 27-30 March 2000.
[20] Jingcao Hu, Radu Marculescu, “Exploiting the Routing Flexibility for
Energy/Performance Aware Mapping of Regular NoC Architectures,” Proceedings
of the Design Automation & Test in Europe (DATE), March, 2003.
[21] Zeferino, C.A., Kreutz, M.E., Carro, L. and Susin, A.A., “A study on
communication issues for systems-on-chip,” Proceedings. 15th Symposium on
Integrated Circuits and Systems Design, pp.121-126, 9-14 Sept. 2002.
[22] Adriahantenaina, A., Charlery, H., Greiner, A., Mortiez, L. and Zeferino,
C.A., “SPIN: a scalable, packet switched, on-chip micro-network,” Design,
Automation and Test in Europe Conference and Exhibition, pp.70-73, 2003.
[23] Ping-Tsung Wang, Kun-Nen Chen and Yen-Tai Lai, “A High Performance FPGA
with Hierarchical Interconnection Structure,” Circuits and Systems, 1994
IEEE International Symposium on, Vol.4, pp.239-242, 30 May-2 June 1994.
[24] Lionel Ni und Philip McKinley, “A Survey of Wormhole Routing Techniques in
Direct Networks,” IEEE Computer, Vol.26, No.2, pp.62-76, Feb. 1993.
[25] W. J. Dally, “Virtual-Channel Flow Control,” IEEE Trans. Parallel and
Distributed Systems, Vol.3, No.2, pp.194-205, Mar. 1992.
[26] Karim, F., Nguyen, A., Dey, S. and Rao, R. “On-chip communication
architecture for OC-768 network processors,” Design Automation Conference,
2001. Proceedings, pp.678 – 683, 18-22 June 2001.
[27] Girish Varatkar and Radu Marculescu: “Traffic Analysis for On-chip Networks
Design of Multimedia Applications,” Annual ACM IEEE Design Automation
Conference archive Proceedings of the 39th conference on Design automation
table of contents New Orleans, Louisiana, USA, pp.795-800, June, 2002.
[28] Praveen Bhojwani, and Rabi Mahapatra, “Interfacing Cores with On-Chip
Packet-Switched Networks,” Proceedings of IEEE Computer Society 16th
International Conference on VLSI Design, pp.382 – 387, 4-8 January, 2003.
[29] M. Sgroi, M. Sheets, A. Mihal, K. Keutzer, S. Malik, J. Rabaey and A.
Sangiovanni-Vencentelli, “Addressing the system-on-a-chip interconnect woes
through communication-based design,” Proceedings of the 38th conference on
Design automation, Las Vegas, Nevada, United States, pp.667-672, June 2001.
[30] William J. Dally and Brian Towles, “Route packets, not wires: on-chip
interconnection networks,” Proceedings of the Design Automation Conference,
Las Vegas, NV, pp.684–689, June 2001.
[31] Yih-Fuh Wang and Jen-Fa Huang, “Preplanned Restoration and Optimal Capacity
Placement on ATM Multicast Tree,” IEICE Transaction on Communication,
Vol.E83-B, No.2, Feb. 2000, pp.281-292.
[32] Peter KK Loh and Venson Shaw, “A Genetic-Based Fault-Tolerant Routing
Strategy for Multiprocessor Networks,” Future Generation Computer Systems
archive vol. 17, Special issue on bio-impaired solutions to parallel
processing problems, pp.415-423, 2001.
[33] Masaharu Munetomo and Yoshiaki Takai and Yoshiharu Sato, “A Migration
Scheme for the Genetic Adaptive Routing Algorithm,” Proceedings of the 1998
IEEE Conference on Systems, Man, and Cybernetics, pp.2774-2779, 1998.
[34] K. Murakami and H. S. Kim, “Near-optimal virtual path routing for
survivable ATM networks,” INFOCOM '94. Networking for Global
Communications. 13th Proceedings IEEE, Vol.1, pp.208-215, Jun. 1994.
[35] A. Szalas and Z. Michalewicz, “Contract mapping genetic algorithm and their
convergence,” Dept. of computer science, University of North Carolina at
Charlotte, Technical Report 006-1993.
[36] Dunwei Gong and Xiaoyan Sun, “A modified contract mapping genetic
algorithm,” Proceedings of the 2002 IEEE International Symposium on, Vol.1,
pp.353-356, 8-11 July 2002.
[37] S. Banach, Sur les operations dans les ensembles abstraits et leur
applications aux equations integrals, Fundamenta Mathematica, Vol.3,
pp.133-181, 1922.