﻿ 基于CUDA的Bezier曲线生成算法并行化研究 Research on the Parallelization of Bezier Curve Generation Algorithm Based on CUDA

Computer Science and Application
Vol.08 No.03(2018), Article ID:24275,12 pages
10.12677/CSA.2018.83040

Research on the Parallelization of Bezier Curve Generation Algorithm Based on CUDA

Zhihong Liang1, Fei Dai1*, Peng Cao2, Yuxiang Huang2, Mingming Qin1

1School of Big Data and Intelligent Engineering, Southwest Forestry University, Kunming Yunnan

2School of Software Engineering, Yunnan University, Kunming Yunnan

Received: Mar. 10th, 2018; accepted: Mar. 22nd, 2018; published: Mar. 29th, 2018

ABSTRACT

The Bezier curve is essential for geometric modeling system and graphic software. A method of calculating Bezier curve based on CUDA is proposed. Based on the analysis of the CUDA isomeric computing architecture and the independence of the Bezier curve sampling points, the multiple threads were opened on the GPU to calculate the Bezier curve. According to the characteristic that the control vertex does not change during the calculation of the sampling point, the calculation of the sampling point was optimized at the memory level. The experimental results show that the performance of Bezier curve generation algorithm based on CUDA has been improved remarkably.

Keywords:GPU, Bezier Curve, CUDA

1西南林业大学大数据与智能工程学院，云南 昆明

2云南大学软件学院，云南 昆明

Copyright © 2018 by authors and Hans Publishers Inc.

1. 概述

2. CUDA编程模型

2.1. CUDA概述

CUDA [12] 是NVIDIA公司在2007年提出的一种基于本公司GPU的可以进行通用计算并且编程性较好的编程模型，是一种利用GPU与CPU协同进行计算的编程模型。在CUDA中，CPU被称作主机，GPU被称作设备。为了使开发者可以更快的使用CUDA编程平台进行开发，CUDA的编程语言采用了扩展后的类C语言—CUDA C。使用CUDA C可以直接编写可以运行在GPU上的程序而不需要懂得OpenGL或者Direct3D等API [13] 。在NVIDIA的官方文档CUDA C Programming Guide Version 7.5中，CUDA的核心主要在三个抽象概念：线程组层次结构(a hierarchy of thread groups)，共享内存(shared memories)，障栅同步(barrier synchronization) [3] 。正是由于这些抽象，CUDA可以提供细粒度的线程并行和数据并行。较细粒度的并行线程组成线程块 [3] ，从而使CUDA可以提供粗粒度的任务并行和数据并行。正是由于这些抽象，程序员可以把一些大的计算任务进行数据划分，划分成无数小的数据集合，每个线程对一个小数据集合进行处理，从而提高程序的运行效率。

2.2. CUDA的软件体系结构

CUDA的软件栈是按照层次结构来组织的，如图1所示。CUDA为开发者提供了一套夸平台的支撑软件来方便程序员更加容易和灵活的开发CUDA程序。如图1所示CUDA的软件层次是：CUDA函数库，CUDA运行时API，CUDA驱动API。CUDA库函数是NVIDIA已经写好的一些函数，程序员可以在应用程序中直接调用，从而节约开发时间。而CUDA运行时API和CUDA驱动API实现GPU内存的分配以及核函数 [3] 的启动等一些GPU资源管理的函数接口。

Figure 1. CUDA software architecture diagram

CUDA应用程序代码包含两部分：一部分是运行在GPU上的设备代码 [10] ，一部分是运行在CPU上的主机代码 [14] 。NVCC (NVIDIA C Compiler) [2] 在编译CUDA应用程序时，如图2所示。NVCC根据CUDA关键字把设备代码和主机代码区分开来。NVCC把这部分主机代码(用ANSI C编写的简单代码)发送到标准C或者C++编译器进一步编译，编译后以一个普通的CPU进行的方式进行运行。而用CUDA关键字标记的设备代码通常再由NVCC编译器进一步编译，并在GPU上运行。

2.3. CUDA的硬件体系架构

2.4. CUDA的执行模型

CUDA异构编程架构的硬件由两部分组成，一部分是CPU，也称作主机 [2] (Host)，另一部分是是协处理器(co-processor) GPU，也称作是设备。在CUDA异构系统中可以由一个主机和若干个GPU搭配组成。正如前面我们提到的GPU与CPU各有分工，相互合作。计算量比较小的串行计算和逻辑比较复杂的事务性处理都放在CPU上运行，而运算量比较大，数据依赖性比较小的大规模数据处理放在GPU上运行。运行在GPU上的代码叫做设备代码，也成为内核函数(kernel) [2] 。运行在CPU上的代码成为主机代码。通过主机端调用核函数，那么再设备上就会有大量的线程实体来执行核函数代码。为了管理大量

Figure 2. CUDA C compilation process diagram

2.5. CUDA的存储器模型

GPU的存储器的种类以及层次相比于CPU会非常的复杂，每一种存储器的存取速度以及存储容量都不一样。GPU的存储器包括寄存器存、局部存储器、全局存储器、常量存储器、纹理存储器、共享内存等。在线程网格中，每个线程根据自己的情况所能访问的存储器也不同。在图3中，可以看出每个线

Figure 3. Memory hierarchy diagram

3. Bézier曲线相关理论

3.1. Bézier曲线的定义

$p\left(t\right)=\sum _{i=0}^{n}{P}_{i}{B}_{i,n}\left(t\right),\text{\hspace{0.17em}}\text{\hspace{0.17em}}t\in \left[0,1\right]$ [10] [11] (2.1)

${B}_{i,n}\left(t\right)={C}_{n}^{i}{t}^{i}{\left(1-t\right)}^{n-i}=\frac{n！}{i!\left(n-1\right)!}{t}^{i}{\left(1-t\right)}^{n-i},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left(i=0,1,2,\cdots ,n\right)$ [10] [11] (2.2)

3.2. Bézier曲线的性质

1) 端点性质。

Bézier曲线的起点和终点与控制多边形的起点和终点重合。

2) 切矢量。

Bézier曲线的起点处的切线方向与特征多边形的第一条边走向一样，终点处的切线方向和特征多边形最后一条边走向一样。

3) 对称性。

Figure 4. Three order Bessel curve

4) 凸包性。

5) 几何不变性。

6) 变差缩减性。

4. 基于CUDA的Bézier曲线生成算的设计与实现

4.1. 基于CUDA的Bézier曲线生成算法的描述

1) 在设备上分配用于存储控制顶点以及曲线采样点的设备内存。输入控制顶点以及控制顶点数m，

2) 输入采样点的数N，N的值要是32的整数倍

3) 把控制定点的数据以及计算出的二项式系数传输到设备

4) 启动核函数，启动N/32个线程块，每个线程块32个线程

6) 根据计算的tid来计算以及N的值按照t=(tid/N)来计算t的值

7) 根据t的值以及控制顶点的坐标对Bézier曲线上的所有采样点同时进行计算

8) 把计算好的采样点坐标值传输回主机

9) 释放设备端分配的内存

4.2. 基于CUDA的Bézier曲线生成算法的实现

1) 数据结构设计

typedef struct Point{//结构体Point用于存放点

float x;

float y;

}Point;

2) 设备内存分配

cudaMemcpyToSymbol(dev_cltpoints,host_ctlpoints,sizeof(Point)*M);

cudaMemcpyToSymbol(dev_bin,host_bin,sizeof(float)*M);

Figure 5. GPU calculation sample point diagram

cudaMalloc((void**)dev_points,sizeof(Point)*N);

cudaMemset(dev_points,0,N*sizeof(Point));//把分配的设备内存初始化为0

3) 二项式的计算

$i\in \left[0,n\right]$ 。设置一个设备函数__device__ int computeBin(int n,int i)来计算每个采样点前的二项式的值。

4) Bézier曲线上采样点的计算

computeBezier<<<(N+63)/64,64>>>(dev_points);

5) 最后清理

cudaMemcpy(host_points,dev_points,N*sizeof(Point),cudaMemcpyDeviceToHost);//把计算好的采样点坐标传输回主机缓冲区。

cudaFree(dev_points);//对cudaMalloc()分配的设备内存进行释放。

5. 实验结果以及分析

1) 实验环境如下：

CPU：Intel Core i5-4210M双核处理器

GPU：NVIDA GTX850M DDR3独立显卡

GPU SM数：5

SP/SM：128

GPU SP数：640

2) 实验结果

3) 实验结果分析

6. 结束语

Figure 6. Run time contrast diagram

Research on the Parallelization of Bezier Curve Generation Algorithm Based on CUDA[J]. 计算机科学与应用, 2018, 08(03): 354-365. https://doi.org/10.12677/CSA.2018.83040

1. 1. 白洪涛. 基于GPU的高性能并行算法研究[D]: [博士学位论文]. 长春: 吉林大学, 2010.

2. 2. NVIDIA Corporation. (2015) CUDA C Programming Guide Version 7.5.

3. 3. Jason Sanders, Edward Kandrot. GPU高性能编程—CUDA实战[M]. 北京: 机械工业出版社, 2011.

4. 4. The Regents of the University of Michigan. http://glotzerlab.engin.umich.edu/hoomd-blue/

5. 5. Govindaraju, N.K., Lloyd, B., Wang, W., Lin, M. and Manocha, D. (2004) Fast Computation of Database Operations Using Graphics Processors. Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, 13-18 June 2004, 215-226.

6. 6. 朱鉴, 吴恩华. 基于GPU的球面深度图实时绘制[J]. 计算机学报, 2009, 32(2): 231-240.

7. 7. 杨正龙, 金林, 李蔚清. 基于GPU的图形电磁计算加速算法[J]. 电子学报, 2007, 35(6): 1056-1060.

8. 8. 陈波. 基于CPU-GPU异构平台的性能优化及多核并行编程模型的研究[D]: [硕士学位论文]. 合肥: 中国科学技术大学, 2011.

9. 9. 杨钦, 徐永安, 翟红英. 计算机图形学[M]. 北京: 清华大学出版社, 2005.

10. 10. 仇茹. Bezier曲线曲面造型技术研究[D]: [硕士学位论文]. 芜湖: 安徽师范大学, 2015.

11. 11. 洪玲. 有理Bézier曲线的扩展及应用[D]: [硕士学位论文]. 合肥: 合肥工业大学, 2015.

12. 12. Cook, S. (2012) CUDA Programming: A Developer’s Guide to Parallel Computing with GPUs. Publishing house, location, 147-153.

13. 13. 侯立华. 图像分割方法综述[J]. 科技创新导报, 2008, 22: 249.

14. 14. DavidB. Kirk, Wen-meiW.Hwu. 大规模并行处理器编程实战[M]. 北京: 清华大学出版社, 2013.

15. 15. 施法中, 韩道康. Bézier基函数的导出[J]. 航空学报, 1980, 1(1): 92-98.

16. NOTES

*通讯作者。