灵活列选路模式下构造紧致逻辑阵列的高效算法

An Efficient Algorithm for Constructing Tightly-coupled Arrays Under Flexible Rerouting Schemes

当前成百上千的处理器可以集成到同一个芯片上,而高密度处理器阵列在高速并行处理的时候经常发生故障.一种有效的解决方法是构造一个不包含故障单元的逻辑阵列,使得原始任务能够继续执行.我们研究在灵活列选路模式下构造逻辑阵列的高效算法,使得所构造的逻辑阵列不仅规模最大而且互连网络长度尽可能短.我们提出的算法TCA首先使用现存算法构造一个最大逻辑阵列,之后优化各个逻辑列来减少阵列的互连网络长度,我们把优化每个逻辑列的问题转化为带权图上的最短路径问题求解.实验结果表明我们的方法显著减少了逻辑阵列互连网络长度.

Currently,hundreds to thousands of processing elements （PEs） are integrated in a single chip to process massive amounts of information in parallel, which increases the possibility of faults due to power overheating during massively parallel computing. An ef- fective way is to find a logical fault-free subarray such that the original application can still work on the subarray. In this paper,we propose an efficient algorithm, denoted as TCA, to construct maximum logical array（ MLA ） with short interconnects under flexible re- routing schemes. TCA first producing a MLA using existing algorithm, then revise each logical column of the MLA to minimize the in- terconnection length. The problem of refining each logical column is solved by modeling it as a shortest path problem on a weighted graph. Experimental results show that our approach significantly reduces the interconnection length of the logical array.