Fault-Tolerant Topology Synthesis For Application-Specific Network-on-Chip

With the scaling of semiconductor manufacturing technologies,hundreds to thou-sands of processing cores can be integrated on a single chip and inter-chip communi-cation within the chip has also become a major challenge.Network-on-Chips(NoC)have emerged as an attractive solution to the interconnection challenges of heteroge-neous System-on-Chip designs because an NoC have a good scalability and enables an ible utilization of communication resources compared with the traditional point-to-point links and buses.However,highly integrated chips increase the failure rate of different components(such as physical links,switches,etc.)in the network-on-chip.Once a physical link or switch in the network-on-chip fails,communication between cores will be blocked,causing the entire chip to fail.Therefore,the reliability of network-on-chip becomes the key to ensure the normal communication within the chip.Researching the fault-tolerant network-on-chip has important significance for improving the relia-bility of network-on-chip.Though an NoC architecture consists of regular or irregular topologies customized irregular topologies are more suitable for application-specific NoCs(ASNoC)because of low energy consumption,low area overhead,etc.This thesis presents a multi-fault-tolerant ASNoC topology synthesis method.The main contribu-tions are as follows:(1)Physical link fault tolerance method.This method proposes a topology gen-eration method that considers only physical link fault tolerance,and integrates the two subproblems,cores clustering and path allocation,into the same integer linear program-ming model to solve simultaneously,which can improve the quality of the optimal so-lution due to the effect of mutual restraint between the results of the two subproblems.This thesis adopts the method of integrating core clustering and path allocation into an integer linear programming model and assigning all the traffic flows between cores together.Experimental results show that:a)Compared with the FTTG,the power con-sumption is reduced by an average of 10.58%,and the average hop count is reduced by 6.25%,embodying the global optimality of integrating the two subproblems,cores clustering and path allocation;b)Compared with the DBG,the power consumption is reduced by an average of 21.72%,and the average hop count is reduced by 9.35%,em-bodying the effectiveness of the integer linear programming algorithm in finding the optimal solution;c)Compared to non-fault-tolerant topologies,the fault-tolerant topol-ogy power consumption of K = 1,K ? 2 and K=3 have increased by an average of 11.9%,23.8%and 52.1%,respectively,which shows that the power consumption of fault-tolerant topology increases with the increase of K value.(2)Multi-fault-tolerant network-on-chip topology generation method based on in-teger linear programming.With a user-defined maximum number of fault tolerance,K(? 1),we propose a three-stage method to generate topologies,which can tolerate at most K faults in switches or phyical channels(links),for ASNoC.For a given core communication graph and location information of cores and switches,this thesis first uses the minimum-cost maximum-flow(min-cost-max-flow)algorithm to establish the physical link between cores and switches;and then uses an algorithm based on integer linear programming to allocate K+ 1 switch-disjoint paths for each communication requirement in order.This thesis needs to adopt a method of assigning traffic flows between cores sequentially for large-scale core communication graph.Experimental results show:Compared with non-fault-tolerant topologies,the fault-tolerant topology power consumptions of K = 1,K = 2 and K = 3 have increased by an average of 94.3%,192.0%and 307.2%respectively,which that the power consumption of router fault tolerant Topology increases with the increase of K value.(3)Redundant port sharing method for switches.To solve the problem of exces-sive power consumption caused by excessive port redundancy with K-fault tolerance,port sharing is proposed to reduce the size of switches,which in turn reduces power consumption.First,this thesis describes the conditions for port sharing when satisfying the nature of multi-fault tolerance.Second,a heuristic algorithm based on maximum group and maximum two-point matching is used to share the redundant port on the switches.Experimental results show:(1)Compared with non-port sharing topologies,the average power consumption was decreased by 27.25%,36.83%and 39.81%with the port sharing topology of K = 1,K = 2 and K = 3.(2)Compared to the non fault-tolerant topology,the average power consumption of the fault-tolerant topology considering the port sharing is 41.70%,85.15%and 146.53%in the K ?1,K =2 and K =3 fault-tolerant conditions,which embodies the effectiveness of the redundant port sharing methodThe fault-tolerant ASNoC topology synthesis method proposed in this thesis can be integrated into EDA tools for the generation of on-chip fault-tolerant interconnected communication network topology.