近年来,随着超大规模集成电路(VLSI)的制造工艺和集成技术的飞速发展,单个芯片中处理单元的集成密度也呈指数性的增长,使得芯片的性能有了极大的提高。然而,随着集成密度的提高,芯片中处理单元出现故障的可能性也随之提高,这些故障单元,会严重影响芯片系统的稳定性和可靠性。因此,有必要对VLSI处理器阵列使用有效的容错技术,使其在故障出现的时候,能有效地对VLSI阵列进行重构,从而保证系统能正常稳定地工作。网状连接结构的VLSI处理器阵列,因其内部结构简单、规整,并且易于实现,被广泛应用于军事、航天和图形处理等领域中。目前针对网状连接结构处理器阵列的容错技术主要有两种:冗余法和降阶法。基于降阶法的思想,本文在二维、三维VLSI阵列重构问题上进行的研究工作有以下两点:一、在二维处理器阵列中,本文对加速构造高性能目标阵列问题进行了研究。本文在已有工作的基础上,针对其不足之处,提出改进方法,提高VLSI的重构速度。首先利用高效数据结构来表示实体结点的方法来构造新的网络模型,使新模型的结点个数比之前的模型少了一半;其次在新的网络模型基础上,基于网络流思想,提出一种可以在一次遍历中同时找出多条独立最短路径的重构算法,减少算法的重构时间,提高了算法的重构效率。最后的实验数据表明,在保证得到相同高性能目标阵列的前提下,提出的算法比之前的网络流重构算法运行时间要短。二、在三维处理器阵列中,本文对减少逻辑子阵列的长链接数目问题进行了研究。本文针对灵活选路构造出的最大规模目标阵列进行长链接优化,提出一种基于动态规划的优化算法,该算法对局部逻辑面以从右到左的方式逐一进行优化,然后把优化之后的局部逻辑面组合起来,得到最后的逻辑子阵列。最后的对比实验表明,该算法与之前算法相比,能有效地减少逻辑子阵列长链接数目。