Interconnection network architectures include a mesh, hypercube, star graphs. They can be categorized into three classes depending on the number of nodes: a star graph with n! nodes, a mesh with n×k nodes, and a hypercube with 2n nodes [1]. Star variations include transposition [2], pancake [3], standard star [4], matrix-star [5], macro-star [6], and bubblesort [7] graph. The overall performance and scalability of a multiple-computer system are significantly influenced by the architecture of the interconnection network. Therefore, the need to further develop interconnection networks is continuously growing with the development of parallel processing computers [8]. Most research on interconnection networks has focused on evaluating the parameters for measuring the performance of networks, including degree, diameter, fault tolerance, embedding, broadcasting, symmetry, and scalability [1,9]. Among these, embedding describes whether a network algorithm developed in an arbitrary interconnection network G can be efficiently executed in another interconnection network H through mapping the processors and communication links of G onto those of H. The common evaluation measurements for embedding are dilation, congestion, and expansion [1,3,8-11].
The n-dimensional star graph, S_{n}, is an edge- and node-symmetric graph containing n! nodes (n-1)n!/2 edges. The nodes are assigned labels each being a distinct permutation of the set of integers {1,2,... ,n}. Two nodes are joined with a link labeled i if and only if the label of one can be obtained from the label of the other by swapping the first digit (conventionally the left most) and the ith digit where 1 <i ≤n. S_{n} has various good properties such as disjoint paths, fault tolerance, partitionability, and recursive structure. Fig. 1 shows a four-dimensional star graph S_{4}.
One of the important interconnection network measures is the network cost. The network cost of an interconnection network is defined as the product of the degree and diameter of the network. The matrix-star graph improves the network cost of the well-known star graph as an interconnection network. The matrix-star graph represents nodes as a matrix form, rather than a vector form. And it defines edges as operations converting matrix. The matrix-star MS_{2,n} has the half degrees of a star graph S_{2n} with the same number of nodes and is an interconnection network with the properties of node symmetry, maximum fault tolerance, and recursive structure, which a star graph also has. In a network cost, a matrix-star graph MS_{2,n} and a star graph S_{2n} are each about 3.5n^{2} and 6n^{2}, which means that the former has a better value by a certain constant than the latter has. Also, in terms of the embedding, we know that a star graph S_{2n} and a bubble sort graph B_{2n} embedded into matrix-star graph MS_{2,n} with unit expansion and dilation 5, and a transposition graph T_{2n} into it with expansion 1 and dilation 7. Also, the average dilation of the star graph S_{2n} is smaller than 3 and the bubble sort graph B_{2n} is smaller than 4 [5,11].
This paper analyzes an embedding algorithm from a matrix-star graph MS_{2,n} to a transposition graph T_{2n}. The matrix-star graph is generally considered a Cayley graph, and our result show that a matrix-star graph MS_{2,n} can be embedded in a transposition graph T_{2n} with dilation n or less and average dilation 2 or less.
An interconnection network can be represented as an undirected graph G = (V, E), where V(G) is a set of nodes and E(G) is a set of edges. Each node and edge of G is presented with a processor and a communication channel between two processors in the interconnection network, respectively. Here, V(G) = {0, 1, 2,
, n–1} and there exists an edge (v, w) between two processors v and w of G if and only if a communication channel between v and w exists [1,5,8].
In a matrix-star graph MS_{2,n} [5], a node v is represented as a 2 × n matrix , which consists of 2n distinct symbols {1, 2, ..., 2n}. In MS_{2,n}, three different types of edges are defined in the following three cases:
(1) Edge C_{i} that connects node v to node w in which the (1, 1)th symbol of v is exchanged with the (1, i)th symbol of v:
(2) Edge E that connects node v to node w in which the first row vector of v is interchanged with second row vector of v:
(3) Edge R that connect node v to node w in which the (1, 1)th symbol of v is swapped with the (2,1)th symbol of v:
Following these definitions, we can see that MS_{2,n} has (2n)! nodes and is a regular graph of degree n+1 (n ≥ 2) because it can generate a matrix with the number of permutations expressed by 2n distinct symbols. However, when n = 1, MS_{2,1} has degree 1 and it is a K_{2} graph consisting of two nodes because the conditions defined in Edge E (2) and Edge R (3) are the same. Fig. 2 shows an example of MS_{2,2}, in which the nodes are represented by 2×2 matrices [11]. The terms node and matrix are interchangeably used in this paper because a node is expressed by a matrix. The diameter of MS_{2,n} is 3.5n+2 or less and the broadcasting time is n^{2}+4n-4 [5].
An n-dimensional transposition graph T_{n} [2] is composed of n! nodes and n(n-1)n!/4 edges. The address of each node is represented as a permutation of n distinct symbols, and there exist an edge between two nodes v and w if and only if the corresponding permutation of the node w is obtained from that of v by exchanging the positions of any two arbitrary symbols from {1, 2, .., n} in v.
A transposition graph T_{n} is defined by the following formulas, where there are n distinct symbols <N> = {1, 2, .., n}, and a permutation of <N>, P = p_{1}p_{2}...p_{n}, p_{i} ∈ <N>.
The transposition graph T_{n} is a regular graph with n(n-1)/2 degree. It is also a node symmetry and bipartite graph. It has maximum fault tolerance because its diameter is n-1, fault diameter is n, and node connectivity is equal to the number of its degree n(n-1)/2 [2,8]. Fig. 3 shows a four-dimensional transposition graph T_{4}.
Embedding entails mapping a specific graph G into another graph H to examine whether G is included in the graph H. Such embedding can be defined by a function f = (ø, ρ), where ø is a function for mapping the set of nodes V(G) in G onto the set of nodes V(H) in H, and ρ is a function for mapping an edge e = (v, w) in G to a path in H that links nodes ø(v) and ø(w). Evaluation parameters for embedding costs include dilation, congestion, and expansion. The dilation of an edge in G is the length of a path ρ(e) in H, the that of embedding f is the maximum value among all edge dilations in G. The congestion of an edge e' in H is the number of ρ(e) included in e', and the congestion of embedding f is the maximum number among all edge congestions in H. The expansion of embedding f is the ratio of the number of nodes in H and G [1,8,11].
In this section, we analyze embedding between a matrix-star graph MS_{2,n} and a transposition graph T_{2n}. The analysis of embedding is accomplished by examining the dilation using node and adjacent properties between the two graphs MS_{2,n} and T_{2n}. The dilation of embedding is the number of edges required for the shortest path routing from v' to u' in T_{2n} when mapping two adjacent nodes (v and u) of MS_{2,n} onto two nodes (v' and u') in T_{2n} that have the identical addresses as the nodes u and v of MS_{2,n}. Both in a matrix-star graph MS_{2,n} and a transposition graph T_{2n}, when a node v is adjacent to an arbitrary node u via an edge k, it is represented as v = k (u). If node v is reached from node u by sequentially applying an edge sequence <k_{i}, k_{j}, k_{k}>, it is denoted as v = k_{k}(k_{j}(k_{i}(u))). The one-to-one mapping for two adjacent nodes of MS_{2,n} onto the nodes of T_{2n} is accomplished by converting the 1×2n matrix node format of T_{2n} into the 2×n matrix node format of MS_{2,n}. For example, when mapping two adjacent nodes X and X' of MS_{2,n} onto the nodes of T_{2n}, we convert the permutation of node to X = (x_{1}x_{2}...x_{i}...x_{n}x_{n+1}x_{n+2}...x_{n+i}...x_{2n}) by attaching the second row vector of X to its first row vector; X' is converted in the same way. Then we replace the symbol t, which consists of a node T=(t_{1}t_{2}...t_{i}...t_{n}t_{n+1}t_{n+2}... t_{n+i}...t_{2n}) of T_{2n} with the symbol x, and map the node X of MS_{2,n} to a node of T_{2n} that is identical to the permutation of node X.
Theorem 1. A matrix-star graph MS_{2,n} can be embedded into a transposition graph T_{2n} with dilation n or less.
Proof. We analyze this embedding by dividing into three cases based on three different types of edges defined in a matrix-star graph MS_{2,n}: Edge C_{i}, E, and R.
Let node X be (i.e., x_{1}x_{2}x_{3}...x_{i}...x_{n}x_{n+1}x_{n+2}...x_{n+i}...x_{2n}) and an adjacent node of X be X'.
Case 1. Edge C_{i}, 2 ≤ i ≤ n
In MS_{2,n}, an adjacent node X' to node via edge C_{i} is . If we convert it into the 1×2n matrix node format of T_{2n}, X' = (x_{i}x_{2}x_{3}...x_{1}.. .x_{n}x_{n+1}x_{n+2}...x_{n+i}...x_{2n}). When mapping nodes X and X' in MS_{2,n} onto nodes T(=t_{1}t_{2}t_{3}...t_{i}...t_{n}t_{n+1}t_{n+2}...t_{n+i}...t_{2n}) and T'(=t_{i}t_{2}t_{3}...t_{1}...t_{n}t_{n+1}t_{n+2}...t_{n+i}...t_{2n}) in T_{2n}, this embedding is possible with dilation 1 because nodes T and T' are adjacent to each other via edge T(1, i) in T_{2n}.
Case 2. Edge R
In MS_{2,n}, an adjacent node X' to node via edge R is and X' = (x_{n+1}x_{2}x_{3}...x_{i}... x_{n}x_{1}x_{n+2}...x_{n+i}...x_{2n}) if we convert it into the 1×2n matrix node format of T_{2n}. When mapping nodes X and X' in MS_{2,n} onto nodes T(=t_{1}t_{2}t_{3}...t_{i}...t_{n}t_{n+1}t_{n+2}...t_{n+i}...t_{2n}) and T'(=t_{n+1}t_{2}t_{3}...t_{i}...t_{n}t_{1}t_{n+2}...t_{n+i}...t_{2n})inT_{2n}, this embedding is possible with dilation 1 because nodes T and T' are adjacent to each other via edge T(1, n+1) in T_{2n}.
Case 3. Edge E
In MS_{2,n}, an adjacent node X' to node via edge E is , and if we convert it into the 1×2n matrix node format of T_{2n}, X' = (x_{n+1}x_{n+2}...x_{n+i}...x_{2n}x_{1}x_{2}...x_{i}...x_{n}), when mapping nodes X and X' in MS_{2,n} onto nodes T(=t_{1}t_{2}t_{3}...t_{i}...t_{n}t_{n+1}t_{n+2}... t_{n+i}...t_{2n}) and T'(=t_{n+1}t_{n+2}...t_{n+i}...t_{2n}t_{1}t_{2}...t_{i}...t_{n}) in T_{2n}, we can see that the nodes T and T' in T_{2n} are not adjacent to each other by the edge definition of the transposition graph T_{2n}. Thus, we analyze the dilation of this embedding using the number of edges used for the shortest path routing from node T to node T' in T_{2n}. The edge sequence required for routing from node T(=t_{1}t_{2}t_{3}...t_{i}...t_{n}t_{n+1}t_{n+2}...t_{n+i}...t_{2n}) to node T'(=t_{n+1}t_{n+2}... t_{n+i}...t_{2n}t_{1}t_{2}...t_{i}...t_{n}) is < T(1, n+1), T(2, n+2), T(3, n+3), ..., T(i, n+i), ..., T(n, 2n) >; that is, we swap the first symbol t_{1} with the (n+1)th symbol t_{n+1} of T, and exchange the second symbol t_{2} with the (n+2)th symbol t_{n+2}; next, we swap the third symbol t_{3} with the (n+3)th symbol t_{n+3}, and repeat this exchanging process until the nth symbol tn is interchanged with the (2n)th symbol t_{2n} of T. Thus, the number of edges required for the routing from node T and node T' in T_{2n} is n, when mapping nodes X and X' in MS_{2,n} onto nodes T(=t_{1}t_{2}t_{3}... t_{i}...t_{n}t_{n+1}t_{n+2}...t_{n+i}...t_{2n}) and T'(=t_{n+1}t_{n+2}...t_{n+i}...t_{2n}t_{1}t_{2}...t_{i}...t_{n}) in T_{2n}. Consequently, this embedding is possible with dilation n.
Corollary 2. A matrix-star graph MS_{2,n} can be embedded into a transposition graph T_{2n} with average dilation of 2 or less.
Proof. In MS_{2,n}, three different types of edges are existed: (C_{i}, R, E). The number of nodes adjacent to an arbitrary node via edge C_{i} is n-1, and the number of nodes adjacent to node X via edge E or edge R is 1. Therefore, we can obtain an average dilation by dividing the sum of the total dilation of the all nodes in MS_{2,n} by the total number of edges. Because the necessary dilation to map node X from all nodes of graph MS_{2,n} via edge C_{i} or edge R is 1, and the necessary dilation to map node X from all nodes of MS_{2,n} via edge E is n, the sum of the total dilation can be expressed as follows: {((2n)! ´ (n - 1)) / 2} + {(2n)! / 2} + {((2n)! ´ n) / 2} = ((2n)! ´ 2n) / 2. Therefore, the average dilation is approximately 2 or less, because it results from the division of the total dilation by the total number of edges and is equal to (((2n)! ´ 2n) / 2) / ((2n)! ´ (n + 1)) / 2 = 2n / (n + 1).
In this paper, we have described a one-to-one mapping method between a matrix-star graph and a transposition graph using adjacent properties in graph theory, and analyzed the dilation that results from this mapping. Our result indicated that a matrix-star graph MS_{2,n} can be embedded in a transposition graph T_{2n} with dilation n or less and average dilation 2 or less. The results mean that various algorithms designed for MS_{2,n} can be executed on T_{2n} efficiently. And the results reported here are expected to be extremely useful for analysis of embeddings among MS_{2,n} and other star graph variants.