第２７卷第７期２０１０年７月计算机应用研究ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓＶ０１．２７Ｎｏ．７Ｊｕｌ．２０１０基于ＣＵＤＡ的汇流分析并行算法的研究与实现木赵向辉Ｌ２，苗青Ｌ２，付忠良１’２，苏畅１’２，李昕１’２（１．中国科学院成都计算机应用研究所，成都６１００４１；２．中国科学院研究生院，北京１０００４９）摘要：针对基于数字高程模型（ＤＥＭ）生成流域等流时线的快速运算问题，提出了一种基于统一设备计算架构（ＣＵＤＡ）平台同时可发挥图形处理器（ＧＰＵ）并行运算特性的；１２流分析的快速并行算法。采用改进后的归并排序算法进行数据排序及新的内存分配策略和改进的并行算法进行汇流分析。用该并行算法和ＣＰＵ上的串行算法，对生成基于ＤＥＭ的等流时线运算时间和矩阵乘法运算时间进行分析验证。实验结果袁明，基于ＣＵＤＡ的汇流分析并行算法能提高系统的计算效率，具有较好的效果。关键词：并行计算；图形处理器；统一设备计算架构；汇流分析；数字高程模型中图分类号：’鹏９１；ＴＰ３０１．６文献标志码：Ａ文章编号：１００１．３６９５（２０ｌｏ）０７．２４４５．０３ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００ｌ－３６９５．２０１０．０７．０１ｌＲｅｓｅａｒｃｈａｎｄｒｅａｌｉｚａｔｉｏｎｉｎｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍｏｆｃｏｎｆｌｕｅｎｃｅａｎａｌｙｓｉｓｂａｓｅｄＺＨＡＯＸｉａｎｇ－ｈｕｉｌ”，ＭＩＡＯｏｎＣＵＤＡｔ２Ｑｉｎ９１”，ＦＵＺｈｏｎｇ－ｌｉａｎ９１”，ＳＵＣｈａｎ９１”。ＬＩＸｉｎｌ（Ｉ．ＣｈｅｎｇｄｕＩｎｓｔｉｔｕｔｅｏｆＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓ，ＣｈｉｎｅｓｅＡｃａｄｅｍｙ矿Ｓｃｉｅｎｃｅｓ，Ｃｈｅｎｇｄｕ６１００４１，Ｃｈ／ｎａ；２．ＧｒａｄｕａｔｅＳｃｈｏｏｌ，ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃ／ｅｎｃｅｓ，＆群，ｌｇ１０００４９，∞讹）ａｔＡｂｓｔｒａｃｔ：Ａｉｍｉｎｇｔｈｅｆａｓｔｐａｒａｌｌｅｌａｃｏｍｐｕｔｉｎｇｏｆｇｅｎｅｒａｔｉｎｇｉｓｏｃｈｒｏｎｅｓｏｆｗａｔｅｒｓｈｅｄｓｔｈａｔｂａｓｅｄｂａｓｅｄｏｎｏｎｄｉｓｔａｌｅｌｅｖａｔｉｏｎｍｏｄｅｌ（ＤＥＭ），ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｄｆａｓｔｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍｏｆｃｏｎｆｌｕｅｎｃｅａｎａｌｙｓｉｓｃｏｍｐｕｔｅｕｎｉｆｉｅｄｄｅｖｉｃｅａｒｃｈｉｔｅｃｔｕｒｅ（ＣＵＤＡ）ｐｌａｔｆｏｒｍｔｈａｔｃｏｕｌｄＵＳｅｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇｏｆｇｒａｐｈｉｃｐｒｏｃｅｓｓｉｎｇｕｎｉｔ（ＧＰＵ）．Ｃａｒｒｉｅｄｄａｔａｓｏｒｔｉｎｇｏｕｔｂｙｕｓｉｎｇｔｈｅｉｍｐｒｏｖｅｄｍｅｒｇｅｓｏｒｔｉｎｇａｌｇｏｒｉｔｈｍ，ａｄｏｐｔｅｄｔｈｅｎｅｗｍｅｍｏｒｙａｌｌｏｃａｔｉｏｎｓｔｒａｔｅｇｙ，ｃａｒｒｉｅｄｃｏｎｆｌｕｅｎｃｅａｎａｌｙｓｉｓｏｕｔｂｙｕｓｉｎｇｔｈｅｉｍ—ｐｒｏｖｅｄｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇａｌｇｏｒｉｔｈｍ．ＵｓｉｎｇｔｈｅｐｒｅｓｅｎｔｅｄｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍａｎｄｔｈｅｓｅｒｉａｌａｌｇｏｒｉｔｈｍｂａｓｅｄＯＯＣＰＵｔｏａｎａｌｙｚｅａｎｄｖｅｒｉｆｙｔｈｅｔｉｍｅｃｏｎｓｕｍｅｄｗｈｅｎｇｅｎｅｒａｔｉｎｇｉｓｏｃｈｒｏｎｅｓｏｆｗａｔｅｒｓｈｅｄｓｂａｓｅｄｏｎＤＥＭａｎｄｅｘｅｃｕｔｉｎｇｍａｔｒｉｘｍｕｌｔｉｐｌｉｃａｔｉｏｎ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔｓｒｅｓｕｌｔｓｉｌｌｕｓｔｒａｔｅｔｈａｔｔｈｉｓｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍｏｆｃｏｎｎｕｅｎｃｅａｎａｌｙｓｉｓｂａｓｅｄｔｉｏｎａｌｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅｓｙｓｔｅｍａｎｄｈａｖｅａｂｅｔｔｅｒｅｆｆｅｃｔ．Ｋｅｙｗｏｒｄｓ：ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ；ｇｒａｐｈｉｃａｎａｌｙｓｉｓ；ｄｉｇｉｔａｌｅｌｅｖａｔｉｏｎｏｎＣＵＤＡｃａｎｉｍｐｒｏｖｅｔｈｅｃｏｍｐｕｔａ－ｐｒｏｃｅ昭ｉｎｇｕｎｉｔ（ＧＰＵ）；ｃｏｍｐｕｔｅｕｎｉｆｉｅｄｄｅｖｉｃｅａｒｃｈｉｔｅｃｔｕｒｅ（ＣＵＢＡ）；．ｃｏｎｆｌｕｅｎｃｅｍｏｄｅｌ（ＤＥＭ）ＣＵＤＡ是ＮＶＩＤＩＡ公司提供的ＧＰＵ用于通用计算的开发环境，是一个全新的软硬件架构，可以将ＧＰＵ视为一个并行数据计算的设备，对进行的计算进行分配和管理。图形显示卡，尤其是高端的显卡，现在几乎是单机必配的重要硬件。其核心部件ＧＰＵ采用ＳＩＭＤ体系结构，大量的计算部件使得它很适合处理高数据量的并行运算０１．－３Ｊ。基于ＣＵＤＡ平台，利用ＧＰＵ强大的并行处理能力来加速通用科学计算及普通应用程序是非常好的应用趋势，已经成功应用到诸如金融风险管理、媒体图像以及科学研究‘４１等领域。本文结合科研项目“基于３Ｓ技术的自然灾害智能预测平台的研发与应用”中相关的关键信息技术来开展基于ＣＵＤＡ的汇流分析并行算法的研究与实现。在自然灾害的山洪汇流分析中，项目中要绘制的等流时线是基于ＤＥＭ高程图绘制的”’６ｊ。若采用传统的基于ＣＰＵ的串行算法，高分辨率的ＤＥＭ图在带来更好的计算效果的同时，也大大地增加了计算量，使得计算时间大幅度增加，降低了计算效率。例如作为四收稿日期：２００９一ｌｌ一２６；修回日期：２０１０—０１—０４川省试点地区的彭州甘溪沟流域，其流域面积１１．１ｋｍ２，沟道长度为６．８３ｋｍ，若使用８０ｍ作为单位栅格边长来划分流域，则流域呵被划分为Ｉ８０５个有效栅格单位，若采用高精度的划分方法，以２０ｍ作为栅格边长来划分流域，则流域被划分为２８９００个有效栅格，在能获得更高精度ＤＥＭ图的情况下，栅格的数量会更大。这样，在获得更精确结果的同时，大大牺牲了运算效率。传统的方法难以满足高数据最的计算需求，本文算法的计算核心是矩阵相乘计算，需要花费大量的时间，ＧＰＵ在计算矩阵相乘时，比ＣＰＵ要快得多，因此可巧妙地利用基于ＣＵＤＡ平台的ＧＰＵ强大的并行处理能力来加速计算速度＂’８ｏ。本文提出了一种基于ＣＵＤＡ平台可发挥ＧＰＵ并行运算特性的快速并行算法。１ＣＵＤＡ并行计算的引入ＣＵＤＡ表示统一计算设备架构，使ＧＰＵ能够解决复杂的计算问题。它是一个并行编程模型和～个软件编程环境，它主基金项目：四川省科技支撑计划基金资助项目（２００８ＳＺ０１００，２００９ＳＺ０２１４）作者简介：赵向辉（１９８２・），男，河南长蔫人，博士研究生，主要研究方向为机器学习、数据挖掘、模式识别、图像分析等（ｘｉ肿ｇｌｌｕｉｚｈａｏ＠ｈｏｔｍａｉｌ．㈣）；苗青（１９８２－），男，四川成都人，博士研究生。主要研宄方向为图形图像处理、机器学习、模式识别等；付忠良（１９６７．），男，重庆人，研究员，博导．主－Ｊｔ－榭＂向为机器学习、机器视觉、模式识别、图形图像处理等；苏畅（１９８３一），男，安徽淮南人。助理研究员，硕士，主要研究方向为机器学习、虚拟仿真、图形图像处理等；李昕（１９８５一），男，胰西汉中人，硕士研究生。主要研究方向为机器学习、虚拟仿真ｉ图形图像处理等．万方数据・２４４６・计算机应用研究第２７卷要是为了帮助广大的程序员来更好地开发平滑扩展的并行程序。当前主流ＧＰＵ产品在浮点运算性能上都超过了１ＴＦＩｏｐｓ【９ｊ，而Ｉｎｔｅｉ公司最新的四核处理器Ｃｏｒｅ２ｉ７也仅达到７０ＧＦｌｏｐｓ［１引。ＣＵＤＡ模型中，ＧＰＵ相当于ＣＰＵ的协处理器，它能并行执行非常多的线程，处理大规模的并行运算。整体来说，ＧＰＵ芯片类似于流处理器，适合一次进行大量相同的工作；ＣＰＵ则比较有弹性，能同时处理变化较多的工作＂ｏ。图ｌ表明，ＧＰＵ具备了超高的计算能力，在多个处理核心和高存储器带宽的配合下，最新的ＧＰＵ成为了图形和非图形处理的超强工具。ＣＵＤＡ的软件堆栈…１采取如图２所示的多层组成方式，以此实现高性能计算。它允许定义一种叫ｋｅｒｎｅｌ的函数扩展，当一个ｋｅｍｅｌ函数被调用时，会有，ｖ个不同的ＣＵＤＡ线程在ＧＰＵ中并行地执行相同的程序，并行执行的线程数量用扩展的“＜（（）））”来指定。例如ＦｕｎｅｔｉｏｎＯｎＧＰＵ（（（４，２５６＞））（…），该函数一旦成功调用，便共有４×２５６＝１０２４个独立的并行线程来执行该函数的内容。其中４为块（ｂｌｏｃｋ）的数量，２５６为每块内的线程（ｔｈｒｅａｄ）的数量。ｌ０００—◆一ＮＶＩＤＩＡＧＰＵＣ，Ｔ２００善７５０—●卜－ＩｎｔｅｌＧＰＵｇ５００Ｎｖ∞１竖√潲眺｝－ｔ２５０，艘兰辈』！璺１Ｗ兰Ｖ－７１／娄＿鱼当３２ＧＰｍ，ｚ０Ｌ—●Ｌ——二————————二！—————－－———＝：—————————————————————————－————・—一”ＪａｎＪｕｎＡｐｒＪｕ．Ｍ”ＮｏｖＭａｙＪｕｎ２００３２００４２００５２０（）６２００７２００８ＧＴ２００＝Ｃ，ｅＦｏｒｅｅＧＴＸ２８０Ｇ７１＝Ｃ，ｅＦｏ佗ｅ７９００ＧＴＸＮＶ３５＝ＧｅＦｏｗ．ｅＦＸ５９５０ＵｌｔｒａＣ９２＝ＧｅＦｏｒｃＰ９８００ＧＴＸＣ７０＝ＧｅＦｏｒｃｅ７８００ＧＴＸＮＶ３０＝ＧｅＦｏｒｃｅＦＸ５８００Ｃ踟ｂ＝ＧｅＦ‘毗七８８００ＧＴＸＭＶ４０＝Ｃ．ｅＦｏｒｃｅ６８００Ｕｌｔｒａ图ｌＣＰＵ和ＧＰＵ的每秒浮点运算次数图２ＣＵＤＡ软件堆栈２基于ＤＥＭ的流域等流时线绘制算法为了解决山洪灾害预测问题。通过建立山洪形成过程的数学模型。实现对山洪预测的数值模拟。等流时线是一种经典的流域汇流曲线¨Ｊ，根据对基于数字高程模型的流域等流时线绘制算法的描述¨２‘，在整个计算和绘制的过程中，主要经过五个大步骤的计算：ａ）对ＤＥＭ图作填洼处理；ｂ）根据高程对栅格进行排序；Ｃ）判断栅格水流方向；ｄ）计算单个栅格汇流时间；ｅ）计算流域汇流时间。其中：步骤ａ）填洼处理可以由ＧＩＳ软件，本文使用ＳｕｐｅｒｍａｐＤｅｓｋｐｍ２００８软件来完成；步骤ｂ）对栅格按高程排序，一般排序算法的复杂度为Ｏ（ｎｌｏｇ２“），对于大量元素的排序，较为耗费系统计算资源；步骤Ｃ）判断栅格水流方向，需要与栅格周围的八个栅格进行比较；步骤ｄ）计算单个栅格汇流时间；步骤ｅ）从ＤＥＭ值最小的栅格开始计算流域汇流时间。若采用传统的基于ＣＰＵ的串行算法，这些运算都需要对栅格进行多次的遍历，在栅格划分较多的高精度ＤＥＭ图上，就会成为整个算法的瓶颈。观察分析以上几步可发现，在栅格运算的过程中，排序可以使用优化的并行排序算法来提高效率，步骤Ｃ）和ｄ）的运算，由于其栅格之间的相关性很低，计算水流方向时，只需要考万方数据虑与之相关的八个栅格；计算单个栅格的汇流时同时几乎是独立运算。这两步运算符合ＳＩＭＤ（ｓｉｎｇｌｅｉｎｓｔｒｕｃｔｉｏｎｍｕｌｔｉｐｌｅｄａ－ｔａ，单指令多数据流）指令系统，宜于利用并行运算将其实现。按照规格网格法，把系统所需的ＤＥＭ图表示成高程矩阵，在计算机中以二维矩阵的方式存放。流域外的空白地区的高程值被设为一９９９。所以对ＤＥＭ图的操作，实际上就是对高程矩阵的运算。ＣＰＵ的流式指令体系结构在提高矩阵运算速度上有着很大的限制。ＧＰＵ（图形处理器）采用单指令多数据流体系结构，大量的计算部件使得它很适合处理矩阵运算。因此，本文将以上几步的算法进行优化，使其适合并行计算，并基于ＣＵＤＡ平台利用ＧＰＵ的通用计算功能，使用改进的并行算法在单机上进行并行实现，最大化利用电脑硬件的计算能力。３基于ＣＵＤＡ汇流分析的并行算法３．１算法实现流程本文使用改进后的归并排序算法对栅格进行排序。将第２章中介绍的相关算法进行优化，使其适合并行计算。该算法在ＧＰＵ上的具体实现（以四川彭州甘溪沟流域的ＤＥＭ图为例来对上述算法并行部分进行验证），主要流程如下：８）将ＤＥＭ转换为高程矩阵。ｂ）使用改进后的归并排序算法，按照高程值对栅格进行排序。对高程矩阵按照数据量将数据分块并排序，将结果送至共享内存并分配空间，同步线程后，对奇偶块进行Ｍｅｒｇｅ运算。Ｃ）计算栅格水流方向和经流时间ｉｄ）绘制等流时线进行汇流展示。３．２算法及其应用分析３．２．１按照高程值对栅格进行排序加利福尼亚州大学的Ｓａｔｉｓｈ等人¨３Ｊ提出了一种在ＣＵＤＡ上进行归并排序的算法，并提出通过预先抽取数据采样，对待排序序列根据采样值进行分块来提高归并算法中Ｍｅｒｇｅ运算的效率。同时，采样以２５６个待排元素为间隔，来保证划分出的每个子块最多含有２５６个元素。这样使在Ｍｅｒｇｅ运算时划分出的子块能够快速地在ＧＰＵ上基于其共享内存来运算。在计算等流时线前需要对栅格进行排序，以获得高程值最低的栅格作为整个流域汇流的出口。在排序算法中，由于多路归并排序，将数据分组排序后再合并，适合并行计算，在此处使用改进后的归并排序。首先将ＤＥＭ对应的高程矩阵看做一维数组，然后按照数据量将数据分成ｋ个块，每块分别送进ＣＵ．ＤＡ的一个ｂｌｏｃｋ，使用ｂｉｔｏｎｉｅ对其进行排序，最后将结果送至共享内存中，同步线程后，对奇偶块进行ｍｅｒｇｅ运算。从国内外已有的研究来看。排序运算元素之间并不能达到高的独立运算，元素之间仍有一定的相关性，并行时加速比不是很高。因此，并行排序运算虽然有一定的效率提高，但并不是整个运算加速的重点。假设高程矩阵是一个ｍ×ｎ的矩阵，根据汇流分析的相关知识，求取栅格水流方向，只需计算该栅格与相邻的八个栅格的距离权落差，在计算单个栅格的流经时间时，需要使用公式：缸＝，讧／［Ｋ（ｓ‘）‘］（１）式中各个参数的意义请参见文献［１２］，只有参数ｓｉ与该栅格的流向栅格有关，这两个运算之间的相关性很高，可以在一个３．２．２计算栅格水流方向和经流时间第７期赵向辉，等：基于ＣＵＤＡ的汇流分析并行算法的研究与实现・２４４７・运算过程中完成。在这两个运算过程中，栅格与栅格之间的相关度较低，可以方便地实现高并行运算。１）高程矩阵的分块和ＣＵＤＡ中内存的分配该算法的整个并行计算过程中，尽量降低内存带宽的使用是提高性能的重要方式。而该算法的特点决定了即使是并行计算，在计算过程中仍可能存在重复读取的现象。例如，分块时把栅格Ａ分入ｂｌｏｃｋ（０，０）中运算，但是栅格Ａ的相邻栅格Ｂ可能在分块时被分入ｂｌｏｃｋ（０，１）中计算，这样Ａ和Ｂ栅格就会在运算的过程中被重复地读取。为提高并行算法在ＧＰＵ上的效率，如何分块尤为重要。为了防止在计算过程中对内存的反复读取，所以分块时，将需要参与计算的元素全部分入一个ｂｌｏｃｋ中。例如需要ｂｌｏｃｋ（０，１）计算☆×ｋ个栅格的流向，就以这＾×ｋ的矩阵为中心，向四周相邻的方向各多取一个元素，即取以这个矩阵为中心的（ｋ＋２）×（ｋ＋２）阶矩阵。这样在计算该｜ｉ｝×矗个栅格时将需要的所有元素完全加载到存取速度很快的共享内存中来，在计算的过程中，该部分栅格的运算就不需要再存取任何外部的内存。针对绘制等流时线的运算，需要创建三个与运算栅格相同大小的辅助矩阵，即流向矩阵、坡度矩阵和单位栅格流经时间矩阵。如果想取得更高的运算速度，最好能将这三个矩阵都存放在存取速度较快的共享内存中。同时，在ＣＵＤＡ平台上，一个线程块最大只支持５１２个线程，而且根据内存节距对齐的原则，ＧＰＵ的内存控制器从某个固定倍数的地址开始读取才会有最高的效率¨…。根据其支持的线程数，最好的办法就是将高程矩阵分解为１４×１４的小矩阵，这样，每次共享内存中就会加载１６×１６阶的矩阵，并在共享内存创建三个１４×１４阶的辅助矩阵。为了方便进行线程块的计算，针对高程矩阵，可为每个线程块分配１４×１４个线程，再建立（ｍ／１４）×（ｎ／１４）个线程块。这就充分利用了ＧＰＵ多线程的特点，从而大大地提高运算速度。当然，分解高程矩阵时，有可能小矩阵块是边沿矩阵块，这就需要在分解时对小矩阵块作出是否是边界元素的判断，如果是边界元素，就需要用一９９９作为值填充在空白的相邻栅格的位置，创建出１６×１６阶的矩阵。由于参加运算的高程矩阵的阶很可能不是１６的倍数，为了使ＧＰＵ更有效率地工作，在开始运算前为分解的分块小矩阵开辟内存空间时，就直接把内存大小配置成１６的倍数，并在复制矩阵到显卡内存之前将其清零。这充分利用了ＧＰＵ的内存读取特点，且符合ＧＰＵ内存读取高效率的原则。使用ＣＵ－ＤＡ提供的ｃｕｄａＭａｌｌｏｃＰｉｔｃｈ（）函数就可以满足该要求，用于提高共享内存的访问速度¨“。分配空间的伪代码如下：＃ｄ硪ｎｅＢＬＯＣＫＳＩＺＥ１６●…●●ｉｎｔＢｌｏｃｋ—ｌｌＵｒｎ＝（（ｎ＋（ＢＬＯＣＫ—ＳＩＺＥ一１）一１）／（ＢＬＯＣＫ—ＳＩＺＥ－１））‘（ＢＬＯＣＫ—ＳＩＺＥ・１）：ｅｕｄａＭａｌｌｏｃＰｉｔｃｈ（（ｖｏｉｄ“）＆ｄｅｍｃ，＆ｐｉｔｃｈ—ｄｅｍ，ｓｉｚｅｄ（ｆｌｏａｔ）’Ｂｌｏｃｋ—Ｈｕｍ．Ｂｌｏｃｋ—ｎｕｍ）；ｅｕｄａＭａｌｌｏｃＰｉｔｃｈ（（ｖｏｉｄ“）＆ｄｉｍ＆ｐｉｔｃｈ—ｄｉｒ，ｓｉｚｅｏｆ（ｆｌｏａｔ）‘Ｂｌｏｃｋ—ｈｕｍ，Ｂｌｏｃｋ—ｈｕｍ）；ｅｕｄａＭａｌｌｏｃＰｉｔｃｈ（（ｖｏｉｄ“）＆ＳｒⅢｔｃ，＆ｐｉｔｃｈ—ｇｒａｄ，８ｉ∞ｏｆ（ｆｌｏａｔ）‘Ｂｌｏｃｋ—ｎｕｍ，Ｂｌｏｃｋ—ｎｕｍ）；ｃｕｄａＭａｌｌｏｃＰｉｔｃｈ（（ｖｏｉｄ“）＆ｔｉｍｅｅ，＆ｐｉｔｃｈ—ｔｉｍｅ，８ｉ／％ｏｆ（ｆｌｏａｔ）‘Ｂｌｏｃｋ＿ｈｕｍ，Ｂｌｏｃｋ＿ｈｕｍ）；ｅｕｄａＭｅｍｓｅｔ（ｄｅｍｃ，０，ｐｉｔｃｈｄｅｍ’Ｂｌｏｅｋ＿ｎｕｍ）；２）运算核函数万方数据有了上述的高程矩阵分块方法和内存分配机制，真正需要在ＧＰＵ上执行的核函数的伪代码如下：—西ｏｂａｌｓｔａｔｉｃｖｏｉｄｇｅｎＤＬＳＸ（ｅｏｎｓｔｆｌｏａｔ。ｄｅｒｎ，ｓｉｚｅ＿ｔｌｄｄｅｍ，ｃｏｎｓｔｆｌｏａｔ＋ｄｉｒ，ｓｉｚｅ—ｔＩｄｉｒ，ｆｌｏａｔ’訇ｍｄ，ｓｉｚｅ—ｔｌｄＦａｄ。ｆｌｏａｔ’ｔｉｍｅ，ｓｉｚｅ—ｔｌｄｔｉｍｅ，ｊｍｎ）｛分配共享内存空间ＤＥＭ［ＢＬＯＣＫＳＩＺＥ］［ＢＬＯＣＫ—ＳＩＺＥ］；将该线程孺汁算的分块矩阵的对应行列载入共享内存对应的位置；ｓｙｎｔｈｒｅａｄｓ（）；／／线程同步，确保各个线程需要数据完全装载在共享内存中；ｆｏｒ（ｉｎｔｉ＝ｌ；ｉ＜ＢＬＯＣＫ－ｓＩＺＥ－２：ｉ＋＋）／／只计算中间的１４×１４阶矩阵｛计算出水流方向表，依据栅格水流方向．将其写入ｄｉｒ矩阵中；根据水流方向，计算出水流方向的长度和坡度的比值，放入矩阵ｇｒａｄ中；依据式（１），计算出单个栅格的汇流时间，存入ｔｉｍｅ矩阵；｝ｓｙｎｔｈｒｅａｄｓ（）；／／线程同步，确保以七各个线程计算均完成；将结果写入ＤＩＲ和ＴＩＭＥ矩阵对应的位置；｝４实验分析实验平台为２．６０ＧＨｚ的ＩｎｔｅｌＥ５３００双核处理器，２ＧＢ内存，Ｗｉｎｄｏｗｓ７×６４操作系统。ＧＰＵ为ＮＶＩＤＩＡＧｅＦｏｒｃｅ％００ＧＴ，显存２５６ＭＢ，使用２．２版本的ＣＵＤＡｔｏｏｌｋｉｔ及对应ＳＤＫ。编程环境为Ｖｊｓ脚Ｓｔｕｄｉｏ２００８。考虑到传统的计算方法难以满足高数据量的计算需求，本文算法的计算核心是矩阵相乘计算，需要花费大量的时间，ＧＰＵ在计算矩阵相乘时，比ＣＰＵ要快得多。因此，本文采用改进后的归并排序算法进行数据排序及新的内存分配策略和改进的并行算法进行汇流分析，可巧妙地利用基于ＣＵＤＡ平台的ＧＰＵ强大的并行处理能力来加速计算速度。实验以四川彭州甘溪沟流域的ＤＥＭ图为例，对上述算法并行部分进行验证（参与运算的数据类型均定义为ｆｌｏａｔ类型）。彭州甘溪沟流域ＤＥＭ图采用１６位ＧＲＩＤ数据集，划分为２５１１×２５５０个栅格，计算机中表达为二维矩阵形式。其中最大值为４８１０．００００，最小值为０．００００，空白边界值为一９９９９。实验结果如表ｌ所示。由于数据量仅达到百万级的运算量，且其中包含加速效果不明显的排序运算，速度的提升不是很明显，仅达到４倍多。借助ＧＰＵ强大的并行计算能力，如果数据量进一步增多，将会大大提高运算速度。实验运算过程中的方阵相乘使用ＣＵＤＡ运算的实验数据如表２所示。若矩阵阶数较小，由于ＧＰＵ运算必须经过ＰＣＩ—Ｅ总线传输及显存分配等必要耗时，加速比不明显；若矩阵阶数较大，如在本实验条件下，矩阵阶数达到４５０，加速比就开始增大。实验结果表明，基于ＣＵＤＡ的并行算法比采用ＣＰＵ上的串行算法具有更好的计算能力，能提高系统计算效率。表１生成基于ＤＥＭ的等流时线的运算时间比较ｍＳＣＰＵ卜串行算法基于ＣＵＤＡ的并行算法３２０７６５０表２矩阵乘法运算时间比较咖黯嚣是辙警加速比阶教串行算法并行算法“８“阶数串行算法并行算法…８“１０（５４１无７００６５７１０２Ｘ６．４４１００＜１０４３无１０００１８８０２３２】（８．１０４５０８４７９Ｘ１．０６２０００１５３０８１３８６ｘ１１．０４（下转第２４５１页）第７期细精度地刻画了信念的形成。刘冬宁，等：智能主体的信念认知时态子结构逻辑模型ｆｏｒｉｎｔｅｎｔｉｏｎ３９６．４０２．ｏｆ・２４５１・ａｇｅｎｔ［Ｊ］．ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ，２００６，１７（３）：在Ｂ婀，系统中讨论Ｒ。和月。关系时，本文主要讨论了它们的必然算子。即田和口。对于曰和口的对偶算子◇和◇在本文中并没有讨论，不讨论其的主要原因在于◇和◇算子不是信念形成的关键，同时也对愿望和意图不起关键作用。因此，在下一步工作中的研究重点在于，如何将尺。扩充为动作和动态关系，如将算子曰扩充为［ｎ］或［ａ］“，又如何进一步在子结构演算中丰富Ｒ。关系，使其进一步具有线性、序列性、非分支性和有穷间隔性等性质。同时，还可以通过添加相应的表示将来状态的算子“■”．由相关领域的研究人员形成相应的愿望、意图和ＢＤＩ模型，并最后付诸领域应用。参考文献：【１］吏忠植．智能主体及其应用［Ｍ］．北京：科学出版社，２０００：１２・２２．［２］ＭＯＯＲＥＲＣ．Ａｆｏｒｍａｌｔｈｅｏｒｙｏｆｋｎｏｗｌｅｄｇｅａｎｄａｃｔｉｏｎ［Ｍ］／／ＦｏｒｍａｌＴｈｅｏｒｉｅｓｏｆｔｈｅｐｅｒａｔｉｏｎ。ｌＣｏｍｍｏｎｓｅｎｓｅ［８】ＫＯＮＯＬＩＧＥＫ，ＰＯＬＬＡＣＫＭＥ．Ａｒｅｐｒｅｓｅｎｔａｔｉｏｎａｌｉｓｔｔｈｅｏｒｙｏｆｔｉｏｎ［Ｃ］／／Ｐｒｏｃ【９］ＳＩＮＧＨＭｏｆｉｎｔｅｎ－ＬＩＣＭ’９３．１９９３：３９０．３９５．ｓｙｓｔｅｍｓ：ａＰ．Ｍｕｈｉａｇｅｎｔｔｈｅｏｒｅｔｉｃａｌｆｒａｍｅｗｏｒｋｆｏｒｉｎｔｅｎ－ｄｏｎｓ，ｋｎｏｗ—ｈｏｗ，ａｎｄｃｏｍｍｕｎｉｃａｔｉｏｎｓ［Ｃ］／／ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ．［Ｓ．１．］：Ｓｐｒｉｎｇｅｒ，１９９４．［１０］ＮＡＩＲＶＣＰ．ＯｎｅｘｔｅｎｄｉｎｇＢＤＩｌｏｇｉｃｓ［Ｄ］．Ｑｕｅｅｎｓｌａｎｄ：ＧｒｉｆｆｉｔｈＵｒｄ・ｖｅｒｓｉｔｙ，２００３．［１１］ＲＡＦＡＥＬＨＢ，ＭＥＨＤＩＤ，ＪＩ）ＲＧＥＮＤ，ｅｔａ／．Ｍｕｌｔｉ－ａｇｅｎｔｐｒｏｇｒａｍ－ｒｕｉｎｇ：ｌａｎｇｕａｇｅｓ，ｐｌａｔｆｏｒｍｓａｎｄａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］．Ｂｅｒｌｉｎ：［８．ｎ．］，２００５．［１２］ＲＡＦＡＥＬＨＢ，ＭＩＣＨＡＥＬＦ，ＷＩＬＬＥＭｐｍｇｒａｍｓｂｙｍｏｄｅｌａｎｄＭｕｌｔｉ—ＡｇｅｎｔＶ，ｅｔｏｆ．Ｖｅｒｉｆｙｉｎｇｍｕｌｔｉ—ａｇｅｎｔｃｈｅｃｋｉｎｇ【Ｊ］．ＪｏｕｒｎａｌｏｆＡｕｔｏｎｏｍｏｕｓＡｇｅｎｔｓＷｏｒｌｄ．［Ｓ．１．］：ＡｂｌｅｘＰｕｂｌｉｓｈｉｎｇＣｏｔ－Ｓｙｓｔｅｍｓ，２００６，１２（２）：２３９—２５６．ｍｕｈｉ—ａｇｅｎｔ９８５：３１９—３５８。［１３］ＲＡＦＡＥＬＨＨＢ，ＪＯＭＩＦＨ，ＭＩＣＨＡＥＬＷ．Ｐｒｏｇｒａｍｍｉｎｇ［３］ＣＯＨＥＮＰＲ，ＬＥＶＥＳＱＵＥＪ．ＩｎｔｅｎｔｉｏｎｉｓｃｈｏｉｃｅｗｉｔｈｃｏｍｍｉｔｍｅｎｔｓｙｓｔｅｍｓｉｎＡｇｅｎｔＳｐｅａｋｕｓｉｎｇＪａｓｏｎ【Ｍ］／／［Ｓ．１．］：Ｗｉｌｅｙ，２００７．［Ｊ］．ＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ，１９９０，４２（２－３）：２１３—２６１．［４ＪＲＡＯＡＳ，ＧＥＯＲＧＥＦＦＭＰ．ＤｅｌｉｂｅｒａｔｉｏｎＮｏｔｅｓ１９９１．【１４］ＲＥＳＴＡＬＬＧ．Ａｎｉｎｔｒｏｄｕｃｔｉｏｎｔｏｓｕｂｓｔｒｕｃｔｕｒａｌｌｏｇｉｃｓ［Ｍ］．Ｒｏｕｆｌｅｄｇｅ，Ｔｏｋｙｏ：ＭａｔｈｅｍａｔｉｃＡｌＳｏｃｉｅｔｙｏｆａｎｄｉｎｔｅｎｔｉｏｎｓ，ＴｅｃｈｎｉｃａｌＪａｐａｎ，２０００．ｉｎ１０［Ｒ］．［Ｓ．１．］：ＡｕｓｔｒａｌｉａｎＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅＩｎｓｔｉｔｕｔｅ，［１５］ＯＮＯＨ．Ｐｒｏｏｆ－ｔｈｅｏｒｅｔｉｃｍｅｔｈｏｄｓ２０７．２５４．ｎｏｎｃｌａｓｓｉｃａｌｌｏｇｉｃｓ［Ｒ】．１９９８：［５］ＪＩＡＯＷｅｎ－ｐｉｎｇ，ＳＨＩＺｈｏｎｇ—ｚＩＩｉ．Ｆｏｒｍａｌｉｚｉｎｇｐｏｌｙａｄｉｃ霄一ｃａｌｃｕｌｕｓ［Ｃ］／／Ｐｒｏｃｓｏｎｉｎｇｏｆａｇｅｎｔ’８ｏｎａｔｔｉｔｕｄｅｓｗｉｔｈｔｈｅ４ｔｈＷｏｒｋｓｈｏｐ［１６］刘冬宁．时态信息处理中若干问题的逻辑公理化研究［Ｒ］．广州：ＰｒａｃｔｉｃＡｌＲｅａ－ａｎｄＲａｔｉｏｎａｌｉｔｙ．Ｓｔｏｃｋｈｏｌｍ：［ｓ．ｎ．］，１９９９：２１・２７．中山大学，２００９．［１７］ＣＡＭＩＬＯ．Ｔ．ＴｈｅＢＤＩ［６］胡山立，石纯一．Ａｇｅｎｔ意图的双子集语义改进模型［Ｊ］．软件学报。２００６，１７（３）：３９６－４０２．［７】ＨＵＳｈａｌｌ—ｌｉ，ＳＨＩＣｈｕｎ－ｙｉ．Ａｎｉｍｐｒｏｖｅｄｔｗｉｎ—ｓｕｂｓｅｔｓｅｍａｎｔｉｃｍｏｄｅｌｏｆａｇｅｎｃｙａｎｄＢＤＩｌｏｇｉｃｓ［Ｒ］．２００５．【１８］ＢＵＬＬＩＮＧＮ．Ｍｏｄａｌｌｏｇｉｃｓｆｏｒｇａｍｅｓ，ｔｉｍｅ，ａｎｄｂｅｌｉｅｆｓ［Ｄ】．［ｓ．１．］：ｍｏｄｅｌＣｈｕｓｔｈａｌＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，２００６．（上接第２４４７页）ｐａｒａｌｌｅｌｃｏｐｒｏｃｅｓｓｏｒ［Ｒ］．Ｔｏｒｏｎｔｏ：ＵｎｉｖｅｒｓｉｔｙｏｆＴｏｍｎｌｏ，２００８．［５］詹道江，叶守泽．工程水文学［Ｍ］．北京：中国水利水电出版社，５结束语本文算法能提高系统的计算效率，具有较好的效果。实验表明，对相同的数据，通过比较分析生成基于ＤＥＭ的等流时线的运算时间和矩阵乘法的运算时间，ＧＰＵ比ＣＰＵ的计算处理速度要快很多。基于ＣＵＤＡ平台可在一台主机上运行多个ＧＰＵ，通过ＣＰＵ的线程来管理多个ＧＰＵ，或建立ＧＰＵ集群，使其计算性能得到更大的提升。可以将基于ＣＵＤＡ的汇流分析的并行算法的设计思想应用于涉及到需求转换后能应用快速并行计算的各种项目系统中，以提高系统的计算效率。本文的算法设计思想和相关技术解决方法，为相关功能的实现提出了新的思路和解决办法，将对构建模型化、定量化、直观现代的新型自然灾害监测预警分析系统等提供重要的借鉴与参考。参考文献：［１】吴恩华．图形处理器用于通用计算技术、现状及其挑战［Ｊ］，软件学报，２００４，１５（１０）：１４９３—１５４０．２０００：９６．［６］熊立华，彭定志．基于高程模型的等流时线推求与应用［Ｊ］．武汉大学学报：工学版，２００３，３６（３）：１－３．［７】ＫＲＩＳＨＮＡＮＭ，ＮＩＥＰＬＯＣＨＡＪ．ＳＲＵＭＭＡ：ａｍａｔｒｉｘｍｕｌｔｉｐｌｉｃａｔｉｏｎＡｌ－ｍｅｍｏｒｙｓｙｓｔｅｍｓｇｕｒｉｔｈｍｓｕｉｔａｂｌｅｆｏｒｃｌｕｓｔｅｒｓａｎｄｓｅａｌａｂｌｅｓｈａｒｅｄ［ｃ］／／Ｐｍｃｏｆｔｈｅ１８ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＰａｒａｌｌｅｌａｎｄＤｉｓｔｒｉｂｕｔｅｄＰｒｏｃｅｓ－ｓｉｎｇＳｙｍｐｏｓｉｕｍ．ＷａｓｈｉｎｇｔｏｎＤＣ：ＩＥＥＥＣｏｍｐｕｔｅｒＳｏｃｉｅｔｙ，２００４．［８］ＮＶＩＤＩＡ．ＣＵＤＡｐｒｏｇｒａｍｍｎｇｇｕｉｄｅ［ｚ］．２００９．［９］ＮＶＩＤＩＡｏｆｆｉｃｉａｌｓｉｔｅ［ＥＢ／ＯＬ］．（２００９）．ｈａｐ：／／ｗｗｗ．ｎｖｉｄｉａ．ｃｅｎｔ／．［１０］Ｉｎｔｅｌｏｆｆｉｃｉａｌｓｉｔｅ［ＥＢ／ＯＬ】．（２００９）．ｈｕｐ：／／ｗｗｗ．ｉｎｔｅｌ．ｔｏｍ／．［１Ｉ］ＮＶＩＤＩＡ．ＮＶＩＤＡＣＵＤＡｃｏｍｐｕｔｅｕｎｉｆｉｅｄｄｅｖｉｃｅａｒｃｈｉｔｅｃｔｕｒｅｒｅｆｅｒｅｎｃｅｍａｎｕａｌ［ＥＢ／ＯＬ］．［２００８－０８・２０］．ｈｔｔｐ：／／ｗｗｗ．ｎｖｉｄｉａ．ｃｏｒｎ／ｏｂｊｅｃｔ／ｃｕｄｓ／ｃｕｄａ＿ｄｅｖｅｌｏｐ．ｈｔｎｄ．［１２］杜尚海，吏超，王晶晶．基于数字高程模型的小流域等流时线绘制方法及应用［ｊ］．中国环境管理，２００６，６（论文专辑）：４４－４５．［１３］ＳＡＴＩＳＨＮ，ＨＡＲＲＩＳＭ。ＧＡＲＬＡＮＤＭ．Ｄｅｓｉｇｎｉｎｇｅｆｆｉｃｉｅｎｔｓｏｒｔｉｎｇａｌ－ｇｕｒｉｔｈｍｓｆｏｒｍａｎｙｃｏｒｅＧＰＵｓ［ＥＢ／ＯＬ】．［２００８—０９－１５．］．ｈｔｔｐ：／／ｍｇａｒ－ｌａｎｄ．ｏｒｇ／ｆｉｌｅｓ／ｐａｐｅｒｓ／ｎｖｒ－２００８・００１．ｐｄｆ．［２］张舒，褚艳利．ＧＰＵ高性能运算之ＣＵＤＡ【Ｍ］．北京：中国水利水电出版杜．２００９．［３］ＧＯＴＩＬＩＥＤＡ，ＨＷＡＮＧＫ，ＳＡＨＮＩＳ．Ｓｐｅｃｉａｌｐｏｓｅｐｒｏｃｅｓｓｉｎｇｉｓｓｕｅｏｎ［１４］ＬＥＦＯＨＮＡ，ＫＮＩＳＳＪ，ＯＷＥＮＳＪ．ＩｍｐｌｅｍｅｎｔｉｎｇｅｆｆｉｃｉｅｎｔｐａｒａｌｌｅｌｄａｔａｓｔｒｕｃｔｕｒｅｓｏｎＧＰＵｓ［Ｃ】／／ＰｒｏｃｏｆＧＰＵＧｒａｐｈｉｃｓｇｅｍｓ２：ＴｅｃｈｎｉｑｕｅｓｆｏｒＨｉｓｈｇｅｎｅｒａｌ—ｐｕｒ－ＰｅｒｆｏｒｍａｎｃｅａｎｄＧｅｎｅｒａｌＰｕｒｐｏ∞Ｃｏｍｐｕｔａｔｉｏｎ．Ｂｏｓｔｏｎ，ＭＡ：ｕｓｉｎｇｇｒａｐｈｉｃｓｐｒｏｃｅｓｓｉｎｇｕｎｉｔｓ【Ｊ］．ＪｏｕｍａｌｏｆＰａｒａｌ－Ａｄｄｉｓｏｎ－Ｗｅｓｌｅｙ。２００５：５１２－５４５．ｌｅｌａｎｄＤｉｓｔｄｂｕｔｅｄＣｏｍｐｕｔｉｎｇ，２００８，６８（１０）：１３０５・１４０２．ｏｎａ［１５］苏畅。付忠良。谭雨展．一种在ＧＰＵ上高精度大型矩阵快速运算ｄａｔａ［４］ＬＥＳＳＩＧＣ．ＡｎｉｍｐｌｅｍｅｎｔａｔｉｏｎｏｆｔｈｅＭＲＲＲＡｌｇｏｒｉｔｈｍ的实现［Ｊ】．计算机应用，２００９．２９（４）：１１７７－１１７９．万方数据