CN102752207B - Reconfigurable 2D (two-dimensional) mesh on-chip network structure and reconfiguration method thereof - Google Patents

Abstract

A reconfigurable 2D mesh on-chip network structure and a reconfiguration method thereof relate to a reconfigurable 2D mesh on-chip network structure and a reconfiguration method thereof. In order to solve the problem that although the virtual topology of the existing 2D mesh structure is the same as the original topology after reconfiguration, the underlying network topology is very different from the original topology. Each core of the reconfigurable 2D mesh on-chip network structure can be connected to one of the four adjacent routers: each router communicates with the four adjacent cores through the multiplexer MUX and the network interface NI. The reconfiguration method based on the above structure: In the selected sub-network, according to the connection status of each router and the core, the routers are connected to the core, and a core can only be connected to one router at a time. The invention is used for reconfiguring the 2D mesh on-chip network structure.

Description

Reconfigurable 2D mesh network-on-chip structure and its reconfiguration method

technical field

The invention relates to a reconfigurable 2D mesh on-chip network structure and a reconfiguration method thereof. the

Background technique

With the advancement of semiconductor manufacturing technology, multi-core chips and multi-core-based parallel computing have become new means to improve chip performance. However, as the density of transistors on a chip increases and the characteristic line width becomes smaller and smaller, the requirements for the production of single-core chips become higher and higher, and the difficulty becomes more and more difficult. A widely used solution is to introduce fault-tolerant technology in the chip design and manufacturing process. As a simple fault-tolerant scheme, redundant fault-tolerance has been rapidly developed and applied in the field of chip design. Previous work mainly focused on redundant fault tolerance at the microarchitecture level, which is more applicable when the number of cores is small. However, when the number of cores increases to a critical value, the hardware cost introduced by microarchitecture redundancy is somewhat outweighed, and core redundancy fault tolerance becomes very important. the

On the other hand, the network-on-chip (Network-on-Chip) technology is widely used as the interconnect architecture of multi-core chips due to its high scalability and high bandwidth characteristics. The topology of the network on chip has a very important impact on the performance of the multi-core system, especially in some communication-intensive applications. Therefore, if the operating system can perceive the topology of the multi-core system, it will greatly help improve the efficiency of task scheduling and assignment, thereby improving the performance of the multi-core system. At the same time, programmers should also understand the topology of multi-core systems in order to optimize their performance when designing parallel programs. However, this optimization also strengthens the coupling between the program and the topology, so that when the underlying physical topology changes (for example, some computing nodes fail), the original optimization of the upper-layer software may not bring about performance improvement, or even lead to performance degradation. Therefore, if the multi-core system can maintain a unified topology structure for the upper-layer operating system and applications, the impact of changes in the physical topology structure on the upper-layer software will be greatly reduced. the

Contents of the invention

The purpose of the present invention is to solve the problem that although the virtual topology of the existing 2D mesh structure is the same as the original topology after reconfiguration, the underlying network topology is very different from the original topology, and to provide a reproducible Configured 2D mesh network-on-chip structure and its reconfiguration method. the

Reconfigurable 2D mesh on-chip network structure, which includes M×N cores and (M+1)×(N+1) routers, M×N cores include K×L working cores, redundant cores (M×N-K×L);

Each core can be connected to one of the four adjacent routers: each router communicates with the four adjacent cores through the multiplexer MUX and the network interface NI. the

Based on the reconfiguration method of the above-mentioned 2D mesh on-chip network structure, it includes the following steps:

Step 1: Select a K×L sub-network in the (M+1)×(N+1) routing network;

Step 2: Judge the status of each router in the subnet one by one, and the status is divided into the following three categories:

State 1. There is no core connected to the router;

State 2, there is only one core connected to the router;

State 3. There are two or more cores connected to the router;

Step 3: Determine whether there is a router in the state 1 in the subnetwork, if it exists, then proceed to step 1, and reselect the subnetwork; if it does not exist, then proceed to step 4;

Step 4: Determine whether there is a router in state 2 in the subnet, if it exists, connect each router in state 2 to the corresponding core, and remove the router and the core connected to it in the subnet, and transfer to Step 2; if it does not exist, go to step 5;

Step 5: Determine whether there is a router in state 3 in the sub-network, if it exists, connect each router in state 3 to one of the two or more cores, and remove the router and the router in the sub-network For the core connected to it, go to step 2; if it does not exist, the reconfiguration is complete. the

The advantage of the present invention is: since a core can only be connected to one router at the same time, it is only necessary to add some multiplexers and reconfiguration registers in the traditional 2D mesh network, without adding additional routers to the core and the router. port. Reconfiguration is accomplished by replacing a failed core with a redundant core. After reconfiguration, the 2D mesh on-chip network structure ensures that the underlying network topology is the same as the original topology, and will not affect the topology information provided to the upper-layer operating system and applications. The additional hardware overhead introduced is moderate, and cores, routers, and links that are not working can achieve low power consumption by sleeping. the

Description of drawings

Fig. 1 is a structural schematic diagram of a reconfigurable 2D mesh network-on-chip structure according to the present invention. Among them, A represents a dormant core, B represents a working core, C represents a dormant route, D represents a working route, E represents a dormant link, and F represents a working link. the

Fig. 2 is the electrical connection schematic diagram of the core and the router of the reconfigurable 2D mesh network on chip structure of the present invention. the

Fig. 3 is the flowchart of the reconfiguration method of the reconfigurable 2D mesh network on chip structure of the present invention. the

Figure 4 is a schematic diagram of a 2D mesh network-on-chip with three damaged cores. Among them, G represents a damaged core, A represents a dormant core, B represents a working core, C represents a dormant route, D represents a working route, E represents a dormant link, and F represents a working link. the

5 is a schematic diagram of a 2Dmesh network-on-chip structure reconfigured by the reconfiguration method of the reconfigurable 2D mesh network-on-chip structure according to the present invention. Among them, G represents a damaged core, A represents a dormant core, B represents a working core, C represents a dormant route, D represents a working route, E represents a dormant link, and F represents a working link. the

Figure 6 shows the reconfiguration success rate of the reconfigurable 2D mesh network structure on a chip with different damaged core sizes using the reconfiguration method of the 2D mesh network structure on a chip

Figure 7 shows the success rate of reconfiguration of reconfigurable 2D mesh network-on-chip structures with different core sizes in the case of extreme damage. the

Detailed ways

Specific Embodiment 1: This embodiment is described in conjunction with FIG. 1. The reconfigurable 2D mesh network-on-chip structure described in this embodiment, the reconfigurable 2D mesh network-on-chip structure, includes M×N cores and (M+ 1) ×(N+1) routers, M×N cores include K×L working cores and redundant cores (M×N-K×L);

Each core can be connected to one of the four adjacent routers: each router communicates with the four adjacent cores through the multiplexer MUX and the network interface NI. the

Specific embodiment two: this embodiment is described in conjunction with Fig. 2, and this embodiment is a further limitation of the reconfigurable 2D mesh on-chip network structure described in specific embodiment one, and the network interface NI includes a bus interface and a write FIFO module , read FIFO module, unpack and pack module and control register, it is characterized in that, described control register also comprises reconfiguration register, and reconfiguration register comprises reconfiguration status register REC_STA, reconfiguration control register REC_CNTL and virtual node number register NODE_NUM,

The unpacking and packaging module is used for unpacking or packaging normal messages in the network, and is also used for packaging or unpacking reconfiguration messages, and writes the reconfiguration messages after packaging or unpacking into the reconfiguration status register REC_STA;

The reconfiguration status register REC_STA is used to control one of the switches in the multiplexer MUX to close and the other switches to be disconnected according to the unpacked reconfiguration message, and is also used to store status information indicating the route connected to the core;

The multiplexer MUX is used to realize the connection between the core and a router under the control of the reconfiguration status register REC_STA;

The reconfiguration control register REC_CNTL is used to store information that controls the sending and enabling of reconfiguration messages;

The virtual node number register NODE_NUM is used to store virtual node number information. the

Specific embodiment three: this embodiment is a further limitation of the reconfigurable 2D mesh network-on-chip structure described in specific embodiment one,

The header flake format of the network interface NI is:

In this embodiment, the format of the traditional network interface header chip is modified, and bits 31-29 of the service type are modified. On the basis of the original BE service and GS service, the reconfiguration service type (RC) is added. the

Specific embodiment four: illustrate this embodiment in conjunction with Fig. 3, this embodiment is based on the reconfiguration method of the reconfigurable 2D mesh on-chip network structure described in specific embodiment one, and it comprises the following steps:

Step 1: Select a K×L sub-network in the (M+1)×(N+1) routing network;

Step 2: Judge the status of each router in the subnet one by one, and the status is divided into the following three categories:

State 1. There is no core connected to the router;

State 2, there is only one core connected to the router;

State 3. There are two or more cores connected to the router;

Step 3: Determine whether there is a router in the state 1 in the subnetwork, if it exists, then proceed to step 1, and reselect the subnetwork; if it does not exist, then proceed to step 4;

Step 4: Determine whether there is a router in state 2 in the subnet, if it exists, connect each router in state 2 to the corresponding core, and remove the router and the core connected to it in the subnet, and transfer to Step 2; if it does not exist, go to step 5;

Step 5: Determine whether there is a router in state 3 in the sub-network, if it exists, connect each router in state 3 to one of the two or more cores, and remove the router and the router in the sub-network For the core connected to it, go to step 2; if it does not exist, the reconfiguration is complete. the

The connection between the router and the core is data communication;

The advantage of reconfigurability of R-mesh is realized by reconfiguration algorithm. For an R-mesh structure with a core size of M×N and a working core of K×L, the size of the routing network is (M+1)×(N+1), and the number of redundant cores is (M×NK×L ), the redundancy is (M×NK×L)/K×L. The problem can be formulated as: For these M×N cores, find K×L cores. For each core C _kl (0≤k<K, 0≤l<L), from (M+1)×(N+1) routers R _mn (0≤m≤M, 0≤n≤M) Find a core to connect with it, and enable these routers to form a standard 2D mesh network.

The mathematical description is: for a set {C _mn } (0≤m<M, 0≤n<N) composed of M×N cores, find a subset {C _kl }, through a one-to-one mapping f: {C _kl }->{R _mn }, making {R _mn } a special set {R _hg } (0≤h≤M, 0≤g≤M) composed of (M+1)×(N+1) routers Subset (that is, a subset that can form a 2D mesh network).

According to the above description of the problem, the present invention designs a deterministic algorithm to find the solution of the reconfiguration. This algorithm is a greedy algorithm, which approaches the global optimal solution through the optimal solution at each step. The algorithm first divides the elements in the collection {C _mn } into three categories according to the number of corresponding elements in the mapping f: {C _kl }->{R _mn } in {R _hg }: the elements in the collection {R _hg } cannot be matched, It can correspond to one element in {R _hg }, and can correspond to multiple elements in {R _hg }. Then choose any one of these elements that can correspond to an element in {R _hg }, and bind it to the map f: {C _kl }->{R _mn }. Then classify and repeat the above process until the final solution is found. If the corresponding element cannot be found through mapping, the selected element is incorrect and needs to be reselected.

The invention is realized through software and hardware collaborative design. It can be roughly divided into the following four parts:

1. Core state detection or read-in: generated by the core's built-in self-test BIST module and implemented by hardware. the

2. Realization of reconfiguration algorithm: realized by software, see R-mesh reconfiguration algorithm for details. the

3. Reconfiguration message sending: To send a message with a fixed format, you need to use the service type bit of the data packet, add a new reconfiguration service RC, pack the reconfiguration message, and send it to each effective core by the master control node. the

4. Select a route for connection: realized by hardware, unpack through the network interface NI, write the reconfiguration information into the register, and complete the selection of router connection. the

A general network interface can be modified into a reconfigurable network interface by adding the reconfiguration function. There are three main parts to modify:

1. Modify the data packet format and add the data packet description of the reconfiguration service RC. the

2. Modify the packing and unpacking module of the network interface to support the reconfiguration service RC. the

3. Add REC_STA, REC_CNTL, NODE_NUM three reconfiguration registers (Reconfig Resister). Among them, REC_STA is a reconfiguration status register, which is used to indicate the status of which route the core is connected to, and is a read-only register. REC_CNTL is a reconfiguration control register, which is used to control the sending of reconfiguration information, and is a read-write register. NODE_NUM is a virtual node number register, which is used to store virtual node number information and is a read-only register. The hardware structure of the modified network interface NI is shown in Figure 2. the

For a certain reconfiguration problem, we can describe the specific algorithm as the following four steps, and the flow chart of the algorithm is shown in Figure 3:

Embodiment 5: This embodiment is a further description of the reconfiguration method of the reconfigurable 2D mesh on-chip network structure described in Embodiment 4. The default selection connection sequence between the core and the router is upper left, upper right, lower left, and right next order. the

In said step 5, the priority principle for selecting the core connected to the router is: after the connection is made, the routing is located in the order of upper left, upper right, lower left, and lower right of the core connected to it; that is: when there are multiple cores that can be connected to When the route is connected, according to the positional relationship between the route and the core after the connection, select the corresponding core to connect according to the above priority principle. the

We constructed R-mesh structures with core sizes of 4×5, 5×6, 6×7, and 7×8, respectively. The rightmost column serves as the redundant core. We tested the number of damaged cores from 1 to full, and finally obtained the probability of successful reconfiguration under different damaged cores. Each case is randomly injected 1 million times using a random test incentive. The results are shown in Figure 6: when the number of damaged cores is relatively small, the success rate of the reconfiguration algorithm is higher, above 90%. When the number of damaged cores increases, the probability of successful reconfiguration drops significantly. Especially when the network scale is as large as 6×7 and 7×8, the reconfiguration success rate is reduced to 60% or even lower. At this time, it means that the redundancy should be increased to improve the probability of reconfiguration success, such as adding a row of redundancy. the

In order to analyze the reconfiguration capability of the R-mesh structure when the number of damaged cores reaches the limit, we tested the case where the number of damaged cores is equal to the number of redundant cores, and obtained the success rate of reconfiguration in this case. The test results are shown in Figure 7: when the core size is small and the number of damaged cores reaches the limit, the probability of successful reconfiguration is still high, above 70%. When the network size is larger than 6×7, the probability drops to Below 70%, especially when it is 7×8, it reaches 50%. This shows that redundancy needs to be increased to improve the success rate of reconfiguration. For example, when adding a column of redundancy, the success rate increased to over 95%. the

The main purpose of the present invention is to propose a reconfigurable on-chip network structure and design a reconfiguration algorithm suitable for the structure on the premise of ensuring fault tolerance and aiming at the requirement of the upper layer to maintain a unified topology structure. Each core in this architecture implements reconfigurable capabilities by routing connections through a multiplexer. Thus, only the network interface needs to be changed, and no modification of the routed network is required. Design time and design complexity are reduced, and design efficiency is improved. the

Claims (4)

1. reconfigurable 2D mesh network-on-chip structure, is characterized in that, it comprises the individual router of M * N core and (M+1) * (N+1), and M * N core comprises that the core of work is that K * L is individual, and (M * N-K * L) is individual for the core of redundancy;

One of four routers that each core can be adjacent connect: each router and adjacent 4 cores realize mutual communication by MUX MUX and network interface NI,

Described network interface NI comprises bus interface, writes fifo module, reads fifo module, unpacks packetization module and control register, described control register also comprises reshuffles register, reshuffling register comprises reconfiguration status register REC_STA, reshuffles control register REC_CNTL and dummy node number register NODE_NUM

Unpack packetization module, for the normal message of network, unpack or pack, also for packing or unpacking reconfiguration message, and the reconfiguration message by packing or after unpacking writes reconfiguration status register REC_STA;

Reconfiguration status register REC_STA, for according to the reconfiguration message that unpacks, control MUX MUX closed other switch of a way switch disconnect, also for storing the state information of the route that represents that core connects;

MUX MUX, for realizing being connected of core and a router under the control at reconfiguration status register REC_STA;

Reshuffle control register REC_CNTL, the information enabling for storing the transmission of control reconfiguration message;

Dummy node number register NODE_NUM, for storing virtual node number information.

2. reconfigurable 2D mesh network-on-chip structure according to claim 1, is characterized in that, a microplate form of described network interface NI is:

。

3. the method for reconfiguration based on reconfigurable 2D mesh network-on-chip structure claimed in claim 1, is characterized in that, it comprises the steps:

Step 1: the sub-network of selecting a K * L in the route network of (M+1) * (N+1);

Step 2: judge one by one the state of each router in sub-network, described state is divided into following three classes:

State 1, do not exist any core to be connected with this router;

State 2, only exist a core to be connected with this router;

State 3, two of existence and above core are connected with this router;

Step 3: judge the router of the state 1 whether existing in sub-network, if exist, proceed to step 1, reselect sub-network; If do not exist, proceed to step 4;

Step 4: whether judge in sub-network and if exist, by the core connection corresponding with this router of each router in state 2, and to remove described router and connected core in sub-network by the router of existence 2, proceed to step 2; If do not exist, proceed to step 5;

Step 5: whether judge in sub-network the router of existence 3, if exist, each router in state 3 is communicated with a core in described two and above core, and the core of removing described router and be communicated with it in sub-network, proceed to step 2; If do not exist, reshuffled.

4. the method for reconfiguration of reconfigurable 2D mesh network-on-chip structure according to claim 3, is characterized in that, it is the order of upper left, upper right, lower-left, bottom right that the acquiescence of core and router is selected the order of connection.