## Generalized Fault-Tolerance Topology Generation for Application Specific Network-on-Chips

Song Chen, Member, IEEE , Mengke Ge, Zhigang Li, Jinglei Huang, Qi Xu, and Feng Wu, Fellow, IEEE

Abstract -The Network-on-Chips based communication architecture is a promising candidate for addressing communication bottlenecks in many-core processors and neural network processors. In this work, we consider the generalized fault-tolerance topology generation problem, where the link (physical channel) or switch failures can happen, for application-specific network-onchips (ASNoC). With a user-defined maximum number of faults, K , we propose an integer linear programming (ILP) based method to generate ASNoC topologies, which can tolerate at most K faults in switches or links. Given the communication requirements between cores and their floorplan, we first propose a convexcost flow based method to solve a core mapping problem for building connections between the cores and switches. Second, an ILP based method is proposed to solve the routing path allocation problem, where K + 1 switch-disjoint routing paths are allocated for every communication flow between the cores. Finally, to reduce switch sizes, we propose sharing the switch ports for the connections between the cores and switches and formulate the port sharing problem as a clique-partitioning problem, which is solved by iteratively finding the maximum cliques. Additionally, we propose an ILP-based method to simultaneously solve the core mapping and routing path allocation problems when only physical link failures are considered. Experimental results show that the power consumptions of fault-tolerance topologies increase almost linearly with K because of the routing path redundancy for fault tolerance. When both switch faults and link faults are considered, port sharing can reduce the average power consumption of faulttolerance topologies with K = 1 , K = 2 and K = 3 by 18.08%, 28.88%, and 34.20%, respectively. When considering only the physical link faults, the experimental results show that compared to the FTTG (fault-tolerant topology generation) algorithm, the proposed method reduces power consumption and hop count by 10.58% and 6.25%, respectively; compared to the DBG (de Bruijn Digraph) based method, the proposed method reduces power consumption and hop count by 21.72% and 9.35%, respectively.

be easily integrated on a single chip [1]. Network-on-Chips (NoCs) have emerged as an attractive solution to the interconnection challenges of heterogeneous System-on-Chip designs [2] [3] [4] and neuromorphic computing systems [5] [6] [7] because NoCs have good scalability and enable efficient and flexible utilization of communication resources when compared to the traditional point-to-point links and buses. NoCs convey messages (in packets) through a distributed system of routers (sometime called switches in ASNoCs) interconnected by links, and these routers may include network interfaces for connecting cores to routers. In this work, we focus on ASNoCs, where the customized irregular network topologies are used because of their low energy consumption and low area overhead [8], [9].

Index Terms -Network-on-Chip, Fault Tolerance, Path Allocation, Application-Specific Network-on-Chips

## I. INTRODUCTION

With the constant scaling of semiconductor manufacturing technologies, hundreds to thousands of processing cores can

This work was partially supported by the National Natural Science Foundation of China (NSFC) under grant Nos. 61874102 and 61732020, Beijng Municipal Science &amp; Technology Program under Grant Z181100008918013, and the Fundamental Research Funds for the Central Universities under grant No. WK2100000005. The authors would like to thank Information Science Laboratory Center of USTC for the hardware &amp; software services.

S. Chen, M. Ge, Z. Li, and F. Wu are with the School of Microelectronics, University of Science and Technology of China (USTC), China; (Email: songch@ustc.edu.cn). S. Chen and F. Wu are also with USTC Beijing Research Institute, Beijing, China

- J. Huang is with State Key Laboratory of Air Traffic Management System and Technology, China (email:huangjl@mail.ustc.edu.cn).
- Q. Xu is with the School of Electronic Science and Applied Physics, Hefei University of Technology, China (email: xuqi@hfut.edu.cn).

With successive technology node shrinking, the transistor size on chips has been scaled down to a few nanometers, where radiation, electromagnetic interference, electrostatic discharge, aging, process variation and dynamic temperature variation are the major causes of failures in MOSFET based circuits [10] [11] [12]. It is extremely difficult for a heterogeneous system to guarantee long-term product reliability because of a combination of these factors. To maintain network connectivity and correct packet-switching operations, we consider faulttolerance issues of the network components in ASNoCs. NoC with regular topologies can achieve fault tolerance by providing alternative routing paths when messages or packets encounter faulty network components. However, in ASNoCs, the path diversity is greatly reduced for lowering the energy and area overhead of the network components. Consequently, we have to introduce structural redundancies, such as switches, ports, links, and network interface, to address these faults [13]-[16]. Then, alternative routing paths are used for the packet switching between the cores, thus bypassing the faulty region [17]. Note that, generally, fault control in NoC involves two phases: fault diagnosis and fault tolerance [18]. Our research mainly focuses on the fault tolerance.

There are many previous works addressing the synthesis of ASNoC topologies [9], [19]-[30]. However, these works rarely consider fault tolerance in the NoC topologies. In particular, the ASNoCs have low path diversities and cannot work normally if any hardware faults occur in the switches or links. In [31], a fault tolerant NoC architecture was proposed, where the cores were linked to two switches instead of one, and a dynamically reconfigured routing algorithm was used to bypass faulty switches. Chatter et al. [32] proposed a fault-tolerant method based on router redundancy. They allocated a spare router for each router for fault tolerance, which increased the

consumed power and area. In [33], the authors placed a spare router for each 2 × 2 router block in the mesh topology and used multiplexers to switch the faulty routers to the intact routers, which could thereby decrease the power and area overheads compared to [32]. However, this method cannot be applied to ASNoC designs.

Tosun et al. [34] proposed a fault-tolerant topology generation (FTTG) method for ASNoC, which focused on permanent link and switch port failures. The authors attempted to add a minimum number of extra switches and links and use the min-cut algorithm to ensure that each switch and link were on a cycle, which provided at least two alternative routing paths to achieve adequate fault-tolerance. The NoC topologies are generated in two phases. In the first phase, the links between the switches (switch topologies) are constructed, and in the second phase, the links from the cores to switches are built (core mapping). However, the switch topology and the core mapping strongly depend on each other; consequently, it is challenging for the FTTG method to effectively explore the design space of the network topologies. Additionally, the FTTG can only generate one-fault tolerant topologies and cannot be applied toward generating multiple-fault tolerant network topologies.

Motivated by these arguments, we propose a method for generating ASNoC topologies with consideration of both switch faults and physical link faults, when given the communication requirements between the cores, floorplan of the cores, and maximum number of tolerable faults, K . The main contributions of this work are as follows.

- 1) We propose a generalized fault-tolerant topology generation method with consideration of both switch faults and link faults. A convex-cost flow based method is used to solve the core mapping problem for building connections between the cores and switches, and an ILP based method is proposed to allocate K + 1 switch-disjoint routing paths for each communication flow.
- 2) To reduce the switch sizes, we propose sharing the switch ports for the connections between the cores and switches, and prove the conditions for port sharing on a switch. The port sharing problem on a switch is formulated as a clique-partitioning problem and heuristically solved by iteratively finding a set of maximum cliques and solving a maximum cardinality matching problem. Moreover, we propose a heuristic method, where a series of maximum independent set problems are solved for removing the conflicts caused by port sharing on multiple switches.
- 3) Additionally, we also propose an ILP-based method to simultaneously solve the core mapping and routing path allocation problems when only the physical link failures are considered.

Experimental results show that the power consumptions of fault-tolerance topologies increase almost linearly with K because of the routing path redundancies (See Fig.12). When both switch faults and link faults are considered, port sharing can respectively reduce the average power consumptions of the fault-tolerance topologies with K = 1, K = 2 and K = 3 by 18.08%, 28.88%, and 34.20%. When considering only the phys- ical link faults, the experimental results show that, compared to the FTTG, the proposed method reduces power consumption and hop count by 10.58% and 6.25%, respectively; compared to the DBG based method, the proposed method reduce power consumption and hop count by 21.72% and 9.35%, respectively.

The remainder of this paper is organized as follows. Section II formulates the K -fault-tolerant ASNoC topology generation problem. The overview of the proposed framework is shown in Section III. The generalized K -fault-tolerant topology generation methodology is discussed in section IV-A, IV-B and V. Section VI discusses the generation method for link-faulttolerance topologies. The experimental results are provided in Section VII, followed by the conclusions in Section VIII.

## II. PRELIMINARIES &amp; PROBLEM FORMULATION

## A. NoC Architecture

In this work, the ASNoC architectures are assumed to support packet-switched communications with source routing and wormhole flow control [35]. In the application-specific design, the communication characteristics are known a priori, and hence, a deterministic routing strategy is used; that is, the routing path for the communications is preallocated, which accordingly determines the topology of the NoC. The ASNoC topology architecture consists of two main components: switches and customized electrical links. The switches are used to route packets from the source to the destination, and the routing information is included in the packet to specify the address of the output port, to which the packet should be forwarded. Given the communication characteristics of an application, this work focuses on the generation of network topologies by preallocating the routing paths for the communication flows.

## B. Problem Definition

Let Vc = { ci | 1 ≤ ≤ i ncore } be the set of cores in an application. The communication requirements (or communication flow in this work) between the cores can be represented as a directed graph, Gcc , and defined as follows.

Definition 1: Gcc =( Vc , Ecc ) is directed. An edge ( ci , cj ) ∈ Ecc represents the communication from ci to cj . Besides, the bandwidth requirement of the communication flow from ci to cj is given by wi j , .

Fig. 1 shows an example of Gcc .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00165v1-figure-03749c41-8bfc-459a-a19f-f1660daf34ad.jpg)

Fig. 1: Gcc of MP3EncMP3Dec encoder application.

In ASNoCs, the switches will be shared among the cores for data communications. If only link failures between the

switches are considered [34], the mapping from the cores to the switches is a many-to-one relationship, which is the same as the clustering problem in the traditional ASNoC synthesis [26] [20]. However, the mapping from cores to switches is a manyto-many relationship if both switch failures and link failures are considered. Let Vs = { si | 1 ≤ ≤ i nsw } be the set of switches. We use the Cartesian products Vc × Vs , Vs × Vc , and Vs × Vs to represent all possible connections from the cores to the switches, from the switches to the cores, and from switches to switches, respectively.

The problem of generalized fault-tolerance topology generation for ASNoCs is defined as follows.

## Problem statement.

Given a core communication graph Gcc , number of switches nsw , floorplan of the cores, and number of tolerable faults K , we attempt to determine the placement of the switches and construct a K -fault-tolerant ASNoC topology with minimization of the power consumption of the ASNoC under the following constraints:

- · the latency constraint l i , j (number of hops) for each communication flow ( ci , cj ) ∈ Ecc ,
- · the switch size constraint max size , which is the maximum number of ports that a switch could support given the NoC operating frequency,
- · and the bandwidth constraint BWmax for the physical links, which is the product of the NoC frequency and bit-width of the physical links.

The ASNoC topology can be represented as a direct graph GNT ( VNT , ENT ) , where VNT = Vc ∪ Vs , and ENT includes two types of edges:

- · a subset of edges Lcs ⊆ Vc × Vs ∪ Vs × Vc determined by solving the core mapping problem, corresponding to the connections between the cores and switches,
- · and a subset of edges Lss ⊆ Vs × Vs determined by solving the routing path allocation problem, corresponding to the physical links between the switches.

In GNT , there are K + 1 switch-disjoint paths for each communication flow ( ci , cj ) in Gcc when both switch failures and link failures are considered.

In the K -fault tolerance structures, K times more switch ports are connected to each core for introducing routing path redundancies. These switch ports greatly increase the area and power consumption of switches. To reduce the number of the switch ports, we also solve a port sharing problem for each switch, which will be discussed in details in Section V.

## III. OVERVIEW OF THE PROPOSED FRAMEWORK

Given the floorplan of ncore cores, their communication requirements represented by Gcc , and the number of switches Nsw , the placement of the switches is determined using the method in [36].

As discussed in Section II-B, the NoC topology generation problem mainly includes two subproblems: core mapping (CM) and routing path allocation (PA). We first map the cores to the switches using a min-cost-max-flow algorithm in Section

IV-A. Second, the routing path allocation is solved using an ILP-based method in Section IV-B. If we fail to find K + 1 switch-disjoint paths for all the communication flows under the given constraints, the number of switches is increased by one and the generalized fault-tolerance topology generation problem is solved again. This procedure is repeated until all the communication flows have K + 1 switch-disjoint routing paths.

To generate the K -fault-tolerant topology, we connect each core to at least K + 1 switches by K + 1 ports, which greatly increases the power and area overheads of the switches. However, for each flow of each core, only one of all the K + 1 ports work for data communication. Consequently, the switch ports connecting different cores could be shared using multiplexers. In Section V, we prove the conditions for port sharing on a switch and propose a clique-partitioning formulation for the problem, which is solved using a heuristic method. Moreover, a heuristic method is proposed to remove the conflicts of routing path selection, caused by port sharing on multiple switches.

Fig.2 illustrates the overall flow of generating fault-tolerance ASNoC topologies.

Fig. 2: Overview of the proposed framework.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00165v1-figure-4367110a-80cd-4772-85a1-959496b29db3.jpg)

## IV. FAULT-TOLERANCE TOPOLOGY GENERATION

## A. Core Mapping

To generate K -fault-tolerant topology, we connect each core to at least K + 1 switches, and many switch ports are introduced for connecting the cores, accordingly. For a switch, the area increases quadratically with the port number, and the power increases superlinearly with the switch size. Consequently, a convex-cost flow based method is used to generate a core mapping with evenly distributed core-switch connections.

In the core mapping stage, we build connections from the source cores of the communication flows to the switches and connections from the switches to the sink cores of the communication flows. Here, we consider building connections from the source cores to the switches. The connections from the switches to the sink cores are built similarly.

To build a convex-cost flow model, we construct a directed graph Gcs ( Vcs , Ecs ) , where Vcs = Vc ∪ Vs ∪ { b t , } and Ecs = Vc × Vs ∪{ Vs → }∪{ t b → Vc } .

The capacity of an edge ( b ci , ) ∈ { b → Vc } is set to K + 1 if there is an outgoing communication flow from ci and is set to 0 otherwise. The capacities of the edges in { Vs → } t are set to Ncs = /floorleft ncore ∗ ( K + ) 1 / nsw /floorright + 1, which is close to the average number of input ports that is used to connect cores on a switch. All the other edges have a capacity of 1.

The edges in { b → Vc } have zero cost. we can map on one switch; For an edge ( ci , s j ) ∈ Vc × Vs , the cost is defined as Ebit × Dci s j , × ∑ k : ( ci , c k ) ∈ Ecc wi k , , where Dci s j , is the distance between core ci and switch s j and Ebit (set to 0.5 in this work) is the bit energy of unit wire length (1 mm ).

To make the connections from cores to switches evenly distributed among the switches, the costs of the edges in { Vs → } t are defined to be a function of the number of flows x on the edges c ( s j , t ) ( x ) , which corresponds to a piecewise linear and convex function for the flow costs. Let 0 = d 0 ≤ d 1 ≤··· ≤ dNcs denote the breakpoints of the piecewise function and the costs vary linearly in the interval [ di -1 , di ] , 1 ≤ ≤ i Ncs . In this work, the edge cost function cs j , t ( x ) = 10 x and the interval between adjacent breakpoints is set to 1. Consequently, the flow cost is calculated as 10 x 2 . Such a convex-cost flow problem can be easily transformed into a traditional min-cost flow problem [37].

According to the solution to the convex cost flow model, the edges in Vc × Vs that have non-zero flow will be selected as the connections from cores to switches.

After we map the cores to switches, we have determined the connections between the cores and the switches, denoted as Lcs ( ⊆ Vc × Vs ∪ Vs × Vc ). Hereafter, for a communication flow ( ci , cj ) in Gcc , we define the switch ports connected to the source core ci as core inports and the switch ports connected to the sink core cj as core outports .

An example of core mapping for Gcc in Fig.1 is shown in Fig.3, where K = 1. Each source core is connected to multiple core inports and multiple core outports respectively through a demultiplexer (DEMUX) and a multiplexer (MUX).

## B. ILP based Path Allocation

To generate K -fault tolerant topologies, we have to find K + 1 alternative switch-disjoint ( node-disjoint ) routing paths in a complete graph of switches Gs Vs ( , Vs × Vs ) for each communication flow considering the costs of switches and links. To reduce the internally node-disjoint paths problem to an edge-disjoint paths problem [38], which is easily formulated as a constrained min-cost multi-flow problem, we perform node splitting on Gs and extend the graph for routing path allocation. Each switch node u ∈ Vs is split into two nodes u and u ′ . A directed graph Gpa Vpa ( , Epa ) is constructed as follows.

- · Vpa = Vc ∪ Vs ∪ V s ′ , where V s ′ is the split node set of Vs .
- · Epa = Lcs ∪ Esplit ∪ Elink , where Esplit = { ( u u , ′ ) | u ∈ Vs ∧ u ′ is the corresponding split node of u } and Elink = ( { u ′ , v ) ( | u v , ) ∈ Vs × Vs ∧ u ′ is the corresponding split node of u } . If there is a directed edge from u to v in Vs × Vs , a corresponding directed edge from u ′ to v is added in Epa .

In the following, we discuss how to find K + 1 edge-disjoint routing paths in Gpa for all the communication flows.

1) Computation of Switch Power and link power: The switch power depends on the switch size, which includes the number of input ports and output ports. To calculate the size of switches, we introduce two types of binary variables xuv i , j , k and duv . xuv i , j , k = 1 indicates that the ( k + ) 1 -th routing path of the communication flow ( i , j ) goes through the edge ( u v , ) ∈ Epa , 0 ≤ k ≤ K ; otherwise, xuv i , j , k = 0. duv = 1 indicates that there is at least one communication flow going through the edge ( u v , ) ∈ Epa , and accordingly a physical link exists between the switches u and v ; otherwise, duv = 0. duv is calculated based on binary variables xuv i , j , k as follows [39].

$$d _ { u v } = m i n \{ \sum _ { ( i, j ) \in E _ { c c } } \sum _ { k = 0 } ^ { K } x _ { u v } ^ { i, j, k }, 1 \}, \forall ( u, v ) \in E _ { l$$

Then, the size of a switch u , including the input port number ipu and output port number opu , can be calculated as follows.

$$\text{work}, \quad i p _ { u } = \sum _ { v \colon ( v, u ) \in E _ { l i n k } } d _ { v u } + c i p _ { u } ; \ o p _ { u } = \sum _ { v \colon ( v, u )$$

cipu and copu respectively represent the number of core inport s and core outport s, which have been determined in the core mapping stage. Consequently, the power consumption of the switches are estimated using Orion 3.0 [40] as follows [29].

$$P _ { s w } ( i p _ { u }, o p _ { u } ) = T _ { s w } [ i p _ { u } ] + C _ { s w } * o p _ { u } \text{ \quad \ \ } ( 3 )$$

where Tsw is a table mapping the input port number to power consumption, and Csw is a constant.

The link power of a communication flow ( i , j ) on an edge ( u v , ) ∈ Elink is determined by the communication requirement wi j , and the physical distance between u and v , Du v , . Considering the cost of opening new physical links, an extra cost Cpl is introduced if the physical link between u and v does not exist. Therefore, the link power Psw ( i , j , u v , ) is calculated as follows [41].

$$\mu _ { \sigma ^ { \dots } } \, \cdot \, \\ P _ { l i n k } = \sum _ { ( u, v ) \in E _ { l i n k } ( i, j ) \in E _ { c c } } \sum _ { ( E _ { b i t$$

where Ebit represents the bit energy of the electrical link.

2) ILP Formulation for Routing Path Allocation: To simplify the discussion, the communication flows in Gcc are relabeled as ( i , j ) = ( ci , cj ) ∈ Ecc (Definition 1). The routing path allocation for ASNoCs with K -fault tolerance can be formulated as a constrained multiple flow problem Gpa as follows.

$$\underset { \text{and} } { \text{ispum} } \quad M i n \sum _ { u \in V _ { s } } P _ { s w } ( i p _ { u }, o p _ { u } ) + P _ { l i n k } \quad \quad \quad$$

$$& G _ { s } \\ & \text{itch} \\ & \quad s. t. \sum _ { v ; ( u, v ) \in E _ { p a } } x _ { u v } ^ { i, j, k } - \sum _ { v ; ( v, u ) \in E _ { p a } } x _ { v u } ^ { i, j, k } = \begin{cases} 1, & \text{if $u=c_{i}$;} \\ 0, & \text{if $u\in V_{s}$;} \\ - 1. & \text{if $u=c_{j}$;} \end{cases} \\. & \quad \forall \ k \in [ 0, K ], \forall \ ( i, j ) \in E _ { c c }, & \quad ( 5 a ) \\ \iota \in \quad & \stackrel { K } { \mathcal { N } }. _ { i, j, k } \times 1 \ \cup \dots \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \colon \end{cases}$$

$$\sum _ { k = 0 } ^ { K } x _ { u u ^ { \prime } } ^ { i, j, k } \leq \sum _ { \substack { \colon \\ \longrightarrow \colon \colon \colon } } 1, \forall ( u, u ^ { \prime } ) \in E _ { s p l i t }, \forall \ ( i, j ) \in E _ { c c }, \quad \ \ ( 5 b )$$

$$\stackrel { \ddot { \cdot } } { \sum _ { ( u, u ^ { \prime } ) \in E _ { s p l i t } } } x _ { u u ^ { \prime } } ^ { i, j, k } \leq l _ { i, j }, \forall \ k \in [ 0, K ], \forall \ ( i, j ) \in E _ { c c }, \quad ( 5 c )$$

$$\sum _ { ( i, j ) \in E _ { c c } } \sum _ { k = 0 } ^ { K } w _ { i, j } * x _ { u v } ^ { i, j, k } \leq B W _ { m a x }, \forall ( u, v ) \in E _ { l i n k }, \quad ( 5 d )$$

$$i p _ { u } \leq m a x _ { - } s i z e, \ \ o p _ { u } \leq m a x _ { - } s i z e, \ \ \ \ \ ( 5 e )$$

$$x _ { u v } ^ { i, j, k } \in \{ 0, 1 \}, k \in [ 0, K ], \forall ( u, v ) \in E _ { p a }, \forall ( i, j ) \in E _ { c c }. \ \ ( 5 f )$$

In the formulation above, the set of constraints (5a) defines K + 1 unit flows (paths) for each communication flow. The constraint (5b) ensures that the K + 1 paths of any communication flow ( i , j ) are edge-disjoint. The constraints (5c) ensure that the latency constraint is satisfied for all K + 1 routing paths of each communication flow. The set of constraints (5d) represents the limited bandwidth of physical links and the set of constraints (5e) denotes the maximum port number for each switch.

The objective (5) is to minimize the total power consumption of switches and the total link power consumption of the default routing paths (k=0) for all communication flows.

The required runtime is unacceptable when directly solving the above large-scale ILP problem. To reduce the runtime of routing path allocation, we process the communication flows one by one in descending order of bandwidth requirements, which cause sub-optimal solutions but greatly reduce the runtime. Additionally, before processing each communication flow, the switch size constraint and the bandwidth constraint can be preprocessed by removing, from the graph Gpa , the vertices corresponding to the switches that have a maximum size and the edges corresponding to the links that have no enough bandwidth. Therefore, the ILP formulation for the routing path allocation of a single communication flow ( i , j ) ∈ Ecc is simplified as follows.

$$M i n \sum _ { u \in V _ { s } } P _ { s w } ( i p _ { u }, o p _ { u } ) + \sum _ { ( u, v ) \in E _ { l i n k } } P _ { l k } ( i, j, u, v )$$

$$\text{s.t.}$$

$$\sum _ { v \colon ( u, v ) \in E _ { p a } } & x _ { u v } ^ { i, j, k } - \sum _ { v \colon ( v, u ) \in E _ { p a } } x _ { v u } ^ { i, j, k } = \begin{cases} \begin{array} { c } 1, & \text{if $u=c_{i}$;} \\ 0, & \text{if $u\in V_{s}$;} \\ - 1. & \text{if $u=c_{j}$;} \end{array} \\ & \forall \ k \in [ 0, K ], & \quad & ( 6 b ) \\ & \sum _ { u u ^ { \prime } } & x _ { u u ^ { \prime } } ^ { i, j, k } \leq l _ { i, j }, \forall \ k \in [ 0, K ], & & ( 6 c ) \end{cases}$$

$$\sum _ { ( u, u ^ { \prime } ) \in E _ { s p l i t } } x _ { u u ^ { \prime } } ^ { i, j, k } \leq l _ { i, j }, \stackrel { \mu } { \forall } \stackrel { \mu } { k } \in [ 0, K ], & & ( 6 c ) & & \text{In a}$$

$$x _ { u v } ^ { i, j, k } \in \{ 0, 1 \}, k \in [ 0, K ], \forall ( u, v ) \in E _ { p a }, \quad \ \ ( 6 d ) \stackrel { \mathfrak { m } a } { K + 1 } \stackrel { \mathfrak { m } a } { c }$$

where the cost of links Plk ( i , j , u v , ) can be simply defined as follows.

$$P _ { l k } ( i, j, u, v ) = \begin{cases} E _ { b i t } \times w _ { i, j } \times D _ { u, v }, \ i f \ p h y s i c a l \ l i n k \ ( u, v ) \ e x i s t s ; & \sin \max \\ E _ { b i t } \times w _ { i, j } \times D _ { u, v } + C _ { p l }, \ o t h e r w i s e, & \text{switch si} \\ \text{(7)} \text{ \ \ switch} \, b \end{cases}$$

(7)

3) An example: As mentioned above, we solve an ILP model for each communication flow ( ci , cj ) in Gcc . As shown in Fig.3, we first allocate the routing paths of the communication flow ( c 3 , c 0 ) and, a physical link from switch s 2 to s 0 is added, where the default path includes only one switch s 3 and the alternative path is from s 2 to s 0; After we allocate routing paths for another communication flow ( c 4 , c 3 ) , a physical link from switch s 1 to s 3 is added, where the default path includes only one switch s 2 and the alternative path is from s 1 to s 3. Fig.3 shows the final network topology with one-fault tolerance, and the routing paths for all communication flows are shown in Table I.

TABLE I: Routing Paths for One-Fault Tolerance

| Flows       | Default Path   | Alternative Path   |
|-------------|----------------|--------------------|
| c 1 → c 0   | s 0 → s 0      | s 3 → s 3          |
| c 2 → c 1   | s 0 → s 0      | s 3 → s 3          |
| c 3 → c 0   | s 3 → s 3      | s 2 → s 0          |
| c 4 → c 3   | s 2 → s 2      | s 1 → s 3          |
| c 7 → c 5   | s 0 → s 0      | s 1 → s 1          |
| c 7 → c 6   | s 0 → s 0      | s 1 → s 3          |
| c 8 → c 7   | s 1 → s 0      | s 2 → s 3          |
| c 9 → c 8   | s 1 → s 1      | s 0 → s 2          |
| c 10 → c 9  | s 1 → s 1      | s 2 → s 2          |
| c 11 → c 8  | s 1 → s 1      | s 2 → s 2          |
| c 12 → c 4  | s 2 → s 2      | s 3 → s 1          |
| c 12 → c 10 | s 2 → s 2      | s 3 → s 0 → s 1    |
| c 12 → c 11 | s 2 → s 2      | s 3 → s 1          |

Fig. 3: Final Network Topology.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00165v1-figure-b454f6c0-5903-4eea-96b6-0fffb2449ef3.jpg)

## V. SWITCH PORT SHARING

In a K -fault tolerance structure, K + 1 core inports or/and K + 1 core outports are required for each core on no less than K + 1 switches, which greatly increase the area and power consumption of switches. Many switch ports are not used simultaneously because only one out of K + 1 routing paths is used for each communication flow at a time. To reduce the switch size, we propose the sharing of switch ports (on the same switch) between the routing paths from different communication flows, using multiplexers. Given the routing path allocation of communication flows, we prove a sufficient and necessary condition for the port sharing on a switch, and formulated the problem into a clique partitioning problem.

The port sharing aims at the sharing of core inport s/ core outport s on the same switch. In this section, we first propose a twostage method to solve the core inport sharing problem, which is also applicable to core outport sharing. Second, we proposed a method to remove the conflicts caused by port sharing on multiple switches. Finally, an independent set based formulation is proposed for selecting routing paths for communication flows.

GLYPH&lt;1&gt;GLYPH&lt;2&gt;GLYPH&lt;3&gt;GLYPH&lt;4&gt;GLYPH&lt;5&gt;GLYPH&lt;6&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;9&gt;GLYPH&lt;5&gt;

GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;6&gt;GLYPH&lt;7&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;6&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;6&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;16&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;16&gt;

GLYPH&lt;1&gt;GLYPH&lt;2&gt;GLYPH&lt;3&gt;GLYPH&lt;4&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;15&gt;GLYPH&lt;5&gt;

GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;9&gt;GLYPH&lt;7&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;6&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;6&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;16&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;16&gt;

GLYPH&lt;1&gt;GLYPH&lt;2&gt;GLYPH&lt;3&gt;GLYPH&lt;4&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;16&gt;GLYPH&lt;5&gt;

GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;6&gt;GLYPH&lt;7&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;6&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;16&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;16&gt;

GLYPH&lt;1&gt;GLYPH&lt;2&gt;GLYPH&lt;3&gt;GLYPH&lt;4&gt;GLYPH&lt;5&gt;GLYPH&lt;16&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;17&gt;GLYPH&lt;5&gt;

GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;16&gt;GLYPH&lt;7&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;16&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;

GLYPH&lt;1&gt;GLYPH&lt;2&gt;GLYPH&lt;3&gt;GLYPH&lt;4&gt;GLYPH&lt;5&gt;GLYPH&lt;17&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;18&gt;GLYPH&lt;5&gt;

GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;19&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;6&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;6&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;

GLYPH&lt;1&gt;GLYPH&lt;2&gt;GLYPH&lt;3&gt;GLYPH&lt;4&gt;GLYPH&lt;5&gt;GLYPH&lt;19&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;18&gt;GLYPH&lt;5&gt;

GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;20&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;6&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;6&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;16&gt;

GLYPH&lt;1&gt;GLYPH&lt;2&gt;GLYPH&lt;3&gt;GLYPH&lt;4&gt;GLYPH&lt;5&gt;GLYPH&lt;20&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;21&gt;GLYPH&lt;5&gt;

GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;18&gt;GLYPH&lt;7&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;6&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;16&gt;

GLYPH&lt;1&gt;GLYPH&lt;2&gt;GLYPH&lt;3&gt;GLYPH&lt;4&gt;GLYPH&lt;5&gt;GLYPH&lt;18&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;22&gt;GLYPH&lt;5&gt;

GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;21&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;6&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;

GLYPH&lt;1&gt;GLYPH&lt;2&gt;GLYPH&lt;3&gt;GLYPH&lt;4&gt;GLYPH&lt;5&gt;GLYPH&lt;21&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;9&gt;GLYPH&lt;6&gt;GLYPH&lt;5&gt;

GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;22&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;

GLYPH&lt;1&gt;GLYPH&lt;2&gt;GLYPH&lt;3&gt;GLYPH&lt;4&gt;GLYPH&lt;5&gt;GLYPH&lt;22&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;9&gt;GLYPH&lt;9&gt;GLYPH&lt;5&gt;

GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;21&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;

GLYPH&lt;1&gt;GLYPH&lt;2&gt;GLYPH&lt;3&gt;GLYPH&lt;4&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;6&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;9&gt;GLYPH&lt;15&gt;GLYPH&lt;5&gt;

GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;17&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;16&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;

GLYPH&lt;1&gt;GLYPH&lt;2&gt;GLYPH&lt;3&gt;GLYPH&lt;4&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;9&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;9&gt;GLYPH&lt;15&gt;GLYPH&lt;5&gt;

GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;9&gt;GLYPH&lt;6&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt;GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;16&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;6&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;

GLYPH&lt;1&gt;GLYPH&lt;2&gt;GLYPH&lt;3&gt;GLYPH&lt;4&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;15&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;9&gt;GLYPH&lt;15&gt;GLYPH&lt;5&gt;

GLYPH&lt;5&gt;GLYPH&lt;8&gt;GLYPH&lt;9&gt;GLYPH&lt;9&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;

GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;5&gt;GLYPH&lt;10&gt; GLYPH&lt;11&gt; GLYPH&lt;12&gt;GLYPH&lt;13&gt;GLYPH&lt;5&gt;GLYPH&lt;15&gt;GLYPH&lt;7&gt;GLYPH&lt;5&gt;GLYPH&lt;16&gt;GLYPH&lt;14&gt;GLYPH&lt;5&gt;GLYPH&lt;9&gt;

## A. Conditions for Port Sharing on a Switch

In this subsection, given a network topology with K -faulttolerance and the corresponding routing path allocation, we derive the conditions for port sharing on one switch only. For clarity, the conditions for the inport sharing in one-faulttolerance and K -fault-tolerance are respectively discussed in Section V-A1 and Section V-A3.

1) Port Sharing in One-Fault-Tolerance Topologies: Suppose there are two core inports, IP 1 and IP 2, on a switch sn , and two communication flows, f 1 and f 2 which are shown on the Fig.4(a). f 1 has two routing paths, p f 1 1 and p f 1 2 , and p f 1 1 goes through IP 1. f 2 has two routing paths, p f 2 1 and p f 2 2 , and p f 2 1 goes through IP 2. Fig.4(b) illustrates port sharing.

Fig. 4: (a)Two independent core inports. (b) Port sharing.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00165v1-figure-02de26d5-6ade-433c-97c0-aea7a03430f8.jpg)

Lemma 1: The two inports on sn , IP 1 and IP 2 respectively used by p f 1 1 and p f 2 1 , can be merged into a single port without violating the property of one-fault tolerance if and only if p f 1 2 and p f 2 2 are vertex-disjoint.

ONLY IF. We show that if p f 1 2 and p f 2 2 are not vertex-disjoint, merging IP 1 and IP 2 will violate the one-fault tolerance. p f 1 2 and p f 2 2 must go through one common switch vertex if they are not vertex-disjoint. Consequently, if the common switch is faulty then f 1 and f 2 have to use p f 1 1 and p f 2 1 for communication, which causes conflict use of core inports. Proof END .

Proof. IF. In the case that p f 1 2 and p f 2 2 are vertex-disjoint, after IP 1 and IP 2 are merged into a single port the routing paths for f 1 and f 2 can always be found when one fault occurs. Because p f 1 2 and p f 2 2 cannot go through sn , the one fault could be on sn , p f 1 2 , or p f 2 2 . If the fault is on switch sn , f 1 and f 2 can use p f 1 2 and p f 2 2 for communication, respectively. If the fault is on p f 1 2 (or p f 2 2 ), f 1 and f 2 can respectively use p f 1 1 and p f 2 2 (or p f 1 2 and p f 2 1 ) for communication. It is concluded that p f 1 1 and p f 2 1 , respectively going through IP 1 and IP 2, are not used simultaneously while the topology keeps the property of one-fault tolerance.

Fig.5 shows the intersection relations between the routing paths of the communication flows f 1 and f 2, which causes core inport conflict if IP 1 and IP 2 are merged and one fault occurs in the intersection point of routing paths p f 1 2 and p f 2 2 .

2) Port Sharing in Multiple-Fault Tolerance Topologies: In this subsection, we give a generalized sufficient and necessary condition for port sharing in K -fault-tolerant ( K ≥ 1) structures.

Suppose there are two core inports, IP 1 and IP 2, on a switch sn , and two communication flows, f 1 and f 2. f 1 has K + 1 vertex-disjoint routing paths, p f 1 0 , p f 1 1 , · · · , p K f 1 , of which p f 1 0 goes through IP 1. f 2 has K + 1 vertex-disjoint routing paths, p f 2 0 , p f 2 1 , · · · , p K f 2 , of which p f 2 0 goes through IP 2.

Fig. 5: The intersection relation violates the one-fault tolerance considering the routing paths of f 1 and f 2.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00165v1-figure-77bd0e97-ef32-4d17-ae9c-3647f77f99a2.jpg)

We construct a bipartite graph, IG V E ( , ) , to represent the intersection relations between the routing paths of f 1 and f 2 as follows.

The vertex set includes all the routing paths of f 1 and f 2 except for p f 1 0 and p f 2 0 . Let Pf 1 = { p i f 1 , i = 1 , · · · , K } and Pf 2 = { p i f 2 , i = 1 , · · · , K } . VIG = Pf 1 ∪ Pf 2 . Further, if two routing paths from Pf 1 and Pf 2 have a common vertex, there is an edge in EIG . That is, EIG = { ( p i f 1 , p j f 2 ) | p i f 1 ∈ Pf 1 p j f 2 ∈ Pf 2 and they have a common vertex . } . It is obvious that IG V E ( , ) is a bipartite graph. Let C IG ( ) be the maximum cardinality matching in IG V E ( , ) . Then, we have the following conclusion.

Theorem 1: The two core inports on sn , IP 1 and IP 2, respectively used by p f 1 0 of f 1 and p f 2 0 of f 2, can be merged into a single port (port sharing) without violating the property of K -fault tolerance if and only if C IG ( ) &lt; K .

Proof. IF. We show that if C IG ( ) &lt; K the merging of IP 1 and IP 2 will not violate the K -fault tolerance. Note that the routing paths from Pf 1 (or Pf 2 ) are vertex-disjoint (except for the source and sink core vertices). One fault causes at most two faulty paths, of which one path is from Pf 1 and the other is from Pf 2 and they have a common vertex. We have two situations considering p f 1 0 and p f 2 0 .

(1). p f 1 0 and p f 2 0 are correct but only one of them can be used since they share one core inport. Let K 1 and K 2 respectively be the number of faulty paths in Pf 1 and Pf 2 . Without loss of generality, we suppose K 1 ≥ K 2. When K 1 &lt; K , there must be at least a correct routing path in both Pf 1 and Pf 2 and, hence, K faults are tolerant. When K 1 = K , we can conclude that K 2 &lt; K . Because K 2 = K 1 = K indicates that C IG ( ) = K , which contradicts C IG ( ) &lt; K . Accordingly, we have at least a correct path in Pf 2 for communication flow f 2 and p f 1 0 can be used for f 1. Consequently, the network topology maintains K -fault tolerance.

(2). p f 1 0 and p f 2 0 are faulty when sn is faulty. In this case, the paths in Pf 1 and Pf 2 are able to construct a K -1 faulttolerance structure since the given topology is K -fault tolerant. Consequently, the network topology also keeps K -fault tolerance.

ONLY IF. We show that if C IG ( ) = K , then merging IP 1 and IP 2 will violate the K -fault tolerance. There will be perfect matching in IG V E ( , ) if C IG ( ) = K . In the perfect matching, each edge corresponds to an intersection of two routing paths from Pf 1 and Pf 2 . All 2 K paths in Pf 1 and Pf 2 are faulty when K faults exactly occur on K intersected vertices. Consequently, p f 1 0 and p f 2 0 are respectively the only available routing path for

f 1 and f 2, which cause a conflicting use of merged core inports if we merge IP 1 and IP 2. Proof END .

Fig. 6: The intersection relation violates the 2-fault tolerance considering the routing paths of f 1 and f 2 where p f 1 1 intersects p f 2 1 at router sn .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00165v1-figure-2afc355a-427c-446e-a212-b61975ae3a82.jpg)

Further, Fig.6 shows the intersection relation violates the 2fault tolerance considering the routing paths of f 1 and f 2 where p f 1 1 intersects p f 2 1 at router sn .

3) Inport with Multiple Communication Flows: For each core inport, there may be one or one more outgoing communication requirements. Accordingly, there may be one or multiple paths going through one core inport.

Suppose there are two core inports, IP 1 and IP 2, on a switch sn and there are respectively m and n communication flows going through IP 1 and IP 2, as shown in Fig.7.

Fig. 7: Multiple paths of the inports.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00165v1-figure-8797b84d-2286-4da7-819a-d02489e0eb10.jpg)

Corollary 1: The two inports IP 1 and IP 2 can be merged if and only if all the m × n pairs of communication flows satisfy Theorem 1.

4) Multiple Port Sharing: Suppose there are J core inports, IP 1 , IP 2 , · · · , IPJ , on a switch sn , and J communication flows, f 1 , f 2 , · · · , f J . f i , i = 1 , · · · , J , has K + 1 vertex-disjoint routing paths, p f i 0 , p f i 1 , · · · , p K f i , of which p f i 0 goes through IPi .

/negationslash

Proof. Let Pf j = { p k f j , k = 1 , · · · , K } be the set of vertex-disjoint routing paths of f j except for p f j 0 . Similarly, we have two situations considering p f i 0 , i = 1 , · · · , J .

Theorem 2: The J core inports on sn , IPj , j = 1 , · · · , J , respectively used by J communication flows, f 1 , f 2 , · · · , f J , can be merged into a single inport without violating the property of K -fault tolerance if the merging relations between J inports form a clique, which indicates that, for all pairs of ( IPi , IPj ) , i = j , and 1 ≤ i , j ≤ J , IPi and IPj can be merged according to Theorem 1.

(1). p f j 0 , j = 1 , · · · , J are correct but only one of them can be used since they share one core inport. Let Kj , j = 1 , · · · , J , respectively be the number of faulty paths in Pf j . Without loss of generality, we suppose that Kj ≥ Kj + 1 , j = 1 , · · · , J -1. When K 1 &lt; K , there must be at least a correct routing path in Pf j , j = 1 , · · · , J , and, hence, K -faults are tolerant. When K 1 = K , we can conclude that Kj &lt; K j , = 2 , · · · , J . This is because Kj = K 1 = K indicates that there will be perfect matching considering the intersection relations between the K paths from Pf 1 and K paths from Pf j and, hence, IP 1 and IPj cannot be merged according to Theorem 1, which is a contradiction. Accordingly, we have at least a correct path in Pf j for communication flow f j , j = 2 , · · · , J and p f 1 0 can be used for f 1. Consequently, the network topology maintains K -fault tolerance.

(2). p f j 0 , j = 1 , · · · , J are faulty when sn is faulty. In this case, the paths in Pf j , j = 1 , · · · , K , are able to construct a K -1 fault-tolerance structure since the given topology is K -fault tolerant. Consequently, the network topology also maintains K -fault tolerance. Proof

## END .

Suppose there are J core inports, IP 1 , IP 2 , · · · , IPJ , on a switch sn , and there are mi communication flows going through IPi , i = 1 , · · · , J .

Corollary 2: The J core inports on sn , IPj , j = 1 , · · · , J , respectively used by mj , j = 1 , · · · , J , communication flows, can be merged into a single inport without violating the property if all the ∏ J i = 1 mi combinations of communication flows satisfy Theorem 2.

Based on the above theorem and corollaries, we conclude the following theorem.

Theorem 3: The J core inports on sn , IPj , j = 1 , · · · , J , respectively used by mj , j = 1 , · · · , J , communication flows, can be merged into a single inport without violating the property of K -fault tolerance if the merging relations between J inports form a clique.

## B. Clique Partitioning for Port Sharing on a switch

Given a network topology and all routing paths for K -faulttolerance, we formulate the port sharing problem on a switch as a clique partitioning problem, where the clique number is minimized to reduce the switch size, according to Theorem 3.

For a switch, a graph Gps ( Vps , Eps ) is constructed to represent the possible sharing relations between the core inports. The vertex set Vps = { IPi , i = 0 , · · · , N } represents the set of core inports. An edge, ( IPi , IPj ) , is added to Eps if IPi and IPj can be shared with each other according to Corollary 1. Fig.8 shows an example of Gps and its two clique-partitioning. The solid edges are the clique edges. In Fig.8.(a), two inports are required, respectively corresponding to a 2-vertex clique and 3-vertex clique. In Fig.8.(b), three inports are required, respectively corresponding to two 2-vertex cliques and one 1-vertex clique.

Because the clique partitioning problem is an NP-hard problem, we propose a heuristic to find the clique partitioning of Gps . Algorithm 1 shows the key steps of the heuristic for port sharing. Firstly, we find a maximum clique QVq Eq , in Gps using an ILP based method [42]. If | Vq | is greater than 2,

Fig. 8: An example of Gps .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00165v1-figure-34009cb8-b8f5-4075-99b0-8eede8aad74d.jpg)

we merge the inports in Vq into a single port and remove QVq Eq , from Gps to update a new Gps . The operation of finding the maximum clique is repeated until | Vq | ≤ 2, where the clique partitioning problem can be solved by finding maximum cardinality matching. Secondly, we find maximum cardinality matching in the rest of Gps , where the edges in the maximum cardinality matching correspond to two-port sharing.

## Algorithm 1 PS on a switch (sn)

Require: fault tolerant paths of communication requirements Ensure: results of port sharing within a switch

Construct a possible port-sharing graph Gps for sn ;

for each pair of inports(or outports) ( IPi , IPj ) on sn do

for each path p f i m 1 through IPi do

for each path p f j n 1 through IPj do

Construct a bipartite graph IG ;

Calculate C IG ( ) of IG ;

if

C IG

(

)

&gt;

=

K

then

goto cont;

end if

end for

## end for

Add an edge ( IPi , IPj ) to Egs ;

cont: Continue;

## end for

## repeat

Find a maximum clique Q Vq ( , Eq ) in Gps and the IPs denoted by Vq share a single port;

Remove Q Vq ( , Eq ) from Gps ;

until | Vq | ≤ 2

Find maximum cardinality matching on Gps ;

## C. Port Sharing on Multiple Switches

The conditions in Section V-A ensure the fault tolerance when port sharing is considered on one switch only. However, port sharing on multiple switches perhaps causes conflicts of routing path selection. In this section, we present a method for removing some port sharing to maintain the fault tolerance when port sharing on all switches are considered.

To select routing paths for communication flows, we can construct a graph Gpc ( Vpc , Epc ) to represent the conflict relations between routing paths and solving an independent set problem on Gpc . Let p k i , j be the k -th routing path of communication flow ( i , j ) . Vpc = { p k i , j | ( i , j ) ∈ Ecc , 0 ≤ k ≤ K } represent the routing paths of all communication flows. Epc includes two types of edges. One represents

/negationslash

/negationslash two routing paths from the same communication flow and the other represents port-sharing relations between two routing paths. Epc = { ( p k 1 ( i , j ) , p k 2 ( i , j ) ) | 0 ≤ k 1 , k 2 ≤ K and k 1 = k 2 } ∪ { ( p k 1 ( i 1 , j 1 ) , p k 2 ( i 2 , j 2 ) ) | ( i 1 , j 1 ) = ( i 2 , j 2 ) , 0 ≤ k 1 , k 2 ≤ K , and p k 1 ( i 1 , j 1 ) and p k 2 ( i 2 , j 2 ) go through a common core inport or core outport } .

The selection of routing paths can be achieved by finding a maximum independent set of Gpc , denoted as IND Gpc ( ) . If there is no port sharing, that is, there is no second type of edges in Epc , we may choose any correct routing path for each communication flow, and, hence | IND Gpc ( ) | = | Ecc | . If port sharing is considered on one switch only, the conditions in Section V-A ensure | IND Gpc ( ) | = | Ecc | for any K switch faults. However, | IND Gpc ( ) | &lt; | Ecc | could happen if we have two or more switches with shared core inports/outports , that is, we cannot find enough routing paths for the communication flows.

Fig.9 shows an example. We have three communication flows f 1, f 2, and f 3 ( | Ecc | = 3), and each flow has two switch-disjoint routing paths, p f i 1 and p f i 2 , for one-fault tolerance. As shown in the figure, the routing paths have two shared ports respectively on the switches Sm and Sn , and p f 1 2 and p f 3 2 go through a common switch Sl . The corresponding Gpc is also shown in the figure. When sl is broken, we have four correct paths after removing p f 1 2 and p f 3 2 . Obviously, | IND Gpc ( ) | = 2 &lt; 3 = | Ecc | , which cause that one flow has no routing paths. The conflict can be solved by removing the port sharing on any switch.

Fig. 9: Example for the conflicts of routing paths with port sharing on two switches.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00165v1-figure-33e9bc93-c556-4946-9b23-3d7fca4e89d5.jpg)

Here, we propose a heuristic to deal with conflicts of port sharing for all the switches. Let Vf be the set of faulty routers. Algorithm 2 shows the key steps.

In Algorithm 2, we first generate the core inport/outport sharing for each switch by calling Algorithm 1. Second, for each subset of possible K faulty switches, the fault-tolerance is verified by solving a maximum independent set problem, where | IND Gpc ( ) | is computed by solving an ILP-based formulation. When | IND Gpc ( ) | &lt; | Ecc | , a port-sharing edge is considered to be removed for increasing the size of maximum independent set. Basically, we consider removal of a port-sharing edge between core outport s while keeping the sharing edges between core inport s as many as possible, because an input port generally has a flit buffer with large area costs and power overhead.

Fig.10 shows the port sharing of the network topology in Fig. 3; the corresponding Gcc in Fig.1. Fig.11 shows the graph Gpc corresponding to Fig.10. When the switch s 0 is broken down, Table II shows the available routing paths, where the faulty paths

## Algorithm 2 PS on multiple switches

Require: fault tolerant paths of communication requirements

Ensure: results of port sharing for each switch sn in Vs do

Call PS on a switch(sn) to generate core inport sharing; Call PS on a switch(sn) to generate core outport sharing;

## end for

Construct a conflict relation graph Gpc between routing paths; for each subset of switches Vf ⊂ Vs and | Vf | = K do

Temporarily remove from Gpc the routing paths going through any switch si ∈ Vf ;

Find a maximum independent set of Gpc ;

if | IND Gpc ( ) | = | Ecc | then continue;

end if

## repeat

Choose a communication flow ( i , j ) having no routing path in IND Gpc ( ) ;

Permanently remove one of the port-sharing edges related to ( i , j ) .

Find a maximum independent set of Gpc ;

until | IND Gpc ( ) | = | Ecc |

Restore Gpc , except for the permanently removed edge; end for

Fig. 10: Result of Port Sharing.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00165v1-figure-bac12e8e-0b9f-4c02-afd1-4a4a75808807.jpg)

TABLE II: Communication paths for one-switch-fault tolerance with s 0 broken down

| Flows       | Default Path   | Alternative Path   |
|-------------|----------------|--------------------|
| c 1 → c 0   | s 0 → s 0      | s 3 → s 3          |
| c 2 → c 1   | s 0 → s 0      | s 3 → s 3          |
| c 3 → c 0   | s 3 → s 3      | s 2 → s 0          |
| c 4 → c 3   | s 2 → s 2      | s 1 → s 3 [c]      |
| c 7 → c 5   | s 0 → s 0      | s 1 → s 1          |
| c 7 → c 6   | s 0 → s 0      | s 1 → s 3          |
| c 8 → c 7   | s 1 → s 0      | s 2 → s 3          |
| c 9 → c 8   | s 1 → s 1      | s 0 → s 2          |
| c 10 → c 9  | s 1 → s 1      | s 2 → s 2          |
| c 11 → c 8  | s 1 → s 1      | s 2 → s 2          |
| c 12 → c 4  | s 2 → s 2      | s 3 → s 1 [c]      |
| c 12 → c 10 | s 2 → s 2      | s 3 → s 0 → s 1    |
| c 12 → c 11 | s 2 → s 2      | s 3 → s 1 [c]      |

Fig. 11: Gpc for selecting routing paths in Fig.10.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00165v1-figure-004fea18-8913-4786-b8f0-a85a37ed79f2.jpg)

are displayed in gray color and the conflict paths are displayed in gray color and marked using c .

## D. Selecting Routing Paths after Port Sharing

The selection of routing paths can be achieved by finding an | Ecc | -size independent set of Gpc . If link faults or switch faults occur, we can just remove the routing paths that go through the faulty links and the faulty switches from Gpc and find a new set of routing paths for all the communication flows by solving an | Ecc | -size independent set problem on Gpc and update the routing tables of the core communications.

## E. Cost Analysis for Multiplexers and Demutiplexers

To develop a fault-tolerance topology, we introduce demultiplexers ( DEMUX ) and multiplexers ( MUX ) for the source cores and the sink cores, respectively, of the communications flows. The routing paths can be selected by sending to the DEMUX s and MUX s control signals.

Because we assume source-routing strategy, where the routing paths are stored in a routing table in the source core side of the communication flow. Each digit of the routing information is used in turn to select the output port at each step of the route, as if the address itself was the routing header determined from a source-routing table [35]. Hence, for a demultiplexer with the input from a core (for example, the DEMUX connected to c 7 in Fig.10), the control signals can be from the routing bits, and for a demultiplexer with the input from a switch (for example, the DEMUX connected to switch 1 in Fig.10), the control signals can also be generated by the switch according to the routing digit in the head flit of packet. For a multiplexer, we can send

one-bit enable signal along with each input data, and the control signals of the multiplexer can be generated based on the enable signals using a simple logic circuit, which includes several logic gates. For K -fault tolerance, we need K + 1 enable signals. In practical designs, K will be very small ( K ≤ 3 in this work), and hence, the power and area overhead is very small. Notice that the MUX and DEMUX only exist at the starting point and ending point of routing paths.

In the following, we analyze the costs of DEMUX and MUX . We set the bit-width to 32 bits and synthesize DEMUX and MUX with different sizes based on the 65 nm process technology using commercial logic synthesis tools. The power consumption is shown in Table III. From the table, we can see that the power consumption of DEMUX and MUX is at least two order of magnitude less than that of the switch. Consequently, the power consumption from introducing one more DEMUX and MUX port is much less than the power consumption reduced by removing a switch port.

TABLE III: Power consumption of DEMUX and MUX

| Size        |   Leakage power( µ W |   Total Power( mW ) |
|-------------|----------------------|---------------------|
| MUX 2 : 1   |             0.011269 |           0.0022274 |
| MUX 3 : 1   |             0.012971 |           0.029082  |
| MUX 4 : 1   |             0.021191 |           0.05328   |
| MUX 5 : 1   |             0.026081 |           0.063278  |
| MUX 6 : 1   |             0.030442 |           0.071425  |
| DEMUX 1 : 2 |             0.019218 |           0.0018354 |
| DEMUX 1 : 3 |             0.026286 |           0.034385  |
| DEMUX 1 : 4 |             0.016736 |           0.048588  |
| DEMUX 1 : 5 |             0.015607 |           0.05052   |
| DEMUX 1 : 6 |             0.017771 |           0.060453  |

## VI. LINK-FAULT TOLERANCE

In this section, we consider the generation of K -link-faulttolerance network topology, which is a special case of the generalized fault-tolerance topology. If only link failures between switches are considered, the mapping from cores to switches exhibits a many-to-one relationship. We propose an ILP based method to simultaneously solve the core mapping problem and the routing path allocation problem to improve the quality of the solutions.

Here, we define a routing path graph Grp ( Vrp , Erp ) to represent the possible connections between the cores and the switches and the possible physical links between the switches.

Definition 2: Routing Path Graph: Grp ( Vrp , Erp ) is directed, and Vrp = Vc ∪ Vs and Erp = Vs × Vs ∪ Vc × Vs ∪ Vs × Vc .

In the following, we give an ILP formulation to find K + 1 edge-disjoint routing paths in Grp for all the communication flows. The objective is to minimize the power consumption of the NoC topology with a switch size constraint, bandwidth constraints, and latency constraints.

The initial number of switches nsw is determined using method similar to the one in [34]. The binary variables xuv ( i , j , k ) and duv are defined similar to those in the formulation (5). The K -link-fault-tolerant topology generation problem can be formulated as the following integer programming problem:

$$M i n \sum _ { u \in V _ { s } } P _ { s w } ( i p _ { u }, o p _ { u } ) + P _ { l i n k } & ( 8 ) \quad \text{tolerant} \\ 1, \ K =$$

$$\Delta _ { \text{e} } \quad s. t. \ \sum _ { \substack { v \colon ( u, v ) \in E _ { r p } \\ \cdot } } x _ { u v } ^ { ( i, j, k ) } - \sum _ { \substack { v \colon ( u, v ) \in E _ { r p } \\ \cdot } } x _ { v u } ^ { ( i, j, k ) } =$$

$$\begin{cases} \cdots \nolimits \nolimits \nolimits \nolimits \nolimits \nolimimits \nolimimits \nolimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimi                                                                                                                                                                                                         \cdots \nolimits \nolimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimim                                                                                                                                                                                                       
                                                                                                                                                                                                        $                                                                                                                                                                                                        "                                                                                                                                                                                                        #                                                                                                                                                                                                        *                                                                                                                                                                                                        -                                                                                                                                                                                                        +                                                                                                                                                                                                       '                                                                                                                                                                                                       }                                                                                                                                                                                                       .                                                                                                                                                                                                        )                                                                                                                                                                                                        1,                                                                                                                                                                                                        (                                                                                                                                                                                                        0,                                                                                                                                                                                                      .
                                                                                                                                                                                                       "$$

$$& \| \sum _ { k \in [ 0, K ] } ^ { \varphi, \quad \cdots - \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \colon \\ & \sum _ { k \in [ 0, K ] } x _ { u v } ^ { ( i, j, k ) } \leq 1, \forall ( u, v ) \in E _ { r p }, ( i, j ) \in E _ { c c } \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \ \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \dots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \ddots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \dots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \ \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \quad \cdots \cdots \quad \cdots \quad \cdots \cdots \quad \cdots \cdots \quad \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \ddots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots$$

$$\sum _ { u \in V _ { c } } d _ { u v } \leq \max _ { - } s i z e - 1, \forall v \in V _ { s }$$

$$i p _ { u } \leq m a x _ { \L } s i z e, \ \ o p _ { u } \leq m a x _ { \L } s i z e$$

$$\sum _ { ( u, v ) \in V _ { s } \times V _ { s } } x _ { i v } ^ { ( i, j, 0 ) } + 1 \leq l _ { i, j }, \forall ( i, j ) \in E _ { c c }, \quad \quad ( 8 e )$$

$$\sum _ { ( i, j ) \in E _ { c c }, k \in [ 0, K ] } x _ { i u v } ^ { ( i, j, k ) } \cdot w _ { i, j } \leq B W _ { m a x }, \forall ( u, v ) \in V _ { r p } \quad ( 8 f )$$

$$\sum _ { v ; ( u, v ) \in V _ { c } \times V _ { s } } d _ { u v } = 1, \forall u \in V _ { c }$$

$$\sum _ { \stackrel { v, ( v, u ) \in V _ { s } \times V _ { c } } { \cdot \cdot \cdot } } d _ { v u } = 1, \forall u \in V _ { c }$$

$$x _ { u v } ^ { ( i, j, k ) } \in \{ 0, 1 \}, \forall ( u, v ) \in E _ { r p }, ( i, j ) \in E _ { c c }, k \in [ 0, K ] \ \ ( 8 i )$$

$$d _ { u v } \in \{ 0, 1 \}, \forall ( u, v ) \in E _ { r p }$$

Psw ( ipu , opu ) and Plink are computed using a method similar to the one in Section IV-B1. The constraint (8a) defines a path from s = ci to t = cj . The constraint (8b) ensures that the K + 1 paths are link-disjoint. Next, we use the (8c) constraint to ensure that each switch has at least one port for connecting to other switches and the constraint (8d) defines the max size for each switch. The constraint (8e) is the latency constraint, which means that the default path (k=0) passes through at most l i , j switches. The constraint (8f) means that the bandwidth requirements of the communication flows going through the physical link ( u v , ) must be less than the BWmax . The constraints (8g) and (8h) ensure that each core connects exactly one switch and the constraints (8i) and (8j) define the binary variables.

## VII. EXPERIMENT

The proposed algorithms have been implemented using C++ on a Linux 64-bit workstation (Intel 2.0 GHz, 64 GB RAM). All the ILP-based formulations are solved using Gurobi [43]. In the first set of experiments, we analyzed the hardware consumption of fault-tolerant topologies. The second set of experiments show the effectiveness of the port sharing. In the third set of experiments, we compared the proposed method for generating link-fault-tolerant topologies with those of previous studies.

## A. Hardware Cost Analysis of Fault Tolerance

In this experiment, the bandwidth constraint BWmax is set at 3000 MB s / and the maximum number of ports on switches, max size , is set to 10. ORION 3.0 [40] was used for estimating the switch power and the model from [41] was used for estimating the link power.

Table IV shows the comparison between the non-faulttolerant topologies and the fault-tolerant topologies with K = 1, K = 2 and K = 3, respectively. The column SwitchNum ,

TABLE IV: Comparison between Non-Fault-Tolerance &amp; K-Fault-Tolerance

| K   | Bench.                 | SwitchNum   | SwitchNum   | SwitchNum                   | LinkNum     | LinkNum     | LinkNum                       | Power(mW)                      | Power(mW)                        | Power(mW)                      | Time(s)                    |
|-----|------------------------|-------------|-------------|-----------------------------|-------------|-------------|-------------------------------|--------------------------------|----------------------------------|--------------------------------|----------------------------|
| K   | Bench.                 | NFT         | FT          | Inc                         | NFT         | FT          | Inc                           | NFT                            | FT                               | Inc                            | Time(s)                    |
|     | D 36 D 43 D 50 D 70    | 8 10 12 16  | 10 13 14 22 | 25.00% 30.00% 16.67% 37.50% | 18 26 26 48 | 23 32 34 71 | 27.78% 23.08% 30.77% 47.92%   | 256.426 330.912 341.88 574.434 | 516.979 622.819 692.739 1128.925 | 101.61% 88.21% 102.63% 96.53%  | 2.908 5.102 8.066 34.634 - |
|     | Average D 36 D 43 D 50 | - 8 10      | - 15 19     | 27.29% 87.50% 90.00% 75.00% | - 18 26     | - 39 49     | 32.39% 116.67% 88.46% 126.92% | - 256.426 330.912 341.880      | - 810.358 932.885 1099.778       | 97.24% 216.02% 181.91% 221.69% | 19.632 36.554 68.142       |
|     | D 70                   | 12          | 36          | 125.00%                     | 26 48       | 59 117      | 143.75%                       | 574.434                        | 1686.243                         | 193.55%                        |                            |
|     | Average                | -           | -           | 94.38%                      | -           | -           | 118.95%                       | -                              | -                                | 203.29%                        | -                          |
|     |                        |             | 21          |                             |             |             |                               |                                |                                  |                                |                            |
|     | D 36                   | 8           | 19          | 137.50%                     | 18          | 48          | 166.67%                       | 256.426                        | 1068.731                         | 316.78%                        | 51.054                     |
|     |                        | 16          | 26          | 160.00%                     |             | 69          | 165.38%                       | 330.912                        |                                  |                                | 674.757                    |
|     | D 43                   | 10          |             |                             | 26          |             |                               |                                | 1252.793                         | 278.59%                        |                            |
|     |                        |             |             |                             |             |             |                               |                                |                                  |                                | 162.595                    |
|     | D 50                   | 12          | 30          | 150.00%                     | 26          | 78          | 200.00%                       | 341.88                         | 1414.200                         | 313.65%                        | 465.502                    |
|     | D 70                   | 16          | 47          | 200.00%                     | 48          | 157         | 227.08%                       | 574.434                        | 2240.320                         | 290.00%                        | 5565.602                   |
|     | Average                | -           | -           | 170.00%                     | -           | -           | 189.78%                       | -                              | -                                | 299.76%                        | -                          |

LinkNum , and Power denote the number of switches, number of links, and the power, respectively. The column Time denotes the running time of the program. Additionally, the column NFT and FT respectively represent the non-fault-tolerant topologies and fault-tolerant topologies, and the column Inc shows the ratios.

As K increased from 1 to 3, the power consumption is increased by 97.24%, 203.29%, and finally to 299.76% compared to NFT ( K = 0). Fig.12 shows that the increase in the power consumption is approximately linear with K for all benchmarks, because the power mainly comes from the switches and communication traffic. The increase in the number of both switches and links is also approximately linear with K .

Fig. 12: Power in different K -fault-tolerant topologies.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00165v1-figure-9d590e58-f3c8-4274-84da-49126bf26b82.jpg)

Fig.13 shows the result of floorplan and topology for the

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00165v1-figure-87d3c0f4-2ae6-4288-a1af-99efba8465a3.jpg)

Fig. 13: One-switch-fault-tolerant topology for MP EncMP Dec 3 3 : (a) floorplan. (b) topology.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00165v1-figure-826da112-175f-4bbf-853f-684de817a7b8.jpg)

testbench MP EncMP Dec 3 3 .

## B. Analysis of Port Sharing

Table V shows the effectiveness of the port sharing. The columns SwitchNum , InportNum , OurportNum , and Power denote the number of switches, the number of input ports, the number of output ports, and the power, respectively. The columns NPT and PT represent the results with/without port sharing, and the column Dec shows the reduction of PT compared to NPT .

For one-fault-tolerance, the number of input ports, output ports, and the power can be reduced by 13.55%, 12.37% and 18.08%, respectively. As K increases, the results show more reduction in the switch power consumption, which demonstrates the effectiveness of port sharing.

## C. Link-fault Tolerance

1) One-link-fault tolerance: In this subsection, we compare the proposed framework to the FTTG method in [34], which includes a one-link-fault switch topology generation followed by a simulated annealing based core mapping, and the de Bruijn Digraph (DBG) based method [44] for the one-link-fault tolerance case.

To compare our results to that of previous studies [34] [44], the link power of the communication flow ( i , j ) on the edge ( u v , ) ∈ Erp are evaluated by Plk ( i , j , u v , ) = Ebit · wi j , · Du v , . Notice that there are no extra costs introduced for opening a new physical link.

a. Comparison to the FTTG method: In this work, we stipulate that physical links are directed whereas the FTTG method uses bi-directional physical links. Hence, we degenerate the directed graph to an undirected graph by adding to the ILP formulation (8) the following constraint:

濄濃

$$d _ { u v } - d _ { v u } = 0, \forall ( u, v ) \in E _ { r p }$$

濆

濇 Additionally, the objective function in FTTG is to minimize the energy consumption of the network topology, which is estimated based on the shortest paths (called the default path in

TABLE V: Comparison between NonPortSharing and PortSharing with different K

| K   | Bench.    | SwitchNum   | Input port   | Input port   | Input port    | Output port   | Output port   | Output port   | Power(mW)        | Power(mW)       | Power(mW)            |
|-----|-----------|-------------|--------------|--------------|---------------|---------------|---------------|---------------|------------------|-----------------|----------------------|
| K   | Bench.    | SwitchNum   | NPT          | PT           | Dec           | NPT           | PT            | Dec           | NPT              | PT              | Dec                  |
|     | D 36      | 10          | 87           | 74           | 14.94%        | 89            | 77            | 13.48%        | 516.979          | 414.609 506.410 | 19.80% 18.69% 19.42% |
|     | D 43      | 13          | 106          | 91           | 14.15%        | 114           | 101           | 11.40%        | 622.819          |                 |                      |
|     | D 50 D 70 | 14 22       | 118 187      | 101 167      | 14.41% 10.70% | 124 197       | 108 174       | 12.90% 11.68% | 692.739 1128.925 | 558.18 966.166  | 14.42%               |
|     | Average   | -           | -            | -            | 13.55%        | -             | -             | 12.37%        | -                | -               | 18.08%               |
|     | D 36      | 15          | 135          | 107          | 20.74%        | 138           | 114           | 17.39%        | 810.358          | 583.529         | 27.99%               |
|     | D 43      | 19          | 160          | 122          | 23.75%        | 172           | 142           | 17.44%        | 932.885          | 641.725         | 31.21%               |
|     | D 50      | 21          | 185          | 140          | 24.32%        | 194           | 158           | 18.56%        | 1099.778         | 746.669         | 32.11%               |
|     | D 70      | 36          | 291          | 238          | 18.21%        | 306           | 260           | 15.03%        | 1686.243         | 1277.790        | 24.22%               |
|     | Average   | -           | -            | -            | 21.76%        | -             | -             | 17.11%        | -                | -               | 28.88%               |
|     | D 36      | 19          | 176          | 133          | 24.43%        | 180           | 143           | 20.56%        | 1068.731         | 717.322         | 32.88%               |
|     | D 43      | 26          | 217          | 165          | 23.96%        | 233           | 162           | 30.47%        | 1252.793         | 844.043         | 32.63%               |
|     | D 50      | 30          | 246          | 170          | 30.89%        | 258           | 186           | 27.91%        | 1414.200         | 844.494         | 40.28%               |
|     | D 70      | 47          | 389          | 297          | 23.65%        | 409           | 314           | 23.23%        | 2240.32          | 1545.64         | 31.01%               |
|     | Average   | -           | -            | -            | 25.73%        | -             | -             | 25.54%        | -                | -               | 34.20%               |

[34]). To make a fair comparison to the FTTG method, we use the same objective function as follows.

$$M i n \sum _ { ( i, j ) \in E _ { c c } } \{ R _ { i, j } * E _ { R _ { b i t } } + L _ { i, j } * E _ { L _ { b i t } } \} * w _ { i, j }. \quad ( 1 0 ) \, \begin{array} { c } \ r e a u { \ p } \\ \text{with $t$} \\ \text{the $pre$} \end{array}$$

In the formula, ERbit represents the bit energy consumption of the switches and ELbit represents the bit energy consumption of the unit length links [34]. Li j , = ∑ ( u v , ) ∈ Erp duv is the number of physical links used by the shortest routing path of the communication flow ( i , j ) and Ri j , = Li j , -1 is the number of switches on the shortest routing path.

table. Columns 5, 6, and 7 are the comparison of the two methods on the average hop count (AHC). Furthermore, column redu presents the reduction of the performance index compared with the FTTG algorithm. Compared with FTTG algorithm, the proposed method can reduce the energy consumption by 10.58% on average. In addition, the proposed method can also reduce the hop count by 6.25% on an average. This is because the switch topology and the core mapping strongly depends on each other and we formulate the two subproblems as a single ILP model, in which we can determine the best solution for the whole problems.

Six widely used benchmarks were used for the comparisons. The port number of switches max size was set to four, which is the same as that in [34]. Because we cannot obtain the value of the bandwidth constraint in [34], the bandwidth constraint f max is set to 3000 MB s / , which corresponds to a 32 bit physical link operating at 750MHz. The proposed ILP-based method is applied to generate a one-fault-tolerant topology with the switch number varying from rmin to rmax . For fair comparisons, we use the energy estimation model in [34]. The energy consumption of the switches and links are set at 3 20 . pJ / Kb and 4 78 . pJ / Kb nm / , and the length of the links is set to 1 mm .

TABLE VI: Comparisons to FTTG [34]

| Benchmark   | Energy(mJ)   | Energy(mJ)   | Energy(mJ)   | Average Hop Count   | Average Hop Count   | Average Hop Count   |
|-------------|--------------|--------------|--------------|---------------------|---------------------|---------------------|
| Benchmark   | FTTG         | Ours         | redu         | FTTG                | Ours                | redu                |
| MPEG 4      | 61.10        | 50.13        | 17.95%       | 1.23                | 1.23                | 0                   |
| VOPD        | 65.15        | 49.55        | 23.94%       | 0.95                | 0.87                | 8.421%              |
| MWD         | 19.14        | 15.68        | 18.08%       | 0.58                | 0.54                | 6.897%              |
| 263 Dec     | 0.297        | 0.285        | 4.04%        | 0.93                | 0.71                | 23.655%             |
| 263 Enc     | 3.74         | 3.76         | -0.54%       | 0.75                | 0.83                | -10.667             |
| MP 3 Enc    | 0.254        | 0.254        | 0            | 0.76                | 0.69                | 9.211%              |
| Average     | -            | -            | 10.58%       | -                   | -                   | 6.25%               |

The experimental results are listed in Table VI. The first column is the name of benchmark. Columns 2 and 3 provide the energy consumption of the fault-tolerant network topology generated using the FTTG algorithm and the proposed ILP based method, respectively. The energy is calculated based on the shortest path between the two alternative paths, which is the default routing path [34]. The benchmark MP Enc 3 refers to the MP EncMP Dec 3 3 because of the limited space in the b. Comparison to the DBG based method: The DBG method [44] generates a link-fault-tolerance topology without consideration of the position of the cores and switches. Hence, we set the distances Duv to 1 mm to calculate the power consumption.

We implemented the 2-D topology generation algorithm (DBG) in [44] and made a comparison. The port number of switches max size is set to 10. Six widely used benchmarks and three synthetic benchmarks, D 36, D 43,and D 50 are used in the experiments.

The experimental results are listed in Table VII, where the average hop count is equal to the number of switches along a path plus one. The proposed method can reduce the power and average hop count by 21.72% and 9.35%, respectively. The synthetic benchmarks use one more switch compared to the DBG method; however, the switch size is smaller, which results in a power reduction. On the other hand, the number of links can be reduced by 45.46% on an average. In the DBG method, each switch has two links for connecting to other switches. This results in many redundant links. Actually, there are some pairs of communication cores allocated on the same router which do not experience the link-fault-tolerance issue. In the proposed method, we consider only the necessary links between the switches. As the number of switches is increased, the diameter of the DGB graph increases even faster, which cause the average hop count to become much larger, especially for the synthetic benchmarks D 36, D 43, and D 50.

Fig.14 shows the result of the floorplan and topology for the testbench MP EncMP Dec 3 3 .

TABLE VII: Comparisons to DBG [44]

| Benchmark        | SwitchNum(mJ)   | SwitchNum(mJ)   | SwitchNum(mJ)   | LinkNum   | LinkNum   | LinkNum   | Power(mW)   | Power(mW)   | Power(mW)   | Average Hop Count   | Average Hop Count   | Average Hop Count   |
|------------------|-----------------|-----------------|-----------------|-----------|-----------|-----------|-------------|-------------|-------------|---------------------|---------------------|---------------------|
| Benchmark        | DBG             | Ours            | reduction       | DBG       | Ours      | reduction | DBG         | Ours        | reduction   | DBG                 | Ours                | reduction           |
| VOPD             | 3               | 2               | 33.33%          | 6         | 3         | 50%       | 107.914     | 85.985      | 20.32%      | 2.20                | 2.13                | 3.18%               |
| MPEG 4           | 3               | 3               | 0               | 6         | 3         | 50%       | 107.914     | 83.704      | 22.43%      | 2.15                | 2.31                | -7.44%              |
| MWD              | 3               | 3               | 0               | 6         | 3         | 50%       | 107.905     | 83.690      | 22.44%      | 2.21                | 2.15                | 2.71%               |
| MP 3 EncMP 3 Dec | 3               | 3               | 0               | 6         | 3         | 50%       | 113.810     | 84.590      | 25.67%      | 2.29                | 2.08                | 9.17%               |
| 263 Dec          | 3               | 3               | 0               | 6         | 3         | 50%       | 120.370     | 94.450      | 21.53%      | 2.33                | 2.14                | 8.15%               |
| 263 Enc          | 3               | 3               | 0               | 6         | 3         | 50%       | 107.900     | 78.680      | 27.08%      | 2.15                | 2.17                | -0.93%              |
| D 36             | 4               | 5               | -25%            | 8         | 5         | 37.5%     | 294.581     | 238.200     | 19.14%      | 2.77                | 2.42                | 12.64%              |
| D 43             | 5               | 6               | -20%            | 10        | 7         | 30%       | 355.900     | 288.426     | 18.96%      | 2.95                | 2.28                | 22.71%              |
| D 50             | 6               | 7               | -16.67%         | 12        | 7         | 41.67%    | 399.593     | 328.175     | 17.87%      | 3.62                | 2.39                | 33.98%              |
| Average          | -               | -               | -6.85%          | -         | -         | 45.46%    | -           | -           | 21.72%      | -                   | -                   | 9.35%               |

Fig. 14: One-link-fault tolerance for MP EncMP Dec 3 3 : (a)Result of floorplan; (b)Result of topology

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00165v1-figure-e21cb3f3-2265-47a3-a5bd-608da6a754f5.jpg)

- 2) Multiple-link-fault tolerance: The proposed ILP-based method can be applied to generate K -link-fault tolerance network topologies.

Table VIII show the results. The benchmark MP E D 3 / refers to the MP EncMP Dec 3 3 . The columns SwitchNum , LinkNum , and Power denote the number of switches, the number of links, and the power, respectively. The columns NFT , 1 FT , 2 FT , and 3 FT denote the results of non-fault tolerance, onefault tolerance, two-fault tolerance, and three-fault tolerance, respectively.

Compared to NFT , one-fault tolerance topologies use the same number of switches and three times as many links on an average, and the power overhead of one-fault tolerance topologies is 11.9%. Compared to NFT , the power consumption increases by 23.8% in 2 FT on average while it is 52.1% in 3 FT , because more switches and links are used to generate fault-tolerance topologies. The increase in power consumption is approximately linear with K .

## VIII. CONCLUSIONS

In this paper, we presented a K -fault-tolerant topology generation method for ASNoC with physical link failures and switch failures. First, an convex-cost flow and ILP based method was proposed to generate a network topology in which each communication flow has at least K + 1 switch-disjoint routing paths, which provide K -fault tolerance. Second, to reduce the switch sizes, we proposed sharing the switch ports for the connections between the cores and switches, and proposed heuristic methods to solving the port sharing problem. Finally, we also proposed an ILP-based method to simultaneously solve the core mapping and routing path allocation problems when only the physical link failures are considered. The experimental results showed the effectiveness of the proposed method.

## REFERENCES

- [1] S. Borkar, 'Thousand core chips: A technology perspective,' in Proceedings of the 44th Annual Design Automation Conference , 2007, pp. 746749.
- [2] W. J. Dally and B. Towles, 'Route packets, not wires: On-chip interconnection networks,' in Proc. 38th Annual Design Automation Conference , 2001, pp. 684-689.
- [3] T. Bjerregaard and S. Mahadevan, 'A survey of research and practices of network-on-chip,' ACM Computing Survey , vol. 38, no. 1, June 2006.
- [4] R. Marculescu, U. Y. Ogras, L. S. Peh, N. E. Jerger, and Y. Hoskote, 'Outstanding research problems in noc design: System, microarchitecture, and circuit perspectives,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , vol. 28, no. 1, pp. 3-21, Jan 2009.
- [5] F. Akopyan, J. Sawada, A. Cassidy, R. Alvarez-Icaza, J. Arthur, P. Merolla, N. Imam, Y. Nakamura, P. Datta, G. J. Nam, B. Taba, M. Beakes, B. Brezzo, J. B. Kuang, R. Manohar, W. P. Risk, B. Jackson, and D. S. Modha, 'Truenorth: Design and tool flow of a 65 mw 1 million neuron programmable neurosynaptic chip,' IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems , vol. 34, no. 10, pp. 1537-1557, Oct 2015.
- [6] B. V. Benjamin, P. Gao, E. McQuinn, S. Choudhary, A. R. Chandrasekaran, J. M. Bussat, R. Alvarez-Icaza, J. V. Arthur, P. A. Merolla, and K. Boahen, 'Neurogrid: A mixed-analog-digital multichip system for large-scale neural simulations,' Proceedings of the IEEE , vol. 102, no. 5, pp. 699-716, May 2014.
- [7] X. Liu, W. Wen, X. Qian, H. Li, and Y. Chen, 'Neu-noc: A high-efficient interconnection network for accelerated neuromorphic systems,' in 23rd Asia and South Pacific Design Automation Conference (ASP-DAC) , Jan 2018, pp. 141-146.
- [8] S. Tosun and et al., 'Application-specific topology generation algorithms for network-on-chip design,' IET computers &amp; digital techniques , 2012.
- [9] S. Murali, P. Meloni, F. Angiolini, D. Atienza, S. Carta, L. Benini, G. De Micheli, and L. Raffo, 'Designing application-specific networks on chips with floorplan information,' in Proceedings of the 2006 IEEE/ACM International Conference on Computer-aided Design , pp. 355-362.
- [10] C. Constantinescu, 'Trends and challenges in vlsi circuit reliability,' IEEE Micro , vol. 23, no. 4, pp. 14-19, July 2003.
- [11] S. Borkar, 'Designing reliable systems from unreliable components: the challenges of transistor variability and degradation,' IEEE Micro , vol. 25, no. 6, pp. 10-16, Nov 2005.
- [12] J. Keane and C. H. Kim, 'Transistor aging,' IEEE Spectrum , vol. 48, no. 5, pp. 28-33, 2011.
- [13] Y. Ren, L. Liu, S. Yin, J. Han, Q. Wu, and S. Wei, 'A fault tolerant noc architecture using quad-spare mesh topology and dynamic reconfiguration,' Journal of Systems Architecture , vol. 59, no. 7, pp. 482-491, 2013.
- [14] Y.-C. Chang, C.-T. Chiu, S.-Y. Lin, and C.-K. Liu, 'On the design and analysis of fault tolerant noc architecture using spare routers,' in Proceedings of the 16th Asia and South Pacific Design Automation Conference . IEEE Press, 2011, pp. 431-436.
- [15] Y. Ren, L. Liu, S. Yin, Q. Wu, S. Wei, and J. Han, 'A vlsi architec- ture for enhancing the fault tolerance of noc using quad-spare mesh topology and dynamic reconfiguration,' in Proc. IEEE Int. Symp. Circuits Syst. , 2013, pp. 1793-1796.

TABLE VIII: Results for K -link-fault ( K = 0 , 1 , 2 , 3) tolerance

| Benchmark   | SwitchNum   | SwitchNum   | SwitchNum   | SwitchNum   | LinkNum   | LinkNum   | LinkNum   | LinkNum   | Power(mW)   | Power(mW)   | Power(mW)   | Power(mW)   | Time(s)   | Time(s)   | Time(s)   | Time(s)   |
|-------------|-------------|-------------|-------------|-------------|-----------|-----------|-----------|-----------|-------------|-------------|-------------|-------------|-----------|-----------|-----------|-----------|
| Benchmark   | NFT         | 1FT         | 2FT         | 3FT         | NFT       | 1FT       | 2FT       | 3FT       | NFT         | 1FT         | 2FT         | 3FT         | NFT       | 1FT       | 2FT       | 3FT       |
| MPEG 4      | 3           | 3           | 4           | 5           | 1         | 3         | 5         | 7         | 74.836      | 78.532      | 93.246      | 106.269     | 1.222     | 10.92     | 62.402    | 1091.638  |
| VOPD        | 3           | 3           | 4           | 5           | 1         | 3         | 5         | 7         | 71.157      | 79.137      | 82.340      | 111.381     | 1.005     | 7.355     | 39.522    | 315.652   |
| MWD         | 3           | 3           | 4           | 5           | 1         | 3         | 5         | 7         | 67.018      | 85.98       | 86.067      | 111.389     | 1.102     | 5.754     | 124.97    | 1396.625  |
| 263 Dec     | 3           | 3           | 4           | 5           | 1         | 3         | 5         | 9         | 83.600      | 89.63       | 106.25      | 116.110     | 1.216     | 38.389    | 952.437   | 4314.34   |
| 263 Enc     | 3           | 3           | 4           | 5           | 1         | 3         | 5         | 7         | 71.136      | 82.103      | 93.592      | 116.370     | 0.785     | 3.266     | 36.619    | 192.64    |
| MP 3 E / D  | 3           | 3           | 4           | 5           | 3         | 3         | 5         | 9         | 77.040      | 82.41       | 89.300      | 114.930     | 0.810     | 6.235     | 134.183   | 3121.806  |
| Average     | 1           | 1           | 1.33        | 1.67        | 1         | 2.25      | 3.75      | 5.75      | 1           | 1.119       | 1.238       | 1.521       | -         | -         | -         | -         |

- [16] N. Chatterjee, S. Chattopadhyay, and K. Manna, 'A spare router based reliable network-on-chip design,' in Proc. IEEE Int. Symp. Circuits Syst. , 2014, pp. 1957-1960.
- [32] N. Chatterjee, S. Chattopadhyay, and K. Manna, 'A spare router based reliable network-on-chip design,' in Circuits and Systems (ISCAS), 2014 IEEE International Symposium on . IEEE, 2014, pp. 1957-1960.
- [17] A. Hosseini, T. Ragheb, and Y. Massoud, 'A fault-aware dynamic routing algorithm for on-chip networks,' in IEEE International Symposium on Circuits and Systems , 2008, pp. 2653-2656.
- [18] P. Ren, X. Ren, S. Sane, M. A. Kinsy, and N. Zheng, 'A deadlock-free and connectivity-guaranteed methodology for achieving fault-tolerance in on-chip networks,' IEEE Transactions on Computers , vol. 65, no. 2, pp. 353-366, Feb 2016.
- [19] K. Srinivasan, K. S. Chatha, and G. Konjevod, 'Linear-programmingbased 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.
- [20] S. Yan and B. Lin, 'Application-specific network-on-chip architecture synthesis based on set partitions and steiner trees,' in Proceedings of the 2008 Asia and South Pacific Design Automation Conference , pp. 277-282.
- [21] C. Seiculescu, S. Murali, L. Benini, and G. De Micheli, 'Sunfloor 3d: A tool for networks on chip topology synthesis for 3-d systems on chips,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , vol. 29, no. 12, pp. 1987-2000, 2010.
- [22] B. Yu, S. Dong, S. Chen, and S. Goto, 'Floorplanning and topology generation for application-specific network-on-chip,' in 2010 15th Asia and South Pacific Design Automation Conference (ASP-DAC), , 2010, pp. 535-540.
- [23] J. Cong, Y. Huang, and B. Yuan, 'Atree-based topology synthesis for onchip network,' in 2011 IEEE/ACM International Conference on ComputerAided Design (ICCAD), , pp. 651-658.
- [24] B. Huang, S. Chen, W. Zhong, and T. Yoshimura, 'Application-specific network-on-chip synthesis with topology-aware floorplanning,' in 2012 25th Symposium on Integrated Circuits and Systems Design (SBCCI) , 2012, pp. 1-6.
- [25] W. Zhong, S. Chen, B. Huang, T. Yoshimura, and S. Goto, 'Floorplanning and topology synthesis for application-specific network-on-chips,' IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , vol. 96, no. 6, pp. 1174-1184, 2013.
- [26] W. Zhong, T. Yoshimura, B. Yu, S. Chen, S. Dong, and S. Goto, 'Cluster generation and network component insertion for topology synthesis of application-specific network-on-chips,' IEICE transactions on electronics , vol. 95, no. 4, pp. 534-545, 2012.
- [27] K. S.-M. Li, 'Cusnoc: Fast full-chip custom noc generation,' IEEE Transactions on Very Large Scale Integration (VLSI) Systems , vol. 21, no. 4, pp. 692-705, 2013.
- [28] V. Todorov, D. Mueller-Gritschneder, H. Reinig, and U. Schlichtmann, 'Deterministic synthesis of hybrid application-specific network-on-chip topologies,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , vol. 33, no. 10, pp. 1503-1516, 2014.
- [29] J. Huang, S. Chen, W. Zhong, W. Zhang, S. Diao, and F. Lin, 'Floorplanning and topology synthesis for application-specific network-on-chips with rf-interconnect,' ACM Transactions on Design Automation of Electronic Systems (TODAES) , vol. 21, no. 3, p. 40, 2016.
- [30] P. Mukherjee, S. D'souza, and S. Chattopadhyay, 'Area constrained performance optimized asnoc synthesis with thermalaware white space allocation and redistribution,' Integration, the VLSI Journal , vol. 60, pp. 167 -189, 2018. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0167926017301165
- [31] A. E. Zonouz, M. Seyrafi, A. Asad, M. Soryani, M. Fathy, and R. Berangi, 'A fault tolerant noc architecture for reliability improvement and latency reduction,' in IEEE 12th Euromicro Conference on Digital System Design, Architectures, Methods and Tools , 2009, pp. 473-480.
- [33] Y. Ren, L. Liu, S. Yin, J. Han, Q. Wu, and S. Wei, 'A fault tolerant noc architecture using quad-spare mesh topology and dynamic reconfiguration,' Journal of Systems Architecture , vol. 59, no. 7, pp. 482-491, 2013.
- [34] S. Tosun, V. B. Ajabshir, O. Mercanoglu, and O. Ozturk, 'Fault-tolerant topology generation method for application-specific network-on-chips,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , vol. 34, no. 9, pp. 1495-1508, 2015.
- [35] W. J. Dally and B. Towles, Principles and Practices of Interconnection Networks . San Francisco: Morgan Kaufmann, 2004.
- [36] W. Zhong, S. Chen, and et al., 'Floorplanning and topology synthesis for application-specific network-on-chips,' IEICE Trans. Fund. , 2013.
- [37] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, 'Network flows: theory, algorithms, and applications,' 1993.
- [38] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency . Berlin: Springer Science &amp; Business Media, 2002, vol. 24.
- [39] Q. Xu, S. Chen, X. Xu, and B. Yu, 'Clustered fault tolerance tsv planning for 3d integrated circuits,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2017.
- [40] A. B. Kahang, B. Lin, and S. Nath, 'ORION3.0: A Comprehensive noc router estimation tool,' IEEE Embedded Systems Letters , vol. 7, no. 2, pp. 41-45, June 2015.
- [41] J. Huang, W. Zhong, Z. Li, and S. Chen, 'Lagrangian relaxation-based routing path allocation for application-specific network-on-chips,' Integration, the VLSI Journal , 2017.
- [42] P. M. Pardalos and G. P. Rodgers, 'A branch and bound algorithm for the maximum clique problem,' Computers &amp; operations research , vol. 19, no. 5, pp. 363-375, 1992.
- [43] I. Gurobi Optimization, 'Gurobi optimizer reference manual,' 2015. [Online]. Available: http://www.gurobi.com
- [44] K. S.-M. Li and S.-J. Wang, 'Design methodology of fault-tolerant custom 3d network-on-chip,' ACM Transactions on Design Automation of Electronic Systems (TODAES) , vol. 22, no. 4, p. 63, 2017.
Song Chen Mengke Ge Zhigang Li Jinglei Huang Qi Xu Feng Wu
Generalized Fault-Tolerance Topology Generation for Application Specific Network-on-Chips
The Network-on-Chips is a promising candidate for addressing communication
bottlenecks in many-core processors and neural network processors. In this
work, we consider the generalized fault-tolerance topology generation problem,
where the link or switch failures can happen, for application-specific
network-on-chips (ASNoC). With a user-defined number, K, we propose an integer
linear programming (ILP) based method to generate ASNoC topologies, which can
tolerate at most K faults in switches or links. Given the communication
requirements between cores and their floorplan, we first propose a
convex-cost-flow based method to solve a core mapping problem for building
connections between the cores and switches. Second, an ILP based method is
proposed to allocate K+1 switch-disjoint routing paths for every communication
flow between the cores. Finally, to reduce switch sizes, we propose sharing the
switch ports for the connections between the cores and switches and formulate
the port sharing problem as a clique-partitioning problem Additionally, we
propose an ILP-based method to simultaneously solve the core mapping and
routing path allocation problems when considering physical link failures only.
Experimental results show that the power consumptions of fault-tolerance
topologies increase almost linearly with K because of the routing path
redundancy. When both switch faults and link faults are considered, port
sharing can reduce the average power consumption of fault-tolerance topologies
with K = 1, K = 2 and K = 3 by 18.08%, 28.88%, and 34.20%, respectively. When
considering only the physical link faults, the experimental results show that
compared to the FTTG algorithm, the proposed method reduces power consumption
and hop count by 10.58% and 6.25%, respectively; compared to the DBG based
method, the proposed method reduces power consumption and hop count by 21.72%
and 9.35%, respectively.