A dynamic programming algorithm for simulation of a multi-dimensional torus in a crossed cube

The torus is a popular interconnection topology and several commercial multicomputers use a torus as the basis of their communication network. Moreover, there are many parallel algorithms with torus-structured and mesh-structured task graphs have been developed. If one network can embed a mesh or torus network, the algorithms with mesh-structured or torus-structured can also be used in this network. Thus, the problem of embedding meshes or tori into networks is meaningful for parallel computing. In this paper, we prove that for n ⩾ 6 and 1 ⩽ m ⩽ ⌈n/2⌉ − 1, a family of 2m disjoint k-dimensional tori of size 2s1×2s2×⋯×2sk2s1×2s2×⋯×2sk each can be embedded in an n-dimensional crossed cube with unit dilation, where each si ⩾ 2, View the MathML source∑i=1ksi=n-m, and max1⩽i⩽k{si} ⩾ 3 if n is odd and View the MathML sourcem=n-32; otherwise, max1⩽i⩽k{si} ⩾ n − 2m − 1. A new concept, cycle skeleton, is proposed to construct a dynamic programming algorithm for embedding a desired torus into the crossed cube. Furthermore, the time complexity of the algorithm is linear with respect to the size of desired torus. As a consequence, a family of disjoint tori can be simulated on the same crossed cube efficiently and in parallel.