Instance-Specific Accelerators for Minimum Covering
Instance-Specific Accelerators for Minimum Covering
复制标题
用于最小覆盖范围的特定于实例的加速器
DOI：
10.1023/a:1024443416592
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
M. Platzner
中科院分区：
文献类型：
--
作者：
Christian Plessl;M. Platzner
本文提出了加速的最小成本覆盖问题的实例特定的硬件。首先，我们制定了最小成本覆盖问题，并讨论了一个分支和定界算法来解决它。然后，我们描述了具体的硬件架构，实现分支和定界的三值逻辑和使用减少技术类似的软件求解器。我们进一步提出了原型加速器实现和相应的设计工具流。我们的实验揭示了显着的原始加速高达五个数量级的一组较小的unate覆盖问题。只要硬件编译时间可以减少，我们的结论是，实例特定的加速硬最小成本覆盖问题将导致大量的整体加速。
This paper presents the acceleration of minimum-cost covering problems by instance-specific hardware. First, we formulate the minimum-cost covering problem and discuss a branch & bound algorithm to solve it. Then we describe instance-specific hardware architectures that implement branch & bound in 3-valued logic and use reduction techniques similar to those found in software solvers. We further present prototypical accelerator implementations and a corresponding design tool flow. Our experiments reveal significant raw speedups up to five orders of magnitude for a set of smaller unate covering problems. Provided that hardware compilation times can be reduced, we conclude that instance-specific acceleration of hard minimum-cost covering problems will lead to substantial overall speedups.