图形渲染多处理器系统分析（下）-526互联

图形渲染多处理器系统分析（下）

4.5 MESI协议

为了在SMP上提供缓存一致性，数据缓存通常支持称为MESI的协议。对于MESI，数据缓存包含每个标记的两个状态位，因此每行可以处于四种状态之一：

已修改（Modified，M）：缓存中的行已被修改（与主内存不同），仅在此缓存中可用。
独占（Exclusive，E）：缓存中的行与主内存中的行相同，不存在于任何其他缓存中。
共享（Shared，S）：缓存中的行与主内存中的行相同，可能存在于另一个缓存中。
无效（Invalid，I）：缓存中的行不包含有效数据。

下表总结了四种状态的含义。

	M Modified	E Exclusive	S Shared	I Invalid
此缓存行有效吗？	是	是	是	否
内存副本是…	过期	有效	有效	-
副本是否存在于其他缓存中？	否	否	可能	可能
一个写入到此行…	不进入总线	不进入总线	进入总线且更新缓存	直接进入总线

下图显示了MESI协议的状态图，缓存的每一行都有自己的状态位，因此状态图也有自己的实现。图a显示了由于连接到此缓存的处理器启动的操作而发生的转换，图b显示了由于在公共总线上窥探的事件而发生的转换。处理器启动和总线启动动作的单独状态图有助于阐明MESI协议的逻辑。任何时候，缓存行都处于单一状态，如果下一个事件来自所连接的处理器，则转换由图a指示，如果下一事件来自总线，则转换则由图b指示。

MESI状态转换图。

读未命中（read miss）：当本地缓存中发生读未命中时，处理器启动内存读取以读取包含丢失地址的主内存行。处理器在总线上插入一个信号，提醒所有其他处理器/缓存单元窥探事务。有许多可能的结果：

如果另一个缓存具有独占状态的行的干净（自内存读取以来未修改）副本，则它将返回一个信号，指示它共享该行。然后，响应处理器将其副本的状态从独占转换为共享，启动处理器从主内存读取该行，并将其缓存中的行从无效转换为共享。
如果一个或多个缓存具有处于共享状态的行的干净副本，则每个缓存都会发出共享该行的信号。启动处理器读取该行并将其缓存中的行从无效转换为共享。
如果另一个缓存具有该行的修改副本，则该缓存将阻止内存读取，并通过共享总线将该行提供给请求缓存，然后响应缓存将其行从修改更改为共享。发送到请求缓存的行也由内存控制器接收和处理，该控制器将块存储在内存中。
如果没有其他缓存具有该行的副本（清除或修改），则不会返回任何信号。启动处理器读取该行并将其缓存中的行从无效转换为独占。

读命中（read hit）：当读命中发生在本地缓存中的当前行上时，处理器只需读取所需的项。没有状态更改：状态保持修改、共享或独占状态。

写未命中（write miss）：当本地缓存中发生写未命中时，处理器启动内存读取以读取包含丢失地址的主内存行。为此，处理器在总线上发出一个信号，表示读取意图修改（read-with-intent-to-modify，RWITM）。加载该行后，将立即标记为已修改。对于其他缓存，加载数据行之前有两种可能的情况：

首先，某些其他缓存可能具有该行的已修改副本（状态=修改）。在这种情况下，报警处理器向启动处理器发出信号，表示另一个处理器具有该行的修改副本，发起处理器放弃总线并等待。另一个处理器获得对总线的访问权，将修改后的缓存线写回主存储器，并将缓存行的状态转换为无效（因为启动的处理器将修改此线）。随后，启动处理器将再次向RWITM的总线发出信号，然后从主存储器读取该行，修改缓存中的行，并将该行标记为修改状态。
其次，没有其他缓存具有请求行的修改副本。在这种情况下，不返回任何信号，启动处理器继续读入该行并修改它。同时，如果一个或多个缓存具有处于共享状态的行的干净副本，则每个缓存都会使其行副本无效，如果一个缓存具有排他状态的行副本，则其行副本将无效。

写命中（write hit）：当本地缓存中当前行发生写命中时，效果取决于本地缓存中该行的当前状态：

共享：在执行更新之前，处理器必须获得该行的独占所有权，处理器在总线上发出信号，在其缓存中具有行的共享副本的每个处理器将扇区从共享转换为无效，然后发起处理器执行更新并将其行副本从共享转换为修改。
独占：处理器已经对该行具有独占控制权，因此它只需执行更新并将该行的副本从独占转换为已修改。
已修改：处理器已经对该行具有独占控制权，并将该行标记为已修改，因此它只需执行更新。

L1-L2缓存一致性：到目前为止，我们已经根据连接到同一总线或其他SMP互连设施的缓存之间的协作活动描述了缓存一致性协议。通常，这些缓存是L2缓存，每个处理器还具有一个L1缓存，该缓存不直接连接到总线，因此不能参与窥探协议，因此需要某种方案来维护两级缓存和SMP配置中所有缓存的数据完整性。

策略是将MESI协议（或任何缓存一致性协议）扩展到L1缓存，L1高速缓存中的每一行包括指示状态的位，目标如下：对于L2缓存及其对应的L1缓存中存在的任何行，L1行状态应跟踪L2行的状态。一种简单的方法是在L1缓存中采用直写策略；在这种情况下，写入是到L2高速缓存而不是到内存。L1直写策略强制对L2缓存的L1行进行任何修改，从而使其对其他L2缓存可见。使用L1直写策略要求L1内容必须是L2内容的子集。这反过来表明，二级缓存的关联性应等于或大于一级缓存的关联性。L1直写策略用于IBM S/390 SMP。

如果一级缓存具有回写策略，则两个缓存之间的关系更为复杂。有几种维护方法，但超出了本文的范围。

4.6 内存一致性模型

典型的内存一致性模型指定了同一线程发出的内存操作之间允许的重新排序类型。例如，在顺序一致性中，所有读/写访问都按程序顺序完成，所有其他线程也按程序顺序感知任何线程的内存访问。

让我们构建一个连贯的内存系统，并提供一定的保证。假设所有的写操作都与完成时间相关联，并在完成时立即执行，任何读取操作都不可能在完成之前获取写入的值。写操作完成后，对同一地址的所有读操作要么得到写操作写入的值，要么得到更新的写操作。由于假设一个一致性内存，所以所有处理器都会以相同的顺序看到对同一内存地址的所有写入操作。其次，每次读取操作都会返回最近完成的写入操作写入该地址的值。现在考虑处理器1向地址x发出写入请求，同时处理器2向同一地址x发出读取请求的情况。这种行为没有定义，读取可以获取并发写入操作设置的值，也可以获取先前的值。但是，如果读取操作获得了并发写入操作设置的值，那么任何处理器发出的所有后续读取都需要获得该值或更新的值。一旦完成读取内存位置的值，读取操作就完成了，生成其数据的写入也完成了。

现在，让我们设计一个多处理器，其中每个处理器在完成之前发出的所有内存请求之后发出一个内存请求，意味着在发出内存请求（读/写）之后，处理器会等待它完成，然后再发出下一个内存请求。具有这种特性的处理器的多处理器是顺序一致的。

现在概述一个简短的非正式证明，首先介绍一个称为访问图（access graph）的理论工具。

访问图

下图显示了两个线程的执行及其相关的内存访问序列。对于每个读或写访问，我们在访问图中创建一个圆或节点（见图（c））。在这种情况下，如果一个访问按程序顺序跟随另一个访问，或者如果来自不同线程的两个访问之间存在读写依赖关系，将在两个节点之间添加一个箭头（或边）。例如，如果在线程1中将x设置为5，而线程2中的读取操作读取x的这个值，那么x的读取和写入之间存在相关性，因此在访问图中添加了一个箭头，箭头表示目标请求必须在源请求之后完成。

内存访问的图形表示。

定义节点a和b之间的发生-之前（happens-before）关系，如果访问图中存在从a到b的路径。

发生-之前（happens-before）关系表示访问图中存在从a到b的路径。此关系表示b必须在a完成后完成其执行。

访问图是一种通用工具，用于对并发系统进行推理，由一组节点组成，其中每个节点都是指令的动态实例（通常是内存指令），节点之间有边节点之间有边，来自A-->B的边意味着B需要在A之后完成执行。在上图中，添加了两种边，即程序顺序边（program order edge）和因果关系边（causality edge）。程序顺序边表示同一线程中内存请求的完成顺序，当等待一条指令完成时，在执行下一条指令之前，同一线程的连续指令之间存在边。

因果边位于线程之间的加载和存储指令之间。例如，如果一条给定的指令写入一个值，而另一条指令在另一个线程中读取该值，我们将从存储到加载添加一条边。

为了证明顺序一致性，需要向访问图添加额外的边，见下面阐述。首先假设有一个圣人（一个知道一切的假设实体），由于假设一致性内存，所以对同一内存位置的所有存储都是按顺序排序的。此外，加载和存储到同一内存位置之间存在顺序。例如，如果将x设置为1，然后将x设置成3，然后读取t1=x，然后将x=5，则位置x有一个存储-存储-加载-存储的顺序。圣人知道每个内存位置的加载和存储之间的这种顺序，假设圣人将相应的发生在边之前添加到访问图中，在这种情况下，存储和加载之间的边是因果关系边，存储-存储和加载-存储边是一致性边的示例。

接下来描述如何使用访问图来证明系统的属性。首先，需要基于给定的程序运行，为给定的内存一致性模型M构建程序的访问图，基于内存访问行为添加了一致性和因果关系边。其次，基于一致性模型在同一线程中的指令之间添加程序顺序边。对于SC，在连续指令之间添加边，对于WC，在从属指令之间、常规指令之间和栅栏之间添加边。理解访问图是一个理论工具，但它通常不是一个实用工具，这点非常重要。我们将对访问图的属性进行推理，而不必为给定的程序或系统实际地构建访问图。

如果访问图不包含循环，就可以按顺序排列节点。现在来证明这一事实。在访问图中，如果存在从a到b的路径，那么让a称为b的祖先。可以通过遵循迭代过程来生成顺序，首先找到一个没有祖先的节点，必然有这样的一个节点，因为某些操作必须是第一个完成的（否则会有一个循环）。将其从访问图中删除，然后继续查找另一个没有任何祖先的节点，按照顺序添加每个这样的节点，如上图（d）所示。在每一步中，访问图中的节点数减少1，直到最后只剩下一个节点，它成为顺序中的最后一个节点。现在考虑这样一种情况，即没有在访问图中查找任何没有祖先的节点，只有在访问图中存在循环时才可能，因此正常情况下不可能。

按顺序排列节点相当于证明访问图符合其设计的内存模型。事实上，我们可以按顺序列出节点，而不违反任何happens-before关系，意味着执行等同于单处理器按顺序依次执行每个节点，正是一致性模型的定义。任何一致性模型都由内存指令之间的排序约束以及一致性假设组成，该定义还意味着，单处理器应该可以按顺序执行指令，而不违反任何happens-before关系。

这正是我们通过将访问图转换为等效的节点顺序列表所实现的。现在，程序顺序、因果关系和一致性边缘足以指定一致性模型的事实更加深刻。

因此，如果一个访问图（对于内存模型，M）不包含循环，可以得出一个给定的执行遵循M的结论。如果可以证明一个系统可以生成的所有可能的访问图都是非循环的，就可以得出整个系统遵循M的结果。

顺序一致性的证明

让我们证明，在发出后续内存请求之前等待内存请求完成的简单系统可以生成的所有可能的访问图（假设为SC）都是非循环的。考虑任意一个访问图G，我们必须证明，可以按顺序写入G中的所有内存访问，这样，如果节点b位于节点a之后，那么G中就没有从b到a的路径。换句话说，我们的顺序遵循访问图中所示的访问顺序。

假设访问图有一个循环，它包含一组属于同一线程t1的节点S，其中a是S中程序顺序中最早的节点，b是S中最晚的节点，显然a发生在b之前，因为按照程序顺序执行内存指令，在同一线程中启动下一个请求之前等待请求完成。对于由于因果边而形成的循环，b需要写入另一个内存读取请求（节点）读取的值，c属于另一个线程。或者，在b和属于另一线程的节点c之间可以存在相干边（coherence edge）。现在，为了存在一个循环，c需要发生在a之前。假设c和a之间有一个节点链，节点链中的最后一个节点是d，根据定义，d∉t1，意味着d写入一个存储位置，节点a从中读取，或者有一条从d到a的相干边。因为有一条路径从节点b到节点a（通过c和d），与节点b相关联的请求必须发生在节点a的请求之前。这是不可能的，因为在节点a请求完成之前，无法执行与节点b关联的内存请求。因此，存在一个矛盾，在访问图中循环是不可能的。因此，执行在SC中。

现在澄清圣人的概念。这里的问题不是生成顺序，而是证明顺序存在，因为正在解决后一个问题，所以总是可以假设一个假设实体向访问图添加了额外的边。产生的顺序次序（sequential order）遵循每个线程的程序顺序、因果关系和基于happens-before关系的连贯性。因此，这是一个有效的顺序。

因此，可以得出结论，在我们的系统中始终可以为线程创建顺序，因此多处理器是在SC中。既然已经证明了我们的系统是顺序一致的，那么让我们描述一种用所做的假设实现多处理器的方法，可以实现如下图所示的系统。

一个简单的顺序一致的系统。

简单顺序一致机器

上图显示了一种设计，它在多处理器的所有处理器上都有一个大的共享L1缓存，每个内存位置只有一个副本，在任何单个时间只能支持一次读或写访问，确保了一致性。其次，当一次写入更改其在一级缓存中的内存位置的值时，写入完成。同样，当读取L1缓存中的内存地址值时，读取完成。我们需要修改前面章节描述的简单有序RISC流水线，以便指令仅在完成读/写访问后才离开内存访问（MA）阶段。如果存在缓存未命中，则指令等待直到块到达一级缓存，并且访问完成。这个简单的系统确保来自同一线程的内存请求按程序顺序完成，因此顺序一致。

请注意，上图描述的系统做出了一些不切实际的假设，因此不实用。如果我们有16个处理器，并且内存指令的频率是1/3，那么每个周期都需要5-6条指令访问一级缓存。因此，一级缓存需要至少6个读/写端口，使得结构太大和太慢。此外，L1缓存需要足够大以容纳所有线程的工作集，进一步使得L1缓存非常大且速度慢。因此，具有这种高速缓存的多处理器系统在实践中将非常缓慢，而现代处理器选择了更高性能的实现，其内存系统更复杂，有很多更小的缓存。这些缓存相互协作，以提供更大缓存的错觉。

很难证明一个复杂系统遵循顺序一致性（SC），设计师选择设计具有弱内存模型的系统。在这种情况下，我们需要证明栅栏指令正确工作，如果考虑复杂设计中可能出现的所有细微角落情况，也是一个相当具有挑战性的问题。

实现弱一致性模型

考虑弱一致系统的访问图，没有边来表示同一线程中节点的程序顺序。相反，对于同一线程中的节点，在常规读/写节点和栅栏操作之间有边缘，需要将因果关系和相干边添加到访问图中，就像对SC的情况所做的那样。

弱一致机器的实现需要确保该访问图没有循环。我们可以证明，下面的实现没有向访问图引入循环，确保在给定线程的程序顺序中的所有先前指令完成后，栅栏指令开始。fence指令是一条伪指令，只需要到达管线的末端，仅用于计时目的。我们在MA阶段暂停栅栏指令，直到前面的所有指令完成，该策略还确保没有后续指令到达MA阶段。一旦所有先前的指令完成，围栏指令进入RW阶段，随后的指令可以向内存发出请求。

总结一下实现内存一致性模型的内容。通过修改处理器的流水线，并确保存储器系统一旦完成对存储器请求的处理就向处理器发送确认，可以实现诸如顺序一致性或弱一致性的内存一致性模型。在高性能实现中，许多细微的角落情况是可能的，确保它们实现给定的一致性模型相当复杂。

关于内存屏障的应用和UE的实现，可参阅1.4.5 内存屏障。

4.7 多线程处理器

现在看看设计多处理器的另一种方法。到目前为止，我们一直坚持需要有物理上分离的管线来创建多处理器，研究了为每个管线分配单独程序计数器的设计。然而，让我们看看在同一管线上运行一组线程的不同方法，这种方法被称为多线程（multithreading）。不在单独的管线上运行单独的线程，而是在同一管道上运行它们。通过讨论称为粗粒度多线程的最简单的多线程变体来说明这个概念。

多线程（multithreading）是一种设计范式，在同一管线上运行多个线程。

多线程处理器（multithreaded processor）是实现多线程的处理器。

粗粒度多线程

假设我们希望在单个管线上运行四个线程。属于同一进程的多个线程有各自的程序计数器、堆栈和寄存器，然而，它们对内存有着共同的视图，所有这四个线程都有各自独立的指令流，因此有必要提供一种错觉，即这四个进程是单独运行的。软件应该忽略线程在多线程处理器上运行的事实，它应该意识到每个线程都有其专用的CPU。除了传统的一致性和一致性保证之外，还需要提供一个额外的保证，即软件应该忽略多线程。

考虑一个简单的方案，如下图所示，线程1执行n个循环，然后切换到线程2并运行n个周期，然后切换至线程3，以此类推。在执行线程4 n个循环后，再次开始执行线程1。要执行线程，需要加载其状态或上下文。程序的上下文包括标志寄存器、程序计数器和一组寄存器，没有必要跟踪主内存，因为不同进程的内存区域不重叠，在多个线程的情况下，明确希望所有线程共享相同的内存空间。

可以采用更简单的方法，而不是显式地加载和卸载线程的上下文，可以在管线中保存线程的上下文，例如，如果望支持粗粒度多线程，就可以有四个独立的标志寄存器、四个程序计数器和四个独立寄存器（每个线程一个），还可以有一个包含当前运行线程的id的专用寄存器。例如，如果正在运行线程2，就使用线程2的上下文，如果在运行线程3，就使用线程3的上下文。以这种方式，多个线程不可能覆盖彼此的状态。

粗粒度多线程的概念图

可以采用更简单的方法，而不是显式地加载和卸载线程的上下文。我们可以在管道中保存线程的上下文。例如，如果我们希望支持粗粒度多线程，那么我们可以有四个独立的标志寄存器、四个程序计数器和四个独立寄存器文件（每个线程一个）。此外，我们可以有一个包含当前运行线程的id的专用寄存器。例如，如果我们正在运行线程2，那么我们使用线程2的上下文，如果我们在运行线程3，我们使用线程3的上下文。以这种方式，多个线程不可能覆盖彼此的状态。

现在看看一些微妙的问题。可能在管线中的同一时间点拥有属于多个线程的指令，当从一个线程切换到下一个线程时，可能会发生这种情况。让我们将线程id字段添加到指令包中，并进一步确保转发和互锁逻辑考虑到线程的id，我们从不跨线程转发值。以这种方式，可以在管线上执行四个独立的线程，而线程之间的切换开销可以忽略不计。我们不需要使用异常处理程序来保存和恢复线程的上下文，也不需要调用操作系统来调度线程的执行。

现在整体来看一下粗粒度多线程。我们快速连续执行n个线程，并按循环顺序执行，此外，有一种在线程之间快速切换的机制，线程不会破坏彼此的状态，但仍然不会同时执行四个线程。那么，这个方案的优点是什么？

考虑一下内存密集型线程的情况，这些线程对内存有很多不规则的访问，它们将经常在二级缓存中发生未命中，其管线需要暂停100-300个周期，直到值从内存中返回。无序管线可以通过执行一些不依赖于内存值的其他指令来隐藏某些延迟，尽管如此，它也将暂停很长一段时间。然而，如果我们可以切换到另一个线程，那么它可能有一些有用的工作要做。如果该线程也来自L2缓存中的未命中，那么我们可以切换到另一个线程并完成其部分工作，这样可以最大化整个系统的吞吐量。可以设想两种可能的方案：可以每n个周期周期性地切换一次，或者在发生二级缓存未命中等事件时切换到另一个线程；其次，如果线程正在等待高延迟事件（如二级缓存丢失），不需要切换到该线程，需要切换到一个具有准备好执行指令池的线程。可以设计大量的启发式算法来优化粗粒度多线程机器的性能。

软件线程和硬件线程的区别：

软件线程是一个子程序，与其他软件线程共享一部分地址空间，这些线程可以相互通信以协作实现共同目标。
硬件线程被定义为在管线上运行的软件线程或单线程程序及其执行状态的实例。

多线程处理器通过跨线程分配资源来支持同一处理器上的多个硬件线程。软件线程可以物理地映射到单独的处理器或硬件线程，与用于执行它的实体无关。需要注意的重要一点是，软件线程是一种编程语言概念，而硬件线程在物理上与管线中的资源相关联。

本文使用“线程”一词来表示软件和硬件线程，需要根据上下文推断正确的用法。

细粒度多线程

细粒度多线程是粗粒度多线程的一种特殊情况，其中切换间隔n非常小，通常为1或2个循环，意味着可以在线程之间快速切换。我们可以利用粒度多线程来执行内存密集型线程，然而，否定多线程对于执行一组线程（例如具有长算术运算，如除法）也很有用。在典型的处理器中，除法运算和其他特殊运算（如三角运算或超越运算）很慢（3-10个周期）。在这段时间内，当原始线程等待操作完成时，可以切换到另一个线程，并在管线阶段中执行它的一些未使用的指令。因此，我们可以利用在线程之间快速切换的能力来减少具有大量数学运算的科学程序中的空闲时间。

因此，我们可以将细粒度多线程视为更灵活的粗粒度多线程形式，在线程之间快速切换，并利用空闲阶段执行有用的工作。请注意，这个概念并不像听起来那么简单。需要在常规有序或无序管线中的所有结构中为多线程提供详细的支持，需要非常仔细地管理每个线程的上下文，并确保不会遗漏指令，也不会引入错误。

线程之间切换的逻辑不是普通的。大多数时候，在线程之间切换的逻辑是基于时间的标准（周期数）和基于事件的标准（高延迟事件，如二级缓存未命中或页面错误）的组合。为了确保多线程处理器在一系列基准测试中表现良好，必须仔细调整启发式。

并发多线程

对于单个执行管线，如果可以通过使用复杂的逻辑在线程之间切换来确保每个阶段都保持忙碌，就可以实现高效率。单个执行管线中的任何阶段每个周期只能处理一条指令。相比之下，多执行流水线每个周期可以处理多个指令，此外，将执行槽的数量设计为等于流水线每个周期可以处理的指令数量。例如，一个3执行处理器，每个周期最多可以获取、解码并最终执行3条指令。

为了在多执行管线中实现多线程，还需要考虑线程中指令之间的依赖性。细粒度和粗粒度方案可能无法很好地执行，因为线程无法为所有执行槽向功能单元执行指令，这种线程可描述成具有低指令级并行性。如果我们使用4个执行流水线，并且由于程序中的依赖性，每个线程的最大IPC为1，那么每个周期中有3个执行槽将保持空闲。因此，4线程系统的总体IPC将为1，多线程的好处将受到限制。

因此，有必要利用额外的执行时段，以便我们能够增加整个系统的IPC。一种简单的方法是为每个线程分配一个执行槽。其次，为了避免结构冲突，可以有四个ALU，并为每个线程分配一个ALU。然而，这是对管线的次优利用，因为线程可能没有执行每个周期的指令。最好有一个更灵活的方案，可以在线程之间动态地划分执行槽，这种方案被称为并发多线程（simultaneous multithreading，SMT）。例如，在给定的周期中，我们可能会从线程2执行2条指令，从线程3和4执行1条指令，这种情况可能在下一个周期中发生逆转。下图说明这个概念，同时还将SMT方法与细粒度和粗粒度多线程进行比较。

多线程处理器中的指令执行。

上图中的列表示多执行机器的执行槽，行表示周期，属于不同线程的指令有不同的颜色。图（a）显示了粗粒度机器中指令的执行情况，其中每个线程执行两个连续的周期。由于没有找到足够数量的可执行指令，所以很多执行槽都是空的，细粒度多线程（图（b））也有同样的问题。然而，在SMT处理器中，通常能够使大多数执行槽保持忙碌，因为总是从准备执行的可用线程集中找到指令。如果一个线程由于某种原因被暂停，其他线程会通过执行更多的指令进行补偿。实际上，所有线程不同时具有低ILP（Instruction Level Parallelism，指令级并行）阶段，因此，SMT方法已被证明是一种非常通用且有效的方法，可以利用多个执行处理器的能力。自从奔腾4（90年代末发布）以来，大多数英特尔处理器都支持不同版本的同时多线程，在英特尔的术语中，SMT被称为超线程，而IBM Power 7处理器有8个内核，每个内核都是4路SMT（每个内核可以运行4个线程）。

请注意，选择要执行的正确指令集的问题对SMT处理器的性能至关重要。其次，n路SMT处理器的内存带宽要求高于等效单处理器，提取逻辑也要复杂得多，因为需要在同一周期内从四个独立的程序计数器中提取。最后，保持连贯性和一致性的问题使情况更加复杂。

执行多个线程的更多方法如下：

它们的说明如下：

超标量（Superscalar）：是没有多线程的基本超标量方法，直到前些年，依旧是在处理器内提供并行性的最强大的方法。注意，在某些周期中，并非使用所有可用的执行槽（issue slot），在这些周期中，发出的指令数少于最大指令数，被称为水平损耗（horizontal loss）。在其他指令周期中，不使用执行槽，是无法发出指令的周期，被称为垂直损耗（vertical loss）。
交错多线程超标量（Interleaved multithreading superscalar）：在每个周期中，从一个线程发出尽可能多的指令。如前所述，通过这种技术，消除了由于线程切换导致的潜在延迟，但在任何给定周期中发出的指令数量仍然受到任何给定线程中存在的依赖性的限制。
阻塞的多线程超标量（Blocked multithreaded superscalar）：同样，在任何周期中，只能发出来自一个线程的指令，并且使用阻塞多线程。
超长指令字（Very long instruction word，VLIW）：VLIW架构（如IA-64）将多条指令放在一个字中，通常由编译器构建，它将可以并行执行的操作放在同一个字中。在一个简单的VLIW机器（上图g）中，如果不可能用并行发出的指令完全填充单词，则不使用操作。
交错多线程VLIW（Interleaved multithreading VLIW）：提供与超标量架构上交错多线程所提供的效率类似的效率。
阻塞多线程VLIW（Blocked multithreaded VLIW）：提供与超标量架构上的阻塞多线程所提供的效率类似的效率。
同时多线程（Simultaneous multithreading）：上图j显示了一个能够一次发出8条指令的系统。如果一个线程具有高度的指令级并行性，则它可能在某些周期内能够填满所有的水平槽。在其他周期中，可以发出来自两个或多个线程的指令。如果有足够的线程处于活动状态，则通常可以在每个周期中发出最大数量的指令，从而提供较高的效率。
芯片多处理器（Chip multiprocessor），亦即多核（multicore）：上图k显示了一个包含四个核的芯片，每个核都有一个两个问题的超标量处理器。每个内核都分配了一个线程，每个周期最多可以发出两条指令。

5 SIMD多处理器

本节讨论SIMD多处理器。SIMD处理器通常用于科学应用、高强度游戏和图形，它们没有大量的通用用途。然而，对于一类有限的应用，SIMD处理器往往优于MIMD处理器。

SIMD处理器有着丰富的历史。在过去的好日子里，我们把处理器排列成阵列，数据通常通过处理器的第一行和第一列输入，每个处理器对输入消息进行操作，生成一条输出消息，并将该消息发送给其邻居。这种处理器被称为收缩阵列（systolic array）。收缩阵列用于矩阵乘法和其他线性代数运算。随后的几家供应商，尤其是Cray，在他们的处理器中加入了SIMD指令，以设计更快、更节能的超级计算机。如今，这些早期的努力大多已经隐退，然而，经典SIMD计算机的某些方面，即单个指令对多个数据流进行操作，已经渗透到现代处理器的设计中。

我们将讨论现代处理器设计领域的一个重要发展，即在高性能处理器中加入SIMD功能单元和指令。

5.1 SIMD：矢量处理器

让我们考虑添加两个n元素数组的问题。在单线程实现中，需要从内存加载操作数，添加操作数，并将结果存储在内存中。因此，为了计算目标数组的每个元素，需要两条加载指令、一条加法指令和一条存储指令。传统处理器试图通过利用可以并行计算（c[i]=a[i]+b[i]）和（c[j]=a[j]+b[j]）的事实来实现加速，因为这两个运算之间没有任何依赖关系，可以通过并行执行许多这样的操作来增加IPC。

现在让我们考虑超标量处理器。如果它们每个周期可以执行4条指令，那么它们的IPC最多可以是单周期处理器的4倍。在实践中，对于4执行的处理器，我们可以通过这种固有的并行阵列处理操作在单周期处理器上实现的峰值加速大约是3到3.5倍。其次，这种通过宽执行宽度来增加IPC的方法是不可扩展的。在实践中没有8或10个执行处理器，因为流水线的逻辑变得非常复杂，并且面积/功率开销变得令人望而却步。

因此，设计人员决定对对大型数据向量（数组）进行操作的向量操作提供特殊支持，这种处理器被称为矢量处理器，主要思想是一次处理整个数据数组。普通处理器使用常规标量数据类型，如整数和浮点数；而向量处理器使用向量数据类型，本质上是标量数据类型的数组。

向量处理器（vector processor）将原始数据类型（整数或浮点数）的向量视为其基本信息单位。它可以一次加载、存储和执行整个向量的算术运算，这种对数据向量进行操作的指令称为向量指令（vector instruction）。

使用多个功能单元来提高单个向量加法C=A+B指令的性能。

包含四通道的矢量单元的结构。

主要使用矢量处理器的最具标志性的产品之一是Cray 1超级计算机，这种超级计算机主要用于主要由线性代数运算组成的科学应用，这样的操作适用于数据和矩阵的向量，因此非常适合在向量处理器上运行。可悲的是，在高强度科学计算领域之外，向量处理器直到90年代末才进入通用市场。

90年代末，个人计算机开始用于研究和运行科学应用。其次，设计师们开始使用普通商品处理器来建造超级计算机，而不是为超级计算机设计定制处理器。从那时起，这一趋势一直持续到图形处理器的发展。1995年至2010年间，大多数超级计算机由数千个商品处理器组成。在常规处理器中使用矢量指令的另一个重要原因是支持高强度游戏，游戏需要大量的图形处理，例如，现代游戏渲染具有多个角色和数千个视觉效果的复杂场景。大多数视觉效果，如照明、阴影、动画、深度和颜色处理，都是对包含点或像素的矩阵进行基本线性代数运算的核心。由于这些因素，常规处理器开始引入有限的矢量支持，特别是，英特尔处理器提供了MMX、SSE 1-4矢量指令集，AMD处理器提供了3DNow！矢量扩展，ARM处理器提供ARM Neon矢量ISA。这些ISA之间有很多共性，因此我们不用关注任何特定的ISA。让我们转而讨论矢量处理器设计和操作背后的广泛原则。

5.2 软件接口

让我们先考虑一下机器的型号，需要一组向量寄存器，例如，x86 SSE（数据流单指令多数据扩展指令集）指令集定义了16个128位寄存器（XMM0...XMM15），每个这样的寄存器可以包含四个整数或四个浮点值，或者也可以包含八个2字节短整数或十六个1字节字符。在同一行上，每个矢量ISA都需要比普通寄存器宽的附加矢量寄存器。通常，每个寄存器可以包含多个浮点值。此处不妨让我们定义八个128位矢量寄存器：vr0...vr7。

现在，我们需要指令来加载、存储和操作向量寄存器。对于加载向量寄存器，有两个选项，可以从连续内存位置加载值，也可以从非连续内存位置装载值。前一种情况更为特殊，通常适用于基于阵列的应用程序，其中所有阵列元素都存储在连续的内存位置。ISA的大多数矢量扩展都支持加载指令的这种变体，因为它的简单性和规则性。此处不妨将ISA设计这样一个向量加载指令v:ld，考虑下图中所示的语义。此处，v:ld指令将内存位置（[r1+12]、[r1/16]、[r2+20]、[r 1+24]）的内容读入向量寄存器vr1。在下表中，请注意是向量寄存器。

示例	语法	解释
v.ld vr1, 12[r1]	v.ld ,	vr1 <-- ([r1+12], [r1+16], [r1+20], [r1+ 24])

现在考虑矩阵的情况。假设有一个10000元素矩阵a[100][100]，并假设数据是按行主顺序存储的，且要对矩阵的两列进行运算。在这种情况下，我们遇到了一个问题，因为列中的元素没有保存在相邻的位置。因此，依赖于输入操作数保存在连续内存位置的假设的向量加载指令将停止工作，需要有专门的支持来获取列中位置的所有数据，并将它们保存在向量寄存器中。这种操作称为分散-聚集（catter-gather）操作，因为输入操作数基本上分散在主内存中。

我们需要收集，并将它们放在一个叫向量寄存器的地方。让我们考虑向量加载指令的分散-聚集变体，并将其称为v.sg.ld。处理器读取另一个包含元素地址的向量寄存器，而不是假设数组元素的位置（语义见下表）。在这种情况下，专用向量加载单元读取存储在vr2中的内存地址，从内存中提取相应的值，并将它们顺序写入向量寄存器vr1。

示例	语法	解释
v.sg.ld vr1, 12[r1]	v.sg.ld ,	vr1 <-- ([vr2[0]], [vr2[1]], [vr2[2]], [vr2[3]])

一旦在向量寄存器中加载了数据，就可以直接对两个这样的寄存器进行操作。例如，考虑128位矢量寄存器vr1和vr2，那么，汇编语句v.add vr3, vr1, vr2，将存储在输入向量寄存器（vr1和vr2）中的每对对应的4字节浮点数相加，并将结果存储在输出向量寄存器（vr3）中的相关位置。注意，这里使用向量加法指令（v.add)。下图显示了矢量加法指令的示例。

矢量ISA为矢量乘法、除法和逻辑运算定义了类似的操作。向量指令不必总是有两个输入操作数，即向量，可以将一个向量与一个标量相乘，也可以有一条只对一个向量操作数进行运算的指令。例如，SSE指令集有专门的指令，用于计算向量寄存器中的一组浮点数的三角函数，如sin和cos。如果一条向量指令可以同时对n个操作数执行操作，就说有n个数据通道，而向量指令同时对所有n个数据路径执行操作。

如果一条向量指令可以同时对n个操作数执行操作，那么就表示有n个数据通道（lane），而向量指令同时对所有n个数据路径执行操作。

最后一步是将向量寄存器存储在内存中，有两种选择：可以存储到相邻的内存位置，也可以保存到非相邻的位置。可以在向量加载指令的两个变体（v.ld和v.sg.ld）的行上设计向量存储指令的两种变体（连续和非连续）。有时需要引入在标量寄存器和矢量寄存器之间传输数据的指令。

5.3 SSE指令示例

现在考虑一个使用基于x86的SSE指令集的实际示例，不使用实际的汇编指令，改为使用gcc编译器提供的函数，这些函数充当汇编指令的封装器，称为gcc内建函数。

现在让我们解决添加两个浮点数数组的问题，希望对i的所有值计算c[i]=a[i]+b[i]。

SSE指令集包含128位寄存器，每个寄存器可用于存储四个32位浮点数。因此，如果有一个N个数字的数组，需要进行N/4次迭代，因为在每个循环中最多可以添加4对数字。在每次迭代中，需要加载向量寄存器，累加它们，并将结果存储在内存中。这种基于向量寄存器大小将向量计算分解为循环迭代序列的过程称为条带开采（strip mining）。

用C/C++编写一个函数，将数组a和b中的元素成对相加，并使用x86 ISA的SSE扩展将结果保存到数组C中。假设a和b中的条目数相同，是4的倍数。一种实现的代码如下：

void sseAdd (const float a[], const float b[], float c[], int N)

{

/* strip mining */

int numIters = N / 4;

/* iteration */

for (int i = 0; i < numIters; i++)

{

/* load the values */

__m128 val1 = _mm_load_ps(a);

__m128 val2 = _mm_load_ps(b);

/* perform the vector addition */

__m128 res = _mm_add_ps(val1, val2);

/* store the result */

_mm_store_ps(c, res);

/* increment the pointers */

a += 4 ; b += 4; c+= 4;

}

上述的代码解析：先计算迭代次数，在每次迭代中，考虑一个由4个数组元素组成的块，将一组四个浮点数加载到128位向量变量中，val1.val1由编译器映射到向量寄存器，使用函数_mm_load_ps从内存中加载一组4个连续的浮点值。例如，函数_mm_load_ps(a)将位置a、a+4、a+8和a+12中的四个浮点值加载到向量寄存器中。类似地，加载第二个向量寄存器val2，从存储器地址b开始的四个浮点值。随后执行向量加法，并将结果保存在与变量res关联的128位向量寄存器中。为此，使用内建函数_mm_add_ps，随后将变量res存储在内存位置，即c、c+4、c+8和c+12。

在继续下一次迭代之前，需要更新指针a、b和c。因为每个周期处理4个连续的数组元素，所以用4个（4个数组元素）更新每个指针。

可以很快得出结论，向量指令有助于批量计算，例如批量加载/存储，以及一次性成对添加一组数字。将此函数的性能与四核Intel core i7机器上不使用向量指令的函数版本进行了比较，带有SSE指令的代码对百万元素数组的运行速度快2-3倍。如果有更广泛的SSE寄存器，那么可以获得更多的加速，x86处理器上最新的AVX矢量ISA支持256和512位矢量寄存器。

5.4 判断指令

到目前为止，我们已经考虑了向量加载、存储和ALU操作。分支呢？通常，分支在向量处理器的上下文中具有不同的含义。例如，一个具有向量寄存器的处理器，其宽度足以容纳32个整数，有一个程序要求仅对18个整数进行成对相加，然后将它们存储在内存中。在这种情况下，无法将整个向量寄存器存储到内存中，因为有覆盖有效数据的风险。

让我们考虑另一个例子。假设想对数组的所有元素应用函数inc10(x)，在这种情况下，如果输入操作数x小于10，希望将其加10。在向量处理器上运行的程序中，这种模式非常常见，因此需要向量ISA中的额外支持来支持它们。

function inc10(x):

if (x < 10)

x = x + 10;

让我们添加一个规则指令的新变体，并将其称为判断指令（predicated instruction，类似于ARM中的条件指令）。例如，我们可以创建常规加载、存储和ALU指令的判断变体。判断指令在特定条件为真时执行，否则根本不执行，如果条件为false，则判断指令等同于nop。

判断指令（predicated instruction）是正常加载、存储或ALU指令的变体。如果某个条件为真，它将正常执行；如果关联条件为false，那么它将转换为nop。

例如，如果最后一次比较结果相等，则ARM ISA中的addeq指令会像正常的加法指令一样执行。但是，如果不是这样，则add指令根本不执行。

现在让添加对判断的支持。首先创建cmp指令的向量形式，并将其称为v.cmp。它对两个矢量进行成对比较，并将比较结果保存在v.flags寄存器中，该寄存器是标志寄存器的矢量形式。v.flags寄存器的每个组件都包含一个E和GT字段，类似于常规处理器中的标志寄存器。

v.cmp vr1, vr2

上述语句比较vr1和vr2，并将结果保存在v.flags寄存器中。我们可以使用此指令的另一种形式，将向量与标量进行比较。

v.cmp vr1, 10

现在，让我们定义向量加法指令的谓词形式。如果v.flags[i]寄存器满足某些属性，则此指令将两个向量的第i元素相加，并更新目标向量寄存器的第i个元素。否则，它不会更新目标寄存器的第i个元素。假设判断向量add指令的一般形式为：v.p.add，p是判断条件。下表列出了p可以取的不同值。

判断条件	解析
lt	<
gt	>
le	<=
ge	>=
eq	=
ne	!=

现在考虑下面的代码片段：

v.lt.add vr3, vr1, vr2

此处，向量寄存器vr3的值是由vr1和vr2表示的向量之和，预测条件小于（lt），意味着，如果在v.flags寄存器中元素i的E和GT标志都为假，那么只有我们对第i个元素执行加法，并在vr3寄存器中设置其值，vr3寄存器中未被加法指令设置的元素保持其先前的值。因此，实现函数inc10(x)的代码如下，假设vr1包含输入数组的值。

v.cmp vr1, 10

v.lt.add vr1, vr1, 10

同样，我们可以定义加载/存储指令和其他ALU指令的判断版本。

6 互连网路

6.1 互联网络概述

现在考虑互连不同处理和存储元件的问题。通常，多核处理器使用棋盘设计，但此处我们将处理器集划分为块（tile，亦称瓦片），块通常由一组2-4个处理器组成，具有其专用缓存（L1和可能的L2），它还包含共享的最后一级缓存（L2或L3）的一部分。共享的最后一级缓存的一部分是给定分片的一部分，称为分片（slice），分片由2-4个存储库（bank）组成。此外，在现代处理器中，一个块或一组块可能共享一个内存控制器，内存控制器的作用是协调片上高速缓存和主内存之间的数据传输。下图显示了32核多处理器的代表性布局，与缓存组相比，内核的颜色更深。我们使用2个块大小（2个处理器和2个缓存组），并假设共享L2缓存具有32个均匀分布在块上的缓存组。此外，每个块都有一个专用的内存控制器和一个称为路由器（router）的结构。

多核处理器的布局。

紧密耦合多处理器的通用架构图。

集群配置。

路由器是一个专用单元，定义如下。

1、路由器通过片上网络将源自其瓦片中的处理器或缓存的消息发送到其他瓦片。

2、路由器通过片上网络相互连接。

3、消息通过一系列路由器从源路由器传送到（远程瓦片的）目的路由器。途中的每一个路由器都会将消息转发到另一个离目的地更近的路由器。

4、最后，与目的地砖相关联的路由器将消息转发到远程砖中的处理器或高速缓存。

5、相邻路由器通过链路连接，链路是一组用于传输消息的无源铜线。

6、路由器通常有许多传入链路和许多传出链路。一组传入和传出链接将其连接到处理器，并在其瓦片中缓存。每个链接都有一个唯一的标识符。

7、路由器具有相当复杂的结构，通常由3至5级管线组成。大多数设计通常将管线阶段用于缓冲消息、计算传出链路的id、仲裁链路以及通过传出链路发送消息。

8、路由器和链路的布置被称为片上网络或片上网络，缩写为NOC。

9、将连接到NOC的每个路由器称为节点，节点通过发送消息相互通信。

在程序执行过程中，它通过NOC发送数十亿条消息，NOC携带一致性消息、LLC（最后一级缓存）请求/响应消息以及缓存和内存控制器之间的消息。操作系统还使用NOC向内核发送消息以加载和卸载线程，由于信息量大，大部分NOC经常遇到相当大的拥堵。因此，设计尽可能减少拥堵、易于设计和制造并确保信息快速到达目的地的NOC至关重要。让我们定义NOC的两个重要特性：等分带宽（bisection bandwidth）和直径（diameter）。

对称多处理器组织如下：

6.2 等分带宽和网络直径

让我们考虑一个网络拓扑，其中顶点是节点，顶点之间的边是链接。假设存在链路故障，或者由于拥塞等其他原因，链路不可用，那么应该可以通过备用路径路由消息。例如，考虑一个布置为环的网络，如果一个链路失败，那么总是可以通过环的另一端发送消息。如果以顺时针方式发送消息，可以以逆时针方式发送。然而，如果存在两个链路故障，则网络可能会断开成两个相等的部分。因此，我们希望最大限度地减少将网络完全断开成相当大的部分（可能相等）所需的链路故障数量。将此类故障的数量称为等分带宽（bisection bandwidth），等分带宽是衡量网络可靠性的指标，它精确地定义为需要将网络划分为两个相等部分的最小链路数。

可以对等分带宽进行另一种解释。假设一半网络中的节点正在尝试向另一半网络中节点发送消息，那么可以同时发送的消息数量至少等于等分带宽。因此，等分带宽也是网络带宽的度量。

等分带宽（bisection bandwidth）被定义为将网络分成两个相等部分所需的最小链路故障数。

我们已经讨论了可靠性和带宽，现在转向关注延迟。考虑网络中的节点对，接下来考虑每对节点之间的最短路径，在所有这些最短路径中，考虑具有最大长度的路径，该路径的长度是网络中节点接近度的上限，称为网络直径（Network Diameter）。或者，可以将网络的直径解释为任何一对节点之间最坏情况下延迟的估计。

让我们考虑所有节点对，并计算每对节点之间的最短路径，最长路径的长度称为网络直径（Network Diameter），它是网络最坏情况下延迟的度量。

6.3 网络拓扑

本节回顾一些最常见的网络拓扑，其中一些拓扑用于多核处理器。然而，大多数复杂的拓扑结构用于使用常规以太网链路连接处理器的松散耦合多处理器。对于每个拓扑，假设它有N个节点，为了计算等分带宽，可以进一步简化N可被2整除的假设。请注意，等分带宽和直径等度量都是近似度量，仅表示广泛的趋势。因此，我们有余地做出简单的假设，从考虑适用于多核的更简单拓扑开始，要以高的等分带宽和低的网络直径为目标。

链和环

下图左显示了一个节点链，它的等分带宽为1，网络直径为N-1，是最糟糕的配置。可以通过考虑一个节点环来改进这两个指标（下图右），此时等分带宽为2，网络直径为N=2。这两种拓扑都相当简单，已被其他拓扑所取代。现在考虑一种称为胖树的拓扑结构，它通常在集群计算机中使用，集群计算机是指由通过局域网连接的多个处理器组成的松散耦合的多处理器。

集群计算机（cluster computer）是指由通过局域网连接的多个处理器组成的松散耦合计算机。

左：链；右：环。

胖树

下图显示了一棵胖树（fat tree），所有节点都在叶子上，树的所有内部节点都是专用于路由消息的路由器，将这些内部节点称为交换机。从节点A到节点b的消息首先传播到最近的节点，该节点是A和b的共同祖先，然后它向下传播到b。请注意，消息的密度在根附近最高，为了避免争用和瓶颈，当向根节点移动时，逐渐增加连接节点及其子节点的链接数。该策略减少了根节点处的消息拥塞。

在示例中，两个子树连接到根节点，每个子树有4个节点，根最多可以从每个子树接收4条消息。其次，它最多需要向每个子树发送4条消息。假设一个双工链接，根需要有4个链接将其连接到其每个子级。同样，下一级节点需要它们与其每个子节点之间的2个链接，每个叶子需要一个链接。因此，当向根部前进时，可以看到这棵树越来越胖，因此它被称为胖树。

网络直径等于2log(N)，等分带宽等于将根节点连接到其每个子节点的最小链路数。假设树的设计是为了确保根上的链接绝对没有争用，那么需要用N=2个链接将根连接到每个子树，这种情况下的等分带宽为N=2。请注意，在大多数实际情况下，不会在根及其子级之间分配N=2个链路，因为子树中所有节点同时发送消息的概率很低，因此在实践中可以减少每个级别的链接数。

网格和圆环

左：网格；右：圆环。

现在看看更适合多核的拓扑，最常见的拓扑之一是网格（mesh），其中所有节点都以类似矩阵的方式连接（上图左）。拐角处的节点有两个邻居，边缘上的节点有三个邻居，其余节点有四个邻居。现在计算网格的直径和等分带宽，最长的路径在两个角节点之间，直径等于。要将网络分成两个相等的部分，需要在中间（水平或垂直）分割网格，因为在一行或一列中有个节点，所以等分带宽等于。就这些参数而言，网格优于链和环。

不幸的是，网格拓扑本质上是不对称的，位于网格边缘的节点彼此远离，可以通过每行和每列的末端之间的交叉链接来增加网格，所得结构称为圆环（torus），如上图右所示。现在看看圆环的性质，网络边缘两侧的节点只相隔一跳，最长的路径位于任何角节点和圆环中心的节点之间，直径再次等于（忽略小的相加常数）。回想一下，圆环每边的长度等于。

现在，将网络分成两个相等的部分，将其水平拆分。因此，需要捕捉个垂直链接，以及条交叉链接（每列末端之间的链接）。因此，等分带宽等于2 。

通过添加2 个交叉链接（行为，列为），将直径减半，并将圆环的等分带宽加倍。然而，这个方案仍然存在一些问题，后面详细说明。

在确定直径时，我们做了一个隐含的假设，即每个链路的长度几乎相同，或者消息穿过链路所需的时间对于网络中的所有链路几乎相同，由此根据消息经过的链接数来定义直径。这种假设并不十分不切实际，因为与沿途路由器的延迟相比，通常通过链路的传播时间很短。然而，链路的延迟是有限制的，如果链接很长，对直径的定义需要修改，就圆环来说，有这样的情况。交叉链路在物理上比相邻节点之间的常规链路长倍。因此，与网格相比，我实践中没有显著减小直径，因为一行末端的节点仍然相距很远。

幸运的是，可以通过使用一种稍加修改的称为折叠圆环（Folded Torus）的结构来解决这个问题，如下图所示。每一行和每一列的拓扑结构都像一个环，环的一半由原本是网格拓扑的一部分的规则链接组成，另一半由添加的交叉链接组成，这些交叉链接用于将网格转换为圆环，交替地将节点放置在常规链接和交叉链接上。该策略确保折叠环面中相邻节点之间的距离是规则环面中的相邻节点之间距离的两倍，但避免了行或列两端之间的长交叉链接（跳长）。

网络的等分带宽和直径与圆环保持相同。在这种情况下，有几个路径可以作为最长路径，但从拐角到中心的路径不是最长的，最长的路径之一是在两个相对的角落之间。折叠圆环通常是多核处理器中的首选配置，因为它避免了长的交叉链路。

超立方体

现在考虑一个具有O(log(N))直径的网络，这些网络使用大量链接，因此它们不适用于多核，通常用于大型集群计算机。这个网络被称为超立方体（hypercube）。超立方体实际上是一个网络族，每个网络都有一个阶（order），k阶的超立方体称为Hk。它有着下图所示的几种拓扑结构。

蝴蝶

最后一个叫做蝴蝶的网络，它也有O(log(N))的直径，但它适合于多核。下图显示了8个节点的蝶形网络，每个节点由一个圆表示。除了节点之外，还有一组交换机或内部节点（以矩形显示），用于在节点之间路由消息。消息从左侧开始，经过交换机，到达图表的右侧。请注意，图最左侧和最右侧的节点实际上是相同的节点集。没有添加从左到右的交叉链接，以避免使图表复杂化，图中显示了两个节点的集合。