• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE International Symposium on Computer Architecture and High Performance Computing >A Parallelization of a Simulated Annealing Approach for 0-1 Multidimensional Knapsack Problem Using GPGPU
【24h】

A Parallelization of a Simulated Annealing Approach for 0-1 Multidimensional Knapsack Problem Using GPGPU

机译：使用GPGPU求解0-1多维背包问题的模拟退火方法的并行化。

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In the last decades, with the advances in multicore/manycore architectures, it became interesting to design algorithms which can take advantage of such architectures aiming the achievement of more efficient algorithms to solve difficult problems. A large number of real-world problems solved with the help of computer programs demand faster or better quality solutions. Some of these problems can be modeled as classical theoretical problems, such as the 0-1 multidimensional knapsack problem (0-1 MKP), known to belong to the NP-hard class of problems, for which we can not obtain an exact solution efficiently. This motivates the search for alternative strategies which can achieve good quality approximate solutions, like metaheuristics, and also different ways to enable their execution in reduced times, such as parallel algorithms which explore multicore/manycore architectures. In this work we describe a parallelization of a simulated annealing approachusing GPGPU to solve 0-1 MKP and compare our results to previous works in order to prove the viability of its use.
机译：在过去的几十年中，随着多核/多核体系结构的发展，设计可以利用这种体系结构以实现更有效的算法来解决难题的算法变得很有趣。在计算机程序的帮助下解决的大量现实问题需要更快或更优质的解决方案。可以将这些问题中的一些建模为经典理论问题，例如0-1多维背包问题（0-1 MKP），已知它属于NP-困难类问题，对于这些问题，我们无法有效地获得精确的解决方案。这激发了人们寻求替代策略的可能性，这些策略可以实现高质量的近似解决方案，例如元启发法，以及实现缩短执行时间的不同方式，例如探索多核/多核体系结构的并行算法。在这项工作中，我们描述了使用GPGPU解决0-1 MKP的模拟退火方法的并行化，并将我们的结果与以前的工作进行比较，以证明其使用的可行性。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号