超大规模处理器性能的高级推测与数学信息通信技术

博士学位论文L’UNIVERSITÉ DE RENNES第601章第一次见面数学与信息与通信科学与技术通过"Kleovoulos Kalaitzidis"提高超大规模处理器性能的高级推测论文于2020年3月6日在雷恩提交并答辩研究单位：Inria Rennes-Bretagne Atlantique论文编号：答辩前的报告员：Pascal Sainrat图卢兹保罗萨巴蒂尔大学教授Smail Niar教授，上法兰西理工大学，巴伦西亚评审团组成：主席：Sebastien Pillement，南特考官：Alain Ketterlin斯特拉斯堡路易斯巴斯德大学讲师Angeliki Kritikakou雷恩第一大学讲师Dir.论文作者：André Seznec，Inria/IRISA雷恩献给我心爱的父母，我一生的灵感计算机理论家发明了解决重要问题的算法，并分析它们的渐近行为（例如O（NlogN））计算机架构师设置了这些算法的常数因子。克里斯托斯·科齐拉基斯7C座桥中的T座论文11摘要导言171现代通用处理器1.1处理器体系结构基础251.1.1一般定义251.1.2指令集体系结构- ISA251.1.3指令格式261.1.4建筑状态271.2简单管道271.2.1关键想法271.2.2第29阶段分解1.2.2.1获取指令- IF301.2.2.2指令解码- ID301.2.2.3执行- EX301.2.2.4内存- M311.2.2.5回写- WB321.2.3限制33.1.2.3.1危害控制331.2.3.2数据风险341.3关键管道开发351.3.1分支预测351.3.2超大规模流水线351.4无序执行371.4.1基本理念371.4.2管道的有序方面381.4.2.1注册表重命名- REN381.4.2.2调度提交指令- DIS/COM401.4.3无序执行引擎401.4.3.1问题、执行和回写401.4.3.2内存指令的操作4281.4.4轮廓452关于无序超大规模处理器2.1导言472.2价值预测482.2.1关键想法482.2.2持续的挑战492.2.2.1可预测值模式2.2.2.2覆盖范围增加502.2.3现实实施的原则512.2.4主预测模型522.2.4.1基于上下文的预测器522.2.4.2基于计算的预测器572.2.4.3混合预测器592.3地址预测602.3.1可能使用案例概述602.3.2通过负载地址预测进行数据推测612.3.2.1预测方案612.3.2.2关键设计方面623论价值预测与ISA水平内在的3.1导言653.2基本ISA属性对价值预测有意义663.2.1 x86_64663.2.1.1主要数据操作类型673.2.1.2基本程序执行寄存器673.2.1.3指令类683.2.2Aarch64703.2.2.1支持的数据类型713.2.2.2注册&指令类713.3所研究的ISA中的价值预测733.3.1ISA感知的价值可预测指令3.3.2从预测结果753.3.3使用多个目的地寄存器753.4实验装置763.4.1模拟器763.4.2价值预测设置773.4.2.1本研究考虑的预测因素77内容表93.4.2.2价值预测器操作783.4.2.3模拟标志的793.4.3Inter-ISA可比模拟的793.5模拟结果813.5.1ISA对价值可预测性的影响813.5.2根据ISA83分析价值预测影响3.5.3矢量优化的影响863.6结论874介绍价值预测的二进制方面：VSEP894.1引言动机894.2通过平等预测进行价值投机- VSEP914.2.1使用ETAGE92进行价值预测4.2.1.1预测924.2.1.2培训924.2.1.3管道详细信息934.2.2剖析VSEP94的预测情景4.3评价方法964.3.1检查的预测因子964.3.2基准964.3.3模拟器974.4实验结果和分析984.4.1VSEP与VTAGE和LVP984.4.1.1性能分析984.4.1.2覆盖率分析1014.4.2VSEP与VTAGE103的组合4.5结论1045通过负载地址预测从5.1引言动机1075.2使用混合VSEP/VTAGE进行负载地址预测5.3负载地址预测的使用案例1105.4早期加载执行1115.4.1早期加载执行的1115.4.1.1推测性内存访问1115.4.1.2延迟地址生成&执行验证1125.4.2备忘录问题1145.4.2.1早期加载执行114105.4.2.2早期记忆依赖推测1145.4.2.3记忆消歧的保证1175.4.3缓存端口争用1185.4.4早期内存访问引擎1185.4.4.1早期存储器请求1185.4.4.2投机价值的传播1195.5微体系结构概述1205.6评估方法1225.6.1模拟器1225.6.2基准1225.7实验结果和分析1225.7.1性能分析1235.7.1.1加速1235.7.1.2违反记忆令1245.7.1.3现有潜力和局限性1255.7.2与负载值预测相关的1275.7.2.1负载地址与负载值验证1275.7.2.2早期加载执行与预测加载值1285.8结论130结论133参考书目137图145列表出版物列表14711他的复活在现代数字化时代，几乎所有的东西都由计算机处理，对计算的需求不断增长。因此，无论设计多么复杂，处理器都必须不断提高性能。因此，尽管现代多功能处理器已经提供了高性能，但在执行延迟和功耗方面仍有持续改进的需求。实际上，这两个问题代表了处理器架构中的两个持续挑战为此，在晶体管水平上起作用的电路设计者试图提供优化，其通常旨在缩短电关键路径以更快地传输信息。另一方面，处理器架构师在更高级别上操作，该级别始终接近逻辑门电路。架构师的责任是定义处理器的组织，包括对其每个组件的描述。为了实现这些性能目标，架构师可以设计新的组件，从传统设计中删除其他组件，或修改其功能和连接，同时确保所有不同处理单元之间的高效编排。然而，他们仍然需要了解当前的电路技术，以便提供脚踏实地的解决方案，即可以在真正的硅上实现的设计。换句话说，计算机架构师可以被认为是传统的架构师，他们根据最先进的设计技术来设计他们的设计，以便制造商（即自从特别地，当前的通用处理器具有数亿到数十亿个晶体管。显然，更多的晶体管（处理器的构建块）意味着更多的单元可用于处理程序指令，并且自然地可以导致更高的处理速度。处理器中晶体管数量的增加已经被摩尔定律所观察到，该定律指出"芯片上的晶体管数量将每两年翻一番" [Moo98]。这意味着虽然论文摘要12在数学领域，摩尔定律40多年来一直被证明是这一趋势的一个相当准确的指标。然而，自2001年左右以来，此外，随着越来越复杂的处理器被设计和制造到纳米级的公差处理器的时钟周期性地触发，并定义完成特定计算步骤所需的最短时间。因此，通过增加时钟频率，可以在一定的时间间隔内完成更多的任务。时钟频率与电路中的晶体管能够可靠地打开和关闭的速度有关。随着晶体管的缩小，它们的开关速度以逆定律增加，这使得高频然而，CPU频率本身受到芯片峰值功率限制的限制，也称为功率墙[Bos11]。因此，时钟速度尽管如此，处理器中大量的晶体管使得这些技术通过并行化指令执行来提高单核处理器的性能，即虽然到目前为止，这些机制一直是处理器架构的支柱，但要继续以晶体管数量增加的速度提高顺序性能已经变得非常困难。因此，为了支持2001年，IBM推出了POWER4[War+02]，这是世界上第一款多处理器芯片。2005年左右，英特尔的奔腾D如今在多核处理器中，可以加快程序的整体执行速度 通过将其划分为在不同内核中同时运行的几个较小的程序。这种"服务器思维"提高了吞吐量方面的性能论文摘要13（即，在给定的时间单位内可以处理更多的工作），这与以执行延迟（即，更快地完成特定任务）为目标的单处理器相反。然而，多核处理器的性能受到程序性质的限制，因为并行计算不能应用于必须按顺序处理的算法组件。换句话说，一些程序本质上是顺序的，根本不能并行，而另一些程序可能有很长的顺序部分，只能部分并行。最后，正如Amdahl定律[ Amd67 ]所建议的换句话说，如果我们可以将程序分为并行部分和顺序部分，那么，假设有无限多个内核同时执行并行部分，总加速将受到顺序元素执行的例如，如果一个应用程序需要4个小时的计算时间，而其中只有2个小时2. 因此，即使在今天的高性能处理器内核使用推测性的技术，这些技术依赖于对程序行为的经验观察，以便在程序执行时变得"更智能"。使用这些技术的主要动机是，在大多数情况下，普通程序的行为不是随机的。相反，它们倾向于在指令流和操作结果中表现出一定的规律性。因此，通过隔离这些重复的程序行为，可以设计能够猜测与程序相关的执行信息的自动机。这些方面可以通过考虑两种广泛使用的推测技术来最好地理解，这两种技术被程序行为所强化：分支预测和内存依赖性预测。分支预测利用在程序倾向于遵循的控制流路径中发现的规律性，而存储器依赖性预测依赖于在存储器读取和存储指令之间的交互中发现的规律性。几乎所有现代高性能内核都使用这两种技术来促进内核中的指令流另一个更高级的推测级别利用了程序生成的原始数据或特定数据来源的内存地址的潜在这种类型的两种主要技术是值预测（VP）和存储器读取的地址预测论文摘要14预测）。VP和LAP是两种发展中的、非常有前途的数据规范化技术，因为它们仍然为探索和优化提供了很大的潜力VP通过允许"消费者"在执行它们各自的"生产者"之前推测性地启动它们的执行，打破了指令之间的真正数据依赖关系。VP是由同一静态指令的不同动态实例产生通常遵循可预测模式的结果这一事实实现的。因此，可以使用硬件结构来遵循这些指令并预测它们的结果。当一条指令被预测时，依赖于它的指令可以使用预测的值同时执行，而不必阻塞。因此，当预测正确时，总执行时间会减少。否则，必须执行某些恢复操作，以确保使用正确的输入重新执行相关语句。L’essentiel est que les performances séquen- tiellesLAP与VP非常相似; LAP机制不是预测内存读取的结果，而是预测内存读取指令从中获取数据的内存地址。这些机制基于这样的观察，即存储器对存储器读取的存储器地址的预测该值与VP一样，内存读取的推测值被传播到相关指令，并允许它们因此，LAP启动类似形式总的来说，这两种推测技术都在共同的目标下，我们对本文的主要贡献如下。首先，我们执行值预测的指令集间探索（或ISA）。自从第一次引入价值预测以来，已经有过多的不同预测器声称独立于ISA具有特定的改进。然而，由于VP技术本质上依赖于程序代码的性质和行为，因此检测ISA的特性和值预测之间的相互作用是至关重要的在我们的研究中，我们仔细比较了在为x86_64和Aarch64 ISA对称编译的应用程序二进制文件中使用VP所带来的加速。事实上，我们的探索表明，ISA的一些特性论文摘要15这可以通过VP来实现。此外，由于值预测器传统上假定64位输入来跟踪执行，因此不覆盖产生至少128位值的向量指令，即不跟踪或预测。具体地，向量指令的预测可以导致相当大的预测器，因为它需要根据要预测的值的最大长度来扩展输入的长度（例如，每个输入128位以覆盖128位指令）。在这方面，在我们对ISA水平的探索中其次，我们发现了一个未探索的值模式，即等间隔，然而，它表征了相当大比例的指令（平均超过18%）。这样的值模式不能被先前提出的预测器有效地捕获，先前提出的预测器通常在相同的输入中保留被跟踪的值（即，将潜在地用于预测）及其对预测的置信度。为了克服这一限制，我们引入了VSEP预测器，它基于二元决策方案，并强烈地将值与它们的预测置信度分离。VSEP实现了与先前提出的VTAGE [PS14b]相同范围内的加速度，但利用了先前未捕获的值模式。换句话说，VSEP通过显著增加暴露相等间隔的预测指令的分数（平均多15%）来有效地补充执行VP的既定方式。基本上，当与VTAGE结合使用时，VSEP将获得的加速度平均提高了19%。此外，使用VSEP，我们可以在相同的存储预算下，使用大约58%的输入（VSEP中的3K个价值输入与VTAGE中的7K个价值输入），实现与最先进的VTAGE相当的性能。以这种方式，VSEP可以显著降低考虑对大于64位的值进行值预测第三，也是最后一点，我们提出了一种基于LAP的机制，即LAPELE，它在内核的无序部分之前进行预期的内存读取。为此，我们将混合VSEP/VTAGE预测器的目标更改为执行LAP。有了这样一个预测器，我们可以预测48%的内存读取的内存地址。平均而言。为了防止可能的内存顺序破坏爆发，我们建议使用一个小规模的辅助预测器来"过滤"显示内存冲突的内存读取。最后，使用该方案，我们可以通过完全将它们从内核的无序部分中取出，提前执行平均32%的已验证内存读取指令。从性能的角度来看，LAPELE的平均加速度与设置为仅推测内存读取值的相同大小的值预测器的平均加速度范围相同事实上，论文摘要16基于LAP的机制不能始终达到或超过一般值预测的性能。然而，通过LAPELE，我们将证明LAP可以成为未来复杂性高效的大窗口架构的必要催化剂，以容忍内存延迟17一、引言在他1937年的论文中，计算机科学之父艾伦·图灵（Alan Turing）指出："发明一台可以用来计算任何可计算序列的单一机器是可能的。图灵机（英语：Turing Machine）是一种数学模型，它定义了一种能够实现任何给定计算机算法的抽象机器。在自动机理论中，抽象机是计算系统的理论模型或规范。在计算机科学领域，这种抽象简单地表示处理单元的模型。图灵原理被认为是处理计算机内部所有计算的中央处理单元（CPU）的一般例子。传统上，术语"CPU"指的是处理器，将其与外部组件（如主内存）区分开来。从本质上讲，计算机被设计用于处理、存储和检索数据。处理器被恰当地称为计算机的"大脑"，因为它们启用了由计算机程序指定的所有基本算术、逻辑、控制和输入/输出（I/O）操作因此，它们基本上设置了计算机处理能力的极限，并且被合理地认为是计算机科学的基石。图像处理、生物信息学、机器学习和人工智能是计算机科学的几个方面，如果没有具有足够高计算能力的机器，这些方面就根本不此外，CPUs的小型化和标准化已经增加了数字设备在现代生活中的存在，远远超出了专用计算机器的有限应用现代微处理器出现在电子设备中，从汽车到手机，从家用电器到关键医疗设备。因此，处理器体系结构被认为是最重要的硬件设计类型之一。"建筑"一词通常指建筑物的设计和建造类似地，在计算世界中，计算机体系结构分别描述计算机系统的设计。更具体地说，处理器芯片的体系结构（称为微体系结构）是对其基本组件、其功能和互连的详细描述，以及它们可以执行的操作。所有这些不同的特性都由处理器支持的指令来充分表达，这些指令共同代表处理器的指令集体系结构（ISA）。不同的处理器系列，如英特尔、IBM、PowerPC和ARM，可以使用不同类别的ISA。因此，由编译器以特定类型的ISA构造的程序不能在不具有相同ISA的机器上执行。另一方面，单个ISA可以由在ISA级别保持兼容的不同处理器模型来实现例如，流行18简介许多家庭，如x86，都有多个制造商提供的处理器。换句话说，ISA在编译器编写者和处理器设计者之间提供了一种概念上的抽象，编译器编写者只需要知道可用的机器指令及其编码，处理器设计者构建执行这些指令的机器。总的来说，ISA与微体系结构一起形成了所谓的计算机体系结构。从微观角度来看，晶体管是典型微处理器芯片的原子部分，就像砖块是建筑物的主要部件一样。晶体管以一定的方式排列，以形成能够携带所有基本二进制函数（如OR和AND）的电路。因此，这些函数的复杂组合可以提供启用更高级运算的设备，例如加法和乘法。仅考虑到设计这样的电路的高复杂性，人们就很容易推断出"构建"处理器的实际过程是多么令人在现代数字化时代，几乎所有的东西都是由计算机处理的，计算需求正处于上升轨道。为了在计算机科学研究和生活质量的提高中保持空间，处理器必须在不考虑设计复杂性的情况下保持性能的提高。因此，即使现代通用进程已经提供了高性能率，但在执行延迟和功耗方面仍需要不断改进。实际上，这代表了处理器体系结构的两个持续挑战。最终，在晶体管级别起作用的电路设计者试图提供优化，该优化通常旨在缩短用于快速信息传输的电关键路径。另一方面，计算机架构师在更高级别上操作，该级别仍然接近逻辑门电路。架构师的责任是提供处理器的蓝图，其中包括对其所有不同组件的描述。为了实现各自的性能目标，架构师可以设计新的组件，从主流模型中删除一些其他组件，或修改它们的功能和连接，始终将所有不同处理部分的有效编排放在一起。然而，他们必须始终了解当前的电路技术，以便提供脚踏实地的解决方案，即可以在真正的硅上实现的设计。换句话说，计算机架构师可以被认为是按照最先进的建筑原则进行设计的普通架构师，因此制造商（即电路设计师）可以将其付诸实践。自从1974年推出第一个广泛使用的计算机处理器英特尔8080以来，硬件制造商传统上一直在努力将越来越多的晶体管封装在成品硅表面上。特别是，当前的通用处理器具有数百万到数万亿个晶体管。显然，更多的晶体管（处理器构建块）意味着更多的单元可用于处理程序指令，并自然导致更高的专业知识。简介19停止速度。处理器芯片中晶体管数量的增加已经被摩尔定律实证地观察到，该定律指出"芯片上的晶体管数量将每2年翻一番这意味着大约每24个月一个晶体管的尺寸将是其当前尺寸的一半，因此在一个等尺寸的芯片中可以容纳两倍数量的晶体管。虽然摩尔定律不是数学意义上的定律，但它已经证明了然而，自2001年左右以来，随着晶体管收缩达到其极限，技术规模一直在放缓，摩尔定律此外，随着越来越复杂的CPUs被设计和制造到纳米级的容差，由于处理器时钟速度的提高，处理器性能已经提高。处理器的时钟周期性地滴答作响，并定义完成特定计算步骤所需的最短时间因此，通过增加时钟频率，可以在一定的时间间隔内完成时钟频率实际上类似于电路中的晶体管可以可靠地打开和关闭的速度。随着晶体管逐渐缩小，它们的开关速度也呈反比增加，允许出现高频处理器，目前范围从2GHz到5GHz。然而，CPU频率固有地受到芯片的峰值功率约束（也称为功率墙）的限制。因此，时钟速度已经停滞了十多年，因为，正如它所表明的，频率的急剧增加可能需要改变物理定律。处理器芯片中大量的晶体管使其成为可能一些新的设计方法，如流水线、超大规模和无序执行[AA93]，表明即使时钟频率稳定，处理器性能也会提高。这种技术通过并行化指令执行来提高单处理器或单处理器的性能，即顺序性能，这一特征通常被称为指令级并行化或ILP。尽管这些机制一直是处理器架构的主干，但随着晶体管数量的增长，要保持连续性能的提高变得非常困难。因此，为了保持性能的提高，芯片制造商和制造商采用了"分而治之"的原则，逐步转向多处理器或多核芯片的实施。2001年，IBM推出了POWER 4[War+02]，这是第一款在单个芯片上具有2核功能的商用多处理器芯片，随后在今天，高性能计算基本上是由2、4、8或更多内核组成的多核处理器实现的在多核处理器中，程序的总体执行可以通过将其划分为在不同内核中同时执行的几个较小的程序来加快。这种"服务器人员"提高了吞吐量方面的性能（即，可以在内部处理更多工作简介20给定的时间单位），与以执行延迟为目标的单处理器（即，快速完成特定任务）。然而，多核处理器的性能受到程序性质的限制，因为并行计算不能应用于需要按顺序处理的算法组件。换句话说，一些程序本质上是顺序的，它们不可能完全并行，而另一些程序可能有很长的顺序部分，它们只能部分并行。最终，正如Amdahl换句话说，如果一个程序可以被分成并行部分和顺序部分，那么，通过假设无限多个内核同时执行并行部分，总的速度将受到顺序元素的执行的限制。例如，如果一个应用程序需要4个小时的计算时间，并且其中只有2个小时可以并行化，则最终执行时间可以减少到最多2个小时。因此，很明显，即使在多核时代，提高单核速度也是实现高性能计算的先决条件[HM08]。当前的前沿处理器内核采用推测性技术，依赖于对程序行为的经验观察，以便有效地"智能"程序执行。作为这些技术的激励因素的主要观察结果是，普通程序在很大程度上并不具有随机性。相反，他们倾向于在其业务的流程和产品中表现出一定的规律性。因此，通过分离这些程序特性，存在能够猜测与程序相关的执行信息的货币自动机的能力。通过考虑由程序行为支持的两种广泛使用的推测技术，可以更好地理解这些方面：分支预测和内存依赖性预测。分支预测利用程序倾向于遵循的控制流路径中发现的规律性，而内存依赖性预测依赖于加载和存储指令之间的交互中发现的规律性。几乎所有现代高性能内核都使用这两种技术来促进内核中的指令流（分别为获取和调度），从而提高顺序性能。另一个更高级的推测水平利用了程序生成的原始数据或特定数据来源的内存地址的潜在规律性。这类技术中的两种主要技术是值预测（VP）和负载地址预测（LAP）。VP和LAP都是开发中的、前景广阔的数据推测技术，因为它们仍然具有大量的探索和优化空间。在这方面，本文提出了一些基于值和负载地址预测的推测性机制，以有效地提高当代通用处理器的顺序性能。这些机制建立在单核处理器架构之上，并且完全独立于多核设计所利用的高级并行性。因此，它们可以被不同的核心所采用。