Lagrangian relaxation based Multi-fault-tolerant topology generation for application-specific Network-on-Chips

With the development of semiconductor technology, application specific network-on-chip (ASNoC) has become an effective solution to the communication problems of nanoscale system-on-chips. This paper presents an ASNoC fault-tolerant topology generation method based on Lagrangian relaxation, which can realize large-scale user-defined K-fault-tolerant topology generation of ASNoC. The fault-tolerant topology generation method of ASNoC not only considers the possible link or router failures in the on-chip network, but also tolerates at least K errors in the router or link for the user-defined fault-tolerant number K. The IP core mapping problem and routing path allocation problem are solved simultaneously, and the power consumption is reduced to the maximum extent under the constraint conditions. The experimental results show that the proposed method significantly reduces power consumption, physical links, hops and running time. Meanwhile, it achieves a large-scale ASNoC fault-tolerant topology with acceptable runtime.