Cycletrees: Flexible Interconnection Graphs for Parallel Computing

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).