Problem statement
Update 2015-06-01
Definition
The order/degree problem with parameters n and d: Find a graph with minimum diameter over all undirected graphs with the number of vertices = n and degree ≤ d. If two or more graphs take the minimum diameter, a graph with minimum average shortest path length (ASPL) over all graphs with minimum diameter must be found.
Example
Let us show examples for the order/degree problem with parameters n = 16 and d = 4. The figure illustrates three examples of a 4-regular graph with 16 nodes. The diameter of the first and the second graphs is 3, while that of the third one is 4. Thus, we should select the first or the second one. Next, we compare the average shortest path length (ASPL) of these two graphs. Since that of the first one is smaller, this is the best solution of the problem among the three.
|
|
|
|
| Graph |
|
|
|
| Diameter | 3 | 3 | 4 |
| ASPL | 1.942 | 1.983 | 2.133 |
Why order/degree problem?
Graph design has a rich variety of application fileds of computer systems. In particular, it is just meeting a network design of future supercomputers and future high-end datacenters in terms of hop counts [SOCC11] [ISCA12] [SC14], since their networks are topologically modeled as undirected regular graphs. Low latency is preconditioned on small hop counts, but existing network topologies have hop counts much larger than theoretical lower bounds. Therefore, computer network designers desire to find a graph that has a small number of hops between any pair of vertices. The same solution is beneficial for desining such a micro network, though the layout of a graph on two-dimensional surface (on a chip) must be considered [MICRO07] [DATE14] [MICRO14].
Why not degree/diameter problem?
The degree/diameter problem (DDP) has been studied for decades and consists in generating the largest possible graph given degree and diameter constraints, striving to approach theoretical upper bounds [DDP-wiki]. However, DDP solutions may not be directly usable for network topologies in supercomputer and high-end datacenter systems because they are for particular number of compute nodes, whereas the number of nodes in a real system is determined based on practical considerations, e.g., budget.
Lower bound of diameter & ASPL
For a order n and a degree d, a lower bound for the diameter is computed as the lowest value k such that 
.
A lower bound on the ASPL is computed in a similar manner, but weighting each term by path length and averaging over n.
Starting point
A random graph serves as a good baseline of diameter and ASPL for each order/degree pair. The Python script below generates a regular random graph with specified order/degree pair calculating its diameter and ASPL. This may be a good starting point if you are new to creating graphs.
- create-random.py (requires NetworkX)
"create-random.py" is licensed under a Creative Commons Attribution 4.0 International License.
References
- [ISCA12] Michihiro Koibuchi, Hiroki Matsutani, Hideharu Amano, D. Frank Hsu, Henri Casanova: "A Case for Random Shortcut Topologies for HPC Interconnects", The 39th International Symposium on Computer Architecture (ISCA), pp.177-188, June 2012
- [SC15] Maciej Besta, Torsten Hoefler: "Slim Fly: A Cost Effective Low-Diameter Network Topology", SC 2014: 348-359
- [MICRO14] Haofan Yang, Jyoti Tripathi, Natalie Enright Jerger and Dan Gibson: "Dodec: Random-Link, Low-Radix On-Chip Networks", MICRO 2014
- [SOCC11] Ji-Yong Shin, Bernard Wong and Emin Gun Sirer: "Small-World Datacenters", ACM Symposium on Cloud Computing, 2011
- [MICRO07] John Kim, James D. Balfour, William J. Dally: "Flattened Butterfly: Topology for On-Chip Networks", MICRO 2007, pp. 172-182
- [DATE14] Hiroki Matsutani, Michihiro Koibuchi, Ikki Fujiwara, Takahiro Kagami, Yasuhiro Take, Tadahiro Kuroda, Paul Bogdan, Radu Marculescu and Hideharu Amano: "Low-latency wireless 3D NoCs via randomized shortcut chips", DATE 2014
- [DDP-wiki] The Degree/Diameter Problem - Combinatorics Wiki