中文摘要：

网格连接的多处理器阵列是人们推崇的高性能体系结构之一，它被广泛地应用在大规模并行分布计算、图形图像处理中。随着VLSI技术的高度发展，越来越多的计算单元可集成在单个芯片上，并由此发展而来了当下流行的片上网络系统。这种高密度集成的处理器网络，无论在其制造过程还是在其运行过程中，处理器都不可避免地会出现故障，容错重构机制成为系统不可缺少的可靠性保障技术. 本项目对网格连接的可重构处理器阵列，研究设计高效快速的容错重构算法与选路技术；针对低功耗、高性能等不同应用的要求，生成不同优化目标下的最优或近似最优的高质量逻辑阵列，而不仅仅是现有重构技术所能产生的普通逻辑阵列；充分利用硬件具有并行加速的内在优势，率先引入并行算法设计技术，用于快速生成特别是实时系统所需的逻辑阵列；借鉴相应的阵列重构技术为多核片上网络系统的实时作业提供低温高性能子阵列，在完成作业分派的同时，兼顾提高片上系统的可靠性。

结论摘要：

课题组紧紧围绕预定的研究目标与相关研究内容，设计积极可行的研究方案，对课题中的各项难题展开技术攻关。提出了对原始阵列的预处理技术，用于降低算法的回溯次数，并为并行重构算法的设计做好了铺垫；对原有的重构算法实现了理想的加速，主要研究成果将重构算法的计算复杂度近乎降到了复杂度的下界；对紧致的目标阵列的构造与定位，提出了近似最优的算法并进行了算法模拟；对给定的容错物理阵列提出了最大逻辑阵列大小的新上界，使得求解重构问题的任意算法性能的评估更为精准高效；提出了多线程的平行重构算法，并基于分治法设计完成了单列构造的并行算法, 并行加速效果平均达到最优状态；使用动态规划技术，提出的算法确保生成局部最优的低温逻辑列， 进而导出近似最优的低功耗逻辑阵列；提出了多种高性能容错路由算法，算法规定了消息选路规则，避免了死锁的发生，并采用最少数量的虚拟通道，降低了开关的成本和功耗。在取得上述突破性进展的同时,课题组进一步拓展了该课题的研究领域。由于VLSI集成技术的高速发展导致元器件集成密度的成倍提高，多处理器阵列中开关出现故障的情况成为一个具有现实意义的研究内容。我们首次提出并讨论了开关容错的多处理器重构算法，初步的研究结果必将导出一系列新的研究课题。另外，针对高性能体系结构中常用的三维mesh结构，我们将二维mesh阵列上的容错重构问题拓展到了三维mesh结构上并得到一系列高水平的研究成果。同时，在相关的Mesh网络设计技术、软硬件协同设计技术等相关方向上开展了卓有成效的研究，并得到了高水平的研究成果。在课题的资助下，课题组主要成员发表各类学术论文39篇，其中5篇被SCI收录、28篇被EI收录，在IEEE Trans.上发表2篇、在审2篇，中国计算机学会指定的或已经召开十届以上的高水平国际学术会议论文14篇，大幅超额完成了课题预定的多项任务指标。