• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 11
    • 下载费用:30 金币  

    重庆时时彩玩法说明: 基于GPU排序的MAPREDUCE优化方法.pdf

    摘要
    申请专利号:

    重庆时时彩单双窍门 www.4mum.com.cn CN201710026869.7

    申请日:

    2017.01.15

    公开号:

    CN106802787A

    公开日:

    2017.06.06

    当前法律状态:

    实审

    有效性:

    审中

    法律详情: 实质审查的生效IPC(主分类):G06F 9/38申请日:20170115|||公开
    IPC分类号: G06F9/38; G06F9/50 主分类号: G06F9/38
    申请人: 天泽信息产业股份有限公司
    发明人: 李鹏飞; 丁有伟; 孙杰
    地址: 210019 江苏省南京市建邺区云龙山路80号
    优先权:
    专利代理机构: 南京中盟科创知识产权代理事务所(特殊普通合伙) 32279 代理人: 孙丽君
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201710026869.7

    授权公告号:

    |||

    法律状态公告日:

    2017.06.30|||2017.06.06

    法律状态类型:

    实质审查的生效|||公开

    摘要

    本发明提出了一种基于GPU排序的MapReduce优化方法,其中MapReduce包含Map阶段、Shuffle阶段、以及Reduce阶段,Map阶段包含Spill过程和Merge过程,Reduce阶段包含Merge过程,其中,在Map阶段的Spill过程中采用基于GPU的快速排序流程,在Map阶段的Merge过程中和Reduce阶段的Merge过程中采用基于GPU的归并排序流程。通过以基于GPU的快速排序和归并排序算法替代传统的基于CPU的快速排序、归并排序和堆排序算法,提高中间数据处理速度,进而提升MapReduce的性能。

    权利要求书

    1.一种基于GPU排序的MapReduce优化方法,其中:MapReduce包含:Map阶段、Shuffle阶
    段、以及Reduce阶段,所述Map阶段包含Spill过程和Merge过程,所述Reduce阶段包含Merge
    过程,其特征在于,在所述Map阶段的Spill过程中采用基于GPU的快速排序流程,在所述Map
    阶段的Merge过程中和Reduce阶段的Merge过程中采用基于GPU的归并排序流程,其中:
    所述基于GPU的快速排序流程包含步骤:
    (1.1)将数据存入GPU的全局存储空间,并划分成m个互不重叠的数据块,每个数据块由
    一个线程块处理;
    (1.2)所述m个线程块并行地遍历对应的数据块,每个线程块内部n个线程并行地遍历
    相应数据块的一部分,并记录大于和小于分界值的元素的个数;
    (1.3)依次统计每个线程块内部的每个线程的相对计数值;
    (1.4)依次统计每个线程块的计数值和相对计数值;
    (1.5)所有线程进行数据交换,序列分成大于分界值和小于分界值的两个子序列:子序
    列1、子序列2;
    (1.6)对步骤(1.5)中产生的所述子序列1、所述子序列2分别再采用步骤(1.1)-(1.5)
    进行排序,直到最终排序完成,即可实现对原始序列的排序,
    所述基于GPU的归并排序流程包含步骤:
    (2.1)将待归并的序列两两分组,分成h组,每组序列包含Ai和Bi两个序列,每次对一组
    序列Ai和Bi进行归并,其中1≤i≤h,Ai和Bi表示第i个分组包含的两个序列;
    (2.2)分别将Ai和Bi划分成m个子序列,每个线程块对Ai的一个子序列和Bi的一个子序列
    进行归并,共需进行log2 m+1轮子序列的归并即可将序列Ai和Bi归并为一个有序序列Ci;
    (2.3)重复步骤(2.2),直到所有分组的序列Ai和Bi归并完成,分别产生每个分组的归并
    结果C1、C2、……、Ch;其中1≤i≤h,Ai和Bi表示第i个分组包含的两个序列,Ci为Ai和Bi归并完
    成后产生的有序序列;
    (2.4)对h个分组的归并结果C1、C2、……、Ch,重复步骤(2.1)-(2.3)进行归并,直到产生
    最终归并结果。
    2.如权利要求1所述的基于GPU排序的MapReduce优化方法,其特征在于,基于GPU的快
    速排序流程的步骤(1.3)中,线程块Bk(1≤k≤m)中的每个线程的计数值分别为Lk,1,...,
    Lk,n和Rk,1,...,Rk,n,则第i(1≤i≤n)个线程的相对计数值分别为:

    其中Lk,1和Rk,1分别表示线程块Bk中第1个线程遍历的数据中比分界值小的数据个数和
    比分界值大的数据个数,Lk,n和Rk,n分别表示线程块Bk中第n个线程遍历的数据中比分界值
    小的数据个数和比分界值大的数据个数,Lk,j和Rk,j分别表示线程块Bk中第j个线程遍历的
    数据中比分界值小的数据个数和比分界值大的数据个数,BLk,i和BRk,i分别表示线程块Bk中
    第i个线程的相对计数值,即该线程块中前i-1个线程遍历的数据中比分界值小的数据总量
    和比分界值大的数据总量。
    3.如权利要求1所述的基于GPU排序的MapReduce优化方法,其特征在于,基于GPU的快
    速排序流程的步骤(1.4)中,线程块Bk(1≤k≤m)的计数值分别为和
    线程块Bk的相对计数值分别为和其中Lk、Lj和
    Rk、Rj分别表示线程块Bk和Bj遍历的数据块内小于分界值的数据总量和大于分界值的数据
    总量,SLk和SRk分别表示线程块Bk之前的k-1个线程块遍历的数据块中小于分界值的数据总
    量和大于分界值的数据总量。
    4.如权利要求1所述的基于GPU排序的MapReduce优化方法,其特征在于,基于GPU的快
    速排序流程的步骤(1.5)中,每个线程块中每个线程将其遍历的小于分界值的数据依次交
    换到分界值左侧,大于分界值的数据依次交换到分界值右侧,然后每个线程块将对应位置
    的数据块写入辅助单元,加入分界值并根据分界值将序列分成比分界值小和比分界值大的
    两个子序列:子序列1和子序列2。
    5.如权利要求1所述的基于GPU排序的MapReduce优化方法,其特征在于,步骤(2.2)中,
    包含以下子步骤:
    (2.21)对于Ai和Bi的第k轮归并(0≤k≤log2 m),产生m/2k个归并结果R1,R2,……,Rkr,
    并将每个归并结果Rp(1≤p≤kr)划分为2k个子序列Rp,1,Rp,2,……,Rp,km;其中kr(kr=m/2k)
    表示序列Ai和Bi的第k轮归并产生的归并结果数量,R1、R2和Rkr分别表示第1个、第2个以及第
    kr个归并结果,km(其中km=2k)表示序列Ai和Bi的第k轮归并产生的每个归并结果划分的子
    序列个数,Rp,1、Rp,2和Rp,km分别表示第p(1≤p≤kr)个归并结果划分后的第1个、第2个和第
    km个子序列;
    (2.22)对于Ai和Bi的第k+1轮归并(0≤k<log2 m),将第k轮产生的m/2k个归并结果依次
    两两分组(R1,R2),...,(Rkr-1,Rkr),每一组归并结果(Ri-1,Ri)(1≤i≤m/2k)相同位置的子序
    列由同一线程块进行归并,即子序列Ri-1,1和Ri,1、Ri-1,2和Ri,2、...、Ri-1,km和Ri,km分别由一个
    线程块进行归并,本轮参与归并操作的线程块数量为m;
    (2.23)重复子步骤(2.21)-(2.22),直到序列Ai和Bi归并完成,输出该分组的归并结果
    Ci。

    说明书

    基于GPU排序的MapReduce优化方法

    技术领域

    本发明涉及MapReduce技术,尤其涉及一种MapReduce的优化处理方法。

    背景技术

    MapReduce是一种分布式编程框架,在云计算和大数据处理中应用非常广泛。
    MapReduce流程如图1所示,分为Map、Shuffle和Reduce三个阶段,Map和Reduce阶段分别执
    行用户编写的Map()和Reduce()程序,而Shuffle阶段介于Map阶段和Reduce阶段中间,用
    于对Map阶段产生的中间结果进行处理,为Reduce阶段准备数据。具体而言,Map阶段包括如
    下几个步骤:

    数据读入(Read):从分布式文件系统中读入数据;

    Map执行(Map):执行用户编写的Map()函数;

    数据收集(Collect):将Map产生的结果存入缓冲区;

    缓存溢写(Spill):当缓存中数据量超过阈值时,将缓存中的数据写入本地硬盘;

    溢写合并(Merge):多次缓存溢写会产生多个溢写文件,需要将所有的溢写文件合
    并成一个输出文件。

    Shuffle阶段的详细操作如下:

    中间数据传输(Copy):将Map端的中间结果通过网络传输到Reduce端的缓冲区;

    缓存溢写(Spill):Reduce端的缓冲区数据量超过阈值时,将缓冲区数据写入本地
    硬盘,每次写入形成一个shuffle文件;

    Reduce阶段的具体流程如下:

    Shuffle文件合并(Merge):在Reduce端将大量的shuffle文件合并形成少量的大
    文件,并将大文件合并形成一个有序的大文件;

    Reduce执行(Reduce):执行用户编写的Reduce()函数;

    数据输出(Output):将Reduce产生的结果输出到分布式文件系统。

    从以上分析可以看出MapReduce框架对中间结果的处理非常复杂,需要花费大量
    的处理时间,尤其是其中包含的四次排序操作:①Map阶段的Spill过程中,每次溢写时需要
    将溢写文件进行排序,一般采用快速排序方法;②Map阶段的Merge过程中,溢写文件合并步
    骤采用归并排序的方法;③Reduce阶段的Merge过程中,采用归并排序方法将大量的
    shuffle文件合并成少量的大文件;④Reduce阶段的Merge过程中,采用堆排序方法将多个
    大文件合并成为一个有序的大文件。由于常用的基于CPU的排序算法的时间复杂度通常为O
    (N·logN),其中N为待排序数据个数或记录条数,当数据量很大时排序操作消耗的时间很
    长,而MapReduce通常用于大数据处理。

    GPU因其强大的计算能力以及相对较低的性能价格比,通常用GPU替代CPU用以提
    高任务处理性能。使用GPU对MapReduce进行优化的方法主要有两类,一是与用户程序相关
    的优化方法,即对MapReduce框架进行扩展,使MapReduce程序执行过程中可以使用GPU设备
    替代CPU,提高程序执行效率;二是与用户程序无关的优化方法,即修改MapReduce框架或者
    组件,使MapReduce框架更好的发挥GPU性能,从而提高效率。用户程序相关的优化方法需要
    用户参与进行任务分配,需要用户对程序的处理流程和GPU的编程规范非常熟悉,并且不同
    的用户程序之间优化方法不可重用。而现有的基于GPU排序的MapReduce优化方法只针对第
    一次排序过程的优化,即将基于CPU的快速排序算法替换成基于GPU的快速排序算法或者基
    于GPU的双调排序算法,而对于其他三次排序操作并不关注,对MapReduce性能的提升有限。

    发明内容

    本发明的目的在于克服现有技术的不足,提出一种基于GPU排序的MapReduce优化
    方法,将MapReduce执行流程中的四次排序操作全部使用GPU执行,并分别使用基于GPU的快
    速排序和归并排序算法替代传统的基于CPU的快速排序、归并排序和堆排序算法,提高中间
    数据处理速度,进而提升MapReduce的性能。为实现本发明的目的,本发明的基于GPU排序的
    MapReduce优化方法中,MapReduce包含:Map阶段、Shuffle阶段、以及Reduce阶段,Map阶段
    包含Spill过程和Merge过程,Reduce阶段包含Merge过程,其中,在Map阶段的Spill过程中
    采用基于GPU的快速排序流程,在Map阶段的Merge过程中和Reduce阶段的Merge过程中采用
    基于GPU的归并排序流程,其中:

    基于GPU的快速排序流程包含步骤:

    (1.1)将数据存入GPU的全局存储空间,并划分成m个互不重叠的数据块,每个数据
    块由一个线程块处理;

    (1.2)m个线程块并行地遍历对应的数据块,每个线程块内部n个线程并行地遍历
    相应数据块的一部分,并记录大于和小于分界值的元素的个数;

    (1.3)依次统计每个线程块内部的每个线程的相对计数值;

    (1.4)依次统计每个线程块的计数值和相对计数值;

    (1.5)所有线程进行数据交换,序列分成大于分界值和小于分界值的两个子序列:
    子序列1,、子序列2;

    (1.6)对步骤(1.5)中产生的子序列1、子序列2分别再采用步骤(1.1)-(1.5)进行
    排序,直到最终排序完成,即可实现对原始序列的排序,

    基于GPU的归并排序流程包含步骤:

    (2.1)将待归并的序列两两分组,分成h组,每组序列包含Ai和Bi两个序列,每次对
    一组序列Ai和Bi进行归并,其中1≤i≤h,Ai和Bi表示第i个分组包含的两个序列;

    (2.2)分别将Ai和Bi划分成m个子序列,每个线程块对Ai的一个子序列和Bi的一个
    子序列进行归并,共需进行log2 m+1轮子序列的归并即可将序列Ai和Bi归并为一个有序序
    列Ci;

    (2.3)重复步骤(2.2),直到所有分组的序列Ai和Bi归并完成,分别产生每个分组的
    归并结果C1、C2、……、Ch;其中1≤i≤h,Ai和Bi表示第i个分组包含的两个序列,Ci为Ai和Bi归
    并完成后产生的有序序列;

    (2.4)对h个分组的归并结果C1、C2、……、Ch,重复步骤(2.1)-(2.3)进行归并,直到
    产生最终归并结果。

    进一步地,在步骤(1.3)中,线程块Bk(1≤k≤m)中的每个线程的计数值分别为
    Lk,1,...,Lk,n和Rk,1,...,Rk,n,则第i(1≤i≤n)个线程的相对计数值分别为:


    其中Lk,1和Rk,1分别表示线程块Bk中第1个线程遍历的数据中比分界值小的数据个
    数和比分界值大的数据个数,Lk,n和Rk,n分别表示线程块Bk中第n个线程遍历的数据中比分
    界值小的数据个数和比分界值大的数据个数,Lk,j和Rk,j分别表示线程块Bk中第j个线程遍
    历的数据中比分界值小的数据个数和比分界值大的数据个数,BLk,i和BRk,i分别表示线程块
    Bk中第i个线程的相对计数值,即该线程块中前i-1个线程遍历的数据中比分界值小的数据
    总量和比分界值大的数据总量。

    进一步地,在步骤(1.4)中,线程块Bk(1≤k≤m)的计数值分别为和
    线程块Bk的相对计数值分别为和其中Lk、Lj和
    Rk、Rj分别表示线程块Bk和Bj遍历的数据块内小于分界值的数据总量和大于分界值的数据
    总量,SLk和SRk分别表示线程块Bk之前的k-1个线程块遍历的数据块中小于分界值的数据总
    量和大于分界值的数据总量。

    进一步地,在步骤(1.5)中,每个线程块中每个线程将其遍历的小于分界值的数据
    依次交换到分界值左侧,大于分界值的数据依次交换到分界值右侧,然后每个线程块将对
    应位置的数据块写入辅助单元,加入分界值并根据分界值将序列分成比分界值小和比分界
    值大的两个子序列:子序列1和子序列2。

    进一步地,在步骤(2.2)中,包含以下子步骤:

    (2.21)对于Ai和Bi的第k轮归并(0≤k≤log2 m),产生m/2k个归并结果R1,R2,……,
    Rkr,并将每个归并结果Rp(1≤p≤kr)划分为2k个子序列Rp,1,Rp,2,……,Rp,km;其中kr(kr=m/
    2k)表示序列Ai和Bi的第k轮归并产生的归并结果数量,R1、R2和Rkr分别表示第1个、第2个以
    及第kr个归并结果,km(其中km=2k)表示序列Ai和Bi的第k轮归并产生的每个归并结果划分
    的子序列个数,Rp,1、Rp,2和Rp,km分别表示第p(1≤p≤kr)个归并结果划分后的第1个、第2个
    和第km个子序列;

    (2.22)对于Ai和Bi的第k+1轮归并(0≤k<log2 m),将第k轮产生的m/2k个归并结果
    依次两两分组(R1,R2),...,(Rkr-1,Rkr),每一组归并结果(Ri-1,Ri)(1≤i≤m/2k)相同位置的
    子序列由同一线程块进行归并,即子序列Ri-1,1和Ri,1、Ri-1,2和Ri,2、...、Ri-1,km和Ri,km分别由
    一个线程块进行归并,本轮参与归并操作的线程块数量为m;

    (2.23)重复子步骤(2.21)-(2.22),直到序列Ai和Bi归并完成,输出该分组的归并
    结果Ci。

    在本发明中,通过在Map阶段的Spill过程中将基于CPU的快速排序替换为基于GPU
    的快速排序;在Map阶段的Merge过程中将基于CPU的归并排序替换为基于GPU的归并排序;
    在Reduce阶段的Merge过程中,将基于CPU的归并排序和堆排序均替换为基于GPU的归并排
    序。由GPU实现的归并排序的性能比堆排序的性能更优,且Merge过程中的堆排序本质上是
    将有序的大文件合并为一个大文件。因此本发明的基于GPU排序的MapReduce优化方法充分
    利用了GPU设备强大的计算能力替代CPU完成MapReduce对中间结果的排序,将MapReduce中
    四次基于CPU的排序操作(包括一次快速排序、两次归并排序和一次堆排序)替换为基于GPU
    的快速排序和归并排序操作,加快排序的速度,进而很大程度地提高了MapReduce的性能。

    相比传统的入侵检测系统中网络日志采集和存储方法,本发明具有如下优点:

    ①用基于GPU的排序算法替代基于CPU的排序算法,充分利用GPU的强大计算能力,
    提高中间数据处理速度,进而提升MapReduce性能;

    ②不需要对MapReduce框架进行修改,只替换对中间结果的排序算法,实现难度较
    ??;

    ③可以与其他基于用户程序的优化方法以及基于MapReduce框架的优化方法同时
    使用,适用范围广泛;

    ④由于GPU设备的应用越来越多,很多服务器和个人计算机均已配置GPU设备,因
    此本发明可以充分发挥现有GPU设备的计算能力,即便新购买GPU设备的硬件成本也不高。

    附图说明

    下面结合附图对本发明作进一步描写和阐述。

    图1是现有技术中MapReduce的流程图。

    图2是本发明首选实施方式的优化方法中基于GPU的快速排序流程。

    图3是本发明首选实施方式的优化方法中基于GPU的归并排序流程的一个流程示
    例。

    具体实施方式

    如现有技术中所述,MapReduce包含:Map阶段、Shuffle阶段、以及Reduce阶段,Map
    阶段包含Spill过程和Merge过程,Reduce阶段包含Merge过程。

    本发明的基于GPU排序的MapReduce优化方法中,采用GPU快速排序替代Map阶段的
    Spill过程中基于CPU的快速排序;采用基于GPU的归并排序替代Map阶段的Merge过程中基
    于CPU的归并排序;采用基于GPU的归并排序替代Reduce阶段的Merge过程中基于CPU的归并
    排序。

    基于GPU的快速排序流程包含:

    (1.1)将数据存入GPU的全局存储空间,并划分成m个互不重叠的数据块,每个数据
    块由一个线程块处理;如图2中a序列划分和b线程遍历所示;

    (1.2)m个线程块并行地遍历对应的数据块,每个线程块内部n个线程并行地遍历
    相应数据块的一部分,并记录大于和小于分界值的元素的个数;如图2中c遍历计数所示;

    (1.3)依次统计每个线程块内部的每个线程的相对计数值;在图2中d技术累加中
    进行;其中线程块Bk(1≤k≤m)中的每个线程的计数值分别为Lk,1,...,Lk,n和Rk,1,...,Rk,n,
    则第i(1≤i≤n)个线程的相对计数值分别为:


    其中Lk,1和Rk,1分别表示线程块Bk中第1个线程遍历的数据中比分界值小的数据个
    数和比分界值大的数据个数,Lk,n和Rk,n分别表示线程块Bk中第n个线程遍历的数据中比分
    界值小的数据个数和比分界值大的数据个数,Lk,j和Rk,j分别表示线程块Bk中第j个线程遍
    历的数据中比分界值小的数据个数和比分界值大的数据个数,BLk,i和BRk,i分别表示线程块
    Bk中第i个线程的相对计数值,即该线程块中前i-1个线程遍历的数据中比分界值小的数据
    总量和比分界值大的数据总量。

    (1.4)依次统计每个线程块的计数值和相对计数值;在图2中d技术累加中进行;线
    程块Bk(1≤k≤m)的计数值分别为和线程块Bk的相对计数值分
    别为和

    其中Lk、Lj和Rk、Rj分别表示线程块Bk和Bj遍历的数据块内小于分界值的数据总量
    和大于分界值的数据总量,SLk和SRk分别表示线程块Bk之前的k-1个线程块遍历的数据块中
    小于分界值的数据总量和大于分界值的数据总量。

    (1.5)所有线程进行数据交换,序列分成大于分界值和小于分界值的两个子序列:
    子序列1,、子序列2;如图2中所示e数据交换、f数据回写、g划分子序列,其中e数据交换后进
    行f数据回写,数据回写完毕形成两子序列,即g划分子序列;更具体一点,首先每个线程块
    中每个线程将其遍历的小于分界值的数据依次交换到分界值左侧,大于分界值的数据依次
    交换到分界值右侧,如第k个线程块的第i个线程中小于分界值的数据从序列的SLk+BLk,i位
    置依次存放至SLk+BLk,i+Lk,i位置,然后每个线程块将对应位置的数据块写入辅助单元,加
    入分界值并根据分界值将序列分成比分界值小和比分界值大的两个子序列:子序列1和子
    序列2。

    (1.6)对步骤(1.5)中产生的子序列1、子序列2分别再采用步骤(1.1)-(1.5)进行
    排序,直到最终排序完成,即可实现对原始序列的排序。

    为了提高GPU的利用率,基于GPU的归并排序方法的具体操作步骤如下:

    (2.1)将待归并的序列两两分组,分成h组,每组序列包含Ai和Bi两个序列,每次对
    一组序列Ai和Bi进行归并,其中1≤i≤h,Ai和Bi表示第i个分组包含的两个序列;

    (2.2)分别将Ai和Bi划分成m个子序列,每个线程块对Ai的一个子序列和Bi的一个
    子序列进行归并,共需进行log2 m+1轮子序列的归并即可将序列Ai和Bi归并为一个有序序
    列Ci;更具体地,步骤(2.2)细化为下面子步骤:

    (2.21)对于Ai和Bi的第k轮归并(0≤k≤log2 m),产生m/2k个归并结果R1,R2,……,
    Rkr,并将每个归并结果Rp(1≤p≤kr)划分为2k个子序列Rp,1,Rp,2,……,Rp,km;其中kr(kr=m/
    2k)表示序列Ai和Bi的第k轮归并产生的归并结果数量,R1、R2和Rkr分别表示第1个、第2个以
    及第kr个归并结果,km(其中km=2k)表示序列Ai和Bi的第k轮归并产生的每个归并结果划分
    的子序列个数,Rp,1、Rp,2和Rp,km分别表示第p(1≤p≤kr)个归并结果划分后的第1个、第2个
    和第km个子序列;

    (2.22)对于Ai和Bi的第k+1轮归并(0≤k<log2 m),将第k轮产生的m/2k个归并结果
    依次两两分组(R1,R2),...,(Rkr-1,Rkr),每一组归并结果(Ri-1,Ri)(1≤i≤m/2k)相同位置的
    子序列由同一线程块进行归并,即子序列Ri-1,1和Ri,1、Ri-1,2和Ri,2、...、Ri-1,km和Ri,km分别由
    一个线程块进行归并,本轮参与归并操作的线程块数量为m;

    (2.23)重复子步骤(2.21)-(2.22),直到序列Ai和Bi归并完成,输出该分组的归并
    结果Ci。

    (2.3)重复步骤(2.2),直到所有分组的序列Ai和Bi归并完成,分别产生每个分组的
    归并结果C1、C2、……、Ch;其中1≤i≤h,Ai和Bi表示第i个分组包含的两个序列,Ci为Ai和Bi归
    并完成后产生的有序序列;

    (2.4)对h个分组的归并结果C1、C2、……、Ch,重复步骤(2.1)-(2.3)进行归并,直到
    产生最终归并结果。

    图3所示为子序列A1和B1划分为4个子序列,采用4个线程块进行归并排序的流程示
    例,其中G1、G2、G3、……、Gn表示用以进行子序列归并的第1、2、3...n个线程块,每个线程块
    在每一轮归并中处理的子序列不同,Ri,j(1≤i≤n,1≤j≤n)表示每轮归并过程中产生的第
    i个归并结果的第j个子序列。

    上述具体实施方式仅仅对本发明的优选实施方式进行描述,而并非对本发明的保
    护范围进行限定。在不脱离本发明设计构思和精神范畴的前提下,本领域的普通技术人员
    根据本发明所提供的文字描述、附图对本发明的技术方案所作出的各种变形、替代和改进,
    均应属于本发明的?;し冻?。本发明的?;し段в扇ɡ笕范?。

    关 键 词:
    基于 GPU 排序 MAPREDUCE 优化 方法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:基于GPU排序的MAPREDUCE优化方法.pdf
    链接地址://www.4mum.com.cn/p-6000531.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03