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

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