Algorithms for reconfiguring NoC-based fault-tolerant multiprocessor arrays

This paper investigates the techniques to construct high-quality target processor array (fault-free logical subarray) from a physical array with faulty processing elements (PEs), where a fixed number of spare PEs are pre-integrated that can be used to replace the faulty ones when necessary. A reconf...

Full description

Saved in:
Bibliographic Details
Main Authors: Wu, Jigang, Wu, Yalan, Jiang, Guiyuan, Lam, Siew Kei
Other Authors: School of Computer Science and Engineering
Format: Article
Language:English
Published: 2020
Subjects:
Online Access:https://hdl.handle.net/10356/142294
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-142294
record_format dspace
spelling sg-ntu-dr.10356-1422942020-06-18T07:33:45Z Algorithms for reconfiguring NoC-based fault-tolerant multiprocessor arrays Wu, Jigang Wu, Yalan Jiang, Guiyuan Lam, Siew Kei School of Computer Science and Engineering Engineering::Computer science and engineering Network On Chip Multiprocessor Array This paper investigates the techniques to construct high-quality target processor array (fault-free logical subarray) from a physical array with faulty processing elements (PEs), where a fixed number of spare PEs are pre-integrated that can be used to replace the faulty ones when necessary. A reconfiguration algorithm is successfully developed based on our proposed novel shifting operations that can efficiently select proper spare PEs to replace the faulty ones. Then, the initial target array is further refined by a carefully designed tabu search algorithm. We also consider the problem of constructing a fault-free subarray with given size, instead of the original size, which is often required in energy-efficient MPSoC design. We propose two efficient heuristic algorithms to construct target arrays of given sizes leveraging a sliding window on the physical array. Simulation results show that the improvements of the proposed algorithms over the state of the art are 19% and 16%, in terms of congestion factor and distance factor, respectively, for the case that all faulty PEs can be replaced using the spare ones. For the case of finding 64×64 target array on 128×128 host array, the proposed heuristic algorithm saves the running time up to 99% while the solution quality keeps nearly unchanged, in comparison with the baseline algorithms. 2020-06-18T07:33:45Z 2020-06-18T07:33:45Z 2019 Journal Article Wu, J., Wu, Y., Jiang, G., & Lam, S. K. (2019). Algorithms for reconfiguring NoC-based fault-tolerant multiprocessor arrays. Journal of Circuits, Systems and Computers, 28(7), 1950111-. doi:10.1142/S0218126619501111 0218-1266 https://hdl.handle.net/10356/142294 10.1142/S0218126619501111 2-s2.0-85052673001 7 28 en Journal of Circuits, Systems and Computers © 2019 World Scientific Publishing Company. All rights reserved.
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic Engineering::Computer science and engineering
Network On Chip
Multiprocessor Array
spellingShingle Engineering::Computer science and engineering
Network On Chip
Multiprocessor Array
Wu, Jigang
Wu, Yalan
Jiang, Guiyuan
Lam, Siew Kei
Algorithms for reconfiguring NoC-based fault-tolerant multiprocessor arrays
description This paper investigates the techniques to construct high-quality target processor array (fault-free logical subarray) from a physical array with faulty processing elements (PEs), where a fixed number of spare PEs are pre-integrated that can be used to replace the faulty ones when necessary. A reconfiguration algorithm is successfully developed based on our proposed novel shifting operations that can efficiently select proper spare PEs to replace the faulty ones. Then, the initial target array is further refined by a carefully designed tabu search algorithm. We also consider the problem of constructing a fault-free subarray with given size, instead of the original size, which is often required in energy-efficient MPSoC design. We propose two efficient heuristic algorithms to construct target arrays of given sizes leveraging a sliding window on the physical array. Simulation results show that the improvements of the proposed algorithms over the state of the art are 19% and 16%, in terms of congestion factor and distance factor, respectively, for the case that all faulty PEs can be replaced using the spare ones. For the case of finding 64×64 target array on 128×128 host array, the proposed heuristic algorithm saves the running time up to 99% while the solution quality keeps nearly unchanged, in comparison with the baseline algorithms.
author2 School of Computer Science and Engineering
author_facet School of Computer Science and Engineering
Wu, Jigang
Wu, Yalan
Jiang, Guiyuan
Lam, Siew Kei
format Article
author Wu, Jigang
Wu, Yalan
Jiang, Guiyuan
Lam, Siew Kei
author_sort Wu, Jigang
title Algorithms for reconfiguring NoC-based fault-tolerant multiprocessor arrays
title_short Algorithms for reconfiguring NoC-based fault-tolerant multiprocessor arrays
title_full Algorithms for reconfiguring NoC-based fault-tolerant multiprocessor arrays
title_fullStr Algorithms for reconfiguring NoC-based fault-tolerant multiprocessor arrays
title_full_unstemmed Algorithms for reconfiguring NoC-based fault-tolerant multiprocessor arrays
title_sort algorithms for reconfiguring noc-based fault-tolerant multiprocessor arrays
publishDate 2020
url https://hdl.handle.net/10356/142294
_version_ 1681059016111816704