（计算机应用技术专业论文）基于分治思想01背包问题的并行算法研究.pdf

1 r e s e a r c ho nt h ep a r a l l e la l g o r i t h m so fo 一1k n a p s a c kp r o b l e mb a s e d o nd i v i d ea n dc o n q u e r b y l il i n g x i a o b e ( h u n a nu n i v e r s i t y ) 2 0 0 8 at h e s i ss u b m i n 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 o 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 c o m p u t e ra p p l i c a t i o n 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 m a y , 2 0 1 1 3肼9m 2 圳60川9 -脚y 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名： 毒婚 日期：z o f 年岁月f 寥日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签 导师签 日期：z 口年歹月i g 日 f j 期：0 - o l 1 年s 月f8f j 硕士学位论文 摘要 0 1 背包问题是一种经典的n p 难问题，目前还无法找到线性时间内求解该问 题的算法，由于求解0 1 背包问题在优化组合、资本预算、货物装载、削减库存以 及信息密码学等领域具有极为重要的应用，因此，降低求解该类问题的计算成本 具有重大的理论和现实意义，并引起了各国学者的极大重视。 随着并行计算技术的逐步成熟，人们将求解0 1 背包问题的重点转向并行算法 的研究，当前解决0 1 背包问题的并行算法主要分为动态规划法和分治法两种思 路，其中动态规划法已经成功运用到了0 1 背包问题的并行算法中，并已经涌现出 大量的研究成果。不过至今为止分治法主要运用到求解子集和问题中，而基于分 治思想设计求解0 1 背包问题的并行算法并没有引起同样的关注。因此，在深入研 究了p r a m 并行计算模型和并行分治思想后，本文给出了求解0 1 背包问题的串行 二表算法和串行三表算法，并创新性的提出了两种基于e r e wp r a m 模型求解o 1 背包问题的并行算法即并行三表算法和并行二表算法，并对算法进行理论上的性 能分析和比较，其中并行三表算法比并行二表算法占用较少的储存空间，而并行 二表算法则是迄今为止求解o 1 背包问题算法性能分析中，仅考虑背包物品规模这 一个因素成本最优且完全避免内存访问冲突的并行算法。 最后，本文分别基于o p e n m p 和m p i + o p e n m p 编程模型对o 1 背包问题并行二 表算法进行了编程实验，并对实验进行反复测试，从而比较了不同多核平台环境 下并行程序运行时间的差异以便分析并行算法的性能。实验结果很好的证明了基 于o p e n m p 编程模型并行二表程序在减少程序运行时间方面的可行性，且程序表 现出较好的加速比和并行效率。 关键词：0 - 1 背包问题；并行算法；分治法；剪枝技术；e r e wp r a m , o p e n m p l l 基于分治思想0 - 1 背包问题的并行算法研究 a b s t r a c t t h eo 1k n a p s a c kp r o b l e mi sw e l lk n o w nt ob en p - h a r dp r o b l e m n o wi ti s u n l i k e l yt ob es o l v e di np o l y n o m i a lt i m e b e c a u s eo fi t si m p o r t a n c ei nc o m b i n a t o r i a l o p t i m i z a t i o na n di t sv a r i e dp r a c t i c a la p p l i c a t i o n si nc a p i t a lb u d g e t i n gp r o b l e m ，c a r g o l o a d i n gp r o b l e m ，c u t t i n gs t o c kp r o b l e ma n dc o m p u t e rc r y p t o s y s t e m ，r e d u c i n gt h e c o m p u t i n g c o s t so f s o l v i n g t h i s p r o b l e mh a sg r e a t t h e o r e t i c a la n dr e a l i s t i c s i g n i f i c a n c e ，a n db e c o m eap r e s s i n gn e e df o rs c i e n t i s t sa n ds c h o l a r s a l o n gw i t ht h eg r a d u a ld e v e l o p m e n to fp a r a l l e lc o m p u t i n g ，p e o p l ea r ei n t e r e s t e d i nr e s e a r c h i n gt h ep a r a l l e la l g o r i t h m so ft h e 0 - 1k n a p s a c kp r o b l e m t h ep a r a l l e l a l g o r i t h m sf o r0 - 1k n a p s a c kp r o b l e mc a nb ec l a s s i f i e di n t ot w om e t h o d s ：t h ed y n a m i c p r o g r a m m i n ga n dt h ed i v i d ea n dc o n q u e r n o w , t h ed y n a m i cp r o g r a m m i n gh a sb e e n s u c c e s s f u l l ya p p l i e dt ot h ep a r a l l e la l g o r i t h m sf o rt h e0 1k n a p s a c kp r o b l e m ，a n dh a s e m e r g e di nal o to fr e s e a r c h b u tt oo u rk n o w l e d g et h ep a r a l l e lm e t h o do fd i v i d ea n d c o n q u e rm a i n l yh a sa p p l i e dt os o l v i n gt h es u b s e tp r o b l e m ，a n dn o tb e e na p p l i e d s u c c e s s f u l l yt os o l v i n gt h e0 1k n a p s a c kp r o b l e m t h e r e f o r e ，b a s e do nt h o r o u g hs t u d y o ft h ep r a m 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 lm e t h o do f d i v i d ea n dc o n q u e r ， t h i sp a p e ri n t r o d u c e st h et h r e el i s ts e r i a la l g o r i t h ma n dt h et w ol i s ts e r i a la l g o r i t h mf o r t h e0 - 1k n a p s a c kp r o b l e m ，a n db a s eo ne r e wp r a mp a r a l l e lc o m p u t i n gm o d e l p r o p o s e st w on e wp a r a l l e la l g o r i t h m sf o rt h e0 - 1k n a p s a c kp r o b l e m ，n a m e dt h et h r e e l i s t p a r a l l e la l g o r i t h m sa n dt h et w ol i s tp a r a l l e la l g o r i t h m s ，t h e na n a l y z e s a n d c o m p a r e st h ep e r f o r m a n c eo ft h ea l g o r i t h m si nt h e o r y t h ef o r m e rt a k eu pl e s s m e m o r ys t o r a g es p a c et h a nt h el a t t e r , a n dt h el a t t e ri sb o t ht h el o w e s tu p p e r b o u n d t i m ea n dw i t h o u tm e m o r yc o n f l i c t si fo n l yq u a n t i t yo fo b j e c t si sc o n s i d e r e di nt h e c o m p l e x i t ya n a l y s i sf o rt h e0 - 1k n a p s a c kp r o b l e m i nt h ee n d ，t h i sp a p e rs e p a r a t e l yu s eo p e n m pa n dm p i + o p e n m pp r o g r a m m i n g m o d e lt od e s i g ne x p e r i m e n to ft h et w ol i s tp a r a l l e la l g o r i t h m sf o r0 1k n a p s a c k p r o b l e m ，a n dt e s tt h ee x p e r i m e n tr e p e a t e d l y t h u sc o m p a r e st h ed i f f e r e n c eo ft h e t i m e c o n s u m i n ga n dp a r a l l e l i z a t i o np e r f o r m a n c eo ft h ea l g o r i t h m su n d e rt h ed i f f e r e n t m u l t i c o r ec i r c u m s t a n c e s t h ee x p e r i m e n tr e s u l t ss h o wt h a to u rp r o p o s e dp a r a l l e l a l g o r i t h m sn o to n l yh a v eg o o df e a s i b i l i t yt or e d u c et h ee x e c u t i o nt i m e ，b u ta l s eh a v e b e t t e rs p e e d u pa n dp a r a l l e le f f i c i e n c y i i i 一 i v 一 基于分治思想0 - 1 背包问题的并行算法研究 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要i i a b s t r a c t i i i 目录。v 插图索引v i i 附表索引v i i i 第l 章绪论。l 1 1 课题的研究背景与意义1 1 2 国内外研究水平与现状l 1 3 论文主要工作3 1 4 论文创新点及主要贡献3 1 5 论文组织结构4 1 6 ，j 、结4 第2 章并行计算机模型及并行程序设计5 2 1 并行计算5 2 1 1 并行计算机模型5 2 1 2 并行求解模型6 2 2 并行编程语言_ 7 2 2 1 基于共享存储结构的o p e n m p 并行编程7 2 2 2 基于消息传递的m p i 并行编程8 2 3 并行算法的性能评价8 2 4 ，j 、结9 第3 章0 1 背包问题并行三表算法设计1 1 3 1 串行三表算法设计1 1 3 2 最优归并算法1 3 3 3 并行三表算法思想与算法设计1 5 3 3 1 生成阶段1 5 3 3 2 求块内最值阶段1 7 3 3 3 剪块阶段l8 3 3 4 搜索阶段2 2 3 4 算法性能分析2 4 v 硕士学位论文 3 5 小结2 5 第4 章o 1 背包问题并行二表算法设计。2 6 4 1 串行二表算法设计2 6 4 2 并行二表算法思想与算法设计。2 7 4 2 1 生成阶段。2 7 4 2 2 求块内最值阶段2 9 4 2 3 剪块阶段3 0 一， 4 2 4 搜索阶段3 2 4 3 并行二表算法处理机数目的自适应3 3 4 4 算法性能分析与比较3 4 4 4 1 算法性能分析3 4 4 4 2 算法性能比较3 4 4 5 小结3 6 第5 章o 1 背包问题并行二表算法程序实验一3 7 5 1 基于m p i + o p e n m p 模型o 1 背包问题并行二表程序3 7 5 1 1 m p i + o p e n m p 混合模型3 7 5 1 2 基于m p i + o p e n m p 混合模型并行二表算法程序设计3 8 5 1 3 实验结果分析。3 9 5 2 基于o p e n m p 模型0 1 背包问题并行二表程序4 0 5 2 1 o p e n m p 并行编程模型4 l 5 2 2 基于o p e n m p 编程模型并行二表算法程序设计4 l 5 2 3 实验结果分析4 7 5 3 小结5l 结 论5 2 参考文献5 4 致 射5 8 附录a 攻读硕士期间发表论文目录5 9 附录b攻读硕士期间参加的科研项目6 0 v 1 图3 3 并行三表算法剪块阶段流程一2 0 图3 4 处理机只的搜索范围2 2 图3 5 基于e r e w p r a m 模型0 1 背包问题并行三表算法2 4 图4 1 表x 的归并流程2 9 图4 2 表x 、】，的组织结构3 0 图5 1m p i + o p e n m p 混合编程模型3 8 图5 2 基于m p i + o p e n m p 模型并行二表算法生成阶段程序设计3 9 图5 3 基于m p i + o p e n m p 模型并行二表算法其余阶段程序设计4 0 图5 4o p e n m p 的f o r k j o i n 并行执行模型4 l 图5 5 基于o p e n m p 表x 生成阶段程序设计4 2 图5 6 基于o p e n m p 求块内最值阶段程序设计4 3 图5 7 基于o p e n m p 剪块阶段程序设计4 5 图5 8 基于o p e n m p 搜索阶段程序设计4 6 图5 9 八核w i n d o w s 环境下不同并行线程数目程序的总执行时间。5 0 图5 1 0 八核w i n d o w s 环境下不同并行线程数目程序的加速比5 0 图5 1 l 八核w i n d o w s 环境下不同并行线程数目程序的并行效率5 0 【一 v u 表2 2m p i 的六个基本调用8 表2 3m p i 和o p e n m p 比较9 表4 10 1 背包问题并行算法性能比较3 5 表5 1 四核环境下生成阶段程序的性能分析4 2 表5 2 八核环境下生成阶段程序的性能分析。4 3 表5 3 四核环境下求块内最值阶段程序的性能分析4 4 表5 4 八核环境下求块内最值阶段程序的性能分析4 4 表5 5 八核环境下剪块阶段程序的性能分析4 5 表5 6 四核环境下搜索阶段程序的性能分析。4 6 表5 7 八核环境下搜索阶段程序的性能分析4 7 表5 8 双核p c 环境下程序的性能分析4 8 表5 9 四核p c 环境下程序的性能分析4 8 表5 1 0 八核l i n u x 环境下程序的性能分析4 9 表5 1 l 八核w i n d o w s 环境下程序的性能分析4 9 v i i i 基于分治思想0 - 1 背包问题的并行算法研究 第1 章绪论 1 1 课题的研究背景与意义 经典的背包问题包括0 1 背包问题和子集和问题。o 1 背包问题可描述如下： 给定刀件物品k l ，娩，毛，背包的容量为m ，其中第f 件物品的重量为岛w ，价 值为k i p ，l f 刀，问题求解将哪些物品放入到背包中使得这些物品的重量之和 不超过背包容量且价值之和最大【l 】。子集和问题可描述如下：给定拧个正整数 肛( 七l 恕，厶) 和正整数m ，问题判断是否存在k 的一个子集s ，使的s 中的各 元素之和等于材引。众所周知，o 1 背包问题和子集和问题分别属于n p 难问题和 n p 完全问题，当前还无法找到线性时间内求解该问题的算法【3 l ，而直接穷举搜索 问题所有可能的解空间在最坏情况下的时间复杂度为0 ( 2 刀) 。由于0 1 背包问题在 优化组合、削减库存、货物装载、资本预算以及信息密码学领域等具有极为重要 的应用 4 1 ，故设计新的算法降低求解该类问题计算成本具有重要的理论和实际意 义。 随着并行计算技术的逐步成熟，人们逐渐将求解背包问题的研究重点转向并 行算法，这些研究工作既包括基于共享存储结构的多核计算机模型，也有基于分 布式存储的集群系统，特别是基于p r a m 共享存储计算模型，求解子集和问题的 并行算法已经涌现出较多的科研成果，但遗憾的是，至今为止针对0 1 背包问题， 利用分治思想设计基于p r a m 共享存储计算模型的并行算法并没有引起同样的 关注。尽管p r a m 计算模型仅是一种理论模型，但过去基于该模型所取得科研成 果表明它对于设计和实现并行算法仍然具有重要的理论意义。 如今随着计算机运算速度的大幅度提高，多核技术的日臻成熟以及其低廉的 价格使得共享存储结构的多核计算机已经普及，并且它与功能日趋完善的并行编 程语言一起成为设计并行程序的主要软硬件平台。因此，在低价的多核计算机平 台环境下，针对求解0 1 背包问题并行算法进行编程实验，从而研究该算法的实 际并行效率具有很大的现实意义。 1 2 国内外研究水平与现状 求解0 1 背包问题和子集和问题通常可以分成两种思路：其一是基于动态规 划法思想，另一种是基于分治法思想。前者是由b e l l m a n 提出的动态规划算法【5 1 ， 利用动态规划算法求解o l 背包问题的时间和空间复杂度为o ( n m ) 。在此类思想 基础上人们发表了许多解决o 1 背包问题的并行算法论文【6 - 1 4 1 ，例如g o l d m a na n d 硕七学位论文 t r y s t r a m