Advanced
An Algorithm for One-to-One Mapping Matrix-star Graph into Transposition Graph
An Algorithm for One-to-One Mapping Matrix-star Graph into Transposition Graph
Journal of the Korea Institute of Information and Communication Engineering. 2014. May, 18(5): 1110-1115
Copyright © 2014, The Korea Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : March 21, 2014
  • Accepted : April 21, 2014
  • Published : May 31, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
종석 김
Department of Computer Science, University of Rochester, Rochester, NY 14627, USA
형옥 이
Department of Computer Education, Sunchon National University, Suncheon, Jonnam 540-742, Korea
oklee@sunchon.ac.kr

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 MS 2,n can be embedded in a transposition graph T 2n with dilation n or less and average dilation 2 or less.
Keywords
Ⅰ. 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 2 n 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 < i n . Sn has various good properties such as disjoint paths, fault tolerance, partitionability, and recursive structure. Fig. 1 shows a four-dimensional star graph S4 .
PPT Slide
Lager Image
스타 그래프 S4 Fig. 1 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.5 n 2 and 6 n 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 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
PPT Slide
Lager Image
, which consists of 2 n distinct symbols {1, 2, ..., 2 n }. 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 :
PPT Slide
Lager Image
(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 :
PPT Slide
Lager Image
(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 :
PPT Slide
Lager Image
Following these definitions, we can see that MS2,n has (2 n )! 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 2 n 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 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.5 n +2 or less and the broadcasting time is n 2 +4 n -4 [5] .
PPT Slide
Lager Image
행렬-스타 그래프 MS2,2 Fig. 2 Matrix-star graph MS2,2
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 = p 1 p 2 ... p n , p i ∈ < N >.
PPT Slide
Lager Image
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 .
PPT Slide
Lager Image
4-차원 전위 그래프 T4 Fig. 3 4-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 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 < ki , kj , kk >, it is denoted as v = kk ( kj ( ki ( 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×2 n 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
PPT Slide
Lager Image
to X = ( x 1 x 2 ... xi ... xn 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 ... ti .. .tn 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 Ci , E , and R .
Let node X be
PPT Slide
Lager Image
(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 Ci , 2 ≤ i n
In MS 2,n , an adjacent node X' to node
PPT Slide
Lager Image
via edge Ci is
PPT Slide
Lager Image
. If we convert it into the 1×2 n matrix node format of T 2n , X' = ( xix2x3 ... 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 ... ti ... tn t n+1 t n+2 ... t n+i ... t 2n ) and T' (= ti t 2 t 3 ... t 1 ... tn 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
PPT Slide
Lager Image
via edge R is
PPT Slide
Lager Image
and X' = ( x n+1 x 2 x 3 ... xi ... xn x 1 x n+2 ... x n+i ... x 2n ) if we convert it into the 1×2 n 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 ... ti ... tn t n+1 t n+2 ... t n+i ... t 2n ) and T' (= t n+1 t 2 t 3 ... ti ... tn t 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, n +1) in T 2n .
Case 3. Edge E
In MS 2,n , an adjacent node X' to node
PPT Slide
Lager Image
via edge E is
PPT Slide
Lager Image
, and if we convert it into the 1×2 n matrix node format of T 2n , X' = ( x n+1 x n+2 ... x n+i ... x 2n x 1 x 2 ... xi ... xn ), when mapping nodes X and X' in MS 2,n onto nodes T (= t 1 t 2 t 3 ... ti ... 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 ... ti ... tn ) 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 ... ti ... tn 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 ... ti ... tn ) is < T (1, n +1), T (2, n +2), T (3, n +3), ..., T ( i , n + i ), ..., T ( n , 2 n ) >; 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 (2 n )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 ... tn 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 ... ti ... tn ) 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: ( Ci , R , E ). The number of nodes adjacent to an arbitrary node
PPT Slide
Lager Image
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 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 Ci 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: {((2 n )! ´ ( n - 1)) / 2} + {(2 n )! / 2} + {((2 n )! ´ n ) / 2} = ((2 n )! ´ 2 n ) / 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 (((2 n )! ´ 2 n ) / 2) / ((2 n )! ´ ( n + 1)) / 2 = 2 n / ( 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 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.
BIO
김종석(Jong-Seok Kim) 컴퓨터과학과 이학박사 ※관심분야 : 상호연결망, 그래프 이론, 계산 이론
이형옥(Hyeong-Ok Lee) 컴퓨터과학과 이학박사 ※관심분야 : 상호연결망, 그래프 이론, 계산 이론
References
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 348 - 357
Latifi S. , Srimani P. K. 1996 “Transposition Networks as a Class of Fault-Tolerant Robust Networks,” IEEE Trans. Computers http://dx.doi.org/10.1109/12.485375 45 (2) 230 - 238    DOI : 10.1109/12.485375
Ranka S. , Wang J. , Yeh N. 1993 “Embedding Meshes on the Star Graph,” Journal of Parallel and Distributed Computing http://dx.doi.org/10.1006/jpdc.1993.1098 19 131 - 135    DOI : 10.1006/jpdc.1993.1098
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 393 - 400
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 478 - 487
Yeh C. H. , Varvarigos E. A. 1998 “Macro-Star Networks: Efficient Low-Degree Alternatives to Star Graphs,” IEEE Trans. Parallel and Distributed Systems http://dx.doi.org/10.1109/71.730528 9 (10) 987 - 1003    DOI : 10.1109/71.730528
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 41 - 48
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 134 - 143
Wu A. Y. 1985 “Embedding of Tree Networks into Hypercubes,” Journal of Parallel and Distributed Computing http://dx.doi.org/10.1016/0743-7315(85)90026-7 2 238 - 249    DOI : 10.1016/0743-7315(85)90026-7
Deng W. , Luo Q. 2012 “Embedding Complete Binary Trees into Locally Twisted Cubes,” Advanced Engineering Forum http://dx.doi.org/10.4028/www.scientific.net/AEF.6-7.70 6-7 70 - 75    DOI : 10.4028/www.scientific.net/AEF.6-7.70
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 http://dx.doi.org/10.1007/978-3-642-20975-8_27 150 243 - 252    DOI : 10.1007/978-3-642-20975-8_27