动态网格的DSMC方法在GPU上的并行.docx
- 文档编号:13864149
- 上传时间:2023-06-18
- 格式:DOCX
- 页数:14
- 大小:186.44KB
动态网格的DSMC方法在GPU上的并行.docx
《动态网格的DSMC方法在GPU上的并行.docx》由会员分享,可在线阅读,更多相关《动态网格的DSMC方法在GPU上的并行.docx(14页珍藏版)》请在冰点文库上搜索。
动态网格的DSMC方法在GPU上的并行
动态网格的DSMC方法在GPU上的并行
文敏华1+,林新华1,SimonChongWeeSee1,2
1(上海交通大学高性能计算中心,上海200240)
2(NVIDIACorporation)
AGPUBasedParallelMethodForDynamicCollisionGridDSMC
WENMinhua1+,LINXinhua1,SimonChongWeeSee1,2
1(HighPerformanceComputingCenter,ShanghaiJiaoTongUniversity,Shanghai200240,China)
2(NVIDIACorporation)
+Correspondingauthor:
Phn:
+86-139********,E-mail:
wenminhua@
Abstract:
TheDirectSimulationMonteCarlo(DSMC)methodisapowerfulcomputationaltoolinthefieldofrarefiedgasdynamics.However,therearetwomainshortagesofDSMCmethod:
oneiscomplexgriddingprocessingandtheotherisitslargetimeconsumption.ThedynamiccollisiongridDSMCmethodgeneratescollisiongridsadaptivelyaccordingtotheflowfield,whichovercomesthefirstshortage.Fortheothershortage,weportthedynamiccollisiongridDSMCmethodtoGPUusingCUDA.Duringourparallelimplement,themaincomputationisperformedonGPUwhileCPUonlydealswiththeprocessesofinitializationandoutput.Atwo-dimensionalbenchmarkproblemindifferentsizesisusedtodemonstratethecorrectnessoftheparallelization.Theresultsshowthat10+XspeedupisachievedbasedonNVIDIAFermiC2050.Forasamecase,theperformanceonNVIDIA’snewlyreleasedKeplerK20is1.3-1.6xhigherthanthatonFermiC2050.
Keywords:
CUDA,GPU,DynamicCollisionGridDSMC,ParallelSimulation
摘要:
直接模拟蒙特卡罗方法(DirectSimulationMonteCarlo,DSMC)是稀薄气体动力学领域的重要工具。
然而,DSMC方法有两个比较主要的缺点:
一是复杂的网格处理,另一个是庞大的计算量。
使用动态网格的DSMC方法可以根据流场信息,动态生成自适应的碰撞网格,能有效解决前一个缺点;针对后一个缺点,本文则基于动态网格的DSMC方法,使用CUDA编写并行程序,将其移植到GPU上以减少计算时间。
在并行实现中,GPU负责绝大部分的计算,而CPU只负责初始化、结果输出等少量工作。
我们使用一个二维超音速横掠平板问题作为算例验证了并行程序的正确性。
对于不同规模的算例,在NVIDIAFermiC2050之上均获得了10倍以上的加速比;对于相同算例,NVIDIA最新发布的KeplerK20上的速度约为FermiC2050上的1.3-1.6倍。
关键词:
CUDA,GPU,动态网格DSMC,并行模拟
中图法分类号:
TP39 文献标识码:
B
1引言
连续性假设通常用于模拟气体流动,当气体十分稀薄时,粒子的间断效应十分明显,连续性假设不再成立,而应当使用稀薄气体动力学的方法才能得到正确的结果。
用于描述稀薄气体的控制方程为Boltzmann方程:
(1)
它是一个微分积分方程,右端的碰撞项极其复杂,而且方程的变量很多(达7个),因此对于一般的问题求得解析解几乎不可能。
另外,对于如此复杂的方程,数值求解也是十分困难的。
DSMC方法是由G.A.Bird提出[],基于Boltzmann方程的模拟仿真粒子的方法。
它用大量的模拟分子代替真实气体分子,并用计算机模拟分子的运动和碰撞过程,最后通过统计模拟分子的运动状态得到流体的宏观量。
这种直接模拟的方法极大的简化了计算模型,使计算过程大大的简化,同时,由于在对分子的移动和碰撞进行了解耦,使得在碰撞计算中可以引入各种碰撞模型,甚至化学反应模型,极大的增加了DSMC方法的适用范围。
已有研究证明该方法收敛于玻尔兹曼方程[][],另一方面,DSMC的结果也十分出色的符合实验结果[],经过数十年的发展,DSMC方法已经成了研究稀薄气体的强有力工具。
尽管传统的DSMC方法有很多优点,但是它的缺点也很明显,其中一个是复杂的网格处理,针对这个缺点,人们在直角网格[]的基础上提出了一系列新的网格划分方法,如非结构网格[][]和结构贴体网格[]。
DSMC的另一个缺点是计算量大,耗时长,近几年人们在尝试对DSMC方法并行化以提高其计算效率。
目前人们对DSMC的并行主要是基于多核CPU和CLUSTER[][],这些并行手段可以较好的提高计算速度,然而安装和维护这些计算设备需要花费较大的成本。
近年来GPU上数量众多的计算单元和通用可编程GPU计算技术的飞速发展为大规模DSMC并行计算提供一种新的可能。
GPU的大规模并行运算潜力既能实现较强的运算能力又可以极大地降低运行成本。
2010年NVIDIA发布的基于Fermi架构的TeslaC2050GPU单精度浮点峰值性能达到了1TFLOPS以上,是核心频率3.0GHz四核CPU的20倍,计算能力几乎可以与机群相比,但是其成本和功耗却只有机群的1/10和1/20。
NVIDIA最新发布的基于Kepler架构的K20GPU性能相比Fermi架构则又有了质的飞跃,不仅如此,其性能/功率比也提升了3倍。
与此同时,基于GPU的通用可编程技术的发展,如CUDA和OpenCL的发布,极大降低了基于GPU的编程难度,人们在不具备专业图形学知识的情况下即可利用GPU的强大计算能力。
目前已有一些工作尝试将DSMC方法和相关流体力学问题移植到GPU上。
陈伯君[]首次在GPU上并行实现DSMC方法,以一维Rayleigh问题为例对DSMC方法进行并行计算。
Su等[]使用CUDA模拟了二维超声速流动并获得了3-10倍的加速比。
Denis[]等在GPU上并行了复杂外形三维翼的DSMC算例,并获得了65倍的加速。
然而,他们的工作均基于传统的静态网格方法。
本文使用CUDA对动态网格DSMC程序[]在GPU上实现了并行,并取得了10倍以上的加速比。
剩余部分结构如下:
第二章介绍了基于GPU的编程模型,第三章介绍了动态划分的DSMC方法,第四章介绍动态划分的DSMC方法在GPU上的并行实现,第五章为实验结果和讨论,第六章是工作的总结。
2GPU编程模型
CUDA(ComputeUnifiedDeviceArchitecture)是由NVIDIA推出的通用并行计算架构,采用C语言作为编程语言提供大量的高性能计算指令,使开发者能够更加方便有效地基于GPU编程,从而充分发掘GPU的强大计算能力。
CUDA的编程模型如图1所示,一个完整的CUDA程序由主机端的串行处理步骤和一系列的设备端并行函数kernel共同组成。
从图上也可以看出,一个kernel函数具有两个层次的并行:
同一个grid内block间存在不需要通信的粗粒度并行和同一个block内thread间允许通信的细粒度并行。
这种双层线程模型是CUDA的一个重要特性,这一特性可以显著提高执行效率,并拓展GPU的适用范围。
Fig.1CUDAprogrammingmodel
图1CUDA编程模型
3动态网格的DSMC方法简介
3.1DSMC算法简介
DSMC方法用大量的模拟分子代替真实气体分子,并在计算机中存储模拟分子的位置坐标、速度分量、以及内能,它们随分子的运动、与边界的碰撞以及分子之间的碰撞而随时间不断地改变,最后通过统计网格内模拟分子的运动状态实现对真实气体流动问题的模拟。
它的主要特点是:
将分子的碰撞和运动解耦。
在一个很短的时间步长内,认为分子的运动和碰撞相互独立,然后将其分开处理,这样可以使用计算机对气体分子进行直接模拟,而不需要求解复杂的Boltzmann方程。
除此以外,DSMC在计算中采用了蒙特卡罗方法,减少了计算量,从而能够模拟大量的分子。
典型的DSMC方法的流程如图2所示。
具体的步骤如下:
1)初始设置。
根据流场的初始条件(温度、密度、初始速度等),以及模拟分子的条件,设置所有模拟分子的初始速度、位置和能量。
其中,初始速度为初始宏观速度加上平衡气体中的热运动速度。
然后根据流场和固壁条件划分网格,使网格大小和网格分子数在一个合理范围。
2)分子移动和边界处理。
分子在当前速度下,在一个时间步长内进行匀速直线运动,根据移动前位置和移动的位移计算分子的新位置。
同时处理分子在边界的运动,包括新的模拟分子进入计算域、分子运动到计算域之外以及分子与固壁的碰撞。
其中,分子与固壁的碰撞采用蒙特卡罗算法。
3)分子重新排序编号。
分子移动后,其在计算域的分布发生了变化,部分分子所在的碰撞网格可能也因此变化。
因而需要根据分子移动后的新位置,重新标记其所在的网格。
4)计算分子碰撞。
这里认为分子只与同一网格内的其它分子碰撞。
对于每一个网格,根据网格内的分子信息计算碰撞次数,再随机选取一对分子,若选取的分子对满足碰撞条件,则按照选择的碰撞模型计算分子对在碰撞后的速度和能量。
重复选择分子对,直到符合碰撞条件的分子对数量达到之前计算出的碰撞次数。
5)判断是否满足结束条件。
若不满足则重复2)到4)步骤直到满足结束条件。
6)统计流场信息并输出结果。
对每个网格的分子信息进行统计,计算得到流场的宏观状态参量然后输出。
Fig.2FlowchartofDSMCprogram
图2.DSMC程序流程
3.2DSMC的动态网格算法
动态网格的DSMC方法[14]与传统DSMC方法大部分的步骤相同,唯一不同的是网格的划分方法。
在传统DSMC方法中,计算网格划分之后不再变化。
然而,由于分子在运动过程中,其分布会不断变化,从而导致不同碰撞网格的分子数目不均衡,这对于DSMC方法的并行效率会有影响。
而且,使用静态网格比较难以适应变化剧烈的流场。
相比之下,动态网格的DSMC方法则可以较好地克服这些缺点,在每一轮的分子碰撞过程中,根据分子的分布情况动态构建网格,并标记分子所属网格,再遍历所构建的动态网格计算分子碰撞。
碰撞网格的划分和分子的标记采用kd-tree算法,具体划分步骤可以参见[14],其网格划分思想如下:
1)设定碰撞网格分子数的阈值,将其作为是否构成碰撞网格的标准;
2)如果网格的分子数小于等于该阈值,则认为该网格已经构成碰撞网格,不再继续划分;
3)如果网格的分子数大于该阈值,则认为不构成碰撞网格,根据空间划分策略计算空间划分的位置,将其等分为两个新的网格;
4)对新生成的网格递归调用网格划分算法,重复2)和3),直至所有网格的分子数均小于阈值。
使用该算法后,各个碰撞网格的分子数可以保持的比较均衡。
3.3串行程序剖析(Profiling)
将动态网格的DSMC方法移植到GPU之前,我们先使用操作系统提供的程序GPROF对串行程序进行了剖析(Profiling),以查找程序的热点,分析结果如图3所示:
Fig.3HotspotsofsequentialDSMCprogram
图3串行DSMC程序的Hotspots
从profiling的结果可以看出,分子移动、网格划分、碰撞计算和统计分子信息花费的时间占了总时间的绝大部分,约为98%,因而我们的并行实现将主要针对这几部分进行。
4动态网格DSMC方法在GPU上的并行
对动态网格的DSMC串行算法分析后发现,分子移动、网格划分、碰撞计算和统计分子信息这几部分都具有一定的并行性,并且它们在迭代过程中需要反复调用,所以我们将这几部分的运算移植到GPU上。
4.1串行程序在GPU上的实现
动态网格DSMC并行程序的流程如图4所示。
实现具体步骤如下:
1)初始化。
初始流场中的每个分子初始化时相互独立,它们的位置和状态依据宏观物理量的设定,以一定的分布随机生成,是一个高度并行的过程,但由于在整个计算流程中占的比重非常小,所以没有必要移植到GPU上,因而在主机端完成初始化的过程,然后将数据传输到GPU上的显存。
2)分子移动/边界处理。
这一部分占的时间比重并不是很大,但是为了使整个迭代过程在GPU上实现,以减少数据传输带来的开销,我们依旧将其移植到GPU上。
不同分子的移动及其在边界的处理是一个高度独立的过程,实际操作中对模拟分子进行并行操作,每一个线程处理一个分子的移动/边界处理。
3)剔除不在计算域的分子。
部分分子在经过分子移动/边界处理后会逸出计算域。
分子移动后是否还在计算区域的判断也是高度并行的过程,因此可以每一个线程处理一个分子,分子流出流场导致的分子总数变化采用原子减函数atomicSub()进行统计。
Fig.4FlowchartofparallelDSMCprogram
图4并行DSMC程序流程图
4)网格划分。
这是DSMC在GPU上并行最难实现的地方,因为动态网格划分方法采用KD-Tree算法,串行代码在实现过程中使用了递归结构,但是GPU上并不支持递归,另外,由于流场密度梯度的存在,使得KD-Tree各个子节点的层数不一样,这也使得使用GPU这种结构高度齐整的设备不易并行,但是,对KD-Tree算法进行分析后可以发现,在判断分子所属node和创建新node的过程中具有大量的并行性,而通过将这两部分写在不同的kernel则可以实现它们之间的全局同步。
在实验中采用的算法如图5。
DSMC程序的动态网格划分方法
创建node
决定每个分子所属的node(并行,每线程处理一个分子)
loop()
{
(对于未达到终止条件的node)继续创建新node
将每个分子分配到所属node(并行,每线程处理一个分子)
}
node划分终止条件:
每个node包含的分子数目小于阈值
Fig.5Algorithmfordynamicgriddingmethod
图5动态网格划分方法
Kd-Tree的创建本应该从一个node开始划分,每一次划分node数量为原先的2倍,但由于每次划分都要全局同步,所以每次都要启动新的Kernel,会加长计算时间,而实际上对大部分node,在划分多次之后才会到达划分的停止条件(分子数小于20)。
因此可以做一些优化,先一次性创建多个node,然后在此基础上进行足够次数的后续划分。
采用这种方法,只要保证第一次划分的节点没有或刚达到划分终止条件即可保证结果的正确性,而第一次划分的node数量则应该根据求解的具体问题决定。
5)碰撞计算:
从profiling结果可以看出,碰撞计算是DSMC程序中占总时间比重最大的部分,因此对它的并行实现是最有意义的。
根据DSMC方法的假设,在碰撞计算过程中不同的网格的模拟分子不会相互影响。
因而,每一个碰撞网格内只处理属于该网格的分子。
即各个网格的碰撞计算是相互独立的,而且是属于易并行问题,因此可以对碰撞网格进行并行操作,每一个线程处理一个网格的碰撞计算。
4.2随机数的读取
在DSMC方法中,随机数是一个很重要的概念,在计算过程中引入概率的方法,是DSMC算法的一个特色,在计算过程中得到足够合格的随机数是保证计算结果正确的一个前提。
我们使用CURAND库里提供的curand_normal函数生成随机数。
CURAND是CUDA库里提供的一个用于生成随机数的库。
它提供了丰富的主机端和设备端函数,可以简单高效的生成高质量的伪随机数。
我们所使用的curand_normal函数用于生成(0,1)之间均匀分布的随机数。
用于生成随机数的种子状态存储在GlobalMemory,在GPU核函数调用时存入每个线程的寄存器,在调用结束时传回GlobalMemory。
这样可以确保安全使用随机数的同时提高其生成速度。
5实验结果及分析
实验所用算例是一个超音速横掠平板的二维流动问题。
具体设置如下:
超音速氮气流以4.0Ma的初始速度,300K的初始温度流过一块温度为500K的热平板,计算区域尺寸为L=1m,H=0.6m,平板位于计算域底部,长度为L=0.9m。
每个模拟分子代表
个真实分子,迭代计算200000次统计网格数为100*100。
5.1并行程序正确性验证
我们使用CUDA在GPU上实现了动态DSMC程序的并行,实验环境如表1所示:
单颗Inteli7CPU搭载单颗NVIDIATeslaC2050GPU。
实验结果如图6和图7,串行程序和并行程序吻合的很好,从而可以验证并行程序的正确性。
Table1Experimentaltestbed
表格1程序运行环境
CPU
Intel®Core(TM)i7CPU@9200@2.67GHz,4Core
Memory
8GBDDR31067MHz
GPU
NVIDIATeslaC2050
NVIDIAKeplerK20
OS
Ubuntu10.10
Compiler
GCC4.4.5+NVCC4.1(NVIDIATeslaC2050)
GCC4.4.5+NVCC5.0(NVIDIAKeplerK20)
(a)(b)
Fig.6Thenumberofmoleculescollisionwithplate:
(a)Sequential;(b)Parallel
图6平板上分子碰撞数量:
(a)串行结果;(b)并行结果
(a)(b)
Fig.7Densitycontours:
(a)Sequential;(b)Parallel
图7流场的密度分布:
(a)串行结果;(b)并行结果
5.2不同规模算例对比
为了验证并行程序的可扩展性,我们使用了不同规模的算例进行实验。
结果如图8所示,可以发现,加速比随着计算规模的增大显著提高,而规模最大的一个算例加速比达到了16倍以上。
这是因为随着计算规模增大,对GPU计算能力的利用效率有显著提高。
Fig.8Speedupofdifferentcases
图8不同规模算例的加速比
5.3KeplerK20上的性能
为了进一步提升性能,我们在NVIDIA最新发布的新一代GPUKeplerK20上进行了测试,并与FermiC2050作了比较,结果如图9所示。
可以看出,对于同样的代码,同样的算例,KeplerK20的速度约为FermiC2050上的1.3-1.6倍,性能得到了显著的提升。
我们认为,该提升主要来自Kepler架构对原子操作的优化,使得统计网格中分子数量时间大大减少。
Fig.9Speedup:
KeplerK20vsFermiC2050
图9KeplerK20和FermiC2050的性能比较
6结论和下一步工作展望
本文实现了动态划分的DSMC在GPU上的并行化。
在整个实现过程中,只有流场的初始化和输出这一部分通过CPU完成,循环迭代的所有步骤,包括分子的移动,动态网格划分和碰撞计算和流场信息的统计都在GPU上实现。
从实验结果看,无论在FermiC2050还是KeplerK20GPU上,并行程序均获得了10倍以上的加速比,这大大减少了程序的运行时间,同时也说明即使对于如动态网格DSMC方法这样的紧耦合问题,移植到GPU上后依然可以获得较大的性能提升。
尽管如此,GPU的计算潜力依旧没有充分开发出来:
在动态划分网格的过程中,每一层节点的划分都需要全局同步,目前CUDA模型中不同block之间的同步需要通过将任务分配给不同的kernel来实现;统计网格分子的时候我们使用了大量的原子操作,这些都会使GPU的计算效率降低,如果想要进一步发挥GPU的计算优势,则势必要开发更加优秀的网格划分算法。
在未来的工作中,我们将尝试将该算法在多机多GPU上测试,并尝试使用Kepler和CUDA5.0的新特性DynamicParallelism来优化并行程序。
References:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 网格 DSMC 方法 GPU 并行
![提示](https://static.bingdoc.com/images/bang_tan.gif)