片上网络多处理器阵列的拓扑重构

摘要

为了充分发挥众核处理器系统的计算能力，提升众核系统的稳定性，基于片上网络的可重构处理器阵列的容错重构技术变得越来越重要。可重构网络互连的多处理器系统通过改变处理器间的互连拓扑来支持系统的高效通信。本文主要研究讨论了多核处理器阵列的容错重构问题。
　　一方面，对于重构最大规模的无故障逻辑子阵列问题，我们提出了两种移位操作，即行双向移位操作和列移位操作，对处理器逻辑拓扑进行变换，并且提出了两个高效重构算法来解决拓扑容错重构问题。第一个算法CRS通过循环使用以上的两种移位操作用来产生初始拓扑结构。第二个算法利用Tabu搜索技术迭代地对CRS产生的拓扑结构进行优化。实验结果验证了所提出的算法有效性。在规模为16×16、包含30％故障处理器的多处理器阵列上，本文提出的算法在网络通信延迟和拥塞参数方面比现有算法改进了大约39％。
　　另一方面，对于重构规模满足应用需求的无故障逻辑子阵列问题，本文提出两个高效的重构算法。第一个算法使用贪心策略，通过引入滑动窗口的概念，构造最小内部通信延迟的逻辑子阵列。第二个算法以重构的实时要求为目的，使用滑动窗口技术，通过寻找具有最少故障节点数的子阵列，得到结构紧凑的目标阵列。通过与现有的算法比较，新算法有着较好的性能。在128×128的阵列上、对目标阵列为8×8的情况，第一个算法将内部通信延迟平均降低了16％;第二个算法将原算法大约22秒的运行时间缩短到5毫秒，并且与第一个算法具有相近的重构性能。

目录

声明

摘要

第一章 引言

1．1 研究背景

1．2 国内外研究现状与存在的问题

1．2．1 国内外研究现状

1．2．2 存在的问题

1．3 研究目标及主要贡献

1．4 论文组织结构

第二章 相关定义及问题描述

2．1 众核处理器阵列的容错技术

2．2 容错系统结构

2．3 问题的描述

第三章 重构最大规模子阵列问题及其容错算法

3．1 RRCS-gSA算法策略

3．1．1 求解初始解——RRCS算法

3．1．2 基于模拟退火算法的初始解的优化

3．2 CRS-TS算法

第四章 重构指定规模子阵列问题及其容错算法

4．1 PEA算法

4．2 FGA搜索算法

第五章 实验结果及分析

5．1 实验环境

5．2 重构最大规模子阵列问题的实验结果及分析

5．3 重构指定规模子阵列问题的实验结果及分析

第六章 总结与展望

6．1 回顾与总结

6．2 未来工作展望

参考文献

研究生期间发表论文及参加科研情况说明

致谢