可重构处理器阵列的容错上界

可重构处理器阵列的容错上界 A New Upper Bound for Reconfigurable Multiprocessor Array with Faults 徐雄 XU Xiong1 1 first-author 沈宇泽 SHEN Yuze1 1 孙学梅 SUN Xuemei1 1 武继刚 WU Jigang1 1 2 天津工业大学计算机科学与软件学院 天津工业大学计算机科学与软件学院 School of Computer Science and Software,Tianjin Polytechnic University School of Computer Science and Software,Tianjin Polytechnic University 中国科学院软件所计算机科学国家重点实验室 中国科学院软件所计算机科学国家重点实验室 State Key Laboratory of Computer Science,The Institute of Software, Chinese Academy of Sciences State Key Laboratory of Computer Science,The Institute of Software, Chinese Academy of Sciences 基于一定约束条件下的多处理器阵列重构问题是一个热点问题,并已被证明具有NP难度.对于可重构处理器阵列容错上界（最大可用处理器阵列的大小）问题的求解,由于其理论上的难解性,多年来未取得突破性的进展.对此本文提出了一种新的求解算法并给予了理论上的论证.该算法通过分析阵列中的删除行与收获的逻辑列之间的关系,阐明了影响逻辑列总数的瓶颈条件.通过使用未损坏处理器（在逻辑上）替换损坏的处理器,突破限制逻辑列增长的瓶颈,逐步增加逻辑列数,最终计算出问题的新上界.仿真实验表明,与同类最新算法相比,在规模为128×128的处理器阵列上、处理器错误率在10%的情况下,原上界被降低了8.68%.最佳情况下的改进高达20%. The reconfiguration problem of degradable VLSI arrays is investigated intensively and has been proved to be NP-Complete.The upper bound for reconfigurable multiprocessor array with faults,with its nature of difficulty has no significant progress in the past ten years.In this paper an algorithm is proposed to calculate the upper bound.By analyzing the relationships between the excluded rows and the number of logic columns and breaking the bottleneck conditions in the host array which reduces the number of available logical column,the proposed algorithm gradually increases the size of target array,and then finds the new upper bound of this problem.Simulation results testify the effectiveness of the algorithm.The proposed algorithm is able to improve the latest work.The original upper bound can be reduced by 8.68% for the host array of size 128×128 with 10% faulty,and the improvement is up to 20%. 多处理器阵列 逻辑列 重构算法 容错上界 multiprocessor array logic columns reconfigurable algorithm upper bound 10.14188/j.1671-8836.2011.06.004 TN406 国家自然基金资助项目（60970016） 2011-06-01 2021-04-01 6 57