『译』计算机体系结构发展史（六）

系列文章第六篇（对应M.7）

往期文章

『译』计算机体系结构发展史（一）

『译』计算机体系结构发展史（二）

『译』计算机体系结构发展史（三）

『译』计算机体系结构发展史（四）

『译』计算机体系结构发展史（五）

M.7The of and ( 5 and F, G, and I)

多处理器（）技术历史悠久，本节中，我们按不同的时间段和体系结构分别进行讨论。我们首先从SIMD方法和 IV开始；然后，对其它一些早期实验性的多处理器系统进行简短的讨论；进而介绍并行处理中一些重大的争论；之后，我们将讨论当前的多处理器技术的历史根源；最后，我们将以最新进展作为总结。

SIMD : Idea, Many , No

The cost of a is, , very high and were which would the cost the power or of the . The of one of the three major . … the [ unit] gives rise to the basic of [an] … array such as the IV.

et al. [1972]

SIMD模型是最早的并行计算模型之一，其历史可以追溯到第一个大型多处理器系统 IV。这些计算机没有像矢量体系结构那样流水地进行数据计算，而是通过功能单元的阵列进行并行计算。因此，它们也可能被视为阵列处理器。

SIMD风格计算机的思想最早来自Unger [1958]和，Borck and [1962]。的设计了 IV（也许是最“臭名昭著”的超级计算机项目）的基础。尽管成功地推出了在后来的项目中证明有用的多种技术，但它作为计算机还是失败了。即使只建造了计划中的多处理器系统的四分之一，但成本从1966年的800万美元增加到1972年的3,100万美元。（以2011年的美元价值计算，即从5400万美元增加到1.52亿美元。）整个系统的实际性能最多为15 ，而最初的预测是1000 [Hord 1982]。该计算机于1972年交付给NASA Ames ，但还需要经过三年的工程才能投入使用。这些事件减慢了对SIMD的研究，但是Danny [1985]在所谓的 中恢复了这种架构，它具有65,536个1位处理器。

实际的SIMD计算机需要混合使用SISD和SIMD指令。一个SISD主机可以执行不需要并行的操作，例如分支和地址计算。SIMD指令被广播到所有执行单元，每个执行单元（ units）都有自己的一组寄存器。为了提高灵活性，在SIMD指令执行期间，某个执行单元可以被禁用。此外，大规模并行SIMD多处理器系统依赖于互连或通信网络在处理元件（ ）之间交换数据。

SIMD最适合处理for循环中的数组。因此，要想充分利用SIMD架构实现大规模并行处理，就必须有大量数据，或者数据本身有很好的并行性（data ）。SIMD架构对于case语句的处理则效率很低，因为每个执行单元必须根据其数据执行不同的操作。这种情况下，需要将拿到“错误”数据的执行单元禁用，以便让需要的执行单元得以继续运行。因此，系统基本上是以1/n的性能在运行，其中n是case语句的分支数量。

SIMD多处理器设计的最基本的权衡是性能与处理器数量之间的关系。80年代的SIMD超级计算机都强调了高度的并行性而非在单个处理器的性能。例如，- 2提供了65,536个单比特处理器，而 IV则计划使用64个64比特处理器。

在80年代，首先是 ，继而由复活之后，SIMD价格在超级计算机领域逐渐消失，要原因有两个：首先，它太僵化了。许多重要问题本身并不是数据并行的，并且体系结构无法有效的缩减规模。也就是说，与替代产品相比，小规模的SIMD多处理器系统的性价比通常较低。其次，SIMD无法利用80年代SISD（单指令，单数据）微处理器技术的巨大性能和成本优势，该技术每18个月的性能就翻一番。SIMD多处理器系统的设计者并没有利用这种低成本技术，而必须为其多处理器构系统研制定制的处理器。

尽管SIMD计算机并不适合通用场景，但这种架构风格将继续在特殊用途的场景中发挥作用。许多特殊用途的任务是处理高度并行的数据，并且只需要一组功能有限的处理单元。因此，设计人员可以设计对特殊操作的硬件，以及硬连线方式的互联通路来连接这些功能单元。这样的架构通常被称为阵列处理器（array ），它们对于诸如图像和信号处理之类的任务很有效。

Other Early

要确定第一个MIMD多处理器是非常困难的。例如，我们很难想到，- 的第一台计算机具有重复的功能单元以提高可用性。（1959）提出了针对多个处理器的早期论证。在记录保留的最充分的多处理器项目中，有两个是70年代在卡内基梅隆大学进行的。其中第一个是C.mmp [Wulf and Bell 1972; Wulf and 1978]，由16个PDP-11组成，这些PDP-11通过交叉连接访问16个存储单元。它是最早的具有多个处理器的多处理器系统之一，并且具有共享内存编程模型。C.mmp项目中的许多研究重点都放在软件上，尤其是在操作系统领域。后来的多处理器系统Cm* [Swan et al. 1977]是一个基于集群的多处理器系统，具有分布式内存，其访问时间是不一致的（）。由于缺少高速缓存，加之远程访问的延迟很大，在这个系统中数据放置的位置是至关重要的。， and [1987]对这种多处理器系统和许多应用实验进行了很好的讨论。到了80年代，微处理器的出现使制造多处理器系统的成本大大降低，这些早期多处理器系统中探索的许多想法重新得到应用。

Great in

The away from the came in the 1960s, when the law of began to take in the to the speed of a . … are in their speed of by the speed of light … and many of the were in the range.

et al. [1972]

… are a limit on their power. Such a limit is the speed of light …

Angel L.

The of , Vol. I (1989)

… today’s … are an as the speed of light. Even if the of a could be made to work this fast, the best that could be is no more than a few per .

David

The : The Time Is Now (1989)

上面的几段引文，都是关于并行处理的经典讨论，而 [1967]对于这个问题也给出了他经典的回答（其结论支持了IBM 360体系结构持续改进）。关于并行处理的争论可以追溯到19世纪[ 1842]！但是，通过多处理器架构来减少单个重要程序的处理延迟，仍然是在探索中的问题。除了这些关于并行处理的优点和局限性的争论之外，一些热烈的争论集中在如何构建多处理器系统上。预测未来非常困难，但在1989年，戈登·贝尔（ Bell）对1995年做出了两项预测。我们将这些预测包括在本书的第一版中，当时结果还不明朗。我们将在本节中讨论这些预测，同时评估预测的准确性。

首先是，到1995年，能够维持处理能力的计算机将会出现，其构建形式可能是具有4K到32K节点的多计算机（）系统，或者是具有数百万个处理元素的 [Bell 1989]。为了验证这一预测，每年 Bell Prize会表彰并行处理方面的进步，包括运行最快的实用程序（实现最高的）。1989年，获胜者使用了八处理器的Cray Y-MP以1680 的速度运行。根据这些数据，1995年要达到1 的处理能力，多处理器系统和应用程序必须每年提高3.6倍。1999年，第一名获得者超过了1 的标准。他们使用了专门为 设计的5832处理器IBM RS/6000 SST系统，他们在冲击波仿真中实现了1.18 。这个比率表明，每年都有1.93的提高，这仍然是相当可观的。

90年代以来，已经公认的是，尽管已经拥有构建多处理器系统的技术，但除少数非常特殊且至关重要的应用外，还不清楚该机器是否具有成本效益。我们在1990年估计，要实现1 ，则需要一台具有约5000个处理器的机器，成本约为1亿美元。的5832处理器的IBM系统花费了1.1亿美元。可以预料的是，单个微处理器在成本和性能方面的提升直接影响大型多处理器系统的成本和性能。但是，使用5000个处理器的系统的价格，将是使用相同处理器的台式机的5000倍以上。从那时起，我们已经建造了速度更快的多处理器系统，但是主要的改进来自过去五年中处理器性能的提升，而不是并行体系结构本身有根本的突破。

Bell的第二个预测涉及1995年发货的超级计算机中的数据流数量。Danny 相信，虽然数据流数量少的超级计算机可能是最畅销的，但最大的多处理器系统将是具有许多数据流，并且将处理大量的计算。Bell和打赌，认为到1995年最后一个季度，使用较少数据流（≤100）而不是大量数据流（≥1000）的多处理器产品会实现更高的持续性（ ）。这个赌注只涉及超级计算机（超级计算机定义为，用于科学应用，成本超过100万美元的多处理器系统)。持续性的定义是每月的浮点运算次数，因此多处理器系统的可用性也会影响其评级。

在1989年下注时，我们还不清楚最终谁会获胜。到1995年，对当时公开的超级计算机进行的一项调查显示，世界上仅存在六个多处理器系统，具有1000个以上的数据流。因此，Bell的预测无疑是准确的。实际上，在1995年，基于微处理器的小型多处理器系统（20个处理器）开始占主导地位。1995年，对使用的500个最高性能的多处理器系统（基于等级）进行的一项调查（称为）表明，最多的多处理器系统是基于总线的共享内存多处理器！到2005年，各种集群或多计算机系统发挥了重要作用。例如，在排名前25位的系统中，有11个是自定义集群，例如IBM Blue Gene系统或Cray XT3。10个是共享内存多处理器集群（均使用分布式和集中式内存）；其余4个是使用PC和现成的互连技术构建的集群。

More

除了并行向量多处理器（请参阅附录G）和IBM Blue Gene的最新版本以外，所有其它最近的MIMD计算机都是使用现成微处理器构建的，它们都使用总线和逻辑上的中央存储器（ ），或者是互联网络结合分布式存储。80年代建造的许多实验性多处理器系统进一步完善和增强了这些概念，构成了当今许多多处理器系统的基础。

The of Bus-Based

尽管在60年代和70年代，人们使用多个处理器构建了规模巨大的大型机，但直到80年代，多处理器系统才取得了巨大的成功。Bell [1985]指出，关键原因在于微处理器的较小尺寸使得用内存总线代替互连网络硬件成为可能，而可移植的操作系统则意味着多处理器项目不再需要开发新的操作系统。Bell在他的论文中定义了和这两个术语，并为构建大型多处理器系统的两种不同方法奠定了基础。

第一个基于总线，使用了侦听缓存（ ）的多处理器系统是 N+1 Frank [1984]. [1983]是第一篇讨论监听缓存的论文。80年代后期，出现了很多商用的基于总线侦听缓存架构的系统，包括 4D/240 [, , and 1988], [], 以及 [ and 1988]。80年代中期，出现大量缓存一致性协议， and Baer [1986]给出了很好的综述和分析，包括对原始论文的参考。图M.2总结了几种侦听缓存一致性协议，并显示了一些已经使用或正在使用该协议的多处理器系统。

90年代初，这类系统的扩展开始了，它们使用了非常宽的高速总线（SGI 系统使用256位，面向数据包的总线，最多支持8个处理器板和32个处理器）。之后，开始使用多个总线和交叉开关互连，例如Sun SPARC 和系统（ [1998]讨论了这些多处理器的互连体系结构）。在2001年，Sun 服务器代表了广泛使用的大规模（> 16个处理器），对称多处理器（- ric ）。如今，大多数基于总线的系统仅提供4个处理和交换机，其他一些设计支持8个或更多的处理器。

Large-Scale

在构建大型多处理器系统的过程中，人们探索了两个不同的方向：消息传递多计算机（- ）和可伸缩共享内存多处理器（ - - ）。尽管人们开始的尝试包括基于网格（mesh ）和超立方体连接（- ）的多处理器系统，但成功将所有部件组合在一起的首批多处理器之一是在建造的 Cube [Seitz 1985]。它实现了路由和互连技术方面的重要进步，并显著降低了互连成本，这有助于使多计算机成为可能。英特尔iPSC 860是超立方体连接的i860的集合，它就是基于这些思想。诸如Intel 之类的较新的多处理器系统已经使用了较低维数和较高单个链接的网络。尽管许多用户发现最好同时使用i860处理器进行计算和通信，但在每个节点中还是采用了单独的i860作为通信控制器。 CM-5使用了现成的微处理器和胖树互连（fat tree）（请参阅附录F）。它支持在用户级访问的通信通道，从而显著改善了通信延迟。在1995年，这两个多处理器系统代表了消息传递多计算机的最新技术。

构建可伸缩共享内存多处理器系统的早期尝试包括IBM RP3 [ et al. 1985]，纽约大学的[Elder et al. 1985年； 1980]，伊利诺伊大学Cedar项目[ et al. 1983]，以及BBN and [BBN 1986; et al. 1990]。这些多处理器系统都是非一致的分布式内存模型上的变体，因此属于分布式共享内存（DSM）多处理器架构，但它们不支持缓存一致性，这使编程非常复杂。RP3和项目都探索了同步（fetch-and-），以及在网络中合并内存访问的新想法。在所有四个项目中，互联网络的成本都比处理节点高，这给较小版本的多处理器带来了问题。Cray T3D/E（ et al. [1995]对T3D的评估，以及Scott [1996]对T3E增强的描述）基于这些探索，使用了非一致（）的共享地址空间，但使用了在多计算机领域开发的互连技术（Scott and [1996]）。

通过结合不同的思想，人们提出了具有可扩展缓存一致性的扩展共享内存模型（- ）。在侦听缓存技术之前，实际上已经有了基于目录的缓存一致性技术。第一个缓存一致性协议使用的是目录方式（如Tang [1976]介绍，并在IBM 3081中实现）。 and [1978]描述了一种在存储器中带有标签的目录一致性方案。 al.[1988]首先提出了用内存分配目录以获得可扩展的高速缓存一致性的想法，并作为斯坦福DASH多处理器系统的基础（ al.[1990，1992]），这是第一个可操作的，缓存一致的DSM多处理器。DASH是一台“ plump”节点cc-NUMA机器，该机器使用四处理器SMP作为其节点，以类似于的样式互连，但是互连使用的是可扩展性更好的二维网格而不是交叉开关。

的KSR-1 [ et al. 1992年]是可伸缩一致共享内存架构的第一个商业实现。它扩展了基本DSM方法，以实现称为cache-only （COMA）的概念，该概念使主内存成为缓存。在KSR-1中，可以在每个节点的主内存中复制存储块，由硬件处理这些复制块的其他一致性要求。（KSR-1并不是严格意义上的纯COMA，因为它不会迁移数据项的原始位置，而是始终在原位置保留一个副本。从本质上讲，它仅实现复制。）许多其他研究[ and Wood 1997; ， and ，1992年； et al. 1995; €om，Joe and Gupta，1992年]提出了各种COMA样式的体系结构和类似方法，这些方法通过迁移（）减少了非一致内存访问的负担[ et al. 1994年； et al. 1998年]开发，但都没有进一步的商业实施。

使用两级体系结构实现了可伸缩的一致性共享内存：在最低级，使用交叉开关构建了八个处理器模块。在此基础上，一个环最多可以连接32个这样的模块，总共256个处理器（ al.[1997]）。 and [1997]描述了SGI ，于1996年首次交付，尽管它在可伸缩性和易于编程方面进行了许多创新，但还是很大程度上基于原始的 DASH机器。为目录结构使用一个比特向量，该向量的长度为16或32比特。每一比特代表一个节点（由两个处理器组成）；另一种粗粒度的比特向量表示方法允许每个比特表示最多8个节点，总共1024个处理器。如 [1996]所述，它将高性能胖超立方体（fat ）用于全局互连。， and Keen [1997]提供了对存储系统性能的全面评估。

同时，人们开展了一些研究原型工作，以探索有无多线程情况下的可伸缩一致性，包括MIT 计算机[ al.1995]和斯坦福FLASH多处理器系统[ al.2000; al.1994]。

集群可能是计算机的用户在60年代“发明”的，他们可能无法在一台计算机上完成所有工作，或者在主计算机出现故障时需要备份计算机[ 1998]。于1975年推出了一个16节点的群集。之后，在1984年推出的VAX群集。它们最初是共享I/O设备的独立计算机，需要分布式操作系统来协调工作。很快，计算机之间建立了通信链接，从而可以在不同地理位置上分散部署，以提高单个站点发生故障或遇到灾难时的可用性。用户登录到群集，并且不知道他们的任务在哪台计算机上运行。到1993年，DEC（现在的惠普）销售了超过25,000个集群。其他早期的公司包括（现在的惠普）和IBM（仍然是IBM）。如今，几乎每个公司都有集群产品。这些产品大多数都是针对可用性，而性能可扩展性是其另一个优势。

集群上的科学计算成为MPP（ ）的竞争者。1993年，项目开始，它的目标是满足NASA对价格低于50,000美元的1 计算机的需求。1994年，使用现成的PC（80486处理器）构建的16节点群集实现了该目标[Bell and Gray 2001]。这种趋势也催生了各种软件接口，使提交，协调和调试大型程序或大量独立程序更加容易。

这个领域的重要努力包括尽力减少集群中通信的延迟并增加带宽。一些研究项目致力解决这些该问题。（低延迟研究的一项商业成果是VI接口标准，该接口已被标准接受，下面将进行讨论。）此外，低延迟被证明在其他应用程序中很有用。例如，在1997年，加州大学伯克利分校的一个由100台Ultra-SPARC台式计算机组成的群集，通过交换机，以每个链接以160 MB/秒的速度连接，打破了数据库排序的世界纪录- 1分钟内完成8.6 GB最初保存在硬盘上的数据排序；还打破了破解加密消息的记录，只需花费3.5个小时即可解密40位DES密钥。

称为 of 的研究项目[， and 1995]，还开发了搜索引擎，该搜索引擎催生了一家具有相同名称的初创公司。遵循的经验，利用台式计算机集群而不是大型SMP计算机构建搜索引擎，这是取代领先的搜索引擎Alta Vista的策略[Brin and Page 1998]。2011年，几乎所有服务都依靠群集为数百万客户提供服务。

集群在科学家中也很受欢迎，原因之一是成本低廉。因此，单个科学家或小组可以拥有一个专用于运行他们的程序的集群。相对于在超级计算机中心的共享MPP的工作队列中等待数周时间，这样的集群可以更快获得结果。如果有兴趣深入，可以看看 [1998]，一本关于集群的很有趣的书。

in Large-Scale

在90年代中期至后期，很明显，超大型并行计算市场增长的希望不太可能实现了。非常明确的是，高端并行计算市场无法支持高度定制的硬件和软件的成本。从这个观察出发，得出的最重要的趋势也许是，群集将被用于达到最高的性能水平。现在有四类通用的大型多处理器系统：

IBM Blue Gene是这些设计中最有趣的，因为其基本思想和单处理器体系结构中朝多核发展的根本原因是相悖的。Blue Gene是IBM内部的一个研究项目，旨在解决蛋白质测序和折叠问题。Blue Gene的设计人员发现，能耗在大型多处理器系统中正变得越来越需要关注，而嵌入式系统中的处理器的性能/瓦数要比高端单处理器好得多。如果并行性是实现高性能的途径，那么为什么不从最高效的处理器开始，仅仅需要更大数量？

因此，Blue Gene是使用定制芯片构建的，该芯片包括嵌入式微处理器，该微处理器提供高端的一半性能，但功耗却小得多。这样可以将更多的系统功能（包括全局互连）集成到同一芯片上。通过这种方式可以获得高度可复制和高效的基本模块，使Blue Gene可以更有效地实现更大的处理器数量。Blue Gene并未使用独立的微处理器或标准台式机板作为基本模块，而是使用了处理器内核。毫无疑问，这种方法可以提供更高的效率。但是，市场是否可以支撑定制设计和专用软件的成本仍然是一个悬而未决的问题。

2006年， 的Blue Gene处理器有32K个处理器（原计划于2005年底达到65K），在性能方面领先于排名第三的由20个SGI Altix 512处理器构成的集群2.6倍。

Blue Gene的前身是一台实验性计算机QCDOD，它利用了低功耗嵌入式微处理器和紧密集成的互连技术来降低节点的成本和功耗。

in and

针对共享内存多处理器系统，人们提出了各种各样的同步原语（ ）。- and Scott [1991]提供了对这些问题的概述，以及重要原语（例如locks and ）的有效实现。大量书籍包含了对其他重要贡献的参考，包括spin locks, locks, and 的发展。 [1979]引入了顺序一致性（ ）的概念以及并行程序正确执行的含义。， and [1988]引入了弱序（weak ）的思想（最初是1986年）。1990年，Adve and Hill提供了更好的weak 定义，并定义了data-race-free的概念。在同一次会议上，和他的同事（1990年）介绍了 ，并提供了有关 性能的第一批数据。更宽松的一致性模型已在包括Sun SPARC，Alpha和IA-64在内的微处理器体系结构中广泛采用。Adve and [1996]提供了关于内存一致性以及这些模型之间差异的出色教程。

Other

1988年，在Kai Li的Ivy系统中首次提出了使用虚拟内存在不同机器之间实现共享地址空间的概念。随后的论文探索了硬件支持问题，软件机制和编程问题。Amza et al. [1996]描述了一种由工作站构建，使用新的一致性模型的系统。 et al. [1997]描述了一种使用远程写入的软件共享存储方案。 al.[1996]描述了使用共享虚拟内存来构建以SMP为节点的大规模多处理器系统。关于多处理器和多计算机体系结构研究的信息量几乎是无限的：会议，期刊论文甚至书籍的出现似乎比任何人能够吸收的速度都快。毫无疑问，这些论文中有许多将被忽略 - 这与以往不同。大多数主要体系结构会议都包含有关多处理器的论文。年度会议， XY（其中X和Y是一年的最后两位数字）汇集了用户，架构师，软件开发人员和供应商，会议记录以书籍，CD-ROM和在线形式发布（请参见www .）表单。 of and Com- and the IEEE on and ，这两个主要期刊都包含有关并行处理各个方面的论文。以下参考书中包含几本关于并行处理的书，其中，Singh and Gupta [1999]是最新的大规模的成果。多年来，NASA Ames 的 Miya收集了并行处理论文的在线书目。该书目现已包含35,000多个条目，可从以下网站在线获取：

liin

这些参考文献除了记录了目前在实践中使用的概念是如何发现，还提供了对许多已经探索的但发现不够理想，或者应用机会尚未到来的想法。考虑到高性能计算机体系结构的未来将朝着多核和多处理器的方向发展，我们预计在未来的几年中将探索许多新方法。一些人将设法解决在过去40年中使用的遇到的关键硬件和软件问题！

- 第六部分完 -

参考资料见『译』计算机体系结构发展史（‍六）

题图由 生成

: a oil and of and , , by Marc , on