Tag Archives: Warp

CUDA, 软件抽象的幻影背后 之二

先更新到这儿,稍后再回来抛光查错。CUDA比较杂,我一写起来容易满嘴跑火车弄出错误,欢迎拍砖。

**********************************************************************

版权声明:原创作品,欢迎转载,但转载请以超链接形式注明文章来源(planckscale.info)、作者信息和本声明,否则将追究法律责任。

上一篇里说到,有两点对CUDA的计算能力影响甚大:数据并行,以及用多线程掩盖延迟。接下来我们要深入到其硬件实现,看一看这些机制是如何运作的。

通常人们经常说某GPU有几百甚至数千的CUDA核心,这很容易让人联想到多核CPU。不过事实上两种“核心”是不一样的概念,GPU的CUDA核心只相当于处理器中的执行单元,负责执行指令进行运算,并不包含控制单元。可以类比到CPU核心的是流多处理器(Streaming Multiprocessor,简写为SM. Kepler中叫做SMX,Maxwell中叫做SMM),通常一个GPU中有数个SM,而每个SM中包含几十或者上百个CUDA核心,以及数个warp scheduler(相当于控制单元)。如下图GM204中有16个SM,每个SM中有128个CUDA核心,4个warp scheduler。

GeForce_GTX_980_SM_Diagram-545x1024

图 1.  GM204的SM结构图

每个SM中有大量的寄存器资源,在GM204的例子中,有总共64k 32-bit寄存器,可以养活成千上万的线程。SM中另外一个重要资源是Shared Memory,没错,它正是软件抽象中Shared Memory的对应物。在GM204中,每个SM有96KB的Shared Memory.

到这里,SM在软件抽象里的对应也呼之欲出了,没错,正是Block。我们不妨先摆出这个对应:
Block <-> SM
Thread执行 <-> CUDA Cores
Thread数据 <-> Register/Local Memory

同一Grid下的不同Block会被分发到不同的SM上执行。SM上可能同时存在多个Block被执行,它们不一定来自同一个kernel函数。每个Thread中的局域变量被映射到SM的寄存器上,而Thread的执行则由CUDA核心来完成。

SM上可以同时存在多少个Block?这由硬件资源的消耗决定:每个SM会占用一定数量的寄存器和Shared Memory,因此SM上同时存活的Block数目不应当超过这些硬件资源的限制。由于SM上可以同时有来自不同kernel的Block存在,因此有时候即便SM上剩余资源不足以再容纳一个kernel A的Block,但却仍可能容纳下一个kernel B的Block.

接下来一个很重要的问题是Block如何被执行。我们可以看到,SM上的CUDA核心是有限的,它们代表了能够在物理上真正并行的线程数——软件抽象里,Block中所有的线程是并行执行的,这只是个逻辑上无懈可击的抽象,事实上我们不可能对一个任意大小的Block都给出一个同等大小的CUDA核心阵列,来真正并行的执行它们。
因而有了Warp这个概念:物理上,Block被划分成一块块分别映射到CUDA核心阵列上执行,每一块就叫做一个Warp.目前,CUDA中的Warp都是从threadIdx = 0开始,以threadIdx连续的32个线程为一组划分得到,即便最后剩下的线程不足32个,也将其作为一个Warp.CUDA kernel的配置中,我们经常把Block的size设置为32的整数倍,正是为了让它能够精确划分为整数个Warp(更深刻的原因和存储器访问性能有关,但这种情况下仍然和Warp的size脱不了干系)。
在GM204的SM结构图里我们可以看到,SM被划分成四个相同的块,每一块中有单独的Warp Scheduler,以及32个CUDA核心。Warp正是在这里被执行。
Warp的执行非常类似于SIMD. Warp中的活动线程由Warp Scheduler驱动,同步执行。我们可以看到,GM204中32个CUDA核心共享一个Warp Scheduler. 关于Warp执行中可能出现的复杂些的问题,留到下文另外说。

现在可以整理一下这个世界的图景了。SM上存活着几个Block,每个Block中的变量占据着自己的寄存器和Shared Memory,Block被划分成32个线程组成的Warp. 这样,大量的Warp生存在SM上,等待被调度到CUDA核心阵列去执行。

Warp Scheduler正如其名,是这个Warp世界里的调度者。当一个Warp执行中出现等待(存储器读写延迟等)后,Warp Scheduler就迅速切换到下一个可执行的Warp,对其发送指令直到这个Warp又一次出现等待,周而复始。这就是上一篇所说“用多线程掩盖延迟”在硬件图景下的模样。

CPU_GPU_COMPARE

图 2.  GPU用多个Warp掩盖延迟 / 与CPU计算模式的对比

本图引用自PPT “CUDA Overview” from Cliff Woolley, NVIDIA.

如图,GPU用多个Warp快速切换来掩盖延迟,而CPU用快速的寄存器来减小延迟。两者的重要区别是寄存器数目,CPU的寄存器快但少,因此Context Switch代价高;GPU寄存器多而慢,但寄存器数量保证了线程Context Switch非常快。

多少线程才能够掩盖掉常见的延迟呢?对于GPU,最常见的延迟大概要数寄存器写后读依赖,即一个局域变量被赋值后接着不久又被读取,这时候会产生大约24个时钟周期的延迟。为了掩盖掉这个延迟,我们需要至少24个Warp轮流执行,一个Warp遇到延迟后的空闲时间里执行其余23个Warp,从而保持硬件的忙碌。在Compute Capability 2.0,SM中有32个CUDA核心,平均每周期发射一条指令的情况下,我们需要24*32 = 768个线程来掩盖延迟。
保持硬件忙碌,用CUDA的术语来说,就是保持充分的Occupancy,这是CUDA程序优化的一个重要指标。

(未完待续)

图像拼接算法原理 2

版权声明:原创作品,欢迎转载,但转载请以超链接形式注明文章来源(planckscale.info)、作者信息和本声明,否则将追究法律责任。

2. 曲面投影

Homography_Near90Degreee

图6. 近90^{\circ}时产生越来越大的畸变

通常简单的图像拼接技术,就是如上节所示的基本原理,找出一张大概处于中间位置的图像,然后利用单应性变换把其他图像变换到该中心图像的视角下,再做一些后续的曝光补偿、图像融合等处理即可。但是这一技术有相当大的局限性,最简单的例子,不能直接用它拼出360^{\circ}的全景图。

为什么呢?让我们来考虑图6中所示情形。可见,三条光线与P^{\prime}相交的三点,原本是近乎等间距均匀分布的,而当它们映射到P平面上后,间距却产生了巨大的差异。表现在图像上,P^{\prime}上的图像变换到P上后,会产生相当大的拉伸畸变。当图中两相机的投影平面越来越趋于垂直时,这个畸变越来越大,以至于P^{\prime}上普通的一点可能会被映射到P平面的无穷远点。这时,这种简单的单应性拼接方案就彻底崩溃了。

Homography_Warp

图7. 曲面投影解决大视场角下的投影畸变问题

怎样得到更宽视场角下的拼接图?解决方法很简单。以上所出现的这种畸变源自于我们将点投影到一个平面上,设想将P掰弯,或者直接弯曲成一个圆柱面,成为图7所示的样子,那原本被投影到P平面无穷远处的点就被拉回来了。我们在圆柱面上选取一个足够均匀的坐标系,把坐标对应到像素坐标,就可以得到一个全景图了。

当然,针对不同的应用,我们还可以选取不同的投影曲面,比如选取球面用于360^{\circ} * 180^{\circ}的球面全景图,甚至也可以选择一个立方体作为投影曲面。

 

3. 后续处理

至此全景拼接的几何原理就大致说完了,虽然我们还没有给出数学表达。为了先居高临下的了解整个拼接流程,我们不妨把后续处理的梗概也在此一说。

实际应用中为了创建出完美的全景图,有很多的问题需要考虑。最典型的问题有两个,一个是如何解决不同照片中曝光不一致的问题;一个是如何在拼接缝处完美平滑的融合两张图像的问题。

第一个由曝光补偿算法来解决,大体思路是估计两张图间的曝光差异,然后进行补偿。此处不多说。

第二个问题也有众多解决方案,最为著名的大概就属Multi-Band融合算法。该算法虽然八十年代就已提出,但其效果至今仍让人赞叹。在通常图像间失配程度不大的情况下,Multi-Band可以达到肉眼几乎不可分辨的融合效果。其原理也不复杂,下面略微一提。

融合两张图像,最直接的方案是在两张图像的重合区域用一个平滑渐变的权重对二者加权叠加。该方法的效果并不理想,关键原因是我们无法兼顾拼缝附近的局域细节和大尺度上两张图片的宏观特征(如光照)。当我们希望局域细节能够完好拼接时,需要用较小的平滑渐变区;而当我们希望要宏观上平滑过渡时,又想要较大的渐变区域。这二者似乎不可调和。

但事实上并非如此。Multi-Band的成功之处就是在于它同时兼顾两种需求,当融合宏观特征时,采用一个大的平滑渐变区;融合局域细节时,则采用小的平滑渐变区。那如何才能把这两种情况分开处理呢?很简单,把图像分解为不同频带的分量之加和,图像的宏观特征在它的低频分量图里,而局域特征在高频分量图里。

所以,Multi-Band算法的过程大致就是:把图像按照频率高低展开成一个金字塔,然后高低频分量各自按照不同的方式平滑加权并叠加,最后把各频带分量重新加和,得到最终的融合结果。

该算法融合效果虽好,但对于计算量要求较大,它需要创建多座金字塔并对金字塔进行各种运算,图像像素较高时,在CPU上要达到实时基本无望。当然,GPU上情况就不一样了,我们自己就实现了实时的Multi-Band融合算法,效果很好。

 

这一系列文章主要以拼接的几何原理为主。下一节开始用数学建模前两节所述的投影模型。

(未完待续)