从当时排名全球第1的“百年帝国”企业并曾长期垄断美国和世界市场的AT&T标识看,上面江泽民主席和著名图论与组合数学家、1993年任美国数学会主席的Ronald Graham教授可能是相见在Graham教授曾经领导过的这公司Bell实验室(即贝尔实验室,它是AT&T的研发机构)
Ronald Graham教授现担任由美国科学院主席、副主席等组成的Officers的5人领导成员;在此之前的美国科学院前一届选举中Ronald Graham也已是美国科学院17个执委之一,这届又更进一步,那会说不定下届可能会是正主席吗?
自离开贝尔实验室后-Ronald
Graham教授主要是在美国加州大学圣地亚哥分校 (University of California, San Diego)计算机科学与工程学系工作。他是美国科学院院士,美国艺术与科学院院士以及许多国家外籍院士等,他的主要研究领域是:图论组合数学及其相关应用学科,他曾任美国数学会(American Mathematical Society)主席,美国数学协会(Mathematical Association of America)主席。这Graham教授曾接受世界图论大师管校长的邀请来中国图论大会做报告…
Ronald Graham教授为第一主编和奖金最多的所有数学奖都获得的国际数学联盟主席László Lovász、国际数学联盟第二号人物-秘书长Martin
Grotschel三人合编2千余页的巨著《Handbook of
Combinatorics》(即《组合数学手册》)就是组合数学至高无上的圣经。
关于被认为是真正下一代大型多计算机系统的互联网络的n维d进位有向 de
Bruijn图B(d,n)(B(d,n)的顶点集V(B(d,n))={0,1,…,dn-1},B(d,n)的边集E(B(d,n))={(x,y): y≡xd+ a(mod dn), aÎ{0,1,…,d-1} or V(B(d,n))={x1x2…xn|
xiÎ{0,1,…,d-1}, i=1,2,…,n}, E(B(d,n))是由从x1x2…xn到d个x2x3…xna的所有arc组成, aÎ{0,1,…,d-1})。Ronald Graham主席和Chung院士以及在哈佛大学指导20个博士的Persi Diaconis院士在“Universal cycles for
combinatorial structures”一文说:‘还是容易知道限制的de Bruijn图是有哈密顿圈的网络的,但对于一般情形要确定哈密顿圈特别是泛圈等这些互联网络重要性能,将是NP难的’。正如此Hardy(其博士和名著合作者E. M. Wright是图论大师)说哈密顿圈是图论三大难题之一…
下面对互连网络做点注解:多处理器互连网络(简称互连网络)是指由若干个处理器按一定方式相互连接而构成的网络,作为并行处理系统的主干,其性质如何直接决定着整个系统性能的优劣。因此,对互连网络结构及其性质的研究是并行处理系统研究的极其重要课题。
我们将互连网络中的每个处理器看作一个顶点,两个处理器之间的连接看作一条边,则一个互连网络可抽象成一个图。于是对互连网络性质的研究可以转变为对其对应图的研究。在互连网络中,存在着许多要考虑的内在性质,其中重要的有正则性、低顶点度数、低直径、Hamiltonian路的存在性、高容错性、可诊断性等。
新型并行机的研制依赖于对新型互连网络的设计以及对互连网络内在性质的研究,迄今为止,国际上已提出许多互连网络,其中超立方体网络的总体性质是较好的,因而,研制出了多种超立方体型并行机,如nCUBE, CM-2, IPSC-860等,而这些并行机的研制和使用又引起人们对超立方体深入研究的兴趣(大约1975年个人计算机制造商IMS Associates宣布了基于Intel8080微处理器的256个点商用超立方体计算机。但任何网络其不同性质间是互相制约、相互冲突的,一般来说,不可能存在一种各方面性质都是最好的互连网络(因此,上面的de Bruijn网络被认为是最有可能取代已被广泛应用的超立方体网络结构,最有可能成为下一代大型多计算机系统的互联网络。受重视的还有augmented Cubes,Kautz
graphs,arrangement graphs,crossed cubes,Möbius cubes,star graphs等)。
由于超立方体计算机是迄今最著名之一的互连网络,因此,人们提出很多超立方体的变型,除了上面点到交叉立方体最著名的还有纽立方体,这里介绍2004年提出的局部纽立方体:n维局部纽立方体LTQn的每个顶点是由{0,1}组成的n元字符串,两个点x=x1x2…xn和y=y1y2…yn之间有边相连,当且仅当它们满足下列两个条件之一:(1)存在整数1≤k≤n-2,使得(a). xk=y'k (y'k是yk在{0,1}中的补), (b) xk+1=yk+1+xn,(c) x和y其分量都相同。(2)存在整数kÎ{n-1,n},使得x和y只有第k个分量不同。