Are de Bruijn digraphs better than Kautz digraphs?

Pavel Tvrdik

Department of Computer Science and Engineering

Czech Technical University, Praha and Labor. de l’Informatique du Parallelisme Ecole Normale Superieure de Lyon

Abstract

Due to the recent advancements in the technology of massively parallel machines, the construction of interconnection networks (ICNWs) connecting as many computing nodes as possible with given upper bounds on the number of links per processor and on the diameter of the network has become crucially important. Among them, Kautz and de Bruijn (K/B) digraphs have been intensively studied in last few years. The main motivation comes from the fact that they represent the densest infinite family of ICNWs. In this talk I will discuss some of the latest results and known pros and cons of these topologies. In particular, I will concentrate on the following measures:

- connectivity and fault-tolerance

- scalability and expandability

- embeddability of trees and cycles

- contractivity

I will present the latest results showing that while in terms of embeddability of trees and cycles, these graphs are almost equivalent, in terms of connectivity and scalability Kautz digraphs are better, and in terms of contractivity, de Bruijn digraphs are better.

These results improve our understanding of structural and computational characteristics of these closely related networks.