A Heuristic (delta, D) Digraph to Interpolate between Hypercube and de Bruijn Topologies for Future On-Chip Interconnection Networks

The paper presents as background several graphs referred to (delta, D) digraphs including the Hypercube and de Bruijn. It shows the major disadvantages when implementing these topologies on chip interconnection networks. Then, the paper presents the "Small-World Heuristic" (SWH), which aims to find a network topology for a large number of nodes that has a maximum out degree and a small diameter, while maintaining an acceptable level of connectivity. It is proposed that this heuristic can be used to determine a compromise between Hypercube and de Bruijn when implementing networks on FPGA or in VLSI.