并行：2 使用GPU理解并行计算_gpu 一个循环拆解成两个循环,绑定两个线程

本文链接

• 打死他

here!!!

2.6弗林分类法

• 大多数人熟悉的标准串行程序设计遵循的是SISD
  • 何时间点上只有一个指令流在处理一个数据项,
  • 单核CPU在一个时刻只执行一个任务
• 可通过time-slicing机制,
  • 在多个任务间迅速切换,达到“同时执行多个任务

 

• 双核或4核桌面计算机是MIMD。
• 它有一个线程或进程的工作池,
• OS负责逐个取出线程或进程,
  • 将他们分配到N个CPU核中的一个上执行。
• 每个线程或进程有一个独立的指令流,
  • CPU内部包含
  • 对不同指令流
  • 同时进行解码所需的全部控制逻辑。

 

• SIMD系统简化了它的实现方法
• 针对数据并行模型,在任何时间点,只有一个指令流
• CPU内只需一套逻辑来对这个指令流解码和执行,
  • 无须多个指令解码通路
• 由于从芯片内部移除了部分硅实体,
• 因此相比它的MIMD兄弟
• SIMD可做得更小、便宜、能耗低,更高频率下工作

 

• 很多算法只需对少量的数据点进行这样或那样处理
• 很多数据点常被交给一条SIMD指令
• 所有的数据点可能都是加上一个固定的偏移量,再乘一个数据
  • 这就容易用SIMD实现
• 从“对一个数据点进行一个操作”改为“对一组数据进行一个操作”
• 既然这组数据中每一个元素需要进行的操作或变换是固定的
  • 所以“访问程序存储区取指令然后译码”只需进行一次。
  • 由于数据区间是有界且连续
  • 所以数据可以全部从内存中取出,而不是一次只取一个字

 

• 如果算法是对一个元素进行A变换而对另一个元素进行B变换,
• 而对其他元素进行C,那么就很难用SIMD来实现
• 除非这算法由于常用而采用硬编码在硬件中实现,
• Advanced Encryption Standard和H.264(视频压缩标准)

 

• 与SIMD稍不同
• GPU实现的是被英伟称Single Instruction Multiple Thread
• 这种模型中,SIMD指令的操作码跟CPU中硬件实现的方式不同,它指示的并不是一个固定的功能
• 程序员需通过一个内核程序,指定每个线程的工作内容。
• 内核程序将统一读入数据,程序代码根据需要执行A、B或C
• 实际上A、B、C通过重复指令流而顺序执行,
  • 不过每次执行时
  • 屏蔽掉无须参与的线程。
• 与仅支持SIMD的模型相比
• 理论上说,这个模型更易掌握

2.7 常见的并行模式

• 很多并行处理问题都可按照某种模式来分析。
• 不是每个人都意识到它们的存在,
• 但我们也可以看到不同的模式,
• 按照模式来分析
• 使我们能够对问题深入解构或抽象

2.7.1 基于循环的模式

• 不同循环语句(for、do. while、while)的主要区别在于入口、退出条件
  • 两次循环送代之间是否会产生依赖

 

• 循环的迭代依赖：
  • 一次迭代依赖于之前的一次或多次先前迭代的结果
  • 这将并行算法的实现变得十分困难
• 若消除不了,则将循环分解成若干个循环块,块内的迭代是可并行执行
• 循环块0执行完后将结果给循环块1,然后给循环块2
• 后面有一个例子就是这种方法来处理前缀求和( prefix-sum)

 

• 基于循环的迭代是实现并行化的模式中最容易的
• 若循环间的依赖被消除,则剩下就是在可用的处理器上如何划分工作
• 划分原则
  • 让处理器间通信量尽可能少,
  • 片内资源(GPU上的寄存器和共享内存,CPU上的一级/二级/三级缓存)的利用率尽可能高
• 通信开销通常会随着分块数目的增多而迅速增,成为瓶颈、
  • 系统设计的败笔

 

• 对问题的分解 依据可用的逻辑处理单元数
• CPU：逻辑硬件线程数;
• GPU：SM数乘以每个SM的最大工作负载
• 依赖于资源利用率、最大工作负荷和GPU模型,SM的最大工作负载取值范围是1~16块
• 用的是逻辑硬件线程而不是物理硬件线程。
• 英特尔CPU采用“超线程”技术,一个物理CPU上支持多个逻辑线程
• GPU在一个SM内运行多个线程块,
  • 所以用SM的数量乘以每个SM支持的最大块数。

 

• 在一个物理设备上支持多个线程可以使设备吞吐率最大化
  • 某线程等待访存或IO类型的操作时,设备可处理其他线程工作
• 这个倍数的选择有助于在GPU上实现负载平衡,并可以应用于改进新一代GPU。
• 当数据划分导致负载不均时,这一点表现得尤为明显\
  • 某些块花费的时间远远大于其他块。
• 这时,可用几倍于SM数目的数量作为划分数据的基础
• 当一个SM空闲下来后
  • 它可以去存放待处理块的“池子”里取一个块来处理

 

• 对于CPU,过多的线程数量却可能会导致性能下降,这主要是由于上下文切换时,操作系统以软件的形式来完成。
• 对缓存和内存带宽竞争的增多,也要求降低线程的数量。
• 因此对于一个基于多核CPU的解决方案,通常它划分问题的粒度要远大于面向GPU的划分粒度。
• 如果在GPU上解决同一个问题,你则要对数据进行重新划分,把它们划分成更小的数据块。

 

• 当考虑采用循环并行来处理一个串行程序时,最关键的是发现隐藏的依赖
• 在循环体中仔细査找,确保每一次迭代的计算结果不会被后面的迭代使用
• 循环计数通常是从0~设置的最大值。
• 当遇到反过来采用递减计数的循环,你应该小心些
• 为什么这个程序员采用相反的计数方法呢?
  • 很可能就是循环中存在某种依赖。

 

• 有一个内循环和多个外循环
• 如何将它们并行化
• 对CPU只有有限线程,只能将这些外循环并行化
  • 前提是不存在循环迭代依赖。

 

• 如果分给GPU执行的内循环很小,通常用一个线程块内的线程处理
• 循环迭代是成组进行,
  • 相邻的线程通常访问相邻的内存地址,
  • 这有助于我们利用访存的局部性,这对CUDA程序设计重要
• 外循环的并行处理都是用线程块来实现,第5章详细

 

• 大多数循环可展开,因此把内循环和外循环合并成一个循环
• 图像中,沿X轴是内循环,沿Y轴是外循环。
• 通过把所有像素点看成是一个一维数组来展开循环,
  • 这样迭代就是沿像素点而不是图像坐标
• 尽管编程时麻烦些,但每次循环包含的迭代次数很小时,收效很大
  • 这些小的循环带来的循环开销相对毎次迭代完成的有效工作比较大,所以这些循环的效率很低

2.7.2 派生/汇集模式

• 串行程序中常见的模式,
  • 模式中含多个同步点且仅有一部分内容可并行
• 先运行串行代码,当运行到某点遇到一个并行区,
  • 并行区内的工作可分到P个处理器
  • 这时程序fork出N个线或进程来并行完成
• N个线程或进程的执行是独立的,工作完成后,则join起来
• OpenMP
  • 程序员用编译指令语句定义可并行区,
  • 并行区中的代码被分成N个线程,随后再汇聚成单个线程。

 

• 图2-2,
• 一个输入的数据项队列和三个处理单元(CPU核),
• 输入数据队列被分成三个小的数据队列,
• 一个处理单元处理一个小的数据队列,
• 每个队列的处理是互不相关
• 处理结果分别写在结果队列的相应位置。

 

• 派生/汇聚模式采用数据的静态划分来实现
• 即串行代码派生出N个线程并把数据集等分到这N个线程上。
• 如果每个数据块的处理时间相同的话,这种划分方法是很好的。
• 但是,由于总的执行时间等于最慢线程的执行时间,所以如果分配给一个线程太多的工作,它将成为决定总时间的一个因素。

 

• Openmp这样的系统跟GPU类似,实现动态的调度分配。
• 办法是,先建一个“线程池”(对GPU是个“块池”),
  • 然后池中的线程取一个任务执行,执行完后再取下一个。
• 1个任务要10个时间完成,其余20个要1个时间能完成,则它们只能分配到空闲的处理器核上执行
• 现在有一个双核处理器,则把那个要10个单位时间的大任务和5个需要1个单位时间的小任务分配给核1,其余的15个需要1个单位时间的小任务分配给核2
• 核1与核2就基本上可以同时完成

 

• 图2-2中,
• 选择生3个线程。
• 队列有6数据,为什么不派生6个线程?
  • 实际中,要处理的数据几百万,派生一百万个线程都会OS崩溃

 

• OS执行的是一个“公平的”调度策略。
• 每个线程都需按顺序,分配到4个可用的处理器核中的某一个上处理,
  • 每个线程都要一个它自己的内存空间,
  • Windows中,每个线程1MB栈空间
• 在派生出足够多的线程前,用尽内存空间

 

• so对CPU而言,程序员或者多数多线程库通常是按照处理器的个数来派生相同数目的逻辑处理器线程。
• CPU创或删除一个线程的开销是大的,且线程过多也降低处理器的利用率
• so用一个“工人”线程池,池中的“工人”每次从待处理的任务队列中取一个任务来处理,处理完后再取下一个

 

• GPU则相反,需成千上万个线程。
• 我们还是使用在很多先进的CPU调度程序中使用过的线程池的概念,将“线程池”改为“线程块池”
• GPU上可并发执行的“线程块”的数目存在一个上限。
• 每个线程块内含若干线程。
  • 每个块内含的线程的数和并发执行的“线程块”的数目
  • 随着不同系列GPU不同。

 

• 派生/汇聚模式用于并发事件的数目事先不确定
• 遍历一个树形结构或者路径搜索这类算法,
  • 遇到另一个节点或路径时,就很可能会派生出额外的线程。
• 当所有的路径都被考查后,
  • 这些线程就汇聚回线程池中或者汇聚后又开始新一轮的派生。

在启动内核程序时,块/线程的数量是固定的,所以GPU不是天生就支持这种模式。

• 额外的块只能由主机程序而不是内核程序启动。
• so在GPU上实现这类算法一般都需
  • 启动一系列的GPU内核程序,
  • 一个内核程序要
    • 产生启动下一个内核程序所需的工作环境。
• 还有一种办法,即通知或与主机程序共同,启动额外的并发内核程序。
• GPU是被设计来执行固定数目的并发线程,
  • so无论哪种方法实际效果都不太好。
• 为解决这个问题,
  • 开普勒架构引人dynamic parallelism)的概念。
• 关于这个概念的更多内容,见12章。

求解某些问题时,内核程序内部的并发性会不断变化,内部也会出现一些问题。

• 为此,线程之间要通信与协调。
• 在GPU的一个线程块内,线程之间通信与协调有很多方法实现。
• 假设你有一个8×8的块矩阵,很多块仅需要64个工作线程。
  • 然而,很可能其他块却需要使用256个线程。
  • 你可以在每个块上同时启动256个线程,这时多数线程处于空闲状态直到需要它们进行工作。
  • 由于这些空闲进程占用了一定的资源,会限制整个系统的吞吐率,但它们在空闲时不会消耗GPU的任何执行时间。
  • 这样就允许线程使用靠近处理器的更快的共享内存,而不是创建一系列需要同步的操作步骤,而同步这些操作步骤需要使用较慢的全局内存并启动多个内核程序。
  • 内存的类型6章介绍

新GPU支持更快的原子操作和同步原语。

• 除可实现同步外,
  • 这些同步原语还可实现线程间通信,本书后面将给出这方面例子。

2.7.3 分条/分块

用CUDA来解决问题,都要求程序员把向题分成若干个小块,即分条/分块。

• 数并行处理方法也是以不同的形式来使用“条/块化”的概念。
• 气候模型这样巨大的超级计算问题也必须分为成千上万个块,每个块送到计算机中的一个处理单元上去处理
• 这种并行处理方法在可扩展方面具有很大的优势。

GPU与集成在单个芯片上的SMP系统类似。

• 每个流处理器簇(SM)就是一个处理器,能同时运行多个线程块,
  • 每个线程块256或512个线程。
• 若干SM集成在一个GPU上,共享一个公共的全局内存
  • 同时工作时(GTX680)峰值性能3 Tflops

但达到这个性能却要精心设计

• 此峰值性能并不包括诸如访存这样的操作,
• 而这些操作却是影响实际程序性能的关键
• 无论什么平台上,为达到高性能,
  • 须了解硬件的知识并深刻理解两个重要的概念
  • 并发性和局部性

许多问题都存在并发性。

• “条/块模型”很直观地展示了并发性的概念。
• 二维空间里想象一个问题
  • 数据的一个平面组织,
  • 它可以理解为将一个网格覆盖在问题空间上。
• 三维空间里想象一个问题,
  • 就像一个魔方( Rubik’ s Cube),
  • 可把它理解为把一组块映射到问题空间中

CUDA提供简单二维网格模型。

• 对很多问题,这样的模型足够
• 如果在一个块内,你的工作是线性分布的,那么你可很好地将其分解成CUDA块。
• 由于在一个SM内,最多可分配16个块,在一个GPU内有16个(有些32)SM,所以把问题分成256甚至更多的块都可以。
• 实际倾向把一个块内的元素总数限制为128、256或者512,
  • 这有助于在数据集内划分更多数量的块

考虑并发性时,还可考虑是否可用ILP

• 理论上认为一个线程只提供一个数据输出。
• 但如果GPU上已经充满了线程,同时还有很多数据需要处理,这时我们能够进一步提高吞吐量吗?
• 答案是yes,但只能借助于LP。

实现ILP的基础是 指令流可在处理器内部以流水线的方式执行。

• 因此,与“顺序执行4个加法操作”(压入一等待一压入一等待一压入ー等待一压入一等待)相比,
  • “把4个加法操作压入流水线队列、等待然后同时收到4个结果”(压入一压入一压入一压入一等待)的效率更高。
• 绝大多数GPU,会发现每个线程采用4个ILP级操作是最佳。
• 9章更详细的研究和例子。
• 如果可能的话,更愿意让每个线程只处理N个元素,
  • 这样就不导致工作线程的总数变少了

2.7.4 分而治之

也是种把大问题分解成的小,每个小是可控

• 通过把这些小的、单独的计算汇集在一起,使一个大问題得到解决。

常见的分而治之的算法用“递归”来实现,

• quick sort就是
• 反复递归地把数据一分为二,一部分是位于支点( pivot point)之上的那些点,另一部分是位于支点之下的那些点。
• 最后,当某部分仅含两数据,则对它们做“比较和交换”

绝大多数递归算法可用迭代模型表示。

• 由于迭代模型较适合于GPU基本的条块划分模型,所以该模型易于映射到GPU上。
• 费米架构GPU也支持递归算法。
• 尽管使用CPU时,你必须了解最大调用深度并将其转换成栈空间使用。
• 所以你可以调用API cudaDeviceGetLimit来查询可用的栈空间,
  • 也可调用API cudaDeviceSetLimito来设置需要的梭空间。
• 若没有申请到足够的梭空间,将产生软件故障。
• Parallel Nsight和CUDA-GDB这样的调试工具可检测出像“栈溢出”( stack overflow)

在选择递归算法时,须在开发时间与程序性能之间做出个折中

• 递归算法易理解,与将其转换成一个迭代的方法相比,编码实现递归算法也比较容易。
• 但递归调用要把所有的形参和全部的局部变量压栈。
• GPU和CPU实现栈的方法是相同的,
  • 从全局内存中划出一块存储区间作为栈
• CPU和费米架构GPU都用缓存栈,但与寄存器来传递数据相比,还很慢。
• 所以,在可能的情况下最好还是使用迭代的方法,这样可以获得更好的执行性能,并可以在更大范围的GPU硬件上运行。

here!!!