JP2017091460A - Compute node network system - Google Patents

Abstract

[Problem] To provide a computation node network system with a network diameter as small as possible. [Solution] The computation node network system (100A) comprises a plurality of computation nodes (10) arranged two-dimensionally to fit within a rectangular area (30), and a plurality of communication links (20) connecting any of the plurality of computation nodes (10), each of the plurality of computation nodes (10) being arranged at a lattice point of a virtual first grid (40), each of the plurality of communication links (20) being wired along a virtual second grid (50), the orientation of the first grid (40) and the orientation of the second grid (50) being the same, and the first grid (40) and the second grid (50) being inclined at 45° with respect to the rectangular area (30). [Selected Figure] Figure 1

Description

  The present invention relates to a computing node network system in which a plurality of computing nodes are connected by communication links.

  A network that connects components such as memory, storage, and processor cores of a computer system as processor cores and computer system massively parallel (within a chip: tens of cores, between chips: 100,000 nodes) The ratio of the performance given to the entire computing system by the communication delay of the interconnection network is increasing. For example, many multi-core parallel applications in next-generation high performance systems are expected to require Message Passing Interface (MPI) communication delays of several hundred nanoseconds to 1 microsecond. Further, regarding the (packet) network in the many-core processor chip, the communication delay between the processor cores and the communication delay with the L2 cache are required to be several cycles at most. How should these designs interconnect efficiently between cores? We are faced with the problem of designing the network configuration (hereinafter referred to as network topology).

  One effective method for reducing the communication delay of the interconnection network between chips and within the chip is to employ a network topology having a small diameter and average shortest path length. In fact, it has been reported from simulation and analysis results that the performance of many parallel applications is improved by adopting a network topology with a small diameter and average shortest path length both inside and between chips. Interestingly, the dominant graphs are those with randomness (eg, topologies with random shortcut links added to links).

  When a random topology is actually used in an on-chip network or a supercomputer, there are restrictions on the communication link length. For example, in an on-chip network, the link delay of metal wiring is ideally 50 ps / mm or less in a 65 nm process. Therefore, it is necessary to keep the wiring length suitable for the operating frequency. In addition, in a chip-to-chip network, a link bandwidth of 40 Gbps or more is becoming a standard. In this case, the electric cable is limited to 7 m for InfiniBand and 5 m for Ethernet (registered trademark). When emphasizing the soft error rate such as bit corruption, the cable length becomes even shorter. Non-Patent Document 1 below discloses a random topology generation algorithm.

Daisuke Takafuji, Kei Fujita, Hiroki Nakano, Kazuaki Fujiwara, Kaoru Shindo, “Improvement of Random Topology Generation Algorithm”, IEICE Technical Report, IEICE, August 2015, 115, 174, p. .217-221

  FIG. 7 is a plan view schematically showing a conventional computing node network system. In the conventional computing node network system, a plurality of computing nodes 10 are arranged at lattice points of a virtual grid 40 in the rectangular region 30, and arbitrary computing nodes 10 are virtual grids 50 (substantially the same as the grid 40). Connected by a communication link 20 wired along the grid. For example, in FIG. 7, 8 × 8 = 64 calculation nodes 10 are arranged in a grid.

  In general, there is a problem that the link distance between the calculation nodes located diagonally is the longest in the calculation node network system. For example, in the calculation node network system shown in FIG. 7, the link distance between the upper left calculation node 10 and the lower right calculation node 10 is the longest. Therefore, when the communication link length is severely limited, the number of hops between these nodes is very likely to be a diameter (also referred to as a network diameter). Since the maximum communication delay increases as the network diameter increases, it is desirable that the network diameter be as small as possible.

  In view of the above problems, an object of the present invention is to provide a computation node network system in which the network diameter is as small as possible.

  A calculation node network system according to one aspect of the present invention includes a plurality of calculation nodes arranged two-dimensionally so as to fit in a rectangular area, and a plurality of communication links connecting any of the plurality of calculation nodes. Each of the plurality of calculation nodes is arranged at a lattice point of the virtual first grid, each of the plurality of communication links is wired along the virtual second grid, and the rectangular area is vertically and horizontally At least two of the three directions, the direction of the first grid and the direction of the second grid, are different from each other.

  According to this, the longest link distance between calculation nodes can be made shorter than before, and the diameter of the network can be reduced.

  For example, the direction of the first grid and the direction of the second grid coincide with each other, and the first grid and the second grid are inclined by 45 ° with respect to the rectangular region.

  Alternatively, the vertical and horizontal directions of the rectangular area coincide with the orientation of the first grid, and the second grid is inclined 45 ° with respect to the rectangular area and the first grid.

  Alternatively, the vertical and horizontal directions of the rectangular area coincide with the orientation of the second grid, and the first grid is inclined 45 ° with respect to the rectangular area and the second grid.

  In addition, it is preferable that a plurality of communication links are obtained by repeatedly replacing any communication link locally so that the network diameter and the average number of hops are reduced after the network is randomly configured. .

  According to the present invention, it is possible to realize a computation node network system in which the network diameter is as small as possible. Thereby, the communication delay between the calculation nodes in a calculation node network system can be made small.

The top view which shows typically the calculation node network system which concerns on the 1st Embodiment of this invention The top view which shows typically the calculation node network system which concerns on the 2nd Embodiment of this invention The top view which shows typically the calculation node network system which concerns on the 3rd Embodiment of this invention The top view which shows typically the calculation node network system which concerns on the 4th Embodiment of this invention Wiring optimization process flowchart The figure explaining exchange of two communication links A plan view schematically showing a conventional computing node network system

  Hereinafter, embodiments will be described in detail with reference to the drawings as appropriate. However, more detailed explanation than necessary may be omitted. For example, detailed descriptions of already well-known matters and repeated descriptions for substantially the same configuration may be omitted. This is to avoid the following description from becoming unnecessarily redundant and to facilitate understanding by those skilled in the art.

  In addition, the inventors provide the accompanying drawings and the following description in order for those skilled in the art to fully understand the present invention, and these are intended to limit the subject matter described in the claims. is not. Moreover, the size of each element drawn in the drawings, the detailed shape of the details, and the like may differ from the actual ones.

<< First Embodiment >>
FIG. 1 is a plan view schematically showing a computation node network system according to the first embodiment of the present invention. The computing node network system 100A according to the present embodiment includes a plurality of computing nodes 10 that are two-dimensionally arranged so as to fit in a rectangular area 30 and a plurality of communication links 20 that connect any of these computing nodes 10 together. Prepare. For convenience, only a few communication links 20 are depicted in FIG. 1, but more communication links 20 are actually wired. In addition, the communication link 20 passing over the calculation node 10 is not connected to the calculation node 10.

  The computing node network system 100A is specifically a supercomputer, NoC (network on chip), or the like. In the case of a supercomputer, the computation node 10 corresponds to an individual rack that houses a system board on which a CPU, a memory, and the like are mounted, a magnetic disk device, a power supply device, an I / O system board (switch device), a cooling mechanism, and the like. . A supercomputer is configured by regularly arranging several hundred such racks in a computer room. In the case of NoC, the calculation node 10 corresponds to an individual processor core on which an arithmetic circuit, a logic circuit, a cache memory, a communication port (switch circuit), and the like are mounted. The NoC is configured by regularly arranging hundreds of such processor cores on a semiconductor substrate.

  In the computation node network 100A, each computation node 10 (specifically, a rack or a processor core) is arranged at a grid point of the virtual grid 40. Here, the grid 40 is inclined 45 ° with respect to the vertical and horizontal directions of the rectangular region 30.

  The communication link 20 is wired along a virtual grid 50. In the case of a supercomputer, the communication link 20 corresponds to an optical fiber or an electric cable. In the case of NoC, the communication link 20 corresponds to a metal wiring or the like. Here, the grid 50 is also inclined by 45 ° with respect to the vertical and horizontal directions of the rectangular region 30, and the grid 50 and the grid 40 are substantially the same grid.

  That is, in the calculation node network 100A, the orientation of the grid 40 that is the reference for the arrangement of the calculation nodes 10 and the orientation of the grid 50 that is the reference for the wiring of the communication link 20 are the same, and the grid 40 and the grid 50 are rectangular regions. It is inclined 45 ° with respect to 30.

  According to the present embodiment, the two diagonal computation nodes 10 that are most distant from each other in the computation node network system 100A can be connected by a diagonal line. As a result, the longest link distance between the computation nodes can be reduced to 1 / √2 (about 70%) compared to the conventional method.

  In the present embodiment, any of the calculation nodes 10 can connect the communication link 20 to the vertical or horizontal side of the substantially square in plan view, that is, to the side portion of the calculation node 10. Generally, since the outlet of the communication link 20 is arranged in the side part of the calculation node 10 in the calculation node 10, it is preferable that the communication link 20 be connectable to the side part of the calculation node 10 as described above. That is.

<< Second Embodiment >>
FIG. 2 is a plan view schematically showing a computation node network system 100B according to the second embodiment. The computing node network system 100B according to the present embodiment includes a plurality of computing nodes 10 that are two-dimensionally arranged so as to fit in a rectangular area 30 and a plurality of communication links 20 that connect any of these computing nodes 10 together. Prepare. For convenience, only a few communication links 20 are illustrated in FIG. 2, but more communication links 20 are actually wired. In addition, the communication link 20 passing over the calculation node 10 is not connected to the calculation node 10.

  The computing node network system 100B is specifically a super computer, NOC, or the like. In the computation node network 100B, each computation node 10 (specifically, a rack or a processor core) is arranged at a lattice point of the virtual grid 40. Here, the orientation of the grid 40 coincides with the vertical and horizontal directions of the rectangular region 30.

  The communication link 20 is wired along a virtual grid 50. Here, the grid 50 is a grid that obliquely connects the lattice points of the grid 40, and is inclined 45 ° with respect to the rectangular region 30 and the grid 40.

  That is, in the calculation node network 100B, the vertical and horizontal directions of the rectangular area 30 where the plurality of calculation nodes 10 are arranged and the orientation of the grid 40 which is the reference for the arrangement of the calculation nodes 10 match, and the wiring of the communication link 20 The reference grid 50 is inclined 45 ° with respect to the rectangular region 30 and the grid 40.

  In this embodiment, since it is necessary to connect the communication link 20 to the corner of the calculation node 10, the connection of the communication link 20 to the calculation node 10 is complicated compared to the first embodiment. In the node network system 100B, the two diagonal computation nodes 10 that are the farthest away can be connected by a diagonal line. As a result, the longest link distance between the computation nodes can be reduced to 1 / √2 (about 70%) compared to the conventional method.

  In particular, in this embodiment, since the arrangement of the calculation nodes 10 is the same grid as the conventional configuration, the arrangement of the calculation nodes 10 in the conventional calculation node network system remains unchanged, and the wiring pattern of the communication link 20 is changed. The conventional computing node network system can be changed to the computing node network system 100B according to the present embodiment. For example, the effect of reducing the longest link distance between calculation nodes can be obtained by simply wiring the communication link 20 as in the present embodiment without changing the rack arrangement in an existing supercomputer.

<< Third Embodiment >>
FIG. 3 is a plan view schematically showing a computation node network system according to the third embodiment of the present invention. The computation node network system 100C according to the present embodiment includes a plurality of computation nodes 10 that are two-dimensionally arranged so as to fit in a rectangular area 30 and a plurality of communication links 20 that connect any of these computation nodes 10 together. Prepare. For convenience, only a few communication links 20 are depicted in FIG. 3, but more communication links 20 are actually wired. In addition, the communication link 20 passing over the calculation node 10 is not connected to the calculation node 10.

  The computing node network system 100C is specifically a supercomputer, NOC, or the like. In the calculation node network 100 </ b> C, each calculation node 10 (specifically, a rack or a processor core) is arranged at a lattice point of the virtual grid 40. Here, the grid 40 is inclined 45 ° with respect to the vertical and horizontal directions of the rectangular region 30.

  The communication link 20 is wired along a virtual grid 50. Here, the grid 50 is a grid that diagonally connects the grid points of the grid 40, and the orientation of the grid 50 coincides with the vertical and horizontal directions of the rectangular region 30.

  In other words, in the computation node network 100C, the vertical and horizontal directions of the rectangular area 30 where the plurality of computation nodes 10 are arranged and the orientation of the grid 50 serving as a reference for the wiring of the communication link 20 are the same. The reference grid 40 is inclined 45 ° with respect to the rectangular region 30 and the grid 50.

  In this embodiment, since it is necessary to connect the communication link 20 to the corner of the calculation node 10, the connection of the communication link 20 to the calculation node 10 is complicated as compared with the first embodiment. It is possible to increase the number of computing nodes 10 that can be connected with the communication link length of. That is, in the present embodiment and the first embodiment, eight calculation nodes 10 are arranged around a certain calculation node 10, but in the first embodiment, the calculation can be connected with the minimum communication link length. Whereas the number of nodes 10 is four, in the present embodiment, it is possible to connect to all eight surrounding calculation nodes 10 with a minimum communication link length. Thereby, the average number of hops can be reduced.

<< Fourth Embodiment >>
FIG. 4 is a plan view schematically showing a computation node network system according to the fourth embodiment of the present invention. The computation node network system 100D according to the present embodiment includes a plurality of computation nodes 10 that are two-dimensionally arranged so as to fit in the rectangular area 30 and a plurality of communication links 20 that connect any of these computation nodes 10 together. Prepare. For convenience, only a few communication links 20 are illustrated in FIG. 4, but more communication links 20 are actually wired. In addition, the communication link 20 passing over the calculation node 10 is not connected to the calculation node 10.

  Specifically, the computation node network system 100D is a supercomputer, NOC, or the like. In the computation node network 100D, each computation node 10 (specifically, a rack or a processor core) is arranged at a grid point of the virtual grid 40. Here, the grid 40 is inclined approximately 18.5 ° with respect to the vertical and horizontal directions of the rectangular region 30.

  The communication link 20 is wired along a virtual grid 50. Here, the grid 50 is a grid that obliquely connects the lattice points of the grid 40, and is inclined 45 ° with respect to the grid 40 and approximately 26.5 ° with respect to the rectangular region 30.

  That is, in the calculation node network 100D, the vertical and horizontal directions of the rectangular area 30 in which the plurality of calculation nodes 10 are arranged, the orientation of the grid 40 that is the reference for the arrangement of the calculation nodes 10, and the grid 50 that is the reference for the wiring of the communication link 20 The three directions are different from each other.

  In the present embodiment, as in the first embodiment, any of the calculation nodes 10 may connect the communication link 20 to the vertical side or the horizontal side of the substantially square in plan view, that is, the side portion of the calculation node 10. it can. Furthermore, in the present embodiment, the number of computing nodes 10 that can be connected with the minimum communication link length can be increased as compared with the first embodiment. That is, in the present embodiment and the first embodiment, eight calculation nodes 10 are arranged around a certain calculation node 10, but in the first embodiment, the calculation can be connected with the minimum communication link length. Whereas the number of nodes 10 is four, in the present embodiment, it is possible to connect to all eight surrounding calculation nodes 10 with a minimum communication link length. Thereby, the average number of hops can be reduced.

  As described above, according to the first to fourth embodiments, it is possible to shorten the longest link distance between computation nodes or reduce the average number of hops in the computation node network. Thereby, the diameter of the network in a calculation node network system can be made as small as possible.

≪Wiring optimization≫
In general, a computing node network system is defined by computing nodes and communication links, and is represented by nodes and edges, respectively, in graph theory. The performance of the computing node network system is evaluated by the network diameter and ASPL (Average Shortest Path Length) (average shortest path length or average number of hops). The diameter is the maximum value of the minimum number of hops between nodes. The average number of hops is an average value of the minimum number of hops between all nodes.

  Since the communication delay becomes large when the communication link is long, an upper limit is set for the communication link length. For example, in order to achieve a transmission speed of 40 Gbps using an electric cable in a supercomputer, it is said that the limit of the communication link length is 7 m. Therefore, when communication is performed between remote nodes that are not directly connected by a communication link, it is necessary to perform communication via another node (hop). However, as the number of vias (the number of hops) increases, the delay between nodes increases and the power consumption also increases. Therefore, it is desirable to reduce both the diameter and the average number of hops in the computation node network system.

  Therefore, a wiring optimization algorithm that reduces both the diameter and the average number of hops in the computation node network system is disclosed. FIG. 5 is a flowchart of the wiring optimization process. The wiring optimization process can be executed using a computer (not shown).

  First, a communication link is randomly set in the computation node network system (S1). However, the upper limit of the communication link length and the number of ports of the calculation node should not be exceeded. In general, it is known that such a random network is an excellent wiring if there is no length restriction on the communication link, but if the communication link has a strong length restriction, the random network is not so good.

  When the random network is completed, any two communication links are selected (S2). Then, two communication links that are alternative candidates for the two selected communication links are set (S3).

  FIG. 6 is a diagram for explaining replacement of two communication links. Assume that two communication links L1 and L2 are selected in step S2. The communication link L1 is a link that connects the calculation node A and the calculation node B. The communication link L2 is a link connecting the calculation node C and the calculation node D. In this case, two communication links L3 and L4 are set as alternative candidates. The communication link L3 is a link that connects the calculation node A and the calculation node C. The communication link L4 is a link that connects the calculation node B and the calculation node D.

  Returning to FIG. 5, when the two communication links selected in step S <b> 2 are replaced with two alternative communication links set in step S <b> 3, it is determined whether the communication link length restriction condition is satisfied. Each calculation node has a limit on the number of communication links that can be connected, that is, the number of ports. However, if the communication link is replaced as shown in FIG. 6, the communication link connected to each calculation node before and after the replacement. Since the number does not change, it is not necessary to consider the limitation on the number of ports.

  If the communication link length restriction condition is not satisfied, i.e., replacement with two alternative communication links exceeds the upper limit of the communication link (NO in S4), the process returns to step S2. , Select another two communication links. On the other hand, if the communication link length restriction condition is satisfied (YES in S4), the network diameter and the average number of hops are calculated for the calculation node network system after replacement with the two alternative communication links (S5). ).

  Then, it is determined whether or not the network diameter and average hop count calculated in step S5 are smaller than the network diameter and average hop count of the calculation node network system before replacement with the two alternative communication links. If not smaller (NO in S6), the process returns to step S2 to select another two communication links. On the other hand, if the two communication links are replaced so that both the network diameter and the average number of hops are smaller than before (YES in S6), the two communication links selected in step S2 (in the example of FIG. 6) The communication links L1 and L2) are deleted, two alternative communication links (communication links L3 and L4 in the example of FIG. 6) set in step S3 are adopted, and the process returns to step S2 and two new communication links Select.

  By repeating the above steps, the diameter and average hop count of the computation node network system converge to the local minimum value.

  Next, an example is shown in which each type of calculation node network system of the conventional configuration (see FIG. 7), the first embodiment, and the second embodiment is wired with the above-described wiring optimization algorithm. In each example, the communication link length when two adjacent calculation nodes are connected is assumed to be 1 unit, and the upper limit of the communication link length is assumed to be 4 units. In addition, the maximum number of ports of each calculation node is four.

≪Comparative example≫
In the comparative example, a conventional type (see FIG. 7) computing node network system is configured using 32 × 32 = 1024 computing nodes. When a random network was formed in the computation node network system according to the comparative example, the diameter was 23 and the average number of hops was 9.576506. When the above wiring optimization algorithm was applied to such a random network, the diameter decreased to 16 and the average number of hops decreased to 6.68486. This diameter is an optimum value in a computation node network system composed of 32 × 32 = 1024 computation nodes.

Example 1
In Example 1, the computation node network system of the type of the first embodiment was configured using 23 × 46 = 1058 computation nodes. When the computation node network system according to Example 1 was wired with the above-described wiring optimization algorithm, the diameter was 12 and the average number of hops was 6.790274.

  When Example 1 is compared with the comparative example, the diameter is small although the number of calculation nodes is slightly larger than that of the comparative example. This diameter is an optimum value in the calculation node network system of the type of the first embodiment composed of 23 × 46 = 1058 calculation nodes.

<< Example 2 >>
In Example 1, the computation node network system of the type of the second embodiment was configured using 32 × 32 = 1024 computation nodes. When the computation node network system according to Example 2 was wired with the above-described wiring optimization algorithm, the diameter was 11 and the average hop count was 6.604497. Strictly speaking, in the second embodiment, the upper limit of the length of the communication link is 3√2 (approximately 4.2) for convenience of wiring the communication link diagonally.

  When Example 2 is compared with the comparative example, the diameter is small even if the number of calculation nodes is the same as that of the comparative example. This diameter is the optimum value in the calculation node network system of the type of the second embodiment composed of 32 × 32 = 1024 calculation nodes.

  As described above, the embodiments have been described as examples of the technology in the present invention. For this purpose, the accompanying drawings and detailed description are provided.

  Accordingly, among the components described in the accompanying drawings and the detailed description, not only the components essential for solving the problem, but also the components not essential for solving the problem in order to illustrate the above technique. May also be included. Therefore, it should not be immediately recognized that these non-essential components are essential as those non-essential components are described in the accompanying drawings and detailed description.

  For example, the planar view shape of the calculation node 10 does not have to be substantially square, and may be rectangular. Moreover, the arrangement intervals of the calculation nodes 10 do not have to be equal. For example, the column spacing may be wider than the row spacing. Therefore, the inclination of the grid 40 does not need to be 45 degrees. You may change the inclination of the grid 40 according to the planar view shape and arrangement | positioning space | interval of the calculation node 10. FIG.

  Moreover, since the above-mentioned embodiment is for demonstrating the technique in this invention, a various change, replacement, addition, abbreviation, etc. can be performed in a claim or its equivalent range.

100A, 100B, 100C Computing node network system 10 Computing node 20 Communication link 30 Rectangular area 40 Grid (first grid)
50 grid (second grid)

Claims (7)

A plurality of calculation nodes arranged two-dimensionally to fit in a rectangular area;
A plurality of communication links connecting any one of the plurality of computing nodes;
Each of the plurality of computation nodes is arranged at a grid point of a virtual first grid;
Each of the plurality of communication links is wired along a virtual second grid;
A computing node network system, wherein at least two of three directions of a vertical and horizontal directions of the rectangular region, a direction of the first grid, and a direction of the second grid are different from each other. The orientation of the first grid and the orientation of the second grid match,
The computing node network system according to claim 1, wherein the first grid and the second grid are inclined by 45 ° with respect to the rectangular region. The vertical and horizontal directions of the rectangular area coincide with the orientation of the first grid,
The computing node network system according to claim 1, wherein the second grid is inclined at 45 ° with respect to the rectangular area and the first grid. The vertical and horizontal directions of the rectangular area coincide with the orientation of the second grid,
The computing node network system according to claim 1, wherein the first grid is inclined by 45 ° with respect to the rectangular area and the second grid.   The plurality of communication links are obtained by repeatedly replacing arbitrary communication links locally so that the network diameter and the average number of hops are reduced after the network is randomly formed. The computing node network system according to claim 4.   6. The computing node network system according to claim 1, wherein the computing node is an individual rack constituting a supercomputer.   6. The computing node network system according to claim 1, wherein the computing node is an individual processor core in NoC (network on chip).

Images