0%

《全局光照》读书笔记(四)

《全局光照》并行计算架构部分

冯诺依曼架构与其瓶颈

架构

冯诺依曼架构的计算机由以下部分组成:

  • 用于二进制运算的算术逻辑单元(arithmetic logic unit,ALU)
  • 高速存储指令和数据的寄存器组(processor registers)
  • 用来控制指令读取的控制单元(control unit)
  • 用于存储所有指令和数据的内存
  • 外加一些大容量存储和输入输出设备

瓶颈

随着处理器运行速度的提高,其花费了更多时间用于等待从内存获取数据,不管处理器多快,它都受限于内存传输速度。

克服瓶颈的方法

缓存(cache)

缓存是一种容量更小,更快的内存,缓存里的数据来自于主存。当处理器需要从主存获取指令或数据时,会先查询一级缓存(L1),若不在则会查询二级与三级缓存(L2或L3)。如果缓存中没有此数据则从主存中读取。当在缓存中读取数据是称作缓存命中(cache hit),反之称为缓存失效(cache miss)。缓存的设计利用的是局部性原理,包括空间局部性和时间局部性。

预取(prefetching)

预取是为了减小缓存失效的几率,通过在处理器读取数据之前预测可能会读取的数据然后读取到缓存中实现。预取技术通常集成于处理器内部,各级缓存都有自己的预取器(prefetcher)

对于数据预取最常用的是常数步幅(constant-stride)模式,即根据之前数据访问的模式预先载入当前数据邻近对应长度范围的数据。但如果程序对数据读取在内存空间随机跳跃则预取器会毫无作用。

对于指令的预取,由于大多情况下指令是线性排列顺序执行的,其相对于数据预取会更加简单。但是函数指针和分支语句会使得指令读取非线性化。

多线程(multithreading)

多线程会在下面并行架构中讲解。

并行计算架构

指令级并行

指令级并行计算(instruction-level parallelism,ILP)指一个单处理器同时执行多条指令的能力。指令级并行技术的目的就是要尽可能地提升ILP值。

指令管线优化

指令管线优化是各种ILP技术的基础,它将一条指令完整的执行流程分成多个阶段。这样划分可以不让处理器一次只处理一条指令,从而充分利用处理器资源。最经典的5步划分为:

  • IF:获取指令(instruction fetch),处理器从一级缓存中获取一个指令并修改程序计数器(program counter,PC)的值。
  • ID/RF:解码指令以及从寄存器中获取操作数(instruction decode and register fetch)
  • EX:执行
  • MEM:读取内存(memory access)
  • WB:写回寄存器(register write back)

由于将指令计算过程管线化,每个管线阶段都允许执行一条指令,充分利用各个生产流水线提高了整个管线的吞吐能力。指令管线化的工作效率取决于应用程序的可并行性,当程序指令中出现依赖时称之为一个障碍(hazard)。通常硬件使用三种主要方法来处理串行指令的并行障碍:

  • 管线气泡(pipeline bubble)
  • 操作数前移(pperand forwarding)
  • 乱序执行(out-of-order execution)

管线气泡

当指令包含障碍时,其在解码阶段被识别,同时处理器会创建一个气泡占据该指令的解码阶段,使当前管线的解码阶段处于空闲等待状态。管线气泡会导致后续一个或多个指令被延迟。

在这种解决方案中,每个气泡表示该时钟周期有一个阶段处理空闲状态。

操作数前移

当指令间出现依赖关系时,后一项指令必须等待前一项指令执行完毕并将数据输出到寄存器后才能执行。通常数据写入和从寄存器里读取的过程会占据几个时钟周期。当后项指令依赖前向指令的值时,操作数前移可以解决这种障碍。

操作数前移需要处理器对这类依赖进行探测,如果后项指令依赖前项指令的值,则芯片集成电路内部直接将值传递给后项不要通过寄存器读写。由于程序中通常存在大量这种前后依赖关系,操作数前移技术不仅能够有效避免这种障碍,而且大大节省了数据在寄存器之间存储和读取导致的时间延迟。

乱序执行

乱序执行基于一个事实,即如果后面的指令不依赖于前面的指令,或者它此时具备执行指令需要的操作数数据,则它可以先于前面的指令被执行。尽管执行顺序被打乱,但程序执行的结果必须和原来一样。

乱序执行的指令执行步骤如下:

  1. 获取指令
  2. 将指令分配到一个指令队列
  3. 指令在指令队列中等待,直到其操作数可用,此时它可以先于前面的指令被执行
  4. 执行指令
  5. 将指令输出结果保存在一个队列中
  6. 只有当一个指令的前面所有指令执行完毕并写入寄存器后才能够将结果写入寄存器,以保证执行结果的顺序一致性

线程级并行

多线程(multithreading)技术是指在单个处理器或者一个多核处理器的其中一个核内部拥有同时执行多个线程的能力,这些线程在内部共享该处理器的各种资源,包括计算单元、寄存器、缓存等。

时分多线程技术(temporal multithreading,TMT)

最简单的时块多线程(block multithreading),它会一直执行一个线程直到其遇到很大的延迟时,会切换到另一个“可执行状态”的线程。

另一种比较聪明的方法是交叉多线程(interleaved multithreading),这种方法是在每个时钟周期都执行一个不同于上一个时钟周期的线程。

同时多线程技术(simultaneous multithreading,SMT)

以英特尔的超线程技术(Hyper-Threading Technology)为例。在结构上,一个超线程架构的处理器由两个逻辑处理器(logical processor)组成,每个逻辑处理器拥有自己的架构状态等,但共享一些执行资源。

每个逻辑处理器拥有的资源包括:

  • 独立的架构状态
  • 并发执行自己的指令
  • 正在执行的指令可以被独立地打断和停止

共享的资源有:

  • 处理器的执行引擎(Execution engine)以及L1缓存
  • 系统数据总线(system bus inerface)

与多核处理器不同在于,SMT并没有多个物理上的执行资源如执行单元、指令调度、寄存器、L1缓存等。

处理器级并行

多处理器架构的对等性

对称性是指所有处理器调的地位和功能是否对等。

非对等多处理器架构(Asymmetric multiprocessing,ASMP)比较典型的例子是Cell处理器架构,它的思想是用一个常规处理器作为监管处理器,该处理器与大量的高速协作处理器相连。

PPE(Power Processor Element)担任与外界和流处理器的接口,协作处理器SPE(Synergistic Processing Element)则在PPE的管理下处理数据集。通过一个共享的互联总线(Element inerconnect bus),SPE之间以及SPE与PPE之间可以相互通信。

Cell处理器的设计目标是为了克服内存访问的延迟对处理器性能的限制。Cell的独特之处在于摒弃了内存缓存结构,而是直接将数据和指令直接发送到每个SPE的本地内存空间LS(Local store),SPE直接从LS上存取数据,每个SPE都有一个直接内存存取(Direct memory access,DMA)引擎,用于将LS的数据高速同步到SPE或者PPE的内存上。

多处理架构的通信方式

通信方式主要有共享内存和基于网络的消息传递方式。

共享内存方式中,每个处理器拥有自己的缓存系统,但共享整个主存,所以需要同步机制保证主存与缓存中数据的一致性(cache coherence)。

另一种多处理器架构称为集群,即通过一些独立廉价的计算机系统通过网络连接起来组成一个多处理器系统。

弗林分类法

根据指令流数目和数据流数目对所有的计算机进行分类。

  • SISD(single instruction stream single data stream)单指令流单数据流
  • SIMD(single instruction stream multiple data stream)单指令流多数据流
  • MISD
  • MIMD