Abstract: In order to solve the problem of low output caused by the defects in VLSI manufacture, A redundant repair method is given. The problem of arrays reconfiguration is translated into the maximum independent set problem of contradiction graph. An ant colony optimization algorithm for redundancy VLSI array reconfiguration is proposed on the basis of contradiction graph of fault element. Experimental results show that compared with the standard genetic algorithm and Hopfield neural network algorithm, ant colony optimization algorithm of array reconfiguration for solving redundancy VLSI using single track switches is proved to be a simple and effective method.

Key words: maximum independent set, ant colony optimization algorithm, array reconfiguration

摘要： 通过冗余修复方法来解决超大规模集成电路(VLSI)制造过程中因缺陷而造成的成品率低的问题。根据物理阵列中缺陷单元的分布情况，构造相应的矛盾图模型，将阵列的重构问题转化为用蚁群优化算法求解矛盾图的最大独立集问题，使得所求独立集的顶点个数恰为缺陷单元的个数。实验表明，与标准遗传算法和神经网络算法相比，用蚁群优化算法来求解单通道冗余VLSI阵列重构问题是简单有效的。

关键词: 最大独立集, 蚁群优化算法, 阵列重构

CLC Number: 

• TP391.9