An Algorithm for One-to-One Mapping Matrix-star Graph into Transposition Graph

행렬-스타 그래프를 전위 그래프에 일-대-일 사상하는 알고리즘

  • cc icon
  • ABSTRACT

    The matrix-star and the transposition graphs are considered as star graph variants that have various merits in graph theory such as node symmetry, fault tolerance, recursive scalability, etc. This paper describes an one-to-one mapping algorithm from a matrix-star graph to a transposition graph using adjacent properties in graph theory. The result show that a matrix-star graph MS2,n can be embedded in a transposition graph T2n with dilation n or less and average dilation 2 or less.


    행렬-스타 그래프와 전위 그래프는 스타 그래프 부류로 그래프 이론 관점에서 노드 대칭성, 고장 허용도, 재귀적 확장성 등 스타그래프의 장점을 가지고 있는 상호연결망이다. 본 논문에서는 그래프 이론의 인접 성질을 이용하여 행렬-스타 그래프와 전위 그래프 사이의 일-대-일 사상 알고리즘을 제안한다. 행렬-스타 그래프가 전위 그래프에 연장율 n 이하에 사상할 수 있음을 보이며, 평균 연장율이 2 이하임을 보인다.

  • KEYWORD

    Algorithm , Interconnection network , Matrix-star graph , One-to-one mapping , Transposition graph

  • Ⅰ. Introduction

    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, Sn, 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 <in. Sn has various good properties such as disjoint paths, fault tolerance, partitionability, and recursive structure. Fig. 1 shows a four-dimensional star graph S4.

    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 MS2,n has the half degrees of a star graph S2n 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 MS2,n and a star graph S2n are each about 3.5n2 and 6n2, 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 S2n and a bubble sort graph B2n embedded into matrix-star graph MS2,n with unit expansion and dilation 5, and a transposition graph T2n into it with expansion 1 and dilation 7. Also, the average dilation of the star graph S2n is smaller than 3 and the bubble sort graph B2n is smaller than 4 [5,11].

    This paper analyzes an embedding algorithm from a matrix-star graph MS2,n to a transposition graph T2n. The matrix-star graph is generally considered a Cayley graph, and our result show that a matrix-star graph MS2,n can be embedded in a transposition graph T2n with dilation n or less and average dilation 2 or less.

    Ⅱ. Definition of Matrix-Star and Transposition Graphs

    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 MS2,n [5], a node v is represented as a 2 × n matrix , which consists of 2n distinct symbols {1, 2, ..., 2n}. In MS2,n, three different types of edges are defined in the following three cases:

    (1) Edge Ci 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 MS2,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, MS2,1 has degree 1 and it is a K2 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 MS2,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 MS2,n is 3.5n+2 or less and the broadcasting time is n2+4n-4 [5].

    An n-dimensional transposition graph Tn [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 Tn is defined by the following formulas, where there are n distinct symbols <N> = {1, 2, .., n}, and a permutation of <N>, P = p1p2...pn, pi ∈ <N>.

    The transposition graph Tn 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 T4.

    Ⅲ. Embedding of Matrix-star Graph into Transposition Graph

    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 MS2,n and a transposition graph T2n. The analysis of embedding is accomplished by examining the dilation using node and adjacent properties between the two graphs MS2,n and T2n. The dilation of embedding is the number of edges required for the shortest path routing from v' to u' in T2n when mapping two adjacent nodes (v and u) of MS2,n onto two nodes (v' and u') in T2n that have the identical addresses as the nodes u and v of MS2,n. Both in a matrix-star graph MS2,n and a transposition graph T2n, 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 <ki, kj, kk>, it is denoted as v = kk(kj(ki(u))). The one-to-one mapping for two adjacent nodes of MS2,n onto the nodes of T2n is accomplished by converting the 1×2n matrix node format of T2n into the 2×n matrix node format of MS2,n. For example, when mapping two adjacent nodes X and X' of MS2,n onto the nodes of T2n, we convert the permutation of node to X = (x1x2...xi...xnxn+1xn+2...xn+i...x2n) 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=(t1t2...ti...tntn+1tn+2... tn+i...t2n) of T2n with the symbol x, and map the node X of MS2,n to a node of T2n that is identical to the permutation of node X.

    Theorem 1. A matrix-star graph MS2,n can be embedded into a transposition graph T2n 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 MS2,n: Edge Ci, E, and R.

    Let node X be (i.e., x1x2x3...xi...xnxn+1xn+2...xn+i...x2n) and an adjacent node of X be X'.

    Case 1. Edge Ci, 2 ≤ in

    In MS2,n, an adjacent node X' to node via edge Ci is . If we convert it into the 1×2n matrix node format of T2n, X' = (xix2x3...x1.. .xnxn+1xn+2...xn+i...x2n). When mapping nodes X and X' in MS2,n onto nodes T(=t1t2t3...ti...tntn+1tn+2...tn+i...t2n) and T'(=tit2t3...t1...tntn+1tn+2...tn+i...t2n) in T2n, this embedding is possible with dilation 1 because nodes T and T' are adjacent to each other via edge T(1, i) in T2n.

    Case 2. Edge R

    In MS2,n, an adjacent node X' to node via edge R is and X' = (xn+1x2x3...xi... xnx1xn+2...xn+i...x2n) if we convert it into the 1×2n matrix node format of T2n. When mapping nodes X and X' in MS2,n onto nodes T(=t1t2t3...ti...tntn+1tn+2...tn+i...t2n) and T'(=tn+1t2t3...ti...tnt1tn+2...tn+i...t2n)inT2n, this embedding is possible with dilation 1 because nodes T and T' are adjacent to each other via edge T(1, n+1) in T2n.

    Case 3. Edge E

    In MS2,n, an adjacent node X' to node via edge E is , and if we convert it into the 1×2n matrix node format of T2n, X' = (xn+1xn+2...xn+i...x2nx1x2...xi...xn), when mapping nodes X and X' in MS2,n onto nodes T(=t1t2t3...ti...tntn+1tn+2... tn+i...t2n) and T'(=tn+1tn+2...tn+i...t2nt1t2...ti...tn) in T2n, we can see that the nodes T and T' in T2n are not adjacent to each other by the edge definition of the transposition graph T2n. 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 T2n. The edge sequence required for routing from node T(=t1t2t3...ti...tntn+1tn+2...tn+i...t2n) to node T'(=tn+1tn+2... tn+i...t2nt1t2...ti...tn) 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 t1 with the (n+1)th symbol tn+1 of T, and exchange the second symbol t2 with the (n+2)th symbol tn+2; next, we swap the third symbol t3 with the (n+3)th symbol tn+3, and repeat this exchanging process until the nth symbol tn is interchanged with the (2n)th symbol t2n of T. Thus, the number of edges required for the routing from node T and node T' in T2n is n, when mapping nodes X and X' in MS2,n onto nodes T(=t1t2t3... ti...tntn+1tn+2...tn+i...t2n) and T'(=tn+1tn+2...tn+i...t2nt1t2...ti...tn) in T2n. Consequently, this embedding is possible with dilation n.

    Corollary 2. A matrix-star graph MS2,n can be embedded into a transposition graph T2n with average dilation of 2 or less.

    Proof. In MS2,n, three different types of edges are existed: (Ci, R, E). The number of nodes adjacent to an arbitrary node via edge Ci 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 MS2,n by the total number of edges. Because the necessary dilation to map node X from all nodes of graph MS2,n via edge Ci or edge R is 1, and the necessary dilation to map node X from all nodes of MS2,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).

    Ⅳ. Conclusion

    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 MS2,n can be embedded in a transposition graph T2n with dilation n or less and average dilation 2 or less. The results mean that various algorithms designed for MS2,n can be executed on T2n efficiently. And the results reported here are expected to be extremely useful for analysis of embeddings among MS2,n and other star graph variants.

  • 1. Kim M., Kim D.-W., Lee H.-O. 2010 “Embedding Algorithms for Star, Bubble-Sort, Rotator-Faber-Moore, and Pancake Graphs,” [Proceedings of the 10th international conference on Algorithms and Architectures for Parallel Processing] P.348-357 google
  • 2. Latifi S., Srimani P. K. 1996 “Transposition Networks as a Class of Fault-Tolerant Robust Networks,” [IEEE Trans. Computers] Vol.45 P.230-238 google doi
  • 3. Ranka S., Wang J., Yeh N. 1993 “Embedding Meshes on the Star Graph,” [Journal of Parallel and Distributed Computing] Vol.19 P.131-135 google doi
  • 4. Akers S. B., Harel D., Krishnamurthy B. 1987 “The Star Graph: An Attractive Alternative to the n-Cube,” [Proceedings of the International Conference on Parallel Processing] P.393-400 google
  • 5. Lee H.-O., Kim J.-S., Park K.-W., Seo J.-H., Oh E. 2005 “Matrix-Star Graphs: A New Interconnection Network Based on Matrix Operations,” [Proceedings of the International Conference on Asia-Pacific Computer Systems Architecture] P.478-487 google
  • 6. Yeh C. H., Varvarigos E. A. 1998 “Macro-Star Networks: Efficient Low-Degree Alternatives to Star Graphs,” [IEEE Trans. Parallel and Distributed Systems] Vol.9 P.987-1003 google doi
  • 7. Chou Z. T., Hsu C. C., Sheu J. P. 1996 “Bubblesort Star graphs: A New Interconnection Network,” [Proceedings of the 9th International conference on Parallel and Distributed Systems] P.41-48 google
  • 8. Lee H.-O., Sim H., Seo J.-H., Kim M. 2010 “Embedding Algorithms for Bubble-Sort, Macro-Star, and Transposition Graphs,” [Proceedings of the 2010 IFIP international conference on Network and parallel computing] P.134-143 google
  • 9. Wu A. Y. 1985 “Embedding of Tree Networks into Hypercubes,” [Journal of Parallel and Distributed Computing] Vol.2 P.238-249 google doi
  • 10. Deng W., Luo Q. 2012 “Embedding Complete Binary Trees into Locally Twisted Cubes,” [Advanced Engineering Forum] Vol.6-7 P.70-75 google doi
  • 11. Kim J.-S., Kim M., Sim H., Lee H.-O. 2011 “Embedding Algorithms for Bubble-Sort, Pancake, and Matrix-Star Graphs,” [Communications in Computer and Information Science] Vol.150 P.243-252 google doi
  • [그림 1.] 스타 그래프 S4
    스타 그래프 S4
  • [그림 2.] 행렬-스타 그래프 MS2,2
    행렬-스타 그래프 MS2,2
  • [그림 3.] 4-차원 전위 그래프 T4
    4-차원 전위 그래프 T4