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 s i ⩾ 2, View the MathML source∑i=1ksi=n-m, and max1⩽i⩽k{s i} ⩾ 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.
The torus is a popular interconnection topology and several commercial multicomputers in use today use the torus as the basis of their communication network. It is also called a wrap-around mesh or a toroidal mesh. Many applications in scientific computing require the use of a multi-dimensional torus. For example, to study the theory of the strong nuclear force, known as quantum chromodynamics (QCD), a 5-dimensional torus connected multicomputer system was deployed at the Jefferson Lab in 2004, and a multicomputer system containing multiple 6-dimensional tori [2] is in construction at various sites such as the Brookhaven National Lab, Columbia University, and University of Edinburgh. Actually, torus-based interconnection networks are deployed in several high performance parallel computers. For instance, there are the iWrap [1] (torus), QCDOC (6D torus) [2], the MIT J-Machine [16](3D mesh), Cray T3D/T3E [17](3D torus), the Mosaic [18], Ametak 2010 [19], and the Tera Parallel Computer [20](torus). Moreover, there are many parallel algorithms with torus-structured and mesh-structured task graphs have been developed [14] and [15].
In addition to torus, several interconnection networks have been proposed for parallel computing and provide many good properties with compared to torus network. The k -ary n -cube is an n -dimensional torus with the same size, k , in each dimension, and the hypercube, which is a 2-ary n -cube; a mesh is a subgraph of a torus. The crossed cube proposed by Efe [5] is one of the most notable variations of hypercube, but some properties of the former are superior to those of the latter. For example, the diameter of the crossed cube is almost the half of that of the hypercube. With regard to embedding abilities of crossed cubes, many interesting results have received considerable attention [3], [4], [6], [7], [8], [9], [10], [11], [13], [22], [23] and [24]. In particular, Fan and Jia [6] found that a mesh of size 2 × 2n−1 is a spanning subgraph of an n -dimensional crossed cube (CQ n), and a family of two disjoint meshes of size 4 × 2n−3 each can be embedded in an CQ n with unit dilation. Recently, Lai and Tsai [12] and [21] proved that an n -dimensional Twisted cube and Möbius cube has the same result that of CQ n, respectively. Dong et al. [3] proved that a family of two (four, respectively) disjoint meshes of size 2 × 2 × 2n−3 (4 × 2 × 2n−5, respectively) each can be embedded in an CQ n with unit dilation. In the same year, Dong et al. [4] also proved more general results that for n ⩾ 4 and View the MathML source1⩽m⩽⌊n2⌋-1, a family of 2m disjoint k -dimensional meshes of size 2s1×2s2×⋯×2sk2s1×2s2×⋯×2sk each can be embedded in an CQ n with unit dilation, where View the MathML source∑i=1ksi=n-m and max1⩽i⩽k{si} ⩾ n − 2m − 1. To our knowledge, the problem of how to embed k-dimensional tori into a crossed cube is open.
In this paper, we investigate the problem of embedding disjoint k -dimensional tori which the size of each dimension is power of 2. It is proved 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 s i ⩾ 2, View the MathML source∑i=1ksi=n-m and max1⩽i⩽k{s i} ⩾ 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.
The rest of this paper is organized as follows. Section 2 introduces notations, definitions and cycle skeletons in CQn that will be used in later. The k-dimensional mesh skeleton is described in first part of Section 3. Indeed, a linear algorithm is proposed to embed a mesh and torus into CQn. Conclusions are given in the final section.
In this paper, we prove that for n ⩾ 6 and View the MathML source1⩽m⩽⌈n2⌉-1, a family of 2m disjoint k -dimensional tori of size 2s1×2s2×⋯×2sk2s1×2s2×⋯×2sk each can be embedded in CQ n with unit dilation, where View the MathML sourcesi⩾2,∑i=1ksi=n-m, and max1⩽i⩽k{s i} ⩾ 3 if n is odd and View the MathML sourcem=n-32; otherwise, max1⩽i⩽k{si} ⩾ n − 2m − 1. Besides, have the following results:
(1)
for n ⩾ 3 and View the MathML source0⩽m⩽⌈n2⌉-1, a family of 2m disjoint k -dimensional meshes of size 2s1×2s2×⋯×2sk2s1×2s2×⋯×2sk each can be embedded in CQ n with unit dilation, whereas View the MathML source∑i=1ksi=n-m and max1⩽i⩽k{si} ⩾ n − 2m − 1, and
(2)
for n ⩾ 3, a family of 2m disjoint k -dimensional hypercubes each can be embedded in CQ n with unit dilation, where View the MathML sourcem⩾⌈n2⌉-1 and k = n − m.
Moreover, we apply the characterization of reflected edge label sequences to build a linear algorithm to embed a mesh, torus, or hypercube into CQn. With our algorithm, many parallel algorithms which are developed for torus network can be efficiently ported to a crossed cube network. In conclusion, a family of disjoint tori (meshes and hypercubes, respectively) can be simulated on the same crossed cube efficiently and in parallel.
