【优秀硕士博士论文】基于gpu的哈希表建立及其应用

基于GPU的哈希表建立及其应用,四川大学.计算机学院.11级硕士研究生毕业论文答辩,研究背景及意义开地址法建表及其实验链地址法建表及其应用杜鹃哈希建表及其应用LSH哈希算法介绍及其应用,主要内容,2,应用领域广泛计算机密码学、病毒检测、信息安全等各领域发展需求 建立哈希表速度及查找速度不能满足需求GPU构架的发展 CUDA（Compute Unified Device Architecture，统一计算设备架构）,研究背景及意义,3,串行建立开地址哈希表,B,E,Z,Y,A,哈希表,哈希函数h(x),A,开地址法建表,4,并行建立开地址哈希表CUDA提供高的存储器带宽CUDA提供原子操作,？,B,A,哈希表,哈希函数h(x),E,Z,Y,B,E,Z,Y,A,开地址法建表,5,实验测试数据32bit（unsigned int 类型）整数互不重复且键是数据本身,开地址法建表,6,二次探测函数建表,串行链地址哈希,A,链式哈希表,B,W,E,K,M,P,N,D,哈希函数h(x),A,链地址法建表,7,链表不适于GPU链表结点包括两个域，而某些存储器空间相对有限查询一个数据时，需从链表表头开始多个线程同时在同一链表中插入数据时，需要串行执行,8,链地址法建表,并行链地址哈希,0,3,3,5,8,A,索引数组,哈希函数h(x),B,W,E,K,M,P,N,A,D,0,1,2,3,4,5,6,7,8,哈希表,9,链地址法建表,索引数组,哈希表,基数排序,A,B,D,E,K,M,P,N,W,3,0,4,0,2,2,3,3,0,B,W,E,K,M,A,P,N,D,0,0,0,2,2,3,3,3,4,0,1,2,3,4,5,6,7,8,0,3,3,5,8,A,B,D,E,K,M,P,N,W,3,0,4,0,2,2,3,3,0,B,W,E,K,M,A,P,N,D,0,0,0,2,2,3,3,3,4,0,1,2,3,4,5,6,7,8,0,3,3,5,8,哈希函数h(x),链地址法建表,10,字符串去重的应用片段数量巨大重复数量多 增加系统拼接难度,并行链地址哈希应用,11,xM_QwGhWMIu642/1 TAAGGAGCAAGGGCTTGACATCAAACCGCGAATCCTCATTATAACTAGGTTGCTGCCTGNTGCTGTT+ bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbcccbcbbbcbccccl_Zw2wYMIu642/1 AAAAAGCACGGATNCATTTGAGATGTCTGAGTTAAACTATAGCAATNAAGCACAGCAGAGTGCTTG+ bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbcbbbbbbbbbbbccbccccbccccaca,基因序列片段,字符串去重的应用选择字符串哈希函数h(x)：BKDRHASH函数引入辅助数组进行基数排序,并行链地址哈希应用,引入辅助数组,12,字符串去重的应用,并行链地址哈希应用,13,以重排辅助数组作为索引查找对应字符串,Trie去掉重复序列字符串存在于Trie树字符串不存在于Trie树,A,C,G,N,T,A,C,G,N,T,A,C,G,N,T,A,C,G,N,T,A,C,G,N,T,A,C,G,N,T,A,C,G,N,T,A,C,G,N,T,A,C,G,N,T,14,并行链地址哈希应用,AGNC,GNGA,字符串去重效率对比,并行链地址哈希应用,Trie树与并行链地址哈希法效率对比,并行链地址哈希应用,局限性数据的不可扩展性需要额外存储空间需要哈希函数均匀分布数据,串行杜鹃哈希杜鹃哈希表由几个子表构成每个子表拥有各自的哈希函数,A,A,A,P,N,G,A,h1(x),h2(x),h3(x),A,A,P,P,哈希表,哈希表,17,杜鹃哈希建表,并行杜鹃哈希,A,M,A,M,C,A,M,C,N,P,C,A,M,N,P,C,N,N,P,A,M,C,N,A,P,P,A,18,杜鹃哈希建表,双层杜鹃哈希结构,P,D,A,Y,N,E,C,M,Z,B,P C A M N,B D E Z Y,A,M,Z,Y,线程块1,线程块2,P,C,M,A,N,B,D,E,Z,Y,共享存储器,共享存储器,全局存储器,哈希函数g(x),19,杜鹃哈希建表,逻辑结构,物理结构,杜鹃哈希表的应用,20,KNN(k-Nearest Neighbor algorithm)查找K个最近邻归类,局部敏感哈希介绍LSH哈希函数：x为高维数据向量a服从标准正太分布N（0，1）W为大于0的常数，是投影的量化宽度b在区间0，W内服从均匀分布,LSH哈希函数,杜鹃