3.0 应用和小矮人
(译者注:原文单词为Dwarfs，意思是有魔法的小矮人)
图1左侧的塔是应用。除了传统的桌面、服务器、科研和嵌入式应用外，面向消费生产的重要性正在增加。
我们决定发掘高性能计算领域中并行化的经验，以期能从中学到有关更广泛领域的并行计算的知识。这样做的前提并非传统的科学计算是并行计算的未来；而是在大规模并行计算机上开发高效运行程序的经验本身或许能为以后应用的并行化提供有用的经验。而且许多其他领域的作者，如嵌入式计算，也为他们自己领域内的未来应用与现有并行计算问题如此的相似而感到吃惊。
比较方便的指导和评测体系结构创新的途径是研究在现有程序基础上构建的基准测试套件，如EEMBC(嵌入式微处理器基准测试组合)、SPEC(标准性能评测协会)或者SPLASH(斯坦福共享存储并行应用).并行计算创新的一个最大障碍是目前还不清楚如何表述一个最好的并行计算。因此，好像就这样鲁莽的就现存的一些源码扩展为并行计算方式并不是明智的做法。现在很需要找到一个更高层次的抽象来就并行应用的需求展开论证。
我们的目标是使用一种不过度针对某个应用或者针对某一类页顶的硬件平台优化的应用需求描述方式，以便我们能引出适用性更广的有关硬件需求的结论。下面将要阐述的我们的方法是定义一定数量的”小矮人”，每个矮人概括了一种适用于一类重要应用的计算和通信模式。
3.1七个小矮人
我们受到了Phil Colella的启发，他找出了七种他相信在至少未来的十年里会对科学和工程应用非常重要的数值计算方法。图3(请打开下面的链接看图)介绍了这七个小矮人，他们依靠计算和数据移动的相似性分成不同的种类。这些在高层次抽象出小矮人使得在大范围的实际需求上的应用能进行理论的验证。一个特定类中的程序能使用不同的方式的方法实现，这些程序底层的数值计算方法也可能随时间而改变，但是需要注意的是底层的模式在这些改变中是始终不变的而且以后也会一样很重要。
有很多的证据表明确实存在这样的特定种类的集合，很多数值计算中都使用这些类来构造。如FFTW用于一些频谱计算，LAPACK/ScaLAPACK用于稠密线性代数计算，OSKI用于稀疏线性代数计算。我们在表3中列出了这些，并且还在表中包含了为特定的小矮人而特别设计的计算机体系结构。例如用于 N-body方法的GRAPE，用于线性代数的向量机，以及FFT加速器。图3中也给出了运行在并行机上时一个小矮人的成员之间的处理器间的通信模式。通信模式是与每个处理器本地发生的存储访问模式紧密相关的。
3.2寻找更多的小矮人
小矮人们给出了一种不同于看起来合理的割裂每个独立实现的方式，而是对应用进行归类并从中观察它们的普遍需求的方法。虽然小矮人这一术语来自Phil Colella就科学计算应用的讨论，但我们对将小矮人应用于更加广泛的计算领域非常感兴趣。这很自然的引出以下问题：
- 这七个用于高性能计算的小矮人在匹配更加广泛的应用中的计算和通信模式方面表现的如何？
- 还需要再增加什么样的小矮人以便满足高性能计算领域之外的重要应用？
如果我们能找到被广泛接受的扩展集合的小矮人，我们就能利用他们来指导创新和对新模式的评测。只要最终的列表不超过30-40个小矮人，体系结构和编程模型的设计者们就能使用它们来衡量是否成功。对比来讲，SPEC2006就有29个基准，EEMBC有41个。我们希望理想情况下，在众核体系结构和编程模型下性能良好的小矮人们在未来的应用中也有良好的表现。
小矮人们是在高抽象层指出的能将相关的计算方法归类但是由于这些方法很不一样。过去，一个小矮人能够扩展应用在不能分割而又应该被看做截然不同的几个小矮人的方法上。倘若我们不使用看起来过多的小矮人，那么将会出现很多盲目的使用新的计算方法的情况.例如，一个非结构化的网格可以被解释成一个稀疏矩阵，但是这将一方面将问题限制在单层非直连上，另一方面也忽略了很多关于这一问题的附加信息。
为了了解这7个小矮人的适用性，我们将这份列表和其他的测试基准套件做了比较：用于嵌入式计算的EEMBC和用于桌面和服务器系统的SPEC2006。这些基准套件是和我们的研究独立的，所以他们的观点将能证实我们这种小规模的计算内核是否是未来应用的好的目标。我们将在3.5节中详细的讨论这个最终列表，但从我们就EEMBC的41个内核和SPEC2006的26个程序的检查中，我们找到了四个新的能添加到列表中的小矮人。
- 组合逻辑通常别用在大量数据间简单操作的位间并行发现。例如，正确验证的关键—计算循环冗余编码(CRC)和数据安全加密的RSA。
- 图遍历应用将遍历一定数目的对象并检查这些对象的属性，如在搜索中的应用。它通常需要非连接表查询以及少量计算。
- 图模型应用需要随机变量作为节点，条件依赖作为边的图。这样的例子包括:贝叶斯网络和隐式马尔科夫模型。
- 有限状态自动机表达一个状态集合之间的互联，如进行语法分析时。一些状态机可以分解为多个能并行工作的同时活跃状态机。
为了能超越EEMBC和SPEC，我们考察了三个正变得越来越重要的应用领域来看是否需要增加机器学习、数据库软件和计算机图形与游戏方面的小矮人。
3.2.1机器学习
使用统计机器学习来从大规模数据中感知，作为未来计算的一个非常有前途的方向。更快的计算机，更大的磁盘和将它们连接起来的互联网的应用正使统计机器学习变为可用。
我们中机器学习方面的专家Michael Jordan和Dan Klein，找到了两个应该添加以便支持机器学习的小矮人:
- 动态规划师一中通过解决嵌套的子问题来最终解决问题的算法技术。它对于一个问题的优化结果建立在其子问题优化结果基础上的优化问题尤为合适。
- 回溯和分支与边界:它们用于解决庞大空间中的各种搜索和全局优化问题。对于没有包含有利的解决方案的搜索空间的范围约束需要一些既定的方法。分支和绑定算法利用的是分治的概念：搜索空间被切分成较小的域(“分支”)，这些被考察的子域中的方案就使用了绑定方法。
很多其他著名的机器学习算法都能归类到其他已有的小矮人中：
- 支持向量机：稠密线性代数
- 主要成员分析:稀疏或稠密线性代数–由实现细节决定。
- 决策树:图遍历
- 哈希：组合逻辑
3.2.2数据库软件
微软研究院的Jim Gray相信排序是现代数据库的中心。他发起了每年一届的比赛来角逐谁能用最快的算法解决输入和输出都在硬盘上的排序问题。在一分钟内能将以100比特单位存储的数据排序最多的人能赢得MinuteSort项目，2006年的获胜者在一个有128GB竹醋和128块硬盘的安腾2 1.6GHz多核处理器32路共享存储的计算机上排序了400百万的记录(40GB)。这个算法使用了一个既能直接对数据排序又能使用指向数据的指针排序的叫做Nsort的商业排序包。它是一个抽样排序算法。尽管它为输入输出和主存之间提供了重要的接口用来使排序变快，但排序没有进入我们的小矮人列表中.
现代数据库系统另一个重要的功能是哈希。不像标准的哈希算法，数据库中的哈希将对大量的数据进行计算，可能是主存中一半的数据。又一次，这些计算和通信模式没能扩展小矮人列表。
Joe Hellerstein是我们研究组中数据库方面的专家，他说未来的数据库将是类似于在Internet能看到的大量数据的集合。一个简单的存取这种集合的方式是被Google开发并广泛使用的MapReduce算法。第一阶段将一个用户提供的函数作用在数以千计的计算机上，处理键/值组合来产生一种中间形式的键值组合。第二阶段将所有这些数以千计的返回值精简到单个结果中，这个结果从与同一个中间键相关联的所有中间值来合并得到的。注意到这两个阶段是高度并行而又容易理解的。他们借用Lisp中一个小函数的名字，将这种方法称为简单的MapReduce。
MapReduce是一个比我们先前称之为Monte Carlo的模式更加通用的版本：它的基础是一个能并行作用在独立数据集合上，只是将输出最终合并生成一个小巧的几个结果的简单函数。为了能让它用于更广的领域，我们将它这个小矮人的名字改为”MapReduce”.
第二个对未来数据库起促进作用的方向是遗传学，典型的例子是被普遍使用的BLAST(基本本地对齐搜索工具)代码。BLAST是一个探索式的方法，主要用于找出DNA或者蛋白质序列中和数据库中非常相近的序列。
有三个主要步骤:
- 从序列中收集出一个高分的词列表
- 扫描数据库来得到命中这个列表的项
- 扩展这些命中项来优化匹配
虽然很明显BLAST很重要，但是它并没有扩展我们的小矮人列表.
3.2.3计算机图形学与游戏
逼真显示的竞赛已经将图形处理单元(GPU)的处理性能提高到了Teraflops的量级，图形还原已经不是独立的在屏幕上画出多边形和纹理。在物理上为处理建模来指导这些图形对象的行为都或多或少的需要一些有大规模科学计算仿真需求的计算模型。对于计算机视觉和多媒体处理中的很多任务也是一样，这些需求构成了未来应用的核心，也同样构成了硬件厂商未来的技术路线。
人们认为所有使用GPU来为所有的实际应用做片上并行来加速计算机图形处理速度的问题已经解决。在这一点上主机处理器所面临的概念上的困扰在于如何为构成游戏和用户界面上的图形单元建立物理属性模型。现实中的物理学需要的物理处理的可计算模型在概念上和科学计算应用中的需求是一样的。那些已被使用的可计算模型和构建最初的七个小矮人的初衷非常的相似。
例如，电影中为液体以及液体行为的特效建模就用到了像颗粒平滑流体力学之类的方法。虽然这种物理模型的展现仍然使用GPU或者软件方式在OpenGL中实现，但是液体的流动形状的底层建模仍然需要基于颗粒的流动模型。还有很多其他对游戏和图形中的物理属性建模的需求与其他小矮人对应的例子:
- 反转变换需要稀疏矩阵计算和图遍历方法的结合.
- 弹簧模型，用于对任何因受压产生形变或者反应弹球或Jell-o的坚硬对象使用稀疏矩阵或者有限元模型建模
- 碰撞检测室一种对Octree和Kd 树之类的图遍历操作用来做深度排序和隐藏表面移除。
- 碰撞反应经常使用有限状态机来实现。
因此，得到令人意外的结论，游戏和图形不需要扩展上面的13个小矮人。
我们从GPU和同性软件中得到的另一个积极的启发是这两者的API都没有直接的将并发问题交给开发者来解决。例如OpenGL允许程序员在Cg(一个用来描述这种操作的特定语言)中描述一个可应用于屏幕上针对每个多边形的“顶点阴影”操作，但并不需要程序员考虑硬件有多少个GPU中硬件已经实现的可用硬件片段处理器或者节点处理器。
3.2.4 对新的6个小矮人的总结
图4给出了我们通过前面几节的谈论增加的6个小矮人。注意我们认为这些算法和输入数据的规模和类型无关(参见5.3节)
虽然这13个小矮人中的12个具有一些形式的并行性有限状态自动机(FSMs)看起来就比较困难了，这也是为什么我们将它作为最后一个小矮人。或许 FSMs能证明为非常复杂的串行算法，就像MapReduce被证明为非常复杂的并行算法一样。如果它仍然很重要又不能在并行化方面有创新，那将是非常令人失望的，但是可能长远来看正确的解决方式可能是改变其算法的结构。在多核和众核时代，串行计算时期比较流行的算法可能会在流行中退去。例如，如果霍夫曼解码只能被证明是复杂的串行算法，可能我们需要使用一个不同的能屈膝于并行化的压缩算法。
无论什么情况下，这13个小矮人的目的都不是为了识别应用底层的高度并行性。他们的目的是识别在未来十年里非常重要的应用中至关重要的独立于并行性的计算和通信的内核。
无论什么情况下，这13个小矮人的目的都不是为了识别应用底层的高度并行性。他们的目的是识别在未来十年里非常重要的应用中至关重要的计算和通信的内核。为了能开发在未来应用中尽可能高效的编程体系结构，我们必须了解他们的局限性和机遇。但是，我们注意到低效的复杂并行程序可能是未来体系结构失败的原因，就像现在串行程序的弱点一样。
可能需要更多的小矮人加入到这个列表中。然而，我们惊奇的发现只需要增加6个小矮人就能覆盖如此大范围的重要应用。
3.3小矮人的构成
像MPEG4解码和IP转发这么有意义的任何应用都会包含多个小矮人，每个小矮人都占整个应用计算量的一定比例。因而，一个大型应用的性能不仅仅由每个小矮人的性能来决定，而且也包括了这些小矮人在该应用上的结合方式。
这些组成特定应用的小矮人们可以再一个多核处理器平台上按照下面两种不同的方式分配：
- 临时分配，或者分时共享一个处理器集合
- 空间分配，或者以每个小矮人单独占领一个或多个处理器的方式来实现空间共享。
选取临时分配或者空间分配将部分依赖于小矮人之间的通信结构。例如，有些应用由一些串行的阶段构成，每个阶段都是一个小矮人且需要在运行下一个小矮人之前结束。在这种情况下，我们自然需要使用分时的方式将整个处理器集合分配给每个阶段。还有一些应用由当前运行的小矮人形成的通信网构成，此时我们就很自然的需要选取在空间分配的方式来讲小矮人们分配到可用的处理器核上。
这两种形式的分配时能够混合使用的。例如，一个小矮人可能需要使用流水线的方式来实现，即对于给定的输入其计算过程可以分成几个不同的步骤，每个步骤可以在它自己所分配的处理器核上运行。而每一个步骤对于连续的输入来说又是可以分时进行的，但是对于单个输入的处理将流过所有这些空间分配的流水线步骤。
当考虑小矮人的组成时有两个软件问题需要注意：
- 构成模型的选择–这些小矮人是如何被放在一起最终组成一个完整应用的。科学软件社区已经开始就这一问题开展工作，然而，在这些模型里，独立的模型之间并没有紧密的联系，这将影响最终应用的实现效率。
- 数据结构转换。不同的算法可能有他们自己独特的数据结构，如稠密矩阵中的循环数据存储。这将可能抑制结合的高效性，因为可用的数据集可能需要在被其他小矮人使用前做转换。
上面的问题只是一个难题中的小片段而已。高效的描述可重构的并行代码库的方式是什么？我们能编写一个与其他小矮人构成一个完全并行的应用时可以理想地映射所有知识的库吗？如果这种理想的映射密切依赖于编译时无法知道的输入数据集，我们要如何面对？
3.4 Intel的研究成果
Intel相信计算需求的增加将来源于处理”Era of Tera”中可用的大规模信息。Intel将计算分成三种：识别、挖掘和合成，简称RMS。识别是一种机器学习，计算机监测这些数据并使用它们构建数学模型，一旦计算机建立了模型，挖掘开始搜索互联网来寻找这个模型的实例，合成是指创建一个新的模型，例如图形。因此，RMS与我们之前在3.2.1到 3.3.3中考察的机器学习、数据库和图形学相关。RMS的通常计算主题是“基于大规模复杂数据集的多模型识别与合成”。Intel相信RMS将会找到在医药，投资，商务，游戏以及家庭中很多重要的应用。Intel在图5中的努力说明伯克利在试图充重组底层计算内核来引领体系结构研究未来的方向上并不孤单。
3.5 Dwarfs 总结
图6总结了我们的研究结果，并且展示了13个小矮人及包含他们的各种不同的应用基准套件，如EEMBC，SPEC2006，机器学习，图形/游戏，数据库软件和Intel的RMS。正如上面提到的，几个程序使用了多个小矮人，因而他们被列在多个表格中。我们不确认这份小矮人列表已经是完备的，而且我们预感到未来还会有更多的小矮人加入。与此同时，我们也为一定数目的小矮人能支持如此多样的重要的应用而感到吃惊不已。
近期评论