多级互连网上无阻塞会议通信的实现
|
摘要
近年来,随着高性能并行计算的迅速发展,多级互连网作为现代并行计算机和交换系统的核心连接网络,需要更好的支持在并行分布计算机系统里多个要求协作的处理器之间的通信——会议组通信。在多级互连网上无阻塞并发实现会议组通信受到越来越广泛的关注,成为重要的研究课题。本文主要研究多级互连网络上各种模式下的通信特点,并基于典型的互连网络结构构造具有良好通信能力和最优硬件代价的无阻塞会议网络。具体研究内容如下:
论文首先研究了全连接交叉开关和Clos网络等两种结构上无阻塞支持会议通信的实现,给出了Clos网络上会议通信的实现策略和无阻塞条件,得到小规模情况下低延迟无阻塞实现的会议网络结构。
接着为了得到更小硬件代价的会议网络结构,结合Omega复制网受限多播可以无阻塞并发的性质,讨论了Omega -1汇集网的结构及其上的自适应路由规约通信策略,进而得到Omega -1汇集网受限多对一规约连接无阻塞并发的结论。通过串接Omega -1汇集网和Omega复制网提出新的2-Omega结构的会议功能网络结构(GBCCN),并证明了其上受限多会议可以无阻塞的并发实现。
进而按照会议网络三明治策略“置换网+会议功能网络+置换网”构造出新的会议网络。新的会议网络中位于两端的置换网采用Omega+Omega重排结构,位于中间的会议功能网络采用本文提出的2-Omega结构的GBCCN,从而得到一个6-Omega的会议网络。该网络可以实现会议成员任意分布的多会议无阻塞并发通信,硬件复杂度为3NlogN,传输延迟为6logN ,路由时间为O(NlogN) ,均达到已有无阻塞网络的最优量级。新构造的6-Omega会议网络具有更好的整体对称性,可以折叠为3-Oemga的会议网络,进一步降低硬件代价。
论文提出的6-Omega会议网络的构造无论在方法上还是在结果上与现有研究成果相比,都具有一定的优势和创新。由于在设计与实现上具有很好的通用性,因此对于进一步研究多级互连网上实现各种通信尤其是会议组通信具有积极的意义。
MINS(Multistage interconnection networks), as important elements in parallel computing computer and switching system, need to effectively sopport conference communication within a cluster of processors collaborating. For decades, realizing concurrent multipe conferences nonblockingly on the MINS becomes an important issue. This dissertation focuses on how to create a new conference network with better performance and lowest costing which can realize concurrent conferences nonblockingly. The specific studies are as follows:
Firstly, this dissertation analyses the strategy and nonblocking conditions of conference communication on Clos network. On Clos network we can easily design nonblocking conference network with relatively lower latency.
Secondly, for getting a lower hardware cost, this dissertation extends the basis on Omega replicating network to Omega -1 merging network. It comes to the conclusion that Omega -1 is nonblocking merging network for constrained concurrent many-to-one connections. Then, by concatenating Omega -1 merging network and Omega replicating network, we propose a novel 2-Omega structure named GBCCN (Gathering&Broadcasting conference component network), and prove that multiple constrained conferences can be nonblockingly realised on GBCCN.
Finally, according to the sandwich strategy of conference network, by using rearrangeable Omega + Omega as replacing network and GBCCN as the conference component network, a 6-Omega conference network is designed, which is based upon analysing how the struture of 5-Omega realises arbitrary multicast. It can realize concurrent multiple disjoint conferences distributed arbitrarily. Then, it has 3NlogN hardware cast、6logN communication delay, O(NlogN) routing time. Moreover, the 6-Omega structure has better integrated symmetry to be folded into 3-Oemga, which further reduces the cost of hardware.
The new conference network is superior to existing designs, has advantages and innovations in the ways and structures. It contributes to further studying on MINS.
论文首先研究了全连接交叉开关和Clos网络等两种结构上无阻塞支持会议通信的实现,给出了Clos网络上会议通信的实现策略和无阻塞条件,得到小规模情况下低延迟无阻塞实现的会议网络结构。
接着为了得到更小硬件代价的会议网络结构,结合Omega复制网受限多播可以无阻塞并发的性质,讨论了Omega -1汇集网的结构及其上的自适应路由规约通信策略,进而得到Omega -1汇集网受限多对一规约连接无阻塞并发的结论。通过串接Omega -1汇集网和Omega复制网提出新的2-Omega结构的会议功能网络结构(GBCCN),并证明了其上受限多会议可以无阻塞的并发实现。
进而按照会议网络三明治策略“置换网+会议功能网络+置换网”构造出新的会议网络。新的会议网络中位于两端的置换网采用Omega+Omega重排结构,位于中间的会议功能网络采用本文提出的2-Omega结构的GBCCN,从而得到一个6-Omega的会议网络。该网络可以实现会议成员任意分布的多会议无阻塞并发通信,硬件复杂度为3NlogN,传输延迟为6logN ,路由时间为O(NlogN) ,均达到已有无阻塞网络的最优量级。新构造的6-Omega会议网络具有更好的整体对称性,可以折叠为3-Oemga的会议网络,进一步降低硬件代价。
论文提出的6-Omega会议网络的构造无论在方法上还是在结果上与现有研究成果相比,都具有一定的优势和创新。由于在设计与实现上具有很好的通用性,因此对于进一步研究多级互连网上实现各种通信尤其是会议组通信具有积极的意义。
MINS(Multistage interconnection networks), as important elements in parallel computing computer and switching system, need to effectively sopport conference communication within a cluster of processors collaborating. For decades, realizing concurrent multipe conferences nonblockingly on the MINS becomes an important issue. This dissertation focuses on how to create a new conference network with better performance and lowest costing which can realize concurrent conferences nonblockingly. The specific studies are as follows:
Firstly, this dissertation analyses the strategy and nonblocking conditions of conference communication on Clos network. On Clos network we can easily design nonblocking conference network with relatively lower latency.
Secondly, for getting a lower hardware cost, this dissertation extends the basis on Omega replicating network to Omega -1 merging network. It comes to the conclusion that Omega -1 is nonblocking merging network for constrained concurrent many-to-one connections. Then, by concatenating Omega -1 merging network and Omega replicating network, we propose a novel 2-Omega structure named GBCCN (Gathering&Broadcasting conference component network), and prove that multiple constrained conferences can be nonblockingly realised on GBCCN.
Finally, according to the sandwich strategy of conference network, by using rearrangeable Omega + Omega as replacing network and GBCCN as the conference component network, a 6-Omega conference network is designed, which is based upon analysing how the struture of 5-Omega realises arbitrary multicast. It can realize concurrent multiple disjoint conferences distributed arbitrarily. Then, it has 3NlogN hardware cast、6logN communication delay, O(NlogN) routing time. Moreover, the 6-Omega structure has better integrated symmetry to be folded into 3-Oemga, which further reduces the cost of hardware.
The new conference network is superior to existing designs, has advantages and innovations in the ways and structures. It contributes to further studying on MINS.
引文
[1] Yang Y Y. A Class of Interconnection Networks for Multicasting[J]. IEEE Trans Computers, 1998, 47(8): 899-906.
[2] Yang Y Y, Wang J C. A Class of Multistage Conference Switching Networks for Group Communication[J]. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(3): 228-243.
[3] Yang Y Y, Masson G M. Broadcast Ring Sandwich Networks[J]. IEEE Trans Computers, 1995, 44(10): 1169-1180.
[4] Houlahan J F, Cowen L J, Masson G M. Hypercube Sandwich Approach to Conferencing[J]. Supercomputing, 1996, 10(3): 271-283.
[5] Du Y, Masson G M. Strictly Nonblocking Conference Networks Using High-Dimensional Meshes[J]. Networks, 1999, 33(4): 293-308.
[6] Yang Y Y. A New Conference Network for Group Communication[J]. Proc. 2001 Int’l Conf. Parallel Processing, 2001: 141-148.
[7] Duato J, Yalamanchili S, Ni L M. Interconnection Networks: An Engineering Approach. Morgan Kaufmann, 2002.
[8] Wong C K, Gouda M, Lam S S. Secure Group Communications Using Key Graphs[J]. IEEE/ACM Trans Networking, 2000, 8(1): 16-30.
[9] Baldi M, Ofek Y, Yener B. Adaptive Group Multicast with Time-Driven Priority[J]. IEEE/ACM Trans Networking, 2000, 8(1): 31-43.
[10] Mishra S, Fei L, Lin X, Xing G. On Group Communication Support in CORBA[J]. IEEE Trans Parallel and Distributed Systems, 2001, 12(2): 193-208.
[11] Gopal A, Gopal I, Kutten S. Fast Broadcast in High-Speed Networks[J]. IEEE/ACM Trans Networking, 1999, 7(2): 262-275.
[12] Yang Y Y, Wang J. Optimal All-to-All Personalized Exchange in Self-Routable Multistage Networks[J]. IEEE Trans Parallel and Distributed Systems, 2000, 11(3):261-274.
[13] Suh Y, Shin K G.. All-to-All Personalized Communication in Multidimensional Torus and Mesh Networks[J]. IEEE Trans Parallel and Distributed Systems, 2001, 12(1): 38-59.
[14] Wang S Y, Tseng Y C. Algebraic Foundations and Broadcasting Algorithms for Wormhole-Routed All-Port Tori[J]. IEEE Trans Computers, 2000, 49(3): 246-258.
[15] Libeskind-Hadas R, Mazzoni D, Rajagopalan R. Tree-Based Multicasting in Wormhole-Routed Irregular Topologies[J]. Proc. 12th Int’l Parallel and Distributed Processing Symp, 1998: 244-249.
[16] Kumar D R, Najjar W A, Srimani P K. A New Adaptive Hardware Tree-Based MulticastRouting in K-Ary N-Cubes[J]. IEEE Trans Computers, 2001, 50(7): 647-659.
[17] Yang Y Y, Wang J. A New Self-Routing Multicast Network[J]. IEEE Trans Parallel and Distributed Systems, 1999, 10(12): 1299-1316.
[18] Zegura E W, Ammar M H, Fei Z, S Bhattacharjee. Application-Layer Anycasting[J]. IEEE/ACM Trans Networking, 2000, 8(4): 455-466.
[19] Xuan D, Jia W, Zhao W, Zhu H. A Routing Protocol for Anycast Messages[J]. IEEE Trans Parallel and Distributed Systems, 2000, 11(6): 571-588.
[20] Yang Y, Masson G M. The Necessary Conditions for Clos-Type Nonblocking Multicast Networks[J], IEEE Trans Computers, 1999, 48(11): 1214-1227.
[21] Pattavina A, Tesei G. Multicast nonblocking switching networks[J]. IEEE Trans Computers, 2002, 50(8): 1240-1243.
[22] Yang Y, Wang J. Nonblocking k-Fold Multicast Networks[J], IEEE Trans Parallel and Distributed Systems, 2003, 14(2): 131-141.
[23] Yang Y Y. A New Design for Wide-Sense Nonblocking Multicast Switching Networks[J]. IEEE Trans On Communications,2005, 53(3).
[24]张联,顾乃杰,刘刚,等.采用二进制寻路法和多Omega网络的自路由无阻塞多级网[J].计算机应用, 2005, 25(12): 2923-2934.
[25]顾乃杰,潘伟,李栋,等.一种新型的可重排多播网络[J].小型微型计算机系统, 2003, 24(2): 179-183.
[26]张联,刘刚,顾乃杰.多播3-Omega交换网的设计思想[J].计算机工程, 2006, 32(17): 184-186.
[27] Shannon C E. Memory requirements in a telephone exchange[R]. Bell System Tech.J, 1950, 47(8): 899-906.
[28]王鼎兴,陈国良.互联网结构与分析[M].北京:科学出版社, 1990.
[29] Lee C, Oruc A Y. Design of Efficient and Easily Routable Generalized Connectors[J]. IEEE Trans Communication, 1995, 43(2-4): 646-650.
[30] Nassimi D, Saahni S. Parallel Permutation and Sorting Algorithms and a New Generalized Connection Network[J]. J.ACM, 1982, 29(3): 642-667.
[31] Ted H, Szumanski.Design Principles for Practical Self-Routing Nonblocking Switiching Networks with O(nlogn)Bit-Complexity[J]. IEEE Trans Computers, 1997, 46(10): 1057-1068.
[32] Clos C. A Study of Nonblocking Switching Network[J]. Bell System Tech.J, 1953, 32(2): 406-424.
[33] Duguid A. Structural Properties of Switching Networks[R]. Brown University ProgressReport BTL-7, 1959.
[34] Slepian D. two Theorems on a Starticular Crossbar Switching Network[R]. Unpublished manuscript, 1952.
[35] Hall P. On Representatives of subsets[J]. J.London Math.Soc., 1935, vol(10): 26-30.
[36] Waksman A. A Permutation Network[J]. J.ACM, 1968, 15(1): 159-163.
[37] Wu C L, Feng T Y. On a Class of Multistage Interconnection Networks[J]. IEEE Trans Computers, 1980, 29(8): 694-702.
[38] Wu C L, Feng T Y. On a Class of Rearrangeable Networks[J]. IEEE Trans Computers, 1992, 41(11): 1361-1379.
[39] Wu C L, Feng T Y. Routing Techniques for a Class of Multistage Interconnection Networks[J]. Proc.of the ICPP, 1978: 197-205
[40] Feng T Y, Seo S W. A New Routing Algorithm for a Class of Rearrangeble Networks [J]. IEEE Transactions on Computers, 1994, 43(11): 1270-1280.
[41] Paull M. Reswitching on Connection Networks[J]. Bell System Tech, 1962, 41(3): 833-855.
[42] Benes V E. On Rearrangeable Three-Stage Connection Networks[J]. Bell System Tech, 1962, vol(41): 1481-1492.
[43] Benes V E. Semilattice Characterization of Nonblocking Networkings[J]. Bell System Tech, 1973, vol(52): 697-706.
[44] Thurber K J, Masson G M. Distributed-Processor Communication Architecture[J]. D.C.Heath and Company, 1979.
[45] Gordon J,Srikanthan S. Novel algorithm for Clos-type networks[J]. ElectronLett,1990,26(21):1772-1774.
[46] Lee H Y, Hwang F K, Carp inelliD. A new decomposition algorithm for rearrangeable Clos interconnection networks[J]. IEEE Trans on Commun, 1996, 44(11): 1572-1578.
[47]曾峰,刘陈.可重排非阻塞三级Clos网络控制算法[J].电子工程师, 1999, No(8): 6-8.
[48] Cardot C. Comments on‘A simple control algorithm for the control of rearrangeable switching networks’[J]. IEEE Trans Commun, 1986, COM-34: 395.
[49] Jajszczyk A. A simple algorithm for the control of rearrangeable switching networks. IEEE Trans Commun, 1985, COM-33: 169-171.
[50] Kubale M. Comments on‘Decomposition of permutation networks’[J]. IEEE Trans Comput, 1982, C-31: 265.
[51] Ramanujam H R. Decomposition of permutation networks[J]. IEEE Trans Computers, 1973, C-22: 639-643.
[52] John D.Carpinelli. A Nonbacktracing Matrix Decomposition Algorithm for Routing on ClosNetworks[J]. IEEE Transactions On Communications, 1993, 41(8): 1245-1251.
[53] Yang Y Y, Masson G M. Nonblocking broadcast switching networks[J]. IEEE Trans Comput, 1991, 40(9): 1005-1015.
[54]顾乃杰,李栋,熊焰,等.无阻塞Clos-Type网上的多源点多播[J].计算机研究与发展, 2002, 39(3): 354-359.
[55] Gu N J, Li D, Pan W . Multiple-Multicast on FB-Clos Network [C] // Proceedings of the Fifth International Conference on Algorithms and Architectures for Parallel Processing. IEEE Press, 2002:359-364.
[56] Gao B, Hwang F K. Wide-sense non-blocking for multirate 3-stage Clos networks[J]. Theor. Comput. Sci., 1997, 182: 171–182.
[57] Liew S C, Ng M H, Chan C W. Blocking and nonblocking multirate Clos switching networks[J]. IEEE/ACM Trans. Netw., 1998, 6(3): 307-318.
[58] Kabacin’ski Wojciech, Liotopoulos F K. Multirate Non-blocking Generalized Three-Stage Clos Switching Networks[J]. IEEE Trans. Commun., 2002, 50(9): 1486-1493.
[59] Turner J S, Melen R. Multirate Clos Networks[J]. IEEE Communications Magazine, 2003: 38-44.
[60] Ngo H Q. A new routing algorithm for multirate rearrangeable Clos networks[J]. Theoretical Computer Science, 2003, 290(3): 2157-2167.
[61] Ngo H Q, Vu V H. Multirate rearrangeable clos networks and a generalized edge coloring problem on bipartite graphs[C]//Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, Baltimore, Maryland, ACM Press, 2003: 834-840.
[62] Benes V. Mathematical Theory of Connecting Networks and Telephone Traffic[M]. New York: Academic, 1965.
[63] Hwang F K. Rearrangeability of multiconnection three-stage Clos networks[J]. IEEE Trans. Netw., 1972, 2: 301-306.
[64] Hwang F K. Control algorithms for rearrangeable Clos networks[J]. IEEE Trans. Commun., 1983, 31(8): 952-954.
[65] Ohta S. A simple control algorithm for rearrangeable switching networks with time division multiplexed links[J]. IEEE J. Select. Areas Commun., 1987, 5(8): 1302-1308.
[66] Park Y, Cherkassky V. Neural Network for Control of Rearrangeable Clos Networks[J]. International Journal of Neural Systems, 1994, 5(3): 195-205.
[67] Liotopoulos F K, Chalasani S. Semi-Rearrangeably Nonblocking Operation of Clos Networks in the Multirate Environment[J]. IEEE Trans. Netw., 1996, 4(2): 281-291.
[68] Liotopoulos F K. Split-connection rearrangeably nonblocking operation of three-stagemultirate Clos networks[J]. Computer Communication, 2002, 25(17): 1584-1595.
[69] Yang Y Y, Wang J. A new design for Wide-Sense Nonblocking Multicast Switching Networks [J]. IEEE Transactions on Communications, 2005, 53(3): 497-504.
[70]程亮,李乔. 4级Clos网络不阻塞的条件[J].上海交通大学学报, 2004, 38(5): 838-841.
[71] Hwang F K, Jajszcyk A. On Nonblocking Multiconnection Networks[J]. IEEE Trans on Communications, 1986, 34(10): 1038-1041.
[72] Jajszcyk A. Comments on three-stage multiconnection networks which are nonblocking in the wide sense[R]. Bell Syst. Tech, 1983, vol 62: 2113-2114.
[73] Beizer B. Conference Nonblocking Switching Networks[J]. IEEE Transactions On Communications, 1972, COM-20(5): 942-946.
[74] Lawrie D H. Access and Alignment of Data in Array Processor[J]. IEEE Trans. Computers, 1975, C-24(12): 1145-1155
[75] Opferman D C, Tsao-Wu N T. On a class of rearrangeable switching networks[J]. Bell Syst.Tech, 1971, 50(5).
[76] Andresen S. The looping algorithm extended to base 2t rearrangeable switching networks[J]. IEEE Trans .comm, 1977, COM-25: 1057-1063.
[77] Nassimi D, Sahni S. Parallel algorithms to set up the benes permutation network[J]. IEEE Trans. Comput., 1982, C-31: 148-154.
[78] Maron D M, Mendlovic D. Comment on‘A New Routing Algorithm for a Class of Rearrangeable Networks’[J]. IEEE Trans. Computers, 1997 46(6): 734.
[79] Lee T. Nonblocking Copy Networks for Multicast Packet Switching[J]. IEEE Journal on Selected Areas in Communications, 1998, 6(9): 1455-1647.
[80] Park J, Jacob L, Yoon H. Performance Analysis of a Multistage Interconnection Networks using a Multicast Algorithm[J]. Proc. of the High-Performance Computing on the Information Superhighway, Seoul, Korea, April 1997: 79-84.
[81] Xu H, Gui Y, Ni M L. Optimal Software Multicast in Wormhole-Routed Multistage Networks[J]. IEEE Trans. Parallel and Distributed Systems, 1997, 8(6): 597-607.
[82]王晓东,周兴铭.多级互连网中的规约通讯[J].计算机工程与设计, 1997, 18(5): 10-15.
[83]刘勇,顾乃杰,任开新,等.基于Omega网的新型自路由多播网络[J].山东大学学报, 2006, 36(4): 37-43.
[84] Seo S W, Feng T Y, Lee H L. Permutation Realizability and Fault Tolerance Property of the Inside-Out Routing Algorithm[J]. IEEE Transctiongs on Parallel and Distributed Systems, 1999, 10(9): 946-957.
[2] Yang Y Y, Wang J C. A Class of Multistage Conference Switching Networks for Group Communication[J]. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(3): 228-243.
[3] Yang Y Y, Masson G M. Broadcast Ring Sandwich Networks[J]. IEEE Trans Computers, 1995, 44(10): 1169-1180.
[4] Houlahan J F, Cowen L J, Masson G M. Hypercube Sandwich Approach to Conferencing[J]. Supercomputing, 1996, 10(3): 271-283.
[5] Du Y, Masson G M. Strictly Nonblocking Conference Networks Using High-Dimensional Meshes[J]. Networks, 1999, 33(4): 293-308.
[6] Yang Y Y. A New Conference Network for Group Communication[J]. Proc. 2001 Int’l Conf. Parallel Processing, 2001: 141-148.
[7] Duato J, Yalamanchili S, Ni L M. Interconnection Networks: An Engineering Approach. Morgan Kaufmann, 2002.
[8] Wong C K, Gouda M, Lam S S. Secure Group Communications Using Key Graphs[J]. IEEE/ACM Trans Networking, 2000, 8(1): 16-30.
[9] Baldi M, Ofek Y, Yener B. Adaptive Group Multicast with Time-Driven Priority[J]. IEEE/ACM Trans Networking, 2000, 8(1): 31-43.
[10] Mishra S, Fei L, Lin X, Xing G. On Group Communication Support in CORBA[J]. IEEE Trans Parallel and Distributed Systems, 2001, 12(2): 193-208.
[11] Gopal A, Gopal I, Kutten S. Fast Broadcast in High-Speed Networks[J]. IEEE/ACM Trans Networking, 1999, 7(2): 262-275.
[12] Yang Y Y, Wang J. Optimal All-to-All Personalized Exchange in Self-Routable Multistage Networks[J]. IEEE Trans Parallel and Distributed Systems, 2000, 11(3):261-274.
[13] Suh Y, Shin K G.. All-to-All Personalized Communication in Multidimensional Torus and Mesh Networks[J]. IEEE Trans Parallel and Distributed Systems, 2001, 12(1): 38-59.
[14] Wang S Y, Tseng Y C. Algebraic Foundations and Broadcasting Algorithms for Wormhole-Routed All-Port Tori[J]. IEEE Trans Computers, 2000, 49(3): 246-258.
[15] Libeskind-Hadas R, Mazzoni D, Rajagopalan R. Tree-Based Multicasting in Wormhole-Routed Irregular Topologies[J]. Proc. 12th Int’l Parallel and Distributed Processing Symp, 1998: 244-249.
[16] Kumar D R, Najjar W A, Srimani P K. A New Adaptive Hardware Tree-Based MulticastRouting in K-Ary N-Cubes[J]. IEEE Trans Computers, 2001, 50(7): 647-659.
[17] Yang Y Y, Wang J. A New Self-Routing Multicast Network[J]. IEEE Trans Parallel and Distributed Systems, 1999, 10(12): 1299-1316.
[18] Zegura E W, Ammar M H, Fei Z, S Bhattacharjee. Application-Layer Anycasting[J]. IEEE/ACM Trans Networking, 2000, 8(4): 455-466.
[19] Xuan D, Jia W, Zhao W, Zhu H. A Routing Protocol for Anycast Messages[J]. IEEE Trans Parallel and Distributed Systems, 2000, 11(6): 571-588.
[20] Yang Y, Masson G M. The Necessary Conditions for Clos-Type Nonblocking Multicast Networks[J], IEEE Trans Computers, 1999, 48(11): 1214-1227.
[21] Pattavina A, Tesei G. Multicast nonblocking switching networks[J]. IEEE Trans Computers, 2002, 50(8): 1240-1243.
[22] Yang Y, Wang J. Nonblocking k-Fold Multicast Networks[J], IEEE Trans Parallel and Distributed Systems, 2003, 14(2): 131-141.
[23] Yang Y Y. A New Design for Wide-Sense Nonblocking Multicast Switching Networks[J]. IEEE Trans On Communications,2005, 53(3).
[24]张联,顾乃杰,刘刚,等.采用二进制寻路法和多Omega网络的自路由无阻塞多级网[J].计算机应用, 2005, 25(12): 2923-2934.
[25]顾乃杰,潘伟,李栋,等.一种新型的可重排多播网络[J].小型微型计算机系统, 2003, 24(2): 179-183.
[26]张联,刘刚,顾乃杰.多播3-Omega交换网的设计思想[J].计算机工程, 2006, 32(17): 184-186.
[27] Shannon C E. Memory requirements in a telephone exchange[R]. Bell System Tech.J, 1950, 47(8): 899-906.
[28]王鼎兴,陈国良.互联网结构与分析[M].北京:科学出版社, 1990.
[29] Lee C, Oruc A Y. Design of Efficient and Easily Routable Generalized Connectors[J]. IEEE Trans Communication, 1995, 43(2-4): 646-650.
[30] Nassimi D, Saahni S. Parallel Permutation and Sorting Algorithms and a New Generalized Connection Network[J]. J.ACM, 1982, 29(3): 642-667.
[31] Ted H, Szumanski.Design Principles for Practical Self-Routing Nonblocking Switiching Networks with O(nlogn)Bit-Complexity[J]. IEEE Trans Computers, 1997, 46(10): 1057-1068.
[32] Clos C. A Study of Nonblocking Switching Network[J]. Bell System Tech.J, 1953, 32(2): 406-424.
[33] Duguid A. Structural Properties of Switching Networks[R]. Brown University ProgressReport BTL-7, 1959.
[34] Slepian D. two Theorems on a Starticular Crossbar Switching Network[R]. Unpublished manuscript, 1952.
[35] Hall P. On Representatives of subsets[J]. J.London Math.Soc., 1935, vol(10): 26-30.
[36] Waksman A. A Permutation Network[J]. J.ACM, 1968, 15(1): 159-163.
[37] Wu C L, Feng T Y. On a Class of Multistage Interconnection Networks[J]. IEEE Trans Computers, 1980, 29(8): 694-702.
[38] Wu C L, Feng T Y. On a Class of Rearrangeable Networks[J]. IEEE Trans Computers, 1992, 41(11): 1361-1379.
[39] Wu C L, Feng T Y. Routing Techniques for a Class of Multistage Interconnection Networks[J]. Proc.of the ICPP, 1978: 197-205
[40] Feng T Y, Seo S W. A New Routing Algorithm for a Class of Rearrangeble Networks [J]. IEEE Transactions on Computers, 1994, 43(11): 1270-1280.
[41] Paull M. Reswitching on Connection Networks[J]. Bell System Tech, 1962, 41(3): 833-855.
[42] Benes V E. On Rearrangeable Three-Stage Connection Networks[J]. Bell System Tech, 1962, vol(41): 1481-1492.
[43] Benes V E. Semilattice Characterization of Nonblocking Networkings[J]. Bell System Tech, 1973, vol(52): 697-706.
[44] Thurber K J, Masson G M. Distributed-Processor Communication Architecture[J]. D.C.Heath and Company, 1979.
[45] Gordon J,Srikanthan S. Novel algorithm for Clos-type networks[J]. ElectronLett,1990,26(21):1772-1774.
[46] Lee H Y, Hwang F K, Carp inelliD. A new decomposition algorithm for rearrangeable Clos interconnection networks[J]. IEEE Trans on Commun, 1996, 44(11): 1572-1578.
[47]曾峰,刘陈.可重排非阻塞三级Clos网络控制算法[J].电子工程师, 1999, No(8): 6-8.
[48] Cardot C. Comments on‘A simple control algorithm for the control of rearrangeable switching networks’[J]. IEEE Trans Commun, 1986, COM-34: 395.
[49] Jajszczyk A. A simple algorithm for the control of rearrangeable switching networks. IEEE Trans Commun, 1985, COM-33: 169-171.
[50] Kubale M. Comments on‘Decomposition of permutation networks’[J]. IEEE Trans Comput, 1982, C-31: 265.
[51] Ramanujam H R. Decomposition of permutation networks[J]. IEEE Trans Computers, 1973, C-22: 639-643.
[52] John D.Carpinelli. A Nonbacktracing Matrix Decomposition Algorithm for Routing on ClosNetworks[J]. IEEE Transactions On Communications, 1993, 41(8): 1245-1251.
[53] Yang Y Y, Masson G M. Nonblocking broadcast switching networks[J]. IEEE Trans Comput, 1991, 40(9): 1005-1015.
[54]顾乃杰,李栋,熊焰,等.无阻塞Clos-Type网上的多源点多播[J].计算机研究与发展, 2002, 39(3): 354-359.
[55] Gu N J, Li D, Pan W . Multiple-Multicast on FB-Clos Network [C] // Proceedings of the Fifth International Conference on Algorithms and Architectures for Parallel Processing. IEEE Press, 2002:359-364.
[56] Gao B, Hwang F K. Wide-sense non-blocking for multirate 3-stage Clos networks[J]. Theor. Comput. Sci., 1997, 182: 171–182.
[57] Liew S C, Ng M H, Chan C W. Blocking and nonblocking multirate Clos switching networks[J]. IEEE/ACM Trans. Netw., 1998, 6(3): 307-318.
[58] Kabacin’ski Wojciech, Liotopoulos F K. Multirate Non-blocking Generalized Three-Stage Clos Switching Networks[J]. IEEE Trans. Commun., 2002, 50(9): 1486-1493.
[59] Turner J S, Melen R. Multirate Clos Networks[J]. IEEE Communications Magazine, 2003: 38-44.
[60] Ngo H Q. A new routing algorithm for multirate rearrangeable Clos networks[J]. Theoretical Computer Science, 2003, 290(3): 2157-2167.
[61] Ngo H Q, Vu V H. Multirate rearrangeable clos networks and a generalized edge coloring problem on bipartite graphs[C]//Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, Baltimore, Maryland, ACM Press, 2003: 834-840.
[62] Benes V. Mathematical Theory of Connecting Networks and Telephone Traffic[M]. New York: Academic, 1965.
[63] Hwang F K. Rearrangeability of multiconnection three-stage Clos networks[J]. IEEE Trans. Netw., 1972, 2: 301-306.
[64] Hwang F K. Control algorithms for rearrangeable Clos networks[J]. IEEE Trans. Commun., 1983, 31(8): 952-954.
[65] Ohta S. A simple control algorithm for rearrangeable switching networks with time division multiplexed links[J]. IEEE J. Select. Areas Commun., 1987, 5(8): 1302-1308.
[66] Park Y, Cherkassky V. Neural Network for Control of Rearrangeable Clos Networks[J]. International Journal of Neural Systems, 1994, 5(3): 195-205.
[67] Liotopoulos F K, Chalasani S. Semi-Rearrangeably Nonblocking Operation of Clos Networks in the Multirate Environment[J]. IEEE Trans. Netw., 1996, 4(2): 281-291.
[68] Liotopoulos F K. Split-connection rearrangeably nonblocking operation of three-stagemultirate Clos networks[J]. Computer Communication, 2002, 25(17): 1584-1595.
[69] Yang Y Y, Wang J. A new design for Wide-Sense Nonblocking Multicast Switching Networks [J]. IEEE Transactions on Communications, 2005, 53(3): 497-504.
[70]程亮,李乔. 4级Clos网络不阻塞的条件[J].上海交通大学学报, 2004, 38(5): 838-841.
[71] Hwang F K, Jajszcyk A. On Nonblocking Multiconnection Networks[J]. IEEE Trans on Communications, 1986, 34(10): 1038-1041.
[72] Jajszcyk A. Comments on three-stage multiconnection networks which are nonblocking in the wide sense[R]. Bell Syst. Tech, 1983, vol 62: 2113-2114.
[73] Beizer B. Conference Nonblocking Switching Networks[J]. IEEE Transactions On Communications, 1972, COM-20(5): 942-946.
[74] Lawrie D H. Access and Alignment of Data in Array Processor[J]. IEEE Trans. Computers, 1975, C-24(12): 1145-1155
[75] Opferman D C, Tsao-Wu N T. On a class of rearrangeable switching networks[J]. Bell Syst.Tech, 1971, 50(5).
[76] Andresen S. The looping algorithm extended to base 2t rearrangeable switching networks[J]. IEEE Trans .comm, 1977, COM-25: 1057-1063.
[77] Nassimi D, Sahni S. Parallel algorithms to set up the benes permutation network[J]. IEEE Trans. Comput., 1982, C-31: 148-154.
[78] Maron D M, Mendlovic D. Comment on‘A New Routing Algorithm for a Class of Rearrangeable Networks’[J]. IEEE Trans. Computers, 1997 46(6): 734.
[79] Lee T. Nonblocking Copy Networks for Multicast Packet Switching[J]. IEEE Journal on Selected Areas in Communications, 1998, 6(9): 1455-1647.
[80] Park J, Jacob L, Yoon H. Performance Analysis of a Multistage Interconnection Networks using a Multicast Algorithm[J]. Proc. of the High-Performance Computing on the Information Superhighway, Seoul, Korea, April 1997: 79-84.
[81] Xu H, Gui Y, Ni M L. Optimal Software Multicast in Wormhole-Routed Multistage Networks[J]. IEEE Trans. Parallel and Distributed Systems, 1997, 8(6): 597-607.
[82]王晓东,周兴铭.多级互连网中的规约通讯[J].计算机工程与设计, 1997, 18(5): 10-15.
[83]刘勇,顾乃杰,任开新,等.基于Omega网的新型自路由多播网络[J].山东大学学报, 2006, 36(4): 37-43.
[84] Seo S W, Feng T Y, Lee H L. Permutation Realizability and Fault Tolerance Property of the Inside-Out Routing Algorithm[J]. IEEE Transctiongs on Parallel and Distributed Systems, 1999, 10(9): 946-957.