基本信息
- 项目名称：
- 可重构多处理器阵列的容错上界
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 信息技术
- 大类：
- 自然科学类学术论文
- 简介：
- 可重构多处理器阵列的容错上界
- 详细介绍：
- 可重构多处理器阵列的容错上界
作品专业信息
撰写目的和基本思路
- 对于一个给定的多处理器阵列，可以通过去除阵列中的某些行，利用这些行的可利用的点在逻辑上补偿阵列中的其他不可用点，以提高处理器的利用率。本作品从研究被去除的行与增加的最大逻辑列数之间的关系入手，推理出自己的结论，并在此基础上进行分析，提出了自己的算法。
科学性、先进性及独特之处
- 本作品针对多处理器容错计算领域中的一个技术难题给予研究,同时给出了求解这一问题新算法，计算出了可用处理器数量的新上界，具有极高的学术价值。
应用价值和现实意义
- 作品具有很好的实际应用价值和很好的应用前景，该课题研究的成果将会大大提高大规模集成电路（VLSI）的使用性能，非常符合现在国家倡导的高性能低功耗的目标。
学术论文摘要
- 本文讨论了一种求解可重构多处理器阵列容错上界的新算法，此问题是多处理器容错计算领域中的一个技术难题，由于其理论上具有难解性，以至于在学术界近十年来都没有突破性进展.本论文分析了阵列中去除行与增加逻辑列的关系并提出了SAR（Select andReverse）算法并给予了理论上的证明.此算法通过打破阵列中影响逻辑列总数的瓶颈条件，逐步增加逻辑列数，最终计算出问题的新上界.通过试验模拟结果计算得出，当处理器错误率在10%的情况下，对于128×128规模的处理器阵列，本算法将该问题上界降低9.43%。
获奖情况
- 无
鉴定结果
- 申报者在其所描述的项目中论据充分，引证可靠，项目内容真实有效。可以进行立项申请。
参考文献
- Chor Ping Low,Member,IEEE,"An Efficient Reconfiguration Algorithm for Degradable VLSI/WSI Arrays,"IEEE Trans on Computers, vol 49, no.6, pp.553-559,June 2000.
同类课题研究水平概述
- 到目前为止主要有两种方法解决阵列重组问题：冗余方法和重构方法。所谓冗余方法就是在制造芯片时预留一定数量的备用处理单元，当有工作处理单元出现故障时，使用备用处理单元来取代不能正常工作的处理器。针对冗余方法有不同的策略，很多文献[1]-[7]详细陈述了这些策略，还有的学者提出了带有备用行和列的处理器体系。这种方法的最大特点是，重构后阵列的大小是固定不变的，但是，如果备用处理器不能完全取代发生故障的处理器，冗余重构策略就失效，导致整个系统停止工作。 不同于冗余方法，重构方法把阵列中的所有元素都同等对待，不提前预留备用处理单元。这种方法采用的是在故障发生后通过尽可能多的使用剩余的无故障处理单元来构建目标阵列的策略。重构后的VLSI阵列的阶数比原VLSI阵列的要小，因此，这种方法又被称为降阶重构方法。 对于VLSI阵列上的降阶重构方法的研究开始于80年代，一些学者开始了对降阶重构问题模型分析、解决策略的探讨。90年代后，降阶重构方法的研究发展迅速，S. Y. Kuo 和 I.Y. Chen针对本问题在三种不同的选路约束条件下进行了研究：1) 行、列穿越方式（rowand column bypass），2) 行穿越、列选路方式（row bypass andcolumn rerouting），3) 行、列选路方式（row and columnrerouting）。通过研究，他们证明了大多数基于这三种约束条件下而产生的问题都是NP完全问题，同时他们针对这类问题提出了启发式的解决算法。 C.P. Low and H.W.Leong提出了在第二及第三种约束条件下的通用启发式解决算法，可以在多项式时间内找到近似最优解，并且指出在第二种约束条件下阵列重组问题的一个特例可以在线性时间内得到最优解，并给出了算法的详细描述和证明过程。这是一种新的基于贪心策略的启发式算法。由于第二种选路约束在重构时具有更大的灵活性，后续的很多研究都偏向于以此为模型。
