Communications of the ACM
Serendipity: When Research in One Area Leads to a Positive Result in Another
That's the way it goes sometimes: research in one scientific area can give a positive result for another scientific area.
We are accustomed to the fact that mathematics, as "the queen of the sciences" (K.F. Gauss), usually lays the foundations for other scientific results related to, or even remote from, mathematics. In this short note, we want to talk about the opposite case, when solving the engineering problem of optimizing algorithms (within the framework of the project "Self-organization in networks on a chip: principles, models, routing algorithms, programs, production technologies"), we unexpectedly solved one mathematical task and found a new (in terms of the scope) family of circulant graphs.
Circulant graphs are the subject of research of many mathematical scientists, and, in general, the main families of such graphs are well described. This is especially true for degree four circulants for whose optimal families the formula descriptions have long been found. Now everyone's attention is focused on the search for extreme circulants (analytical expressions for describing the signatures of various families of circulants) and estimating their characteristics, such as diameter, mean path width, bisection width, etc. The problem is that such studies are already so far removed from the real world that their authors do not ask themselves: "Why is this necessary?", and the results obtained essentially remain a pile of articles by mathematicians for mathematicians. Not a mathematician is unlikely to be able to understand this kind of article; an engineer may simply not guess that the problem has a mathematical solution. We believe this situation is harmful, and mathematicians should first of all work on solving problems from the real world, and not look for how to apply their calculations in the real world.
In this note, we want to show a good example of how a rather elegant mathematical solution was born from an engineering problem statement. We provide a justification for the application of the circulant topology for a specific engineering problem. We use the feature of the circulant, which consists in its unique symmetry and invariance of its vertices.
Currently, our research group is developing new topologies and routing algorithms for organizing a communication subsystem in multi-core computing systems, such as networks-on-chip and computing clusters. It should be noted that the problem of finding the order and topology of a graph that has a minimum diameter and a maximum number of vertices is relevant in itself. The solution of this problem can be applied in various fields, but primarily for the construction of various computer networks. The vertices of the graph may contain computational cores, and the edges represent the network connections between them. That is, the main areas of application of this task are networks-on-chip and high-performance clusters.
Let us now dwell on the formal formulation of the problem. Let's assume that we have a system of N computing cores, each of which is connected by connections to four neighbors. It is required to find the topology of the corresponding graph in which the minimum number of hops between any two vertices (diameter) does not exceed the value D and a mathematical equation relating N and D.
We approached the solution of this problem from a purely engineering point of view, starting with assigning a central vertex (root node) and finding the number of vertices in each of the neighborhoods of the selected vertex (Fig. 1). The nearest neighboring vertices of the selected vertex make up the first neighborhood. Their neighbors (not included in the first neighborhood) form the second neighborhood, and so on. The set of vertices, for which the minimum number of transitions along the graph to the central vertex is equal to n, form a n-neighborhood.
Fig. 1. Selection of neighborhoods around the central vertex
From Fig. 1, it follows that:
- only the vertex itself is placed in the zero neighborhood;
- there are 4 vertices in the first neighborhood;
- there are 8 vertices in the second neighborhood;
- there are 12 vertices in the third neighborhood;
- etc.
In general, the n-neighborhood contains 4n vertices, and the total number of vertices N in all D neighborhoods is
L = 2D(D + 1) + 1. (1)
This formula is valid for any infinite graph, where each vertex is connected to four neighbors. In real applications, the graph is bounded, and vertices on the boundary are an exception. As soon as at least one boundary node enters the -neighborhood, the action of equation (1) stops.
The above reasoning shows that from a network point of view, the optimal shape for a chip with a planar mesh topology for the location of computing nodes is a regular rhombus, not a square (Fig. 1). For a rhombus, the maximum number of transitions between any two computational cores will be less than for a square of the same size.
Note that any vertex inside a rhombus of neighborhoods is removed from the central node by no more than n hops along the connectivity graph. To further solve the problem, it is necessary to find such a graph topology in which all vertices are equivalent. In other words, the graph must be invariant under a transformation that takes an arbitrary vertex to any other. A graph with a ring circulant topology has such a symmetry (Fig. 2) [1].
Fig. 2. An example of a circulant C(13; 1,5)
In a ring topology, all vertices are connected in series. The initial vertex of the set is adjacent to the last vertex (s1 = 1). Each vertex of the circulant additionally has links with a shift of several s2 vertices clockwise and counterclockwise. A circulant with an arbitrary number (k) of generators is denoted as C(N; s1, s2,…, sk).
It should be noted that Equation 1 can be used to find the optimal circulant for which, for a given number of nodes N, the graph diameter takes the minimum value D. Optimal circulants should be sought for sets of 13, 25, 41, 61, 85, 113, etc. vertices, which are defined by (1). But to completely fill the rhombus shown in Fig. 1, it is required to find the lengths of the circulant generators s1 and s2, which is not a trivial task.
The search should start with a circulant with D = 2, which has 13 vertices. Let's take the length of the smaller generator equal to 1 (s1 = 1). When iterating over the lengths of the larger generator, the answer is easily found in the form of s2 = 5. Fig. 3 shows the distribution of nodes in the neighborhood for the found circulant.
Fig. 3. Distribution of nodes of the circulant C(13: 1,5) by neighborhoods.
In the Y direction, the number of neighborhoods to the current vertex is plotted along the largest generator s2; and in the X direction – along the smallest s1 (Fig. 3).
Fig. 3 gives a hint on the further search for optimal circulants. Between the largest value 2 in the horizontal diagonal and the smallest value 4 in the second horizontal row, there is an intermediate vertex 3. That is, for the next circulant with 25 vertices and D = 3, the value of the second generator should be greater by 2, and the optimality of a circulant C(25; 1,7) should be tested. Verification shows this circulant is also optimal in terms of having a minimum diameter. The number D from equation 1 in optimal circulants limits the number of transitions along the graph between any two vertices. In other words, for any two arbitrarily chosen vertices of the optimal graph, there can be a route which is shorter than or equal to D.
It is easy to prove by contradiction that in an optimal circulant, there always exists a route connecting two arbitrary nodes with a length less than or equal to the diameter D.
Let us prove the hypothesis put forward above. Suppose that the described condition is not satisfied, and there is a pair of vertices for which only a route with more than D hops can be obtained. We choose the beginning of such a route as a root node and construct the distribution of the circulant to the neighborhood relative to this node. As a result of this distribution, all vertices will fit inside the rhombus, which means that there is a route to each vertex with a length less than or equal to D. Thus, a contradiction arises, which proves the assertion made earlier.
Let us return to the family of optimal circulants and write down an expression for it in an analytical form. Equation (1) determines the number of vertices. The length of the smaller generator is equal to 1 (s1 = 1), and the length of the second generator s2 is 2D + 1. That is, the signature that defines the entire family of graphs that fit most densely in the neighborhood of a rhombus can be written as
C(2D(D + 1) + 1; 1,2D + 1),(2)
where D is a natural number greater than or equal to 2 and representing the diameter of such a graph. For example, if D = 15, there is an optimal circulant of 481 vertices (481; 1,31). Note that the length of the route between the nodes of this circulant (diameter) will not exceed 15 hops between the vertices.
Thus, a graph of diameter D can include at most 2D(D + 1) vertices, provided each vertex is connected to four neighbors. The general solution can be written as a circulant C(2D(D + 1) + 1; 1, 2D + 1).
We checked the signatures of the resulting family of graphs using a dataset of optimal circulants found by optimized greedy search method [2]. And they really are there; moreover, for specific N, these signatures are the only possible ones. Only in comparison with the usual optimal circulants for any N, such graphs are most densely packed; i.e., the vertices fill all places in the vicinity of the central vertex and are geometrically located on the edges of rhombuses (neighborhoods), which opens up many interesting possibilities for developing routing algorithms in them. These graphs are also good because the optimal ring circulant of order N + 1, will already have a diameter greater than 1. The given solution of the problem can be used to describe new topologies of networks-on-chip. And in computing clusters, this solution allows communication without an expensive central switch by increasing the number of network adapters in each of the computing nodes.
Thus, trying to find a solution to an engineering problem, we found a beautiful mathematical decision and were able to describe a very interesting and promising family of circulant graphs. In fact, such graphs have long been described in the literature as extremely optimal circulant graphs [1, 3], but we have not ever seen the description of the family of ring extremely optimal graphs considered here in the scientific literature in an explicit form and in the signature format. If it even existed, without an engineering formulation of the problem, it would remain just a formula.
This task can be offered to students in relevant courses on computing systems and networks. It is simple enough to understand. You can also try to find a generalization of this problem for the case of degree six circulants, that is, for three-dimensional architectures.
References
[1] E. A. Monakhova. 2012. A survey on undirected circulant graphs. Discret. Math. Algorithms Appl. 4, 1 (April 2012), 17–47. DOI: https://doi.org/10.1142/S1793830912500024.
[2] Optimal circulant topologies dataset. DOI: https://doi.org/10.5281/zenodo.7265637.
[3] R. R. Lewis. 2021. Analysis And Construction Of Extremal Circulant And Other Abelian Cayley Graphs. The Open University. DOI: https://doi.org/10.21954/OU.RO.00013612.
Andrei Sukhov ([email protected]) is a senior member of ACM, as well as a Leading Research Fellow of HSE University and Sevastopol State University, Moscow, Russia. Aleksandr Romanov ([email protected]) is an Associate Professor and Head of the CAD Laboratory of HSE University, Moscow, Russia.
No entries found