《基于分治策略的背包问题gpu并行算法研究》由会员分享，可在线阅读，更多相关《基于分治策略的背包问题gpu并行算法研究（74页珍藏版）》请在金锄头文库上搜索。
1、学校代号：1 0 5 3 2 学 密 号G 0 7 1 0 0 0 1 4 级：普通 湖南大学工程硕士学位论文 基于分治策略的背包问题 G P U 并行算法研究 诠室提童日期；2 Q1 2 生3 旦1 2 旦 诠室签避旦期；2 Q i 2 生三旦2 垒旦 哪| I I | f l | | l | | I I | | I | I | I i I | l | I I | I I f I I l I I Y 2 0 6 5 9 81 R e s e a r c ho nt h eG P UP a r a l l e lA l g o r i t h mo ft h eK n a p s a c kP
2、 r o b l e m B a s e do nD i V i d ea n dC o n q u e r b y J I A N G H a n y a n g B E ( H u n a nN o m a lU n i V e r s i t y ) 2 0 0 1 At h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e R e q u i r e m e n t sf 0 rt h ed e g r e eo f M a s t e ro fe n g i n e e r i n g I
3、n C o m p u t e rt e c h n o l o g y i nt h e G r a d u a t eS c h o o l o f H u n a n U n i V e r s i t y S u p e r V i s o r P r o f e s s o rL IK e n l i S e n i o re n g i n e e rS H E N Y a n i n g M a r c h ，2 0 1 2 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任
4、 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名轷形 日期：加矿年争月，咱 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密瓯 ( 请在以上相应方框内打“、 ) 作
5、者签名厂，；跚 别磁一吃心 日期：扣乡年垆月，二 日 日期：小卯汐年午月夕日 基于分治策略的背包问题G P U 并行算法研究 摘要 0 1 背包问题是运筹学中一种典型组合优化的N P 难问题。国内外很多研究人 员一直在潜心扩展和深化研究该问题，到目前为止，还没有找到一个能在线性时 间内求解的算法，但由于其在实际应用领域中具有重要的价值，所以国内外学者 一直都很重视如何降低求解该类问题的计算成本。 近年来，随着并行处理技术的日趋成熟，求解0 1 背包问题的算法由传统的串 行算法逐步转向并行算法的研究，且已经成为该领域的研究热点。目前主要有动 态规划法和分治法两种并行算法解决0 1 背包问题，其中
6、不少学者已经在动态规划 并行算法方面的研究上取得了大量的研究成果，但是在分治并行算法方面的研究 不如前者。 本文在深入研究C U D A 并行计算模型和基于分治策略的并行算法的基础上， 分析了求解0 1 背包问题的串行二表算法，并提出了基于C P U + G P U 异构编程模 型求解0 1 背包问题的并行二表算法，详细分析了二表算法的的子集和生成子算 法、求块内最值和并行剪块子算法和解的并行搜索子算法的基本思想和算法的设 计流程，在每一个并行子算法的设计过程中，将各算法的并行任务分配到G P U 中 的相应的各线程中，从而实现算法的并行计算。在只考虑背包物品规模这一个因 素成本最优的情况下对
7、算法进行理论上的性能分析和比较，该算法完全避免了 G P U 存储器访问冲突的问题。 最后，本文基于C P U + G P U 异构编程模型对0 1 背包问题的并行二表算法进 行了编程实验，并对实验进行反复测试，从而比较了在传统的基于C P u 编程模型 工程硕t = 学位论文 A b s t r a c t T h e0 一l k n a p s a c kp r o b l e mi sak i n do ft y p i c a lp o r t f o l i oo p t i m i z a t i o nN P h a r d p r o b l e m M a n yd o m
8、e s t i ca n df o r e i g nr e s e a r c h e r sh a v e b e e nc o n c e n t r a t e di nt h e e x t e n d i n ga n dd e e p e n i n gt h es t u d yo ft h ep r o b l e m ，a n dh a V en o tf o u n das o l v i n g a l g o r i t l l n li nl i n e a rt i m es of a r b u ti th a si m p o I r t a n ta p p
9、 l i c a t i o nv a l u ei nt h ep r a c t i c a l a p p l i c a t i o nf i e l d ，s ot h ed o m e s t i ca n do v e r s e a ss c h o l a r sh a v eb e e ne m p h a s i z e dh o wt o r e d u c ec o m p u t a t i o nc o s to fs o l V i n gt h ep r o b l e m I nr e c e n ty e a r s ，w i t ht h em a t
10、u r eo ft h ep a r a l l e lp r o c e s s i n gt e c h n o l o g y ，s o l v i n g 0 lk n a p s a c kp r o b l e mb yt h et r a d i t i o n a ls e r i a la l g o r i t h mh a sb e e ng r a d u a l l yt u m i n gt o t h ep a r a l l e la l g o r i t h mo fr e s e a r c h ，a n dh a sb e c o m eah o ti
11、s s u ei nt h i sf i e l d T h e r ea r e t w ok i n d so fm e t h o d so fs o l V i n gi t ：d y n a m i cp r o g r a m m i n gm e t h o da n dd i v i d ea n d c o n q u e ra l g o r i t h m Al o to fs c h o l a r sh a V eg o tm a n yr e s u l t sb yd y n a m i cp r o g r a m m i n g ， b u tt h e yg
12、 o tl e s sb yt h el a t t e r B a s e do nt h et h o r o u g hs t u d yo fC U D A p a r a l l e lc o m p u t i n gm o d e la n dt h ep a r a l l e l a l g o r i t h mb a s e do np a r t i t i o ns t r a t e g i e s ， t h ep a p e ra n a l y z e dt h et w ol i s ts e r i a l a l g o r i t h mo fs o
13、l V i n g0 1k n a p s a c kp r o b l e m s ，a n dp u tf b r w a r dp a r a l l e la l g o r i t h mo f t w ol i s tb a s e do nt h eC P U + G P U h e t e r o g e n e o u sp r o g r a m m i n gm o d e lf 0 rs o l v i n g k n a p s a c kp r o b l e m ，a n da n a l y z e dt h et w ol i s ta l g o r i t
14、 h ma n dt h eg e n e r a t i o no ft h e s u b s e to ft h ea l g o r i t h m ，ab l o c kf o rt h em o s tV a l u ea n dp a r a l l e lc u tp i e c e sa l g o f i t h mo f p a r a l l e ls e a r c ha l g o r i t h ma n dt h es o no ft h eb a s i ci d e a sa n da l g o r i t h md e s i g np r o c e
15、s s A n di ne a c hd e s i g n i n gp r o c e s so ft h es o no ft h ep a r a l l e la l g o r i t h m ，t h ep a r a l l e lt a s k s a r ed i s t r i b u t e si n t or e s p e c t i V ep r o g r a m m i n gi nG P Ut or e a l i z es u c hc a l c u l a t i n g I nt h e o n I yc o n s i d e r a t i o
16、no ft h eb a c k p a c ki t e m ss c a l et h eo p t i m a lc o s tf a c t o r so ft h e p e r f o 加a n c eo ft h ea l g o r i t h mt h e o r ya n a l y s i sa J l dc o m p a r i s o n ，t h ea l g o r i t h ma v o i d e d G P Um e m o r ) ra c c e s sc o n f l i c tc o m p l e t e l y F i n a l l y t h i sp a p e r ，b a s e do nt h eC P U + G P Uh e t e r o g e n e o u sp r o g r a m m i n gm o d e l f o r0 - l k n a p s a c kp r o b l e m
