251. Flexible scheme for reconfiguring 2D mesh-connected VLSI subarrays under row and column rerouting
- Author
-
Hao Ding, Zhongyi Zhai, Bisheng Huang, Lingzhong Zhao, and Junyan Qian
- Subjects
Very-large-scale integration ,Computer Networks and Communications ,Computer science ,020206 networking & telecommunications ,02 engineering and technology ,Parallel computing ,Fault (power engineering) ,Column (database) ,Theoretical Computer Science ,Dynamic programming ,Artificial Intelligence ,Hardware and Architecture ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Maximum subarray problem ,Routing (electronic design automation) ,Time complexity ,Host (network) ,Software - Abstract
In the mesh-connected processors, some processor elements (PEs) become ineffective due to high temperature, overload and other factors, which can affect the stability of the system. This paper deals with the problem of reconfiguring the largest possible subarray from the processor with faults under the row and column rerouting constraint. Firstly, a flexible routing scheme, based on dynamic programming, is proposed to construct the local optimal logical columns. Secondly, we discuss and revise the PEs that cannot be connected between every two logical columns under this scheme. Finally, an efficient algorithm is presented to construct the maximum subarray in polynomial time. The experimental results show that, both on the random and clustered fault scenarios, the proposed algorithm under flexible rerouting scheme is capable of constructing the larger scale logical arrays. On a 48 × 48 host array with 15% fault density, the improvement on the use of fault-free PEs is up to 6.22% for random faults. On a 256 × 256 host array, the improvement can be up to 85.60% for clustered faults. Moreover, the proposed algorithm runs faster than previous algorithms under different size arrays and fault densities, the average improvement in running time is up to 99% compared with state-of-the-art.
- Published
- 2021
- Full Text
- View/download PDF