TY - JOUR
AB - 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.
AU - Plessl, Christian
AU - Platzner, Marco
ID - 2420
IS - 2
JF - Journal of Supercomputing
KW - reconfigurable computing
KW - instance-specific acceleration
KW - minimum covering
SN - 0920-8542
TI - Instance-Specific Accelerators for Minimum Covering
VL - 26
ER -
TY - CONF
AB - In this paper we present instance-specific accelerators for minimum-cost covering problems. We first define the covering problem and discuss a branch&bound algorithm to solve it. Then we describe an instance-specific hardware architecture that implements branch&bound in 3-valued logic and uses reduction techniques usually found in software solvers. Results for small unate covering problems reveal significant raw speedups.
AU - Plessl, Christian
AU - Platzner, Marco
ID - 2428
KW - minimum covering
KW - accelerator
KW - funding-sundance
T2 - Proc. Int. Conf. on Engineering of Reconfigurable Systems and Algorithms (ERSA)
TI - Instance-Specific Accelerators for Minimum Covering
ER -