软件设计者的契机与挑战.doc

新一代的处理器体系结构-软件设计者的契机和挑战新一代处理器体系结构软件设计者的契机与挑战 中国科学技术大学计算机系系统结构实验室 王峰 陈艾 编者按：本报今年5月9日刊出的CMP开启处理器效能时代技术专题引起了读者强烈的反响，很多读者来信希望能对有关软件编程问题做进一步的深入介绍。本期特约中国科大的专家撰文以飨读者。盛宴的开始“Andy Grove giveth, and Bill Gates taketh away”是流行在业界的一句谚语，它描述了一个有趣的现象：无论处理器能够提供多高的性能，软件都能够将它们统统“消化”掉。在过去几十年里，被处理器 技术领域奉为金科玉律的“摩尔定律”一直处于雷打不动的地位。但就在近两年，传统处理器体系结构技术面临着性能的瓶颈。人们逐渐发现过去惯常的技术方案已 经不能够在处理器设计领域获得更高的收益。处理器的设计者们开始思考新的技术架构，试图推动处理器的性能能够遵照“摩尔定律”得到继续提高。处理器的硬件 架构作为计算机系统中最核心的技术，它的变革势必会导致业界的一系列动荡。特别是软件开发者们就首当其冲地迎来了新的契机与挑战。为了能够享受到新的处理 器技术带来的这场“盛宴”，就必须迎接一场具有颠覆性的革命。 多线程并行：多核伴侣在传统处理器技术中，用于提高处理器性能的主要方法有三种：提高时钟频率、优化执行流和Cache技术。提高时钟频率是为了获得更多的时钟周期数。目前的理论和实践都已经证明，由于众多物理因素的影响，比如散热、能耗、漏电流问题等，提升处理器的主频已经碰 到了不可逾越的障碍。Intel去年秋天宣布放弃4GHz主频处理器研发表明提高时钟频率已经不能再作为主流的处理器技术。优化执行流技术是为了在每个周期内完成更多的工作。包括流水线、分支预测、指令多发射、指令乱序执行等方法。设计者为了提高处理器性能，会重新组织指令的 执行顺序以达到优化的目的。但片面追求面向高性能的执行流优化技术，会导致很坏的情况发生，比如可能会危及到代码的语义甚至改变程序的功用，同时给软件开 发者的调试工作带来很大的麻烦。Cache技术能够缩小处理器与存储系统间的性能差异。计算机系统对存储器的访问始终是一个性能瓶颈，特别是在处理器性能的改进远快于存储器、I/O设备等的情况下。必要的Cache能够有效地减少访存时间。当前主流处理器都在尽力提供更多的Cache资源。从上述对这三种方法的分析中可以看出，提高时钟频率和优化执行流技术当前已经很难再有进展，而Cache技术则随着芯片集成度的增高仍旧能够发挥巨大的作用。在传统的处理器技术已经不再能够推动处理器性能遵循“摩尔定律”向前发展的时候，以单芯片多核技术（CMP）为主流的新一代处理器体系结构开始崭露头角并 已经逐渐占据了处理器市场的主导地位。为了能够充分利用新一代处理器体系结构带来的种种优势，软件设计者们必须能够掌握并使用多线程并行的编程思想。这将 是软件产业的一场革命。在新一代处理器体系结构的研究中，各种新技术层出不穷。在当前逐渐趋于成熟的技术当中，有三项技术已经被应用于新一代处理器当中。它们分别是：单核多线程技术、单片多核（CMP）技术和Cache技术。单核多线程技术是指在单个处理器核上同时运行两个或更多个线程。目前已经应用在具有超线程结构的奔腾4处理器当中。CMP技术是指在单个芯片内集成两个或更多个真正的处理器核，不同的线程同时运行在不同的处理器核上。采用CMP的芯片有很多，比如Sparc和PowerPC都已经有了产品，Intel和AMD也在今年推出了各自的多核芯片。Cache技术作为处理器关键技术中的“常青树”，仍旧会有长足的发展，这主要是因为Cache不命中导致的访存延迟代价实在太高。未来Cache技术的发展方向主要体现在容量的增加上。在单核多线程和CMP技术中，单核多线程技术由于需要多个线程共享同一个处理器核上的Cache资源、整数部件、浮点部件等关键资源，会给线程的管理和执 行带来诸多困难，并且对这些资源的共享和竞争会进一步影响到处理器性能的提高。而CMP技术正日益成为业界研究和发展的焦点。随着超大规模集成电路技术的 发展，有十亿量级的晶体管已经可以集成在单片芯片上，这就为CMP技术提供了基本技术支持。我们不妨以Sun公司对片上多核处理器的研发路线为例回顾一下片上多核技术的发展历程。上世纪90年代中期，Sun公司意识到了仅单纯依靠在单线程处理器 架构上提高主频来提高处理器性能的方法将会遭遇障碍，于是开始研究自己的线程级并行处理器体系结构MAJC。MAJC是业界迈向多线程处理器技术的第一 步。MAJC-5200是第一代CMP的处理器芯片，它的特点是两个处理器核共享L1 Cache。之后，Sun开始将Sparc芯片族纳入CMP设计中。2003年，Sun发布了两款多核处理器:Gemini和Jaguar。同MAJC- 5200一样，它们同属于第一代多核处理器，特点是片上各处理器核使用的仍旧是过去单核处理器的设计，除了片外数据通路以外，两个处理器核并不共享任何资 源。同年，Sun发布了第二代多核架构处理器：UltraSparc-IV+。 这款处理器的特点在于两个处理器核是共享片上的L2 Cache和片外L3 Cache的。当前，Sun已经在实验室里开始了对第三代多核处理器的研制测试工作。第三代处理器的项目代号叫作Niagara，它在芯片上集成了8个处 理器核，每个处理器核又支持4路同时多线程（SMT）技术，而且有自己的私有L1 Cache。所有的处理器核共享3MB的12路的L2 Cache。第三代单片多核处理器体系结构的特点是它的整个设计，包括片上的各个处理器核，都是专门针对多线程并行体系结构技术做过优化的。当前采用多核技术的处理器主要面向的对象是高端服务器，因为这类应用中存在着大量的线程级并行可供挖掘以提高处理性能。但是，已经有迹象表明，多核处理器的应用已经开始向桌面应用和嵌入式应用方向转移。从过去的处理器关键技术与新一代处理器关键技术间的对比可以看出，当前的技术主要关注的是多线程并行的处理器体系结构。之所以会有这样的技术趋势，主要是 有两个原因：首先是因为在过去的处理器体系结构中指令执行时往往会有大量的停滞和延迟，而线程的存在就可以充分有效地利用和掩盖这些延迟：当某个线程中的 指令流被迫等待时，可以及时地切换进另一个线程执行以节省时间。其次是因为可以通过挖掘线程间并行的能力来提高系统的吞吐量，提高系统中的资源利用率。在新一代处理器逐渐占据市场的主导地位后，各种问题会相继涌现。其中最急切的需求是配套的系统软件支持和应用软件开发。随着多线程处理器体系结构特别是 CMP的提出并成为处理器领域中的主流技术，多线程并行的编程技术势必将成为新一代处理体系结构中的软件编程技术的发展方向。下面本文首先讨论了应用软件 开发中面临的诸多问题，然后会就系统软件需要解决的某些关键问题做一些探讨。多线程并行编程：从阳春白雪到下里巴人过去所有在单核处理器上开发的串行应用软件仍旧可以在新一代处理器体系结构上运行。但仅这样不能充分利用新一代处理器架构带来的性能优势，是一种“暴殄天 物”的做法。可以毫不夸张地说，新一代处理器体系结构给软件产业带来的将是一场革命：它要求软件设计者们务必摒弃之前传统的串行编程方法，去掌握多线程并 行的编程理念。谈及软件产业的革命，我们不妨先回顾一下上一场由面向对象编程思想引发的软件界革命。从上世纪90年代到现在，我们开始学习、掌握乃至大量应用 “对象”这个概念，完成了从结构化编程到面向对象编程方法的转变。这个转变可以说是过去20年里最重大的变化，它直接颠覆了软件设计者的视点和编程思想。 在过去的岁月里，软件领域还有很多其他变化，比如Web服务的兴起等等，但是它们显然没有面向对象编程这场革命给软件设计者的职业生涯带来的影响这么深 远。那么为什么我们认为当前的多线程并行编程理念将是又一场软件界的革命呢？也许有人会说：并行的编程方法由来已久，早已经不是什么新技术了。此言不错，但是 需要注意的是，在过去的日子里，真正掌握并使用并行编程技术的软件设计者大多集中在科研院所和大专院校，他们只占全部软件设计者人数的极少部分，是软件界 的“阳春白雪”。这里我们仍旧要提及面向对象的编程思想：追溯到上世纪60年代Simula语言出现的时候，从那时起就已经有人开始进行了面向对象编程的工作。但是直到 90年代，整整30余年的时间，面向对象技术一直都没有能够成为一场革命，没有能够占据主流软件设计领域的主导地位。但是为什么它突然就引发了一场重大的 变革呢？答案很简单。在软件产业中，越来越强的处理器和存储资源使得我们可以编写越来越庞大的系统去解决越来越复杂的问题。而面向对象的编程技术在系统抽 象和项目管理方面的巨大优势使得它在大规模软件开发过程中成为了一种必需。它能够帮助软件开发人员获得经济的、可靠的和可重用的开发模式。同样的，多线程并行的编程技术以当前多核体系结构的广泛使用为背景，也必将成为即将到来的必需。不可否认，在过去的时日里，已经有太多的新技术被人们标榜 为“一场软件开发界的革命”。但是我们要切记一件事：新的技术往往是有趣的，在某些方面也是卓有成效的，但是如果这项技术要作为一场革命，那么它务必要经 过很多年的积累和成长，最重要的是它必须被充分地验证过，才有可能够引爆一场革命。因此，一项软件开发技术从提出到成熟（比如有可靠的开发商和工具支持） 到排除了性能缺陷和其他问题从而能够在业界被广泛应用，这期间一般需要至少七八年的时间。最终，一场类似面向对象的软件开发界的革命要经历十数年甚至数十 年的磨砺，正所谓“厚积薄发”。多线程并行的编程技术就是软件界即将到来的革命。它给软件界带来的冲击是否会超越上一次革命中的面向对象编程思想，我们还不得而知。但是毫无疑问的是，对 于软件设计者们来说，如果我们希望仍旧能够充分利用到新一代处理器不断增强的性能，那么我们就必须要能够熟练地编写支持多线程并行的应用软件代码。由上述的分析我们有理由相信：多线程并行的编程技术就是软件界即将到来的革命。它给软件界带来的冲击是否会超越上一次革命中的面向对象的编程思想，我们还 不得而知。但是毫无疑问的是，对于软件设计者们来说，如果我们希望仍旧能够充分利用到新一代处理器不断增强的性能，那么我们就必须要能够熟练地编写支持多 线程并行的应用软件代码。这个过程说起来很容易，但是做起来却会非常困难。问题与挑战我们之所以能够通过在CMP上运用多线程并行的编程技术来提高软件系统的执行性能，主要是因为如下两个原因。众多应用中与生俱来地存在着彼此相互独立的控制流。比如数据库应用中，只要几个操作不同时访问同一数据，那么它们彼此间就是互相独立互不干扰的操作。并行（严格地说应该是并发，并行与并发的最主要区别在于并行执行是完全的随时都在同时执行，并发则是指可以在某一个时间段内同时完成。但这两个概念的差异 在本文中并不影响论述，故下文不再做具体区分，统称为并行）的代码能够充分利用多个物理处理器核的优势，同时还可以充分利用应用中其他部分的延迟和停止时 间。在享受多线程并行编程技术带来的收益的同时，不可避免要付出相应的开销，但这些开销往往都是无碍大局的。例如，在并行编程中最经常使用的锁机制就是要付出 一定代价才能获得的。如果程序设计者能够正确恰当地使用锁机制，适当地并行化相关操作，最小化甚至消除共享状态，那么程序就完全可以从中获得更高的收益。 这些收益足以抵消在锁机制中同步操作带来的损失。也许有人会说在并行编程领域中最关键的问题是并非全部的应用都能够顺利地并行化。这个观点正确却不免偏颇。其实，在并行编程技术中最关键也是最困难的问题是在软件设计者的头脑中缺乏并行的编程思想。这也直接导致了人们一致认为某些应用是不能够被并行化实现的。对于大多数人来讲，当我们有意识地去做某件事的时候，特别是在做抽象思维的时候，我们大脑的思维模式就是串行的。这就导致了相对于串行控制流，软件设计者 对于程序并行化的把握要差很多。我们很难想象出合适、合理的并行执行过程，从而也就很难将并行处理的思想引入到应用代码开发的过程中。曾经有很多学习过并行编程技术的软件设计者认为他们已经掌握了并行编程思想的精髓，但是在实际操作时他们却发现了很多莫名其妙的冲突，这表明实际上还是有 很多东西是他们没有真正理解的。也许我们可以采用内部测试的方法来捕捉冲突，但是除非真的可以建立起一个完备的压力测试模型，否则我们仍旧会发现那些测试 后的软件中还是有着很多问题。这些问题只是冰山一角，特别是线程的执行并非只是在单个处理器上反复切换而是在真正的多个处理器核上同时执行的时候，就会产 生更多更复杂的问题。因此我们不能指望发现问题后再对我们设计的软件进行补救，最关键的是要在初始的设计阶段就以并行的思想来避免各种冲突的产生。在当前 新一代处理器体系结构发展的背景下，我们需要重新并行化设计从前的串行应用软件，这个过程会暴露相当多的问题。真正的多线程并行环境会毫不留情地揭露出我 们设计中的种种错误。即使我们已经能够编写出安全、可靠的并行代码，那么也还会存在其他的问题。例如，完全没有冲突的并行代码的效率有可能比在单核处理器 上运行的串行程序还要低。这是因为各个线程间并非是充分独立的，它们需要同时依赖于某个资源，这样会使得这个并行程序又变回了从前的串行执行模式。图 Sun公司CMP处理器研发路线图多核结构下编程思想的变化通过上面的分析，我们可以总结出在新一代处理器体系结构下从事应用软件开发过程中需要具备的几点认识。首先，最主要的一点认识就是如果我们想充分利用新一代处理器体系结构提供的强大性能和高吞吐量，就必须尽量增大对程序并行化的需求。对应用程序并行性的挖 掘可以在多个层面上进行，这其中需要有软件设计者的参与和编译软件的支持。当前的现状是并非所有的应用（更精确地说应该是应用中重要的操作）都能够被方便 地并行化。这里可以举一个例子，母鸡孵鸡蛋，要三周才能孵出小鸡。但是这并不意味着如果我们有三只母鸡的话就可以用一周的时间孵出一只小鸡。我们可能在这 个问题之前之后碰到过类似的问题，我们应该怎么考虑这个问题呢？是不是我们就可以认为这个鸡孵蛋的问题是天生不能够被并行化的呢？也许人们往往会很武断地 做出类似的问题都是不可并行化的推断。但是这个推断并非就是完全正确的。这个推断只有在我们要解决的问题是仅仅孵化一只小鸡的情况下才是正确的，但是如果 我们的目标需求是孵出很多只小鸡的话，那么母鸡孵蛋问题就是一个很理想的并行化问题。这个简单的例子告诉我们在设计应用程序中务必要明确软件设计的真正目 标，不同的设计目标在实现上往往会有很大的差异。在考虑你的软件设计是不是能够以及如何能够并行化的时候，一定要在头脑中时刻牢记这个基本的“面向设计目 标”的原则。这本身也是并行化编程思想对软件设计者们提出的要求。其次，未来的应用会向CPU-bound（接近占用100%CPU处理能力）的方向发展，最终并行化的主流程序设计必将替代现有的单线程应用程序。可以看 到，当前的部分应用仍旧没有CPU-bound的需求，这主要是因为计算机系统中其他一些因素导致的，比如访存的延迟就会导致在那些存储器访问密集型的应 用执行过程中出现处理器时间大量空闲的情况。但是，我们应该注意到，在当前各项传统的处理器技术已经逐步走向尽头的时候，这些相关领域（比如I/O、网络 以及数据库技术等）的各种性能改进仍旧在高速进行着，并可能在不远的将来赶上处理器的性能或者与其性能相匹配，甚至很有可能超越当前处理器的处理能力。由 于从前的处理器技术主要依赖的提高主频改进性能的方法已经很难再有突破，同时各种其他的主流技术也很难发挥出自己的效力，比如流水线技术，处理器设计者们 就已经发现不再能找出更好的方法来保证流水线中的各个流水段总是尽量充满。这种种迹象表明单线程的应用程序已经达到了性能的顶峰。当然凭借于更大规模的 Cache容量，单线程的应用可能还会有部分性能改进，但也只是杯水车薪，它终将不能满足更高的性能需求。我们即将面临的是不断增长的数据处理需求，这就 要求我们编写的程序能做更多的事情。届时，我们会发现我们编写的程序会不断地超越单个处理器核的处理能力。现实情况将逼迫我们必须将应用程序并行化。最后，当前的各种编程语言和系统并不能够处理应用程序并行化带来的诸多问题。当前，软件设计者们使用的各种语言并没有能够完全满足并行化编程的需求。 Java语言从一开始就包含了对并行的支持，但是在Java语言的后续版本中一直在不断地修正其中的一些问题以保证并行编程的正确性和效率。C+语言也 已经在很长的时间里被用于编写处理繁重任务的多线程系统，但是它一直缺乏标准的对并行化的支持（ISO的C+标准中甚至都没有提及线程的概念），这就导 致了我们在使用C+语言编写并行程序时要能够熟练地使用各种平台相关的不具有可移植性的并行特征和库函数。但是即使我们这么做了也经常是不完善的，比如 按照规定，C+程序中的静态变量在内存中只能被初始化一次，那么典型的实现应该是由编译器将其用锁机制进行封装，但是很多C+开发环境在实现这一点时 都不会利用锁机制。当前我们也已经有了一些并行的标准，比如 pthreads和OpenMP，这些标准中有的可以像支持显式并行一样来处理隐式并行。编译器会观察我们编写的单线程程序，自动挖掘出并行化该程序的方 法。但是那些自动转换工具的能力是有限的，并不能获得与我们手工编写的具有显式并行控制的程序等同的收益。总的说来，当前主流的多线程并行编程技术发展方 向仍旧是基于锁的编程方法，但这种方法是有一定风险的。我们需要有更高级的并行编程模型，但这是当前的所有语言都不能给予的。 CMP上的系统软件技术在整个计算机系统中，编译器和操作系统是两个举足轻重的软件系统。也许大部分的应用软件设计者不会深入到底层去探究它们的奥秘，但是我们编写的每一个程序 的性能好坏都与这两个系统软件休戚相关。当新一代处理器浪潮袭来的时候，编译器和操作系统也受到了深刻的影响。前文已述，CMP处理器体系结构将是当前新 一代处理器体系结构发展的主流。在这种架构上，不同的线程在不同的处理器核上运行，彼此间共享片上的L2 Cache。编译器能够将程序设计者编写的应用程序转换为可以在处理器上执行的二进制代码。在编译过程中，编译器可以做大量的代码优化以提高生成代码的执行性能和减小 生成代码所需的执行空间。在从前的针对单核处理器的编译优化过程中，编译器花费了大量的精力去挖掘程序中指令级和循环级的并行关系（在应用程序中存在着各 个层次上的并行性。其中，最底层的就是指令级并行，它指的是应用中各条独立的指令间的并行关系。如果这些可以并行执行的指令来源于同一循环的彼此没有数据 依赖关系的不同叠代的时候，就被称为循环级并行）。而现在面向新一代处理器体系结构的编译器必须要尽力挖掘线程级的并行。编译器划分线程主要是通过对程序 控制流图进行静态的分析，再将其划分为各个线程，每个线程对应控制流图上的一部分。传统的指令级并行的挖掘方法，比如循环展开、复制传播等等，已经不能够 为线程级并行优化做出更大的贡献。如何正确高效地对线程级并行性进行挖掘？面向新一代多核处理器体系架构的编译器主要面临着以下几个问题。第一，如何合理划分线程。在新一代处理器体系结构，特别是CMP架构中，合理的线程划分首先要保证各个处理器核上的负载平衡。负载平衡问题一直是并行计算 系统中最难解决的问题之一。因为达到真正的负载平衡已经被证明是NP问题，所以编译器只能尽力寻找次优的方案。线程的划分中还要考虑到线程间的通信问题。 虽然CMP架构中各个处理器核紧密耦合在一起，但是对它们彼此间的通信仍旧要给予足够的重视。另外，在未来多核处理器的发展中，很有可能出现片上的各个处 理器核为异构的情况。那样的话，编译器的线程划分任务就更加繁重。将新一代处理器带来的高处理能力转化成为应用软件的高执行性能是所有软件设计者面临的契机和挑战。过去的串行编程思想已经不能够在软件性能提高上有更大的 作为，多线程并行编程技术势必会成为软件业的又一场革命。已经习惯了传统编程思想的软件设计者们又要经历一次类似十余年前面向对象技术兴起时的洗礼，但这 个过程也许会更加痛苦。第二,充分利用硬件推断。为了提高性能，新一代处理器体系结构大都提供了专门的硬件来支持线程的推断执行和运行时线程间数据依赖关系的检查。编译技术务必 要能充分利用这些硬件资源的支持。编译器“大胆”地推测某些线程可以投机执行，往往可以极大地提高程序性能。但是如果出现了线程间依赖关系的违背就需要退 回重新执行，相应的代价也是高昂的。同时因为受到推断硬件的影响，编译器划分线程时还要考虑到线程规模的大小。如果线程规模太大，意味着线程中可能会有更 多的访存操作带来更高的遭遇依赖关系违背的概率，当发生退回时也就需要更长的启动时间。另外，用于判断线程间数据依赖关系所使用的缓冲区的大小也是有限 的，并不能够容纳过大的线程。同时，由于线程的创建和撤销都需要一定的开销，如果线程规模过小，那么这些额外的开销会占据较高的比例，造成性能损失。第三，优化资源利用率。程序编译后的代码规模在任何时候都是越精简越好，这有助于减少对存储资源的占用，同时有利于发挥程序局部性的优势。优化资源利用率 在将来的第三代CMP处理器架构中显得尤其重要。在第三代架构中，每个处理器核中可能同时执行着多个线程（比如SMT技术），这些线程虽然各自拥有自己的 寄存器文件，但是它们需要共享算术逻辑运算部件等资源。尽量减少线程间对资源利用的冲突也是编译器的主要工作。第四，针对不同类型的程序做相应并行性挖掘。在实践中我们可以发现，并非所有的应用程序都蕴含着充足的线程资源。比如，通常的整数应用程序就只有极少数的 指令级并行性可供挖掘，同时完全没有线程级并行的可能；桌面/服务器环境下的多媒体应用则具有天生的指令级和线程级并行性，同时又由于算法实现为计算密集 型，所以还有一定的存储需求；用于科学计算的浮点应用程序中有大量的循环级并行存在，同时对存储带宽的需求也很高，针对那些本身不具备充足线程级并行潜力 的应用程序，编译器可以适当调整策略充分利用传统的优化方法进行处理。针对那些具有大量线程并行性可供挖掘的程序，在挖掘程序线程级并行的同时，还要关注 进行各线程内部的指令级并行性的挖掘，以进一步提高性能。编译系统对于应用程序能够高性能执行有着不可替代的重要作用。线程级并行性的开发研究当前还处于起步阶段，各项技术还远没有成熟。伴随着新一代处理器普及速度的加快，编译技术无