CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Heuristic Search for Adaptive, Defect-Tolerant Multiprocessor Arrays

V. Vasilikos ; G. Smaragdos ; C. Strydis ; Ioannis Sourdis (Institutionen för data- och informationsteknik, Datorteknik (Chalmers))
ACM Transactions on Embedded Computing Systems (1539-9087). Vol. 12 (2013),
[Artikel, refereegranskad vetenskaplig]

In this article, new heuristic-search methods and algorithms are presented for enabling highly efficient and adaptive, defect-tolerant multiprocessor arrays. We consider systems where a homogeneous multiprocessor array lies on top of reconfigurable interconnects which allow the pipeline stages of the processors to be connected in all possible configurations. Considering the multiprocessor array partitioned in substitutable units at the granularity of pipeline stages, we employ a variety of heuristic-search methods and algorithms to isolate and replace defective units. The proposed heuristics are designed for off-line execution and aim at minimizing the performance overhead necessarily introduced to the array by the interconnects' latency. An empirical evaluation of the designed algorithms is then carried out, in order to assess the targeted problem and the efficacy of our approach. Our findings indicate this to be a NP-complete computational problem, however, our heuristic-search methods can achieve, for the problem sizes we exhaustively searched, 100% accuracy in finding the optimal solution among 10(19) possible candidates within 2.5 seconds. Alternatively, they can provide near-optimal solutions at an accuracy which consistently exceeds 70% (compared to the optimal solution) in only 10(-4) seconds.

Nyckelord: Reliability, Algorithms, Design, Performance, Heuristic methods, adaptable architectures

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2013-04-19. Senast ändrad 2016-09-14.
CPL Pubid: 175863


Läs direkt!

Länk till annan sajt (kan kräva inloggning)


Denna publikation är ett resultat av följande projekt:

on-Demand System Reliability (DESYRE) (EC/FP7/287611)