基于GPU并行的自适应基数树动态索引方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN112000847A(43)申请公布日2020.11.27(21)申请号202010836011.9(22)申请日2020.08.19(71)申请人东北大学地址110819辽宁省沈阳市和平区文化路3号巷11号(72)发明人谷峪宛长义李传文宋振于戈(74)专利代理机构沈阳东大知识产权代理有限公司21109代理人李在川(51)Int.Cl.G06F16/901(2019.01)G06F16/245(2019.01)权利要求书3页说明书8页附图3页(54)发明名称基于GPU并行的自适应基数树动态索引方法(57)摘要本发明提供一种基于GPU并行的自适应基数树动态索引方法。首先构建自适应基数树数据结构，前两层创建Node256类型的树节点，第三、四层的创建基于高位优先的基数排序方法，根据分支的数量创建能容下对应大小的树节点，实现动态数据结构的创建，可以保证在原批数据中最新的更新在进行排序后仍旧是在旧的更新后面，然后去重操作，去掉多余的旧更新保留最新的更新，去重之后再把每一段无重复数据的序列插入该段对应的节点内，完成对整个自适应基数树的创建，其次基于GPU并行计算能力，可以并行进行对数据的插入、查询、删除操作。CN112000847ACN112000847A权利要求书1/3页1.一种基于GPU并行的自适应基数树动态索引方法，其特征在于，包括如下步骤：步骤1：构建层数为四层的自适应基数树数据结构，包括：步骤1.1：创建第一、二层Node256类型的树节点，并连接第二层和第一层；步骤1.2：将待存储的S个整型数据进行高位优先的基数排序，创建自适应基数树的第三层、第四层数据结构，并连接第二层和第三层，连接第三层和第四层；步骤1.3：利用warp中每个线程处理一个8bit的键key来进行去重操作，若warp内第x个线程处理的第x个数据等于第x+1个数据，则结束对第x个数据的处理，其中x＝0,1,…,X，X表示一个warp中处理的数据总个数；步骤1.4：将去重之后每一分支内无重复数据的序列插入到自适应基数树的节点中；步骤2：针对构建的自适应基数树数据结构，利用warp对数据进行查询操作；步骤3：针对构建的自适应基数树数据结构，利用warp对数据进行插入操作；步骤4：针对构建的自适应基数树数据结构，利用warp对数据进行删除操作。2.根据权利要求1所述的一种基于GPU并行的自适应基数树动态索引方法，其特征在于，步骤1.1包括：步骤1.1.1：创建一个Node256类型的节点N1,1作为自适应基数树的第一层，即自适应基数树的第一层分支，则节点N1,1表示为i＝0,1,…,255，表示第一层节点的第i个值value；步骤1.1.2：以为节点创建一个Node256类型的节点N2,i作为自适应基数树的第二层第i个分支，则节点N2,i表示为j＝0,1,…,255，表示第二层的第i个节点的第j个值value；步骤1.1.3：令i＝0,1,…,255，利用GPU的warp并行为第一层的每个值value创建一个Node256类型的节点，得到自适应基数树第二层的256个分支；步骤1.1.4：将第二层第i个节点的指针存放在第一层的第i个值value中。3.根据权利要求1所述的一种基于GPU并行的自适应基数树动态索引方法，其特征在于，步骤1.2包括：步骤1.2.1：将S个数据中0～7bit均相同的数据分到第一层分支中；步骤1.2.2：将第一层每一分支中8～15bit均相同的数据分到第二层的同一个分支中，则第二层的每个分支中存储的数据均为前缀相同的数据；步骤1.2.3：利用GPU的warp并行对第二层的每个分支中数据的16～23bit进行高位优先的基数排序，将前缀相同的数据中16～23bit均相同的数据分为一组，定义第二层的第i个分支中前缀相同的数据被分为Hi组，第二层第i个分支中的第hi组数据的数量为个，hi＝0,1,…,Hi；步骤1.2.4：以第二层第i个分支中的每个值value为节点依次创建一个节点容量大于等于的节点类型作为自适应基数树的第三层的第i*hi个分支，则表示为u＝1,2,…,U，U∈{4,16,48,256}，且表示第三层的第i*hi个节点的第u个值value，所述节点类型包括Node4类型的节点、Node16类2CN112000847A权利要求书2/3页型的节点、Node48类型的节点和Node256类型的节点；步骤1.2.5：令hi＝0,1,…,Hi,i＝0,1,…,255，利用GPU的warp并行为第二层的每个值value创建一个节点容量大于等于待存放数据大小的节点类型，得到自适应基数树第三层的所有分支；步骤1.2.6：将第个节点的指针存放在第二层第i个分支中的第hi个值v