摘要: 多处理器阵列结构的大规模集成电路系统具有结构规整、易于实现的特点。它在嵌入式系统、高性能计算、以及信号及图像的并行处理等领域具有广泛的应用。随着 VLSI 技术的高度发展，多处理器阵列可以被集成到一个微小的芯片上。在产品处理阶段，由于集成密度的增大，处理器被损坏的可能性也随之增高。为了应对这一问题，容错技术不得不被引入，以提高系统的可靠性。 常用的容错技术有两类，它们是冗余方法和降阶方法。在冗余方法中，整个系统添加了一些空闲的处理器以作备用。 当空闲处理器及其相关连接被全部用尽后， 整个系统也就不得不废弃。 这是冗余方法的主要缺点。而对于降阶方法则不同，整个系统中的所有处理器被同等对待， 而没有空闲的处理器。这种方法尽可能多地使用无损坏的处理器来构造最大的处理器阵列。相关的文献指出了在给定的有损阵列上构造最大子阵列的问题是 NP 难解问题， 并给出了相应的启发式算法。 硬件的面积及其在速度上的有效性是 VLSI 设计中的主要问题之一。随着硬件技术的发展，处理器之间的内部连接对硬件面积、速度和电路的功耗产生了巨大的冲击。 人们提出了许多算法用来产生最优的电路布线，以便最小化功耗和速度上的延迟。近年来便携式个人计算器件和无线通讯系统的使用促使工程技术人员设计和生产高性能的系统。最优化降阶的处理器阵列的内部连接无疑增加了系统的各项性能。 本文对降阶的处理器阵列的内部连接进行优化， 其主要贡献为：1）首次提出了可重构阵列上内部连接的优化问题，并使用单元最短路经模型证明了寻找最优连接的子阵列问题是一个典型的多阶段决策最优化问题；2) 给出了一个有效的启发式算法用来最小化开关的数目和内部连接的长度。我们的算法在选路的策略上采用了中、右、左的优先次序对原有的逻辑列进行校正。算法的运行时间被控制的线性量级上，子阵列的内部连接长度得到了巨大改进，同时保持了原有子阵列的大小。