• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Symposium on Computer Architecture and High Performance Computing Workshop >A Benchmark on Multi Improvement Neighborhood Search Strategies in CPU/GPU Systems
【24h】

A Benchmark on Multi Improvement Neighborhood Search Strategies in CPU/GPU Systems

机译：CPU / GPU系统中的多重改进邻域搜索策略基准

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

摘要

In combinatorial optimization problems, the neighborhood search (NS) is a fundamental component for local search based heuristics. It consists of selecting a solution from a high cardinality set of neighbor solutions, by means of operations called moves. To perform this search, NS algorithms usually adopt two main approaches: selecting the first or best improving move. The Multi Improvement (MI) strategy is a recently proposed method that consists in exploring simultaneously multiple move operations during the NS phase aiming to reach good quality solutions with shorter computational steps. This paper presents a benchmark for MI strategies in hybrid CPU/GPU systems. This technique efficiently explores the CPU processing power together with the massive parallelism achieved by modern GPUs, emerging as an efficient alternative for classic CPU neighborhood search strategies. The advantage of this approach depends heavily on finding the best tradeoff between CPU and GPU processing, as well as minimizing the memory transfers involved in the process. In the experiments, several MI configurations were tested in a hybrid CPU/GPU environment presenting better results than classical neighborhood search strategies for the Minimum Latency Problem, a hard combinatorial optimization problem.
机译：在组合优化问题中，邻域搜索（NS）是基于本地搜索的启发式算法的基本组成部分。它包括通过称为移动的操作从一组高基数的邻近解决方案中选择一个解决方案。为了执行此搜索，NS算法通常采用两种主要方法：选择第一个或最佳改进方法。多重改进（MI）策略是最近提出的一种方法，该方法包括在NS阶段同时探索多个移动操作，旨在以较短的计算步骤来获得高质量的解决方案。本文提出了混合CPU / GPU系统中MI策略的基准。这项技术有效地探索了CPU的处理能力以及现代GPU所实现的大规模并行性，成为传统CPU邻域搜索策略的有效替代方案。这种方法的优势在很大程度上取决于在CPU和GPU处理之间寻找最佳折衷，以及最大程度地减少该过程中涉及的内存传输。在实验中，在混合CPU / GPU环境中测试了几种MI配置，与针对最小延迟问题（一种硬的组合优化问题）的传统邻域搜索策略相比，其结果要好得多。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号