《基于gpu的近似字符串匹配并行算法的研究》由会员分享，可在线阅读，更多相关《基于gpu的近似字符串匹配并行算法的研究（88页珍藏版）》请在金锄头文库上搜索。
1、中文摘要 中文摘要中又于两矍 图形处理器( G P U ) 具有很强的并行处理能力，并且设备成本低，利用G P U 加速字符串操作已经成为了当前并行计算领域的研究热点。近似字符串匹配技术 在病毒检测、文件检索、计算生物学等很多领域都有着广泛的应用，传统的串行 算法运算速度慢，而现存的并行算法都是基于多处理器模式，计算设备成本很高， 耗电量大。因此，在G P U 上研究有效的近似字符串匹配并行算法具有重大的实际 意义。本文的主要研究内容及贡献如下： 首先，对G P U 通用计算的编程环境进行了总结，重点研究了N V I D I AC U D A 的 工作原理，编程模型和存储器模型，以及如何配置c
2、 u D A 编程环境。 其次，对于允许肛m i s m a t c h 的近似字符串匹配问题，基于C u D A 模型，本文提 出了三种并行算法，即线程级并行算法，两级并行算法，以及两级并行优化算法。 两级并行优化算法在利用G P u 强大并行处理能力的同时，使得各线程负载均衡， 并且利用G P U 的存储器模型减少了每个线程对全局存储器中数据的访问次数。本 文使用真实的D N A 序列作为实验数据对算法的性能进行评估，实验结果表明，两 级并行优化算法在G P U 上的执行时间对于传统的C P U 端串行算法的加速比可达到 4 0 一8 0 ，加速比变化趋势与理论分析一致，其它两个算法的加速
3、比也可以达到7 1 0 。 最后，对于允许肛d i f f e r e n c e 的近似字符串匹配问题，基于动态规划的方法，通 过消除编辑距离矩阵中同一行数据间的依赖关系，本文提出了一个空间复杂度为 D ( I l 以) ，时间复杂度为D ( 盟圣尝坐) 的并行算法D A s M P ，2 为文本长度，m 为 模式长度，l I 为字典表集合的大小，M 为处理器个数。本文分别在G P u 和多核 c P u 上对算法进行了实现，并对两种环境下算法的加速比进行了分析。实验结果 表明，D A s M P 算法在G P u 上的执行时间对于传统的C P U 端串行算法的加速比可以 达到7 1 3 ，
4、在双核C P U 上算法的加速比可以达到1 3 ，在2 4 核c P U 上的加速比可以 达到8 1 2 ，并且加速比的变化趋势与理论分析一致。 关键字：近似串匹配，G P U ，并行算法，汉明距离，编辑距离 黑龙江大学硕士学位论文 A b s tr a c t G P Uh a sh i 曲p a r a l l e lp m c e s s i n gc a p a b i l i t ya n d1 0 wc o s to fe q u i p m e n t s A c c e l e r a t i n gs t r i n go p e r a t i o n so nG P Uh
5、 a sb e e nar e s e a r c hf o c u so np a r a l l e lc o m p u t i n g a u r e a A p p r o x i m a t es t r i n gm a t c h i n gt e c l u l i q u eh a sb e e nw i d e l ya p p l i e dt om a n y f i e l d s s u c ha sv i r u sd e t e c t i o n ，t e x tm i n i n ga I l dc o m p u t a t i o n a lb i o
6、 l o g y T h et r a d i t i o n a l s e q u e n t i a la l g o r i t sa r es l o w ，a n dm ep a r a l l e la l g o r i t I l l I l sa r ea Ub a s e do nm u l t i p l e p r o c e s s o r S ，w h i c hh a v eh i 曲c o s to fe q u i p m e n t sa n de n e 唱y T h e r e f o r e ，t h ee 行e c t i v e p a r a
7、l l e la l g o r i t l l mf o r 印p r o x i m a t es t r i n gm a t c h i n gh a ss i 印i f i c a l l tp r a c t i c a ls i 印i f i c a n c e T h em a i nr e s e a r c h sa n dc o n t r i b u t i o n so fm i st h e s i sa r ea sf o l l o w s F i r s t l y ，t h i sp a p e rs u m m a r i z e st h ep r o
8、伊a m m i n ge n v i r o m n e n tf o rG P G P U ，a n d s t u d i e st h ew o r k i n gp r i n c i p l e ，p r o 伊a m m i n gm o d e l ，s t o r a g em o d e la n dp r o g r a m m i n g e n V i r o n m e n tc o n f i g u r a t i o nm e m o do fC U D Ai nd e t a i l S e c o n d l y ，f o rt h ep r o b l
9、e mo f 肛m i s m a t c ha p p r o x i m a t es t i n gm a t c h i n g B a s e do n C U D A ，m i sp a p e rp r e s e n t st h r e ep a r a l l e la l g o r i t h m s ，n 锄e l y ，m et h r e a d p a r a l l e l a l g o r i t l l I n ，t h eb l o c k - m r e a dp a r a l l e la l g o r i t h m ，a 1 1 dt h
10、eO P T - b l o c k - t h r e a dp a r a l l e l a l g o r i t h m T h eO P l 乙b l o c k - t h r e a dp a r a U e la l g o r i t h mc a nt a k e 如l la d v a n t a g eo fm e p o w e r 如lp a r a l l e lc a p a b i l i t yo fG P U F u r t h e n n o r e ，i tb a l a j l c e st h el o a d 锄o n gm e t h r e
11、 a d sa n do p t i m i z e st h ee x e c u t i o nt i m ew i t hm em e m o r ym o d e lo fG P U T h i sp a p e r u s e sa c t u a l ) N As e q u e n c e sa se x p e r i m e n t a ld a t a ，a n dt h ee x p e r i m e n t a lr e s u l t ss h o wt h a t c o m p a r e dw i t ht h et r a d i t i o n a ls
12、e q u e n t i a la l g o r i t h mo nC P U ，t h eO P T - b l o c k t 1 1 r e a d p a r a l l e la l g o r i t h mo nG P U i nt h i sp a p e ra c h i e V e ss p e e d u po f4 0 一8 0 ，a n dt h es p e e d u pi s c o n s i s t e n tw i t ht h e o r e t i c a la n a l y s i s F u t h e m o r e ，t h eo t
13、h e ra l g o n t h m sa c h i e v et h e s p e e d u p so f 7 1 0 I nt h ee n d ，f o rt h ep r o b l e mo f 肛d i n e r e n c ea p p r o x i m a t es t i n gm a t c h i n g B a s e do n d ) ，n a m i cp r o 黟a m m i n gm e t h o d ，t h i sp a p e rp r e s e n t sap a m l l e la l g o r i t h mw h i c
14、hc a n 芒 A b s t r a c t c a l c u l a t em ee l e m e n t si nt h es a m er o wo ft h eE d i tD i s t a n c eM a t r i xi np a r a l l e lb y e l i m i l l a t i n gd a t ad 印e n d e n c y T h ea l g o r i m mr e q u i r e sD ( I l ，z )s p a c ea 1 1 d r u n si n D ( ( I I + m ) 以 ) t i m e ，w h e
15、r e ，z i sm el e n 舀ho fat e x t ，mi st h e1 e n 酉ho fap a t t e m ， Ii sm es i z eo fc h a r a c t e rs e t ，a n dMi sm ep r o c e s s e r s T h i sp a p e ra l s oi m p l e m e n t sm e a l g o r i t l l mo nG P U a n dm u l t i p l e c o r eC P U s ，a n da n a l y s e sm es p e e d u p so ft h ea
16、 l g o r i t h m u n d e rt w oe n v i r e m e n t s T h ee x p e r i m e n t a lr e s u l t ss h o wt h a tc o m p a r e dw i t l lt 1 1 e t r a d i t i o n a ls e q u e n t i a la l g o r i t h mo nC P U ，t 1 1 ep a r a l l e la l g o r i t h mp r o p o s e di nt h i sp 印e r a c h i e V e ss p e e d u po f7 13o nG P U ，1 3o nd u a l - c o r eC P U ，a n d8 12o nC P Uw i t l l t 、) l ，e n t y f o u rc o r e s F u t h e m o r e ，m es p e e d u p sa
