• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Proceedings of the 2008 international conference on parallel and distributed processing techniques and applications >Two Parallel Algorithms to Solve the 2D Knapsack Problem Using GPUs
【24h】

Two Parallel Algorithms to Solve the 2D Knapsack Problem Using GPUs

机译：使用GPU解决2D背包问题的两种并行算法

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper describes two parallel algorithms for the 2D knapsack (or cutting-stock) problem which is the optimal packing of multiples of n rectangular objects into a knapsack of size L × W and are only obtainable with guillotine-type (side to side) cuts. Here, we describe and analyze this problem for parallel computing with GPUs. These algorithms solve this NP class problem with a parallel algorithm that runs in O(W(n+L+W)) time using L processors, where L≥W for a 2D knapsack problem with a capacity of L × W. The new multiple IS version using LW processors and max(L,M) ISs runs in O(n+L+W) given practical hardware considerations. Both of these results are cost optimal with respect to the best sequential implementation. Moreover, an efficient GPGPU algorithm for this well-known problem should give insight to how the parallel computing using graphics processing units compares to other parallel models such as PRAM.
机译：本文针对二维背包问题（或切削刀具）描述了两种并行算法，这是将n个矩形物体的多个以最佳方式打包成L×W尺寸的背包的最佳算法，并且只能通过断头台型（左右）切口获得。在这里，我们描述并分析了使用GPU进行并行计算的问题。这些算法通过使用L个处理器以O（W（n（L + L + W））时间运行的并行算法解决了NP类问题，其中L≥W用于容量为L×W的二维背包问题。考虑到实际的硬件考虑，使用LW处理器和max（L，M）IS的IS版本在O（n + L + W）中运行。就最佳顺序实施而言，这两个结果在成本上都是最优的。此外，针对此众所周知的问题的有效GPGPU算法应使人深刻了解使用图形处理单元的并行计算与其他并行模型（例如PRAM）的比较。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号