文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Embedding Algorithm Between the Macro-star
侵权投诉

Embedding Algorithm Between the Macro-star

The Macro-star graph which has the star graph as a basic module has node symmetry, maximum fault tolerance, and hierarchical decomposition property. And, it is an interconnection network which improves a network cost against the star graph. A Matrix-star g

The communication between the processor is processed by the message transaction method through interconnection network. The multi-computer interconnection networks affected to the performance and extensibility of total system[5].

Such interconnection network is usually modeled as an undirected graph where the set of nodes represents the processors and the set of edges represents the bidirectional communication links between the processors. The network estimation to test the interconnection networks is network costs[11,12], which multiply degree by diameter. Interconnection networks are classified by the number of nodes, such as meshes[5,10] with k×n nodes, hypercubes[10,11] with 2n nodes, star graphs[2,3] with n! nodes.

The star graph has lower degree and smaller diameter than the hypercube, but it has limitations which the embedding with other networks is difficult and with the increase of node by increasing the dimension is very large. Therefore SCC[8], (n,k)-star graph[3], Bubblesort Star graph[4], Transposition graph[9], HCN[1] etc. have been proposed. When it has same nodes, Macro-star graph[11] and Matrix-star graph [12] which has lower degree and more improved network costs than star graph were also proposed. Macro-star graph having same basic module with the star graph has lower degree than the star graph, when it has same number of nodes. But it still has star graph's properties such as node symmetry, maximum fault tolerance, and hierarchical decomposition. Matrix-star graph has the good properties of Macro-star graph and is a better interconnection network which the network costs were improved.

The embedding is that a specific graph is mapping into other graph in order to know the relation of association and inclusion between the two graphs. What network G is possible to embed into network H at low cost is that all algorithms for network G can be efficiently used to network H at low cost. Therefore it is important to estimate an embedding of interconnection networks[5,6,10]. The f=(φ,ρ), embedding graph G into graph H, is defined as following. The φ is a function which corresponds G's vertex set V(G) to H's vertex set V(H). The ρ is a function which corresponds G's edge e=(v,w) to H path linking φ(v) and φ(w). The criterion to estimate the embedding costs is dilation, congestion, expansion and so on. The dilation of edge e of graph G means the length of path ρ(e) on the graph H. The dilation of embedding f is the maximum value among all edge G. The congestion is the number of ρ(e) including H's edge e'. The congestion of f means the maximum value among all edge's congestion of H. The expansion of embedding f means the ratio of G's vertex to H's vertex.

This paper analize the embedding between Macro-star graph and Matrix-star graph which the network cost is better improved than star graph. It also shows that various algorithm for the star graph can be efficiently simulated under the Matrix-star graph by analyzing the embedding relation between two graphs. Section 2 defines and discusses some of the basic properties of Macro-star graph and Matrix-star graph with dilation 2 and that Matrix-star can be embedded into Macro-star graph with dilation 4. Finally conclusions and future studies are presented.

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email