›› 2015,Vol. 30 ›› Issue (5): 1154-1160.doi: 10.1007/s11390-015-1551-0

所属专题： Theory and Algorithms

• Special Section on Selected Paper from NPC 2011 • 上一篇    

异构网络的边着色图构造

Rui Hou1(侯睿), Student Member, IEEE, Ji-Gang Wu1,2*(武继刚), Member, CCF, IEEEYawen Chen3(陈亚文), Haibo Zhang3(张海波), Xiu-Feng Sui2(隋秀峰), Member, CCF, IEEE   

  1. 1 School of Computer Science and Software Engineering, Tianjin Polytechnic University, Tianjin 300387, China;
    2 State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences Beijing 100190, China;
    3 Department of Computer Science, University of Otago, Dunedin 9054, New Zealand
  • 收稿日期:2014-05-24 修回日期:2014-11-08 出版日期:2015-09-05 发布日期:2015-09-05
  • 通讯作者: Ji-Gang Wu E-mail:asjgwu@gmail.com
  • 作者简介:Rui Hou received his Bachelor's degree in software engineering from Tianjin Polytechnic University (TJPU), Tianjin, in 2012. He is working toward his Master's degree in computer science and technology at the School of Computer Science and Software Engineering in TJPU. His research interests include graph theory, parallel/distributed computing, cluster/grid/cloud computing, optical wireless communication, and high-performance computer architectures.
  • 基金资助:

    This work was supported by the National Natural Science Foundation of China under Grant Nos. 61173032 and 61202062, the National Natural Science Foundation of China (Tianyuan Special Foundation) under Grant Nos. 11326211 and 11326198, the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No. 20131201110002, and the Key Laboratory of Computer Architecture Opening Topic Fund Subsidization under Grant No. CARCH201303.

Constructing Edge-Colored Graph for Heterogeneous Networks

Rui Hou1(侯睿), Student Member, IEEE, Ji-Gang Wu1,2*(武继刚), Member, CCF, IEEEYawen Chen3(陈亚文), Haibo Zhang3(张海波), Xiu-Feng Sui2(隋秀峰), Member, CCF, IEEE   

  1. 1 School of Computer Science and Software Engineering, Tianjin Polytechnic University, Tianjin 300387, China;
    2 State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences Beijing 100190, China;
    3 Department of Computer Science, University of Otago, Dunedin 9054, New Zealand
  • Received:2014-05-24 Revised:2014-11-08 Online:2015-09-05 Published:2015-09-05
  • Contact: Ji-Gang Wu E-mail:asjgwu@gmail.com
  • About author:Rui Hou received his Bachelor's degree in software engineering from Tianjin Polytechnic University (TJPU), Tianjin, in 2012. He is working toward his Master's degree in computer science and technology at the School of Computer Science and Software Engineering in TJPU. His research interests include graph theory, parallel/distributed computing, cluster/grid/cloud computing, optical wireless communication, and high-performance computer architectures.
  • Supported by:

    This work was supported by the National Natural Science Foundation of China under Grant Nos. 61173032 and 61202062, the National Natural Science Foundation of China (Tianyuan Special Foundation) under Grant Nos. 11326211 and 11326198, the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No. 20131201110002, and the Key Laboratory of Computer Architecture Opening Topic Fund Subsidization under Grant No. CARCH201303.

PDF (PC)

1025

为了组建一个容错网络, 会将一些完全异构但功能相同的设备同时安装在网络中以防止发生同构故障而对网络造成严重的损害。文中使用边着色图来探索一个在一组同构设备发生故障后仍然能维持正常功能的网络的特性, 并提出了一个在任意给定的参数下设计这种网络的方法。文中还展示了该方法也能用于优化片上网络中路由器之间的连接以达到减少能耗和运行时间延迟的目的。

Abstract: In order to build a fault-tolerant network, heterogeneous facilities are arranged in the network to prevent homogeneous faults from causing serious damage. This paper uses edge-colored graph to investigate the features of a network topology which is survivable after a set of homogeneous devices malfunction. We propose an approach to designing such networks under arbitrary parameters. We also show that the proposed approach can be used to optimize inter-router connections in network-on-chip to reduce the additional consumption of energy and time delay.

[1] Wang Y, Desmedt Y. Edge-colored graphs with applications to homogeneous faults. Information Processing Letters, 2011, 111(13):634-641.

[2] Wang Y. LT codes for efficient and reliable distributed storage systems revisited. arXiv:1207.5542, 2012. http://arxiv.org/abs/1207.5542, Feb. 2015.

[3] Wang Y. Array BP-XOR codes for reliable cloud storage systems. In Proc. ISIT, Jul. 2013, pp.326-330.

[4] Tan S, Lv J. Characterizing the effect of population heterogeneity on evolutionary dynamics on complex networks. Scientific Reports 4, 2014, Article No. 5034.

[5] Arora S, Barak B. Computational Complexity:A Modern Approach. Cambridge:Cambridge University Press, 2009.

[6] Constantine G. Colorful isomorphic spanning trees in complete graphs. Annals of Combinatorics, 2005, 9(2):163-167.

[7] Hammadi A, Mhamdi L. A survey on architectures and energy efficiency in Data Center Networks. Computer Communications, 2014, 40(1):1-21.

[8] Stensgaard M B, Sparso J. ReNoC:A network-on-chip architecture with reconfigurable topology. In Proc. the 2nd NoCS, Apr. 2008, pp.55-64.

[9] Murali S, De Micheli G. Bandwidth-constrained mapping of cores onto NoC architectures. In Proc. DATE, Feb. 2004, pp.896-901.

[10] Gao Y, Jin Y, Chang Z, Hu W. Ultra-low latency reconfigurable photonic network on chip architecture based on application pattern. In Proc. OFC, Mar. 2009.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 朱明远;. Two Congruent Semantics for Prolog with CUT[J]. , 1990, 5(1): 82 -91 .
[2] 金志权; 柳诚飞; 孙钟秀; 周晓方; 陈佩佩; 顾建明;. Design and Implementation of a Heterogeneous Distributed Database System[J]. , 1990, 5(4): 363 -373 .
[3] 韩建超; 史忠植;. Formalizing Default Reasoning[J]. , 1990, 5(4): 374 -378 .
[4] 宋茂强; FelixGrimm; HorstBunke;. A Prototype Expert System for Automatic Generation of Image Processing Programs[J]. , 1991, 6(3): 296 -300 .
[5] 沈一栋;. Form alizing Incomplete Knowledge in Incomplete Databases[J]. , 1992, 7(4): 295 -304 .
[6] 向东; 魏道政;. GLOBAL: A Design for Random Testability Algorithm[J]. , 1994, 9(2): 182 -192 .
[7] 曾建超; Hidehiko Sanada; 徐光佑;. A Form-Correcting System of Chinese Characters Using a Model of Correcting Procedures of Calligraphists[J]. , 1995, 10(1): 23 -34 .
[8] 吴训威; 杭国强;. Design Technique of I~2L Circuits Based on Multi-Valued Logic[J]. , 1996, 11(2): 181 -187 .
[9] 陈芳; 袁保宗;. An Approach to Intelligent Speech Production System[J]. , 1997, 12(2): 185 -188 .
[10] 庄越挺; 芮勇; Thomas S.Huang;. Video Key Frame Extraction by Unsupervised Clustering and Feedback Adjustment[J]. , 1999, 14(3): 283 -287 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：