基于gpu的rma算法

A. 计算机视觉领域主流的算法和方向有哪些

人工智能是当下很火热的话题，其与大数据的完美结合应用于多个场景，极大的方便了人类的生活。而人工智能又包含深度学习和机器学习两方面的内容。深度学习又以计算机视觉和自然语言处理两个方向发展的最好，最火热。大家对于自然语言处理的接触可能不是很多，但是说起计算机视觉，一定能够马上明白，因为我们每天接触的刷脸支付等手段就会和计算机视觉挂钩。可以说计算机视觉的应用最为广泛。

目标跟踪，就是在某种场景下跟踪特定对象的过程，在无人驾驶领域中有很重要的应用。目前较为流行的目标跟踪算法是基于堆叠自动编码器的DLT。语义分割，则是将图像分为像素组，再进行标记和分类。目前的主流算法都使用完全卷积网络的框架。实例分割，是指将不同类型的实例分类，比如用4种不同颜色来标记4只猫。目前用于实例分割的主流算法是Mask R-CNN。

B. 做数据集群训练，如何比较好的资源调度做到程序稳定（多深度学习GPU的调度策略）

蓝海大脑液冷数据中心研发人员指出：这是一个就是GPU集群管理调度的一个问题，现在主流的GPU系统在国内可以分成2部分，一类是交通系统，一类是基于容器的一个比如K8S的调度编排的一个调度系统。K8S里面是支持了GPU设备的自发现，然后你只是去提交GPU的一个请求的个数以及GPU资源的类型，然后它会自动去帮你去做调度。另外的话是以HPC为传统的那种，比如说PPS或SLAM调度，SLAM里面也有支持GPU设备的一个自我调度，然后把GPU设备作为一个计算对象可以去请求。当然由于GPU系统的拓扑结构是一样的，不同的调度算法，给你分配的GPU资源可能会存在一些GPU拓扑不是最优的情况。然后针对这种情况，不管是SLAM还是K8S系统，NVIDIA写了一个拓扑自我检测的小程序算法，它可以很好的集成到K8S以及SLAM里面，然后在做GPU资源分配时，根据这个算法去分配GPU资源，以保证你分配的CPU资源是最优的，拓扑最优，而且也会保证以后的分配，对以后资源的拓扑最优也会有保证。

C. HartSift: 一种基于GPU的高准确性和实时SIFT

尺度不变特征变换 (SIFT) 是最流行和最强大的特征提取算法之一，因为它对尺度、旋转和光照保持不变。它已被广泛应用于视频跟踪、图像拼接、同时定位和映射（SLAM）、运动结构（SFM）等领域。然而，高计算复杂度限制了其在实时系统中的进一步应用。这些系统必须在准确性和性能之间进行权衡以实现实时特征提取。他们采用其他更快但精度较低的算法，如 SURF 和 PCA-SIFT。为了解决这个问题，本文提出了一种使用 CUDA 的 GPU 加速 SIFT，命名为 HartSift，充分利用单机CPU和GPU的计算资源，实现高精度、实时的特征提取。实验表明，在 NIVDIA GTX TITAN Black GPU 上，HartSift 可以根据图像的大小在 3.14-10.57ms (94.61-318.47fps) 内处理图像。此外，HartSift 分别比 OpenCV-SIFT（CPU 版本）和 SiftGPU（GPU 版本）快 59.34-75.96 倍和 4.01-6.49 倍。同时，HartSift 的性能和 CudaSIFT（迄今为止最快的 GPU 版本）的性能几乎相同，而 HartSift 的准确度远高于 CudaSIFT。

SIFT算法可以提取大量显着特征，这些特征在缩放、旋转、光照和3D视点保持不变，还提供了跨越噪声和仿射失真的稳健匹配。但SIFT的高计算复杂度限制了其在大规模数据和实时系统中的进一步应用。而复杂度较低的算法，如SURF、PCA-SIFT的准确性又不太高。因此，在主流计算平台上实现高精度、实时的SIFT是一个重要而有意义的研究课题。

而SIFT算法具有很好的并行性，可以正确移植到GPU上。因此，在配备GPU的异构计算系统上实现高性能的SIFT具有重要的实用价值。

SIFT 算法包含三个阶段，包括高斯差分（DoG）金字塔的构建、精确的关键点定位和 128 维描述符生成。由于每个阶段都有自己的并行特性，因此必须使用不同的并行粒度和优化来实现高性能。尤其是后两个阶段，负载不平衡不利于GPU优化，会导致性能下降。

本文的主要贡献和创新可以概括如下：

有许多工作尝试在GPU上使用SIFT算法。

然而，为了实现高性能，他们省略了 SIFT 算法的一些重要步骤，例如将输入图像加倍、保持尺度变化的连续性和拟合二次函数以定位准确的关键点信息。作者的实验表明，这些遗漏会导致 SIFT 丢失很多关键点和准确性。

Lowe将输入图像尺寸加倍作为高斯金字塔 的最底层，每个尺度 通过高斯卷积产生：

高斯金字塔确定之后，利用相同Octave的层级相减，得到差分金字塔：

其中 ，在本文中， .

检测尺度空间极值

将DoG金字塔每个像素与相邻像素比较，同层8个，上下层9个，若像素是局部最大值或局部最小值，将其视为关键点候选。

去除无效关键点

去除较低对比度和不稳定边缘响应的候选关键点，通过将3D二次函数拟合到附近数据执行子像素插值，以获取精确的位置、比例和主曲率比。

方向分配

将候选关键点周围的梯度累积到36 bins的直方图中，根据每层的尺度计算搜索半径。每个紧邻像素由一个高斯加权窗口加权，梯度方向累计到36 bins的方向直方图中。峰值为主要梯度方向，同时超过峰值80%的局部峰值bin也被视为关键点方向。

对关键点周围像素计算梯度直方图，搜索半径比上一步骤大得多，同样用一个高斯加权函数用于为每个邻居的梯度值分配权重。

根据梯度方向将最终的梯度值累积到一个 360-bin 的圆形方向直方图。最后，直方图将被归一化、平滑并转换为 128D 描述符。

构建金字塔应该保持顺序，以保证尺度空间变化连续性。Acharya和Bjorkman为加快这一过程，牺牲准确性打破构建顺序。考虑到不能使准确性降低，构建顺序在HartSift中保留。

分离卷积核

对于 大小的卷积核处理 大小的图像需要进行 次运算，如果将2D卷积核拆解为两个1D的卷积核，计算量减少至 . 通过使用共享内存和向量化方法，更容易实现合并全局内存访问并减少一维卷积的冗余访问。

Uber 内核

Uber内核将多个不同任务放到一个物理内核中，在一个内核中并行处理任务，而不需要在内核之间切换。差分金字塔第 层由高斯金字塔第 和第 层决定。将高斯差分金字塔和高斯卷积核封装在单个核中，可以充分挖掘并行性。

线程不需要重复读取高斯金字塔第 层的值，这是由于第 层的值计算完后，结果会放在寄存器内而不是全局内存中。借助Uber内核的优势，我们可以节省 的空间和 的内核运行时间

异构并行

HartSift 采用异构并行方法来加速这一阶段。CPU 和 GPU 将并行协作，构建 DoG 金字塔。

由于GPU处理小图像没有优势，作者将 以下的图像放到CPU处理，大图像放到GPU处理。用户也可以自行设置分离点，确保CPU和GPU负载平衡。

存在两个问题：

负载均衡

Warp是GPU最小并行执行单元，即以锁步方式执行的 32 个线程的集合。若负载不均衡，则warp执行时间取决于最后一个线程完成的时间，warp负载不均衡会导致GPU效率降低。

由于候选关键点分布的随机性，几乎所有经线都包含不同数量的空闲线程。如果这些warp继续处理以下部分，就会出现两个级别的负载不平衡.

在去除无效的候选关键点部分时，线程将进行亚像素插值以获得准确的候选关键点信息，从而去除具有低对比度或不稳定边缘响应的关键点候选。换句话说，一些线程会比其他线程更早返回一次。负载不平衡会变得更加严重。

为了突破性能瓶颈，HartSift 引入了重新平衡工作负载和多粒度并行优化。

重新平衡工作负载

当检测到负载不平衡时，HartSift 将通过启动具有适当粒度的新内核并分派每个具有 32 个活动线程的新经线来重新平衡工作负载。

此外，启动三个内核分别处理这三个部分，不仅可以重新平衡工作量，还可以根据不同部分的并行特性提供多粒度的并行。

多粒度并行

重新平衡工作负载优化保证每个内核中的线程和经线被完全加载，多粒度并行优化保证工作负载将平均分配到线程和经线。此外，不同内核的并行粒度取决于工作负载的特性。

HartSift通过将一个线程映射到一个或多个像素，采用与关键点候选检测部分和无效关键点去除部分并行的线程粒度。然而，线程粒度并行会导致方向分配部分的负载不平衡，因为不同关键点的相邻区域半径不同。线程粒度并行会为单个线程分配过多的工作，这在某些情况下限制了硬件资源的利用率。所以在这部分应用混合粒度并行：扭曲粒度构建直方图，线程粒度找出并将主导方向分配给相应的关键点。

基于扭曲的直方图算法

作者针对每个关键点提出了一种基于扭曲粒度和原子操作的高性能直方图算法，以充分利用局部性。

该阶段关键点的邻域半径远大于前一阶段。需要为每个关键点累积数千个邻居到一个 360-bin 直方图。如果采用前一阶段的基于原子扭曲的直方图算法，会对这一阶段的性能产生不同的影响。

HartSift引入了一种atomic-free的直方图算法，进一步提升了这一阶段的性能。

该算法包含三个步骤：

为了消除线程间的负载不平衡，实现全局合并访问，HartSift 使用一个warp 来处理一个keypoint 的所有邻居。当线程计算出它们的方向 bin 时，它们需要根据bin变量的值将梯度值累加到局部直方图。考虑到有如此多的邻居并且一个经线的一些线程可能具有相同的 bin，算法1引入了一种无原子的多键约简方法来累积每个经线的部分和。这种方法可以利用warp级shuffle和vote指令完全消除原子操作和本地同步。它根据bin对经纱的线程进行分组并指定每组具有最低车道的线程作为队长线程。队长线程将保存他们自己的 bin 的部分总和，并将它们并行地累积到驻留在共享内存中的本地直方图，而不会发生 bank 冲突和同步。在遍历所有邻居后，HartSift 将最终的局部直方图复制到驻留在全局内存中的全局直方图。

本文提出了一种GPU上的并行SIFT，命名为Hart-Sift，它可以在单机内同时使用CPU和GPU来实现高精度和实时的特征提取。HartSift根据每个阶段的不同特点，通过适当采用不同的优化策略来提升性能，例如负载均衡、基于warp的直方图算法和不同尺度样本的atomic-free直方图算法等。在NVIDIA GTX TITAN Black GPU上，HartSift可以在3.14 ~ 10.57ms（94.61 ~ 318.47fps）内提取高精度特征，轻松满足高精度和实时性的苛刻要求。另外，与OpenCV-SIFT和SiftGPU相比，HartSift获得了59.34 ~ 75.96倍和4.01 ~ 6.49倍加速分别。同时，HartSift 和 CudaSIFT 的性能几乎相同，但 HartSift 远比 CudaSIFT 准确。

D. 如何用python一门语言通吃高性能并发，GPU计算和深度学习

第一个就是并发本身所带来的开销即新开处理线程、关闭处理线程、多个处理线程时间片轮转所带来的开销。

实际上对于一些逻辑不那么复杂的场景来说这些开销甚至比真正的处理逻辑部分代码的开销更大。所以我们决定采用基于协程的并发方式，即服务进程只有一个(单cpu)所有的请求数据都由这个服务进程内部来维护，同时服务进程自行调度不同请求的处理顺序，这样避免了传统多线程并发方式新建、销毁以及系统调度处理线程的开销。基于这样的考虑我们选择了基于Tornado框架实现api服务的开发。Tornado的实现非常简洁明了，使用python的生成器作为协程，利用IOLoop实现了调度队列。

第二个问题是数据库的性能，这里说的数据库包括MongoDB和Redis，我这里分开讲。

先讲MongoDB的问题，MongoDB主要存储不同的用户对于验证的不同设置，比如该显示什么样的图片。
一开始每次验证请求都会查询MongoDB，当时我们的MongoDB是纯内存的，同时三台机器组成一个复制集，这样的组合大概能稳定承载八九千的qps，后来随着我们验证量越来越大，这个承载能力逐渐就成为了我们的瓶颈。
为了彻底搞定这个问题，我们提出了最极端的解决方案，干脆直接把数据库中的数据完全缓存到服务进程里定期批量更新，这样查询的开销将大大降低。但是因为我们用的是Python，由于GIL的存在，在8核服务器上会fork出来8个服务进程，进程之间不像线程那么方便，所以我们基于mmap自己写了一套伙伴算法构建了一个跨进程共享缓存。自从这套缓存上线之后，Mongodb的负载几乎变成了零。
说完了MongoDB再说Redis的问题，Redis代码简洁、数据结构丰富、性能强大，唯一的问题是作为一个单进程程序，终究性能是有上限的。
虽然今年Redis发布了官方的集群版本，但是经过我们的测试，认为这套分布式方案的故障恢复时间不够优秀并且运维成本较高。在Redis官方集群方案面世之前，开源世界有不少proxy方案，比如Twtter的TwemProxy和豌豆荚的Codis。这两种方案测试完之后给我们的感觉TwemProxy运维还是比较麻烦，Codis使用起来让人非常心旷神怡，无论是修改配置还是扩容都可以在配置页面上完成，并且性能也还算不错，但无奈当时Codis还有比较严重的BUG只能放弃之。
几乎尝试过各种方案之后，我们还是下决心自己实现一套分布式方案，目的是高度贴合我们的需求并且运维成本要低、扩容要方便、故障切换要快最重要的是数据冗余一定要做好。
基于上面的考虑，我们确定基于客户端的分布式方案，通过zookeeper来同步状态保证高可用。具体来说，我们修改Redis源码，使其向zookeeper注册，客户端由zookeeper上获取Redis服务器集群信息并根据统一的一致性哈希算法来计算数据应该存储在哪台Redis上，并在哈希环的下一台Redis上写入一份冗余数据，当读取原始数据失败时可以立即尝试读取冗余数据而不会造成服务中断。

E. GPU上图像拼接的快速计算

图像拼接已被研究并广泛应用于计算机科学的许多领域，但在特征匹配、扭曲和混合步骤中存在大量计算。从而无法满足某些应用的实时性需求。幸运的是，已经在图形处理器单元 (GPU) 上开发并实现了一些可以加快拼接过程的相关并行操作。在本文中，我们使用统一计算设备架构 (CUDA) 提出了基于 GPU 的图像拼接的并行实现。我们在执行时间方面获得了比在中央处理单元 (CPU) 上实现更好的结果。在实验中使用集成 GPU GTX745 时，我们对大输入图像实现了高达 27.6 倍的加速比。

典型的拼接过程主要包括三个不同的图像处理步骤，即配准、扭曲和插值以及混合。图像配准是图像拼接的关键任务。配准是指在描绘同一场景的一对图像之间建立几何变换，该变换由一个8自由度的平面单应性决定。

GPU以其强大的并行计算能力吸引许多领域的研究，作为一种协处理器对计算量大的算法加速已成为实践的重要途径。在前人的研究中，他们都避免了考虑两个极其耗时的步骤，即特征匹配和随机样本共识（RANSAC）。作为图像配准中的两个关键过程，在提出的 GPU 加速并行算法中应考虑它们。

使用GPU并行计算会遇到两个限制

CUDA的出现解决了上述问题，并且CUDA使用C语言，最初为CPU编写的C语言函数可以移植到CUDA内核，无需修改。

在CUDA中，一定数量的线程被分组到一个块中，一定数量的块以规则的网格模式在逻辑上排列（见图1）。每个块都映射到一个多处理器，一个多处理器可以同时运行多个线程块。由于本地资源（寄存器和共享内存）在块之间进行划分，包含在同一块中的线程可以访问相同的共享内存并快速实现同步操作。但是，不同块中的线程并不能直接实现通信和同步。除了本地寄存器和共享内存，所有线程都可以访问全局内存、常量内存和纹理内存。

A. 特征匹配

令点 经过仿射变换后得到 ，即

向量 是平移分量， 控制缩放、旋转效果。利用齐次坐标系，方程(2)也可以写为

接着计算两幅图像特征点之间的欧几里得距离，并将距离按照升序排序，比较升序排序中第一和第二的比值如果小于某个阈值，则认为是匹配点。

由于 中有六个未知参数，随机选择3对不共线的点匹配 ，使用该矩阵 计算剩余 对匹配点的误差。执行大量迭代，直到内点对最多。可以使用最小二乘估计器估计所有六个参数。

B. 变形和插值

扭曲变形过程中，可能使像素点位置出现负值或者没有数值与之对应，在这种抢矿下需要插值算法创建更平滑和准确的数值，进一步减少翘曲中产生的变形。最常用的插值方法是最近邻插值、双线性插值和双三次插值。考虑到精度和计算复杂度之间的权衡，实验采用双线性插值算法。

C. 混合

为了实现并行计算，本文采用了基于羽化的混合方法，其混合函数可以表示为：

其中 是像素 的权重函数。

A. 并行匹配

匹配分为粗匹配和精匹配。粗匹配过程中，块线程数由特征元素数决定，每个块可以实现一个关键点之间的匹配，每个线程计算两个图像两个特征向量的距离。在计算完所有距离后，使用并行计算的归并排序对距离值排序。最后，所有块得到的匹配结果存储在全局内存中，然后传送到CPU。

精匹配过程，设计内核执行RANSAC迭代，只启动一个block，线程数为 ，首先用CPU将三个非共线点计算得到的变换矩阵 ，然后将 、阈值和剩余 个点传到GPU，判断内外点。

通过内存分配，可以实现精细匹配优化。

B. 平行变形和插值

将 矩阵的逆矩阵 存放在常量内存中，由于需要频繁地调用。将待校正的图像存放在纹理内存中，纹理内存是专门为本地访问模式设计的。

为了进一步提升性能，若两个坐标小数部分小于0.2则强度值分配为整数部分，否则使用双线性插值。

C. 并行混合

由于混合数是像素和像素的混合，因此线程数等于重叠部分包含的像素。令重叠图像的列数设置为16的倍数。 gridDim.x的大小等于重叠图像的行数，gridDim.y的大小等于重叠图像的列数重叠图像除以16。

基于 CPU 的算法在配备 16GMB DDR3 RAM 的 Intel Core i7-4790、3.60GHz 处理器上实现。基于 GPU 的算法在 NVIDIA GeForce GTX745 集成显卡上进行测试，每块最大 1024 个线程和 4096 MB 全局内存。

可以清楚地看到，这两种图像之间几乎没有差异。原因是实验中使用的GPU卡支持浮点计算，与CPU版本相比产生的误差非常小。

在本文中，我们提出了一种使用 CUDA 架构在 GPU 上运行的并行图像拼接方法。顺序算法通过几个 CUDA 内核转换为并行版本。通过使用不同类型的内存，我们实现了并行算法的优化。同时，将GPU获得的结果与CPU获得的结果进行比较，我们实现了高达27.6的加速比。尽管所提出的方法显着提高了计算性能，但仍有许多工作要做。例如，更精确的插值方法（双三次插值）和可变权重 c( x, y) 可以考虑进一步改善镶嵌结果。此外，并行镶嵌算法也可以在多个GPU平台上运行，对于大数据可以更有效地执行算法。在今后的工作中，我们将一一处理这些问题。

F. c# 如何使用gpu计算

如何通过编程将GPU用于通用计算任务

随着现代图形处理器(GPU)可编程能力及性能的提高，应用开发商们一直希望图形硬件可以解决以前只有通用CPU才能完成的高密集计算任务。尽管利用通用GPU进行计算很有发展前景，但传统图像应用编程接口仍然将GPU抽象成一个包括纹理、三角形和像素在内的图像绘制器。寻找一种能够使用这些基本元素的映射算法并不是一项简单的操作，即便对最先进的图形开发商而言也是如此。
幸运的是，基于GPU的计算从概念上讲很容易理解，并且现有多种高级语言和软件工具可以简化GPU的编程工作。但是，开发商必须首先了解GPU在图像绘制过程中是如何工作的，然后才能确定可用于计算的各个组件。
在绘制图像时，GPU首先接收宿主系统以三角顶点形式发送的几何数据。这些顶点数据由一个可编程的顶点处理器进行处理，该处理器可以完成几何变换、亮度计算等任何三角形计算。接下来，这些三角形由一个固定功能的光栅器转换成显示在屏幕上的单独“碎片(fragment)”。在屏幕显示之前，每个碎片都通过一个可编程的碎片处理器计算最终颜色值。

计算碎片颜色的运算一般包括集合向量数学操作以及从“纹理”中提取存储数据，“纹理”是一种存储表面材料颜色的位图。最终绘制的场景可以显示在输出设备上，或是从GPU的存储器重新复制到宿主处理器中。
可编程顶点处理器和碎片处理器提供了许多相同的功能和指令集。但是，大部分GPU编程人员只将碎片处理器用于通用计算任务，因为它通常提供更优的性能，而且可以直接输出到存储器。
利用碎片处理器进行计算的一个简单例子是对两个向量进行相加。首先，我们发布一个大三角形，其所包含的碎片数量和向量大小(容纳的元素)相同。产生的碎片通过碎片处理器进行处理，处理器以单指令多数据(SIMD)的并行方式执行代码。进行向量相加的代码从存储器中提取两个待加元素，并根据碎片的位置进行向量相加，同时为结果分配输出颜色。输出存储器保存了向量和，这个值在下一步计算中可以被任意使用。
可编程碎片处理器的ISA类似于DSP或Pentium SSE的指令集，由四路SIMD指令和寄存器组成。这些指令包括标准数·运算、存储器提取指令和几个专用图形指令。
GPU与DSP的比较
GPU在几个主要方面有别于DSP架构。其所有计算均使用浮点算法，而且目前还没有位或整数运算指令。此外，由于GPU专为图像处理设计，因此存储系统实际上是一个二维的分段存储空间，包括一个区段号(从中读取图像)和二维地址(图像中的X、Y坐标)。
此外，没有任何间接写指令。输出写地址由光栅处理器确定，而且不能由程序改变。这对于自然分布在存储器之中的算法而言是极大的挑战。最后一点，不同碎片的处理过程间不允许通信。实际上，碎片处理器是一个SIMD数据并行执行单元，在所有碎片中独立执行代码。
尽管有上述约束，但是GPU还是可以有效地执行多种运算，从线性代数和信号处理到数值仿真。虽然概念简单，但新用户在使用GPU计算时还是会感到迷惑，因为GPU需要专有的图形知识。这种情况下，一些软件工具可以提供帮助。两种高级描影语言CG和HLSL能够让用户编写类似C的代码，随后编译成碎片程序汇编语言。这些语言编译器可以从Nvidia和微软公司的网站免费下载。尽管这些语言大大简化了描影汇编代码的编写，但实际应用时仍然必须使用图形API来建立并发布计算任务。
Brook是专为GPU计算设计，且不需要图形知识的高级语言。因此对第一次使用GPU进行开发的工作人员而言，它可以算是一个很好的起点。Brook是C语言的延伸，整合了可以直接映射到GPU的简单数据并行编程构造。
经GPU存储和操作的数据被形象地比喻成“流”(stream)，类似于标准C中的数组。核心(Kernel)是在流上操作的函数。在一系列输入流上调用一个核心函数意味着在流元素上实施了隐含的循环,即对每一个流元素调用核心体。Brook还提供了约简机制，例如对一个流中所有的元素进行和、最大值或乘积计算。
Brook编译器是一个源到源的编译器，能够把用户的核心代码映射成碎片汇编语言，并生成C++短代码，从而链接到大型应用中。这允许用户只把应用中的性能关键部分输入Brook。Brook还完全隐藏了图形API的所有细节，并把GPU中类似二维存储器系统这样许多用户不熟悉的部分进行了虚拟化处理。
用Brook编写的应用程序包括线性代数子程序、快速傅立叶转换、光线追踪和图像处理。Brook的编译器和实时运行环境可以从http://brook网站上免费获取。
sourceforge.net网站也为许多此类应用提供资源。利用ATI的X800XT和Nvidia的GeForce 6800 Ultra型GPU，在相同高速缓存、SSE汇编优化Pentium 4执行条件下，许多此类应用的速度提升高达7倍之多。
对GPU计算感兴趣的用户努力将算法映射到图形基本元素。类似Brook这样的高级编程语言的问世使编程新手也能够很容易就掌握GPU的性能优势。访问GPU计算功能的便利性也使得GPU的演变将继续下去，不仅仅作为绘制引擎，而是会成为个人电脑的主要计算引擎。