Reconfiguring Three-Dimensional Processor Arrays for Fault-Tolerance: Hardness and Heuristic Algorithms

With the increased density of three-dimensional (3D) processor arrays, faults can potentially occur quite often due to power overheating during massively parallel computing. In order to achieve fault-tolerance under such a scenario, an effective way is to find an as large as possible logical fault-free subarray of $m^{prime };times;$ $n^{prime };times;$ $h^{prime }$ from a faulty array of $m;times;$ $n;times;$ $h$ ( $m^{prime }$ $;le;$ $m,n^{prime }$ $;le;$ $n, h^{prime }$ $;le;$ $h$ ), such that an original application can still work on the $m^{prime };times;$ $n^{prime };times;$ $h^{prime }$ subarray. This paper investigates the problem of constructing maximum fault-free subarrays with minimum interconnection length from 3D arrays with faults. First, we prove that constructing maximum logical array (MLA) is NP-complete. We propose a linear-time algorithm which is capable of producing an MLA for the problem with the constraint of selected indexes. Second, we prove that minimizing the interconnection length (inter-length) of the MLA is NP-hard. We propose an efficient heuristic which significantly reduces the inter-length by revising each logical plane of the MLA. This leads to the reduction of communication cost, capacitance and dynamic power dissipation.