超立方体互连网络中的组播算法研究
|
摘要
互连网络是构成高性能计算机系统和决定系统通信性能的关键部分。随着VLSI技术的飞速发展以及多核、多线程和片上系统等新技术的应用,高性能计算机系统的规模不断扩大,处理结点的性能持续增长。相比之下,互连网络性能增长速度十分缓慢,已逐渐成为制约系统整体性能发挥的瓶颈。因此,在研发新型互连技术(光互连)的同时,如何提高以组播和归约等操作为基础的聚合通信性能也是当前互连网络研究的热点之一。高性能计算机系统规模的不断扩大,导致互连网络中结点出错的概率也大大增加。若某些处理结点出错而导致解决挑战性应用的高性能计算机系统宕机,造成的计算能力的巨大浪费是不可忍受的。因此,系统应具有降级重组能力,保证正确的处理结点能正常工作。此时,互连网络提供容错通信能力,保证结点间的可靠、高效通信至关重要。
超立方体是人们最早研究且仍是目前最重要的互连网络拓扑结构之一,具有正规性、对称性、强容错性、直径短、可嵌入性等诸多优点。并且随着高维度路由器和高速串行传输技术的出现,因高维超立方体网络有巨大的结点容量,其备受诟病的可扩展性在很长一段时间内将不成问题。
本文研究了超立方体网络上的组播算法。包括对无错误结点的常规超立方体网络的组播算法研究,和对包含错误结点的超立方体网络上的容错组播算法研究。
组播的通信开销是评价组播性能的重要标准之一。我们根据超立方体拓扑结构的规整性和组播目标结点间的局部性特征,提出了一个分簇组播模型。分析表明:簇的度较小且簇内目标结点间局部性特征好,使得簇内通信开销小,从而减小组播通信开销。
基于分簇组播模型,我们设计了一个组播树算法和一个组播路径算法。这两个算法对组播消息的路由是完全分布的。和已有的同类组播算法相比,基于分簇的组播树和组播路径算法对组播目标结点间局部性特征的利用率更高,能显著减小组播通信开销。
针对目前超立方体网络上容错能力最强的容错模型——局部子立方连通,我们提出了一个结点可达性模型。该可达性模型是完全分布的,不需要集中式的控制。并且,我们证明了:仅使用结点上的可达性信息,任意两个正确结点之间均是可路由的。此外,我们设计了三个算法用于结点间交换、更新可达性信息,一个算法用于检测局部子立方体的连通性。这些算法都是简洁高效且完全分布的,算法的主要操作是与、或等逻辑操作,复杂度低,利于硬件实现。
基于可达性模型,我们设计了一个简洁高效的容错路由算法。与局部子立方连通超立方体网络上已有的容错路由算法相比,我们的算法是完全分布的,复杂度更低。并且,算法的主要操作是与、或等逻辑操作,利于硬件实现,有很高的实用价值。
基于可达性模型,我们设计了局部子立方连通超立方体网络上的首个容错组播算法。该算法也是简洁高效且完全分布的,复杂度低,主要操作是与、或等逻辑操作,利于硬件实现,有很高的实用价值。
The interconnection network is one of the most essential subsystem in high performance computing systems. It determines the performance of the inter-node communication. Due to rapid development of VLSI technology and the new technology such as multicore, multithreaded and SoCs, both the size of interconnection network and the performance of processor increase dramatically. However, the performance increase of interconnection network is much slower. It becomes the new bottleneck gradually. Therefore, besides the research of new interconnecting technology such as optical interconnecting, the collective communication based on multicast and reduction becomes the hot spot. With the increase of network size, the possibility of node failure also increases. The high performance computing system should degrade gracefully when node failure occurred. So it's important guarantee the fault-tolerant, reliable communication between non-faulty nodes.
Hypercube is one of the most popular, versatile and efficient topological structures of interconnection networks. With high-radix router and serial transport, the hypercube with large dimension can connect a huge number of nodes. Therefore, the scalability won't be a shortcoming of hypercube for a long time.
This dissertation is the research of multicast algorithms on hypercube interconnection, including the multicast on non-faulty hypercube and the multicast on faulty hypercube.
The multicast overhead is one the metric of performance. Based on the locality between multicast destination nodes, we propose the clustering model. Due to the small degree of cluster and nice locality between destination nodes inside cluster, the overhead is small for inner-cluster. It decreases the overhead of multicast traffic.
We present a multicast tree algorithm and a multicast path algorithm based on the clustering model, in which message routing can be fully distributed. Compared with existing works, our multicast algorithms are with higher utility of locality and reduce the multicast traffic significantly.
The locally subcube-connected hypercube is the fault tolerant model for hypercube, whose capacity is much greater than others. We propose the reachability model for locally subcube-connected hypercube. This model is fully distributed without centric controller. We proofs that it is routable for arbitrary two non-faulty nodes with reachability. We present three algorithms for exchanging, updating locality, and an algorithm for local subcube-connectivity detecting. All these algorithms are efficient and fully distributed. It is suitable for hardware implementation due to that the major operations are bitwise.
We present an efficient fault tolerant routing algorithm based on the reachability model. Compared with existing works, our routing algorithm is fully distributed, with lower complexity. It is suitable for hardware implementation due to that the major operations are bitwise.
We also present the first fault tolerant multicast algorithm based on the reachability model for locally subcube-connected hvpercube. It is efficient, fully distributed and with low complexity. It is suitable for hardware implementation due to that the major operations are bitwise.
超立方体是人们最早研究且仍是目前最重要的互连网络拓扑结构之一,具有正规性、对称性、强容错性、直径短、可嵌入性等诸多优点。并且随着高维度路由器和高速串行传输技术的出现,因高维超立方体网络有巨大的结点容量,其备受诟病的可扩展性在很长一段时间内将不成问题。
本文研究了超立方体网络上的组播算法。包括对无错误结点的常规超立方体网络的组播算法研究,和对包含错误结点的超立方体网络上的容错组播算法研究。
组播的通信开销是评价组播性能的重要标准之一。我们根据超立方体拓扑结构的规整性和组播目标结点间的局部性特征,提出了一个分簇组播模型。分析表明:簇的度较小且簇内目标结点间局部性特征好,使得簇内通信开销小,从而减小组播通信开销。
基于分簇组播模型,我们设计了一个组播树算法和一个组播路径算法。这两个算法对组播消息的路由是完全分布的。和已有的同类组播算法相比,基于分簇的组播树和组播路径算法对组播目标结点间局部性特征的利用率更高,能显著减小组播通信开销。
针对目前超立方体网络上容错能力最强的容错模型——局部子立方连通,我们提出了一个结点可达性模型。该可达性模型是完全分布的,不需要集中式的控制。并且,我们证明了:仅使用结点上的可达性信息,任意两个正确结点之间均是可路由的。此外,我们设计了三个算法用于结点间交换、更新可达性信息,一个算法用于检测局部子立方体的连通性。这些算法都是简洁高效且完全分布的,算法的主要操作是与、或等逻辑操作,复杂度低,利于硬件实现。
基于可达性模型,我们设计了一个简洁高效的容错路由算法。与局部子立方连通超立方体网络上已有的容错路由算法相比,我们的算法是完全分布的,复杂度更低。并且,算法的主要操作是与、或等逻辑操作,利于硬件实现,有很高的实用价值。
基于可达性模型,我们设计了局部子立方连通超立方体网络上的首个容错组播算法。该算法也是简洁高效且完全分布的,复杂度低,主要操作是与、或等逻辑操作,利于硬件实现,有很高的实用价值。
The interconnection network is one of the most essential subsystem in high performance computing systems. It determines the performance of the inter-node communication. Due to rapid development of VLSI technology and the new technology such as multicore, multithreaded and SoCs, both the size of interconnection network and the performance of processor increase dramatically. However, the performance increase of interconnection network is much slower. It becomes the new bottleneck gradually. Therefore, besides the research of new interconnecting technology such as optical interconnecting, the collective communication based on multicast and reduction becomes the hot spot. With the increase of network size, the possibility of node failure also increases. The high performance computing system should degrade gracefully when node failure occurred. So it's important guarantee the fault-tolerant, reliable communication between non-faulty nodes.
Hypercube is one of the most popular, versatile and efficient topological structures of interconnection networks. With high-radix router and serial transport, the hypercube with large dimension can connect a huge number of nodes. Therefore, the scalability won't be a shortcoming of hypercube for a long time.
This dissertation is the research of multicast algorithms on hypercube interconnection, including the multicast on non-faulty hypercube and the multicast on faulty hypercube.
The multicast overhead is one the metric of performance. Based on the locality between multicast destination nodes, we propose the clustering model. Due to the small degree of cluster and nice locality between destination nodes inside cluster, the overhead is small for inner-cluster. It decreases the overhead of multicast traffic.
We present a multicast tree algorithm and a multicast path algorithm based on the clustering model, in which message routing can be fully distributed. Compared with existing works, our multicast algorithms are with higher utility of locality and reduce the multicast traffic significantly.
The locally subcube-connected hypercube is the fault tolerant model for hypercube, whose capacity is much greater than others. We propose the reachability model for locally subcube-connected hypercube. This model is fully distributed without centric controller. We proofs that it is routable for arbitrary two non-faulty nodes with reachability. We present three algorithms for exchanging, updating locality, and an algorithm for local subcube-connectivity detecting. All these algorithms are efficient and fully distributed. It is suitable for hardware implementation due to that the major operations are bitwise.
We present an efficient fault tolerant routing algorithm based on the reachability model. Compared with existing works, our routing algorithm is fully distributed, with lower complexity. It is suitable for hardware implementation due to that the major operations are bitwise.
We also present the first fault tolerant multicast algorithm based on the reachability model for locally subcube-connected hvpercube. It is efficient, fully distributed and with low complexity. It is suitable for hardware implementation due to that the major operations are bitwise.
引文
[1]David Clark.ASCI Pathforward:to 30 Tflops and Beyond.IEEE Concurrency:Parallel,Distributed and Mobile Computing.1998,06(2):13-15
[2]http://www.highproductivity.org/
[3]John L.Hennessy,David A.Patterson,David Goldberg.Computer Architecture:A Quantitative Approach.Morgan Kaufmann,2002,3 edn.
[4]Gordon E.Moore.Cramming more Components onto Integrated Circuits.Electronics.1965,38(8)
[5]Lance Hammond,Basem A.Nayfeh,Kunle Olukotun.A Single-Chip Multiprocessor.Computer.1997,30(9):79-85
[6]R.Kumar,K.I.Farkas,N.P.Jouppi,P.Ranganathan,D.M.Tullsen.Single-ISA heterogeneous multi-core architectures:the potential for processor power reduction.36th Annual IEEE/ACM International Symposium on Microarchitecture(MICRO-36).2003:81-92
[7]Dean M.Tullsen,Susan J.Eggers,Henry M.Levy.Simultaneous Multithreading:Maximizing On-Chip Parallelism.In 22nd Annual International Symposium on Computer Architecture.1995,392-403
[8]Wander O.Cesario,Amer Baghdadi,Lovic Gauthier,Damien Lyonnard,Gabriela Nicolescu,Yanick Paviot,Sungjoo Yoo,Ahmed Amine Jerraya,Mario Diaz-Nava.Component-based design approach for multicore SoCs.Proceedings of the 39th Design Automation Conference,DAC 2002.2002,789-794
[9]Susan L.Graham,Marc Snir,Cynthia A.Patterson.Getting Up to Speed The Future of Supercomputing.Computer Science and Telecommunications Board,THE NATIONAL ACADEMIES PRESS,2004
[10]A.Von Lehmen,G.Clapp,J.W.Gannett,H.Kobrinski,R.A.Skoog.Data in the optical domain technology:A network-level perspective.Lasers and Electro-Optics Society,2004 LEOS 2004 The 17th Annual Meeting of the IEEE.Nov.2004,1
[11]王与力,杨晓东.k元n方体互联网络性能分析与研究.计算机工程.2000,(12)
[12]王与力,杨晓东.并行系统性能影响因素分析.计算机科学.2001,(4)
[13]J.Duato,S.Yalamanchili,L.M.Ni.Interconnection Networks:An Engineering Approach.Morgan Kaufmann Publishers,2002
[14]Z.Bozkus,A.Choudhary,G.Fox,T.Hanpt,S.Ranka,R.Thakur,Jhy-Chun Wang.Scalable libraries for Fortran 90D/High Performance Fortran.A.Choudhary,(Editor)Proc.Scalable Parallel Libraries Conference.1993,67-76
[15]M.Barnett,S.Gupta,D.G.Payne,L.Shuler,R.van de Geijn,J.Watts.Building a high-performance collective communication library.S.Gupta,(Editor) Proc.Supercomputing '94.1994,107-116
[16]M.Barnett,L.Shuler,R.van de Geijn,S.Gupta,D.G.Payne,J.Watts.Interprocessor collective communication library(InterCom).L.Shuler,(Editor) Proc.Scalable High-Performance Computing Conference.1994,357-364
[17]Philip K.McKinley,Yih jia Tsai,David F.Robinson.A Survey of Collective Communication in Wormhole-Routed Massively Parallel Computers.Tech.Rep.MSU-CPS -94-35,1994
[18]Yih-Jia Tsai,P.K.McKinley.An extended dominating node approach to collective communication in all-port wormhole-routed 2D meshes.P.K.McKinley,(Editor)Proc.Scalable High-Performance Computing Conference.1994,199-206
[19]Hong Xu,Ya-Dong Gui,L.M.Ni.Optimal software multicast in wormhole-routed multistage networks.Ya-Dong Gui,(Editor) Proc.Supercomputing '94.1994,703-712
[20]P.Banerjee.The cubical ring connected cycles:a fault tolerant parallel computation network.IEEE Transactions on Computers.1988,37(5):632-636
[21]M-S.Chert,K.G.Shin.Message routing in an injured hypercube.Proceedings of the third conference on Hypercube concurrent computers and applications.New York,NY,USA:ACM,1988,312-317
[22]J.C.Bermond,N.Homobono,C.Peyrat.Large fault-tolerant interconnection networks.Graphs and Combinatorics.Dec.1989,5(1):107-123
[23]J.J.Shen,I.Koren.Yield enhancement designs for WSI cube connected cycles.I.Koren,(Editor) Proc.[1st]International Conference on Wafer Scale Integration.1989,289-298
[24]刘燕,杨晓东.MPP系统的互连通信技术研究.计算机科学.1999,(6)
[25]刘燕,杨晓东.MPP系统的关键技术研究.计算机工程与设计.2000,(2)
[26]王鼎兴,陈国良.互连网络结构分析.科学出版社,1990
[27]刘燕,孙利民,杨晓东,王志英.一个低代价的完全自适应路由器设计.电子学报.1998,26(11)
[28]刘燕,孙利民,杨晓东.LCFAA:一个低代价的完全自适应路由算法.计算机研究与发展.1999,(3)
[29]Steven L.Scott.Synchronization and communication in the T3E multiprocessor.Operating systems review.1996,26-36
[30]刘燕,王春艳,杨晓东.MPP系统中自适应路由算法的分类及分析.计算机科学.1998,(3)
[31]刘燕,杨晓东,王志英.直接网络中的自适应路由算法分析.国防科技大学学报.1998,(1)
[32]刘燕,杨晓东.虫孔网络中的自适应路由算法.计算机工程与设计.1999,(2)
[33]刘燕,孙利民,杨晓东.虚网叠加——构造自适应路由算法的有效框架.计算机研究与发展.1999,(4)
[34]邓波,杨晓东.BNR:最短路径无死锁全自适应路由算法的分析与设计工具.计算机科学.2000,(12)
[35]邓波,杨晓东,陈一骄.一个2D-Mesh上的完全自适应路由器设计.电子学报.2000,(s1)
[36]徐虎,邓波,杨晓东,王志英.一个高效完全自适应路由器的设计.计算机研究与发展.2002,(4)
[37]邓波,杨晓东.一种高效全自适应路由算法的构造框架.计算机研究与发展.2000,(5)
[38]邓波,杨晓东.虫孔寻径无死锁充要条件分析.计算机工程与科学.2000,(2)
[39]Dhabaleswar K.Panda.Issues in Designing Efficient and Practical Algorithms for Collective Communication in Wormhole-Routed Systems.In ICPP Workshop on Challenges for Parallel Processing.1995,8-15
[40]Rolf Rabenseifner.Automatic MPI counter profiling of all users:First results on a CRAY T3E 900-512.In Proceedings of the Message Passing Interface Developer' s and User' s Conference.1999,77-85
[41]Fabrizio Petrini,Darren Kerbyson,Scott Pakin.The case of the Missing Supercomputer Performance:Achieving Optimal Performance on the 8192 Processors of ASIC Q.In Proceedings of the 2003 ACNI/IEEE Conference on Supercomputing.2003
[42]P.K.McKinley,Yih-jia Tsai,D.F.Robinson.Collective communication in wormholerouted massively parallel computers.Computer.1995,28(12):39-50
[43]Rajeev Thakur,Rolf Rabenseifner,William Gropp.Optimization of Collective Communication Operations in MPICH.International Journal of High Performance Computing Applications.2005,19(1):49-66
[44]E.W.Chan,M.F.Heimlich,A.Purkayastha,R.A.van de Geijn.On optimizing collective communication.IEEE International Conference on Cluster Computing.2004,145-155
[45]The BlueGene/L Team.An Overview of the BlueGene/L Supercomputer.ACM/IEEE conference on Supercomputing.2002
[46]屈婉霞,蒋句平,杨晓东,徐炜遐.并行计算机系统容错设计.计算机工程与科学.2005,(9)
[47]Jukka Helin,Rudolf Berrendorf.Analyzing the performance of message passing MIMD Hypercubes:a study with the Intel iPSC/860.Proceedings of the 5th international conference on Supercomputing(ICS).1991,376-385
[48]Bernd Wiesen.Scalable Hardware and Scalable Software:The nCUBE System.Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures (SPAA).1993,240
[49]Stavros A.Zenios,Robert Lasken.The connection machines CM-1 and CM-2:solving nonlinear network problems.Proceedings of the 2nd international conference on Supercomputing(ICS).1988,648-658
[50]J.Laudon,D.Lenoski.System Overview of the SGI Origin 200/2000 Product Line.Proceedings of COMPCON 97.1997
[51]William J.Dally.Performance Analysis of k-Ary n-Cube Interconnection Networks.IEEE Transactions on Computers.1990,39(6):775-785
[52]Anant Agarwal.Limits on Interconnection Network Performance.IEEE Transactions on Parallel and Distributed Systems.1991,2(4):398-412
[53]Kai Hwang,Choming Wang,Cho-Li Wang.Evaluating MPI collective communication on the SP2,T3D,and Paragon multicomputers.Choming Wang,(Editor) Proc.Third International Symposium on High-Performance Computer Architecture.1997,106-115
[54]Steve Scott,Greg Thorson.Optimized routing in the Cray T3D.1994,281-294
[55]Steven L.Scott,Gregory M.Thorson.The CRAY T3E network:adaptive routing in a high performance 3D torus.Proc.HOT Interconnects IV.1996
[56]Ed Anderson,Jeff Brooks,Charles Grassl,Steve Scott.Performance of the CRAY T3E multiprocessor.Supercomputing '97:Proceedings of the 1997 ACM/IEEE conference on Supercomputing.ACM,1997,1-17
[57]Steven L.Scott,James R.Goodman.The Impact of Pipelined Channels on k-ary n-Cube Networks.IEEE Transactions on Parallel and Distributed Systems.1994,5(1):2-16
[58] Jose Duato, M. Malumbres. Optimal topology for distributed shared-memory multiprocessors: Hypercubes again? Euro-Par'96 Parallel Processing. 1996, 205-212
[59] John Kim, William J. Dally, Brian Towles, Amit K. Gupta. Microarchitecture of a High-Radix Router. 32nd International Symposium on Computer Architecture, 2005. ISCA '05. 2005, 420-431
[60] S. Scott, D. Abts, J. Kim, W.J. Dally. The BlackWidow High-Radix Clos Network. 33rd International Symposium on Computer Architecture, 2006. ISCA '06. 2006, 16-28
[61] Laxmi N. Bhuyan, Dharma P. Agrawal. Generalized Hypercube and Hyperbus Structures for a Computer Network. IEEE Trans Computers. 1984, 33(4):323-333
[62] Dikran S. Meliksetian, C. Y. Roger Chen. Optimal Routing Algorithm and the Diameter of the Cube-Connected Cycles. IEEE Transactions on Parallel and Distributed Systems. 1993, 4(10):1172-1178
[63] Qutaibah M. Malluhi, Magdy A. Bayoumi. The Hierarchical Hypercube: A New Interconnection Topology for Massively Parallel Systems. IEEE Transactions on Parallel and Distributed Systems. 1994, 5(1):17-30
[64] Kanad Ghose, Kiran Raghavendra Desai. Hierarchical Cubic Networks. IEEE Transactions on Parallel and Distributed Systems. 1995, 6(4):427-435
[65] Dyi-Rong Duh, Gen-Huey Chen, Jywe-Fei Fang. Algorithms and Properties of a New Two-Level Network with Folded Hypercubes as Basic Modules. IEEE Transactions on Parallel and Distributed Systems. 1995, 6(7):714-723
[66] Paul Cull, Shawn M. Larson. The Mobius Cubes. IEEE Trans Computers. 1995, 44(5):647-659
[67] Sabine R. Ohring, Sajal K. Das. Folded Petersen Cube Networks: New Competitors for the Hypercubes. IEEE Transactions on Parallel and Distributed Systems. 1996, 7(2):151-168
[68] http://www.myri.com
[69] http://www.top500.org
[70] P. Bhat, C. Raghavendra, V. Prasanna. Efficient Collective Communication in Distributed Heterogeneous Systems. Proceedings of the International Conference on Distributed Computing Systems (ICDCS). 1999
[71] Thilo Kielmann, Rutger F. H. Hofman, Henri E. Bal, Aske Plaat, Raoul A. F. Bhoedjang. MagPIe: MPI's collective communication operations for clustered wide area systems. Proceedings of the 7th ACM SIGPLAN symposium on Principles and practice of parallel programming. 1999
[72] X. Lin, L. M. Ni. Multicast communication in multicomputer networks. IEEE Transactions on Parallel and Distributed Systems. 1993, 4(10):1105-1117
[73] Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993
[74] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. The MIT Press, 2001, 2 edn.
[75] L. Kou, G. Markowsky, L. Berman. A fast algorithm for Steiner trees. Acta Infor-matica. Jun. 1981, 15(2):141-145
[76] Youran Lan, Abdol-Hossein Esfahanian, Lionel M. Ni. Multicast in hypercube multiprocessors. Journal of Parallel and Distributed Computing. 1990, 8(1):30-41
[77] Shih-Hsien Sheu, Chang-Biau Yang. Multicast Algorithms for Hypercube Multiprocessors. Journal of Parallel and Distributed Computing. 2001, 61(1):137-149
[78] S.B. Akers, B. Krishnamurthy. A group-theoretic model for symmetric interconnection networks. IEEE Transactions on Computers. Apr 1989, 38(4):555-566
[79] W. Najjar, J.-L. Gaudiot. Network resilience: a measure of network fault tolerance. IEEE Transactions on Computers. 1990, 39(2):174-181
[80] Abdol-Hossein Esfahanian. Generalized Measures of Fault Tolerance with Application to N-Cube Networks. IEEE Trans Computers. 1989, 38(11):1586-1591
[81] Shahram Latifi, Manju V. Hegde, Morteza Naraghi-Pour. Conditional Connectivity Measures for Large Multiprocessor Systems. IEEE Trans Computers. 1994, 43(2):218-222
[82] T. C. Lee, J. P. Hayes. A Fault-Tolerant Communication Scheme for Hypercube Computers. IEEE Transactions on Computers. 1992, 41(10):1242-1256
[83] J. Bruck, R. Cypher, D. Soroker. Tolerating faults in hypercubes using subcube partitioning. IEEE Transactions on Computers. 1992, 41(5):599-605
[84] Jie Wu. Reliable Unicasting in Faulty Hypercubes Using Safety Levels. IEEE Trans Computers. 1997, 46(2):241-247
[85] Ge-Ming Chiu, Kai-Shung Chen. Use of Routing Capability for Fault-Tolerant Routing in Hypercube Multicomputers. IEEE Transactions on Computers. 1997, 46(8):953-958
[86] Qian-Ping Gu, Shietung Peng. k-Pairwise Cluster Fault Tolerant Routing in Hypercubes. IEEE Transactions on Computers. 1997, 46(9): 1042-1049
[87] Jie Wu. Adaptive Fault-Tolerant Routing in Cube-Based Multicomputers Using Safety Vectors. IEEE Transactions on Parallel and Distributed Systems. 1998, 9(4):321-334
[88] Dong Xiang, Ai Chen, Jie Wu. Local-Safety-Information-Based Broadcasting in Hypercube Multicomputers with Node and Link Faults. Journal of Interconnection Networks. 2001, 2(3):365-378
[89] Jianer Chen, Guojun Wang, Songqiao Chen. Locally subcube-connected hypercube networks: theoretical analysis and experimental results. IEEE Transactions on Computers. 2002, 51(5):530-540
[90] Kejun Yao, Jie Wu. A Limited-Global-Information-Based Multicasting Scheme for Faulty Hypercubes. IEEE Transactions on Computers. 1995, 44(9): 1162-1167
[91] Ge-Ming Chiu, Kai-Shung Chen. Efficient Fault-Tolerant Multicast Scheme for Hypercube Multicomputers. IEEE Transactions on Parallel and Distributed Systems. 1998, 9:952-962
[92] Dong Xiang, Ai Chen, Jiaguang Sun. Fault-tolerant routing and multicasting in hypercubes using a partial path set-up. Parallel Computing. 2005, 31(3-4):389-411
[93] Dong Xiang, Ai Chen, Jia-Guang Sun. Fault-tolerant multicasting in hypercubes using local safety information. Journal of Parallel and Distributed Computing. 2006, 66(2):248-256
[94] Youcef Saad, Martin H. Schultz. Topological properties of hypercubes. IEEE Transactions on Computers. 1988, 7:867-872
[95] Junming Xu. Topological Structure and Analysis of Interconnection Networks. Kluwer Academic Publishers, 2001
[96] J. A. Bondy, U. S. R. Murty. Graph Theory With Applications. Elsevier Science Ltd., 1976
[97] Reinhard Diestel. Graph Theory. Springer, 2000, 2 edn.
[98] William James Dally, Brian Patrick Towles. Principles and Practices of Interconnection Networks. Morgan Kaufmann Publishers, 2003
[99] S. Gunes, N. Yilmaz, N. Allahverdi. A multicast routing algorithm based on parallel branching method for faulty hypercubes. International Conference on Trends in Communications, EUROCON 2001. 2001
[100] Song Lu, BaoHua Fan, Yong Dou, XiaoDong Yang. Clustering multicast on hypercube network. High Performance Computing and Communications. Second International Conference, HPCC 2006. Proceedings (Lecture Notes in Computer Science Vol. 4208). Springer Berlin, Germany, 2006, 61-70
[101] Vivek Halwan, Fusun Ozguner. Efficient Heuristics for All-Port Multicast in Wormhole-Routed Hypercubes. IEEE Transactions on Parallel and Distributed Systems. 2000, 11(1):81-94
[102] David F. Robinson, Dan Judd, Philip K. McKinley, Betty H. C. Cheng. Efficient Multicast in All-Port Wormhole-Routed Hypercubes. Journal of Parallel and Distributed Computing. 1995, 31(2):126-140
[103] Hong Shen. Efficient Multiple Multicasting in Hypercubes. Journal of Systems Architecture. 1997, 43(9):655-662
[104] Youran Lan, Abdol-Hossein Esfahanian, Lionel M. Ni. Multicast in hypercube multiprocessors. Seventh Annual International Phoenix Conference on Computers and Communications. 1988, 26-30
[105] D.K. Panda, S. Singal, R. Kesavan. Multidestination message passing in wormhole k-ary n-cube networks with base routing conformed paths. IEEE Transactions on Parallel and Distributed Systems. 1999, 10(1):76-96
[106] Philip K. McKinley, Hong Xu, Abdol-Hossein Esfahanian, Lionel M. Ni. Unicast-Based Multicast Communication in Wormhole-Routed Networks. IEEE Transactions on Parallel and Distributed Systems. 1994, 5(12):1252-1265
[107] Y. Lan, L. M. Li, A-H. Esfahanian. Distributed multi-destination routing in hypercube multiprocessors. Proceedings of the third conference on Hypercube concurrent computers and applications. New York, NY, USA: ACM Press, 1988, 631-639
[108] Qian-Ping Gu, Shietung Peng. Cluster Fault Tolerant Routing in Hypercubes. 1998 International Conference on Parallel Processing (ICPP '98), 10-14 August 1998, Minneapolis, Minnesota, USA, Proceedings. 1998, 148-155
[2]http://www.highproductivity.org/
[3]John L.Hennessy,David A.Patterson,David Goldberg.Computer Architecture:A Quantitative Approach.Morgan Kaufmann,2002,3 edn.
[4]Gordon E.Moore.Cramming more Components onto Integrated Circuits.Electronics.1965,38(8)
[5]Lance Hammond,Basem A.Nayfeh,Kunle Olukotun.A Single-Chip Multiprocessor.Computer.1997,30(9):79-85
[6]R.Kumar,K.I.Farkas,N.P.Jouppi,P.Ranganathan,D.M.Tullsen.Single-ISA heterogeneous multi-core architectures:the potential for processor power reduction.36th Annual IEEE/ACM International Symposium on Microarchitecture(MICRO-36).2003:81-92
[7]Dean M.Tullsen,Susan J.Eggers,Henry M.Levy.Simultaneous Multithreading:Maximizing On-Chip Parallelism.In 22nd Annual International Symposium on Computer Architecture.1995,392-403
[8]Wander O.Cesario,Amer Baghdadi,Lovic Gauthier,Damien Lyonnard,Gabriela Nicolescu,Yanick Paviot,Sungjoo Yoo,Ahmed Amine Jerraya,Mario Diaz-Nava.Component-based design approach for multicore SoCs.Proceedings of the 39th Design Automation Conference,DAC 2002.2002,789-794
[9]Susan L.Graham,Marc Snir,Cynthia A.Patterson.Getting Up to Speed The Future of Supercomputing.Computer Science and Telecommunications Board,THE NATIONAL ACADEMIES PRESS,2004
[10]A.Von Lehmen,G.Clapp,J.W.Gannett,H.Kobrinski,R.A.Skoog.Data in the optical domain technology:A network-level perspective.Lasers and Electro-Optics Society,2004 LEOS 2004 The 17th Annual Meeting of the IEEE.Nov.2004,1
[11]王与力,杨晓东.k元n方体互联网络性能分析与研究.计算机工程.2000,(12)
[12]王与力,杨晓东.并行系统性能影响因素分析.计算机科学.2001,(4)
[13]J.Duato,S.Yalamanchili,L.M.Ni.Interconnection Networks:An Engineering Approach.Morgan Kaufmann Publishers,2002
[14]Z.Bozkus,A.Choudhary,G.Fox,T.Hanpt,S.Ranka,R.Thakur,Jhy-Chun Wang.Scalable libraries for Fortran 90D/High Performance Fortran.A.Choudhary,(Editor)Proc.Scalable Parallel Libraries Conference.1993,67-76
[15]M.Barnett,S.Gupta,D.G.Payne,L.Shuler,R.van de Geijn,J.Watts.Building a high-performance collective communication library.S.Gupta,(Editor) Proc.Supercomputing '94.1994,107-116
[16]M.Barnett,L.Shuler,R.van de Geijn,S.Gupta,D.G.Payne,J.Watts.Interprocessor collective communication library(InterCom).L.Shuler,(Editor) Proc.Scalable High-Performance Computing Conference.1994,357-364
[17]Philip K.McKinley,Yih jia Tsai,David F.Robinson.A Survey of Collective Communication in Wormhole-Routed Massively Parallel Computers.Tech.Rep.MSU-CPS -94-35,1994
[18]Yih-Jia Tsai,P.K.McKinley.An extended dominating node approach to collective communication in all-port wormhole-routed 2D meshes.P.K.McKinley,(Editor)Proc.Scalable High-Performance Computing Conference.1994,199-206
[19]Hong Xu,Ya-Dong Gui,L.M.Ni.Optimal software multicast in wormhole-routed multistage networks.Ya-Dong Gui,(Editor) Proc.Supercomputing '94.1994,703-712
[20]P.Banerjee.The cubical ring connected cycles:a fault tolerant parallel computation network.IEEE Transactions on Computers.1988,37(5):632-636
[21]M-S.Chert,K.G.Shin.Message routing in an injured hypercube.Proceedings of the third conference on Hypercube concurrent computers and applications.New York,NY,USA:ACM,1988,312-317
[22]J.C.Bermond,N.Homobono,C.Peyrat.Large fault-tolerant interconnection networks.Graphs and Combinatorics.Dec.1989,5(1):107-123
[23]J.J.Shen,I.Koren.Yield enhancement designs for WSI cube connected cycles.I.Koren,(Editor) Proc.[1st]International Conference on Wafer Scale Integration.1989,289-298
[24]刘燕,杨晓东.MPP系统的互连通信技术研究.计算机科学.1999,(6)
[25]刘燕,杨晓东.MPP系统的关键技术研究.计算机工程与设计.2000,(2)
[26]王鼎兴,陈国良.互连网络结构分析.科学出版社,1990
[27]刘燕,孙利民,杨晓东,王志英.一个低代价的完全自适应路由器设计.电子学报.1998,26(11)
[28]刘燕,孙利民,杨晓东.LCFAA:一个低代价的完全自适应路由算法.计算机研究与发展.1999,(3)
[29]Steven L.Scott.Synchronization and communication in the T3E multiprocessor.Operating systems review.1996,26-36
[30]刘燕,王春艳,杨晓东.MPP系统中自适应路由算法的分类及分析.计算机科学.1998,(3)
[31]刘燕,杨晓东,王志英.直接网络中的自适应路由算法分析.国防科技大学学报.1998,(1)
[32]刘燕,杨晓东.虫孔网络中的自适应路由算法.计算机工程与设计.1999,(2)
[33]刘燕,孙利民,杨晓东.虚网叠加——构造自适应路由算法的有效框架.计算机研究与发展.1999,(4)
[34]邓波,杨晓东.BNR:最短路径无死锁全自适应路由算法的分析与设计工具.计算机科学.2000,(12)
[35]邓波,杨晓东,陈一骄.一个2D-Mesh上的完全自适应路由器设计.电子学报.2000,(s1)
[36]徐虎,邓波,杨晓东,王志英.一个高效完全自适应路由器的设计.计算机研究与发展.2002,(4)
[37]邓波,杨晓东.一种高效全自适应路由算法的构造框架.计算机研究与发展.2000,(5)
[38]邓波,杨晓东.虫孔寻径无死锁充要条件分析.计算机工程与科学.2000,(2)
[39]Dhabaleswar K.Panda.Issues in Designing Efficient and Practical Algorithms for Collective Communication in Wormhole-Routed Systems.In ICPP Workshop on Challenges for Parallel Processing.1995,8-15
[40]Rolf Rabenseifner.Automatic MPI counter profiling of all users:First results on a CRAY T3E 900-512.In Proceedings of the Message Passing Interface Developer' s and User' s Conference.1999,77-85
[41]Fabrizio Petrini,Darren Kerbyson,Scott Pakin.The case of the Missing Supercomputer Performance:Achieving Optimal Performance on the 8192 Processors of ASIC Q.In Proceedings of the 2003 ACNI/IEEE Conference on Supercomputing.2003
[42]P.K.McKinley,Yih-jia Tsai,D.F.Robinson.Collective communication in wormholerouted massively parallel computers.Computer.1995,28(12):39-50
[43]Rajeev Thakur,Rolf Rabenseifner,William Gropp.Optimization of Collective Communication Operations in MPICH.International Journal of High Performance Computing Applications.2005,19(1):49-66
[44]E.W.Chan,M.F.Heimlich,A.Purkayastha,R.A.van de Geijn.On optimizing collective communication.IEEE International Conference on Cluster Computing.2004,145-155
[45]The BlueGene/L Team.An Overview of the BlueGene/L Supercomputer.ACM/IEEE conference on Supercomputing.2002
[46]屈婉霞,蒋句平,杨晓东,徐炜遐.并行计算机系统容错设计.计算机工程与科学.2005,(9)
[47]Jukka Helin,Rudolf Berrendorf.Analyzing the performance of message passing MIMD Hypercubes:a study with the Intel iPSC/860.Proceedings of the 5th international conference on Supercomputing(ICS).1991,376-385
[48]Bernd Wiesen.Scalable Hardware and Scalable Software:The nCUBE System.Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures (SPAA).1993,240
[49]Stavros A.Zenios,Robert Lasken.The connection machines CM-1 and CM-2:solving nonlinear network problems.Proceedings of the 2nd international conference on Supercomputing(ICS).1988,648-658
[50]J.Laudon,D.Lenoski.System Overview of the SGI Origin 200/2000 Product Line.Proceedings of COMPCON 97.1997
[51]William J.Dally.Performance Analysis of k-Ary n-Cube Interconnection Networks.IEEE Transactions on Computers.1990,39(6):775-785
[52]Anant Agarwal.Limits on Interconnection Network Performance.IEEE Transactions on Parallel and Distributed Systems.1991,2(4):398-412
[53]Kai Hwang,Choming Wang,Cho-Li Wang.Evaluating MPI collective communication on the SP2,T3D,and Paragon multicomputers.Choming Wang,(Editor) Proc.Third International Symposium on High-Performance Computer Architecture.1997,106-115
[54]Steve Scott,Greg Thorson.Optimized routing in the Cray T3D.1994,281-294
[55]Steven L.Scott,Gregory M.Thorson.The CRAY T3E network:adaptive routing in a high performance 3D torus.Proc.HOT Interconnects IV.1996
[56]Ed Anderson,Jeff Brooks,Charles Grassl,Steve Scott.Performance of the CRAY T3E multiprocessor.Supercomputing '97:Proceedings of the 1997 ACM/IEEE conference on Supercomputing.ACM,1997,1-17
[57]Steven L.Scott,James R.Goodman.The Impact of Pipelined Channels on k-ary n-Cube Networks.IEEE Transactions on Parallel and Distributed Systems.1994,5(1):2-16
[58] Jose Duato, M. Malumbres. Optimal topology for distributed shared-memory multiprocessors: Hypercubes again? Euro-Par'96 Parallel Processing. 1996, 205-212
[59] John Kim, William J. Dally, Brian Towles, Amit K. Gupta. Microarchitecture of a High-Radix Router. 32nd International Symposium on Computer Architecture, 2005. ISCA '05. 2005, 420-431
[60] S. Scott, D. Abts, J. Kim, W.J. Dally. The BlackWidow High-Radix Clos Network. 33rd International Symposium on Computer Architecture, 2006. ISCA '06. 2006, 16-28
[61] Laxmi N. Bhuyan, Dharma P. Agrawal. Generalized Hypercube and Hyperbus Structures for a Computer Network. IEEE Trans Computers. 1984, 33(4):323-333
[62] Dikran S. Meliksetian, C. Y. Roger Chen. Optimal Routing Algorithm and the Diameter of the Cube-Connected Cycles. IEEE Transactions on Parallel and Distributed Systems. 1993, 4(10):1172-1178
[63] Qutaibah M. Malluhi, Magdy A. Bayoumi. The Hierarchical Hypercube: A New Interconnection Topology for Massively Parallel Systems. IEEE Transactions on Parallel and Distributed Systems. 1994, 5(1):17-30
[64] Kanad Ghose, Kiran Raghavendra Desai. Hierarchical Cubic Networks. IEEE Transactions on Parallel and Distributed Systems. 1995, 6(4):427-435
[65] Dyi-Rong Duh, Gen-Huey Chen, Jywe-Fei Fang. Algorithms and Properties of a New Two-Level Network with Folded Hypercubes as Basic Modules. IEEE Transactions on Parallel and Distributed Systems. 1995, 6(7):714-723
[66] Paul Cull, Shawn M. Larson. The Mobius Cubes. IEEE Trans Computers. 1995, 44(5):647-659
[67] Sabine R. Ohring, Sajal K. Das. Folded Petersen Cube Networks: New Competitors for the Hypercubes. IEEE Transactions on Parallel and Distributed Systems. 1996, 7(2):151-168
[68] http://www.myri.com
[69] http://www.top500.org
[70] P. Bhat, C. Raghavendra, V. Prasanna. Efficient Collective Communication in Distributed Heterogeneous Systems. Proceedings of the International Conference on Distributed Computing Systems (ICDCS). 1999
[71] Thilo Kielmann, Rutger F. H. Hofman, Henri E. Bal, Aske Plaat, Raoul A. F. Bhoedjang. MagPIe: MPI's collective communication operations for clustered wide area systems. Proceedings of the 7th ACM SIGPLAN symposium on Principles and practice of parallel programming. 1999
[72] X. Lin, L. M. Ni. Multicast communication in multicomputer networks. IEEE Transactions on Parallel and Distributed Systems. 1993, 4(10):1105-1117
[73] Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993
[74] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. The MIT Press, 2001, 2 edn.
[75] L. Kou, G. Markowsky, L. Berman. A fast algorithm for Steiner trees. Acta Infor-matica. Jun. 1981, 15(2):141-145
[76] Youran Lan, Abdol-Hossein Esfahanian, Lionel M. Ni. Multicast in hypercube multiprocessors. Journal of Parallel and Distributed Computing. 1990, 8(1):30-41
[77] Shih-Hsien Sheu, Chang-Biau Yang. Multicast Algorithms for Hypercube Multiprocessors. Journal of Parallel and Distributed Computing. 2001, 61(1):137-149
[78] S.B. Akers, B. Krishnamurthy. A group-theoretic model for symmetric interconnection networks. IEEE Transactions on Computers. Apr 1989, 38(4):555-566
[79] W. Najjar, J.-L. Gaudiot. Network resilience: a measure of network fault tolerance. IEEE Transactions on Computers. 1990, 39(2):174-181
[80] Abdol-Hossein Esfahanian. Generalized Measures of Fault Tolerance with Application to N-Cube Networks. IEEE Trans Computers. 1989, 38(11):1586-1591
[81] Shahram Latifi, Manju V. Hegde, Morteza Naraghi-Pour. Conditional Connectivity Measures for Large Multiprocessor Systems. IEEE Trans Computers. 1994, 43(2):218-222
[82] T. C. Lee, J. P. Hayes. A Fault-Tolerant Communication Scheme for Hypercube Computers. IEEE Transactions on Computers. 1992, 41(10):1242-1256
[83] J. Bruck, R. Cypher, D. Soroker. Tolerating faults in hypercubes using subcube partitioning. IEEE Transactions on Computers. 1992, 41(5):599-605
[84] Jie Wu. Reliable Unicasting in Faulty Hypercubes Using Safety Levels. IEEE Trans Computers. 1997, 46(2):241-247
[85] Ge-Ming Chiu, Kai-Shung Chen. Use of Routing Capability for Fault-Tolerant Routing in Hypercube Multicomputers. IEEE Transactions on Computers. 1997, 46(8):953-958
[86] Qian-Ping Gu, Shietung Peng. k-Pairwise Cluster Fault Tolerant Routing in Hypercubes. IEEE Transactions on Computers. 1997, 46(9): 1042-1049
[87] Jie Wu. Adaptive Fault-Tolerant Routing in Cube-Based Multicomputers Using Safety Vectors. IEEE Transactions on Parallel and Distributed Systems. 1998, 9(4):321-334
[88] Dong Xiang, Ai Chen, Jie Wu. Local-Safety-Information-Based Broadcasting in Hypercube Multicomputers with Node and Link Faults. Journal of Interconnection Networks. 2001, 2(3):365-378
[89] Jianer Chen, Guojun Wang, Songqiao Chen. Locally subcube-connected hypercube networks: theoretical analysis and experimental results. IEEE Transactions on Computers. 2002, 51(5):530-540
[90] Kejun Yao, Jie Wu. A Limited-Global-Information-Based Multicasting Scheme for Faulty Hypercubes. IEEE Transactions on Computers. 1995, 44(9): 1162-1167
[91] Ge-Ming Chiu, Kai-Shung Chen. Efficient Fault-Tolerant Multicast Scheme for Hypercube Multicomputers. IEEE Transactions on Parallel and Distributed Systems. 1998, 9:952-962
[92] Dong Xiang, Ai Chen, Jiaguang Sun. Fault-tolerant routing and multicasting in hypercubes using a partial path set-up. Parallel Computing. 2005, 31(3-4):389-411
[93] Dong Xiang, Ai Chen, Jia-Guang Sun. Fault-tolerant multicasting in hypercubes using local safety information. Journal of Parallel and Distributed Computing. 2006, 66(2):248-256
[94] Youcef Saad, Martin H. Schultz. Topological properties of hypercubes. IEEE Transactions on Computers. 1988, 7:867-872
[95] Junming Xu. Topological Structure and Analysis of Interconnection Networks. Kluwer Academic Publishers, 2001
[96] J. A. Bondy, U. S. R. Murty. Graph Theory With Applications. Elsevier Science Ltd., 1976
[97] Reinhard Diestel. Graph Theory. Springer, 2000, 2 edn.
[98] William James Dally, Brian Patrick Towles. Principles and Practices of Interconnection Networks. Morgan Kaufmann Publishers, 2003
[99] S. Gunes, N. Yilmaz, N. Allahverdi. A multicast routing algorithm based on parallel branching method for faulty hypercubes. International Conference on Trends in Communications, EUROCON 2001. 2001
[100] Song Lu, BaoHua Fan, Yong Dou, XiaoDong Yang. Clustering multicast on hypercube network. High Performance Computing and Communications. Second International Conference, HPCC 2006. Proceedings (Lecture Notes in Computer Science Vol. 4208). Springer Berlin, Germany, 2006, 61-70
[101] Vivek Halwan, Fusun Ozguner. Efficient Heuristics for All-Port Multicast in Wormhole-Routed Hypercubes. IEEE Transactions on Parallel and Distributed Systems. 2000, 11(1):81-94
[102] David F. Robinson, Dan Judd, Philip K. McKinley, Betty H. C. Cheng. Efficient Multicast in All-Port Wormhole-Routed Hypercubes. Journal of Parallel and Distributed Computing. 1995, 31(2):126-140
[103] Hong Shen. Efficient Multiple Multicasting in Hypercubes. Journal of Systems Architecture. 1997, 43(9):655-662
[104] Youran Lan, Abdol-Hossein Esfahanian, Lionel M. Ni. Multicast in hypercube multiprocessors. Seventh Annual International Phoenix Conference on Computers and Communications. 1988, 26-30
[105] D.K. Panda, S. Singal, R. Kesavan. Multidestination message passing in wormhole k-ary n-cube networks with base routing conformed paths. IEEE Transactions on Parallel and Distributed Systems. 1999, 10(1):76-96
[106] Philip K. McKinley, Hong Xu, Abdol-Hossein Esfahanian, Lionel M. Ni. Unicast-Based Multicast Communication in Wormhole-Routed Networks. IEEE Transactions on Parallel and Distributed Systems. 1994, 5(12):1252-1265
[107] Y. Lan, L. M. Li, A-H. Esfahanian. Distributed multi-destination routing in hypercube multiprocessors. Proceedings of the third conference on Hypercube concurrent computers and applications. New York, NY, USA: ACM Press, 1988, 631-639
[108] Qian-Ping Gu, Shietung Peng. Cluster Fault Tolerant Routing in Hypercubes. 1998 International Conference on Parallel Processing (ICPP '98), 10-14 August 1998, Minneapolis, Minnesota, USA, Proceedings. 1998, 148-155