小土刀

【计算机系统导论】3.3 并行与并发

人们对性能的追求永无止境,从最初的流水线、到超标量处理器和多核处理器,都是为了让我们的计算更快更强。这背后的思路其实很简单,就是对于并发和并行的充分利用,本节我们就来一探究竟。


  • 数据冒险(转发与阻塞)
  • 控制冒险(假定分支不发生、缩短分支的延迟、动态分支预测)
  • 超标量与超级流水线的对比
  • 设计考虑(指令级并行性和机器并行性、指令发射策略、寄存器重命名、分支预测、超标量执行、超标量实现)
  • 并行和高级指令级并行(静态多发射处理器、动态多发射处理器)
  • Pentium 4(前端、乱序执行逻辑、整数和浮点执行单元)

先介绍基本的概念逻辑

通常,处理一条指令包括很多操作。将它们组织成某个特殊的阶段序列,即使指令的动作差异很大,但所有的指令都循序统一的序列。每一步的具体处理取决于正在执行的指令。创建这样一个框架,我们便能够设计一个能充分利用硬件的处理器。下面是关于各个阶段以及各阶段内执行操作的简略描述:

  • 取指(fetch):取值阶段从存储器读取指令字节,地址为程序计数器 PC 的值。
  • 译码(decode):译码阶段从寄存器文件读入最多两个操作数
  • 执行(execute):在执行阶段,ALU 要么执行指令明确的操作,计算存储器引用的有效地址,要么增加或减少栈指针。对一条跳转指令来说,这个阶段会检验条件码和分支条件,看看是否应该选择分支
  • 访存(memory):访存阶段可以将数据写入存储器,或者从存储器读出数据。
  • 写回(write back):写回阶段最多可以写两个结果到寄存器文件
  • 更新 PC(PC update):将 PC 设置成下一条指令的地址

然后引入流水线

流水线增加了同时执行的指令数目以及指令开始和结束的速率。流水线并不能够减少单一指令的执行时间,也称为延迟。对流水线的设计者来说,指令集既可能将事物简单化,也可能将事物复杂化。流水线设计者必须解决结构冒险、控制冒险和数据冒险。而分支预测、转发和阻塞机制能够在保证得到正确结果的前提下提高计算机的性能。

流水线和多发射都提高了指令的吞吐率并致力于开发指令级并行。然而,由于处理器有时必须等待依赖关系明确后才能继续工作,所以程序中的数据相关和控制相关往往限制了可达性能的上限。基于软件的指令级并行开发主要依赖于编译器来寻找依赖关系并尽量减少这些依赖关系可能造成的不良后果。基于硬件的指令级并行开发主要依赖于流水线和多发射机制。推测执行可以由硬件或编译器完成,它可以增加指令行并行。但是使用时必须小心,因为错误的推测可能会降低性能。

除了存储系统以外,流水线的有效运作是决定处理器 CPI 乃至性能最终要的因素。结构冒险、数据冒险和控制冒险在简单流水线处理器和更复杂的流水线处理器中都是非常重要的,对现代流水线而言,结构冒险常出现在浮点单元附近,浮点单元是一个几乎不可能完全流水的地方。与之相比,控制冒险一般出现在整数程序中,因为其中分支出现的概率更高,也更难预测。数据冒险在整数和浮点程序中都可能成为性能平静。一般来说浮点程序中的数据冒险更容易处理,因为低的分支出现频率和规则的存储器存取使得编译器有更大的空间调度指令以避免冒险。与之相比,在整数程序中涉及大量的指针,存储器的存取更不规则,做这样的优化就要困难一些。有很多编译器和基于硬件的技术通过调度来减少数据间的依赖。

通过动态多发射和推测执行开发指令级并行的负面问题是功耗效率。每项发明都成功将更多的晶体管转化为性能,但是这种转化往往极其缺乏效率。因为功耗墙的原因,最新的处理器是单片多核式的,而非前辈的深流水线或贪婪式推测。尽管简单的处理器没有复杂的处理器那么快,但是在同样的功耗下却能得到更高的性能。所以当设计的约束更多来自功耗而非晶体管数量时,简单的处理器能在单芯片上获得更高的性能。

流水线的细节

流水线化的一个重要特性就是增加了系统的吞吐量(throughput),也就是单位时间内服务的顾客总数,不过它也会轻微地增加延迟(latency),也就是服务一个用户所需要的时间。

流水线的局限性

  • 不一致的划分
    • 运行时钟的速率是由最慢阶段的延迟限制的(木桶理论)
    • 对硬件设计者来说,将系统计算设计划分成一组具有相同延迟的阶段是一个严峻的挑战。通常,处理器中的某些硬件单元,如 ALU 和存储器,是不能被划分成多个延迟较小的单元的。这就使得创建一组平衡的阶段非常困难。
  • 流水线过深,收益反而下降

然后介绍为了提高指令效率所采用的各种策略

比如超标量,多发射等等,然后介绍各种关键算法,如 tomasolu 等等


处理器包括用户可见的寄存器和控制/状态寄存器。用户可见寄存器是指,用户使用机器指令显式或隐式可访问的寄存器。它们可以是通用寄存器,也可以是用于定点或浮点数、地址、变址和段指针这样的专用寄存器。控制和状态寄存器用于控制 CPU 的操作。一个明显的例子是程序计数器。另一重要的例子是程序状态字(PSW),它包含各种状态和条件位,例如反映最近一次算术运算结果的标志位、中断允许位和指示 CPU 当前运行于特权模式下还是用户模式下的状态位。

处理器采用指令流水方式来加速指令的执行。从本质上讲,流水是将指令周期分解成几个连续出现的阶段,如取指令、译码指令、确定操作数地址、取操作数、执行指令和写结果操作数。指令向前移动通过这些段,就像车间的一条装配线一样;于是,不同的指令能同时在各个段上工作。不过,转移和指令间相关性的出现,使流水线的设计和使用变得复杂了。

依然是围绕这一幅图来进行说明

并行与并发的区别

话题

  • 流水线
  • 冒险
  • 按序/乱序执行
  • 预测执行
  • 寄存器重命名

分支预测

研究表明,使用总是选择(always taken)分支的预测策略的成功率大约是 60%,相反,从不选择(never taken, NT) 策略的成功率大约为 40%。稍微复杂一点的是反向选择、正向不选择(backward taken, forward not-taken, BTFNT)的策略,当分支地址比下一条呆滞低时就预测选择分支,而分支地址比较高时,就预测不选择分支。这种策略的成功率大约为 65%。这种改进源自于一个事实,即循环是由后想分支结束的,而循环通常会执行多次。前向分支用于条件操作,而这种选择的可能性较小。

分支预测及对应算法

既然编译器可以根据数据依赖关系调度代码,为什么还需要超标量处理器来进行动态调度呢?有三个原因。1)不是所有的阻塞都可以事先知道的。尤其是 cache 缺失会导致不可预测的阻塞。动态调度使得处理器可以调度并执行其他无关的指令以掩盖阻塞。2)如果处理器采用动态分支预测推测分支结果,那么由于这些信息依赖于预测和分支指令的真实情况,编译器无法得知指令的精确顺序。采用动态推测而不是动态调度,会极大地限制可开发的指令级并行度(ILP)。3)由于流水线延时和发射宽度根据处理器的具体实现的不同有很大而差别,所以最佳的编译代码顺序也并不固定。例如,调度一个相互依赖的指令序列的具体方式与发射宽度和延时存在着密切关系。流水线的结果同样会影响循环展开的尝试,才能避免可能的阻塞。它还回影响编译器进行寄存器重命名的过程。动态调度使得硬件将这些细节隐藏起来。因此,用户和软件发行商就不用针对同一指令集的不同处理器发行相应的软件了。同样的,以前的代码也能从更新的处理器上获得好处而不用重新编译。

编译器经常创建一些在编程语言中没出现过的分支和标签。避免显式编写这些标签和分支是使用高级编程语言的好处之一,也是其编码速度块的一个原因。

以分支指令结束的这类指令序列对编译非常重要,因此它们有对应的专用术语:基本块。基本块是没有分支(可能出现在末尾者除外)并且没有分支目标/分支标签(可能出现在开始者除外)的指令序列。编译最初阶段的任务之一就是将程序分解为若干基本块。

虽然在 C 或 Java 这样的编程语言中有许多分支判断和循环语句,但是在指令集这一层次实现其功能的基本语句是条件分支。

和算术运算一样,对取数指令来说有符号位和无符号位是有区别的。取回有符号数后需要使用符号位填充寄存器的所有剩余位,称为符号扩展,但其目的是在寄存器中放入数字正确的表示方式。

编译器或汇编程序必须把大的常数分解为若干小的常数然后再合并到一个寄存器中。

大多数条件分支都转移到一个附近的位置,但有时也会转移很远,距离超过位数可能表示的范围。汇编器的解决方法就像处理对大地址或大常数的方法一样:插入一个跳转到分支目标的无条件跳转,并将条件取反以便由分支决定是否跳过该无条件跳转指令。

流水线冒险

数据冒险

并行层次

  • 位级并行
  • 指令集并行(标量、超标量)
  • 数据并行
  • 任务并行

超标量

超标量处理器是一种使用多条相互独立的指令流水线的处理器。每条流水线由多个段(stage)组成,因此每条流水线能同时处理多条指令。多流水线引入了新一级并行性,允许同时处理多个指令流。超标量处理器利用了所谓的指令级并行性(instruction-level parallelism),指令级并行性指的是程序中的指令可以并行执行。

超标量处理器一次取多条指令,然后试图找出几条彼此不相关因而能够并行执行的指令。如果一条指令的输入取决于前面指令的输出,则这条指令不能同时,更不能先于前面指令完成执行。一旦这种相关性被确认,处理器可以以不同于原来代码的顺序发射和完成指令。

通过使用更多的寄存器,或对原代码中的寄存器引用换名,处理器可取消某些不必要的相关性

纯 RISC 处理器经常使用延迟分支来最大限度地利用指令流水线,然而,这种方法不太适用于超标量处理器,大多数超标量机器使用了传统的分支预测法来提高流水线效率。

超标量实现的处理器结构是指,在这样的结构中,包括整数和浮点运算、装载、保存以及条件分支之类的普通指令,能通水启动并独立执行。这种实现引出了涉及指令流水线的几个复杂问题。

超标量设计紧跟 RISC 体系结构的脚步。虽然 RISC 机器的精简指令集体系结构自身已倾向于应用超标量技术,但超标量方法既能用于 RISC 也能用于 CISC 体系结构。

线程

  • 多线程
  • 同步多线程
  • 超线程

多线程

Temporal Simultaneous Preemptive Cooperative

多线程 https://zh.wikipedia.org/wiki/%E5%A4%9A%E7%BA%BF%E7%A8%8B

多线程(英语:multithreading),是指从软件或者硬件上实现多个线程并发执行的技术。具有多线程能力的计算机因有硬件支持而能够在同一时间执行多于一个执行绪,进而提升整体处理性能。具有这种能力的系统包括对称多处理机、多核心处理器以及芯片级多处理(Chip-level multithreading)或同时多线程(Simultaneous multithreading)处理器。
软件多线程。即便处理器只能运行一个线程,操作系统也可以通过快速的在不同线程之间进行切换,由于时间间隔很小,来给用户造成一种多个线程同时运行的假象。这样的程序运行机制被称为软件多线程。如微软的Windows作业系统和Linux就是在各个不同的执行绪间来回切换,被称为单人多任务作业系统。而DOS这类文字接口作业系统在一个时间只能处理一项工作,被视为单人单工作业系统。
除此之外,许多系统及处理器也支持硬件多线程技术。对称多处理机(SMP)系统具有多个处理器,所以具有真正的同时执行多个线程的能力;CMP技术通过在一块芯片上集成多个核心(Core)也具有真正的多线程能力;CMT技术则稍有不同,有的是依靠硬件执行线程切换来获得多线程能力,操作系统不再负责线程切换,因而这部分开销可以减少甚至消除,这方面典型的例子是Sun的UltraSPARC T1,它同时综合了CMP和CMT。微软的Windows 2000以后的操作系统皆支持多线程与超线程技术。
目录 [隐藏]
1 概观
2 粗粒度交替多线程
2.1 概念
2.2 硬件成本
2.3 示例
3 细粒度交替式多线程
3.1 概念
3.2 硬件成本
3.3 示例
4 同步多线程
4.1 概念
4.2 硬件成本
4.3 示例
5 实现
6 参见
7 外部链接
概观[编辑]
由于程序代码中存在的数据及控制依赖关系,单线程中所能发掘的指令并行潜力是有限的。为了发掘有限的指令级并行潜力而一味强化乱序执行和分支预测,以至于处理器复杂度和功耗急剧上升,有时候是得不偿失的。因此,现代微处理器多采用硬件多线程技术来发掘线程之间的线程级并行潜力。这样子允许在接口转换的专业领域之运算能力大幅提升:
既使这样做对于提升单一程序或是线程的性能相当困难,但是目前多数的系统都是使用多任务的方式作业。
能够明显的提升整体系统运算能力,总体吞吐量获得提升。
有两种提升运算能力的主要技术分别是多进程与多线程。
不过有些对多线程的批评如下:
当共享硬件资源(像是缓存或是TLB)时多线程会造成干预。
单线程的运行时间可能不会因为多线程而变短。硬件侦测技术有可能改变这一状况。
多线程的硬件支持会牵涉到软件支持,如此程序与操作系统就需要比多过程化更大幅度的修改。
粗粒度交替多线程[编辑]
概念[编辑]
一个线程持续运行,直到该线程被一个事件挡住而制造出长时间的延迟(可能是内存load/store操作,或者程序分支操作)。该延迟通常是因缓存失败而从核心外的内存读写,而这动作会使用到几百个CPU周期才能将数据回传。与其要等待延迟的时间,线程化处理器会切换运行到另一个已就绪的线程。只要当之前线程中的数据送达后,上一个线程就会变成已就绪的线程。这种方法来自各个线程的指令交替执行,可以有效的掩盖内存访问时延,填补流水线空洞。
举例来说:
周期 i :接收线程 A 的指令 j
周期 i+1:接收线程 A 的指令 j+1
周期 i+2:接收线程 A 的指令 j+2,而这指令缓存失败
周期 i+3:线程调度器介入,切换到线程 B
周期 i+4:接收线程 B 的指令 k
周期 i+5:接收线程 B 的指令 k+1
在概念上,它与即时操作系统中使用的合作式多任务类似,在该任务需要为一个事件等待一段时间的时候会主动放弃运行时段。
硬件成本[编辑]
此种多线程硬件支持的目标,是允许在挡住的线程与已就绪的线程中快速切换。为了要达成这个目标,硬件成本将复制程序看得见的寄存器与一些处理器控制寄存器(像是程序计算器)。从一个线程切换到另一个线程对硬件来讲意谓著从一个寄存器复制到另一个。
这些新增功能的硬件有这些优势:
线程切换能够在一个 CPU 周期内完成(实际上可以没有开销,上个周期在运行线程A,下个周期就已在运行线程B)。
这样子看起来像是每个线程是独自运行的,没有其他线程与目前共享硬件资源。对操作系统来说,通常每个虚拟线程都被视做一个处理器。这样就不需要很大的软件变更(像是特别写支持多线程的操作系统)。
为了要在各个现行中的线程有效率的切换,每个现行中的线程需要有自己的暂存设置(register set)。像是为了能在两个线程中快速切换,硬件的寄存器需要两次例示(instantiated)。
示例[编辑]
许多微控制器与嵌入式处理器有多重的寄存器列,就能够在中断时快速环境切换。这样架构可以视为程序的线程与中断线程之间的块状多线程处理。
细粒度交替式多线程[编辑]
参见:桶形处理器
概念[编辑]
另一种更高性能的多线程做法是将所有 CPU 周期轮流切换至不同的线程,来自各线程的指令按顺序交替执行。执行过程很像桶形处理器(Barrel Processor)就像这样:
周期 i :接收线程 A 的一个指令
周期 i+1:接收线程 B 的一个指令
周期 i+2:接收线程 C 的一个指令
这种线程的效果是会将所有从运行管线中的数据从属(data dependency)关系移除掉。因为每个线程是相对独立,管线中的一个指令层次结构需要从已跑完管线中的较旧指令代入输出的机会就相对的变小了。
而在概念上,这种多线程与操作系统的核心先占多任务(pre-exemptive multitasking)相似。
硬件成本[编辑]
除了讨论块状多线程的硬件成本,交错式多线程也因每层管线需要追踪运行中指令的线程代码而增加硬件成本。而且,当越来越多的线程同时在管线中运行,像是缓存与 TLB 等共享资源也要加大来避免不同线程之间的冲突。
示例[编辑]
Denelcor Heterogeneous Element 处理器 (HEP)
Intel Super-threading
昇阳 UltraSPARC T1
Lexra NetVortex
搭载 Multi-Threaded ASE 的 MIPS 34K 核心
Raza Microelectronics Inc XLR
同步多线程[编辑]
参见:同步多线程
概念[编辑]
目前最先进的多线程技术是应用在超标量处理器上。超标量处理器内在每个CPU周期中,单独一个线程会发布众多的指令。套用同步多线程(SMT)之后,超标量处理器就可以在每个CPU周期中,从多个线程中发布指令。辨识到任何一个单一线程拥有有限数量的指令平行处理,这种类型的多线程是试着利用并行的方式跨越多线程,以减少浪费与闲置的资源。 举例来说:
周期 i:线程 A 的 j 指令 与 j+1 指令,还有 B 线程的指令 k 同时发布
周期 i+1:线程 A 的 j+2 指令、线程 B 的 k+1指令,与线程 C 的 m 指令同时发布
周期 i+2:线程 A 的 j+3 指令,与线程 C 的 m+1 与 m+2 指令同时发布
硬件成本[编辑]
交错式多线程如果不计硬件成本,SMT在每个管线层次结构的追踪线程指令会有多余的花费。而且,像是缓存与TLB这类共享的资源可能会因为多出来的线程而变得更大。
示例[编辑]
Alpha AXP EV8 (未完成)
Intel 超线程
IBM Power5
Cell 微处理器 内的 Power 运算对象件
昇阳 UltraSPARC T2
昇阳 Rock微处理器
AMD Bulldozer
实现[编辑]
在大多数研究领域内是要求线程调度器要能够快速选择其中一个已就绪线程去运行,而不是一个一个运行而降低效率。所以要让调度器去分辨线程的优先级是很重要的。而线程调度器可能是以硬件、软件,或是软硬件并存的形式存在。
而另一个研究领域则是要研究何种事件(缓存失败、内部运行续连系、使用DMA等)会造成线程切换。
如果多线程的方案会复制所有软件可见的状态,包括特许的控制登录、TLB 等,那就能够让虚拟机去创造各式线程。这样子就允许在相同的处理器中每个线程跑各自的操作系统。换句话说,如果只有存储了用户模式的状态,就能够让相同的裸晶大小的芯片在一段时间内处理更多的线程。

超线程

超线程技术在线程这个层面是否是真正的空间并行? https://www.zhihu.com/question/20277695

超线程 https://zh.wikipedia.org/wiki/%E8%B6%85%E5%9F%B7%E8%A1%8C%E7%B7%92

超线程(HT, Hyper-Threading)[1]是英特尔研发的一种技术,于2002年发布。超线程技术原先只应用于Xeon处理器中,当时称为“Super-Threading”。之后陆续应用在Pentium 4中,将技术主流化。早期代号为Jackson。
通过此技术,英特尔实现在一个实体CPU中,提供两个逻辑线程。之后的Pentium D纵使不支持超线程技术,但就集成了两个实体核心,所以仍会见到两个线程。超线程的未来发展,是提升处理器的逻辑线程。英特尔于2014年发布的Core i7-5960X便是将8核心的处理器,加上超线程技术,使之成为16个逻辑线程的产品。
英特尔表示,超线程技术让(P4)处理器增加5%的裸晶面积,就可以换来15%~30%的性能提升。但实际上,在某些程序或未对多线程编译的程序而言,超线程反而会降低性能。除此之外,超线程技术亦要操作系统的配合,普通支持多处理器技术的系统亦未必能充分发挥该技术。例如Windows 2000,英特尔并不鼓励用户在此系统中利用超线程。原先不支持多核心的Windows XP Home Edition却支持超线程技术。
目录 [隐藏]
1 运作方式
2 使用HT技术的CPU
3 顾虑
4 另见
5 脚注
6 外部链接
运作方式[编辑]
每个单位时间内,一个单运行管线的CPU只能处理一个线程(操作系统:thread),以这样的单位进行,如果想要在一单位时间内处理超过一个线程是不可能的,除非是有两个CPU的实体单元。双核心技术是将两个一样的CPU放置于一个封装内(或直接将两个CPU做成一个芯片),而英特尔的HT技术是在CPU内部仅复制必要的资源、让两个线程可同时运行;在一单位时间内处理两个线程的工作,模拟实体双核心、双线程运作。
Intel自Pentium开始引入超标量、乱序运行、大量的寄存器及寄存器重命名、多指令解码器、预测运行等特性;这些特性的原理是让CPU拥有大量资源,并可以预先运行及平行运行指令,以增加指令运行效率,可是在现实中这些资源经常闲置;为了有效利用这些资源,就干脆再增加一些资源来运行第二个线程,让这些闲置资源可运行另一个线程,而且CPU只要增加少数资源就可以模拟成两个线程运作。
使用HT技术的CPU[编辑]

编号SL6WK支持HT的P4 3.0G

虚拟的2个CPU在任务管理器中显示出都在运转
Pentium 4 CPU中,Northwood及其之后推出的版本自带超线程技术;但在早期的Northwood核心中,一些型号的HT技术被关闭,纵使有软件侦测到超线程技术的存在,用户并不可以激活;而双核心的Pentium D中也只有EE版提供HT技术。英特尔的Core 2 Duo处理器则没有HT技术。但处理器已集成了两个实体CPU核心,所以仍然支持两个线程。[2]
而在2008年推出的Intel Core i7及Intel Atom处理器又支持类似HT的技术,在 Nehalem 中,Hyper-Threading 大举卷土重来。在 Intel NetBurst 架构的 Northwood 版本中开始导入的 Hyper-Threading-在 Intel 世界之外称为 Simultaneous Multi-Threading (SMT)-是善用线程平行性的方法,让单一核心在应用软件层能运行两个逻辑线程。
顾虑[编辑]
把运行管线的状态,想像成流水线,资源A→资源B→资源C,来了两条数据要计算, 一条需要消耗A的100%→B的50%→C的50%,另一条一样需要消耗A的100%→B的50%→C的50%, 一条单纯的(无HT)的运行管线的资源A需要先运用100%性能把第一条运算完才能再运算下一条,但后面的资源B跟C却都有50%性能的浪费; 如果把运行管线的资源A,变成两个,资源B跟C依然只有一个, 那这条管线就可以变成“两个资源A同时消耗100%性能运算两条数据,到了资源B跟C阶段时,两条数据再各自消耗50%的性能”, 即达成“不必增加一条完整的运行管线,却能在一样时间运算两条线程”
但实际应用时,运行管线不会都是收到这么完美的需运算数据, 可能会是需消耗“A的10%→B的70%→C的70%”+“A的30%→B的50%→C的70”+……等多种不同性能需求的需运算数据, 依照文件的统计数字,整体能够提升的性能约为5~15%左右,且万一发生资源互抢的情形时,整体性能反而会下降。 (以上是非常简略地描述大略情形,实际的超线程架构从P4时代至i系列6代,每一代都有所进化)
要令电脑支持超线程技术,通常需操作系统和硬件的配合。芯片组需要支持具有HT技术之处理器。为此,当时的Intel推出了新的芯片组,i865PE和i875P。要充分发挥超线程的性能,用户要使用Windows 2000之后的操作系统,而Windows XP家用版亦支持超线程技术。除了微软的Windows外,Linux kernel 2.4.x亦开始支持该技术。软件方面,通常优化多线程的程序都可以支持到。早期,游戏软件的支持是比较少。但随着多核心技术的普及,愈来愈多游戏软件支持多线程的处理器。[3]

您的支持是对我创作最大的鼓励!

热评文章