Efficient tilings of de Bruijn and Kautz graphs

Details Efficient tilings of de Bruijn and Kautz graphs Efficient tilings of de Bruijn and Kautz graphs

2011-01-10

arxiv.org/abs/1101.1932v1

Computer Science

Distributed, Parallel, and Cluster Computing

29 pages, 11 figures

Scientific paper

Kautz and de Bruijn graphs have a high degree of connectivity which makes them ideal candidates for massively parallel computer network topologies. In order to realize a practical computer architecture based on these graphs, it is useful to have a means of constructing a large-scale system from smaller, simpler modules. In this paper we consider the mathematical problem of uniformly tiling a de Bruijn or Kautz graph. This can be viewed as a generalization of the graph bisection problem. We focus on the problem of graph tilings by a set of identical subgraphs. Tiles should contain a maximal number of internal edges so as to minimize the number of edges connecting distinct tiles. We find necessary and sufficient conditions for the construction of tilings. We derive a simple lower bound on the number of edges which must leave each tile, and construct a class of tilings whose number of edges leaving each tile agrees asymptotically in form with the lower bound to within a constant factor. These tilings make possible the construction of large-scale computing systems based on de Bruijn and Kautz graph topologies.

Affiliated with

Also associated with

No associations

Rating

Efficient tilings of de Bruijn and Kautz graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient tilings of de Bruijn and Kautz graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient tilings of de Bruijn and Kautz graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-457467