l GPU硬件特性
n 存储层次
u Global memory：
l 大小一般为几GB
l chip-off的DRAM介质存储器
l 访问速度慢（是shared memory的上百倍）
l 对于是否对齐和连续访问敏感（由DRAM的性质决定）
l 可以被所有的线程访问
u Shared memory：
l 每个SM中一般几十KB
l chip-on的SRAM介质存储器
l 访问速度快（与register相当）
l 对于是否对其和连续访问不敏感，但是对bank conflict敏感（由bank设计决定）
l 只对自身block中的线程可见
u Register
l 每个SM中一般为几千个（约30K）
l Chip-on的寄存器
l 访问速度最快
l 只对每个thread本身可见
u Other
l Local memory
n 每个线程有512KB（计算能力2.x），或者16KB（计算能力1.x）
n Chip-off的存储器，与global memory类似
n 访问速度慢（与global memory类似）
n 由编译器控制，存放寄存器溢出的自动变量
n 只对每个thread本身可见
l Texture memory
n 大小为6-8KB
l Constant memory
n 大小为64KB
n 执行层次
u 逻辑
l Grid：由block构成，维数及维度可以设置，所有的block在Grid中并行执行
l Block：由thread够层，维数及维度可以设置，同一个block中的thread并行执行
l Thread：由threadId识别，每个thread有自己的寄存器，私有变量，共享同一个block中的shared memory
u 物理
l SM：由多个流处理器组成，每个SM有独立的资源，包括：block槽，warp槽，thread槽，shared memory，register
l Warp：由32个thread组成，每次执行的时候，32个thread动作一致，如果有分支，则串行执行
l Thread：物理上属于warp，与其他thread一同，组成最小的执行单元warp，拥有自己的寄存器
l GPU优化原则
n 访存方式
u Global memory：尽量让一个warp中的线程访问连续的一个内存块，实现级联访问（合并访问）
u Shared memory：尽量减少bank conflict，让同一个warp中的线程访问不同的bank
n 数据分块
u Shared memory block：在SM能够支持的情况下，尽量多地利用此资源提高局部重用性
u Register memory：在shared memory之上可以多加一层寄存器层，进一步提高重用性（寄存器的带宽和延迟都优于共享内存）
n 限制分支
u Warp divergence：尽量减少分支判断，将同一个分支中的thread尽量放在同一个warp中
n 提高计算密度
u Instruction throughput：一方面提高warp的效率，让warp充分用到function unit，尽量接近理论峰值；另一方面可以降低非运算类的比例，使得指令更多地用于计算
l GPU优化策略
n 级联访存
u Global memory：将线程组织称为可以一次性访问一个warp中内容的形式
n 共享内存
u Shared memory：减少bank conflict来加快对shared memory的访问
n 重组线程
u 将各个分支中的线程进行重组，让同一个warp中的线程尽量地走同一个分支
n 指令流水线
u 对指令进行分类，分析每一类指令的吞吐量，减少混合指令
n 指令调度
u 将长延迟的指令插入到与该指令独立的计算密集点处，使用计算来隐藏延迟（一般为访存造成的延迟）
l GPU优化实现
n 《实战》
u CGMA：compute to global memory access
l 计算：浮点数操作/访存操作，能够比较准确地体现kernel的性能，在访存性能一定的时候，通过提高CGMA的值可以使得浮点操作的性能大幅提升（浮点操作的峰值性能远远超过访存的峰值带宽）
l 例子：CGMA=1.0，则浮点操作的性能最好的时候也就跟访存性能一致，而G80的global memory的带宽为86.4GB/s，但是其浮点计算的峰值性能却为367Gflops，这样，性能将被访存速度所约束
u 减少global memory的流量
l 将具有局部重用性的数据块加载到每个block中的shared memory中，减少对global memory的频繁访问，提高读取数据的性能
l 例子：矩阵乘法的分块实现，利用shared memory来存储每一小块所需的数据及结果
u 存储器的使用需要谨慎
l 如果每个线程使用得存储器过多，将会直接导致每个SM上可以驻留的线程数减少，造成并行度不足的问题
l 例子：G80中每个SM有8K的寄存器，16K的shared memory，如果每个块分配的shared memory超过了2K，则SM中驻留的块将无法达到全部的8个，降低并行度，寄存器也是同样的道理
u Warp divergence的问题
l 一个warp中的线程存在分支的时候，会造成串行执行不同分支，降低性能，可以通过调整线程执行内容来减少warp中存在的分支，提高性能
l 例子：tid % 2造成了每个warp中都有分支，换成了tid < stride后，将直接消除了几乎所有分支
u Global memory带宽
l 由于global memory是有DRAM组成，所以，访问的速度慢，而每次访问将会返回连续的一段数据（硬件设计决定），所以，为了接近峰值，应该坚持每次访问都对连续的单元进行访问（即合并访问）
l 例子：矩阵的行优先转换成列优先，可以一次性读取连续的单元，提高效率；如果warp访问的是global memory中的连续单元，则该访问将会被合并成一次性访问
u SM资源的动态划分（分块大小的策略）
l GT200中，每个SM最多驻留1024个线程，8个块，可以划分为4*256，也可以划分成8*128，但是后者更能充分地利用线程槽和块槽，效率将会更高
l 寄存器数目可能造成的性能悬崖：GT200种每个SM有8192个寄存器，对于16*16的线程块，如果每个线程用到的寄存器为10个，那么可以容纳3个块，如果每个线程用到的寄存器为11个，则只能容纳2个块，这种情况可能极大地降低并行度，造成性能退化
n 说明：上面描述的情况也不一定降低性能，如果一个寄存器能够使得独立的浮点操作数大幅提高，那么，就算少了一个块，也能够有充分的warp来隐藏延迟
n 问题：寄存器溢出是在寄存器不够用的情况下出现的，按照上面的说法，寄存器如果不够用，会减少块的个数来避免这个问题，那么什么时候将会溢出？另一方面，寄存器溢出会造成对local memory的访问，降低性能，但是没有想象中的低，因为Fermi已经为local memory提供了缓冲
u 数据预取
l 当所有的线程都在等待存储器访问结果的时候，延迟将没有办法被隐藏，这个时候，可以调整处理过程为：使用当前元素时，预取下一个元素，隐藏延迟（书中观点是：在读取global memory到shared memory中的这个过程中间，插入了独立的计算指令，有效地隐藏延迟）
l 例子：将原来读取global memory到shared memory的过程拆分成global memory到register，再从register到shared memory，这样，从global memory读取下一块到register的时候，就可以同时计算当前块，隐藏延迟了
u 混合指令的消除
l 对于循环，往往混合了多种指令：取址，分支，计数，运算，而指令的混合将会降低执行效率，可以通过消除这种混合来提高指令的执行效率
l 例子：将循环次数不多的循环体直接展开称为长的表达式，消除指令的混合
u 线程粒度调整
l 提高线程的粒度有时候能够降低访存的次数，因为其提高了数据的重用性，当然，期间不可避免地用到了更多的寄存器和shared memory
l 例子：矩阵分块乘法中，每个块计算C的几个块，可以减少对输入矩阵的加载，但是，使用更多的register和shared memory可能降低性能
u 总结：调整好块的大小是最重要的，其次考虑数据预取和指令展开，最后调整线程粒度，找到最好的平衡点
n 论文一
u 文章内容：提出了一个定量的性能分析模型，衡量CUDA程序的三个主要组成部分：指令流水线，共享存储器访问，全局存储器访问；用于统计数据的工具：barra simulator
u 建模分析：传统分析：计算限制/访存限制；替代分析：指令吞吐量限制/内存层次限制；将模糊的“算法，计算量”量化为清晰的“指令吞吐量，内存分层”
u 模型建立：
l 指令层次：将指令按照执行代价进行分类，然后利用一般化的代码在不同warp数目情况下执行，收集信息并估算出每一类指令的流水线吞估量
l 共享存储层次：对于一般化代码，利用bank conflict信息更正内存事务的数量，在不同warp数目情况下执行，利用吞吐量估算访问共享存储器所用的时间
l 全局存储层次：使用一个内存事务模拟器来计算硬件层次上的事务数量，从而计算时间
l 大致过程：Barra生成一个关于指令执行次数的动态程序执行信息，然后用这个信息来生成每一类动态指令的数目，共享内存事务的数目，全局内存事物的数目，被同步所分开的阶段的数目
u 模型的作用
l 定量地分析每一部分的性能，找出瓶颈，检测瓶颈是否消除，给出确切的瓶颈原因
l 指令瓶颈：计算密集度低，高代价的指令多，warp并行效率低
l 共享内存瓶颈：bank conflict，bookkeeping 指令引起的内存拥塞，warp并行效率低
l 全局内存瓶颈：并行化隐藏延迟的效率低，非级联的内存放访问和内存事务粒度过大
u 详细建模过程：
l 利用Barra生成动态指令，通过信息收集器输出三部分信息：每种指令的个数，共享存储器的事务数目，全局存储器的事务数目（通过同步将程序分成单个的阶段，对单个的阶段进行分析，找出这些数据）
l 内建一个工具修改原有的指令，将修改后的指令重新编译成二进制代码嵌入到执行文件中
l 对指令流水线的建模：通过可以执行该指令的FU（function unit）数量不同，将指令进行分类，对每一类指令可以通过收集的信息计算出其理论的吞吐量峰值（#FU*Freq*#SM/warpSize）
l 对共享存储器事务的建模：已知shared memory带宽，通过调整SM中的warp数目，找出带宽饱和时最少需要的warp数目；利用自动程序导出不同程度的bank conflict所对应的有效共享存储器事务的数量
l 对全局存储器事物的建模：运行一个综合标准测试程序（同样的数目的块，块内线程，线程的存储事件个数），然后根据级联规则将这些存储事务分成几个硬件层次上的事件，估算全局存储器事务的数量
n CUDA的级联访问规则：
u 对于每个存储事件，找出最小下标线程所请求的内存段地址
u 找出所有其他也请求该内存段的线程
u 尽可能归约缩小该内存段的大小
u 重复以上三步直到处于同一个half-warp中的线程都获得服务
n 论文二
u 文章内容：warp divergence对性能的影响表现为branch的串行执行，一个warp可能执行1次，也可能执行32次，需要对这个问题进行分析，建立评估模型，并且进行优化
u 问题分析：warp divergence可以从硬件和软件两个方面进行优化：硬件方面：动态warp形成技术（提供有限的线程重组）；动态warp子划分，让不同分支的线程重叠执行，意在减小这些分支对性能的影响；软件方面：线程重新组织技术，减少分支；综合分析这些技术，没有任何技术能够完全消除分支的影响，这里致力于减小分支对性能的影响（具体表现为最小化没有用到计算资源的那些时钟周期）
u 建立模型：
l 介绍两个常用的标准：divergence branches，用于记录warp中的分支数；divergence warp ratio，用于记录存在分支的warp占所有warp的百分比
l 考虑三种类型的估算：BBV（basic block vector），EV（edge vector），PV（path vector），精确性递增， 计算复杂性递增，本文选择了BBV
l 估算过程：
n 找出每个basic block中执行次数最多的thread，记录其次数，所有的次数加起来作为metric：
，该matric可以衡量一个warp中basic block的执行次数，但是无法对执行次数相同的basic block进行区分
n 考虑basic block执行的指令数目，乘上次数，再做加法，可以衡量更为精细的线程性能，metric：
n 加入block的动态调度，最终形成metric为：BBV-Weighted-scheduled，测试结果可以说明不同线程组成的操作之间的性能差别
u 性能优化：
l 大致流程（包括下面三个部分）：利用GPGPU-Sim模拟器简历程序控制流程图，获得每个线程的BBV个数，然后通过重组算法对线程进行重组，新的组合将被用来提高应用的性能，而主程序和kernel程序都会作出响应的修改（参见论文Figure4）。
l 程序控制流程分析
n 使用模拟器获取所需要的数据
l 线程重组分析
n 线程重组函数（三种重组算法后面介绍）为线程产生用于引用重定向的ID的重定向数组，也为数据分布转换而重排输入数据（当然也要调整输出数据）
l 应用及Kernel代码修改
n 修改kernel函数中对输入数据的引用函数，host中添加重组函数
u 重组算法（具体过程参考论文）
l 简单排序算法：对线程进行简单排序，按照排序的结果连续分组
l 贪婪算法：每个thread独立成一个group，迭代计算两个group合并的效益，合并最大效益的两个group直到生成K个group
l K-均值聚集算法：迭代计算线程之间的距离，将互相之间距离最近的线程聚集成一个group，直到这个过程没有任何聚集为止
u 模型的作用：
l 提出一个分支控制流程的标准，精确地对kernel中分支对性能造成的影响进行衡量
l 使用这些标准，用户可以无需真正的转化操作就能够准确预测优化所能带来的潜在性能提升
l 提出了三个重组算法，利用一个值函数来衡量性能的提升
l 对于访存为主的kernel，本模型并不适用
n 论文三
u 文章内容：提出一个衡量程序运行时间的模型（从而给出程序的性能瓶颈），主要从运行时线程数量和存储带宽进行考虑，估算出并行访存请求的数量（称为访存warp并行度），基于访存warp并行度，模型估算出内存请求的代价，进而估算整个程序的执行时间。
u 模型基本观点：
l 在并行的GPU应用中，估算性能的时候，其最主要部分为内存操作的消耗（所以本文主要分析这方面）
l 针对这些操作，提出两个标准：MWP（memory warp parallelism）和CWP（compute warp parallelism）
l MWP为能够同时访问内存的最大warp数目，CWP为在一个warp的访存期间，一个SM中能够同时执行计算的warp个数加1；
l 通过对这两个标准的计算，可以进一步推算出执行程序所需要的总时钟周期。
u 建立模型：
l 计算出MWP和CWP
n MWP主要衡量的是内存层次的并行化程度，CWP衡量的是程序的其他特性：越高的CWP以为这越低的计算密集度
n MWP的计算：
u 在级联访问和非级联访问的情况下，分别计算出最大的MWP数目，然后通过权重得出一个平均的MWP数目，最后与每个SM中活跃的warp数目相比，取其小者
n CWP的计算：
u 访存操作的时钟周期/计算的时钟周期+1，然后与每个SM中活跃的warp数目相比，取其小者
l 计算出程序执行的时钟周期
n MWP>CWP：
u 此时，程序属于计算为主的类型
u 计算方式：
n CWP>MWP：
u 此时，程序属于访存为主的类型
u 计算方式：
n MWP=CWP=N：
u 此时，程序属于warp数量不足的类型
u 计算方式：
l 将这些因素都放进CUDA里面考虑
n 每个SM的warp数目不同，重复调度warp的数目也就不同，通过计算可以得到相关参数
n 对PTX汇编出来的指令进行统计，得到动态的指令数目（有一定的误差）
n 计算CPI（cycles per instruction），用总消耗了的时钟周期除以总的指令数目即可（越低的CPI意味着越高的性能）
n 级联访问或者非级联访问，以及同步产生的影响，都需要加入到估算之中
n 总共执行的时钟周期由计算出来的MWP和CWP的关系决定如何计算
u 模型的作用
l 估算GPU架构上的执行时钟周期
l 模型提出一个标准MWP来估算有效访存指令的代价
l 模型提出一个简单的性能估算标准CPI，可以为编程人员或者编译器提供参考
u 模型的局限性
l 没有考虑cache miss（I-cache，texture，constant）的问题
l 没有建立一个分析cache的模型
l 没有分析分支所产生的代价
n 论文四
u 文章内容：使用分块算法（shared memory block和register block）实现了双精度的稠密矩阵乘法；优化内容有软件流水线，向量存储操作，指令调度；相比较与CUBLAS提高了20%的性能
u 问题分析及简介：
l 当前稠密线性代数库的问题：性能提升的背后使用了什么技术细节？目前的性能还有多少可以提升的空间？
l 在Fermi架构上对DGEMM进行优化，提出性能模型，主要使用了三种优化策略，展示了代码调优的试验
u Fermi特性简介
l 在DRAM和SM之间多了一层缓存，与shared memory不同，这将有助于减缓非级联访问带来的延迟
l 每个SM有两个warp调度器，意味着每个时钟周期可以发射两个warp，但是双精度指令无法与其他类型指令同时发射
l 内存操作的位宽增大到了128bit，但是，使用大位宽的指令将会造成更高的延迟
u 建模过程：
l 理论分析出shared memory block的大小和register block的大小（详细过程见论文分析过程）
l 分析两个基本的算法：算法1和算法2
n 算法1：由于对global memory的访问（读取元素到shared memory中）没有被很好地缓冲，所以性能不佳
n 算法2：对算法1进行改进，增加了一倍的寄存器，在计算当前块的同时，读取下一个块的数据到register，利用计算来隐藏访存的延迟（与《实战》中的方法一样），性能有所提升；但是，由于寄存器用多了，导致寄存器溢出到local memory中，同样造成了性能的下降，所以，总体的性能提升并不明显（故而，软件预取过程应该尽可能少地增加寄存器）
l 使用拇指原则分析：
n 在一个应用中，浮点数的吞吐量取决于浮点指令的百分比，提高百分比，就能够获得更大的吞吐量，而算法1已经十分接近理论百分比了，难以提升
n 由于Fermi能够进行128bit的内存操作，所以，可以通过增加一倍的位宽减少一般的访存指令，从而提高浮点指令的百分比，获得更大的性能提升空间
n 考虑到128bit的内存操作将会造成更加严重的延迟，所以，需要找出适当的方法来隐藏这种延迟
l 三种主要的优化策略
n 数据线程映射：使用128bit的内存操作来取代原有的64bit内存操作，每次可以读写两个double类型的数据，通过调整数据与线程的映射关系，可以减少一半的访存指令，提高浮点指令的百分比
n 双缓存策略：为了使得计算与访存重叠从而使得延迟得以隐藏，我们将同一块中的数据分成两部分进行操作，使得每次计算和访存所涉及的数据都不一样，则可以使得计算与访存重叠起来，从而避免了使用额外的寄存器，又隐藏了延迟
n 指令调度策略：
u 可以通过对不同的寄存器计算stall time，从而调整指令的顺序（超出本文范围）
u 将程序转化为汇编指令，将内部循环完全展开，然后对汇编指令进行重排（分析程序，大致计算寄存器的stall time，手工将访存延迟的指令插入到合适的位置）
u 试验结果分析
l 最终版本性能提升最为明显，其使用了上面所有的策略，性能比CUBLAS3.2提高了20%
l 各种策略的优化效果分析（以下版本基于算法三进行修改，启用了双缓存技术，没有使用128bit访存指令）
n 版本一：使用了128bit访存指令，效果并不明显，性能提升之后只能与CUBLAS不相上下
n 版本二：仅仅将算法三转换成了汇编指令，不对指令做任何调整，性能稍有提升
n 版本三：在版本二的基础上，对内部for循环进行了指令调度优化（只对shared memory访问优化），性能稍有提升
n 版本四：在版本三的基础上，对总体都进行了指令调度优化（增加了对global memory的访问优化），性能大幅提升
n 总结：对于Fermi，寄存器溢出的情况并不会造成很大性能下降（由于local memory的cache），所以，双缓存对于性能提升不会太明显（个人觉得相对于算法1和2还是相当明显的），global memory的访存延迟隐藏是主要因素，而使用128bit的访存指令也造成了这个因素的重要性更加突出
u 一般性优化讨论
l 128bit的访存指令能够提高浮点数的运算潜能（当然，需要与另外两种策略相结合）
l 双缓存策略可以有效减少寄存器的使用，隐藏存储延迟
l 最有效的优化策略是指令调度（能够最好地隐藏global memory访问引起的延迟），小部分指令往往占据了大量的执行时间（可惜只能手工调整）
u 个人问题
l 对两个层次的block大小实现自动化计算
l 对指令调度过程实现自动化
l 没有考虑warp divergence，bank conflict，texture & constant memory？
n 延伸
u 不同的优化策略适用于不同的应用程序，能否自动检测出某个程序适用那些优化策略？
u 如何更好地使用texture memory，constant memory，L2 cache，L1 cache？