An improved fault-tolerant routing algorithm for a Network-on-Chip derived with formal analysis

Abstract : A fault-tolerant routing algorithm in Network-on-Chip (NoC) architectures provides adaptivity for on-chip communications. Adding fault-tolerance adaptivity to a routing algorithm increases its design complexity and makes it prone to deadlock and other problems if improperly implemented. Formal verification techniques are needed to check the correctness of the design. This paper describes the discovery of a potential livelock problem through formal analysis on an extension of the link-fault tolerant NoC architecture introduced by Wu et al. In the process of eliminating this problem, an improved routing architecture is derived. The improvement simplifies the routing architecture, enabling successful verification using the CADP verification toolbox. The routing algorithm is proven to have several desirable properties including deadlock and livelock freedom, and tolerance to a single-link-fault.
Type de document :
Article dans une revue
Science of Computer Programming, Elsevier, 2016, 〈10.1016/j.scico.2016.01.002〉
Liste complète des métadonnées

Littérature citée [41 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01261234
Contributeur : Wendelin Serwe <>
Soumis le : lundi 25 janvier 2016 - 07:29:07
Dernière modification le : vendredi 12 octobre 2018 - 01:18:06
Document(s) archivé(s) le : mardi 26 avril 2016 - 10:22:36

Fichier

scp_fmics2014.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Zhen Zhang, Wendelin Serwe, Jian Wu, Tomohiro Yoneda, Hao Zheng, et al.. An improved fault-tolerant routing algorithm for a Network-on-Chip derived with formal analysis. Science of Computer Programming, Elsevier, 2016, 〈10.1016/j.scico.2016.01.002〉. 〈hal-01261234〉

Partager

Métriques

Consultations de la notice

638

Téléchargements de fichiers

351