Reducing the Interconnection Length for 3D Fault-Tolerant Processor Arrays

摘要

The three-dimensional (3D) processor array has benefits of reducing interconnection latency, consuming less power and improving bandwidths compared to 2D processor arrays. However, it suffers from frequent faults due to power overheating during massively parallel computing. To achieve fault-tolerance under such a such a scenario, an effective method is to construct a non-faulty sub-array from the faulty array as large as possible, such that the original application can still work on the sub-array. However, logical sub-arrays produced by previous works contain large number of long interconnects, which leads to more communication cost, capacitance and dynamic power dissipation. In this paper, we investigate the problem of reducing the interconnection length of a logical array. First, we prove that it is a NP-hard problem. Then we propose an efficient heuristic to reduce the interconnection redundancy of a logical array by reducing the number of long interconnects in each logical plane. Each logical plane is optimized based on statistical information. Experimental results show that, on 32 × 32 × 32 host array with fault densities ranging from 0.1% to 5%, the proposed algorithm is capable of reducing the interconnection length by 49.7% and 29.8% in average compared to the existing algorithm GPR and CAR, respectively.