CN1020972C - 超大规模计算机 - Google Patents

Abstract

一种通过在大量用户中分配并行计算机资源以提高并行计算机利用率的方法和装置。并行计算机在大量用户中分配以满足在计算机上同时运行的大量数据库和程序的要求，它是通过把并行计算机分成多个相互独立的处理机阵列的装置来完成的。并行计算机的构成允许由阵列中的每个实际处理机对其它并行处理机进行模拟，并提供模拟并行处理器间的通信，在虚拟存贮器中提供了存贮虚拟处理器的手段。

Description

本发明涉及大规模并行处理机，特别涉及对上述参照的日本专利号第109776/84和美国专利号4，598，400中所首先揭示的方法和装置的改进。

如上述′400专利中图1A（在此以图1形式重视）所示，在那些发明中的计算机系统包括：主机10，微控制器20，并行处理集成电路35的阵列30，数据源40，第一缓冲器和多路转换器/多路分配器50，第一、第二、第三和第四双向总线控制电路60、65、70、75，第二缓冲器和多路转换器/多路分配器80，以及数据接收器90。主机10可以是经过适当编程的市场上有售的通用计算机，例如数字设备公司生产的VAX（TM）计算机。微控制器20是常规设计的指令序列发生器，它能产生通过32位并行总线22而应用于阵列30的指令序列。微控制器20从线26上接收来自阵列30的一个信号。该信号是可用于数据输出和状态信息的通用信号或GLOBAL信号。总线22和线26并行连到每个集成电路35。结果，来自微控制器20的信号同时加到阵列30中的每个集成电路35上，而通过线26加到微控制器20上的信号则由该阵列中所有集成电路35的输出信号综合而成。

阵列30包含数千个相同的集成电路35，并且每个集成电路35包含若干个相同的处理器/存贮器36。在′400号专利所揭示的实施例中，指出阵列可以包含有32，768（＝2¹⁵）个集成电路35;每个集成电路35可包含32（＝2⁵）个相同的处理器/存贮器36。在递交本专利申请案时，包含多达4096（＝2¹²）个相同集成电路35，并且每个 集成电路包含16（＝2⁴）相同处理器/存贮器的阵列已由受让者作为连接机（TM）计算机被生产和发运。

处理器/存贮器36按二种几何结构构成和联接。一种几何结构是惯用的二维网格型式，其中处理器/存贮器按矩形阵列构成并且与该阵列中的四个最近的相邻单元相连。为了说明方便，该阵列的边用东、南、西、北表示。为了使每个处理器/存贮器与其四个最近相邻单元相连，每个处理器/存贮器全部都连接到处于网格上每行和每列相邻处理器/存贮器之间的电导线上。

第二种几何结构是15维的n-立方体的布尔结构。为了理解n-立方体连接型式，最好对集成电路从0到32，767加以编号，并用15位二进制数字来表示这些数字和地址。就象我们可以用二位数字，其中一个表示二维网络中第一维的位置，另一个表示第二维的位置来指定二维网络中一个物体的位置一样，以此类推，也可用一个数字来描述一个集成电路在布尔15-立方体的15维中的每一维的位置。然而，在一个n-立方体中，一个集成电路在每一维中只能有两种不同状态0和1中的一个。这样，一个由15位二进制数构成的地址，便可表示集成电路在n-立方体的15维中的位置。更进一步说，由于一个二进制数只能有二个值，0和1，同时由于每个集成电路系由一个15位二进制数唯一确定，所以每个集成电路具有与其地址仅有一位不同的15个其他集成电路。我们把这15个在地址上与第一个集成电路二进制地址仅差一位的集成电路称为该集成电路的最近相邻单元。熟悉汉明距离的数学定义的人将发现，该集成电路与15个最近相邻单元中的每一个各相隔一个汉明距离。

为了使上述参照申请中的集成电路35按布尔15-立方体形式连接，每个集成电路就由15根输入线38和15根输出线39与其最近相邻的单元相连。连到每个集成电路35的15根输入线38中的每一根是与布尔15-立方体型式的15维中的不同维相联系的，同样， 每个集成电路35的15根输出线39中的每一根也是与不同的维相联系的。布尔n-立方体连线的详细情况由日本专利申请128，294/86案提供。为了允许布尔15-立方体经由互连模式进行通信，把计算结果构成信息包的形式;这些包根据包内所含的地址信息，通过每个集成电路中的发送电路从一个集成电路发送到另一个集成电路。

一个典型的处理器/存贮器36由′400专利申请的图7A详细说明。如图7A所示，该处理器/存贮器包括32×12位随机存贮器（RAM）250，算术逻辑单元（ALU）280和标志控制器290。ALU接受三种来源的数据，即RAM中的二个寄存器和一个标志输出信号，并产生二个输出信号，即一个和输出信号，将要被写入二个RAM寄存器中的一个，以及一个进位输出信号供标志控制器中的某些寄存器和某个其它处理器/存贮器使用。

输入到RAM250的是地址总线152，154，156，158，来自ALU270的和信号输出线285，来自′400专利中图6B所示的通信接口单元（CIU）180的信息包输入线122，以及来自标志控制器290的允许写入线298。RAM250的输出线是256，257。线256，257上的信号来自RAM250中二个不同寄存器的同一列，其中一个被称为寄存器A，而另一个称为寄存器B。总线152，154，156，158根据微控制器20的指令字访问这些寄存器和列。

ALU280包含一个八选一解码器282，一个和信号输出选择器284以及一个进位输出选择器286。如′400专利中所详细说明的，这使它能产生包括算术加，逻辑或和逻辑与等多种功能的和信号及进位输出信号。ALU把操作同时加到三个二进制位，即来自RAM250中寄存器A和寄存器B的线256，257上的二个位和来自标志控制器290的线296上的一位。ALU具有二个输出：即写入RAM250中寄存器A的线285上的和信号;以及可能写入标志寄存器292并加到与该处理器/存贮器相连的其它处理器/存贮器36 的东、南、西、北以及数据捕获和译码系统输入端的线287上的进位信号。在进位线287上的信号也可通过信息包输出线123提供到通信接口单元180。

每个集成电路35还包括对于集成电路上的处理器/存贮器进行管理的某种电路以及使集成电路连接到它在布尔n-立方体中最近相邻集成电路的发送电路200。如′400专利案所揭示的，管理电路包括时标发生器140，对于来自微控制器20的指令进行译码并向集成电路的处理器/存贮器提供译出的指令的可编程逻辑阵列150，以及对集成电路的处理器/存贮器和与之相关的发送电路之间的输入和输出信息包的流动进行控制的通信接口180。

发送电路200控制信息包在布尔n-立方体中最近相邻集成电路之间的传送。通过该电路，信息包可以按布尔n-立方体型式中由任一集成电路发送到其它集成电路。如′400专利中图6B所示，电路200包括线分配器205，信息检测器210，缓冲和地址还原器215和信息发射器220，它们按上述顺序串联成环状，使一个元件的输出被提供为下一元件的输入，并且信息发射器220的输出提供到线分配器205上。线分配器205包括一个由15×15个大致相同的发送逻辑单元400构成的阵列。该阵列的每一列控制布尔15-立方体一个维中的最近相邻发送电路200间的信息包的流动。该阵列中的每一行控制发送电路200中的一个信息包的存贮。发送电路的信息检测器210把访问与该发送电路相关的处理器/存贮器的信息包提供给通信接口单元（CIU）180，信息发射器220从CIU180把信息包发射到正在发送电路中循环流动的信息包组中。

′400专利申请的图11示出了九个这样的发送逻辑单元400，在此用图2重视。在左列的三个单元与第一维相关，中间列的三个单元与第二维相关，右列三个单元与第十五维相关。每个单元列有一输出总线410，同与该维相关的输出线39相连。对于行来说，底行的 三个单元是阵列中最低的单元，它们接收来自输入线38的输入信号。顶行的三个单元是阵列中最高的单元。中间三个单元代表顶部和底部间的任何单元，但在图中示出的是与底行相连的三个单元。

图2中同时也示出了代表信息检测器210，缓冲和地址还原器215以及发送电路200中的信息发射器220等部分的三个处理和存贮装置420，它们处理与存贮来自线分配器205中的对应的三行单元400的信息。还有十二个相似的处理和存贮装置用来处理和存贮来自其它行的信息（图中未示）。

如果没有发生发送冲突，信息包将被从一个输入端送到第一维发送单元，并送到在一个信息周期内被寻址的处理器/存贮器的寄存器中。如果发生发送冲突，信息包将被暂时地在一个或多个中间点上存贮在发送电路的处理和存贮装置中;把信息包送到其目标需要多于一个发送周期。

利用图2可以方便地对每个发送单元400的输入和输出端作简要的说明。例如底行的三个单元400所指出，来自布尔15-立方体的不同维的信息包被加到NAND门405。这些门只有在复位（reset）情况下才关死。信息包反相后成为每个NAND门405的输出，被加到最低行中一个单元400的输入端L-in。一个表明在L-in端有信息包出现的信号也加到同一单元的输入端LP-in。对于底行的每个单元来说，该信息出现信号被接地，以便为位于底行下一列中的单元创造对所接受的信息包作进一步处理的条件。这种表明在单元输入端有信息包出现的信息出现信号被用于整个发送电路200，以便为整个发送电路200建立发送信息包所需的数据通道。

从某一线38接收到的信息包从一列中最低单元400的M-OUT端被送出，并被加到其直接右方一列中的单元400的M-IN端。与此同时，信息出现信号从MP-OUT端送出，送到其直接右方单元的MP-IN。

任一单元400的M-IN端接收得的信号可在任何一个总线端（U-OUT输出端或M-OUT端送出该单元，依赖于网络中其他信号是什么内容。在一列中所有单元400的总线端是连到公共输出总线410上的，该公共总线410通过NOR门（异或门）415连到输出线39，再连到布尔n-立方体中该维的最近邻近单元上。异或门415的另一输入是定时信号t-INV-OUT-n，其中n是维数。该定时信号对信息包中重复地址中适当的地址位求反，以便当信息包通过布尔15-立方体时修正该地址。

从U-OUT端离开单元的信息即时地被加到同列中直接上方单元的L-in端，并且由该单元按在L-in端接收到的任一信号同样处理。信息出现信号按同样方式从UP-OUT端传送到它的直接上方单元的LP-in端。

在每列中的单元400中的电路被设计成能在每列（或每维）的输出总线410上放置访问该维的信息;该信息在最靠近顶部的一行中流转，并把所有行向顶行压缩。为达到此目的，在每列中提供控制信号允许（G）和全满（AF），向该列中的各个单元提供在该列各个单元的状态信息。特别是，允许信号（G）通过经由G-in和G-OUT端顺次加到单元中每一列的信号，控制对每列（或每维）的输出总线410的存取。传播该信号的电路向访问该维地址的在列中的最高位置的信息包获得总线，并且防止该列中的较低单元中的信息传送到输出总线上。全满（AF）信号则通过在每个单元的AF-OUT端和AF-in端，向单元指明在该列中在它上方的各个单元是否有信息，来控制把信息从一个单元400传输到同一列上的它的上方单元。如果任一个上方单元是空的，位于较低单元中的信息就会移到该列中的上一单元。

对于顶行中的单元，输入到端头的信号总是高电位的。对于这些单元，加到G-in端的输入信号是复位信号的反码，因此除了复位 期间都为高信号。结果，在一列的顶部单元中的信息包一般将送到输出总线410上，如果访问的是该维地址。如果输出线39断了，通过给与该线相对应维的顶部单元的G-in输入端一个低电平信号，就可把该线从互连的15-立方体网络中去掉。在单元400的最低行中，来自G-OUT端的允许信号常用于控制一个旁路晶体管425，它能使输出总线接地。特别是，如果在那输出线上没有信息，则给那维的输出线都写入0位。

在单元中有某些触发器的工作情况由定时信号t-COL-n控制，其中n是维数，而其他触发器由基本时钟信号phil定时。从以下说明可以明显看出，每列中的发送单元与阵列30中的所有发送电路的同一列中的所有其他发送单元将同步进行工作。

本发明用几千个相同的并行工作的处理器/存贮器打开了计算的全新远景。由于串行的计算机的限制而不能解决的种种问题现在能在合理的时间内通过并行计算机例如连机计算机实现。

计算能力的大大增加，促进了研究使现有并行计算机不堪负担的更复杂问题的兴趣，并且还促进了对于越来越大的并行计算机的需求。同时，并非每一个可由并行计算机解决的问题都需要非常大的计算机进行处理。有些问题缺乏足够的数据去占用大型并行计算机的所有资源;其他一些问题则对并行计算机的计算能力缺乏严格的要求。除非能发现一种方法，在所有时间内都利用并行计算机的大部资源，否则从经济上来说，很难证明用这样的计算机是值得的。

一种折衷的方法是，利用多余的处理能力和存贮容量以模拟附加的并行处理机，如上述参照申请日本专利申请第39301/87号所描述的。根据那种技术，与每个实际处理机相关的存贮器可分为多个子存贮器，并且每个子存贮器可被相继利用，就象它与一个独立的处理机相连一样。这样，第一条或第一组指令被加到并行计算机 的所有处理器上，至少使一些处理器处理第一子存贮器中的第一个（或一组）单元中的数据。以后，这同样的一条或一组指令被加到计算机的所有处理器上，至少又使一些处理机处理存贮在第二子存贮器中相同的第一单元的数据。对每一个子存贮器均以此类推。虽然该技术在许多情况下都很有用，处理每组模拟处理器中数据的实际处理器机仍然是传统的顺序（或者Von    Neumann）处理器。其结果是，如果有大量模拟处理器和/或大量数据与实际处理器相关，在实际处理器中会有出现Von    Neumann式的瓶颈阻塞。

本发明的目的，旨在提供一种通过在大量用户中合理分配并行计算机的资源从而改善并行计算机利用率的方法和装置。根据本发明，在大量用户中分配一台并行计算机以满足在计算机上同时运行多个程序和数据库的要求。它是通过把并行计算机分成多个处理器阵列来完成的。每个处理器陈列都可独立于其它处理器陈列使用。该种划分是动态的，即是说这种划分能够容易地改变，并且在分时环境中实际上能在机器的二个相继时间片之间改变。

此外，并行计算机能如′301申请案所述的那样构成，使阵列中的每个实际处理器都能模拟附加的并行处理机，并能提供所模拟的并行处理机间的通信。根据本发明，不仅在第一特殊实际处理器同与它相关的模拟处理器相互之间进行通信是可能的，而且在与任何实际处理器相关的任何模拟处理器同与并行计算机中另一任意实际处理器相关的别的模拟处理机之间进行通信也成为可能。通过与虚拟存贮器相似的概念，我们此后把这些模拟处理器看作虚拟处理器。此外，根据本发明，还提供了在虚拟存贮器中存贮虚拟处理器的手段。

本设计的结果，可能制造出具有数量级为1，000，000个实际处理器和数量级为1，000，000，000，000个虚拟处理器的并行计算机。而且，由于计算机可动态地重新组合成多个独立的处理机阵列，这 样大小的装置能被大量用户分享，每个用户只是用了整个计算机的一部分，适合于解决该问题当时所需的容量。要特别指出，大约1，000用户可通过局部网络与并行计算机相接。

为了在处理器之间提供通信，实际处理器按足够大小的二进位n-立方体型式互联，在立方体中给每个实际处理器指定唯一的位置，每个虚拟处理器被指定其独自的地址。这样的地址结构允许对2⁴⁰个虚拟处理器进行编址。

本发明中并行计算机的其它特点还包括：

计算机支持常规的每次一字（word-at-a-time）的指令集。另外，它还支持并行指令的同构集。对于每次一字的运算，对应数据的并行运算是对整个数据集同时进行的。

计算机还提供硬件，支撑在多个处理器间分配和同步执行指令。结果，通过机器的那些运算彼此间将按完全确定的次数发生。

用户可能按需要来分配尽可能多的冗余存贮量以保证重要事务的可靠运算。其范围可以从简单的非关键应用的自检，直到无失效事务的四倍模块全冗余量。由于冗余部分只根据需要分配，故冗余量的花费只是当需要冗余量时才能发生。

本发明的这些和其它目的，特征和优点将从以下对本发明最佳实施例所作的描述中明显看出，其中：

图1是已有技术中并行处理机的结构图;

图2是图1中的并行处理机的发送电路的结构图;

图3是本发明的最佳实施例的总体结构图;

图4是本发明一个处理器单元的结构图;

图5和图6是把图4所示的处理器单元组织到并行处理机阵列中的结构说明图;

图7是说明图4所示的处理器单元的部件的详细结构图;

图8-12是图7的部件的详细结构图;

图13是本发明的最佳实施例寻址方式的说明;

图14是有助于理解本发明的结构示意图。

如图3所示，本发明的最佳实施例是一个系统300，它包括多个用户终端310A-N，局部网络320以及一个处理器阵列330。典型地，每个终端包括由键盘314和CRT显示316构成的控制台312，一些硬拷贝输出例如打印机（图中未画），以及位于终端和局部网络320间的接口318。如果需要的话，通常的个人计算机可用作终端310。

处理器阵列330典型地包括：262，144（＝2¹⁸）个实际处理器部件（PPU），与每个处理器相连的四兆字节的高速读/写或者随机存贮器，外加的低速大存贮量读/写存贮器以及扩展支持电路，兆兆字节的高速存贮器典型地是由集成电路存贮芯片来提供的。大存贮量读/写存贮器可能为例如32.768（2＝¹⁵）个硬盘驱动器，每个具有300兆字节的容量，总的容量是10兆兆字节。262，144个PPU按18维超立方体加以联结，其中每个PPU沿着超立方体的十八个边的每一边连结18个相邻的PPU，可详细说明如下。

局部网络320把处理器阵列330中的一些PPU与终端310相连，这样特定的终端与特定的PPU通信。这些PPU依次地动态控制阵列中其它PPU，后者又递归地控制更多的PPU，以对特定的问题提供充分的处理功能和存贮器。局部网络最好是象开关一样灵活，使任一终端可与连网的任何PPU相连，并且，这些连接随时可按需要改变，甚至就象在分时环境下所需的经常程度一样。任何常用的局部网络，例如以太网（TM）系统或digital的PBX均可用于该目的，只要它能提供足够的能力以连接包含在系统300中的终端的数目。如果需要，可用多个局部网络。典型地，局部网络应该能连接本发明的系统中的1000个终端。

可以看出，本发明的装置提供了比传统机器上实际使用更多的 RAM数。它允许全部数据库存贮在主存贮器中，其中存取时间成千倍地快于磁盘。顺序机器使用兆兆字节的主存贮器主要是不经济，因为只有一个用户在一个单元进行存取，其余的都闲置着。在本发明中不会发生这样的问题，这是因为存贮器的许多部分被同时存取。

根据以上参照申请所揭示的，通过把与PPU相连的存贮器分小，并把每个分存贮器指定给不同的虚拟处理器，可使每个PPU作为多个虚拟处理器来工作。根据本发明，存贮器的划分甚至能扩展到虚拟存贮器，例如硬盘或磁带存贮装置。进而，每个虚拟处理器在计算机的处理过程中可被认为是等效于实际处理器。

根据本发明，用户可以对PPU指定数据处理和存贮的要求，PPU能构成足以满足这些要求的一组处理器（包括实际处理器和虚拟处理器）。有利的是，该组处理器可用递归方法构成，这样一个处理器控制一个或多个其它处理器而其他处理器又控制更多的处理器，依此类推。最好是，数据库的每个成份对处理器是一对一地存贮的，且处理器也按与数据库相同的结构构成，这样安排的结果是：

1.每个处理器能够完成常规的Von    Neumann型运算，包括算术/逻辑运算，数据移动和常规的例如子程序或分支运算等控制流。

2.每个处理器能够支配一组数据处理器，使它们在并行指令执行过程中受它控制。支配处理器称为控制处理器，被支配的处理器称为数据处理器，这些是相对术语，因为数据处理器具有控制处理器的全部能力，并能自身支配数据处理器。

3.每个处理器可以从其支配的数据处理器中选择一个上下文集合，该上下文集合是一组被并行操作的数据。该上下文集合是根据作用于所有数据处理器或当前上下文集合中所有数据处理器上的某个条件选择的。上下文集合可以被保存起来，也可以恢复。

4.每个处理机可以对其上下文集合中的所有数据并发执行并行运算。并行运算与分类目录1中的顺序运算完全相同，差别在于它们同时用于上下文集合中所有数据。这些包括所有数据操作，存贮器访问（通信），以及控制流操作。直至程序员能够看到的地方，这些运算都是在数据集合中的所有处理器上同时发生的。

5.每个处理器能够存取共享的数据库并把其中的部分数据装入存贮器。虚拟处理机同样也能修改数据库。

本发明中并行计算机的指令相似于传统计算机的指令。它们可分成三类：局部指令，并行指令，和上下文指令。

局部指令完全相同于传统计算机的指令，包括子程序调用，条件和非条件转移，返回，基于寄存器的算术数据移动，逻辑运算和测试。局部指令在控制处理器内执行。

并行指令就象局部指令一样，不过它们是在数据处理器的上下文集合中同时被执行。成组的并行指令称为命令，是在上下文集合中在所有虚拟数据处理器上同时执行的。对于每个局部数据指令，存在有一个对应的并行数据指令。

上下文指令被用来指定将要进行并行处理的虚拟数据处理器集合。有四种上下文指令：

把所有满足某个条件的虚拟处理器设置为上下文集合;

把现行上下文的范围内满足某个条件的子上下文处理器作为上下文。

把现行上下文压入堆栈;

使现行上下文跳出堆栈。

这些上下文指令可与并行数据指令混合编组以形成命令。

命令是本发明的并行计算机中的基本同步单位，它也是控制处理器和数据处理器之间的通信单位。在最简单的情况中，一条命令为一条单个指令。它也可以是一组可一起执行的指令，而不考虑在 该命令中通过实际数据处理器的同步情况。控制处理器的基本作用是通过α路由器（图7）发出命令并且等待表明它已被所有数据处理器执行的回答。不同的虚拟处理器能够并一般地将在不同时刻执行命令中不同的指令。

命令也是在系统中对指令高速存贮的基本单位。这意味着在命令中所允许的指令数是有限的。因为一条命令可以包含调用指令，由命令完成的运算数目可以任意大。除子程序调用以外，命令中也可以包含有简单循环和在命令中的条件转移。

指令可根据简单的规则组成命令，这些规则保证命令中的指令能异步执行。这可以通过以下方法来实现，例如，仅允许包含非局部通信的指令在命令的最后指令中出现。

命令通过α路由器从控制处理器向各数据处理器广播。当命令被所有数据处理器执行时，由α路由器向控制处理器提供一个信号，该信号机制也被用于把在控制处理器中控制程序设计流的条件码组合起来。

如图4的结构图所示，每个PPU包括微处理器350，功能电路360，和存贮器370。PPU可以任选地包括一专用的数学电路以提高高速数学运算的性能。微处理器350，存贮器370和数学电路380可以是传统的集成电路。例如，微处理器350可以是Intel    8086而数学电路380可以是浮点加速器，例如Intel    8087。也可用Motorola    68000。有些微处理器例如Fairchild    clipper具有特别的优点，因为它们具有独立的指令和数据引脚。

存贮器370可以是任何高速大容量的读/写存贮器。举例说，该存贮器是由32个4×64千位集成电路芯片构成的阵列所提供的4兆字节存贮器。为了有利于错误检测和校正，可使用存贮奇偶和错误控制位的附加存贮器。随着更大容量的存贮器芯片能在市场上买到，还可增加存贮容量的大小和/或减少所需集成电路片的数量。

功能电路360负责管理存贮器接口，信息通路，错误校正，指令分配和同步，数据高速存贮和虚拟处理机控制。该电路接收来自PPU的信息并产生适合于驱动动态存贮器的地址信息。它还把数据送入或取出PPU的数据引脚送入或取出动态存贮器的数据引脚。该功能电路还执行把PPU用作虚拟处理机所需的所有管理功能。微处理器350，功能电路360和存贮器370的连接使功能电路360位于微处理器350和存贮器370之间，允许微处理器对比′400专利所述系统中更多的存贮器进行寻址，在′400专利中，微处理器和存贮器直接耦合在一起。与此同时，该结构还适于信息包发送，如下所述。

PPU由16个单元构成，这样从0-15的16个PPU和外围电路的集成电路将设在如图5所示的一块单电路板400上。外围电路包括硬盘接口410，总输入/输出电路420，自检电路430，时钟电路440，标识电路450和性能测量电路460。

硬盘接口410是标准的SCSI（小型机系统接口）接口，它连到PPU0上。它被设计成与下面将要说明的大容量存贮设备470相连，其最大通信带宽近似为每秒10兆位。在电路板400上的其他PPU通过用作文件服务器的PPU0与大容量存贮体相接。

输入/输出电路420是32位宽的并行口或串行口，连到PPU1上。该端口具有约为每秒50兆位的最大带宽。电路420把局部网络320与PPU1相接，该PPU1在网络中作为另一终端或简单地作为一并行或串行口。电路板400的其它PPU通过PPU1与输入/输出电路420相接。这样安排的结果，使得在任一终端310A-N处的用户可在处理器阵列330中对任何PPU进行选择寻址，就象用户能用连到电话网络中的任何电话一样。

自检电路430能够检测发生在电路板400上的任何错误，从而把该装置从系统中去除。一种有益的作法是，把它连到发光二极管 上，使之能提供视觉信号指明该装置正脱机等待维修。每个电路板包含其自己的时钟电路440，它同步于系统中其它PPU的时钟电路。标识电路450是一电可擦非易失性存贮器，它包含该电路板的生产和维修历史，序号等等。性能测量电路460检测软件的性能。

大容量存贮体470典型地包括一个标准的盘控制器480和一标准的5-1/4英寸300-兆字节驱动器490，在同一控制器上还可增加七个附加驱动器，使总的存贮容量达2400-兆字节。

电路板400和存贮体470装在箱500中，后者包括由16块板400和16个存贮体470组成的箱体502。这样，在具有262，144个PPU的系统的情况下，可用1，024（＝2¹⁰）个箱来容纳PPU，箱与箱通过光导纤维通信线互连。与此相应，每个箱包括一个或多个通信装置505，每个通信装置505包括至少一个用于在箱体间转发并传送数据的光纤收发通信装置。该收发装置可以是常用的光纤收发装置，具有每秒100兆位的数据传送率，并能够把一个箱中的不同PPU通过分时多路通信传送到其它箱中的PPU，以发挥光纤通信线带宽较大的优点。有益的是，在每个通信装置中至少用二个收发装置，这样，信号在每个通信装置中可以同时接收和发射。

最好，PPU330根据上述参照发明′294号所述的技术进行超立方体互连。这样，每个PPU在立方体网络中对应于超立方体的四维与同一电路板上的四个其它PPU连接，并且还连到在一个箱中其它4块电路板的PPU上，对应于超立方体的另外四维。在具有262，144个PPU的系统情况下，一个箱中的每个PPU还被连到十个不同箱中的十个PPU上。这另外的十对连接对应于超立方体余下的十个维。每个箱在这十维上的连接是通过一独立的通信装置505来完成的。

如图7所示，功能电路包含9个主要功能单元：地址映射器510，存贮器接口520，虚拟处理器（VP）定序器530，高速数据存贮器 540，错误校正器550，α路由器560，β路由器570，阻断器580，以及高速命令存贮器590。所有这些功能单元都做在单个集成电路或芯片上，但是也可用多个芯片来完成。地址引线532和数据引线582把虚拟处理器定序器530和阻断器580连到PPU的微处理器350上。地址引线522和数据引线552把存贮器接口520和错误校正器550连到PPU的存贮器370上。α引线562和立方体引线572把PPU的α和β路由器560，570连到其它PPU的α和β路由器上，下面还将详细说明。

如图8所示，地址映射器510包含一个PPU地址寄存器605，起始寄存器610，VP偏移寄存器615，VP增量寄存器620，以及一个页面表625。地址映射器还包括第一、第二、第三多路转换器630，635，640和第一，第二加法器645，650。地址映射器通过地址总线602接收来自VP定序器530的输入，映射器的输出通过实际地址总线652而送到存贮接口520代表页码的二位通过页位线654提供到VP定序器530。如图所示，地址总线是二十四位码宽，实际地址总线是二十二位码宽。

为了理解地址映射器的工作情况，理解本发明的寻址方式是很有帮助的。如图13所示，在系统中存贮了四种类型的地址：单元地址，路由器地址，虚拟地址，以及实际地址。为了提供足够的虚拟处理以满足1，000个用户的需要，本发明的系统提供甚至存贮在虚拟存贮器中的虚拟处理器。这样，即使实际贮在盘中的数据也可与虚拟处理器相联系。结果，本发明的系统被设计成可以支持一万亿个虚拟处理器（2⁴⁰）。由于整个地址空间原理上可由一个用户使用，所以CM2能够支持带有64位地址空间的寻址结构。

地址的最一般的形式需要64个存贮位的单元地址。该地址能在整个系统中的任何虚拟处理器中指出任何存贮位置。地址的最高40位指定正被存取的虚拟处理器。最低24位指定在那个虚拟处理器中 的位移。由于2⁶⁴大于整个系统虚拟存贮器的规模，所以在编码中为冗余留有余地。在虚拟处理器的40位中用18位指明虚拟处理器所在位置的PPU，另22位表示虚拟处理器所开始的那个字在该实际处理单元的虚拟存贮器中的地址虚拟处理器可在实际处理单元的24-位虚拟地址空间中任一32-位的边界偶地址上启动。

路由器地址是通信网络所用的地址。它们基本上是压缩形式的单元地址，是通过把24位偏移量和四乘虚拟处理地址的22位偏移部分加在一起而形成。路由器地址指明了系统中的某个实际处理器单元的虚拟存贮器中的一个单字。路由器地址的长度是42位，它对应于整个系统上虚拟存贮器的字数。

在PPU中，所有地址计数器以24位虚拟地址形式被存贮。在这样的一个地址中，8位码代表存贮器的页，16位码代表在该页中一个字节的地址。页是虚拟存贮系统请求高速存贮的单位。在任一给定时刻，在存贮器中实际可达64页。

24位虚拟地址由页面表625映射为22位实际地址。页面表是一个256个字乘6位的查找表，把虚拟存贮器中的每一个2⁶页映射为实际存贮器中的2⁶个页。

地址映射器510把虚拟地址带入功能电路，并把它或者变为存贮器的实际地址，或者变换为路由器地址以便通信。地址映射器被设计成能提供三种不同的寻址方式，普通，相对虚拟处理，以及扩展地址。在普通寻址方式中，24位实际地址从PPU中直接取出并分解成8位页号和16位偏移量。8位页号被用作页面表625的索引，它包含虚拟页面与实际存贮器的对应。当参照页面在实际存贮器中时，页面表将产生6位地址告诉页存在于实际存贮器的哪一部分。它与16位偏移量组合以形成直接通向存贮接口的22位实际地址。当参照页被“换出”时，页面表将通过页面位的置值来指明，并且发生一个中断，以允许页面从辅助存贮装置中转到实际存贮器中。页 面是在“先进先出”的基础上装入的，这样，新页将被装入到最初被装入页面的顶部。利用页位对某些页进行“线入”（wired    in）也是可能的，这样它们便永远不会移出到辅助存贮装置上。

寻址的第二种方式是相对虚拟处理器。在该情况下，来自总线的地址被当作相对于当前正在执行的虚拟处理器的偏移地址的偏移量。这两个24位地址通过加法器650加在一起以产生24位虚拟地址，和以前一样通过页面表转换为实际地址。虚拟处理器偏移量由虚拟处理器定序器设定，或者当虚拟处理器大小固定时由一个增量来设置。

寻址的最后一种形式是用于完成处理机相互通信的机制，在该情况下，是通过β路由器来计算相关函数的，其地址如下计算：目的点上的PPU的18位地址，被拼接到来自芯片（偏移量寄存器）的24位实际地址与装入到起始地址寄存器610中的24位起始字地址的和上。典型地，它是在前一周期扩展寻址运算的过程中装入的。当信息地址接收到以后，该接收地址的存贮器部分（等于一个起始地址和一个偏移量的和）将被用作虚拟存贮器的地址，并通过页面表按普通寻址方式索引到实际地址。

存贮器接口单元520负责寻址的实际多路转换和动态随机存贮器的存贮器刷新。如图9所示，接口单元520包含刷新计数器660，行数寄存器665，多路转换器670和比较器675。多路转换器670把22位实际地址在11根地址引线上作多路传送。刷新计数器660可为诊断目的而复位。存贮接口单元同样也设计成能够利用现今大多数动态随机存贮器所支持的快速成块存取方式。为了达到这点，存贮器接口单元的行寄存器665中存贮了最后被存取的行的行号。如果比较器675判定出存取是发生在先前存取相同的行上，则将执行一个快速周期以只选通地址的列部分。这样，对同一存贮器块的访问大约只需要普通随机存贮所需的一半时间。这对于顺序数据块的 存取特别重要。

虚拟处理器定序器530是一简单的有限状态机，用以迅速完成虚拟处理器开销所需的表操作。一个PPU通过在时间上顺序执行多路运算实现多个虚拟处理器的工作。PPU把存贮空间（包括其虚拟存贮器）的某一部分分配给每个虚拟处理器，尽管每个虚拟处理器的虚拟存贮器数量是完全不同的。典型地，由一个PPU实现的几个虚拟处理器将用于几种不同的任务。对于每个任务，PPU须按当前任务的上下文对所有处理器定序，向它们提供所执行的命令。同样，PPU必须对每个与任务顺序相关的命令定序。但是，对不在被执行的任务的上下文里的由PPU实现的虚拟存贮器不必定序。结果，大大节约了对由PPU实现的虚拟处理器的定序所需的时间。

虚拟存贮器和多任务上下文切换都由硬件直接支持，存贮器中的虚拟处理器的构成如图14所示。任务被链接在一起成为一个循环表，称为任务表，在任何给定时刻PPU包含一个指向任务表中一个任务的指针。通过定序器530的帮助，PPU依次循环通过每个任务，在走向下一个任务以前，对现有任务上下文中的每个虚拟处理器执行一个命令。这样，如果上下文相对较小，同所有处理器都放在现有上下文中进行处理所需的时间来比，它将在较短的时间内执行。

每个任务具有与它相关的一个标题，包含三种信息：指向现行上下文的指示器;指向存贮链接表的栈指针，以及指向任务中所有虚拟处理器清单的指针。定序器也包含一个指向任务表中下一个任务的指针，以及关于任务的辅助信息，例如优先级和运行统计等。PPU按链接表（从上下文指针处开始，直到链接表结束时停止）决定虚拟存贮器中每个虚拟处理器的单元位置。这些链表被存贮在存贮器受保护的区域内。

为了执行“推入上下文”的指令，PPU分配新的存贮部件并把现行上下文指针推入栈内，改变栈指示器使其指向栈顶。“跳出上下 文”指令则恰恰相反，只有当栈下溢时要用到栈顶的上下文指针。下一个最常用的操作是根据一些条件把上下文限制为现行上下文的子集合。在这种情况下，虚拟处理器表将根据条件分裂，从现行上下文开始。符合限定条件的虚拟处理器被加到表的末端。指向表尾的指针就成为现行上下文。这种方法使代表连续上下文的嵌套的子集合序列得以有效地存贮。根据这种设计，不在现行上下文中的虚拟处理器在命令执行过程中不会增加开销。

如图10所示，虚拟处理器定序器530包含5个主寄存器，其中每个都能够保持虚拟处理器的最高22位地址。上下文寄存器680保持指向现行上下文表起始地址的指针。栈寄存器685保持指向现行任务的上下文栈指针。栈顶寄存器680保持指向现行栈上下文表顶部的指针。任务寄存器695保持指向任务表中的下一个任务的指针，而下一个寄存器700保持指向虚拟处理器系列中下一个虚拟处理器的指针。如果需要，还可用另外的寄存器存贮所需的辅助信息。定序器530的输出通过多路转换器715被选择，以响应可编程逻辑阵列（PLA）710来的信号。

虚拟处理器定序器中包含一个由状态寄存器7C5和PLA710实现的有限状态机，以管理这些寄存器，并控制地址映射器和命令高速存贮器中的寄存器。该有限状态机排列所需的管理指令系列以完成任务和虚拟处理器的交换操作。状态机的输出取决于现行状态和来自功能电路其余部分的条件位，例如页面表625的页位。PLA也能够根据由零位检测器720检测得的现行数据是否为零有条件地作出变换。在某种意义上，虚拟处理器定序器是一个不带算术运算单元的非常简单的计算机。

数据高速存贮器540完全是传统的存贮只读数据的高速存贮器。

错误校正器550是标准的基于6位汉明码的单位错误纠正和多 位错误检测逻辑。如图11所示，它包含线驱动器740，745，750，755，用以计算奇偶位的错误控制电路760，765，检测奇偶错误的异或门770，判别一个错误能否被纠正的译码器775，以及用于校正检出错误的异或门780。错误控制电路760把错误纠正位加到写入实际存贮器的所有数据上。通过在错误控制电路765中重新计算从存贮器读出的数据的奇偶位以及在与门770中比较这些位和从存贮器读出的奇偶位，对由实际存贮器读出的所有数据进行检测。译码器775判别错误是否能被纠正，并且通过把合适的信号加到与门770（如果可能）来实现。如果发生多重错误，由译码器775反映出单元失效。

α和β路由器560，570被分别用作为指令和数据传送，并能分享实际通信线，尽管发送硬件是独立的。如图12所示，α路由器包含一个由触发器805A-N控制的与门800A-N阵列、第一、第二或门810，815，由触发器825A-N控制的多路转换器820A-N，由触发器832，834所控制的第一多路转换器830和由触发器842控制的第二多路转换器840。输入线802A-N被加到与门800A-N，输出线822A-N从多路转换器820A-N送出。这些线在二进制超立方体中把PPU的α路由器连到最近相邻的PPU的α路由器上。因此，与门800A-N的数目，多路转换器820A-N和与他们相关电路的数目对应于超立方体的维数，例如18，但为简明起见在此只示出了三个维。由于与每维相关的输入和输出线通向同一个α路由器，这些线如果需要可以多路复用。此外，由于这些线作为β路由器的输入、输出线通向相同的PPU。它们也能与β路由器的线多路复用。

α路由器用于分配和同步指令。它基本上起着与4，598，400专利申请所描述的指令分配树和“全局-或”（global-or）树相同的作用，除掉任何一个处理器或任何数量的处理器均可作指令的来源这一点与之不同。这些指令聚集在一起被称为命令。一条命令的执行是通过α路由器在整个机器中同步的，这样在下一条命令发出以前，一 条命令将被完全执行。

被广播发送的命令在来自本地阻断器580的命令进入线上接收，而从其他路由器上接收到的命令则通过命令输出线提供到命令高速存贮器540上。表明命令接收结束的同步信号在同步进入线上由PPU提供给路由器，表明从其他PPU来的一个命令接收结束的信号则经同步输出线提供给PPU。

α路由器的运算方式根据从PPU接收到的信号由触发器控制。这样，如果本地PPU要给其他PPU广播命令，由触发器842给多路变换器840置值以在命令进入线上传送信号，而触发器825A-N给多路转换器820A-N置值以传输这些信号。如果本地PPU接收来自另一个PPU的命令，触发器832，834被置值以把特定的输入维线指定给正在等待命令的多路变换器830。如果该命令要通到另一个PPU的话，触发器842也给多路变换器840置值，以把来自多路转换器830的信号传输给多路转换器820A-N。通过这样安排，一个PPU可以把命令广播给其最邻近单元中的每一个并以此控制它们;每个PPU可监听来自其最邻近单元之一的命令并被它所控制。

在一个命令发出以后，发布该命令的PPU通过同步信号监测命令的执行情况。PPU通过同步输入线把同步信号传输到或门815，并通过给触发器825A-N置值，使多路变换器820A-N传输来自或门815的信号。接受一个同步信号，可通过置值触发器805A-N，使与门800A-N能给或门810传送一个接收到的信号。或门810的输出也可通过或门815的输入端给其他PPU传送信息。通过这样安排，PPU可以有选择地等候从它所控制的那些最邻近单元PPU来的同步信号，而忽略其他那些它不控制的PPU所来的信号。

β路由器570基本上是与4，598，400专利中所描述的相同型号的路由器。如图2所示，它具有输入输出线38，39的阵列，输入输出线38，39通过图7所示的立方体引线572与超立方体中最近相邻 PPU的β路由器通信。信息包通过地址映射器510和高速数据存贮器540从微处理器提供到β路由器570，接收到的信息包通过同样部件提供到微处理器。输入和输出线可以多路复用，这些线也能与α路由器的线802A-N和822A-N多路复用。

β路由器主要负责三种不同的功能，它把信息包从一个PPU传输到另一个，完成4，598，400专利相同的功能。它产生对应于与之相关的PPU的存贮器请求的信息包，并把它传输给与其它PPU相关的存贮器。它接收来自其它PPU的要求送到与它相关的PPU的输入信息包，并适当传递这些信息。虽然这后二个功能是新的，但在每个功能中信息包的传送是与′400专利所揭示的一样的。

本发明的全部安装好的并行计算机是一个很贵的设备，或许是太大的一个设备以致于一个用户用任何长的时间也不能占据整个系统。计算机的一个设计前提是同时可被几千个用户使用。虽然一个用户的峰值要求可能非常高，但假设平均的需求是适中的，例如每个用户每秒1亿条指令。此外，假定用户能够利用共享资源，而不仅只是计算周期，例如，共享数据库里的信息。

由于用户通过共享空间和共享时间来分离计算机的空间和时间资源，故可把共享资源的技术称为空间共享与时间共享。就这种意义上说，空间共享可以被更精确地称为“空间一时间共享”，因它也能包含在时间上的多路转换。即使在每个用户在所有时间内给整个系统提交相同负载的情况下共享空间时间也能工作，但是就用户感觉到的利益来说，它工作得比上述情况更好，这是因为下列典型用户负荷的不均匀性所决定的。

闲置时间：许多用户在他们使用机器的时候，在大部分时间中事实上只需要很少的周期。对于能提供询问和共享数据库的事务系统尤其是这样。

非均匀并行性：当执行并行程序时，在程序中会有许多点，可 能有效地同时利用成千成百个虚拟处理器。还会有其他一些点，在那里单个单步执行已足够。

非均匀存贮器需要：许多用户在任何给定时刻只对计算机中一个兆兆位存贮器的相对较小部分要求直接存取。

数据的共同性：许多用户在一个短的时间周期内可能对同一数据库进行存取，使它在代价较低的情况下保存在主存贮器中。在共享软件中有相似的情况。

为了利用这些非均匀性，计算机根据运行时间的需求动态地把实际处理器分配给虚拟处理器。这样，用户占用的资源正比于实际所需量，而不是正比于想象中需用的资源量。

β路由器的特点之一是在不同用户中划分PPU的阵列，使共享空间成为可能。如图2所示，G-in输入端控制通信线39的存取，它能把信息包从一个PPU传送到另一个。如果该线断掉的话，通过给与那根线相连的G-in输入端提供一个低电平信号，就可以把该线从网络中去掉。根据本发明，超立方体的任何子立方体可以与超立方体的其余部分分开，只要在与通信线相连的G-in输入端提供一个低电平信号就行了，而所述通信线是连接超立方体的其余部分和子立方体的。例如，若要把一个包含256个PPU的子立方体从一个18维超立方体中分开，可以在子立方体的256个PPU中的每一PPU内与第8维到18维的通信线相连的G-in输入端提供一个低电平。同时，在超立方体的其它部分的大量子立方体也可同样与超立方体分开，其方法是通过给与不再用的那维通信线相关的G-in输入端提供低电平信号。

为了实现这一点，每个PPU的微控制器允许对G-in输入端进行存取，以便它能响应于一个子立方体特定配置给G-in加上低电平信号。这一存取举例说可通过一触发器（图中未画）来完成，该触发器的输出状态可由PPU的微处理器控制。

根据本发明，指令中的标志位表示了由其他PPU并行执行的并行指令。阻断器580检测该标志位。所有由PPU从存贮器中存取的数据通过阻断器580，如果数据的标志位指明是并行指令，则一条无操作指令被送到数据引线，阻断器把并行指令送到α路由器中以传送给其他PPU。如果标志位没有指明并行指令，则指令由数据引线提供给PPU。

命令高速存贮器590是用以存贮来自α路由器指令的存贮器。虚拟处理器定序器530将使PPU从命令存贮器中存取指令以实现每个虚拟处理器上的动作。命令存贮器大体上是一个存贮在每个任务中正在并行工作的指令的指令存贮器。典型地，该存贮器是256个字深度。

由于计算机内部元件的重复，自然可通过冗余技术提高其容错率。一种有益的作法是，在数据库中的所有存贮内容放在至少二个实际独立的装置中，这样，当一个存贮装置失效时，可使用来自后备装置中的数据，并复制给另一个后备装置。当一个处理器装置失效时，它便与系统分开直到它被替换，或者从剩余的可用处理机库中再分配实际的处理器。

在这类容错系统中最困难的问题是在出现错误时检测并分离它们，以及处理出错时刻正在加工的作业。在此，在任务被完美地完成的确信程度和分配给任务的硬件数量之间有一折中方案。在本发明的并行计算机中，用户根据任务的紧急程度，可在运行期间作出折中方案。任务可根据所需的冗余量按三种方式中的一种来完成。

在系统运行的最简单方式中，如图11所示的错误校正器电路550一类自检硬件被用于检测和分离错误。该硬件能够检测最常见类型的误差和错误，例如，没有校正的存贮器错误，失电，通信中无纠正的错误。在自检方式工作时，一旦错误被检测，当前作业停止，硬件重新配置以隔离失效部分，于是作业再从头重新开始。

尽管自检电路将检测发生的大多数错误，但是不能保证检测到每一类的错误。特别是许多发生在PPU本身的错误将不被检测。在双冗余方式中，运算系统在两个实际上独立的处理器的同构集合中执行二个相同的程序并在规定间隔处比较中间值。（按n-维立方体型式连接的通信系统的引线，正好给这类比较提供正确的通信路径）。比较机制保证错误检测，并分析错误为什么发生。一旦在双冗余方式中检测到错误，可用与自检方式中同样的方式处理。在诊断分析判别出哪个处理器出错之前，两个处理器都与系统分开。

自检和双冗余方式的缺点是当错误发生时它们需要重新开始作业。这对于不易方便地拆成相对较小作业的任务来说是可以接收的。但是，一些任务具有实时处理要求，不允许作业的重做。对于这二种情况中的任何一种，四倍冗余方式是达到无错运行的合适方式。

在四倍冗余方式中，应用的四个相同拷贝同步运行。每个任务把其运算按循环形式与其他的相比较;例如，A检查B，B检查C，C检查D，而D检查A。当出现一个错误时，通过对失配的比较将它检测和分离开来。在这种情况下，处理的正确状态从无错任务之一复制到另一个子立方体中，运行连续，不发生明显中断。使用四倍而不是三倍的冗余能在n-维立方体型式中获得进行比较所需的合适的连线。

可明显看出，在本发明的思想和范围内，上述方法和装置可以有各种变型。例如，当本发明被描述成以二进位超立方体形式构成并行处理机的阵列时，不言而喻也可使用其它配置，例如′400专利提出的方法。在那种情况下可以看出，对于通信装置，例如上面所述的α和β路由器，也需要适当改进，使在处理器阵列中能有合适的信号指示。

Claims (24)

1、一种并行计算机，包括：

多个处理器单元，每个处理器单元包括一个处理器、一个读/写存贮器和一个控制电路；

其特征在于它还包括：多个主机；以及

将所述主机连接到至少若干处理器单元以形成一种多处理机环境的互连装置；

所述每个处理器单元的控制电路包括：

通过经所述并行计算机中的通信线路，将信息包从一个处理器单元发送到另一个处理器单元，以互连所述处理器单元的装置，以及

将所述并行计算机划分成二组或多组互连的处理器单元、各组之间相互不影响的装置，所述划分装置包括：

有选择地控制对每一所述信息包通信线路进行访问的装置；以及

根据控制电路从主机接收到的信号来设定所述控制的装置，以便阻止对选定的信息包通信线路进行访问的装置。

2、如权利要求1所述的并行计算机，其特征在于，所述处理器单元以超立方体形式互连，每一通信线路沿超立方体的一维建立处理器单元之间的互连，并由控制装置有选择地控制对超立方体每一维的访问，超立方体的各部分可以划分为同构单元。

3、如权利要求1所述的并行计算机，其特征在于，所述处理器单元以超立方体形式互连，每一通信线路沿超立方体的一维建立处理器单元之间的互连，所述互连装置包括：

输入阵列，其数量与超立方体的维数相等，所述各输入端通过所述通信线路接收来自超立方体中最近相邻的处理器单元的信号;

输出阵列，其数量与超立方体的维数相等，所述各输出端通过所述通信线路将信号发送到超立方体中最近相邻的处理器单元;

将所述输入端接收到的信息包连接到选定输出端的逻辑装置;

对所述输入端接收到的所有信息包建立通向选定输出端的优先级次序的装置;

划分装置，它通过对通向选定输出端的所有的信息包均不给予足够的优先级，有选择地阻止对输出端进行的访问。

4、如权利要求1所述的并行计算机，其特征在于，所述处理器单元按n维超立方体的形式互连，每个处理器单元的控制电路进一步包括：

具有来自超立方体每一维中最近相邻处理器单元的一个信号输入的第一选通装置;

用以控制所述选通装置的装置，以便能从超立方体一个或多个最近相邻的处理器单元中选择一个信号输入，作为选通装置的一个输出;

具有通向超立方体每一维中最近相邻处理器单元的一个信号输出的第二选通装置;

用以控制第二选通装置的装置，以便能从多个输入信号中选择一个作为加至超立方体最近相邻处理器单元的一个输出，在这些输入信号中，第一个是来自第一选通装置的输出，第二个是来自该控制电路所在的处理器单元中处理器的输出，这样，来自所述处理器或所选最近相邻处理器单元的信号，可以通过所述第二选通装置广播传送到与所述第二选通装置相连接的最近相邻的处理器单元中。

5、如权利要求4所述的并行计算机，其特征在于，所述第一选通装置包括用以从最近相邻的处理器单元选择任何一个或多个信号输入以及用以对所述选择的输入形成“逻辑或”的装置。

6、如权利要求4所述的并行计算机，其特征在于，加至第二选通装置的第二输入信号是来自处理器的一个同步信号，该信号通过第二选通装置广播传送到与所述第二选通装置相连接的最近相邻的处理器单元。

7、如权利要求6所述的并行计算机，其特征在于，所述同步信号通过第一选通装置的输出，由控制电路从最近相邻的处理器单元接收，通过经第二选通装置将同步指令广播传送到所述处理器单元，以及在第一选通装置的输出端监测来自所述处理器单元的适当响应，所述处理器就能够使连接到第二选通装置的各处理器单元同步地运行。

8、如权利要求5所述的并行计算机，其特征在于，加至第二选通装置的第二输入信号是来自处理器的一个指令信号，所述指令信号通过第二选通装置广播传送到与第二选通装置相连接的最近相邻的各处理器单元。

9、如权利要求8所述的平行计算机，其特征在于，所述指令信号通过第一选通装置的输出，由控制电路从一个选定的最近相邻的处理器单元接收。

10、如权利要求5所述的平行计算机，其特征在于，所述控制电路进一步包括：

具有来自超立方体每一维中最近相邻处理器单元的一个信号输入的第三选通装置;

用以控制第三选通装置的装置，以便能从超立方体一个最近相邻的处理器单元中选择一个信号输入，作为来自选通装置的一个输出;

具有一个信号输出，作为第二个输入提供给第二选通装置的第四选通装置;以及

用以控制第四选通装置的装置，以便能选择多个输入信号中的一个作为输出，其中第一个是第三选通装置的输出，第二个是来自该控制电路所在的处理器单元中处理器的输出，借此，来自所述处理器或所选最近相邻处理器单元的信号，可以通过所述第二选通装置广播传送到与所述第二选通装置连接的最近相邻的处理器单元。

11、如权利要求10所述的并行计算机，其特征在于，至第二选通装置的第二输入信号是来自处理器的一个同步信号，该同步信号通过第二选通装置，广播传送到与所述第二选通装置相连接的超立方体中最近相邻的处理器单元，而且，至第四选通装置的第二输入信号是来自处理器的一个指令信号，该信号通过第二选通装置，广播传送到与所述第二选通装置相连接的最近相邻的处理器单元。

12、如权利要求11所述的并行计算机，其特征在于，所述同步信号通过第一选通装置的输出，由控制电路从最近相邻的处理器单元接收;所述指令信号通过第三选通装置的输出，由控制电路从最近相邻的处理器单元接收。

13、如权利要求1所述的并行计算机，其特征在于所述的每个处理器单元的控制电路进一步包括：

根据从所述处理器单元的处理器接收到的地址，寻址所述处理器单元的读/写存贮器并且从所述存贮器读出信息的装置;

用以存贮从读/写存贮器读出的信息的数据高速缓冲存贮器;

连接到所述数据高速缓冲存贮器，用以将数据从一个处理器单元发送到另一个处理器单元的装置;

用以将指令从一个处理器单元发送到另一个处理器单元的装置;

用以测试所述数据高速缓冲存贮器所存贮的信息是否为并行指令的装置，如果是，就将此并行指令提供给指令发送装置，如果不是，就将信息提供给处理器单元。

14、如权利要求1所述的并行计算机，其特征在于，所述每个处理器单元的控制电路进一步包括;

第一选通装置，它具有从该选通装置所连接的多个处理器单元的每个单元来的一个信号输入;

用以控制第一选通装置的装置，以便能从一个或多个所述处理器单元中选择一个信号输入，作为该选通装置的输出;

第二选通装置，它对该选通装置所连接的多个处理器单元中的每个单元具有一个信号输出;

用以控制第二选通装置的装置，以便能从多个信号中选择一个作为加至各处理器单元的输出，在这多个信号中，有一个是来自第一选通装置的输出。

15、如权利要求14所述的并行计算机，其特征在于，所述第一选通装置包括用以从该输入端所连接的处理器单元选择任何一个或多个信号输入以及用以对所述选择的输入形成“逻辑或”的装置。

16、如权利要求14所述的平行计算机，其特征在于，加至所述第二选通装置的第二输入信号是来自处理器的一个同步信号，该信号通过第二选通装置广播传送到与所述第二选通装置相连接的处理器单元。

17、如权利要求16所述的平行计算机，其特征在于，所述同步信号来自第二选通装置的输出端所连接的处理器单元，并在第一选通装置的输入端接收，这样，通过经第二选通装置将同步指令广播传送到所述处理器单元，以及在第一选通装置的输出端监测来自所述处理器单元的适当的响应，所述处理器就能使连接到第二选通装置的处理器单元同步地运行。

18、如权利要求14所述的并行计算机，其特征在于，加至第二选通装置的第二输入信号是来自处理器的一个指令信号，所述信号通过第二选通装置广播传送到与第二选通装置相连接的处理器单元。

19、如权利要求18所述的平行计算机，其特征在于，所述指令信号通过第一选通装置的输出，由控制电路从一个选定的处理器单元中接收。

20、如权利要求14所述的并行计算机，其特征在于，所述控制电路进一步包括：

具有来自第一选通装置所连接的多个处理器单元的每个单元的一个信号输入的第三选通装置;

用以控制第三选通装置的装置，以便能从一个所述处理器单元中选择一个信号输入，作为该选通装置的一个输出;

具有一个信号输出，作为第二个输入提供给第二选通装置的第四选通装置;以及

用以控制第四选通装置的装置，以便能选择多个输入信号中的一个作为输出，其中第一个是第三选通装置的输出，第二个是来自该控制电路所在的处理器单元中的处理器的输出，这样，来自所述处理器或连接到第三选通装置输入端的所选处理器单元的信号，可以通过所述第二选通装置广播传送到与所述第二选通装置相连接的处理器单元。

21、如权利要求20所述的平行计算机，其特征在于，加至所述第二选通装置的第二输入信号是来自处理器的一个同步信号，该信号通过第二选通装置，广播传送到与所述第二选通装置相连接的处理器单元，而且，加至第四选通装置的第二输入信号是来自处理器的一个指令，该指令通过第二选通装置，广播传送到与第二选通装置相连接的处理器单元。

22、如权利要求21所述的平行计算机，其特征在于，所述同步信号来自第二选通装置的输出端所连接的处理器单元，在第一选通装置的输入端接收，所述指令信号通过第三选通装置的输出端，由控制电路从所述处理器单元接收。

23、如权利要求1所述的平行计算机，其特征在于，所述处理器单元被划分为多个处理器单元组，每组包括至少一个处理器单元，每个处理器单元产生用以传送到另一个处理器单元的信息，所述用以互连处理器单元的装置包括由所述通信线路所互连的多个节点，每个节点包括：

（1）接收电路，用以接收来自有关处理器单元组的处理器单元的信息;

（2）外发通信链路鉴别器，用以鉴别有接收信息要向外发送的通信链路;

（3）耦合器，用以耦合所述通信链路鉴别器上的每个信息。

24、如权利要求23所述的平行计算机，其特征在于，所述处理器单元按n维超立方体形式互连，所述通信线路沿超立方体的各维建立各处理器单元之间的互连，所述信息传送网络沿超立方体的各维有选择地控制对每条通信线路的访问，所述超立方体的各部分可以被划分为同构单元。

Images