Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Cycletrees: Flexible Interconnection Graphs for Parallel Computing

Margus Veanes and Jonas Barklund

Abstract

Natural cycletrees, formally defined in this report, is a subclass of Hamiltonian graphs with maximum degree 3 that contain a binary spanning tree. A natural cycletree used as an interconnection network thus supports directly broadcasting through the binary tree as well as nearest ­neighbour communication through the cycle. Natural cycle­ trees have several other interesting properties, e.g., they are planar, easily extensible and can be contracted using the same methods as for binary trees. The two main results of the paper are: (i) Given an arbi­trary basic binary spanning tree, there exists a natural cycletree with a minimal number of edges. (ii) Given a set of vertices, we present an algorithm for constructing a natural cycletree such that it has a min­imal number of edges, its binary spanning tree has the minimal total path length and its structure satisfies a given abstract specification. For example, if we wish to construct a natural cycletree connecting k processing elements, we could invoke the algorithm with a set of k distinct vertices and a simple specification (provided as an example in the paper).

Details

Publication typeTechReport
Number97
SeriesUPMAIL Technical Report
InstitutionUppsala University, Computing Science Department
> Publications > Cycletrees: Flexible Interconnection Graphs for Parallel Computing