精华内容
下载资源
问答
  • gpu算法
    千次阅读
    2021-02-14 22:23:43

    嵌入式算法移植优化学习笔记5——CPU,GPU,TPU,NPU都是什么


    随着AI的广泛应用,深度学习已成为当前AI研究和运用的主流方式。面对海量数据的并行运算,AI对于算力的要求不断提升,对硬件的运算速度及功耗提出了更高的要求。

    目前,除通用CPU外,作为硬件加速的GPU、NPU、FPGA等一些芯片处理器在深度学习的不同应用中发挥着各自的优势,但孰优孰劣?

    以人脸识别为例,其处理基本流程及对应功能模块所需的算力分布如下:
    在这里插入图片描述
    为什么会有这样的应用区分?

    意义在哪里?

    想要知道其中的答案,需要我们先从CPU、GPU、NPU、FPGA它们各自的原理、架构及性能特点来了解。

    首先,我们先来了解一下通用CPU的架构

    一、什么是CPU?

    中央处理器(CPU),是电子计算机的主要设备之一,电脑中的核心配件。其功能主要是解释计算机指令以及处理计算机软件中的数据。CPU是计算机中负责读取指令,对指令译码并执行指令的核心部件。中央处理器主要包括两个部分,即控制器、运算器,其中还包括高速及实现它们缓冲处理器之间联系的数据、控制的总线。电子计算机三大核心部件就是CPU、内部存储器、输入/输出设备。中央处理器的功效主要为处理指令、执行操作、控制时间、处理数据。在计算机体系结构中,CPU 是对计算机的所有硬件资源(如存储器、输入输出单元) 进行控制调配、执行通用运算的核心硬件单元。CPU 是计算机的运算和控制核心。计算机系统中所有软件层的操作,最终都将通过指令集映射为CPU的操作。
    主要逻辑架构包括控制单元Control,运算单元ALU和高速缓冲存储器(Cache)及实现它们之间联系的数据(Data)、控制及状态的总线(Bus)。简单说,就是计算单元、控制单元和存储单元
    架构图如下所示:
    在这里插入图片描述
    CPU遵循的是冯诺依曼架构,其核心是存储程序、顺序执行。CPU的架构中需要大量的空间去放置存储单元(Cache)和控制单元(Control),相比之下计算单元(ALU)只占据了很小的一部分,所以它在大规模并行计算能力上极受限制,而更擅长于逻辑控制。

    CPU无法做到大量矩阵数据并行计算的能力,但GPU可以。

    二、什么是GPU?

    图形处理器(英语:Graphics Processing Unit,缩写:GPU),又称显示核心、视觉处理器、显示芯片,是一种专门在个人电脑、工作站、游戏机和一些移动设备(如平板电脑、智能手机等)上做图像和图形相关运算工作的微处理器。

    GPU使显卡减少了对CPU的依赖,并进行部分原本CPU的工作,尤其是在3D图形处理时GPU所采用的核心技术有硬件T&L(几何转换和光照处理)、立方环境材质贴图和顶点混合、纹理压缩和凹凸映射贴图、双重纹理四像素256位渲染引擎等,而硬件T&L技术可以说是GPU的标志。GPU的生产商主要有NVIDIA和ATI。

    GPU的构成相对简单,有数量众多的计算单元和超长的流水线,特别适合处理大量的类型统一的数据。但GPU无法单独工作,必须由CPU进行控制调用才能工作。CPU可单独作用,处理复杂的逻辑运算和不同的数据类型,但当需要大量的处理类型统一的数据时,则可调用GPU进行并行计算。

    在这里插入图片描述

    与CPU相比,CPU芯片空间的不到20%是ALU,而GPU芯片空间的80%以上是ALU。即GPU拥有更多的ALU用于数据并行处理

    以Darknet构建的神经网络模型AlexNet、VGG-16及Restnet152在GPU Titan X, CPU Intel i7-4790K (4 GHz) 进行ImageNet分类任务预测的结果:
    在这里插入图片描述

    备注:以上数据源自https://pjreddie.com/darknet/imagenet/#reference

    由此可见,GPU处理神经网络数据远远高效于CPU。

    总结GPU具有如下特点:

    • 1 、多线程,提供了多核并行计算的基础结构,且核心数非常多,可以支撑大量数据的并行计算。

    • 2、拥有更高的访存速度。

    • 3、更高的浮点运算能力。

    因此,GPU比CPU更适合深度学习中的大量训练数据、大量矩阵、卷积运算。

    GPU虽然在并行计算能力上尽显优势,但并不能单独工作,需要CPU的协同处理,对于神经网络模型的构建和数据流的传递还是在CPU上进行。同时存在功耗高,体积大的问题。

    性能越高的GPU体积越大,功耗越高,价格也昂贵,对于一些小型设备、移动设备来说将无法使用

    因此,一种体积小、功耗低、计算性能高、计算效率高的专用芯片NPU诞生了。

    三、什么是NPU?

    嵌入式神经网络处理器(NPU)采用“数据驱动并行计算”的架构,特别擅长处理视频、图像类的海量多媒体数据。
    NPU处理器专门为物联网人工智能而设计,用于加速神经网络的运算,解决传统芯片在神经网络运算时效率低下的问题。在GX8010中,CPU和MCU各有一个NPU,MCU中的NPU相对较小,习惯上称为SNPU。

    NPU处理器包括了乘加、激活函数、二维数据运算、解压缩等模块。

    • 乘加模块用于计算矩阵乘加、卷积、点乘等功能,NPU内部有64个MAC,SNPU有32个。

    • 激活函数模块采用最高12阶参数拟合的方式实现神经网络中的激活函数,NPU内部有6个MAC,SNPU有3个。

    • 二维数据运算模块用于实现对一个平面的运算,如降采样、平面数据拷贝等,NPU内部有1个MAC,SNPU有1个。

    • 解压缩模块用于对权重数据的解压。为了解决物联网设备中内存带宽小的特点,在NPU编译器中会对神经网络中的权重进行压缩,在几乎不影响精度的情况下,可以实现6-10倍的压缩效果。

    NPU工作原理是在电路层模拟人类神经元和突触,并且用深度学习指令集直接处理大规模的神经元和突触,一条指令完成一组神经元的处理。相比于CPU和GPU,NPU通过突触权重实现存储和计算一体化,从而提高运行效率。
    在这里插入图片描述
    NPU是模仿生物神经网络而构建的,CPU、GPU处理器需要用数千条指令完成的神经元处理,NPU只要一条或几条就能完成,因此在深度学习的处理效率方面优势明显。

    实验结果显示,同等功耗下NPU 的性能是 GPU 的 118 倍

    与GPU一样,NPU同样需要CPU的协同处理才能完成特定的任务。下面,我们可以看一下GPU和NPU是如何与CPU协同工作的。

    GPU的加速

    GPU当前只是单纯的并行矩阵的乘法和加法运算,对于神经网络模型的构建和数据流的传递还是在CPU上进行
    在这里插入图片描述

    CPU加载权重数据,按照代码构建神经网络模型,将每层的矩阵运算通过CUDA或OpenCL等类库接口传送到GPU上实现并行计算,输出结果;CPU接着调度下层神经元组矩阵数据计算,直至神经网络输出层计算完成,得到最终结果。

    四、什么是TPU?

    TPU(Tensor Processing Unit)即张量处理单元,是一款为机器学习而定制的芯片,经过了专门深度机器学习方面的训练,它有更高效能(每瓦计算能力)。

    因为它能加速其第二代人工智能系统TensorFlow的运行,而且效率也大大超过GPU――Google的深层神经网络就是由TensorFlow引擎驱动的。TPU是专为机器学习量身定做的,执行每个操作所需的晶体管数量更少,自然效率更高。

    TPU与同期的CPU和GPU相比,可以提供15-30倍的性能提升,以及30-80倍的效率(性能/瓦特)提升。

    TPU每瓦能为机器学习提供比所有商用GPU和FPGA更高的量级指令,这基本相当于7年后的科技水平。TPU是为机器学习应用特别开发,以使芯片在计算精度降低的情况下更耐用,这意味每一个操作只需要更少的晶体管,用更多精密且大功率的机器学习模型,并快速应用这些模型,因此用户便能得到更正确的结果。

    附:

    CPU/GPU/NPU/FPGA各自的特点
    在这里插入图片描述

    • APU – Accelerated Processing Unit, 加速处理器,AMD公司推出加速图像处理芯片产品。

    • BPU – Brain Processing Unit, 地平线公司主导的嵌入式处理器架构。

    • CPU – Central Processing Unit 中央处理器, 目前PC core的主流产品。

    • DPU – Deep learning Processing Unit, 深度学习处理器,最早由国内深鉴科技提出;另说有Dataflow Processing Unit 数据流处理器, Wave Computing 公司提出的AI架构;Data storage Processing Unit,深圳大普微的智能固态硬盘处理器。

    • FPU – Floating Processing Unit 浮点计算单元,通用处理器中的浮点运算模块。

    GPU – Graphics Processing Unit, 图形处理器,采用多线程SIMD架构,为图形处理而生。

    • HPU – Holographics Processing Unit 全息图像处理器, 微软出品的全息计算芯片与设备。

    • IPU – Intelligence Processing Unit, Deep Mind投资的Graphcore公司出品的AI处理器产品。

    • MPU/MCU – Microprocessor/Micro controller Unit, 微处理器/微控制器,一般用于低计算应用的RISC计算机体系架构产品,如ARM-M系列处理器。

    • NPU – Neural Network Processing Unit,神经网络处理器,是基于神经网络算法与加速的新型处理器总称,如中科院计算所/寒武纪公司出品的diannao系列。

    • RPU – Radio Processing Unit, 无线电处理器, Imagination Technologies 公司推出的集合集Wifi/蓝牙/FM/处理器为单片的处理器。

    • TPU – Tensor Processing Unit 张量处理器, Google 公司推出的加速人工智能算法的专用处理器。目前一代TPU面向Inference,二代面向训练。

    • VPU – Vector Processing Unit 矢量处理器,Intel收购的Movidius公司推出的图像处理与人工智能的专用芯片的加速计算核心。

    • WPU – Wearable Processing Unit, 可穿戴处理器,Ineda Systems公司推出的可穿戴片上系统产品,包含GPU/MIPS CPU等IP。

    • XPU – 百度与Xilinx公司在2017年Hotchips大会上发布的FPGA智能云加速,含256核。

    • ZPU – Zylin Processing Unit, 由挪威Zylin 公司推出的一款32位开源处理器。

    更多相关内容
  • 为了进一步提高CPU-GPU协同贝叶斯种系发生算法n( MC)3的并发度,本文在n( MC )3算法基础上提出了优化算法,修改算法并行策略,重组计算次序,削弱相邻计算节点之间的依赖关系,增强GPU空闲单元的利用,实现了更高的加速比,...
  • 基于向量融合的GPU算法.pdf
  • 异或逻辑GPU算法的性能分析与优化.pdf
  • NVIDIA的python-GPU算法生态 ︱ RAPIDS 0.10

    千次阅读 2020-02-25 19:55:30
    NVIDIA的python-GPU算法生态 ︱ RAPIDS 0.10 nvidia-rapids︱cuML机器学习加速库 nvidia-rapids︱cuGraph(NetworkX-like)关系图模型 文章目录 RAPIDS RAPIDS定义 rapids背景资料 RAPIDS核心库更新 cuDF cuML...

    随着新版本的推出,RAPIDS 迎来了其推出一周年纪念日。回顾所经历的一年,RAPIDS团队就社区对该项目的关心和支持表示衷心的感谢。此前,RAPIDS获得了其首个BOSSIE奖。非常感谢各位的支持!RAPIDS团队将继续推动端对端数据科学加快发展,达到新高度。

    在这里插入图片描述

    关联文章:

    nvidia-rapids︱cuDF与pandas一样的DataFrame库
    NVIDIA的python-GPU算法生态 ︱ RAPIDS 0.10
    nvidia-rapids︱cuML机器学习加速库
    nvidia-rapids︱cuGraph(NetworkX-like)关系图模型



    RAPIDS

    RAPIDS定义

    RAPIDS,全称Real-time Acceleration Platform for Integrated Data Science,是NVIDIA针对数据科学和机器学习推出的一套开源GPU加速库,基于CUDA-X AI打造,可加速数据准备、模型训练和图分析。

    使用RAPIDS加速库可以实现从数据准备、模型训练到预测整个端到端流程得到GPU的加速支持,大大提升任务的执行效率,在模型精度方面实现突破的同时降低基础架构TCO。

    CUDNN已经成为GPU加速深度学习框架的标准加速库。RAPIDS(如下图)提供的cuDF、cuML和CuGraph则提供了对数据准备、机器学习算法以及图分析的GPU加速库。

    在这里插入图片描述

    RAPIDS支持轻量级大数据框架DASK,使得任务可以获得多GPU、多节点的GPU加速支持。

    RAPIDS以数据准备为起点,引入新型 GPU 数据框架 (cuDF),进而能实现并行化数据加载和数据操作,充分利用 NVIDIA GPU 上的大型高带宽显存。 cuDF 为数据科学家提供了简单易用且基于 Python 的工具集,可以替换其已十分熟悉的pandas 工具集。数据科学家无需从头学习 NVIDIA CUDA 技术,只需要对现有代码做出极少量更改,便能够大幅提速数据准备,使其不再受限于 CPU 或 CPU 与内存之间的输入输出。

    RAPIDS 还引入了不断发展壮大的全新 GPU 加速 ML 算法(cuML) 库,当中包括 XGBoost 等时下热门算法,以及 Kalman、K-means、 KNN、 DBScan、 PCA、 TSVD、 OLS 线性回归、Kalman Filtering 等算法。 ML 算法可产生大量数据传输,至今仍难以实现并行化。随着 GPU 加速的 ML 和 NVIDIA NVLink™ 以及NVSwitch 架构陆续应用于服务器系统,模型训练现可轻松分布于多个 GPU 和多个节点(系统)之间,几乎不会产生延迟,且能避过 CPU 与内存之间的输入输出瓶颈。

    rapids背景资料

    RAPIDS团队在讨论0.10版本时思考了之前Wes Mckinney所写的一篇博客《Apache Arrow和“我最讨厌Pandas的10个问题”》。
    在这里插入图片描述

    简单回顾一下数据科学的历史。十年前,组成今天大数据的许多要素相继出现 。在数据世界的一角,Hadoop生态诞生, Hadoop、Hive、Cassandra、Mahout等都在快速发展。

    在这里插入图片描述

    另一方面,数据科学家口中的PyData堆栈正在兴起。NetworkX(2005)、Numpy(2006)、Scikit-Learn(2007)和Pandas(2008)掀起了一波可用性浪潮;Hadoop、Hive、Cassandra、Flume、Pig和Spark将数据科学扩展到前所未有的水平。它们都在数据科学生态中加入了大量新的库、供应商以及几乎无数种构建数据管道方法,以解决数据科学的问题。

    在这里插入图片描述

    虽然新工具和工作流程的出现激动人心,但很少有人反过来思考在Apache Arrow之前,这些库和框架如何进行有效协作。因此,大多数数据科学家/工程师将大部分时间用于库之间的序列化和反序列化数据(大量副本和转换)。

    RAPIDS结合了人们喜爱的众多库.、社区和框架的诸多优点,以及人们在大规模使用这些工具时经历过的困苦和烦恼。这些正面情绪与负面情绪引导RAPIDS生态解决了Wes讨厌的关于Pandas的10个问题(实际上是11个问题)等。

    “我最讨厌Pandas的10个问题”列表

    • 1、内部构件离“metal”太远;
    • 2、不支持内存映射数据集;
    • 3、数据库和文件摄取/导出性能不佳;
    • 4、Warty缺少数据支持;
    • 5、缺乏内存使用的透明度和RAM管理;
    • 6、对分类数据的支持弱;
    • 7、复杂的分组功能操作既笨拙又缓慢;
    • 8、将数据附加到DataFrame很繁琐且成本高昂;
    • 9、类型元数据有限且不可扩展;
    • 10、急切的评估模式,无查询规划;
    • 11、“慢”,多核算法处理较大数据集的能力有限。

    在这里插入图片描述

    RAPIDS并非独自解决这些问题;人们非常重视“生态”。没有加速发展的数据科学生态,就不可能有RAPIDS。首先,RAPIDS是基于 Apache Arrow构建的。Apache Arrow是一个用于内存中数据的跨语言开发平台。如果不是Apache项目及其贡献者,那么RAPIDS的构建将变得更加困难。然后,不要忘了Anaconda、Peter Wang和Travis Oliphant(为我们带来了许多促进其发展的PyData库)以及他们为了鼓励和突出PyData生态性能所做的一切。Numba(2012)为Python生态提供了一个JIT编译器。该编译器还可以针对RAPIDS在我们所有库中都大量使用的GPU。由于能够任意扩展功能并使用纯Python编写用户定义函数(UDF),因此Python生态系统具有许多其他语言所没有的优势。

    另外还有Python原生调度程序Dask(2014)。该程序可在整个Python生态中使用,并几乎与所有调度程序(包括Slurm、Kubernetes和Yarn)存在关联。GoAi(2017)聚集了多位GPU分析领域的开拓者构建RAPIDS基础的原型并制定GPU库之间的通信和互操作标准。最后,在互操作性方面,许多CUDA Python数组和深度学习库(PyTorch、 MxNet、 Chainer、 CuPy和即将推出的 PaddlePaddle)采用DLPack和CUDA_Array_Interface(希望能够有更多)。所有这些在RAPIDS生态中连接的库一起实现了新库的快速创建,例如cuSpatial、pyBlazing、cuXFilter和GFD(下文将作进一步的介绍),并且这种趋势还将继续。

    就我个人而言,这也是我最喜欢RAPIDS的地方 —— 实现了Python生态GPU的民主化,使其他人能够以前所未有的速度构建具有多种功能的高性能库。为了凑满一张“10大”列表,我还要求每个RAPIDS库的领导者说出他们对RAPIDS的喜爱之处(您会发现他们之前一定花了很多时间互相串通回答,因为他们许多人的回答都相同)。

    RAPIDS库十大领先之处

    Keith Kraus:
    ---- 速度 —— 核心功能“靠近metal”;
    ---- GPU生态互操作性;
    ---- PyData生态互操作性;
    ---- 强大的内存布局语义;
    ---- 低级别访问和控制(用户可以在需要时获取指向其数据的裸指针);
    ---- 开源;
    ---- 深度学习框架集成;
    ---- 遵循已知的PyData 应用编程接口(API);
    ---- 通过BlazingSQL实现的结构化查询语言(SQL)。

    John Zedlewski:
    ---- 我记得以前每天要 花好几个小时等待大型集群上的机器学习工作批量完成,所以每次看到台式机能够在几秒钟内完成如此大型的工作我都很高兴!

    Bartley Richardson:
    ---- 对于专门研究某个领域 (例如网络安全和信息安全)的数据科学家而言,其他Python工具之间的互操作性至关重要。我们不但受益于更快的数据分析(通常是网络安全中的TB+级数据集),同时还能与安全分析人员所依赖的域专属下游Python软件包和API保持互操作性,这真的是太棒了。

    Mark Harris:
    ---- 我们的团队太出色了。RAPIDS团队是一个由充满热情、能力出众的人组成的一支多元化分布式团队。尽管我们分布在世界各地,我们中的许多人在家工作,但我们的团队可以通过公开交流和合作建立新的功能并以惊人的速度解决问题。每个人都积极地提供帮助,而经常逼迫自己接触自己专业领域以外的东西以学习新的技能。我们觉得做这件事情十分快乐。

    Brad Rees:
    ---- ETL、数据工程、机器学习和图表分析之间实现了无缝过渡。RAPIDS让数据科学家只需要考虑分析即可,而无需考虑如何在工具之间移动数据。

    Matt Rocklin:
    ---- 我喜欢RAPIDS符合标准的Python API,这样就可以轻松地与现有的Python生态系统集成;
    ---- 我喜欢RAPIDS为许多其他Python软件包做出了贡献,而不是只管自己;
    ---- 我喜欢RAPIDS让用户可以轻松、快速地尝试各种硬件,而不必学习新系统;
    ---- 我喜欢RAPIDS使新科学领域的发展速度加快,而不仅仅是增加深度学习功能。


    RAPIDS核心库更新

    cuDF

    cuDF在过去一年中的发展速度非常之快。每个版本都加入了令人兴奋的新功能、优化和错误修复。0.10版本也不例外。cuDF 0.10版本的一些新功能包括 groupby.quantile()Series.isin()、从远程/云文件系统(例如hdfs、gcs、s3)读取、Series和DataFrame isna()、按分组功能中的任意长度Series分组 、Series 协方差和Pearson相关性以及从DataFrame / Series .values 属性返回 CuPy数组。此外,apply UDF函数API经过了优化,并且加入了通过.iloc访问器的收集和散播方法。

    除了提供所有上述出色的功能、优化和错误修复之外,cuDF 0.10版本还花费大量的精力构建未来。该版本将cuStrings存储库合并到cuDF中,并为合并两个代码库做好了准备,使字符串功能能够被更紧密地集成到cuDF中,以此提供更快的加速和更多的功能。此外,RAPIDS添加了cuStreamz元数据包,因此可以使用cuDF和Streamz库简化GPU加速流处理。cuDF继续改进其Pandas API兼容性和Dask DataFrame互操作性,使我们的用户可以最大程度地无缝使用cuDF。

    在幕后,libcudf的内部架构正在经历一次重大的重新设计。0.10版本加入了最新的cudf :: column和cudf :: table类,这些类大大提高了内存所有权控制的强健性,并为将来支持可变大小数据类型(包括字符串列、数组和结构)奠定了基础。由于已构建对整个libcudf API中的新类的支持,这项工作将在下一个版本周期中继续进行。此外,libcudf 0.10添加了许多新的API和算法,包括基于排序、支持空数据的分组功能、分组功能分位数和中位数、cudf :: unique_count,cudf :: repeat、cudf :: scatter_to_tables等。与以往一样,此版本还包括许多其他改进和修复。

    RAPIDS内存管理器库RMM也正在进行一系列重组。这次重组包括一个基于内存资源的新架构,该架构与C ++ 17 std :: pmr :: memory_resource大多兼容。这使该库更容易在公共接口之后添加新类型的内存分配器。0.10还用Cython取代了CFFI Python绑定,从而使C ++异常可以传播到Python异常,使更多可调整的错误被传递给应用程序。下一个版本将继续提高RMM中的异常支持。

    最后,你会注意到cuDF在这个版本中速度有了显著提升,包括join(最多11倍)、gather和scatter on tables(速度也快2-3倍)的大幅性能改进,以及更多如图5所示的内容。
    在这里插入图片描述
    图5:单个NVIDIA Tesla V100(立即免费试用) GPU与双路Intel Xeon E5–2698 v4 CPU(20核)上的cuDF vs Pandas加速

    cuML 和 XGBoost

    RAPIDS团队开始为GPU加速XGBoost(最流行的梯度渐变决策树库之一)做出贡献时承诺将所有改进上游移至主存储库而不是创建长期运行的fork。RAPIDS团队高兴地宣布,0.10版本随附一个完全基于XGBoost主分支的XGBoost conda软件包。这是一个快照版本,该版本包含即将发布的1.0.0 XGBoost版本中的许多功能。它支持将数据从cuDF DataFrames加载到XGBoost时的透明性,并且提供更加简洁的全新Dask API选项(详细信息请参见XGBoost存储库)。目前已弃用较旧的Dask-XGBoost API,但它仍可以与RAPIDS 0.10配合使用。为了简化下载,目前XGBoost的conda软件包(rapids-xgboost)已被包含在主要的Rapidsai conda通道中,如果你安装了RAPIDS conda元软件包,就会自动安装 conda软件包(详细信息请参见入门页面)。

    在这里插入图片描述
    对比:Intel Xeon E5–2698 v4 CPU(20核)与NVIDIA V100

    RAPIDS机器学习库cuML 扩展后支持多种流行的机器学习算法。cuML现在包含一个支持向量机分类器(SVC)模型,其速度比同等CPU版本快300倍。它在CannyLabs的GPU加速工作基础上建立一个加速TSNE模型,该模型提供最受欢迎的高性能降维方法,同时其运行速度比基于CPU的模型快1000倍。我们随机森林模型的每个版本都在不断改进,并且现在包含了一个分层算法,其速度比scikit-learn的随机森林训练快30倍。

    从cuML 训练到推理

    不仅是训练,要想真正在GPU上扩展数据科学,也需要加速端到端的应用程序。cuML 0.9 为我们带来了基于GPU的树模型支持的下一个发展,包括新的森林推理库(FIL)。FIL是一个轻量级的GPU加速引擎,它对基于树形模型进行推理,包括梯度增强决策树和随机森林。使用单个V100 GPU和两行Python代码,用户就可以加载一个已保存的XGBoost或LightGBM模型,并对新数据执行推理,速度比双20核CPU节点快36倍。在开源Treelite软件包的基础上,下一个版本的FIL还将添加对scikit-learn和cuML随机森林模型的支持。

    在这里插入图片描述
    图3:推理速度对比,XGBoost CPU vs 森林推理库 (FIL) GPU
    在这里插入图片描述

    图4:XGBoost CPU和FIL推理时间随批处理大小的增加而扩展(越低越好)

    将来,cuML还将支持GPU上其他算法的推理。

    Dask

    Dask在HPC和Kubernetes系统上实现了标准化部署,包括支持与客户端分开运行调度程序,从而使用户可以在本地笔记本计算机上轻松地启动远程集群上的计算。Dask还为使用云但无法采用Kubernetes的机构添加了AWS ECS原生支持。

    UCX上的高性能通信开发仍在继续,包括使用NVLINK的单个节点中的GPU以及使用InfiniBand的集群中的多个节点。RAPIDS团队已将ucx-py绑定重写,使其变得更简洁,并解决了跨Python-GPU库(如Numba、RAPIDS和UCX)共享内存管理方面的多个问题。

    cuGraph

    cuGraph已在将领先的图形框架集成到一个简单易用的接口方面迈出了新的一步。几个月前,RAPIDS收到了来自佐治亚理工学院的Hornet副本,并将其重构和重命名为cuHornet。这一名称更改表明,源代码已偏离Georgia Tech基准并体现了代码API和数据结构与RAPIDS cuGraph的匹配。cuHornet的加入提供了基于边界的编程模型、动态数据结构以及现有分析的列表。除了核心数函数之外,可用的前两个cuHornet算法是Katz centrality 和K-Cores。

    cuGraph是RAPIDS的图形分析库,针对cuGraph我们推出了一个由两个新原语支持的多GPU PageRank算法:这是一个COO到CSR的多GPU数据转换器,和一个计算顶点度的函数。这些原语会被用于将源和目标边缘列从Dask Dataframe转换为图形格式,并使PageRank能够跨越多个GPU进行缩放。

    下图显示了新的多GPU PageRank算法的性能。与之前的PageRank基准运行时刻不同,这些运行时刻只是测量PageRank解算器的性能。这组运行时刻包括Dask DataFrame到CSR的转换、PageRank执行以及从CSR返回到DataFrame的结果转换。平均结果显示,新的多GPU PageRank分析比100节点Spark集群快10倍以上。

    在这里插入图片描述
    图1:cuGraph PageRank在不同数量的边缘和NVIDIA Tesla V 100上计算所用的时间

    下图仅查看Bigdata数据集、5000万个顶点和19.8亿条边,并运行HiBench端到端测试。HiBench基准运行时刻包括数据读取、运行PageRank,然后得到所有顶点的得分。此前,HiBench分别在10、20、50和100个节点的Google GCP上进行了测试。

    在这里插入图片描述
    图2:5千万边缘端到端PageRank运行时刻,cuGraph PageRank vs Spark Graph(越低越好)

    cuGraph 0.9还包括了一个新的单GPU强连接组件功能。

    cuSpatial

    RAPIDS 0.10还包括cuSpatial的初始版本。cuSpatial是一个高效C ++库,它被用于使用CUDA和cuDF的GPU加速地理空间分析。该库包含供数据科学家使用的python绑定。cuSpatial比现有算法实现的速度提高了50倍以上并且还在开发中。cuSpatial的初始版本包括用于计算轨迹聚类、距离和速度、hausdorff和hasrsine距离、空间窗口投影、多边形中的点以及窗口相交的GPU加速算法。在未来版本中,将有计划地添加shapefile支持和四叉树索引。

    在这里插入图片描述

    cuDataShader

    发布该RAPIDS版本的同时,RAPIDS还发布了cuDataShader GPU加速和cuDF支持端口。该端口用于高性能的Datashader。凭借快速、大规模的数据可视化功能及其围绕python的设计,Datashader非常适合与GPU驱动的viz一起使用。我们的第一个版本实现了大约50倍的速度。基于这些结果,将在下一个版本中将GPU功能加入到Datashader本身 !因此请继续关注该产品。如果您想尝试,最简单的方法就是在我们的另一个Viz库cuXfilter中使用它。

    在这里插入图片描述

    cuXfilter

    cuXfilter被用于支持我们的按揭虚拟化演示(新的链接位于此处),在经过完全重构后,其交叉过滤仪表板的安装和创建变得更加简单,而所有这些工作都可以通过python笔记本计算机完成!由于网络上有许多出色的可视化库,因此我们一般不创建自己的图表库,而是通过更快的加速、更大的数据集和更好的开发用户体验来增强其他图表库,这是为了消除将多个图表互连到GPU后端的麻烦,使你可以更快地以可视化方式浏览数据。

    RAPIDS社区

    用户对生态的贡献是最大的。BlazingSQL刚刚发布了V0.4.5,该版本在GPU上的运行速度更快,并且加入了新的基准测试。和GCP上的TPC-H查询从本地NVME和GCS提取数据的情况相比,该基准测试能够查询600M行。ensemblecap.ai的Ritchie Ng发布了使用RAPIDS cuDF的分数差分(GFD)GPU 实现方法,该实现方法的速度比CPU高出100倍以上。

    在接下来的几个月时间,RAPIDS工程团队将在全球各地的活动、会议和编程马拉松上进行演示并提供教程。加入我们的GTC DC、PyData NYC和PyData LA。RAPIDS团队希望与你共同努力,不断完善RAPIDS。


    阿里云GPU云服务器现已支持NVIDIA RAPIDS加速库

    支持实例

    阿里云目前支持RAPIDS的实例规格有GN6i(Tesla T4(立即免费试用))、GN6v(Tesla V100(立即免费试用))、GN5(Tesla P100)和GN5i(Tesla P4)。

    如何在GPU实例上使用RAPIDS加速库

    关于如何在阿里云GPU实例上基于NGC环境使用RAPIDS加速库,请参考文档:《在GPU实例上使用RAPIDS加速机器学习任务》

    按照上述文档,可以运行一个单机的GPU加速的数据预处理+训练的XGBoost Demo,并对比GPU与CPU的训练时间。

    用户也可以通过选择更多的数据量和GPU个数来验证多GPU的支持。

    后续阿里云还会继续提供更多的RAPIDS加速的最佳实践。


    参考文献

    RAPIDS 0.10现已推出!数据科学数十载的成果,人见人爱
    超级公开课第17讲 | 开源软件平台RAPIDS如何加速数据科学
    RAPIDS 0.9 现已推出:构建了许多新的算法

    展开全文
  • 针对SIFT特征提取算法过程复杂且实时性低的缺陷,提出了一种基于GPU的实时尺度不变特征变换( Scale-invariant feature transform,SIFT)的优化算法— CUDA OpTImized SIFT( Cosift)。该算法首先利用CUDA流并发...
  • GPU-压缩在 GPU 上运行的数据压缩算法示例。 目前,所有示例都使用 Microsoft C++ AMP。 Accelerators :枚举所有加速器并打印它们的所有属性。 直方图:256-bin 直方图(即字节频率)。 速度为 15 GB/s,我希望在...
  • L-BFGS-B(cuLBFGSB)的GPU实现cuLBFGSB是用于非线性实现算法GPU实现(使用NVIDIA CUDA)的开源库,名为有限内存Broyden-Fletcher-Goldfarb-Shanno(带边界)(L-BFGS-B)。 它是跨平台的(Windows和Linux),并...
  • 算法工程师面试宝典

    2019-02-27 14:28:50
    接近400页的文档,包含机器学习领域基本所有门类算法的重点内容。
  • 协议特征识别技术中用到了一种重要的LCS算法,它是一种字符串比对算法,提取出字符串中的最长连续公共子串。然而,通过理论分析和实验表明:这个查找过程...实验结果表明,GPU下LCS算法的运行效率比CPU有了显著的提高。
  • CUDA学习笔记(LESSON3)——GPU基本算法(Part I) CUDA学习笔记(LESSON4)——GPU基本算法(Part II) CUDA学习笔记(LESSON5)——GPU优化 CUDA学习笔记(LESSON7)——常用优化策略&动态并行化 GPU...

    CUDA系列笔记

    CUDA学习笔记(LESSON1/2)——架构、通信模式与GPU硬件

    CUDA学习笔记(LESSON3)——GPU基本算法(Part I)

    CUDA学习笔记(LESSON4)——GPU基本算法(Part II)

    CUDA学习笔记(LESSON5)——GPU优化

    CUDA学习笔记(LESSON7)——常用优化策略&动态并行化


    GPU基本算法(Part I)

    步骤复杂度(step complexity)与工作量复杂度(work complexity)

    我们在讨论串行程序的算法复杂度是往往用时间复杂度这个指标衡量,也就是执行指令的条数,因为对于CPU来说,它运行的时间是与所执行指令的条数成正比的。而到并行算法中我们会考虑两个指标:step complexity与work complexity。step complexity指的是线程执行的步骤总共有多少,work complexity指的是考虑所有线程的工作量后计算出的复杂度。正是因为GPU具有并行计算的优势,使得许多工作我们可以同时完成,这就导致了程序的时间复杂度不再与work complexity相关,而是与step complexity相关

     

    归约(Reduce)

    Reduce要求输入一组元素,与一个二元操作符,这个二元操作符满足操作的结合性(例如加号),它的操作就是遍历这组元素,对每两个元素进行操作符运算。

    我们可以实现reduce的串行版本,也就是最简单的累加操作,这个操作的step complexity与work complexity都是O(n)。显然这不适合GPU进行运算。

    为了解决这个问题,我们需要reduce的并行版本,由于操作符具有结合性,因此我们可以通过结合不同的元素来达到相同的结果。我们采用二分的思想很容易得到下图所示的这种算法,这种算法的step complexity为O(logn),work complexity仍是原来的O(n),因为虽然步骤减少了,但是总共进行的操作数是不变的。

     

    扫描(Scan)

    scan的操作有点类似reduce,它的作用对当前元素之前的所有元素进行操作符运算(例如相加),之后输出。scan在并行世界中非常有用,具体的例子我在下一个博客再写。

    scan除了像reduce要求输入的元素与一个二元操作符以外还要求一个标识元素(identity element),一个元素与标识元素进行操作会得到他的本身。这个元素主要作为第一个输入元素的输出。

    scan一般分为两种:exclusive scan和inclusive scan。顾名思义,exclusive就是进行操作符运算的所有元素不包括当前输入元素,inclusive就是进行操作符运算的所有元素包括当前输入元素。当我们将scan算法的时候,如果我们仔细去想,我们似乎很难想到它在并行世界中是如何实现的。

    在看dalao的算法们之前我们先来看看一种比较蠢的算法。既然scan是对输入元素之前的所有元素进行reduce运行,那我们就给每一个元素安排一个线程,来计算它之前元素的归约结果,这种方法也确实是一种并行的实现啊。但是我们来分析一下它的复杂度呢。我们会发现它的step complexity为O(logn),嗯...看起来还不错。但是work complexity确是O(n^2),这就不太令人满意了。

    下面来看看dalao们的想法,我们主要说两种,一种是Hillis&Steele的算法,一种是Blelloch的算法,其中前者在step complexity上表现得更好,而后者在work complexity上表现更好。

    Hillis&Steele

    以下就是Hillis&Steele的算法,它的结果是inclusive的,它的主要思想就是将每个元素与右边相邻的第1个元素相加,得到一组新的元素,再将每个元素与右边相邻的第2个元素相加,如此反复一直到将每个元素与右边相邻的第logn个元素相加以后输出的就是最终的inclusive scan的结果。这种算法的step complexity是O(logn),work complexity是O(nlogn),我们可以看出这种算法与前一种算法相比提升了work complexity的性能。

    Blelloch

    以下是Blelloch的算法,它的结果是exclusive的,这个算法包括两个部分:reduce与downsweep。downsweep的操作已经在下图右方给出。这种算法的复杂度为:reduce与downsweep的step分别有logn步,reduce的work complexity为O(n),downsweep的work complexity也为O(n),因此合起来Blelloch的算法step complexity为O(2logn),work complexity为O(2n)。

     

    因此我们最终可以得出结论,在渐进的意义上,如果考虑常数项的影响,Hillis&Steele的算法的step complexity为O(logn)是要优于Blelloch算法的O(2logn),而work complexity上面,Blelloch算法的O(2n)优于Hillis&Steele算法的O(nlogn)。

     

    直方图(Histogram)

    Histogram就是我们平时理解的直方图,也就是把输入数据进行分类,放到不同的计数器中,不同的计数器代表不同的区间范围,最终将计数器的值进行输出。我们将这个计数器称作bin。让我们想想办法如何去实现histogram呢?

    第一种方法是最容易想的,就是bin放在global memory中,开启等同于元素个数的线程来读取数据,然后写入bin中。但这会出现一个严重的问题,就是线程冲突,这个问题我们在上一章已经讨论过,解决的方法就是采用atomic操作,来保护memory。这种方法速度严重受限于bin的数目,当bin比较少的时候,大多数线程不得不处在等待中,这大大地浪费了GPU的资源。因此我们说这并不是一种很好的方法。

    第二种实现方法就是我们在每一个线程中开辟一个local histogram,这样子就避免了对公共内存访问的冲突,在每个线程各自执行完自己的任务以后我们再把local histogram用reduce的方法加起来,合成最终的histogram

     

    第三种方法是用sort+reduce来实现,我们给每一个元素建立一个map,key值为bin的索引,value值为二元值,代表这个元素归属这个bin中,之后我们用对其以key值的顺序大小进行排序,排序之后我们就可以用reduce方法计算出每个bin中有多少个元素了,注意这个时候元素的存储是连续的,因此在访问的时候也具有很高的效率。

    当然我们也可以将这三种方法结合起来使用,以满足不同场景的不同需求。

     

     

    展开全文
  • 使用GPU并行化遗传算法,并行方式为粗粒度式并行,开发环境为ubuntu16.04;最终计算结果相比于传统的遗传算法,在结果精度差不多的情况下,时间约为传统方法的五分之一
  • GPU并行算法

    2018-10-15 18:08:44
    里面包含Parellel Prefix Sum算法,非常有利于GPU编程,可以加速程序运行
  • 针对传统的环境光遮挡算法中不能自适应的问题,提出了基于GPU自适应的环境遮挡算法.该算法充分利用了GPU并行计算技术和离屏渲染技术,快速计算出适合所载入场景的自适应步长;并将传统环境遮挡采样方法和抖动采样的...
  • CUDA系列学习(五)GPU基础算法: Reduce, Scan, Histogram

    万次阅读 多人点赞 2015-06-25 11:19:39
    这一讲中我们将介绍3个基础的GPU算法:reduce,scan,histogram,它们在并行算法中非常常用,我们在本文中分别就其功能用处,串行与并行实现进行阐述。 1. Task complexitytask complexity包括step complexity...
    喵~不知不觉到了CUDA系列学习第五讲,前几讲中我们主要介绍了基础GPU中的软硬件结构,内存管理,task类型等;这一讲中我们将介绍3个基础的GPU算法:reduce,scan,histogram,它们在并行算法中非常常用,我们在本文中分别就其功能用处,串行与并行实现进行阐述。
    ———-

    1. Task complexity

    task complexity包括step complexity(可以并行成几个操作) & work complexity(总共有多少个工作要做)。
    e.g. 下面的tree-structure图中每个节点表示一个操作数,每条边表示一个操作,同层edge表示相同操作,问该图表示的task的step complexity & work complexity分别是多少。

    tree operation

    Ans:
    step complexity: 3;
    work complexity: 6。
    下面会有更具体的例子。




    2. Reduce

    引入:我们考虑一个task:1+2+3+4+…
    1) 最简单的顺序执行顺序组织为((1+2)+3)+4…
    2) 由于operation之间没有依赖关系,我们可以用Reduce简化操作,它可以减少serial implementation的步数。


    2.1 what is reduce?

    Reduce input:

    1. set of elements
    2. reduction operation
      1. binary: 两个输入一个输出
      2. 操作满足结合律: (a@b)@c = a@(b@c), 其中@表示operator
        e.g +, 按位与 都符合;a^b(expotentiation)和减法都不是

    2. add_tree.png



    2.1.1 Serial implementation of Reduce:

    reduce的每一步操作都依赖于其前一个操作的结果。比如对于前面那个例子,n个数相加,work complexity 和 step complexity都是O(n)(原因不言自明吧~)我们的目标就是并行化操作,降下来step complexity. e.g add serial reduce -> parallel reduce。


    2.1.2 Parallel implementation of Reduce:

    3. parallel_add.png

    也就是说,我们把step complexity降到了 log2n

    举个栗子,如下图所示:
    example



    那么如果对 210 个数做parallel reduce add,其step complexity就是10. 那么在这个parallel reduce的第一步,我们需要做512个加法,这对modern gpu不是啥大问题,但是如果我们要对 220 个数做加法呢?就需要考虑到gpu数量了,如果说gpu最多能并行做512个操作,我们就应将 220 个数分成1024*1024(共1024组),每次做 210 个数的加法。这种考虑task规模和gpu数量关系的做法有个理论叫Brent’s Theory. 下面我们具体来看:

    4. brent's theory.png

    也就是进行两步操作,第一步分成1024个block,每个block做加法;第二步将这1024个结果再用1个1024个thread的block进行求和。kernel code:

    __global__ void parallel_reduce_kernel(float *d_out, float* d_in){
        int myID = threadIdx.x + blockIdx.x * blockDim.x;
        int tid = threadIdx.x;
    
        //divide threads into two parts according to threadID, and add the right part to the left one, lead to reducing half elements, called an iteration; iterate until left only one element
        for(unsigned int s = blockDim.x / 2 ; s>0; s>>=1){
            if(tid<s){
                d_in[myID] += d_in[myID + s];
            }
            __syncthreads(); //ensure all adds at one iteration are done
        }
        if (tid == 0){
            d_out[blockIdx.x] = d_in[myId];
        }
    }



    Quiz: 看一下上面的code可以从哪里进行优化?

    Ans:我们在上一讲中提到了global,shared & local memory的速度,那么这里对于global memory的操作可以更改为shared memory,从而进行提速:

    __global__ void parallel_shared_reduce_kernel(float *d_out, float* d_in){
        int myID = threadIdx.x + blockIdx.x * blockDim.x;
        int tid = threadIdx.x;
        extern __shared__ float sdata[];
        sdata[tid] = d_in[myID];
        __syncthreads();
    
        //divide threads into two parts according to threadID, and add the right part to the left one, lead to reducing half elements, called an iteration; iterate until left only one element
        for(unsigned int s = blockDim.x / 2 ; s>0; s>>=1){
            if(tid<s){
                sdata[tid] += sdata[tid + s];
            }
            __syncthreads(); //ensure all adds at one iteration are done
        }
        if (tid == 0){
            d_out[blockIdx.x] = sdata[myId];
        }
    }


    优化的代码中还有一点要注意,就是声明的时候记得我们第三讲中说过的kernel通用表示形式:

    kernel<<<grid of blocks, block of threads, shmem>>>
    最后一项要在call kernel的时候声明好,即:
    parallel_reduce_kernel<<<blocks, threads, threads*sizeof(float)>>>(data_out, data_in);


    好,那么问题来了,对于这两个版本(parallel_reduce_kernel 和 parallel_shared_reduce_kernel), parallel_reduce_kernel比parallel_shared_reduce_kernel多用了几倍的global memory带宽? Ans: 分别考虑两个版本的读写操作:
    parallel_reduce_kernel
    Times Read Ops Write Ops
    1 1024 512
    2 512 256
    3 256 128
    n 1 1
    parallel_shared_reduce_kernel
    Times Read Ops Write Ops
    1 1024 1

    所以,parallel_reduce_kernel所需的带宽是parallel_shared_reduce_kernel的3倍


    3. Scan

    3.1 what is scan?

    • Example:

      • input: 1,2,3,4
      • operation: Add
      • ouput: 1,3,6,10(out[i]=sum(in[0:i]))
    • 目的:解决难以并行的问题

    拍拍脑袋想想上面这个问题O(n)的一个解法是out[i] = out[i-1] + in[i].下面我们来引入scan。

    Inputs to scan:

    1. input array
    2. 操作:binary & 满足结合律(和reduce一样)
    3. identity element [I op a = a], 其中I 是identity element
      quiz: what is the identity for 加法,乘法,逻辑与,逻辑或?
      Ans:
    opIdentity
    加法0
    乘法1
    逻辑或||False
    逻辑与&&True



    3.2 what scan does?

    I/Ocontent
    input[ a0 a1 a2 an ]
    output[ I a0 a0a1 a0a1 an ]

    其中 是scan operator,I 是 的identity element




    3.2.1 Serial implementation of Scan

    很简单:

    int acc = identity;
    for(i=0;i<elements.length();i++){
        acc = acc op elements[i];
        out[i] = acc;
    }

    work complexity: O(n)
    step complexity: O(n)

    那么,对于scan问题,我们怎样对其进行并行化呢?



    3.2.1 Parallel implementation of Scan

    考虑scan的并行化,可以并行计算n个output,每个output元素i相当于 a0a1 ai ,是一个reduce operation。

    Q: 那么问题的work complexity和step complexity分别变为多少了呢?
    Ans:

    • step complexity:
      取决于n个reduction中耗时最长的,即 O(log2n)
    • work complexity:
      对于每个output元素进行计算,总计算量为0+1+2+…+(n-1),所以复杂度为 O(n2) .

    可见,step complexity降下来了,可惜work complexity上去了,那么怎么解决呢?这里有两种Scan算法:

    more step efficiencymore work efficiency
    hillis + steele (1986)
    blelloch (1990)




    1. Hillis + Steele

      对于Scan加法问题,hillis+steele算法的解决方案如下:

    hillis + steele

    即streaming’s
    step 0: out[i] = in[i] + in[i-1];
    step 1: out[i] = in[i] + in[i-2];
    step 2: out[i] = in[i] + in[i-4];
    如果元素不存在(向下越界)就记为0;可见step 2的output就是scan 加法的结果(想想为什么,我们一会再分析)。

    那么问题来了。。。
    Q: hillis + steele算法的work complexity 和 step complexity分别为多少?

    Hillis + steele Algorithm complexity
    log(n) O(n) O(n) O(nlogn) O(n^2)
    work complexity
    step complexity

    解释:

    为了不妨碍大家思路,我在表格中将答案设为了白色,选中表格可见答案。

    1. step complexity:
      因为第i个step的结果为上一步输出作为in, out[idx] = in[idx] + in[idx - 2^i], 所以step complexity = O(log(n))
    2. work complexity:
      workload = (n1)+(n2)+(n4)+... ,共有 log(n) 项元素相加,所以可以近似看做一个矩阵,对应上图,长 log(n) , 宽n,所以复杂度为 nlog(n)




    2 .Blelloch

    基本思路:Reduce + downsweep

    还是先讲做法。我们来看Blelloch算法的具体流程,分为reduce和downsweep 两部分,如图所示。

    这里写图片描述



    1. reduce部分:
      每个step对相邻两个元素进行求和,但是每个元素在input中只出现一次,即window size=2, step = 2的求和。
      Q: reduce部分的step complexity 和 work complexity?
      Ans:

      Reduce part in Blelloch
      log(n) O(n) O(n) O(nlogn) O(n^2)
      work complexity
      step complexity

      我们依然将答案用白色标出,请选中看答案。

    2. downsweep部分:
      简单地说,downsweep部分的输入元素是reduce部分镜面反射的结果,对于每一组输入in1 & in2有两个输出,左边输出out1 = in2,右边输出out2 = in1 op in2 (这里的op就是reduce部分的op),如图:


    downsweep operation

    如上上图中的op为加法,那举个例子就有:in1 = 11, in2 = 10, 可得out1 = in2 = 10, out2 = in1 + in2 = 21。由此可以推出downsweep部分的所有value,如上上图。
    这里画圈的元素都是从reduce部分直接“天降”(镜面反射)过来的,注意,每一个元素位置只去reduce出来该位置的最终结果,而且由于是镜面反射,step层数越大的reduce计算结果“天降”越快,即从reduce的“天降”顺序为

    36
    10
    3, 11
    1, 3, 5, 7

    Q: downsweep部分的step complexity 和 work complexity?
    And:downsweep是reduce部分的mirror,所以当然和reduce部分的complexity都一样啦。

    综上,Blelloch方法的work complexity为 O(n) ,step 数为 2log(n) .这里我们可以看出相比于Hillis + Steele方法,Blelloch的总工作量更小。那么问题来了,这两种方法哪个更快呢?

    ANS:这取决于所用的GPU,问题规模,以及实现时的优化方法。这一边是一个不断变化的问题:一开始我们有很多data(work > processor), 更适合用work efficient parallel algorithm (e.g Blelloch), 随着程序运行,工作量被减少了(processor > work),适合改用step efficient parallel algorithm,这样而后数据又多起来啦,于是我们又适合用work efficient parallel algorithm…


    总结一下,见下表为每种方法的complexity,以及适于解决的问题:

    serialHillis + SteeleBlelloch
    workO(n)O(nlogn) O(n)
    stepnlog(n)2*log(n)
    512个元素的vector
    512个processor
    一百万的vector
    512个processor
    128k的vector
    1个processor





    4. Histogram

    4.1. what is histogram?

    顾名思义,统计直方图就是将一个统计量在直方图中显示出来。

    4.2. Histogram 的 Serial 实现:

    分两部分:1. 初始化,2. 统计

    for(i = 0; i < bin.count; i++)
        res[i] = 0;
    for(i = 0; i<nElements; i++)
        res[computeBin(i)] ++;

    4.3. Histogram 的 Parallel 实现:

    1. 直接实现:

    kernel:

    __global__ void naive_histo(int* d_bins, const int* d_in, const in BIN_COUNT){
        int myID = threadIdx.x + blockDim.x * blockIdx.x;
        int myItem = d_in[myID];
        int myBin = myItem % BIN_COUNT;
        d_bins[myBin]++;
    }

    来想想这样有什么问题?又是我们上次说的read-modify-write问题,而serial implementation不会有这个问题,那么想实现parallel histogram计算有什么方法呢?

    法1. accumulate using atomics
    即,将最后一句变成
    atomicAdd(&(d_bins[myBin]), 1);
    但是对于atomics的方法而言,不管GPU多好,并行线程数都被限制到histogram个数N,也就是最多只有N个线程并行。


    法2. local memory + reduce
    设置n个并行线程,每个线程都有自己的local histogram(一个长为bin数的vector);即每个local histogram都被一个thread顺序访问,所以这样没有shared memory,即便没有用atomics也不会出现read-modify-write问题。
    然后,我们将这n个histogram进行合并(即加和),可以通过reduce实现。

    法3. sort then reduce by key
    将数据组织成key-value对,key为histogram bin,value为1,即

    key21121022
    value 11111111

    将其按key排序,形成:

    key01112222
    value 11111111

    然后对相同key进行reduce求和,就可以得到histogram中的每个bin的总数。


    综上,有三种实现paralle histogram的方法:
    1. atomics
    2. per_thread histogram, then reduce
    3. sort, then reduce by key


    5. 总结:

    本文介绍了三个gpu基础算法:reduce,scan和histogram的串行及并行实现,并巩固了之前讲过的gpu memory相关知识加以运用。

    展开全文
  • GPU加速的超级平滑器算法(随附论文,“ GPU启用的搜索形状未知的周期性信号”正在审查中)。 代码作者:Mike Gowanlock...如本文所述,GPU算法允许处理单个对象(例如,用户要处理较大的时间序列或需要搜索大量的频率
  • 分析了K-means算法GPU上实现并行计算的可能性,并在GTX8800 GT显卡上实现,研究了GPU的存储访问机制,在对数据进行合理组织基础上对算法进行改进,避免了存储体冲突的产生,提高了算法的健壮性。研究结果证明该方法在...
  • 基于GPU的AES算法实现

    2020-10-22 09:44:02
    近几年图形处理器GPU的通用...本文利用GPU来加速AES算法,即利用GPU作为CPU的协处理器,将AES算法GPU上实现,以提高计算的吞吐量。最后在GPU和CPU平台上进行了实验,获得了GPU的加速结果,并对实验结果进行了优化。
  • 超声成像算法的仿真对于成像系统的研究和设计有重要的意义。我们在分析波束形成算法和图形...对基于GPU和基于CPU的仿真方案进行了对比实验,实验所得成像图像完全一致。通过实验证明新的超声成像算法仿真方案是可行的。
  • CUDA-quicksort 是一种基于 GPU 的快速排序算法实现。 CUDA-quicksort 旨在利用现代 NVIDIA GPU 的计算能力。 “文献中介绍了两种基于 GPU 的快速排序实现:GPU 快速排序,一种计算统一设备架构 (CUDA) 迭代实现,...
  • opencv hog算法实现

    2015-09-01 09:35:23
    菜鸟级别,实现了opencv自带算法hog行人检测,仅供各位初学者参考,各位大神请飘过。
  • 针对FDK算法重建图像异常耗时的问题,提出了一种极坐标反投影...实验结果表明,采用这两种措施实现了FDK算法优化,与传统的FDK算法相比,重建速度提高8倍,采用CUDA技术,实现GPU对其加速,速度提高40倍,且均不产生新的误差。
  • 一种易于硬件实现的嵌入式GPU三角形光栅化算法.pdf
  • 基于CUDA的GPU并行,给出了三种不同的前缀求和算法,第一种是基本的规约并行算法,第二种是采用共享内存优化的GPU并行算法,第三种是采用trust库的前缀求和函数。并且给出了三种方法对比之间的性能差异
  • 算法使用图像上的滑动窗口来生成直方图。 特征向量保存在“GPU_features”下,梯度幅度和角度计算步骤保存在“gradient.txt”中,虽然它并不漂亮:P 安装 从磁盘读取图像需要 。 它已经包含在内。 确保已安装 ...
  • 分析了KNN算法GPU上实现并行计算的可能性,提出了通过使用CUDA实现KNN算法的方案,在研究了GPU对存储访问的机制后,通过设计合理的数据以及对算法的改进,避免存储体冲突的产生,提高了算法的健壮性。研究结果证明...
  • 一个例子:主动反狙击探测猫眼效应↓瞄准镜目标↓检测标记↓有很多种标记算法,其中一种↓原理描述:数据输入:从文件中读取图像数据,记为D初始化:开辟与图像尺寸相同的数据空间,对每个像素顺序标号,生成标号...
  • 关于实现Halcon算法加速的基础知识 详情:https://blog.csdn.net/libaineu2004/article/details/104202063
  • 遗传算法在求解这类组合问题方面明显优于传统算法,同时也提出了许多求解较好路径的交叉算子。在对比分析唐立新提出的两种启发式交叉算法的基础上,提出了一种新的交叉算子。该算子通过判断父代的城市是否相邻来保存...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 104,272
精华内容 41,708
关键字:

gpu算法