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

作者：Lai Chia Jui; Tsai Chang Hsiung^*; Hsu Hong Chun; Li Tseng Kui

来源：Information Sciences, 2010, 180(24): 5090-5100.

DOI：10.1016/j.ins.2010.08.029

• Interconnection network
• Linear-time algorithm
• Reflected edge label sequence
• Torus embedding
• Mesh embedding
• Hypercube embedding

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 2(m) disjoint k-dimensional tori of size 2(s1) x 2(s2) x ... x 2(sk) each can be embedded in an n-dimensional crossed cube with unit dilation, where each s(i) >= 2, Sigma(k)(i=1) s(i) = n - m, and max(1 <= i <= k){s(i)} >= 3 if n is odd and m = n-3/2; otherwise, max(1 <= i <= k){s(i)} >= 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.

• 出版日期2010-12-15
• 单位东华大学