Generation of Application Specific Fault Tolerant Irregular NoC Topologies Using Tabu Search

• Gustavo Bezerra UFRN
• Patricia Cruz UFRN
• Monica Pereira UFRN
• Márcio Kreutz UFRN

Resumo

Initial Network on Chip (NoCs) topologies tended to have a regular structure, aiming flexibility regular performance for different applications, and multiple paths between routers. However, regular topologies lack in performance if compared to specific application generated topologies, often irregular. On the other hand, irregular topologies may lack flexibility (multiple communication paths). Moreover, in the billion-transistor era, circuit components are more susceptible to faults, transients and permanents. Due to the cost of producing such circuits, it is desirable to increase their lifespan which may be achieved by adding fault tolerance to the circuit, such as through hardware redundancy. This work proposes the generation of irregular topologies considering additional links to provide fault tolerance. The irregular topology with the additional links were generated through a Tabu Search approach. Thus generating intermediate topologies: flexible if compared to most irregular ones (some fault resistance), yet achieving application specific high performance if compared to regular NoCs.

Palavras-chave: Fault Tolerance and Dependability, Performance Evaluation and Optimization

Referências

C. Wang J. Wu G. Jiang J. Sun "An efficient topology reconfiguration algorithm for noc based multiprocessor arrays" High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing (HPCC EUC) 2013 IEEE 10th International Conference on pp. 873-880 2013.

R. R. Schaller "Moore’s law: past present and future" IEEE spectrum vol. 34 no. 6 pp. 52-59 1997.

W. Stallings Computer organization and architecture: designing for performance Pearson Education India 2003.

D. A. Patterson J. L. Hennessy "Computer Organization and Design MIPS Edition: The Hardware/Software Interface" Newnes 2013.

C. A. Zeferino A. A. Susin "Socin: a parametric and scalable network-on-chip" Integrated Circuits and Systems Design 2003. SBCCI 2003. Proceedings. 16th Symposium on pp. 169-174 2003.

A. Hemani A. Jantsch S. Kumar A. Postula J. Oberg M. Millberg D. Lindqvist "Network on chip: An architecture for billion transistor era" Proceeding of the IEEE NorChip Conference vol. 31 pp. 11 2000.

G. Ascia V. Catania M. Palesi "Multi-objective mapping for mesh-based noc architectures" Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis pp. 182-187 2004.

N. Choudhary M. Gaur V. Laxmi "Irregular noc simulation framework: Irnirgam" Emerging Trends in Networks and Computer Communications (ETNCC) 2011 International Conference on pp. 1-5 2011.

N. Choudhary M. S. Gaur V. Laxmi V. Singh "Genetic algorithm based topology generation for application specific network-on-chip" Circuits and Systems (ISCAS) Proceedings of 2010 IEEE International Symposium on pp. 3156-3159 2010.

K. Jain N. Choudhary D. Singh "Energy efficient branch and bound based on-chip irregular network design" Global Journal of Computer Science and Technology 2014.

Y.-C. Chang C.-T. Chiu S.-Y. Lin C.-K. Liu "On the design and analysis of fault tolerant noc architecture using spare routers" Proceedings of the 16th Asia and South Pacific Design Automation Conference pp. 431-436 2011.

J. W. d. Mesquita "Exploração de espaço de projeto para geração de redes em chip de topologias irregulares otimizadas: a rede utnoc" Master’s thesis 2016.

P. Shah A. Kanniganti J. Soumya "Fault-tolerant application specific network-on-chip design" Embedded Computing and System Design (ISED) 2017 7th International Symposium on pp. 1-5 2017.

M. Gendreau J.-Y. Potvin et al. Handbook of metaheuristics Springer vol. 2 2010.

E. Salminen A. Kulmala T. D. Hamalainen "Survey of network-on-chip proposals" white paper OCP-IP vol. 1 pp. 13 2008.

M. Radetzki C. Feng X. Zhao A. Jantsch "Methods for fault tolerance in networks-on-chip" ACM Computing Surveys (CSUR) vol. 46 no. 1 pp. 8 2013.

C. Neeb N. Wehn "Designing efficient irregular networks for heterogeneous systems-on-chip" Journal of Systems architecture vol. 54 no. 3–4 pp. 384-396 2008.

K. Srinivasan K. S. Chatha G. Konjevod "Linear-programming-based techniques for synthesis of network-on-chip architectures" IEEE Transactions on Very Large Scale Integration (VLSI) Systems vol. 14 no. 4 pp. 407-420 2006.

N. Venkataraman R. Kumar "Design and analysis of application specific network on chip for reliable custom topology" Computer Networks 2019.

M. Koibuchi H. Matsutani H. Amano T. M. Pinkston "A lightweight fault-tolerant mechanism for network-on-chip" Proceedings of the Second ACM/IEEE International Symposium on Networks-on-Chip pp. 13-22 2008.

S.-Y. Lin W.-C. Shen C.-C. Hsu C.-H. Chao A.-Y. Wu "Fault-tolerant router with built-in self-test/self-diagnosis and fault-isolation circuits for 2d-mesh based chip multiprocessor systems" 2009 International Symposium on VLSI Design Automation and Test pp. 72-75 2009.

P. Yang Q. Wang W. Li Z. Yu H. Ye "A fault tolerance noc topology and adaptive routing algorithm" Embedded Software and Systems (ICESS) 2016 13th International Conference on pp. 42-47 2016.

M. Hosseinabady M. R. Kakoee J. Mathew D. K. Pradhan "Reliable network-on-chip based on generalized de bruijn graph" 2007 IEEE International High Level Design Validation and Test Workshop pp. 3-10 2007.

A. Jantsch H. Tenhunen et al. Networks on chip Springer vol. 396 2003.

S. H. Bokhari "On the mapping problem" IEEE Transactions on Computers no. 3 pp. 207-214 1981.

R. J. Wilson Introduction to graph theory India:Pearson Education 1979.

M. Gendreau J.-Y. Potvin "Tabu search" in Search methodologies Springer pp. 165-186 2005.

R. P. Dick D. L. Rhodes W. Wolf "Tgff: task graphs for free" Proceedings of the Sixth International Workshop on Hardware/Software Codesign.(CODES/CASHE’98) pp. 97-101 1998.