From Sequential Algorithm Selection to Parallel Portfolio Selection
From Sequential Algorithm Selection to Parallel Portfolio Selection
复制标题
从顺序算法选择到并行投资组合选择
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
F. Hutter
中科院分区：
文献类型：
--
作者：
M. Lindauer;H. Hoos;F. Hutter
鉴于硬件并行性的重要性日益增加，对每实例算法选择的自然扩展是根据给定问题实例的特征选择一组并行运行的算法。在这里，我们探讨如何现有的算法选择技术可以有效地并行化。为此，我们利用现有顺序算法选择器（如3S、ISAC、SATzilla和ME-ASP）使用的机器学习模型，并修改其选择程序，以产生给定候选算法的排名；然后，我们选择这个排名下的前n个算法，在n个处理单元上并行运行。此外，我们调整了由速度获得的预求解计划，使其在每个处理单元具有不同时间预算的并行设置中有效。我们的实证结果表明，使用4个处理单元，我们的最佳方法在算法选择库中的一系列具有挑战性的场景中实现了比最佳单个求解器平均12倍的加速。
In view of the increasing importance of hardware parallelism, a natural extension of per-instance algorithm selection is to select a set of algorithms to be run in parallel on a given problem instance, based on features of that instance. Here, we explore how existing algorithm selection techniques can be effectively parallelized. To this end, we leverage the machine learning models used by existing sequential algorithm selectors, such as 3S, ISAC, SATzilla and ME-ASP, and modify their selection procedures to produce a ranking of the given candidate algorithms; we then select the top n algorithms under this ranking to be run in parallel on n processing units. Furthermore, we adapt the pre-solving schedules obtained by aspeed to be effective in a parallel setting with different time budgets for each processing unit. Our empirical results demonstrate that, using 4 processing units, the best of our methods achieves a 12-fold average speedup over the best single solver on a broad set of challenging scenarios from the algorithm selection library.
影响因子：
14.4
作者：
Hutter, Frank;Xu, Lin;Leyton-Brown, Kevin
通讯作者：
Leyton-Brown, Kevin