片上网络高性能可重构拓扑设计与任务分配技术

With the development of very large scale integration (VLSI) and wafer-scale integration (WSI) technologies, mesh connected processor arrays can be integrated on a single chip or wafer with high density. Reconfigurable techniques make the interconnected network on chips (NoC) more flexible, and thus efficient approaches for NoC system design become one of the hot research topics. As the density of VLSI and WSI arrays increases, the probability of the occurrence of defects in the arrays also increases. Therefore, fault tolerance design becomes one of the necessary techniques for the reliable of the NoC systems. This project is to explore efficient approaches on topology reconfiguration, topology customization, and task assignment on switch connected reconfigurable processor array with faults, under some certain constraints in high performance computing. By building contradiction graph and the complementary graph of the target topology，we try to construct the high performance logical array with shortest interconnect length for synchronous communication. Furthermore, we explore the reconfiguration algorithm design on three dimensional processor arrays with switch faults, that is the first consideration of the fault cases. Based on the given relation of the tasks, we customize the topology to (approximately) match the topology of the connected processors, and explore the maintenance techniques for the popular topology on fault tolerance. We investigate the task graph partitioning and reduction to minimize the communication cost between processors. In addition, we explore the algorithms for task assignment on the real time systems of processor array with faults. This project will provide critical algorithm techniques with property of high speed, high reliability and low power, for fault tolerant reconfigurable NoC systems.

随着VLSI 技术与半导体工艺的迅猛发展, 多处理器阵列已被高密度集成到单个芯片上，可重构技术又使得这种芯片上的互连网络具备了灵活多样的拓扑结构，致使片上网络技术成为当今高性能系统设计的研究热点。由于集成密度不断增加，容错机制成为系统可靠性必不可少的保障技术。该课题针对开关链接容错可重构片上网络，研究高性能目标下拓扑重构、拓扑定制、以及任务分配技术。以建立矛盾图以及目标拓扑的补图为思路，构造具有最佳同步通信性能并且内部链接紧致的高性能子阵列，并率先开展开关容错的三维阵列重构算法研究；依据给定的任务间关系，定制与任务图匹配或相近的处理器网络拓扑，探索容错环境中常用拓扑的实时维护技术；研究面向可有处理器及其拓扑连接的任务图划分/归约算法，谋求任务分配的自然与便捷，最小化处理器间的通信代价，并探索容错状态下动态任务的实时分配策略。为容错可重构片上系统提供高速度、高可靠、以及低功耗的算法技术支撑。

本课题针对开关链接容错可重构片上网络，研究高性能目标下拓扑重构、拓扑定制、以及任务分配技术。在目标阵列的重构方面，完成了从多处理器阵列中获取所需大小并且同步通讯性能优良的子阵列，提出了不同的逻辑列剔除策略，给出了三个面向通讯同步的拓扑重构算法。在处理器网络拓扑定制与重构技术方面，研究已将处理器网络上的问题推广到一般网络架构上，主要集中在网络可存活生成树的快速恢复技术。在任务划分、任务分配与任务归约方面，分别采用拍卖理论、智能优化算法等求解策略，给出了系统中资源位置的定位与分配的快速算法。.在学术成果的产出方面，在基金的资助下，课题组发表各类学术论文30篇，其中7篇论文发表在IEEE Transactions上，21篇被SCI收录、6篇被EI收录，5项授权专利。圆满完成了项目预定的立项指标。总体而言，经过项目组4年的努力，本项目取得了良好的研究成果，实现了高性能目标拓扑的重构、面向任务图的处理器拓扑定制与重构、以及面向处理器拓扑的任务划分、分配与归约。课题中预想的关键问题均已得到不同程度的解决。